Understanding comparisons of clustering results

Question

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.

Answer 1

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.

Answer 2

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.