With the K Clusters generated using K Means Clustering, how do we calculate the density of each cluster? Is there any formula for it?

  • 1
    $\begingroup$ How do you define 'density'? $\endgroup$ – chl Oct 19 '12 at 10:50
  • 1
    $\begingroup$ K-means is not a density based algorithm. As the clusters usually are not at all uniform in density, any such number would have a limited use. $\endgroup$ – Has QUIT--Anony-Mousse Oct 19 '12 at 11:38
  • $\begingroup$ Do you want to just evaluate the quality of clusters using some sort of density metric, or do you actually want to make the clusters based on that density? $\endgroup$ – Marcin Oct 19 '12 at 13:25
  • 1
    $\begingroup$ K-means aims to minimize within-cluster sum of squares, because when the centres get stabilized, they are the means, and a mean is the locus of minimal sum of squred deviations from it. So, the most natural (non)density measure is the within cluster SS or SS/n (the variance). (The problem with K-means, though, is that it is prone to local optimum results, being very dependent on choice of initial centres.) $\endgroup$ – ttnphns Oct 20 '12 at 8:16

One possible method:

  1. For each data point, calculate its distance from each of the centroids. Let x be a coordinate vector pointing to the data point and c be a coordinate vector pointing to some centroid. Then the distance to the centroid can be defined as: $d = \sqrt{(\vec{x}-\vec{c})'*(\vec{x}-\vec{c}) }$
  2. For each data point, identify the centroid(s) with the smallest distance value ($d$). If there are $m$ such centroids, give a score of $\frac{1}{m}$ to each centroid (typically one would expect $m=1$).
  3. Accumulate the total score for each centroid across all of the data points. The total score can be considered the "density" of the cluster as it conveys the number of data points within the "region of influence" of the centroid.

A more sophisticated approach might be to also weight the scores based on some decreasing function of the $d$ value, giving a higher density score for points that are very close to the centroid.

For comparison between datasets, you could also scale the final density scores by dividing each centroid's score by the total across all centroids. Then each score would be a value between 0 and 1.

  • $\begingroup$ @Marcin I wish to use the density metric to evaluate the quality of clustering. And I wish to know, if we could calculate density of each cluster in K Means clustering or not.. $\endgroup$ – user16073 Oct 25 '12 at 5:42
  • $\begingroup$ @WillTowns Thanks for your method. I think I could use that. Thanks a lot. $\endgroup$ – user16073 Oct 25 '12 at 5:43

K-Means tries to minimize the sum of square distances of the points to their cluster center. After running K-Means, you can compute some statistics that will help you measure the "density" of the clustering. In R, these statistics are included in the generated clustering object, but you can also compute them by yourself. The "density" or "goodness" is expressed by the ratio of the "betweenss" - the sum of squares between the clusters - and the "totalss" which is the total sum of squares for the entire collection. The higher the ratio, the better. Here is a quick example in R:

tbl = iris[,1:4]
cat("The clustering 'density' is", clust$betweenss / clust$totss," the higher the better\n")

#This is how you can compute the withinss, betweenss and totss by yourself
withinss = 0
for (i in 1:length(clust$size))
  clust_i = tbl[which(clust$cluster==i),]
  withinss = withinss+sum((clust_i-matrix(data=clust$centers[i,],ncol=ncol(clust_i), nrow=nrow(clust_i),byrow = TRUE))^2)

totss = sum(rowSums((scale(tbl,scale=FALSE))^2))
betweenss = totss-withinss
score = betweenss/totss

cat("The clustering 'density' is", score," the higher the better\n")


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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