# Understanding comparisons of clustering results

I'm experimenting with classifying data into groups. I'm quite new to this topic, and trying to understand the output of some of the analysis.

Using examples from Quick-R, several R packages are suggested. I have tried using two of these packages (fpc using the kmeans function, and mclust). One aspect of this analysis that I do not understand is the comparison of the results.

# comparing 2 cluster solutions
library(fpc)
cluster.stats(d, fit1$cluster, fit2$cluster)


I've read through the relevant parts of the fpc manual and am still not clear on what I should be aiming for. For example, this is the output of comparing two different clustering approaches:

$n [1] 521$cluster.number
[1] 4

$cluster.size [1] 250 119 78 74$diameter
[1]  5.278162  9.773658 16.460074  7.328020

$average.distance [1] 1.632656 2.106422 3.461598 2.622574$median.distance
[1] 1.562625 1.788113 2.763217 2.463826

$separation [1] 0.2797048 0.3754188 0.2797048 0.3557264$average.toother
[1] 3.442575 3.929158 4.068230 4.425910

$separation.matrix [,1] [,2] [,3] [,4] [1,] 0.0000000 0.3754188 0.2797048 0.3557264 [2,] 0.3754188 0.0000000 0.6299734 2.9020383 [3,] 0.2797048 0.6299734 0.0000000 0.6803704 [4,] 0.3557264 2.9020383 0.6803704 0.0000000$average.between
[1] 3.865142

$average.within [1] 1.894740$n.between
[1] 91610

$n.within [1] 43850$within.cluster.ss
[1] 1785.935

$clus.avg.silwidths 1 2 3 4 0.42072895 0.31672350 0.01810699 0.23728253$avg.silwidth
[1] 0.3106403

$g2 NULL$g3
NULL

$pearsongamma [1] 0.4869491$dunn
[1] 0.01699292

$entropy [1] 1.251134$wb.ratio
[1] 0.4902123

$ch [1] 178.9074$corrected.rand
[1] 0.2046704

\$vi
[1] 1.56189


My primary question here is to better understand how to interpret the results of this cluster comparison.

Previously, I had asked more about the effect of scaling data, and calculating a distance matrix. However that was answered clearly by mariana soffer, and I'm just reorganizing my question to emphasize that I am interested in the intrepretation of my output which is a comparison of two different clustering algorithms.

Previous part of question: If I am doing any type of clustering, should I always scale data? For example, I am using the function dist() on my scaled dataset as input to the cluster.stats() function, however I don't fully understand what is going on. I read about dist() here and it states that:

this function computes and returns the distance matrix computed by using the specified distance measure to compute the distances between the rows of a data matrix.

-
 Are you looking for further clarifications or are you unhappy with @mariana's response? I guess it concerns your very first question (2nd §). If this is the case, maybe you should update your question so that people understand why you're setting a bounty on this question. – chl♦ Feb 20 '11 at 18:58 @chl I will update it to make it clearer. I'm just looking for some guidance on interpreting the clustering comparisons, as don't understand what the output means. @mariana's response was very helpful explaining some of the terms associated with this method. – celenius Feb 20 '11 at 19:15

First let me tell you that I am not going to explain exactly all the measures here, but I am going to give you an idea about how to compare how good is the clustering (lets assume we are comparing 2 clustering methods of the same amount of clusters.

1.For example the bigger the diameter of the cluster, the worst the clustering, because the points that belong to it are more scattered.

2.The higher the average distance of each clustering, the worst the clustering method (Lets assume that the average distance is the averaged distance of each point from the cluster to the center of the cluster)

Then there are this 2 metrics that are the most used, check the links to understand what they stand for:

inter-cluster distance (the higher the better, is the summatory of the distance between the different cluster centroids)

intra-cluster distance (the lower the better, is the summatory of the distance between the cluster members to the center of the cluster)

Also for understanding better the metrics above check this.

Then you should read the manual of the library and functions you are using to understand which measure represent which one of these, or if it is not here what is the meaning of it, but I wouldn't bother I would stick with the ones I stated here)-

Lets go on with the questions you made:

1) regarding scaling data: Yes you should always scale the data for clustering, otherwise the different scales of the different dimensions (variables) will have different influences in how data is clustered, the higher the values from the variable, the more influential will be that variable in how the clustering is done, while indeed they should all have the same (unless for some particular strange reason you do not want it that way)

2) The distance functions computes all the distances from one point(instance) to another. The most common distant measure is euclidean, so for example lets suppose you wan't to measure the distance from instance 1 to instance 2 (lets assume you only have 2 instances for the sake of simplicity). Also lets assume that each instance has 3 values (x1,x2,x3), so I1=0.3,0.2,0.5 and I2=0.3,0.3,0.4 so the euclidean distance from I1 and I2 would be: sqrt((0.3-0.2)^2+(0.2-0.3)^2+(0.5-0.4)^2)=0.17, hence the distance matrix will result in

    i1    i2
i1  0     0.17
i2  0.17  0


notice that the distance matrix is always simmetrical.

So the euclidean distance formula is not the only one that exists, there are many other distances that can be used to calculate this matrix. Check for example in wikipedia Manhattain Distance and how to calculate it. At the end of the wikipedia page for Euclidean Distance you can also check it's formula and at the end check which other distances exists.

-
 Thank you for your very comprehensive answer - it's very helpful. – celenius Feb 14 '11 at 16:39 Well done thank you! – B_Miner Feb 20 '11 at 17:07 I am really happy it was helpfull for you. – mariana soffer Feb 21 '11 at 20:46

I think the best quality measure for clustering is the cluster assumption, as given by Seeger in Learning with labeled and unlabeled data:

For example, assume X = Rd andthe validity of the “cluster assumption”, namely that two points x, x shouldhave the same label t if there is a path between them in X which passes onlythrough regions of relatively high P(x).

Yes, this brings the whole idea of centroids and centers down. After all, this are rather arbitrary concepts if you think about the fact that your data might lie within a non-linear submanifold of the space you are actually operating in.

You can easily construct a synthetic dataset where mixture models break down. E.g. this one: .

Long story short: I'd measure the quality of a clustering algorithm in a minimax way. The best clustering algorithm is the one which minimizes the maximal distance of a point to its nearest neighbor of the same cluster while it maximizes the minimal distance of a point to its nearest neighbor from a different cluster.

You might also be interested in A Nonparametric Information Theoretic Clustering Algorithm.

-
 How do I go about examining a cluster fit using a minimax approach? My knowledge level of clustering is very basic, so at the moment I'm just trying to understand how to compare two different clustering approaches. – celenius Feb 20 '11 at 21:56 Could you please share the R code for the attached figure? – Andrej Feb 20 '11 at 22:14 @Andrej My guess is a Gaussian cloud (x<-rnorm(N);rnorm(N)->y) split into 3 parts by r (with one of them removed). – mbq♦ Feb 21 '11 at 0:03 I don't know of a practical algorithm that fits according to that quality measure. You probably still want to use K-Means et al. But if the above measure breaks down, you know that the data you are looking at is not (yet!) suitable for that algorithm. – bayerj Feb 21 '11 at 7:43 @Andrej I don't use R (coming from ML rather than stats :) but what mbq suggests seems fine. – bayerj Feb 21 '11 at 7:45