# What are the differences between Lloyd's, MacQueen's and Hartigan's algorithms for K-Means?

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.

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.

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

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?

• 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. Commented Nov 26, 2015 at 9:45
• @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. Commented Nov 26, 2015 at 19:55
• Thanks for the attention. The point was that with clearer graphs (now achieved) people should indeed be able to focus on the question. Commented Nov 26, 2015 at 20:03