Unit 4: Clustering Techniques

4.1 Introduction to Clustering

Clustering is an unsupervised learning technique that groups similar data points together without predefined labels. Unlike classification (supervised), clustering discovers natural structures in data.

Supervised vs Unsupervised Learning

• Supervised: Labeled training data — the algorithm learns input-output mappings (e.g., classification, regression).
• Unsupervised: No labels — the algorithm finds hidden patterns and groupings (e.g., clustering, dimensionality reduction).

Types of Clustering

• Partitioning Methods: Divide data into k non-overlapping groups (K-Means, K-Medoids). Each point belongs to exactly one cluster.
• Hierarchical Methods: Build a tree of nested clusters (Agglomerative, Divisive). Dendrograms visualize the hierarchy.
• Density-Based Methods: Group points in high-density regions, separated by low-density regions (DBSCAN, OPTICS). Can find arbitrary-shaped clusters.
• Model-Based Methods: Assume data follows a statistical model (Gaussian Mixture Models, EM algorithm). Each cluster is a probability distribution.

4.2 K-Means Clustering

K-Means is the most widely used partitioning algorithm. It partitions n data points into k clusters by minimizing the within-cluster sum of squares (SSE).

Algorithm Steps

1. Initialize: Choose k initial centroids randomly (or use K-Means++).
2. Assign: Assign each data point to the nearest centroid (using Euclidean distance).
3. Update: Recalculate centroids as the mean of all points assigned to each cluster.
4. Repeat steps 2-3 until centroids stabilize (convergence) or max iterations reached.

Elbow Method

The Elbow Method helps determine the optimal k. Plot SSE vs k — the "elbow" where SSE stops decreasing significantly indicates the best k.

Sensitivity to Outliers

K-Means is sensitive to outliers because centroids are calculated as means. A single outlier can shift the centroid significantly. K-Medoids (PAM) is more robust — it uses actual data points as cluster centers.

Pros and Cons

• Pros: Simple, fast (O(nkt)), scales well to large datasets.
• Cons: Must specify k, sensitive to initialization and outliers, assumes spherical clusters, only finds convex shapes.

4.3 Hierarchical Clustering

Hierarchical clustering builds a tree of nested clusters (dendrogram). You can cut the tree at different levels to get different numbers of clusters.

Agglomerative (Bottom-Up)

1. Start with each data point as its own cluster (n clusters).
2. Find the two closest clusters and merge them.
3. Update the distance matrix.
4. Repeat until only one cluster remains (all points merged).

Divisive (Top-Down)

1. Start with all points in one cluster.
2. Split the most heterogeneous cluster into two.
3. Repeat until each point is its own cluster.

Linkage Criteria

Linkage determines how the distance between two clusters is calculated:

• Single Linkage: Minimum distance between any two points in different clusters. Produces long, chain-like clusters. Sensitive to noise.
• Complete Linkage: Maximum distance between any two points in different clusters. Produces compact, spherical clusters. Robust to outliers.
• Average Linkage: Average distance between all pairs of points in different clusters. Compromise between single and complete.
• Ward's Method: Minimizes the total within-cluster variance after merging. Tends to produce equal-sized clusters.

4.4 DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups together closely packed points and marks outliers in low-density regions.

Core Concepts

• Epsilon (ε): Radius of the neighborhood around a point.
• MinPts: Minimum number of points required within ε for a point to be a core point.
• Core Point: A point with at least MinPts points within its ε-neighborhood (including itself).
• Border Point: Within ε of a core point but has fewer than MinPts neighbors itself.
• Noise Point: Neither core nor border — considered an outlier.

Algorithm

1. Pick an arbitrary unvisited point.
2. If it has ≥ MinPts neighbors within ε, start a new cluster.
3. Recursively add all density-reachable points to the cluster.
4. If the point has < MinPts neighbors, mark it as noise (may later become border of another cluster).
5. Repeat until all points are visited.

Limitations

• Struggles with varying densities — single ε and MinPts may not work for all regions.
• Sensitive to distance metric and parameter choice.
• High-dimensional data suffers from the curse of dimensionality.

4.5 Cluster Evaluation

Evaluating clustering quality is crucial because there are no ground-truth labels in unsupervised learning.

Internal Evaluation Metrics

• Silhouette Coefficient: Measures how similar a point is to its own cluster vs. other clusters. Range: [-1, +1]. Values near +1 indicate well-clustered; near 0 indicates overlapping clusters; near -1 indicates wrong assignment.
• SSE (Sum of Squared Errors): Sum of squared distances from each point to its centroid. Lower = tighter clusters. Used in the Elbow Method.
• Dunn Index: Ratio of minimum inter-cluster distance to maximum intra-cluster diameter. Higher = better separated clusters.
• Calinski-Harabasz Index: Ratio of between-cluster dispersion to within-cluster dispersion. Higher = better defined clusters.

External Evaluation (When Labels Exist)

• Adjusted Rand Index (ARI): Measures agreement between clustering and true labels, corrected for chance.
• Normalized Mutual Information (NMI): Measures shared information between clustering and true labels.