# Interpreting the C-Index

I have some problems understanding/interpreting the C-Index cluster quality measure. So, if we have

$c(x_i, x_j) = 1$ if $x_i, x_j$ in the same cluster; $0$ else

$\Gamma = \sum_ {i=1}^{n-1}\sum_ {j=i+1}^n d(x_i,x_j)*c(x_i,x_j)$

$\alpha = \sum_ {i=1}^{n-1}\sum_ {j=i+1}^n c(x_i,x_j)$

$min=$ sum of the $\alpha$ smallest $d(x_i,x_j)$ of distinct pairs $x_i,x_j$ where $x_i \neq x_j$

$max=$ sum of the $\alpha$ largest $d(x_i,x_j)$ of distinct pairs $x_i,x_j$ where $x_i \neq x_j$

then the C-Index is defined as $C=\frac{\Gamma - min}{max - min}$

The result is a value in $[0, 1]$, where lower values indicate a better cluster quality.

So, here are some things I get from this value:

• if all elements in a cluster are close together and all clusters are far apart, we can get $\Gamma=min$, which means $C=0$
• Analogously, in a worst case scenario, all the observations that are furthers apart might be in the same cluster, so we would get $\Gamma=max$, which means $C=1$

Now, these are the things I'm unsure about:

First: If we only have a single cluster in our clustering (e.g. k-Means for $k=1$), then $\alpha$ is equal to the number of distinct pairs of observations, so $max=min$, which means $C=\frac{\Gamma - min}{max - min} = \frac{\Gamma - min}{min - min} = \frac{\Gamma - min}{0}$ and we get a division by 0. A similar problem occurs if we have $N$ observations in $N$ different clusters, since $c$ is always $0$ in that case. So, is it correct to say that the C-Index can only be used for clusterings with $k$ many clusters where $1 < k < N$, for $N$ observations?

Second: Is it reasonable to say that the C-Index is agnostic to the number of clusters (e.g. the value of $k$ in k-Means)? For instance, we might have 5 observations $x_1...x_5$ close to each other, but each put into a separate cluster $C_1...C_5$. Then, we might have a clusters $C_6=\{x_6, x_7\}$ where $x_6, x_7$ are very close to each other but far apart from all other observations. In that case, $\Gamma=d(x_6,x_7)$, $\alpha=1$, $\min=d(x_6,x_7)$, so $\Gamma=min$, which means $C=0$. That is, we have the best possible C-Index-Value, even though, intuitively, it might have been better to put $x_1...x_5$ into a single cluster.

Lastly, this is more about k-Means: if we use normal k-Means (not global k-Means), are we always guaranteed to reach $C=0$, for an unbounded number of iterations? I can't seem to find an example that wouldn't result in this.

## 1 Answer

For the first Q you already give a counterexample:

It is biased to k, it prefers k = N. And it will also overrate N-1, N-2, ... So it is not agnostic to k.

If k-means would always find the best C index, then the C index would just be redundant to SSQ, which is much cheaper to compute... But you probably have just been looking at way too simple toy datasets. Use real data.

• Great, that makes sense, thanks for the answer! I still have some trouble picturing exactly how the C-Index can increase while the SSQ decreases (although I do work on a dataset where that happens), but I'll work on that ;-) Still, I don't quite see how it can prefer k = N. That would leave alpha=0, and if min and max are the alpha shortest/longest distances, that means max and min are 0, max-min=0, and we get a division by 0, right...? – Silas Berger Mar 14 '18 at 7:43
• More precisely, you get 0/0, and in most cases (you'll need to check the math yourself for this particular case though) the proper substitute then is 0. Or intuitively: if the best case equals the worst case (max=min), then any solution is perfect (0). But what you need to consider is k almost n! – Has QUIT--Anony-Mousse Mar 14 '18 at 8:48