What is Clustering?
Grouping Without Labels
Clustering is unsupervised learning - we don't have predefined labels. The goal is to discover natural groupings where observations within a cluster are similar to each other and different from observations in other clusters. It's about finding structure in unlabeled data.
Real-World Uses
Clustering applies wherever you want to discover groups: customer segments for marketing, patient subgroups for medicine, document topics for search, fraud patterns for detection. It's exploratory - revealing structure you didn't know existed.
Supervised vs Unsupervised
Classification learns from labeled examples to predict categories. Clustering discovers categories without labels. Classification asks 'which known group?'; clustering asks 'what groups exist?'. Different goals, different methods, complementary uses.
Distance Metrics
Straight-Line Distance
Euclidean distance is the straight-line distance between two points. It's the most common metric, intuitive and works well when features are continuous and on similar scales. Sensitive to scale differences - standardize features first.
City-Block Distance
Manhattan distance measures the path along grid lines, like walking city blocks. It's the sum of absolute differences. More robust to outliers than Euclidean. Good when features represent different things (can't be combined via Pythagorean theorem).
Angular Similarity
Cosine similarity measures the angle between vectors, ignoring their length. Two documents with the same word proportions but different lengths are similar by cosine. Ideal for text analysis, recommendations, and high-dimensional sparse data.
Which Distance to Use?
| Use Case | Best Metric |
|---|---|
| Continuous features, similar scales | Euclidean |
| Features on different scales | Manhattan |
| Text / document similarity | Cosine |
| Binary features | Jaccard |
| Mixed types | Gower |
Distance choice matters. Euclidean for continuous, standardized features. Manhattan for mixed scales or outlier robustness. Cosine for text and sparse data. Jaccard for binary (presence/absence). Gower for mixed data types. The wrong metric gives meaningless clusters.
K-Means Clustering
How K-Means Works
K-means iteratively assigns points to clusters and updates cluster centers. It minimizes within-cluster variance (sum of squared distances to centroid). Simple, fast, scales well to large datasets. But requires choosing k and sensitive to initialization.
K-Means in Action
Watch centroids move: start random, points get assigned to nearest centroid, centroids move to cluster centers, repeat. Centroids converge when assignments stop changing. Different initializations can give different results - run multiple times.
The Elbow Method
The elbow method plots within-cluster sum of squares against number of clusters. More clusters always reduce error, but at diminishing returns. The 'elbow' where the curve bends suggests a good k - beyond that, you're just splitting natural groups.
When K-Means Fails
K-means assumes clusters are spherical and similar in size. It struggles with elongated clusters, clusters of different densities, and is very sensitive to outliers (which pull centroids). For complex cluster shapes, consider DBSCAN or Gaussian Mixture Models.
Hierarchical Clustering
Building a Cluster Tree
Hierarchical clustering builds a tree (dendrogram) of nested clusters. Start with each point as its own cluster, then repeatedly merge the closest clusters until one remains. Cut the tree at any height to get different numbers of clusters. No need to prespecify k.
How to Measure Cluster Distance
Linkage determines how cluster distance is measured. Single linkage uses minimum distance (can create chains). Complete uses maximum (compact clusters). Average is a compromise. Ward's minimizes variance increase when merging - often produces the most interpretable clusters.
Choosing Number of Clusters
Cut the dendrogram at any height to get clusters. Large vertical gaps indicate natural cluster boundaries - cut there. Unlike k-means, you can explore multiple cluster solutions from one dendrogram. Height of merge indicates dissimilarity.
Comparing Methods
| Feature | K-Means | Hierarchical |
|---|---|---|
| Specify k? | Yes, upfront | No, decide later |
| Scalability | Very large n | Moderate n |
| Cluster shapes | Spherical | Any (varies) |
| Visualization | Scatter plot | Dendrogram |
| Deterministic? | No (random init) | Yes |
K-means is fast and scales well but needs k upfront. Hierarchical is slower (O(n²) space) but gives rich structure via dendrogram and doesn't need k. Use k-means for large datasets, hierarchical for interpretability and exploring cluster structure.
Cluster Validation
Silhouette Score
Silhouette score measures how similar a point is to its own cluster versus other clusters. Ranges from -1 to 1. High values mean points are well-matched to their cluster. Average silhouette across all points measures overall clustering quality.
Internal Validation Metrics
Internal metrics evaluate clustering without external labels. WSS measures compactness (want low). BSS measures separation (want high). Calinski-Harabasz balances both. Davies-Bouldin index measures cluster similarity (want low). Use multiple metrics.
External Validation
External validation compares clusters to known labels (if available). Adjusted Rand Index measures agreement corrected for chance. Normalized Mutual Information measures shared information. Use these to evaluate if clustering recovers known structure.
Cluster Stability Analysis
Unstable: Vary significantly → may not be real
Stability analysis tests if clusters are robust or artifacts of particular data. Resample and recluster many times. Stable clusters appear consistently. If membership changes drastically, clusters may not reflect real structure - try different k or methods.
Real-World Examples
Apply your knowledge to practical scenarios
Retail Customer Segmentation
A retailer has data on 10,000 customers: total purchases ($), visit frequency, recency (days since last purchase). They want to segment customers for targeted marketing. K-means with k=4 yields clusters.
Sample Data
{
"cluster1": {
"name": "High-Value Loyalists",
"avg_spend": "$2,500",
"frequency": "15/month",
"recency": "3 days"
},
"cluster2": {
"name": "At-Risk VIPs",
"avg_spend": "$2,000",
"frequency": "8/month",
"recency": "45 days"
},
"cluster3": {
"name": "Occasional Shoppers",
"avg_spend": "$200",
"frequency": "2/month",
"recency": "20 days"
},
"cluster4": {
"name": "Churned",
"avg_spend": "$500",
"frequency": "1/month",
"rKey Insights
- Clustering reveals actionable customer segments
- Different clusters need different marketing strategies
- Business utility matters more than perfect cluster separation
Image Color Compression
A photograph has millions of pixels, each with RGB values (0-255 for Red, Green, Blue). To compress the image, k-means clusters the colors into k=16 representative colors. Each pixel is then replaced with its nearest cluster center.
Key Insights
- K-means clustering can compress continuous data
- Compression = representing data with fewer representative values
- k controls the quality-compression trade-off
Fraud Detection via Clustering
A bank clusters credit card transactions by amount, time of day, location, and merchant type. Most transactions fall into clear clusters (normal patterns). Some transactions don't fit any cluster well.
Key Insights
- Points that don't fit any cluster may be anomalies
- Anomaly ≠ fraud; it means 'unusual, investigate further'
- Clustering provides interpretable rules for detection
Clustering Quiz
Test your understanding • Passing score: 70%