1
$\begingroup$

In the iterations of Hartigan and Wong Algo of K-Means clustering, If the centroid is updated in the last step, for each data point included, the within- cluster sum of squares for each data point if included in another cluster is calculated.
If one of the cluster sum of squares is smaller than the current one, the data point( case) would be assigned to new cluster.

My question is- How is it different from Llyod's algorithm?
In Lloyd's new data points will be assigned to new cluster if distance from its(new cluster) lesser that current one. I am wondering how is it possible for a data point to have higher distance from another cluster( new cluster) but lesser squared distance from same another cluster( new cluster) ? paper I referred- https://core.ac.uk/download/pdf/27210461.pdf

I think it is sth to do with number of data points in a cluster, but I could't related it to any example where a data point falls in different clusters in both the algos. Can some please explain on it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Lloyd's kmeans also minimizes the sum of squares (it does not minimize Euclidean distances). So no difference here.

But the standard algorithm is pretty dumb. It recomputed all the distances in each iteration. Hartigan's also pays attention to a very important fact: of you add a point to a cluster, the mean will change. This will increase the distance of the other points to the mean. So reassigning a point from one cluster to another to slightly reduce the points distance can reduce the quality of all the other points in the cluster to the point where this was not a smart change to perform.

Improve this answer
$\endgroup$
4
  • $\begingroup$ As I have read on paper mentioned, it clearly says Lloyd's take one of the distance metrics. Your explanation of Hartigan seems like Macqueen algo. :) $\endgroup$
    – Arpit Sisodia
    Commented Jul 26, 2018 at 12:50
  • 1
    $\begingroup$ No, MacQueen does not take the negative effects into account. He does an incremental Single-Pass that will often yield fairly bad results. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jul 26, 2018 at 19:13
  • 1
    $\begingroup$ And the paper you linked above is wrong to suggest using all these metrics with k-means. It's easy to find counterexamples that k-means will not find a (local) optimal solution with Euclidean or Manhattan distance. It only finds local optima with squared Euclidean and other Bergman divergences (a fairly narrow class). See the many other questions on k-means and other metrics. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jul 26, 2018 at 19:20
  • $\begingroup$ seems like some more research is required before moving forward. :( $\endgroup$
    – Arpit Sisodia
    Commented Jul 27, 2018 at 14:31

Your Answer

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

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