1
$\begingroup$

Can we choose automatically the K value, trying every possible values (k=1,.., n) where n is the number of instances to be clustered. We then keep the value of K for which we obtained the minimum value by the method of sum of least squares.

Can this strategy work?

$\endgroup$
1
  • 3
    $\begingroup$ One problem with this idea is that k=n will always give you the minimum least-squares value. Similarly, whatever range you allow for k, say [1, m], m will always give you the best least-squares. You need a metric that measures the trade-off between number of clusters and cluster spread. $\endgroup$
    – zachdj
    Dec 23, 2020 at 1:35

3 Answers 3

2
$\begingroup$

This is a known problem of automatic clustering, how to choose / adapt the number of clusters so it represents the "real" clusters.

Hierarchical clustering is more helpful in this regard. For algorithms like K-means this is not so easy and research has tried various approaches to determine the optimum number of clusters (eg employing Information-Theoretic criteria like Akaike information criterion - AIC).

An overview in given in wikipedia article and references therein.

Determining the number of clusters in a data set, a quantity often labelled 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.

[..]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 (i.e., when k equals the number of data points, n). 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.

$\endgroup$
1
$\begingroup$

Inspection oif within cluster sum of squares (WCSS) is one of the approaches used in selecting the number of clusters for k-means. There are other well known methods such as the elbow method.

See this R package for range of other methods for selecting number of clusters (for k-means and some others) https://cran.r-project.org/web/packages/NbClust/NbClust.pdf

$\endgroup$
5
  • $\begingroup$ But this isn't really an efficient strategy, right? $\endgroup$
    – cristid9
    Dec 23, 2020 at 0:17
  • $\begingroup$ What strategy are you referring to? Also, what do you mean by efficient? I think something like the below method is convenient. $\endgroup$
    – Suren
    Dec 23, 2020 at 1:12
  • $\begingroup$ WCSS, I was wondering wether it is efficient $\endgroup$
    – cristid9
    Dec 23, 2020 at 1:13
  • $\begingroup$ I am not quite sure what you meant by efficient? People have found other methods (for example the elbow method) are better in selecting the number of clusters compared to WCSS. $\endgroup$
    – Suren
    Dec 23, 2020 at 1:17
  • $\begingroup$ Maybe see this paper among others web.stanford.edu/~hastie/Papers/gap.pdf $\endgroup$
    – Suren
    Dec 23, 2020 at 1:19
0
$\begingroup$

To complement the answers above.

Using the elbow method, you can also determine the number of clusters quantitatively in an automatic way (as opposed to doing it by eye using this method), if you introduce the quantity called the "elbow strength". Basically, it is based on the derivative of the elbow-plot with some more information-enhancing tricks. More details about the elbow strength can be found in the supplementary information of the following publication:

https://iopscience.iop.org/article/10.1088/2632-2153/abd87c

$\endgroup$

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.