20
$\begingroup$

Is there any way to determine the optimal cluster number or should I just try different values and check the error rates to decide on the best value?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ @berkay How do you define an error rate for this unsupervised method? (or do you mean the within SS?) $\endgroup$
    – chl
    Commented Mar 31, 2011 at 19:17
  • $\begingroup$ @chl, i can use sum of squared errors for all clusters or overall accuracy (in this case i know the class labels.) $\endgroup$
    – berkay
    Commented Mar 31, 2011 at 20:10
  • 3
    $\begingroup$ @berkay A simple algorithm for finding the No. clusters is to compute the average WSS for 20 runs of k-means on an increasing number of clusters (starting with 2, and ending with say 9 or 10), and keep the solution that has minimal WSS over this clusters set. Another method is the Gap statistic. But if you already have labelled instances, then why are you trying an unsupervised method? $\endgroup$
    – chl
    Commented Mar 31, 2011 at 20:21
  • $\begingroup$ @chl thanks, good question, we can guess the clusters depending features of the intances, i'm analyzing the new intrusion characteristics, mimicry of legal applications. $\endgroup$
    – berkay
    Commented Mar 31, 2011 at 20:30
  • 2
    $\begingroup$ I've answered a similar Q with half a dozen methods (using R) over here: stackoverflow.com/a/15376462/1036500 $\endgroup$
    – Ben
    Commented Mar 18, 2013 at 8:21

1 Answer 1

Reset to default
9
$\begingroup$

The method I use is to use CCC (Cubic Clustering Criteria). I look for CCC to increase to a maximum as I increment the number of clusters by 1, and then observe when the CCC starts to decrease. At that point I take the number of clusters at the (local) maximum. This would be similar to using a scree plot to picking the number of principal components.

SAS Technical Report A-108 Cubic Clustering Criterion (pdf)

$n$ = number of observations
$n_k$ = number in cluster $k$
$p$ = number of variables
$q$ = number of clusters
$X$ = $n\times p$ data matrix
$M$ = $q\times p$ matrix of cluster means
$Z$ = cluster indicator ($z_{ik}=1$ if obs. $i$ in cluster $k$, 0 otherwise)

Assume each variable has mean 0:
$Z’Z = \text{diag}(n_1, \cdots, n_q)$, $M = (Z’Z)-1Z’X$

$SS$(total) matrix = $T$= $X’X$
$SS$(between clusters) matrix = $B$ = $M’ Z’Z M$
$SS$(within clusters) matrix = $W$ = $T-B$

$R^2 = 1 – \frac{\text{trace(W)}}{\text{trace}(T)}$
(trace = sum of diagonal elements)

Stack columns of $X$ into one long column.
Regress on Kronecker product of $Z$ with $p\times p$ identity matrix
Compute $R^2$ for this regression – same $R^2$

The CCC idea is to compare the $R^2$ you get for a given set of clusters with the $R^2$ you would get by clustering a uniformly distributed set of points in $p$ dimensional space.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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