2
\$\begingroup\$

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]
    # }
    # return answer
# }

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)))

    # return answer
    answer=cosine_similarity(vectorA,vectorB)
    # print answer
    return answer[0][0]


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

    #create a answer variable equal to the dimension of the noOFTokens
    # Float[] answer = new Float[noOFTokens]
    # answer=np.zeros(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))
    answer= np.add(answer,input)


    # for i in range( noOFTokens):
        #divide the sum of all the cluster members by the total number of memebers to calculate the new centroid
        # answer[i] /= clusterMemberSize
    answer=np.divide(answer,clusterMemberSize)

    return answer

threshhold = 0.017
singlePassAlgorithm(threshhold)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – hpaulj Mar 10 '17 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.