-1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Please add the [self-study] tag & read its wiki. Then tell us what you understand thus far & where you're stuck. $\endgroup$
    – gung - Reinstate Monica
    Commented Jan 17, 2015 at 2:48

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But, I have understood that McQueen is an iterative method too, isn't? $\endgroup$
    – user1260391
    Commented Jan 17, 2015 at 11:59
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jan 17, 2015 at 12:03
0
$\begingroup$

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.

Improve this answer
$\endgroup$

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.