I've got a distance matrix between examples. I want to cluster them into m clusters with a nearest neighbor algorithm which works like this:

1. Set i = 1 and k = 1. Assign example x_1 to cluster C_1.
2. Set i = i + 1. Find nearest neighbour of x_i
   among the patterns already assigned to clusters.
   Let d_n  denote the distance from x_i to its nearest neighbour.
   Suppose the nearest neighbour is in cluster n.
3. If d_n less than or equal to t then assign x_i to C_n where t is the 
   threshold specified by the user. Otherwise set k = k+1 and assign x_i  to a      
   new cluster C_k.

How could I adapt this algorithm so I could specify how many clusters I want?

Is anybody aware of an existing R implementation of nearest neighbour clustering?

  • 1
    $\begingroup$ In this algorithm you cannot specify the number of clusters, you can change them varying parameter 't'. For R implementations just Google it, there is at least one. $\endgroup$ Aug 19, 2012 at 21:58
  • $\begingroup$ Is this a homework question? $\endgroup$ Aug 20, 2012 at 4:04
  • $\begingroup$ In 3. I think you mean "less than equal" instead of "greater than or equal", do you ? $\endgroup$
    – steffen
    Aug 20, 2012 at 8:09
  • $\begingroup$ It is not a homework. Oops, it was a mistake, I mean "less than equal". $\endgroup$
    – Uros K
    Aug 20, 2012 at 8:16

2 Answers 2


As Dmitry Laptev already said correctly, the threshold t is determining the number of clusters indirectly. Using your algorithm there is no way to determine the number of clusters beforehand while still producing meaningful results.

As a more convenient bottom-up agglomerative nearest neighbor clustering approach you may want to take a look at Single Linkage, which works in a comparable (albeit certainly not equivalent) way. Single Linkage is implemented in R in hclust in the package stats

If you liked this approach, you should also take a look at the other linkage algorithms, especially Ward's method, which tends to deliver better results.

  • $\begingroup$ Thank you. I looked into single linkage hierarhical clustering and it is somehow similar to NN method. $\endgroup$
    – Uros K
    Aug 22, 2012 at 19:04

A quick google search produces k-Nearest Neighbour Classification and knn (weighted k-nearest neighbors

  • $\begingroup$ I think these two are not meant for clustering (they don't work with distance matrix). $\endgroup$
    – Uros K
    Aug 20, 2012 at 8:32
  • $\begingroup$ @genesiss the first link not, but the second one. From the description of the method specClust it uses spectral clustering, but yes, a precomputed distance matrix cannot be supplied as far as I see. $\endgroup$
    – steffen
    Aug 20, 2012 at 9:02
  • 1
    $\begingroup$ Michael, for finding R solutions use rseek.org instead of Google. One of the first hits when searching on "cluster" takes you to the Cluster task view listing approximately 100(!) packages. $\endgroup$
    – whuber
    Aug 20, 2012 at 20:15

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.