Density calculation in K Means clustering With the K Clusters generated using K Means Clustering, how do we calculate the density of each cluster? Is there any formula for it?
 A: One possible method:  


*

*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}) }$  

*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$).

*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.
A: 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:
data(iris)
tbl = iris[,1:4]
clust=kmeans(tbl,2)
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")


