External, internal, relative quality measures

Cluster validity measures judge how good a clustering is. They are of three kinds.

1. External measures

Compare the clustering with external information, i.e. known class labels (ground truth). Used when labels exist.

• Purity: for each cluster take the proportion of its most frequent class; the weighted sum over clusters is the purity.
• Entropy of the class distribution in each cluster (0 = perfect).
• Precision, recall and F-measure of each cluster with respect to a class.
• Rand index and Jaccard coefficient: count agreements of pairs of objects (same cluster/same class) between the clustering and the ground truth; adjusted Rand index, normalised mutual information.

2. Internal measures

Use only the data itself, without external labels, to judge compactness and separation.

• Cohesion (within-cluster SSE): Σ over clusters Σ_{x∈Cᵢ} d(x, cᵢ)²; smaller is better.
• Separation (between-cluster SS): Σ |Cᵢ|·d(cᵢ, c)²; larger is better.
• Silhouette coefficient: for object i, a = average distance to others in its own cluster, b = smallest average distance to another cluster, s = (b − a)/max(a, b). It lies between −1 and 1; near 1 means a good clustering.
• Others: Dunn index, Davies-Bouldin index, cophenetic correlation (for hierarchical clustering).

3. Relative measures

Compare two clusterings (or the same algorithm with different parameters, such as different k) to choose the better one. Internal or external indices are used for the comparison. Example: plot SSE against k and choose the "elbow", or choose the k with the highest average silhouette.