# Single-pass clustering algorithm for sparse matrices

I have written single pass clustering algo for reading sparse matrices passed from scikit tfidfvectoriser but the speed is king of average for medium size matrix. How can I scale for large size matrices?

I'm using Python 2.7.

from scipy.sparse import csr_matrix
import scipy
import sklearn
from sklearn.metrics.pairwise import cosine_similarity
import numpy as np
import pickle

def singlePassAlgorithm(threshhold):
docNo = 0

#variable to store the clusters
cluster = []

#variable to store the clusterRepresentations-centroids
clusterRepresentative = []

#initial no of cluster
noOfClusters = 1

#declared but intialised later on first read
noOfTokens=0

#Code to read from a file one line at a time without consuming memory
import os
cur_dir=os.path.dirname(__file__)
X = pickle.load(open(os.path.join(cur_dir,"N-Trimmed-N-Weighted",'vectorizer.pickle'), 'rb'))

#stores the current line read from the stream
#loop until no more entry exists in the stream
for fResult in X:
#TODO may be check for the number of dimension for every record
#handle blanks and nulls
#print row
if True :
# fResult=np.array([float(x) for x in row if x != ''])
# print fResult

#if first record
if docNo == 0:
#set no of tokens from single feature
noOfTokens = fResult.shape[1]
#parse the string feature into Float
#add the parsed record as the zeroth record
# i.e. since it is the first document read it can put into cluster
#as first cluster without any harm

cluster.append([docNo])

#convert the read features into float and add them to the clusterRepresentative Store as the first centroid
# Float[] temp = new Float[noOfTokens]
# temp = convertintArrToFloatArr(fResult)
clusterRepresentative.append(fResult)

else:

#it is not the first record...any other record
#parse it into float

#variable to capture the max similarity till now
max = -1#float
#variable to capture the max similarity clusterId
clusterId = -1
#since we are in else part we assume there are other cluster
#loop through every current cluster found till now to calculate the similarity and the cluster id

for  j in range(noOfClusters):
# compute the cosine similarity
similarity = calculateSimilarity(fResult, clusterRepresentative[j])
# check if greater than the threshold
if (round(similarity,2) > threshhold):
# check if greater than max
if (similarity > max) :
max = similarity
clusterId = j

if (max == -1) :
#case when the similarity value never crossed the threshold
#it means new cluster needs to be created
#add the current doc as new entry in to the cluster
cluster.append([docNo])
noOfClusters+=1
#add the current doc as new represenation for itself
clusterRepresentative.append(fResult)
else:
#else we found a candidate for merging with existing cluster
#cluster contains other docs so fetch them
values = cluster[clusterId]

#create a new array with size one
# int[] newValue = new int[1]
#add the newly found doc into the newValue
# newValue[0] = docNo

#merge both the values from the cluster ..old and the latest found
values.append(docNo)
cluster[clusterId]=values

#compute the new centroid representation for the newly modified cluster
clusterRepresentative[clusterId]=calculateClusterRepresentative(cluster[clusterId], fResult, clusterId, clusterRepresentative, noOfTokens)

if docNo % 100 == 0:
print(docNo)
docNo += 1

for i in range( noOfClusters):
print "\n" + str(i) + "\t"
for j in range(len(cluster[i])):
print cluster[i][j]
print cluster

# def convertintArrToFloatArr(input) {
# int size = input.length
# Float[] answer = new Float[size]
# for (int i = 0 i < input.length ++i) {
# answer[i] = (float) input[i]
# }
# }

def calculateSimilarity(vectorA,  vectorB):

# double dotProduct = 0.0
# double normA = 0.0
# double normB = 0.0
# for (int i = 0 i < vectorA.length i++) {
# dotProduct += vectorA[i] * vectorB[i]
# normA += Math.pow(vectorA[i], 2)
# normB += Math.pow(vectorB[i], 2)
# }
# answer = (float) ((float) dotProduct / (Math.sqrt(normA) * Math.sqrt(normB)))

def calculateClusterRepresentative(cluster, input, clusterId,clusterRepresentative,noOFTokens) :

#create a answer variable equal to the dimension of the noOFTokens
# Float[] answer = new Float[noOFTokens]
# for i in range( noOFTokens):
# answer[i] = Float.parseFloat("0")

#get the cluster representation
clusRepresent = clusterRepresentative[clusterId]

#get the number of members in the cluster
clusterMemberSize = len(cluster)

# for  i in  range(noOFTokens):
#so we multiply the previous cluster represenation by one number less and add it to new member features
# answer[i] = clusRepresent[i] * (clusterMemberSize - 1) + input[i]
answer= np.multiply(clusRepresent,(clusterMemberSize - 1))

• Testing this code requires loading unspecified pickled files. So it can't be tested as posted. Why the sparse title and scipy tag? All that I can see along that line sklearn which may use or generate sparse matrices. – hpaulj Mar 10 '17 at 1:30