3
$\begingroup$

There are three distinct algorithms for the K-Means function in R. These are:

  • Lloyd's
  • MacQueen's
  • Hartigan's

I believe I understand how Lloyd's works. 1. The cluster centers are chosen. 2. Points are assigned to the nearest center. 3. Centers are shifted to the mean of the points assigned to them.

My question is about how MacQueen's and Hartigan's algorithms differ to it. Here are some more specific questions, but any information about these methods would be helpful:

  1. Supposedly MacQueen's is more efficient, because it updates centroids more often. (Source).

    At what stages does MacQueen's update centroids that Lloyd's algorithm does not? (the source is unclear to me)

    Why does this make it more efficient?

    What exactly does 'more efficient' even mean? (My tests show that MacQueen's and Lloyds and Hardigan's all run at the pretty much the same speed for any data).

  2. My tests show that Hartigan's algorithm is more accurate because it does not seem to be affected as much by the random initial centroid positions. Here is the test I did:

There are 4 points. The vertical distance between them is 1, and the horizontal distance between them is 1000.

enter image description here

Assuming there are 2 clusters, clearly the correct clusters (with the lowest sum of squares) would be clusters of points above and below each other.

enter image description here

But because of the random initial centroid positions, sometimes the algorithm converges to a local optimum, and produces this obviously wrong result.

enter image description here

After doing >1,000,000 runs on each of the three, I found that Lloyd's and MacQueen's were both correct 2/3 of the time, and wrong for the other 1/3. However, Hartigan's was correct 100% of the time.

How does Hartigan's method even work? And how does this make it more accurate in terms of 'fixing' the wrong results that are caused by the initial random centroids?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Orthogonal comment: Your graphs are not crisp and clear. The contrast between the data points and the grey backdrop is not strong. Larger open markers or point symbols are easier to spot than small dots. The grid machinery is too obtrusive and not needed for your purposes any way. The numeric labels on the axes are very small. These are small points, and partly matters of taste, but they combine to make your graphs distracting as well as helpful. $\endgroup$
    – Nick Cox
    Nov 26, 2015 at 9:45
  • $\begingroup$ @NickCox Thank you for the suggestions, I have redone the graphs, although the old ones at normal size (click on them) were not bad. In any case, I hope people focus on the actual question, as the graphs were just one example of the different outputs of these algorithms. $\endgroup$
    – Yang Li
    Nov 26, 2015 at 19:55
  • $\begingroup$ Thanks for the attention. The point was that with clearer graphs (now achieved) people should indeed be able to focus on the question. $\endgroup$
    – Nick Cox
    Nov 26, 2015 at 20:03

1 Answer 1

Reset to default
3
$\begingroup$

Could't figure out much from the graphs but to answer your questions-

At what stages does MacQueen's update centroids that Lloyd's algorithm does not? Macqueen recalculates the center every time an iteration is completed like Lloyd's but also everytime a data point changes it's subspace (Cluster). So many more centroid calculations in Macqueen.

Why does this make it more efficient? It might not be efficient always, Consider a scenario where both the clusters are easily separable. Macqueen moves slowly as calculating new centroids while Llyods would jump towards right centroids in every iteration in lesser centriod calculation. So i think efficiency is not guaranteed.

What exactly does 'more efficient' even mean? (My tests show that MacQueen's and Lloyds and Hardigan's all run at the pretty much the same speed for any data). - Overall performace, like there can be a case where K-means will lead to an empty cluster. While macqueen and Hartigan algos may give different results for same datasets( if order of points is high)

How does Hartigan's method even work? And how does this make it more accurate in terms of 'fixing' the wrong results that are caused by the initial random centroids? Please read the below paper- goto page 17. It takes within cluster sum of squares rather than distance as metrics to classification a point in any cluster.
https://core.ac.uk/download/pdf/27210461.pdf

Improve this answer
$\endgroup$

Your Answer

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

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