Discovering the Ideal Number of Clusters in K-Means Using the Elbow Method

The Elbow Method is a popular technique for determining the optimal number of clusters (k) in K-Means clustering. By evaluating how clustering performance changes with varying k values, this method helps identify the best k for a given dataset.

Understanding the Elbow Method

• WCSS Plotting: The method involves plotting the WCSS (Within-Cluster Sum of Squares) against different k values.
• Trend Analysis: As k increases, WCSS decreases, indicating a better fit.
• Elbow Point: The "elbow" in the plot suggests the optimal k, where improvements slow down.

How the Elbow Method Works

1. Select k Range: Choose a range of k values, such as 1 to 10.
2. Calculate WCSS: For each k, run K-Means and compute WCSS, reflecting data proximity to cluster centroids: [ \text{WCSS} = \sum_{i=1}^{k} \sum_{j=1}^{n_i} \text{distance}(x_j^{(i)}, c_i)^2 ] Here, (\text{distance}(x_j^{(i)}, c_i)) is the distance between the jth data point in cluster i and its centroid.
3. Plot Results: Graph k against WCSS.
4. Identify Elbow: WCSS decreases with more clusters, but the improvement rate drops at a certain point, marking the elbow.
   • Before Elbow: Rapid WCSS drop indicates better clustering.
   • After Elbow: Slow WCSS drop suggests diminishing returns from extra clusters.

Metrics: Distortion and Inertia

• Distortion: Measures the average squared distance between data points and their cluster centers. Lower distortion means better clustering. [ \text{Distortion} = \frac{1}{n} \sum_{i=1}^{n} \min_{c \in \text{clusters}} \left| x_i - c \right|^2 ]
• Inertia: The sum of squared distances of points to their closest cluster center, indicating total clustering error. [ \text{Inertia} = \sum_{i=1}^{n} \text{distance}(x_i, c_j^*)^2 ]

Both metrics are plotted to find the elbow, signifying the optimal number of clusters.

Implementing the Elbow Method

Step 1: Import Libraries

from sklearn.cluster import KMeans
from sklearn import metrics
from scipy.spatial.distance import cdist
import numpy as np
import matplotlib.pyplot as plt

Step 2: Create and Visualize Data

x1 = np.array([3, 1, 1, 2, 1, 6, 6, 6, 5, 6, 7, 8, 9, 8, 9, 9, 8, 4, 4, 5, 4])
x2 = np.array([5, 4, 5, 6, 5, 8, 6, 7, 6, 7, 1, 2, 1, 2, 3, 2, 3, 9, 10, 9, 10])
X = np.array(list(zip(x1, x2))).reshape(len(x1), 2)

plt.scatter(x1, x2, marker='o')
plt.xlim([0, 10])
plt.ylim([0, 10])
plt.title('Dataset Visualization')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Step 3: Build Clustering Model

distortions = []
inertias = []
mapping1 = {}
mapping2 = {}
K = range(1, 10)

for k in K:
    kmeanModel = KMeans(n_clusters=k, random_state=42).fit(X)
    distortions.append(sum(np.min(cdist(X, kmeanModel.cluster_centers_, 'euclidean'), axis=1)**2) / X.shape[0])
    inertias.append(kmeanModel.inertia_)
    mapping1[k] = distortions[-1]
    mapping2[k] = inertias[-1]

Step 4: Visualize Results

• Distortion Values

print("Distortion values:")
for key, val in mapping1.items():
    print(f'{key} : {val}')

plt.plot(K, distortions, 'bx-')
plt.xlabel('Number of Clusters (k)')
plt.ylabel('Distortion')
plt.title('The Elbow Method using Distortion')
plt.show()

• Inertia Values

print("Inertia values:")
for key, val in mapping2.items():
    print(f'{key} : {val}')

plt.plot(K, inertias, 'bx-')
plt.xlabel('Number of Clusters (k)')
plt.ylabel('Inertia')
plt.title('The Elbow Method using Inertia')
plt.show()

Step 5: Visualize Clustered Data

k_range = range(1, 5)

for k in k_range:
    kmeans = KMeans(n_clusters=k, init='k-means++', random_state=42)
    y_kmeans = kmeans.fit_predict(X)
    
    plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, cmap='viridis', marker='o', edgecolor='k', s=100)
    plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1],
                s=300, c='red', label='Centroids', edgecolor='k')
    plt.title(f'K-means Clustering (k={k})')
    plt.xlabel('Feature 1')
    plt.ylabel('Feature 2')
    plt.legend()
    plt.grid()
    plt.show()