I am performing a hierarchical clustering and a DBSCAN clustering on a distance matrix (A self-organizing map is something that I want to do as well). I am trying to find a method to choose the number of clusters based on some criteria (like an elbow plot with some criteria for its slope or a BIG criteria or…), but I am not sure what are the efficient and reliable methods of doing so when only the distance matrix exist. Any suggestion is appreciated.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ stats.stackexchange.com/questions/64924/… $\endgroup$– sitemsJul 25, 2013 at 14:02
-
$\begingroup$ But DBSCAN does not need to know the number of clusters! $\endgroup$– Has QUIT--Anony-MousseJul 26, 2013 at 13:07
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
I agree with the post above, but in situations like these, one method I like to use involves permuting the data 1000 times, reclustering them each time by the same metrics, and selecting the number of observed clusters at a tree height that significantly exceeds all tree heights identified from permutations (P < 0.001).
Something like
d <- dist(mydata, method = "euclidean")
fit <- hclust(d,method="ward")
clusters<-c()
for (i in 1:1000){
km.rand <- t(apply(mydata,1,sample))
d <- dist(km.rand, method = "euclidean")
fit2 <- hclust(d,method="ward")
clusters[i]<-length(which((fit$height-fit2$height)>0))
}
Note that in the above code I'm only permuting the columns, not the rows, because those were the variables for which I was interested in determining the number of clusters.
Hope this helps as a possible solution to your problem!
Ron
-
$\begingroup$ Thank you!! This is a great technique. But I have to do the clustering on a distance matrix of size 10,000 by 10,000 which takes a lot of time. Is there a techniques that is fast but not the most accurate technique which gives me a good balance of speed and getting a number of clusters? $\endgroup$– PODJul 25, 2013 at 15:27
-
$\begingroup$ Hm...you could randomly sample and permute 1000 rows by 1000 columns from your data 10000 times to speed up the calculation of the randomized distance matrix substantially. This should be sufficient because permutation thresholds such as these tend to be tight around the mean for the expected number of clusters at given heights. You can confirm this empirically by comparing these results to what you would get from the whole dataset by doing 100 permutations or so. $\endgroup$ Jul 25, 2013 at 18:37
$\begingroup$
$\endgroup$
3
This is not really a solution, but just a thought on the issue. I consider this type of question very domain-dependent. If you were doing the clustering by hand, how would you decide when to stop? When there are ten clusters? When the clusters have an average size of 72? When the distances you are crossing to make a cluster get up to 17?
What I'm saying is there's no right or wrong answer here other than picking a stopping condition that makes sense given your data. I could give a suggestion as to how to accomplish a certain stop condition, but you need to specify what you want your stop condition to be based on.
-
$\begingroup$ I am trying to cluster the users of a webpage based on their activity log. I have their record, age, gender, location and etc. I created a distance matrix for their history record. Now I want to do a clustering on all of the data. What I have in mind is to cluster the distance matrix first and then combine it with other information and create a table where each row is a user. What would be a good stopping criteria for both steps of clustering if I do a hierarchical or a DBSCAN clustering. $\endgroup$– PODJul 25, 2013 at 15:20
-
$\begingroup$ How many clusters to you want? What do you want the users who are the same cluster to have in common? $\endgroup$– rcortyJul 25, 2013 at 15:26
-
$\begingroup$ I want to cluster the users based in their activity log (like a sequence of activity which I compared them and created a distance matrix for it) and the users' age, gender, location, etc. That is the thing that I do not know how many clusters should I choose. I want to have some criteria or visualization to say 'yes, this a good estimation' $\endgroup$– PODJul 25, 2013 at 15:30