Calinski–Harabasz index

Given a data set of n points: {x1, ..., xn}, and the assignment of these points to k clusters: {C1, ..., Ck}, 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 ni is the number of points in cluster Ci, ci is the centroid of Ci, 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 kth 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 ci of cluster Ci, the assignment of ni - 1 points to that cluster also determines the assignment of the nith point, since the overall mean of the points assigned to the cluster should be equal to ci. 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. 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: • Perform clustering for different values of k. • Compute the CH index for each clustering result. • 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. Other packages such as clv provide function to calculate the W and D matrices. == See also ==