Gfyuki

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.