Calinski–Harabasz index

The Calinski–Harabasz index (CHI), also known as the Variance Ratio Criterion (VRC), is a metric for evaluating clustering algorithms, introduced by Tadeusz Caliński and Jerzy Harabasz in 1974. It is an internal evaluation metric, where the assessment of the clustering quality is based solely on the dataset and the clustering results, and not on external, ground-truth labels.

Definition

Given a data set of n points: {x₁, ..., x_n}, and the assignment of these points to k clusters: {C₁, ..., C_k}, the Calinski–Harabasz (CH) Index is defined as the ratio of the between-cluster separation (BCSS) to the within-cluster dispersion (WCSS), normalized by their number of degrees of freedom:

$CH={\frac {BCSS/(k-1)}{WCSS/(n-k)}}$

BCSS (Between-Cluster Sum of Squares) is the weighted sum of squared Euclidean distances between each cluster centroid (mean) and the overall data centroid (mean):

$BCSS=\sum _{i=1}^{k}n_{i}||\mathbf {c} _{i}-\mathbf {c} ||^{2}$

where n_i is the number of points in cluster C_i, c_i is the centroid of C_i, and c is the overall centroid of the data. BCSS measures how well the clusters are separated from each other (the higher the better).

WCSS (Within-Cluster Sum of Squares) is the sum of squared Euclidean distances between the data points and their respective cluster centroids:

$WCSS=\sum _{i=1}^{k}\sum _{\mathbf {x} \in C_{i}}||\mathbf {x} -\mathbf {c} _{i}||^{2}$

WCSS measures the compactness or cohesiveness of the clusters (the smaller the better). Minimizing the WCSS is the objective of centroid-based clustering algorithms such as k-means.

Explanation

The numerator of the CH index is the between-cluster separation (BCSS) divided by its degrees of freedom. The number of degrees of freedom of BCSS is k - 1, since fixing the centroids of k - 1 clusters also determines the k^th centroid, as its value makes the weighted sum of all centroids match the overall data centroid.

The denominator of the CH index is the within-cluster dispersion (WCSS) divided by its degrees of freedom. The number of degrees of freedom of WCSS is n - k, since fixing the centroid of each cluster reduces the degrees of freedom by one. This is because given a centroid c_i of cluster C_i, the assignment of n_i - 1 points to that cluster also determines the assignment of the n_i^th point, since the overall mean of the points assigned to the cluster should be equal to c_i.

Dividing both the BCSS and WCSS by their degrees of freedom helps to normalize the values, making them comparable across different numbers of clusters. Without this normalization, the CH index could be artificially inflated for higher values of k, making it hard to determine whether an increase in the index value is due to genuinely better clustering or just due to the increased number of clusters.

A higher value of CH indicates a better clustering, because it means that the data points are more spread out between clusters than they are within clusters.

Although there is no satisfactory probabilistic foundation to support the use of CH index, the criterion has some desirable mathematical properties as shown in. For example, in the special case of equal distances between all pairs of points, the CH index is equal to 1. In addition, it is analogous to the F-test statistic in univariate analysis.

Liu et al. discuss the effectiveness of using CH index for cluster evaluation relative to other internal clustering evaluation metrics. Maulik and Bandyopadhyay evaluate the performance of three clustering algorithms using four cluster validity indices, including Davies–Bouldin index, Dunn index, Calinski–Harabasz index and a newly developed index. Wang et al. have suggested an improved index for clustering validation based on Silhouette indexing and Calinski–Harabasz index.

Finding the optimal number of clusters

Similar to other clustering evaluation metrics such as Silhouette score, the CH index can be used to find the optimal number of clusters k in algorithms like k-means, where the value of k is not known a priori. This can be done by following these steps:

1. Perform clustering for different values of k.
2. Compute the CH index for each clustering result.
3. The value of k that yields the maximum CH index is chosen as the optimal number of clusters.

Implementations

The scikit-learn Python library provides an implementation of this metric in the sklearn.metrics module.

R provides a similar implementation in its fpc package.

See also

• Cluster analysis
• Silhouette score
• Davies–Bouldin index
• Dunn index