Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 4 down vote favorite

If I have a certain dataset, how smart would it be to initialize cluster centers using means of random samples of that dataset. For example, suppose I want 5 clusters. I take 5 random samples of say, size=20% of the original dataset. Could I then take the mean of each of these 5 random samples and use those means as my 5 initial cluster centers? I don't know were I read this but I wanted to know what you guys think about the idea. Thank you in advanced.

share|improve this question
7  
If you randomly split the sample into 5 subsamples your 5 means will almost coincide. What is the sense of making such close points the initial cluster centers? In most K-means implementations, the default selection of initial cluster centres is based on the opposite idea: to find the 5 points which are most far apart and make them the initial centres. – ttnphns Jun 19 '12 at 6:50
1  
@ttnphns This would be a nice answer. – mbq♦ Jun 19 '12 at 9:50
1  
I would think it would be much better to pick the overall mean as one point and choose others that are far away from that center in various directions. – Michael Chernick Jun 19 '12 at 12:44
1  
Makes sense. How would I go around about finding these 5 points which are far apart? Thank you! – JEquihua Jun 19 '12 at 16:16
@JEquihua, I posted my comment as the answer and added details which you are requesting. – ttnphns Jun 20 '12 at 1:19

4 Answers

up vote 2 down vote accepted

If you randomly split the sample into 5 subsamples your 5 means will almost coincide. What is the sense of making such close points the initial cluster centres?

In many K-means implementations, the default selection of initial cluster centres is based on the opposite idea: to find the 5 points which are most far apart and make them the initial centres. You may ask what may be the way to find those far apart points? Here's what SPSS' K-means is doing for that:

Take any k cases (points) of the dataset as the initial centres. All the rest cases are being checked for the ability to substitute those as the initial centres, by the following conditions:

  • a) If the case is farther from the centre closest to it than the distance between two most close to each other centres, the case substitutes that centre of the latter two to which it is closer.
  • b) If the case is farther from the centre 2nd closest to it than the distance between the centre closest to it and the centre closest to this latter one, the case substitutes the centre closest to it.

If condition (a) is not satisfied, condition (b) is checked; if it is not satisfied either the case does not become a centre. As the result of such run through cases we obtain k utmost cases in the cloud which become the initial centres. The result of this algo, although robust enough, is not fully insensitive to the starting choice of "any k cases" and to the sort order of cases in the dataset; so, several random starting attempts are still welcome, as it is always the case with K-means.

share|improve this answer
Once I have done what you describe, what statistic could I use to determine which initialization point lead to a better partition? Thank you for all. – JEquihua Jun 20 '12 at 19:52
Using utmost points as initial centres once does not guarantee getting the best partition in the end, thought they (as compared to random initial centres) do diminish the chance of getting trapped into a "local optimum", and they speed up the process of convergence. Varying order of cases, do the entire k-means partition 2-5 times, save the final centres obtained, average them and input as the initial ones for one final clusterization. This partition is surely the best. You actually need not any special statistic to check it, unless you're going to compare partinions of different k. – ttnphns Jun 20 '12 at 20:23
I do want to compare partitions of different k. What could I use? What's a good idea? thank you for helping me so much. @ttnphns. – JEquihua Jun 21 '12 at 14:20
There exist a great number of "internal" clustering criterions. One of the most appropriate for k-means is Calinski-Harabasz (multivariate Fisher's F). Google for it or for others. – ttnphns Jun 21 '12 at 14:33
up vote 2 down vote

Using the means of random samples will give you the opposite of what you need, as ttnphns pointed out in his comment. What we would need is a way to find data points that are fairly far from each other.

Ideally, you could iterate over all points, find the distances between them, determine where the distances are the largest ...

Not to sidestep the OP's intention, but I think the "solution" is built into the k-means algorithm. We perform multiple iterations and recalculate cluster centroids based on the previous iterations. We also usually run the kmeans algorithm several times (with random initial values), and compare the results.

If one has a priori knowledge, domain knowledge, then that could lead to a superior method of identify where initial cluster centers should be. Otherwise, it's probably a matter of selecting random data points as initial values and then utilizing multiple runs and multiple iterations per run.

share|improve this answer
Once I have done what you describe, what statistic could I use to determine which initialization point lead to a better partition? Thank you for all. – JEquihua Jun 20 '12 at 19:45
up vote 1 down vote

The means will be much too similar. You could just as well find the data set mean, and then place the initial centroids in a small circle/sphere around this mean.

If you want to see some more sound initialization scheme for k-means, have a look at k-means++. They have devised a quite clever method for seeding k-means.

  • Arthur, D. and Vassilvitskii, S. (2007).
    k-means++: the advantages of careful seeding".
    Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Author slides: http://www.ima.umn.edu/~iwen/REU/BATS-Means.pdf

share|improve this answer
I read this, It looks pretty intuitively advantageous but I think it is yet to be proven that it works better than simply taking a lot of random initialization points. I found this simple code in case you want to try it out: kmpp <- function(X, k) { n <- nrow(X) C <- numeric(k) C[1] <- sample(1:n, 1) for (i in 2:k) { dm <- distmat(X, X[C, ]) pr <- apply(dm, 1, min); pr[C] <- 0 C[i] <- sample(1:n, 1, prob = pr) } kmeans(X, X[C, ]) } – JEquihua Jun 20 '12 at 19:45
It is known to significantly reduce the number of iterations until convergence and produce on average better results. I can confirm that in my own experiments, kmeans++ is the way to go. I'm using the ELKI implementation. – Anony-Mousse Jun 20 '12 at 21:05
What is the ELKI implementation? where can I look it up? greetings! – JEquihua Jun 21 '12 at 14:22
en.wikipedia.org/wiki/ELKI – Anony-Mousse Jun 21 '12 at 16:27
up vote 0 down vote

The answers proposed are all effective, but are much more difficult to operationalize than your original proposal. A very simple way to initialize is to take $k$ random observations as the original points. The probability of getting two initial points close is quite low, and the algorithm executes quickly for all but the most extreme cases.

share|improve this answer
Makes a lot of sense. Could I ask you the same I asked Aman. Suppose I take a zillion random initial points. What could I use to determine which of the resulting partitions is best? Greetings! @gmacfarlane – JEquihua Jun 20 '12 at 19:47
Typically, $k$-means algorithms iterate until the mean squared error (or mean absolute error) is minimized and stable between iterations. In any given dataset, there will be a finite number of combinations that truly minimize this MSE. So a zillion runs will probably produce between one and ten partition schemes (depending on the weirdness of your data), and I would pick the one that had the lowest MSE among all the groups. – gmacfarlane Jun 20 '12 at 23:27
I should note that if your partitions are highly sensitive to the initial points selection, it means your data do not have natural clusters and a $k$-means clustering algorithm might not be the best thing to use. Or, you are trying to fit more clusters than the data naturally present. – gmacfarlane Jun 20 '12 at 23:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.