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.


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.

  • $\begingroup$ 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...? $\endgroup$ – Silas Berger Mar 14 '18 at 7:43
  • $\begingroup$ 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! $\endgroup$ – Anony-Mousse Mar 14 '18 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.