# Determining which cluster to split among several groups using k-mean

I have 3 sets of data that will cluster into 3 distinct groups. Each group is unbalanced meaning that there are different number of points in each cluster (cluster1 = 300, cluster2=50, cluster3=900). I'd like to know the best way to determine how and where to add a fourth cluster to these groups (i.e. which group can best accommodate for another cluster?).

What I've done to this point is preformed k-means clustering on each group. I've also computed the sum of squared error (SSE) for each group for k=2..15:

wss = (nrow(data)-1)*sum(apply(data,2,var))
for (i in 2:15) wss[i] = sum(kmeans(data,centers=i)\$withinss)


Now I have a table that looks something like this:

"m"                "d"                  "e"
2813569.28725861    472355.029297394    5784658.19776383
1904107.38583311    318157.708967953    3506296.79084521
1648681.74129464    276421.573303097    2925602.69727677
1524909.05220068    259298.616113487    2685211.28641095
1465477.09738752    249822.780393088    2568056.73068996
1436268.67341786    244545.97418366 2492074.85372952
1418250.72662858    241004.184066676    2446687.20606313
1405885.99063985    237817.978851278    2411366.20542939
1395267.90044412    235054.310901762    2398095.04077986
1386557.42023853    232570.376337123    2374974.99416473
1379531.10300039    231250.918255804    2371436.20025802
1366720.2571021 229001.055906548    2352940.58741131
1360624.70769575    227234.173112882    2339408.89209271
1350787.58878321    226286.438463845    2333231.7286477
1345737.53064247    224540.981656591    2325617.52627248


Each line corresponds to the SSE for a particular k (row) in a particular group (column). I'm under the assumption that it would be incorrect to simply compare the row for each k and take the maximum value and use that corresponding group to add the cluster to. Am I correct in thinking this? Is there a better way to go about this?

Clarification Edit: The three clusters in the table provided above (m, d, e) are the three distinct, initial datasets. By themselves they form 3 distinct cluster. Now, say I'd like to split one of these clusters into 2. Which do I choose? How do I determine which one to split?

## migrated from stackoverflow.comApr 19 '16 at 18:26

This question came from our site for professional and enthusiast programmers.

• Please see the link @Boro post. There is a good explanation of kmean clustering. – Dave2e Apr 13 '16 at 0:09
• @Dave2e I must not have been clear enough. I've responded to Boro with more detail. Hopefully this clarifies. If not, please let me know. – user2117258 Apr 13 '16 at 0:24
• The concept behind Kmeans is to choose a given number of centers in your case starting with 3, run the algorithm a few times to see how stable the centers are. Kmeans is not deterministic thus the centers can change between simulations. Calculate your SSE if it there is a significant change then add another center and repeat, if not then you are likely around the optimal number of centers. The short answer is you choose the number of centers and the algorithm finds the centers. – Dave2e Apr 13 '16 at 0:32
• @Dave2e, I should clarify further. Kmeans was run on the three initial clusters independently, not merged together. The table posted in the OP are the SSE results for each cluster independently. I will ultimately plot the merged data (the initial three clusters) and label them as they will be very distinct. I want to know now, how would I split the initial 3 clusters to make room for a 4th? Which cluster would I split to make this happen? – user2117258 Apr 13 '16 at 1:54
• Your objective of trying to decide how to split one of your sets into a fourth set is not very clear. I don't believe the Kmeans is the proper criteria to use, but with the provided information and a lack of understanding, I am afraid, I can't provide any additional help. – Dave2e Apr 13 '16 at 2:12

I am not sure whether I understood the question correctly. If the question is whether to determine the optimal number of clusters; you can simply plot your above code as following:

 plot(1:15, wss, type="b", xlab="Number of Clusters",
ylab="Within groups sum of squares")


There is a very detailed discussion in this link.

Hope it helps.

• Sorry I must have have been clear. I would like to determine which of the three groups can best accept a split. Say for example that cluster1 really consists of two 2 clusters but we initially cluster it as one (along with cluster2 and cluster3). How would I go about choosing cluster1 to split over cluster2 or cluster3? Is there a metric to compare against all initial clusters? – user2117258 Apr 13 '16 at 0:23
• I should have clarified, the data is quantile normalized and outliers have been removed. I can bootstrap the kmeans clustering for consistency but that will not address the question at hand. Thank you for your response! – user2117258 Apr 13 '16 at 1:51

The usual approach (see bisecting k-means, x-means, g-means) is to try splitting each cluster, and only keep those that yield an improvement in AIC or BIC.

SSQ is not a suitable measure, because it will always decrease if you add another centroid.