Cluster Analysis: Techniques, Algorithms & Applications

What is Cluster Analysis?

Cluster analysis is an unsupervised learning technique that groups similar data points into clusters based on their features, without predefined labels. Unlike classification (supervised), it discovers hidden patterns in data.

Key Characteristics:

• No labels: Input data has no target variable.
• Similarity-based: Groups objects with similar attributes.
• Exploratory: Used to uncover unknown structures in data.

Why Use Cluster Analysis?

Applications in Nepal:

1. eSewa: Groups users by transaction behavior to personalize offers (e.g., frequent bill payers vs. one-time users).
2. Pathao: Clusters drivers by route efficiency to optimize ride assignments.
3. NTC: Analyzes call patterns to detect fraudulent SIMs (e.g., clusters of high-volume calls at odd hours).

Global Examples:

• Google: Clusters search queries to improve autocomplete suggestions.
• Netflix: Groups users by viewing habits to recommend shows.
• Banks: Identify high-risk loan applicants via spending clusters.

---

Distance Metrics: How Similarity is Measured

Clustering relies on distance metrics to quantify similarity. Common metrics:

Example: For points $A(1,2)$ and $B(4,6)$:

• Euclidean distance = $\sqrt{(4-1{)}^2+(6-2{)}^2}=5$.
• Manhattan distance = $|4-1|+|6-2|=7$.

---

Clustering Algorithms

1. Partitioning Methods (K-means)

How it works:

1. Randomly select $K$ centroids.
2. Assign each point to the nearest centroid.
3. Recalculate centroids as the mean of assigned points.
4. Repeat until convergence.

Worked Example: Cluster these 5 points into $K=2$ groups using K-means:

Points: (2,3), (4,5), (6,7), (8,9), (1,1)

1. Step 1: Choose centroids at $(2,3)$ and $(8,9)$.
2. Step 2: Assign points:
   • Cluster 1: $(2,3),(1,1)$
   • Cluster 2: $(4,5),(6,7),(8,9)$
3. Step 3: Recalculate centroids:
   • New centroid 1: $\left(\frac{2+1}{2},\frac{3+1}{2}\right)=(1.5,2)$
   • New centroid 2: $\left(\frac{4+6+8}{3},\frac{5+7+9}{3}\right)=(6,7)$
4. Repeat: No further changes → Final clusters:
   • Cluster 1: $(1,1),(2,3)$
   • Cluster 2: $(4,5),(6,7),(8,9)$

Real-World Tie-In: Daraz could use K-means to group customers by purchase frequency to target promotions. For example:

• Cluster 1: High-frequency buyers (e.g., weekly orders).
• Cluster 2: Low-frequency buyers (e.g., seasonal shoppers).

---

2. Hierarchical Clustering

How it works:

• Agglomerative: Starts with each point as a cluster, merges the closest pairs iteratively.
• Divisive: Starts with one cluster, splits recursively.

Example: Cluster these 4 points hierarchically:

Points: A(1,2), B(1,4), C(5,6), D(5,8)

1. Step 1: Compute pairwise distances (Euclidean):
   • $d(A,B)=2$, $d(A,C)=5.1$, $d(A,D)=7.2$, etc.
2. Step 2: Merge closest pair: $A$ and $B$ → Cluster $\{A,B\}$.
3. Step 3: Recompute distances (e.g., $d(\{A,B\},C)=5.0$).
4. Step 4: Merge $\{A,B\}$ and $C$ → Cluster $\{A,B,C\}$, then merge with $D$.

Visualization:

Dendrogram (tree of merges):

        ________D______
       /                   \
{A,B}                     C
 /   \                     /
A     B                   D

Use Case: NEPSE could use hierarchical clustering to group stocks by volatility for portfolio diversification.

---

3. Density-Based: DBSCAN

How it works:

• Groups points in dense regions, marks outliers as noise.
• Parameters:
  • eps: Maximum distance between two points to be considered neighbors.
  • minPts: Minimum points to form a dense region.

Example: For eps=3 and minPts=2:

Points: (1,2), (2,3), (3,1), (10,10), (11,11)

1. Step 1: Start at $(1,2)$:
   • Neighbors: $(2,3),(3,1)$ → Form cluster 1.
2. Step 2: $(10,10)$ has no neighbors within eps=3 → Noise.
3. Result:
   • Cluster 1: $(1,2),(2,3),(3,1)$
   • Noise: $(10,10),(11,11)$

Real-World Tie-In: Ncell could use DBSCAN to detect fraudulent call clusters (e.g., spam calls in a dense region vs. isolated outliers).

---

Cluster Validation

Internal Metrics:

Example: For $K=2$ to $5$, the elbow occurs at $K=3$:

Distortion: [50, 30, 15, 12, 10]

→ Choose $K=3$.

---

Advanced Techniques

1. Fuzzy C-Means

• Allows points to belong to multiple clusters with membership probabilities.
• Useful when hard boundaries don’t exist (e.g., customer segments overlapping).

2. Spectral Clustering

• Uses graph Laplacian to improve partitioning for non-convex clusters.

3. Model-Based Clustering

• Assumes data is generated from a mixture of distributions (e.g., Gaussian Mixture Models).

---

Applications in Nepal

Example: Khalti could cluster merchants by transaction volume to detect high-risk accounts:

• Cluster 1: Low-volume merchants (safe).
• Cluster 2: High-volume merchants (flag for review).

---

Challenges and Limitations

• Scalability: Hierarchical clustering is $O(n^3)$.
• Parameter Sensitivity: K-means needs $K$; DBSCAN needs eps and minPts.
• Interpretability: Dense clusters may not align with business logic.

---

Exam Tip

1. Algorithm Selection:

   • K-means: Fast, scalable, but assumes spherical clusters.
   • DBSCAN: Handles noise, but struggles with varying densities.
   • Hierarchical: Interpretability (dendrograms), but slow for large data.

2. Worked Examples:

   • Always show distance calculations (Euclidean/Manhattan).
   • For K-means, demonstrate centroid updates step-by-step.
   • For DBSCAN, highlight eps-neighborhoods and noise points.

3. Real-World Links:

   • Tie clustering to customer segmentation, fraud detection, or traffic analysis.
   • Example: "How would Pathao use K-means to optimize driver assignments?"

4. Validation:

   • Know Silhouette Score and Elbow Method for choosing $K$.
   • Compare algorithms using time complexity (e.g., K-means is $O(n)$ per iteration).

---

Hierarchical clustering dendrogram for 6 data points. (Image: This picture is a work by Emmanuel Douzery. Please credit th, CC BY-SA 4.0, via Wikimedia Commons)