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

Question

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?

Answer 1

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 probably 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 converged 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 use an automatic matching of clusters of two 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 the number of your clusters, a wide range from exhaustive (brute-force) approaches to search strategies might be appropriate.

Answer 2

try random_state=0 parameter

kmeans = KMeans(n_clusters = 20,  random_state=0)

see official Glossary

Answer 3

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.

Answer 4

How about using v-measure? It is a symmetric measure

https://scikit-learn.org/stable/modules/generated/sklearn.metrics.v_measure_score.html

You might also want to read more about homogeneity score and completeness score.