Determining the number of clusters in a data set

Determining the number of clusters in a <a href="/facts/Data_set/eDvegUTK">data set</a>, a quantity often labelled k as in the <a href="/facts/K-means_clustering/vxIcqHwN">k-means algorithm</a>, is a frequent problem in <a href="/facts/Data_clustering/HUeDnWPt">data clustering</a>, and is a distinct issue from the process of actually solving the clustering problem.
For a certain class of <a href="/facts/Clustering_algorithm/HUeDnWPt">clustering algorithms</a> (in particular k-means, <a href="/facts/K-medoid/YFYaESyy">k-medoids</a> and <a href="/facts/Expectation%E2%80%93maximization_algorithm/32P2bdBc">expectation–maximization algorithm</a>), there is a parameter commonly referred to as k that specifies the number of clusters to detect. Other algorithms such as <a href="/facts/DBSCAN/EKKoHRkM">DBSCAN</a> and <a href="/facts/OPTICS_algorithm/NqbewAnI">OPTICS algorithm</a> do not require the specification of this parameter; <a href="/facts/Hierarchical_clustering/KxXs6GPK">hierarchical clustering</a> 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 (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.

Determining the number of clusters in a data set open-in-new

Determining the number of clusters in a data set