-1
$\begingroup$

I am trying to stop at best quality metric in my clustering task. (I make spectral clustering using k-means).

In short, I calculate intra-cluster pair-wise distances, take their square and sum them up for each cluster.

After I get those intra-cluster metrics, I sum them across all clusters.

I think that better clustering should produce lower values of this metric.

Below is the code of the function I am using.

# function to compute clustering quality

rm(avg_sil)

avg_sil <- function(k, df = evL$vectors) {

     gc()

     km.res <- kmeans(
          df[,(ncol(df)-k+1):ncol(df)]
          , centers = k #df[sample(nrow(df), k, replace = F),(ncol(df)-k+1):ncol(df)]
          , algorithm = "MacQueen"
          , nstart = 25
          , iter.max = 1000
          )

     dists <- sapply(
          unique(km.res$cluster)
          , function(x){
               sum(
                    dist(
                         df[km.res$cluster == x, (ncol(df)-k+1):ncol(df)]
                         , method = "euclidean"
                         ) ^ 2
                )
          }
     )

     sum(dists)
}

I got some interesting results that advise to use 23 clusters as an optimal number. It is a little counterintuitive because I would expect that more clusters will generate lower intraclass distances and as a result lower sum of their squares. Just because the number of pair-wise comparisons by cluster should decrease in a power fashion, and so should the sum.

enter image description here

Do you think such a metric makes sense?

As a note: earlier in this study I found that the optimal cluster number may be 50 by analyzing a spike of the eigenvalues of the laplacian of my proximity matrix.

D <- diag(apply(A, 1, sum)) # sum rows

U <- D - A

evL <- eigen(U, symmetric=TRUE)

ei_vals <- rev(evL$values)[1:100]

plot(ei_vals + 0.0001, log="y")

enter image description here

Update:

Well, it looks that lots of the points that I cluster just collapse in one dot?

> table(km.res$cluster)

   1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23 
   2    1    1    1    1    2    1 2551    4    3    4    3    8    1    2    1    4    3    1    5    1    3    3


> di <- round(dists, 2)
> names(di) <- unique(km.res$cluster)
> di
    8     6     3     7    19    11    20    22    12    18     2     4    13     1     5    17    15    23    14 
 0.00  0.33 21.58 21.96  0.70  0.25 10.41  5.30  0.33  2.70  0.64 21.50 17.01  1.89 21.24  0.51  0.00  0.44 16.50 
   16     9    10    21 
14.40  3.58  0.47 10.12 
$\endgroup$
  • $\begingroup$ Isn't it a variation of loss function minimized by k-means en.wikipedia.org/wiki/K-means_clustering#Description ? $\endgroup$ – Tim Feb 5 at 14:32
  • $\begingroup$ Thank you. Yes, indeed it is. The only major difference is that k-means exploits this measure during fit process with a fixed cluster number, and I use it to guess the best cluster number. $\endgroup$ – Alexey Burnakov Feb 5 at 14:40
  • 2
    $\begingroup$ The problem is that with $N$ clusters per $N$ samples you'd get perfect fit and the metric will be smallest. $\endgroup$ – Tim Feb 5 at 14:55
  • $\begingroup$ I understand this. I iterate over a limited region, for example, from 20 to 50 clusters, given 2500 points to cluster. $\endgroup$ – Alexey Burnakov Feb 5 at 15:00
  • 2
    $\begingroup$ Still, you can easily imagine that with more clusters, it will be more overfitting and the measure does not account for it anyhow. Moreover, it will work better for clustering algorithms that minimize it directly (k-means) and I'm not sure how useful it would be for algorithms that use different criteria for defining clusters. $\endgroup$ – Tim Feb 5 at 15:07
2
$\begingroup$

You can trivially prove that the optimum k-means result with k clusters will at least as good as the result with k-1 clusters. (Take the optimum result with k-1, and make the worst point an additional centroid).

Hence this measure (known as SSQ, inertia, etc.) is unsuitable for choosing k.

Most likely your code to compute his value is broken. Have you compared it to the result computed by the kmeans function? And why do you use MacQueens kmeans, and not the faster and better default?

Silhouette is better, but very slow: O(n²). So you probably want to choose CH Index DB Index, etc. instead.

$\endgroup$
  • $\begingroup$ Thank you. "And why do you use MacQueens kmeans, and not the faster and better default?". Other methods resulted in lots of warnings about empty clusters. "Most likely your code to compute his value is broken." It is not that trivial. The problem is that most of my data points seem to be in almost a perfectly small dot for k eigen-vectors, and while I vary k, this 'collapsing' change alos since I change the dimensionality of the problem each time (if you looked into code to see that). $\endgroup$ – Alexey Burnakov Feb 6 at 14:28
  • $\begingroup$ These are probably disconnected components, that you should have clustered separately. In spectral clustering, you are interested in non-zero eigenvalues. $\endgroup$ – Anony-Mousse Feb 6 at 15:50

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.