Clustering Algorithms

Clustering partitions unlabeled data into groups (clusters) of similar instances.

Centroid-Based: K-Means

K-Means partitions data into $K$ clusters by minimizing the Within-Cluster Sum of Squares (Inertia):

$J = \sum_{j=1}^{K} \sum_{x \in C_j} ||x - \mu_j||^2$

Lloyd’s Algorithm

1. Initialize $K$ centroids $\mu_j$ randomly (or using K-Means++).
2. Assign each instance to its closest centroid: $c^{(i)} = \arg\min_j ||x^{(i)} - \mu_j||^2$.
3. Update centroids: $\mu_j = \frac{1}{|C_j|} \sum_{x \in C_j} x$.
4. Repeat steps 2-3 until convergence.

K-Means++ initialization spreads centroids far apart during initialization, reducing the risk of converging to sub-optimal local minima.

Density-Based: DBSCAN

DBSCAN groups points based on local density, classifying them into three categories:

• Core Points: At least MinPts neighbors within a radius of $\epsilon$.
• Border Points: Not core points, but within $\epsilon$ of a core point.
• Noise Points: Neither core nor border points.

DBSCAN detects the number of clusters automatically and handles outliers effectively by marking them as noise.

Hierarchical (Agglomerative) Clustering

Agglomerative clustering is a “bottom-up” approach. It begins by treating every single data point as its own cluster. It then iteratively merges the closest pairs of clusters until all points are merged into a single root cluster.

• Dendrogram: This merging process is visualized as a tree-like diagram called a dendrogram. By analyzing the vertical height of the branches in the dendrogram, one can decide on an optimal number of clusters by cutting the tree horizontally.
• WCSS: Within-Cluster Sum of Squares can also be used as a metric to evaluate cluster cohesion.

Linkage Criteria

The decision of which clusters to merge depends on the defined distance (linkage) between clusters:

• Single Linkage: The distance between two clusters is defined by their two closest members.
• Complete Linkage: The distance is defined by their two furthest members.
• Average Linkage: The average distance between all points in the two clusters.
• Ward’s Linkage: Merges clusters in a way that minimizes the total variance within all clusters.

Probabilistic: Gaussian Mixture Models

Gaussian Mixture Models (GMM) represent clusters as covariance ellipsoids rather than spheres, allowing for varying cluster shapes. GMM uses the Expectation-Maximization (EM) algorithm to assign “soft clustering” probabilities.

Example: Comparing Algorithms

The following example demonstrates clustering using scikit-learn:

from sklearn.cluster import KMeans, DBSCAN
from sklearn.datasets import make_moons

# Synthetic crescent-shaped data
X, _ = make_moons(n_samples=100, noise=0.05, random_state=42)

# K-Means (spherical clusters, K centroids)
kmeans = KMeans(n_clusters=2, n_init='auto')

# DBSCAN (density-based clusters)
dbscan = DBSCAN(eps=0.3, min_samples=5)

# Predict cluster labels
print(f"K-Means cluster labels: {set(kmeans.fit_predict(X))}")
print(f"DBSCAN cluster labels: {set(dbscan.fit_predict(X))}")

K-Means cluster labels: {0, 1}
DBSCAN cluster labels: {0, 1}

Exercise

Test your understanding of clustering paradigms:

Selecting the Number of Clusters

Choosing the parameter $K$ in K-Means is challenging. We use two main validation methods:

• The Elbow Method: Plotting inertia vs. $K$ and finding the point where the rate of decrease drops.
• Silhouette Analysis: Computing the average silhouette coefficient for all points. A higher average coefficient indicates well-defined, dense clusters.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.