Clustering and Dimensionality Reduction

This lesson on Clustering and Dimensionality Reduction is hands-on and example-driven. You will be able to define, execute, and evaluate the K-means clustering algorithm, a fundamental unsupervised learning technique. You will learn how to select the optimal number of clusters ($K$) using the Elbow Method and apply the Euclidean distance metric across various data dimensions.

What You'll Be Able To Do

• Define the goal and core iterative steps of the K-means algorithm.
• Calculate the Euclidean distance between two points in N-dimensional space.
• Implement a strategy to mitigate the impact of poor random centroid initialization.
• Apply the Within-Cluster Sum of Squares (WCSS) metric to assess clustering quality.
• Interpret an Elbow Plot to heuristically determine the optimal value for $K$.

Detailed Concept Walkthrough

1. K-Means Algorithm Core Loop

K-Means is an unsupervised, iterative algorithm that partitions data points into $K$ predefined clusters by minimizing the variance within each cluster.

• Initialization: You must first select $K$, the desired number of clusters, and then randomly select $K$ distinct data points to serve as the initial cluster centers (centroids).
• Assignment Step: Each data point is assigned to the nearest centroid based on a distance metric, typically the Euclidean distance, creating $K$ initial clusters.
• Recalculation Step: The centroid of each cluster is updated by calculating the mean position of all data points currently assigned to that cluster.
• Convergence: The assignment and recalculation steps repeat until the cluster assignments no longer change, or a maximum number of iterations is reached, indicating stability.

import numpy as np
from sklearn.cluster import KMeans

# 1. Define K
K = 3
data = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]])

# 2. Initialize and Fit (handles iteration internally)
kmeans = KMeans(n_clusters=K, random_state=42, n_init=10)
kmeans.fit(data)

# 3. Get final centroids and labels
final_centroids = kmeans.cluster_centers_
labels = kmeans.labels_

Key Takeaway: K-Means minimizes intra-cluster variance by iteratively assigning points and recalculating the cluster mean until stability.

2. WCSS and Initialization Sensitivity

Cluster quality is measured by the Within-Cluster Sum of Squares (WCSS), which quantifies the total variation within all clusters; minimizing WCSS is the goal.

• WCSS Definition: WCSS is the sum of the squared distances between each data point and its assigned cluster centroid across all clusters.
• Local Minima: Because the initial centroid placement is random, a single run of K-Means may converge to a suboptimal solution (a local minimum) with a higher WCSS.
• Best Practice: To mitigate sensitivity to random initialization, the algorithm should be run multiple times (e.g., 10 or 100 restarts), tracking the WCSS for each result.
• Selection Criterion: The final clustering solution chosen for deployment is the one that achieves the lowest overall WCSS across all random initializations.

# Assuming 'data' is loaded and K is defined

best_wcss = float('inf')
best_model = None

# Run 10 times to find the global minimum WCSS
for i in range(10):
    # n_init=1 forces a single initialization per loop
    model = KMeans(n_clusters=K, n_init=1).fit(data)
    if model.inertia_ < best_wcss:
        best_wcss = model.inertia_
        best_model = model

# The best_model holds the globally optimal solution found.

Key Takeaway: Always run K-Means multiple times with different initializations and select the result that yields the lowest WCSS to avoid local minima.

3. The Elbow Method Heuristic

The Elbow Method is a heuristic used to estimate the optimal $K$ by plotting the WCSS against increasing values of $K$ and identifying the point of diminishing returns.

• Variance Reduction: As $K$ increases, the WCSS will always decrease because adding more centroids naturally reduces the distance between points and their nearest center.
• Plot Generation: Calculate the WCSS for a range of $K$ values (e.g., $K=1$ to $K=10$) and plot these values on a graph where the x-axis is $K$ and the y-axis is WCSS.
• Elbow Interpretation: The optimal $K$ is typically chosen at the 'elbow' point—the value of $K$ after which the reduction in WCSS begins to slow down significantly.
• Nuance: This method is subjective; the 'elbow' is not mathematically defined and requires expert interpretation of the variance reduction curve.

wcss_list = []
max_k = 10

# Calculate WCSS for K=1 through max_k
for k in range(1, max_k + 1):
    # Use n_init=10 for robust WCSS calculation at each K
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
    kmeans.fit(data)
    wcss_list.append(kmeans.inertia_)

# Plotting wcss_list against k=1 to 10 reveals the elbow point.

Key Takeaway: The Elbow Method identifies the optimal $K$ where the benefit of adding another cluster centroid no longer significantly reduces the total within-cluster variance.

4. Euclidean Distance Generalization

K-Means relies entirely on measuring the distance between points and centroids; the Euclidean distance is the standard metric used across all dimensionalities.

• 1D and 2D: In two dimensions (XY plane), the distance is calculated using the Pythagorean theorem, which is the basis for Euclidean distance.
• N-Dimensional Generalization: For data with $N$ features (dimensions), the Euclidean distance formula generalizes by summing the squared differences across all $N$ dimensions before taking the square root.
• Mechanism: This generalized distance calculation is the only mechanism required for K-Means to function, making it dimension-agnostic.
• Under the Hood: The distance calculation determines the assignment step, ensuring that each point is grouped with the centroid that minimizes its measured proximity.

import numpy as np

def euclidean_distance(point1, point2):
    # Assumes point1 and point2 are numpy arrays of length N
    # Calculates the generalized Euclidean distance for N dimensions
    squared_diffs = (point1 - point2) ** 2
    distance = np.sqrt(np.sum(squared_diffs))
    return distance

p1 = np.array([1, 5, 10]) # 3D point
p2 = np.array([4, 1, 12]) # 3D point
dist = euclidean_distance(p1, p2)

Key Takeaway: K-Means scales seamlessly to N-dimensional data by using the generalized Euclidean distance formula to measure proximity.

Topics Covered in Clustering and Dimensionality Reduction

1. K-Means Introduction (0:12 - 0:27) — K-means is an unsupervised algorithm designed to partition data into defined groups.
2. Initialization Step (0:58 - 1:11) — Select K and randomly choose K distinct data points as initial cluster centers.
3. Assignment Process (1:19 - 2:22) — Data points are assigned to the nearest centroid based on measured distance.
4. Recalculation and Stop (2:22 - 2:36) — New centroids are calculated as the mean of assigned points until assignments stabilize.
5. Quality Assessment (2:40 - 3:43) — WCSS measures total variation within clusters; run multiple times to find the lowest WCSS.
6. Optimizing K (3:44 - 5:03) — The Elbow Method plots WCSS vs K to find the point of diminishing returns.
7. K-Means vs Hierarchical (5:05 - 5:18) — K-Means requires a fixed K, unlike Hierarchical Clustering which determines similarity pair-wise.
8. N-Dimensional Data (5:52 - 6:36) — The generalized Euclidean distance allows K-Means to cluster data in any number of dimensions.

ML Foundations Cheat Sheet

• K-Means Clustering — Unsupervised algorithm partitioning data into K clusters

  KMeans(n_clusters=3)
  

• WCSS (Inertia) — Measures total squared distance from points to their centroid

  model.inertia_
  

• Elbow Method — Heuristic used to select the optimal number of clusters (K)

  for k in range(1, 10): ...
  

• Euclidean Distance — Standard metric for measuring proximity in N-dimensional space

  np.sqrt(np.sum((p1 - p2)**2))
  

• Random Initialization — Required step; affects final cluster assignments and WCSS

  KMeans(n_init=10)
  

Comparison Table

Common Pitfalls

• Mistake: Running K-Means only once and accepting the result. Avoid: Run multiple times and select the lowest WCSS solution.
• Mistake: Assuming the Elbow Plot gives a definitive, mathematical K. Avoid: Interpret the elbow point as a subjective heuristic.
• Mistake: Using K-Means without scaling features in high dimensions. Avoid: Ensure all features contribute equally to the distance calculation.
• Mistake: Confusing the assignment step with the recalculation step. Avoid: Assignment uses distance; recalculation uses the mean.

FAQs

• Why is K-Means considered unsupervised learning? It finds structure (clusters) in data without requiring pre-labeled training examples or target variables.
• What is the stopping condition for the K-Means algorithm? The algorithm stops when the cluster assignments of the data points no longer change between iterations.
• Does K-Means work if my data has 50 features? Yes, K-Means uses the generalized Euclidean distance formula, which works regardless of the number of dimensions (N).
• What does n_init=10 do in scikit-learn's K-Means? It runs the algorithm 10 times with different random initializations and returns the best result (lowest WCSS).