Clustering Algorithms - Discovering Patterns in Unlabeled Data

Clustering is one of the most fundamental unsupervised learning tasks. It groups similar data points together without prior knowledge of group labels. This post explores major clustering algorithms and when to use them.

What is Clustering?

Clustering partitions data into groups where:

• Similar points: Close together in the same cluster
• Different points: Separated into different clusters
• No labels: Groups discovered from data itself

Key Metric: Similarity (or distance) between points. Close points are similar; distant points are different.

Distance Metrics

Clustering algorithms use distance to measure similarity.

Euclidean Distance

Formula: √[(x₁-y₁)² + (x₂-y₂)² + … + (xₙ-yₙ)²]

Intuition: Straight-line distance between points

When to Use:

• Continuous numerical data
• Most common choice
• Good general baseline

Manhattan Distance

Formula: |x₁-y₁| + |x₂-y₂| + … + |xₙ-yₙ|

Intuition: City-block distance (right angles)

When to Use:

• When dimension independence matters
• Sparse data
• Robust to outliers

Cosine Similarity

Formula: (A·B)/(||A|| ||B||)

Intuition: Angle between vectors

When to Use:

• Text and document clustering
• High-dimensional sparse data
• Care about direction, not magnitude

Correlation Distance

Formula: 1 - Correlation(X,Y)

When to Use:

• Time series clustering
• When relative patterns matter more than absolute values

K-Means: The Most Popular Algorithm

How K-Means Works

1. Initialization: Randomly choose K initial cluster centers
2. Assignment: Assign each point to nearest center
3. Update: Calculate new centers as mean of assigned points
4. Repeat: Steps 2-3 until convergence (centers don’t move)

Pseudocode:

Initialize K random centers
While not converged:
    Assign each point to nearest center
    Update each center to mean of assigned points

Example: Clustering Customer Spending Patterns

Data: Annual spending of 1000 customers

Step 1: Random initialization
    Center 1: $5000/year
    Center 2: $15000/year
    Center 3: $40000/year

Step 2: Assign customers to nearest center
    $4500 customer → Center 1
    $14800 customer → Center 2
    $41000 customer → Center 3

Step 3: Update centers
    Center 1: mean of assigned customers ($4800)
    Center 2: mean of assigned customers ($15200)
    Center 3: mean of assigned customers ($40500)

Repeat until stable

Advantages

• Simple: Easy to understand and implement
• Fast: Efficient for large datasets
• Scalable: Works well with millions of points
• Versatile: Works with any distance metric

Disadvantages

• Must Specify K: Need to know number of clusters beforehand
• Random Initialization: Different runs may give different results
• Assumes Spherical Clusters: Works poorly with elongated clusters
• Sensitive to Outliers: Outliers pull cluster centers
• May Not Converge to Optimal: Gets stuck in local optima

Choosing K

Elbow Method:

1. Run K-means for K = 1, 2, 3, …, N
2. Calculate within-cluster sum of squares (WCSS)
3. Plot WCSS vs K
4. Look for “elbow” - point where curve bends
5. That K is usually optimal

Silhouette Score:

• Measures how well points fit into clusters
• Ranges -1 to 1 (higher is better)
• Calculate for different K values
• Pick K with highest average silhouette score

Domain Knowledge:

• How many groups make sense for your problem?
• Business context may constrain K

Hierarchical Clustering

Creates tree-like structure of clusters.

Agglomerative (Bottom-Up)

Process:

1. Start: Each point is its own cluster
2. Repeatedly merge closest pair of clusters
3. Continue until single cluster remains
4. Tree structure (dendrogram) shows merge history

Linkage Methods (define cluster distance):

• Single Linkage: Distance between closest points

  • Chains clusters together
  • Prone to creating long thin clusters

• Complete Linkage: Distance between farthest points

  • More balanced clusters
  • Tends to create compact, spherical clusters

• Average Linkage: Average distance between all pairs

  • Good compromise
  • Often better than single or complete

• Ward Linkage: Minimizes within-cluster variance

  • Similar to K-means objective
  • Usually best for general purposes

Dendrogram Reading:

• Horizontal axis: Data points
• Vertical axis: Distance/dissimilarity
• Height of connections: When clusters merge
• Cut at height h: Get clusters at that level

Divisive (Top-Down)

Process:

1. Start: All points in one cluster
2. Recursively split clusters
3. Continue until each point is own cluster
4. Also creates dendrogram

(Less common than agglomerative)

Advantages

• No K Required: Can choose number of clusters post-hoc from dendrogram
• Interpretable: Dendrogram shows cluster relationships
• Flexible: Different linkage methods for different problems
• Hierarchical Structure: Shows clusters at multiple levels

Disadvantages

• Computationally Expensive: O(n²) or O(n³) complexity
• Slow for Large Data: Usually not practical for 100k+ points
• Irreversible Decisions: Once merged, can’t be unmerged
• Dendrogram Interpretation: Can be subjective

DBSCAN: Density-Based Clustering

Finds clusters of arbitrary shape based on point density.

How DBSCAN Works

1. Parameters: ε (epsilon) = neighborhood radius, MinPts = minimum points in neighborhood
2. Core Points: Points with ≥ MinPts neighbors within ε
3. Border Points: Non-core points within ε of core point
4. Noise Points: Points neither core nor border
5. Clusters: Connected core points and their border points

Intuition: Clusters are dense regions separated by sparse regions

Example

With ε=2 and MinPts=3:

Points:     xx  x  xxxxx  x  xx
            ││  │  █████  │  ││
Cluster 1: ││              
Noise:         │    
Cluster 2:       █████
Noise:              │
Cluster 3:           ││

Advantages

• No K Required: Automatically finds number of clusters
• Arbitrary Shapes: Finds non-spherical clusters
• Outlier Detection: Identifies noise points
• Density-Based: Natural for many real-world problems

Disadvantages

• Parameter Tuning: ε and MinPts sensitive to data
• Varying Density: Struggles with clusters of varying density
• High Dimensions: Distance becomes less meaningful
• Not Deterministic: Tie-breaking at boundaries can vary

Parameter Selection

ε Parameter:

• Too small: Everything is noise
• Too large: Everything in one cluster
• K-distance graph: Plot distance to K-th nearest neighbor, look for “knee”

MinPts Parameter:

• Typical: 2 × dimensions
• Minimum: Number of dimensions + 1

Comparison of Clustering Methods

Practical Application: Customer Segmentation

Problem: Segment 10,000 customers by purchasing behavior

Data: Frequency, monetary value, recency

Approach:

1. Normalize features to 0-1
2. Try K-means with K=3,4,5,6 (using elbow method)
3. Also try hierarchical clustering
4. Compare results:
   • K-means: Fast, repeatable, good business sense
   • Hierarchical: See relationships between segments
5. Combine: Use hierarchical for exploration, K-means for production

Result: 4 customer segments

• Premium: High frequency, high value
• Growing: Medium frequency, increasing value
• Occasional: Low frequency, low value
• At-risk: Decreasing engagement

Clustering Best Practices

1. Normalize Features: Ensure equal weighting
2. Remove Duplicates: Exact duplicates inflate clusters
3. Handle Outliers: Decide: remove or keep?
4. Try Multiple Methods: Different algorithms highlight different patterns
5. Visualize Results: 2D/3D plots reveal quality
6. Validate: Does interpretation make business sense?
7. Document: Record parameters, decisions, rationale

Challenges and Solutions

Challenge: Too many clusters Solution: Increase K (K-means) or merge similar clusters (hierarchical)

Challenge: Too few clusters Solution: Decrease K or check ε parameter

Challenge: Outlier contamination Solution: Use DBSCAN, robust distance metrics, or remove outliers

Challenge: High-dimensional data Solution: Reduce dimensions first (PCA), use Manhattan distance, or cosine similarity

Conclusion

Clustering discovers natural groupings in data. K-means offers speed and simplicity for spherical clusters. Hierarchical clustering provides interpretability and flexibility. DBSCAN handles arbitrary shapes and detects outliers. No single algorithm is best for all problems. Understanding their characteristics helps you choose wisely, and trying multiple approaches often reveals the richest insights in your data.