# Can someone explain the C-Index in the context of hierarchical clustering?

This is a followup to this question. I am currently trying to implement the C-Index in order to find a near-optimal number of clusters from a hierarchy of clusters. I do this by calculating the C-Index for every step of the (agglomerative) hierarchical clustering. The problem is that the C-Index is minimal (0 to be exact) for very degenerated clusterings. Consider this:

$c = \frac{S-S_{min}}{S_{max}-S_{min}}$

In this case $S$ is the sum of all distances between pairs of observations in the same cluster over all clusters. Let $n$ be the number of these pairs. $S_{min}$ and $S_{max}$ are the sums of $n$ lowest/highest distances across all pairs of observations. In the first step of the hierarchical clustering, the two closest observations (minimal distance) are merged into a cluster. Let $d$ be the distance between these observations. Now there is one pair of observations in the same cluster, so $n=1$ (all other clusters are singletons). Consequently $S=d$. The problem is that $S_{min}$ also equals $d$, because $d$ is the smallest distance (that is why the observations where merged first). So for this case, the C-Index is always 0. It stays 0 as long as only singleton clusters are merged. This means the optimal clustering according the C-Index would always consist of a bunch of clusters containing two observations, and the rest singletons. Does this mean that the C-Index is not applicable to hierarchical clustering? Am I doing something wrong? I have searched a lot, but could not find any suitable explanation. Can someone refer me to some resource that is freely available on the internet? Or, if not, at least a book I may try to get at my universities library?

• Your observation is correct, but it is all fine with C-index. C-index is 0 when the observed clustering solution does not differ from the theoretically "ideal" best one under the given (observed) number of within-cluster distances. Consider a dataset which all consists of tight pairs of objects, and the pairs are quite far apart. Hierarchical clustering under virtually any linkage method will first - on initial steps - "collect" the objects into these pairs. And all that time C-index will remain 0. Later, the clustering will come to merge between the apart pairs: C-index will abrubtly worsen. Commented May 8, 2018 at 9:49
• Algorithm to compute C-index is shown here stats.stackexchange.com/q/343878/3277. Commented May 8, 2018 at 9:50
• P.S. Don't forget that C-Index is the lower (closer to 0) is the better! Commented May 8, 2018 at 10:39