Determining the number of clusters in a data set, a quantity often labeled k as
in the k-means algorithm, is a frequent problem in data clustering, and is a
distinct issue from the process of actually solving the clustering problem.
For a certain class of clustering algorithms, there is a parameter
commonly referred to as k that specifies the number of clusters to detect. Other
algorithms such as DBSCAN and OPTICS algorithm do not require the
specification of this parameter; hierarchical clustering avoids the
problem altogether. The correct choice of k is often
ambiguous, with interpretations depending on the shape and scale of the
distribution of points in a data set and the desired clustering resolution of the
user. In addition, increasing k without penalty will always reduce the amount of
error in the resulting clustering, to the extreme case of zero error if each
data point is considered its own cluster. Intuitively then, the optimal
choice of k will strike a balance between maximum compression of the data
using a single cluster, and maximum accuracy by assigning each data point to
its own cluster. If an appropriate value of k is not apparent from prior
knowledge of the properties of the data set, it must be chosen somehow. There
are several categories of methods for making this decision.
Rule of thumb One simple rule of thumb sets the number
to with n as the number of objects.
The Elbow Method Another method looks at the percentage
of variance explained as a function of the number of clusters: One should
choose a number of clusters so that adding another cluster doesn't give much
better modeling of the data. More precisely, if one plots the percentage
of variance explained by the clusters against the number of clusters, the
first clusters will add much information, but at some point the
marginal gain will drop, giving an angle in the graph. The number of clusters is
chosen at this point, hence the "elbow criterion". This "elbow" cannot always
be unambiguously identified. Percentage of variance explained is the ratio of
the between-group variance to the total variance, also known as an F-test. A
slight variation of this method plots the curvature of the within group
variance. The method can be traced to speculation by Robert L. Thorndike in
1953. Information Criterion Approach
Another set of methods for determining the number of clusters are information
criteria, such as the Akaike information criterion, Bayesian information
criterion, or the Deviance information criterion — if it is possible to make a
likelihood function for the clustering model. For example: The k-means model is
"almost" a Gaussian mixture model and one can construct a likelihood for the
Gaussian mixture model and thus also determine information criterion values.
An Information Theoretic Approach Rate distortion theory has been applied
to choosing k called the "jump" method, which determines the number of clusters
that maximizes efficiency while minimizing error by information
theoretic standards. The strategy of the algorithm is to generate a distortion
curve for the input data by running a standard clustering algorithm such as
k-means for all values of k between 1 and n, and computing the distortion of
the resulting clustering. The distortion curve is then transformed by a negative
power chosen based on the dimensionality of the data. Jumps in the resulting
values then signify reasonable choices for k, with the largest jump
representing the best choice. The distortion of a clustering of some
input data is formally defined as follows: Let the data set be modeled as
a p-dimensional random variable, X, consisting of a mixture distribution of
G components with common covariance, . If we let be a set of K cluster
centers, with the closest center to a given sample of X, then the minimum
average distortion per dimension when fitting the K centers to the data is:
This is also the average Mahalanobis distance per dimension between X and the
set of cluster centers C. Because the minimization over all possible sets of
cluster centers is prohibitively complex, the distortion is computed in
practice by generating a set of cluster centers using a standard clustering
algorithm and computing the distortion using the result. The pseudo-code for
the jump method with an input set of p-dimensional data points X is:
JumpMethod(X): Let Y =
Init a list D, of size n+1 Let D[0] = 0
For k = 1 ... n: Cluster X with k clusters
Let d = Distortion of the resulting clustering
D[k] = d^(-Y) Define J(i) = D[i] - D[i-1]
Return the k between 1 and n that maximizes J(k)
The choice of the transform power is motivated by asymptotic reasoning using
results from rate distortion theory. Let the data X have a single, arbitrarily
p-dimensional Gaussian distribution, and let fixed K = floor(), for some greater
than zero. Then the distortion of a clustering of K clusters in the limit as
p goes to infinity is . It can be seen that asymptotically, the distortion of a
clustering to the power is proportional to , which by definition is
approximately the number of clusters K. In other words, for a single Gaussian
distribution, increasing K beyond the true number of clusters, which should be
one, causes a linear growth in distortion. This behavior is important
in the general case of a mixture of multiple distribution components.
Let X be a mixture of G p-dimensional Gaussian distributions with common
covariance. Then for any fixed K less than G, the distortion of a clustering
as p goes to infinity is infinite. Intuitively, this means that a
clustering of less than the correct number of clusters is unable to describe
asymptotically high-dimensional data, causing the distortion to increase
without limit. If, as described above, K is made an increasing function of p,
namely, K = floor(), the same result as above is achieved, with the value of the
distortion in the limit as p goes to infinity being equal to .
Correspondingly, there is the same proportional relationship between the
transformed distortion and the number of clusters, K.
Putting the results above together, it can be seen that for sufficiently high
values of p, the transformed distortion is approximately zero for K = G. The
jump algorithm for choosing K makes use of these behaviors to identify the most
likely value for the true number of clusters.
Although the mathematical support for the method is given in terms of
asymptotic results, the algorithm has been empirically verified to work well
in a variety of data sets with reasonable dimensionality. In addition
to the localized jump method described above, there exists a second algorithm
for choosing K using the same transformed distortion values known as
the broken line method. The broken line method identifies the jump point in the
graph of the transformed distortion by doing a simple least squares error line
fit of two line segments, which in theory will fall along the x-axis for K
= G. The broken line method is more robust than the jump method in that its
decision is global rather than local, but it also relies on the assumption of
Gaussian mixture components, whereas the jump method is fully non-parametric and
has been shown to be viable for general mixture distributions.
Choosing k Using the Silhouette The average silhouette of the data is
another useful criterion for assessing the natural number of clusters. The
silhouette of a datum is a measure of how closely it is matched to data within
its cluster and how loosely it is matched to data of the neighbouring
cluster, i.e. the cluster whose average distance from the datum is lowest. A
silhouette close to 1 implies the datum is in an appropriate cluster, while a
silhouette close to -1 implies the datum is in the wrong cluster. Optimization
techniques such as genetic algorithms are useful in determining the number of
clusters that gives rise to the largest silhouette. It is also possible to
re-scale the data in such a way that the silhouette is more likely to be
maximised at the correct number of clusters.
Cross-validation One can also use the process of
cross-validation to analyze the number of clusters. In this process, the data
is partitioned into v parts. Each of the parts is then set aside at turn as a
test set, a clustering model computed on the other v-1 training sets, and the
value of the goal function calculated for the test set. These v values are
calculated and averaged for each alternative number of clusters, and the
cluster number selected that minimizes the test set errors.
Finding Number of Clusters in Text Databases
In text databases, a document collection defined by a document by term D matrix
number of clusters can roughly be estimated by the following formula
where t is the number of non-zero entries in D. Note that in D each row
and each column must contain at least one non-zero element.
Analyzing the Kernel Matrix Kernel matrix defines the proximity of
the input information. For example, in Gaussian Radial basis function,
determines the dot product of the inputs in a higher-dimensional space, called
feature space. It is believed that the data become more linearly separable in
the feature space, and hence, linear algorithms can be applied on the data
with a higher success. The kernel matrix can thus be analyzed
in order to find the optimal number of clusters . The method proceeds by the
eigenvalue decomposition of the kernel matrix. It will then analyze the
eigenvalues and eigenvectors to obtain a measure of the compactness of the input
distribution. Finally, a plot will be drawn, where the elbow of that plot
indicates the optimal number of clusters in the data set. Unlike previous
methods, this technique does not need to perform any clustering a-priori. It
directly find the number of clusters from the data.
External links Clustergram - cluster diagnostic plot -
for visual diagnostics of choosing the number of clusters
Six methods for determining an optimal k value for k-means analysis - Answer on
stackoverflow containing R code for several methods of computing an optimal
value of k for k-means cluster analysis Bibliography
Ralf Wagner, Sören W. Scholz, Reinhold Decker: The Number of Clusters in Market
Segmentation, in: Daniel Baier, Reinhold Decker; Lars Schmidt-Thieme: Data
Analysis and Decision Support, Berlin, Springer, 157 - 176.