0
$\begingroup$

I am currently writing a K-means clustering algorithm in Python, and I seem to have coded myself into a corner... I begin my algorithm with data sets assigned randomly to the appropriate number of K clusters, but I always end up converging to a single cluster (convergence time depends on value of K). The only case where this doesn't happen is when K=N, my number of data sets. In that case, I keep 31 clusters (as expected - you can't be closer to anyone than yourself). The code requires specific file formatting, but I can supply some examples upon request. I've put the code at the bottom of the post (it's rather bulky), but my logic is as follows:

  1. Randomly assign N models (of size M) to K clusters
  2. Average the models in each K
  3. Calculate similarity (in place of euclidean distance) between N models and each K cluster
  4. Assign N models to "closest" similarity K.
  5. Repeat

For benchmarking purposes, 31 data sets initialized to 4 clusters will converge to a single cluster in 3-5 iterations.

    import numpy as np
    from math import pow,sqrt

    ################### Function for scoring the differences between clusters ############################
    def Score(PROFILES):
            NUM=len(PROFILES)
            scores=np.zeros((NUM,NUM))
            for x in range(NUM):
                    for y in range(x+1,NUM):
                            scores[x,y]=Similarity(PROFILES[x],PROFILES[y])
                            scores[y,x]=scores[x,y]
                            scores[y,y]=0
            return scores
    ######################################################################################################

    ################################### Function for calculating the score 'distance' between two clusters #
    def Similarity(PROFILE1,PROFILE2):
            profile1=np.log(PROFILE1)
            profile2=np.log(PROFILE2)
            sum=0
            for idx in range(len(profile1)):
               sum+=pow(profile1[idx]-profile2[idx],2)/(2*(0.1**2)) # Denominator is approximate error, numerator is difference in I(q)
            score=sqrt(sum)
            return score
    ######################################################################################################

    ########### Determine Initial Clusters ###############################################################
    def FirstGrouping(PROFILES,K):
            Nprofiles=len(PROFILES)
            CLUST_IDX=np.random.randint(1,K+1,size=Nprofiles) #Assign each profile a cluster number
            AVERAGES=AverageCluster(PROFILES,CLUST_IDX) #Calculate cluster Average Profile
            return CLUST_IDX,AVERAGES #List of cluster numbers and KxN array of cluster average profiles
    ######################################################################################################

    ########## Calculate average of profiles in each cluster #############################################
    def AverageCluster(PROFILES,CLUST_IDX):
            CLUSTER_AVERAGE=np.zeros((np.amax(CLUST_IDX),len(PROFILES[0]))) # Initialize a KxN array to store the I(q) (for N q-values) for the K clusters
            for CLUSTER in CLUST_IDX:
                    PROFILES_IN_CLUST=np.where(CLUST_IDX==CLUSTER)[0] # Find the profiles belonging to CLUSTER
                    NUMBER_IN_CLUST=len(PROFILES_IN_CLUST) # Count the total number in the cluster
                    for PROFILE in PROFILES_IN_CLUST:
                            CLUSTER_AVERAGE[CLUSTER-1]+=PROFILES[PROFILE] #Calculate the sum of the scattering profiles
                    CLUSTER_AVERAGE[CLUSTER-1]=CLUSTER_AVERAGE[CLUSTER-1]/NUMBER_IN_CLUST #Divide by number in cluster to get the average

            return CLUSTER_AVERAGE # KxN array
    ######################################################################################################

    ############## Find closest Center (Cluster average) for each profile ################################
    def FindClosest(PROFILES,CLUST_IDX,CLUSTERS): #MxN array of individual profiles, K-array of cluster identities, KxN array of cluster average profiles
            NEW_CLUSTERS=np.copy(CLUST_IDX) #Keep the old cluster index, but make a copy for editing to the new one
            for profile in range(len(PROFILES)):
                    Similarity_to_clusters=np.zeros(len(CLUSTERS)) #Initialize a length K array to store similarity values within
                    for cluster in range(len(CLUSTERS)):
                            Similarity_to_clusters[cluster]=Similarity(PROFILES[profile],CLUSTERS[cluster])
                            print("Profile %i, Cluster %i - %f" % (profile,cluster,Similarity_to_clusters[cluster]))
                    NEW_CLUSTERS[profile]=np.where(Similarity_to_clusters==np.amin(Similarity_to_clusters))[0]+1 #Assign the profile to the closest cluster in similarity
                    NEW_AVERAGE=AverageCluster(PROFILES,NEW_CLUSTERS)

            return NEW_CLUSTERS,NEW_AVERAGE,CLUST_IDX,CLUSTERS  #new cluster dictionary, new cluster average, old cluster dictionary, old cluster average
    ######################################################################################################

    ################# Function for stopping the while loop ###############################################
    def StopCondition(OLD_CLUSTER,NEW_CLUSTER,ITERATION,MAX):
            if ITERATION > MAX: # Stop if you have surpassed max iteration count
                    print("Cluster search reached maximum number of iterations(%i)" % MAX)
                    return 1
            print(np.array_equal(NEW_CLUSTER,OLD_CLUSTER))
            if np.array_equal(NEW_CLUSTER,OLD_CLUSTER): # Stop if you have no change in cluster identities
                    print("Cluster search has converged! (after %i iterations)" % ITERATION)
                    return 1
    ######################################################################################################

    ########### Function for K-Means Clustering of Profiles ##############################################
    def KMeansClustering(PROFILES,K):

            #Bookkeeping variables
            iteration=0
            max_iteration=100

            #Assign first group of clusters
            old_idx=None
            new_idx,new_avg=FirstGrouping(PROFILES,K)

            while not StopCondition(old_idx,new_idx,iteration,max_iteration):
                    iteration+=1
                    new_idx,new_avg,old_idx,old_avg=FindClosest(PROFILES,new_idx,new_avg)
                    print("OLD:\n"+str(old_idx))
                    print("NEW:\n"+str(new_idx))
            return new_idx,new_avg

    ######################################################################################################

    ################### Run the Clustering ###############################################################
    num=31 # number of data sets
    K=4    # number of desired clusters
    for x in range(num):
            if x==0:
                    profiles=np.genfromtxt("file."+str(x),usecols=2,skip_header=3)
            else:
                    profiles=np.vstack((profiles,np.genfromtxt("file"+str(x),usecols=2,skip_header=3)

    cluster_index,cluster_average=KMeansClustering(profiles,K)
    print(cluster_index)
    print("Clustering complete.")
    ######################################################################################################
$\endgroup$
3
  • $\begingroup$ What do you mean by data sets? $\endgroup$ Aug 13, 2015 at 23:33
  • $\begingroup$ I'm trying to cluster solution scattering curves, so my PROFILES variable is an NxM array for the N different scattering curves of length M (I have scattering intensities for M different scattering angles). I assign each curve to a random cluster to begin the algorithm. I apologize if I have slaughtered the semantics. $\endgroup$
    – Sam
    Aug 14, 2015 at 16:07
  • $\begingroup$ I'm sorry but I'm not able to answer this (partially due to my limited Python knowledge). Have you considered using an already-implemented k-means? Isn't there one in sci-kit learn? $\endgroup$ Aug 17, 2015 at 12:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.