K-means Clustering › Number of Clusters

One of the key challenges in K-means clustering is determining the optimal number of clusters k. Since the algorithm requires us to specify k beforehand, we need reliable methods to evaluate different values of k and select the best one. Two of the most widely-used methods are the elbow method and silhouette analysis.

The elbow method is based on the principle that as we increase the number of clusters k, the within-cluster sum of squares (WCSS) or inertia will decrease. However, the rate of decrease typically slows down after the optimal number of clusters, creating an "elbow" shape in the plot of k versus WCSS.

Mathematical Foundation

The Within-Cluster Sum of Squares (WCSS), also known as inertia, is a key metric used to evaluate the compactness of clusters formed by the K-means algorithm. It measures the total squared distance between each data point and the centroid of the cluster to which it has been assigned. The goal of K-means is to minimize this value, resulting in clusters where points are as close as possible to their respective centroids.

Mathematically, WCSS for a given number of clusters $k$ is defined as:

$$\text{WCSS}(k) = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2$$

Where:

• $k$ is the number of clusters.
• $C_i$ denotes the set of data points assigned to the $i$-th cluster.
• $\mu_i$ is the centroid (mean vector) of the $i$-th cluster.
• $\|x - \mu_i\|^2$ is the squared Euclidean distance between a data point $x$ and the centroid $\mu_i$.

The WCSS value decreases as $k$ increases, because adding more clusters allows each cluster to be more compact. However, increasing $k$ indefinitely will eventually result in each data point being its own cluster, which is not useful for most applications.

The Elbow Criterion

The elbow method is a visual and intuitive technique for choosing the best number of clusters ($k$) in K-means clustering. Here’s how it works, step by step:

1. Plotting WCSS vs. $k$: For each possible value of $k$ (for example, from 1 to 10), you run K-means clustering and calculate the Within-Cluster Sum of Squares (WCSS). WCSS measures how tightly grouped the data points are within each cluster: the lower the WCSS, the more compact the clusters.

2. Looking for the "Elbow": You then plot the WCSS values on the y-axis against the number of clusters $k$ on the x-axis. As you increase $k$, WCSS will always decrease (or stay the same), because more clusters mean each cluster can be tighter. However, after a certain point, adding more clusters doesn't improve the WCSS by much. The plot typically looks like a bent arm, and the point where the curve bends sharply (like an elbow) is considered the optimal $k$.

3. Understanding the "Elbow" Mathematically: The "elbow" is the point where the rate at which WCSS decreases changes most dramatically. Before the elbow, adding clusters greatly reduces WCSS; after the elbow, the improvement is much smaller.

   To make this more precise, we can look at how WCSS changes as $k$ increases:

   • The first difference (similar to the first derivative in calculus) tells us how much WCSS drops when we add one more cluster:

     $$\text{Change at } k = \text{WCSS}(k) - \text{WCSS}(k+1)$$

     A large value means adding a cluster made a big difference; a small value means it didn’t help much.

   • The second difference (similar to the second derivative) tells us how the rate of improvement itself is changing. For discrete $k$, we estimate this using:

     $$\text{Second difference at } k \approx \text{WCSS}(k+1) - 2\,\text{WCSS}(k) + \text{WCSS}(k-1)$$

     The "elbow" is where this second difference is largest in absolute value, meaning the curve bends the most.

   In practice, you don't need to calculate derivatives. Most people simply look at the plot and pick the $k$ where the WCSS curve visibly flattens out (the point of diminishing returns).

To recapitulate all steps:

• Run K-means for a range of $k$ values (e.g., 1 to 10).
• Record the WCSS for each $k$.
• Plot WCSS versus $k$.
• Find the "elbow" (the point where adding more clusters doesn't reduce WCSS by much).

The elbow method helps you balance between having compact clusters (low WCSS) and keeping your model simple (not too many clusters). The "elbow" is the value of $k$ where adding more clusters yields only small improvements, so it’s a good choice for the number of clusters.

Keep in mind that sometimes the "elbow" is not very clear, and you may need to use your judgment or try other methods to confirm your choice.

Limitations of the Elbow Method

The elbow method has several limitations:

• The "elbow" is often subjective and not always clearly defined
• It may not work well when clusters have different sizes or densities
• The method assumes that the optimal k corresponds to a significant change in the WCSS curve
• It can be misleading when the data has a smooth, gradual decrease in WCSS

Let's visualize the elbow method in action:

This visualization shows the characteristic "elbow" shape where the rate of decrease in WCSS slows down after k=4, indicating the optimal number of clusters. The red dashed line marks the true number of clusters in our synthetic data.

Silhouette analysis offers another method for determining the optimal number of clusters by measuring how similar an object is to its own cluster compared to other clusters.

Mathematical Definition

For each data point i, the silhouette coefficient is calculated as:

$$s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}$$

Where:

• $a(i)$ is the average distance from point i to all other points in the same cluster (intra-cluster distance)
• $b(i)$ is the minimum average distance from point i to all points in any other cluster (inter-cluster distance)

Step-by-Step Calculation

Let's break down in detail how to calculate the silhouette coefficient for a single data point $x_i$:

1. Calculate the intra-cluster distance $a(i)$:

   The intra-cluster distance $a(i)$ measures how well $x_i$ is matched to its own cluster. It is defined as the average distance between $x_i$ and all other points in the same cluster $C_i$ (excluding $x_i$ itself):

   $$a(i) = \frac{1}{|C_i| - 1} \sum_{j \in C_i,\, j \neq i} \|x_i - x_j\|$$
   • $|C_i|$ is the number of points in cluster $C_i$.
   • The sum runs over all points $x_j$ in $C_i$ except $x_i$ itself.
   • $\|x_i - x_j\|$ denotes the distance (typically Euclidean) between $x_i$ and $x_j$.
   • If $x_i$ is the only point in its cluster, $a(i)$ is undefined, and the silhouette is not computed for that point.

2. Calculate the inter-cluster distance $b(i)$:

   The inter-cluster distance $b(i)$ quantifies how well $x_i$ would fit into its "neighbor" cluster, i.e., the next best cluster other than its own. For each cluster $C_k$ (where $C_k \neq C_i$), compute the average distance from $x_i$ to all points in $C_k$:

   $$d(i, C_k) = \frac{1}{|C_k|} \sum_{j \in C_k} \|x_i - x_j\|$$

   Then, $b(i)$ is the minimum of these average distances over all clusters $C_k$ not containing $x_i$:

   $$b(i) = \min_{C_k \neq C_i} d(i, C_k)$$
   • This means $b(i)$ is the average distance from $x_i$ to the nearest cluster it does not belong to.

3. Calculate the silhouette coefficient $s(i)$:

   The silhouette coefficient for $x_i$ combines $a(i)$ and $b(i)$ into a single value:

   $$s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}}$$
   • $s(i)$ ranges from -1 to 1.
   • If $s(i)$ is close to 1, $x_i$ is much closer to its own cluster than to the next nearest cluster (well-clustered).
   • If $s(i)$ is close to 0, $x_i$ lies between two clusters.
   • If $s(i)$ is negative, $x_i$ is closer to another cluster than to its own (possibly misclassified).

Summary of Steps:

• For each data point $x_i$:
  1. Compute $a(i)$: average distance to all other points in the same cluster.
  2. Compute $b(i)$: lowest average distance to all points in any other cluster.
  3. Compute $s(i)$ using the formula above.

By repeating this process for every point in the dataset, you obtain a silhouette coefficient for each point, which can be averaged to assess the overall clustering quality.

Interpretation of Silhouette Values

The silhouette coefficient ranges from -1 to +1:

• $s(i) \approx 1$: Point i is well-clustered (much closer to its own cluster than to other clusters)
• $s(i) \approx 0$: Point i is on or very close to the decision boundary between clusters
• $s(i) \approx -1$: Point i is poorly clustered (closer to other clusters than to its own)

Average Silhouette Score

The overall quality of a clustering solution is measured by the average silhouette score:

$$\text{Silhouette Score} = \frac{1}{n} \sum_{i=1}^{n} s(i)$$

Where n is the total number of data points.

Choosing the Optimal k

To determine the optimal number of clusters:

1. Calculate the average silhouette score for different values of k
2. Choose the k that maximizes the average silhouette score
3. Additionally, examine the silhouette plot to ensure that most points have positive silhouette coefficients

Silhouette analysis offers several advantages when evaluating clustering results. It gives a clear, numerical measure of clustering quality. This method is effective even when clusters vary in size and shape, and it offers useful insight into the assignment of individual data points to clusters. Unlike the elbow method, silhouette analysis is less subjective, as it relies on a well-defined mathematical criterion. Additionally, it can help identify points that may be poorly clustered or potentially misclassified.

The silhouette coefficient possesses several important mathematical properties. It is always bounded between -1 and 1. The coefficient is invariant to scaling and translation of the data, which means that the results are not affected by changes in the units or origin of the dataset. The silhouette score is also independent of the number of clusters, allowing for meaningful comparisons between clustering solutions with different values of k. This makes it a versatile tool for evaluating and comparing various clustering outcomes.

Let's visualize silhouette analysis in action with both the score comparison and detailed silhouette plots for multiple k values:

In this analysis, the silhouette score suggests that 3 clusters might be slightly better, but the elbow method and visual inspection of the charts for 4 clusters indicate that 4 clusters may provide a more meaningful grouping for real-world scenarios. This highlights the importance of combining quantitative metrics with domain intuition and visual inspection when selecting the optimal number of clusters.

When deciding which method to use for determining the optimal number of clusters in K-means clustering, consider the characteristics of your dataset. The elbow method is most effective when you expect the clusters to be well-separated and clearly defined, as it identifies the point where adding more clusters yields diminishing returns in reducing within-cluster variance. In contrast, silhouette analysis is often more informative for datasets with complex structures or clusters of varying shapes and sizes, as it evaluates how well each point fits within its assigned cluster compared to other clusters.

A practical approach is to combine both methods. Begin with the elbow method to obtain an initial estimate of the optimal number of clusters. Then, use silhouette analysis to validate and potentially refine this choice. It is also important to incorporate domain knowledge and consider any practical constraints relevant to your specific application. If the two methods suggest different values for the optimal number of clusters, silhouette analysis is generally considered more reliable due to its direct assessment of clustering quality.

Be mindful of certain warning signs during this process. If the elbow plot does not display a clear "elbow," the method may not be suitable for your data. Low average silhouette scores indicate that the clusters may not be well-separated, while negative silhouette coefficients suggest that some points may have been misclassified. In cases where the results are inconsistent or unsatisfactory, it may be necessary to revisit your data preprocessing steps or explore alternative clustering algorithms.