Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
1  
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. – Dmitry Laptev Aug 19 '12 at 21:58
Is this a homework question? – Anony-Mousse Aug 20 '12 at 4:04
In 3. I think you mean "less than equal" instead of "greater than or equal", do you ? – steffen Aug 20 '12 at 8:09
It is not a homework. Oops, it was a mistake, I mean "less than equal". – genesiss Aug 20 '12 at 8:16

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
Thank you. I looked into single linkage hierarhical clustering and it is somehow similar to NN method. – genesiss Aug 22 '12 at 19:04
up vote 0 down vote

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

share|improve this answer
I think these two are not meant for clustering (they don't work with distance matrix). – genesiss Aug 20 '12 at 8:32
@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. – steffen Aug 20 '12 at 9:02
1  
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. – whuber♦ Aug 20 '12 at 20:15
Great tip, thanks whuber. – AGS Aug 20 '12 at 22:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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