Which K-mean algorithm I have to use for this problem?

Perform a k-means Clustering (non-iterative algorithm) using k=2 randomly initialised centroids (cluster prototypes), and the Euclidean distance.

At the moment I manage to understand you can use different algorithms to run K-means clustering (Lloyd, Forgy's, McQueen, Hattigan), but I understand all of the algorithm are iterative and I don't find or understand the non-iterative idea of non-iterative clustering.

Please, could some one clarify me that?

Thanks

• Please add the [self-study] tag & read its wiki. Then tell us what you understand thus far & where you're stuck. – gung Jan 17 '15 at 2:48

What non-iterative version of k-means was discussed before? The “default” version - Lloyds algorithm - is iterative. So you are probably meant to use MacQueens, or a matrix based dual form, depending on what was discussed.

• But, I have understood that McQueen is an iterative method too, isn't? – user1260391 Jan 17 '15 at 11:59
• From my understanding of the original publication, it does a single pass over the data. But you also would initialize it with the first k objects as centers (because you haven't seen other data yet) then. So there probably is another non-iterative algorithm in your class/book. – Anony-Mousse Jan 17 '15 at 12:03

An example

Lloyd's algorithm is the standard k-means clustering algorithm and it is iterative. You chose k random starting points from your data set and compute the (Euclidean) distance of each point to each cluster center. You assign each point to its nearest cluster. After the assignment of one point to one cluster, you recalulate the mean of that cluster. After you've done this for all points, your first iteration is complete and you start from the beginning, i.e. you start a new iteration. The cluster means will have changed during your first iteration, which makes it necessary to, again, calculate the distance of each point to each cluster center, and see if there aren't perhaps some points that are now closer to other cluster centres.

In principle you could also stop the Lloyd's algorithm after your first round of assigning points and your algorithm would be non-iterative. The quality of your solution will, however, be not that great.

MacQueen's algorithm is non-iterative in the sense you choose your k random starting points and assign all your points to those centers only once. Algorithmically, MacQueen's does nearly the the same thing as Lloyd's: you go through each point and compute the increase in variance for each cluster (this is where it is mathematically different to Lloyd's), if it were assigned to it. You chose to assign the point to the cluster, whose variance increase is minimally. After you have gone through all points once you stop and your MacQueen's algorithm terminates. From an algorithmic point of view, this is where MacQueen's and Lloyd's are different.

In principle you could also continue with more iterations, this would make your algorithm iterative.