# How to avoid k-means assigning different labels on different run?

I have unlabeled dataset. I am running k-means flat cluster with 2 number of clusters. Every time I run the below program the labels are different. How can I make labels not to change. Is it even possible?

X = np.array([[1, 2],
[5, 8],
[1.5, 1.8],
[8, 8],
[1, 0.6],
[9, 11]])

kmeans=KMeans(n_clusters=2)

kmeans.fit(X)

centeroids=kmeans.cluster_centers_
labels=kmeans.labels_

colors = ["g.","r."]

for i in range(len(X)):
print("coordinate:",X[i], "label:", labels[i])
plt.plot(X[i][0], X[i][1], colors[labels[i]], markersize = 10)

plt.scatter(centeroids[:, 0],centeroids[:, 1], marker = "x", s=150, linewidths = 5, zorder = 10)
print centeroids
print labels
plt.show()


On first run labels are [0 1 0 1 0 1]. One second run labels are [1 0 1 0 1 0]. How can I make it fixed?

    On the first run, this is how clusters are assigned to the dataset.

[1, 2] ------>0
[5, 8] ---------->1
[1.5, 1.8] ---------> 0
[8, 8] ---------->1
[1, 0.6] ---------> 0
[9, 11]----------->1

On the second run, this is how clusters are assigned to the dataset.

[1, 2] ------>1
[5, 8] ---------->0
[1.5, 1.8] ---------> 1
[8, 8] ---------->0
[1, 0.6] ---------> 1
[9, 11]----------->0


How do I make it not change?

• Why do you want this? – cangrejo Jul 20 '16 at 15:46
• I am working on cluster recommendation. The recommendation is not the same because of this. – NewBeeee Jul 20 '16 at 15:48
• What is cluster recommendation? What is the criterion for making the final recommendation? – cangrejo Jul 20 '16 at 15:49
• It is a matrix factorization. I have this user item rating matrix. I convert it to user item clusters rating matrix. Then I factorize the matrix. Then using adaptive gradient descent, I fill up the factorized matrix. Based on this filled up matrix, I make the recommendation. The problem is not with my recommender, but with cluster computation. My recommender works very well. – NewBeeee Jul 20 '16 at 15:52
• yes. My bad. Sorry. I will add that. Yes. I am clustering the dataset. – NewBeeee Jul 20 '16 at 16:10

In short: no, you cannot simply instruct most K-Means implementations to use the same names for their clusters each time (at least I am not aware of any such) - so you likely need to do this on your own.

The simple reason is that K-Means intentionally distributes cluster centers randomly at the start, so there would not be any semantic meaning in assigning names to clusters at this point. As the clusters are still the same when K-Means converges (only their centers and associated samples changed) this does not change from a semantic point of view either.

What you can do is e.g. automatically order cluster centers after K-Means convered by some metric you define (e.g. their distance to some origin). But be aware that a) K-Means will very likely converge differently on different runs ("local optima" if you would want to call them such) which might change your naming completely, and b) even if you converge very closely each time, small changes might still cause your metric to order cluster centers differently, which in turn would cause e.g. 2 clusters to have their names "switched", or one cluster being ordered far earlier/later than on previous runs, thereby also changing names of many other clusters if you are unlucky. And keep in mind that in case you change e.g. the amount of clusters between runs the results will naturally be quite different, hence common labels will likely not contain useful information again.

Update:

As pointed out by @whuber and @ttnphns in the comments, you can of course also using a automatic matching of clusters of 2 converged runs of K-Means, using some cluster similarity measure. The general idea is to obtain a pairwise matching of clusters over run A and B, where the distance of all clusters of run A to their counterparts in run B is minimized. This will likely give you better results than individually ordering clusters in most cases. Depending on your amount of clusters, a wide range from exhaustive (brute-force) approaches to search strategies might be appropriate.

• Why not attempt to match cluster centers automatically between pairs of outputs? That reduces the problem to the following: given two sets $\{x_1,\ldots, x_k\}$ and $\{y_1, \ldots, y_k\}$ of $k$ vectors in $\mathbb{R}^n$ and an ordering of the first set, order the second set via some permutation $\sigma$ of its indices so as to minimize some collective measure of the distances $|x_i - y_{\sigma(i)}|, i=1,\ldots, k$. A simple, fast greedy algorithm ought to do well in most practical cases. Exhaustive enumeration would be fine for small $k$. – whuber Jul 20 '16 at 17:04
• This is the general task for matching labels of two classification results having the confusion table. If the table is small and sparse, its diagonalization (i.e. matching the labels) is visually simple. Otherwise, Hungarian matching algorithm can be used. – ttnphns Jul 20 '16 at 18:07

I have similar problem and use this advice here https://stackoverflow.com/questions/44888415/how-to-set-k-means-clustering-labels-from-highest-to-lowest-with-python in that case, I have always structured labels based on their values. I guess this will help you.