Comparing clustering algorithms [duplicate]

Question

I am conducting clustering analysis in which I am using three clustering algorithms K-means, Spectral Clustering, and Hierarchical clustering on 3 datasets in UCI repository.

I have used R packages to conduct clustering analysis and got the results such as Size of clusters, cluster vector, cluster means, Within cluster sum of squares, and grouping of cluster by Class.

Following is an example of my K-means on the Pima Indian diabetes data in UCI repository:

diabetes <- read.csv(url("http://archive.ics.uci.edu/ml/machine-learning-databases/pima-indians-diabetes/pima-indians-diabetes.data"), header = FALSE)

names(diabetes)<- c("No.ofTimesPregnant", "GlucoseConcentration", "BloodPressure", "TricepSkinThickness", "insulin", "BMI", "PedigreeFunction", "Age", "Class") 

set.seed(20)

KmeansCluster <- kmeans(diabetes[, 1:8], 4, nstart = 20, iter.max=10)

pcol <- as.character(diabetes$Class)
pairs(diabetes[1:8], pch = pcol, col = c("green", "red") KmeansCluster$cluster])
KmeansCluster
table(KmeansCluster$cluster, diabetes$Class)

I wish to know how I can compare the results of each clustering algorithm? So that I can say that particular clustering algorithm is best for this dataset. More specifically to say, what metric should I choose and how I can get that metric in R (For example, it would be helpful if you could tell me how to get those metric on my above R code for K-means)?.

As I know the diameter of the cluster and average distance of each cluster is used as a measure to compare clustering algorithm in general.

Answer 1

I would start off with the package 'clusteval', since it appears to be aimed exactly at what you want to do and it's on CRAN. Description:

An R package that provides a suite of tools to evaluate clustering algorithms, clusterings, and individual clusters.

For example useful metrics for you might be Jaccard and Rand similarities, which aim to evaluate how stable your clusterings are - that is, when perturbations are introduced to the original data sets, how robustly the same clusters are again detected. The function called clusteval (same as the package name) seems to suit your task at hand. They appear to favor Jaccard similarity by default.

Answer 2

One quality indicator for a clustering is the silhouette coefficient:

Get a distance metric $dist$ for two objects in your space. For example, the euclidean distance.

Let $a$ be the average distance between an object $o$ and other objects of the same cluster. $C(o)$ is the set of objects in the same cluster as $o$:

$$a(o) = \frac{1}{|C(o)|} \sum_{p \in C(o)} dist(o, p)$$

Let $b(o)$ be the average distance of o to the second-closest cluster:

$$b(o) = \min_{C_i \in \text{Cluster} \setminus C(o)}(\frac{1}{C_i}) \sum_{p\in C_i} \sum_{p \in C_i} \text{dist}(o, p)$$

The shilouette $s(o)$ is

$$s(o) = \begin{cases}0 &\text{if } a(o) = 0, \text{i.e. } |C_i|=1\\ \frac{b(o)-a(o)}{\max(a(o), b(o))} &\text{otherwise}\end{cases}$$

The silhouette $\text{silh}(C)$ of your clustering $C$ is

$$\text{silh}(C) = \frac{1}{|C|} \sum_{C_i \in C} \frac{1}{|C_i|} \sum_{o \in C_i} s(o)$$

$\text{silh}(C) \in [-1; 1]$. You want this value to be as big as possible. Everything below 0 is bad.