Cluster Analysis: Algorithms, Applications & Evaluation

TAKEAWAYS:

• Clustering groups unlabeled data into meaningful clusters using similarity metrics (Euclidean, Manhattan, cosine).
• Partitioning (K-means) vs. Hierarchical vs. Density-based (DBSCAN) algorithms differ in scalability, cluster shape, and noise handling.
• Evaluation metrics (Silhouette Score, DBI) measure cluster quality—higher silhouette = better separation.
• Real-world uses: Khalti segments users by transaction patterns; Ncell clusters network traffic anomalies; Daraz groups similar products for recommendations.
• Curse of dimensionality degrades clustering performance—use PCA or feature selection.
• DBSCAN excels at non-spherical clusters and noise, while K-means fails on irregular shapes but scales to large datasets.

1. What is Cluster Analysis?

Cluster analysis is an unsupervised learning technique that groups similar data points into clusters based on distance/similarity metrics. Unlike classification (supervised), it does not require predefined labels.

Key Definitions

• Cluster: A collection of objects similar to one another but dissimilar to objects in other clusters.
• Centroid: The mean position of all points in a cluster (used in K-means).
• Outlier: A data point far from any cluster (e.g., fraud in transactions).
• Feature Space: The multi-dimensional space where data points reside (e.g., customer age, income, purchase history).

Why Cluster?

• Exploratory Data Analysis (EDA): Discover hidden patterns (e.g., customer segments in eSewa).
• Anomaly Detection: Identify outliers (e.g., unusual Ncell network traffic).
• Data Compression: Reduce storage by grouping similar images (e.g., WhatsApp photo clustering).
• Market Segmentation: Group customers for targeted ads (e.g., Daraz promotions).

2. Distance/Similarity Metrics

Clustering relies on measuring how "close" data points are. Common metrics:

Worked Example: Euclidean Distance Suppose we have two customers in a 2D space (Age, Income):

• Customer A: (30, 50,000)
• Customer B: (45, 80,000) Distance = $\sqrt{(45-30{)}^2+(80,000-50,000{)}^2}=\sqrt{225+9,000,000}=3,008.3$

3. Clustering Algorithms

graph TD;
    A["Start: 5 customers"] --> B["Initialize C1=(30,50k), C2=(40,80k)"]
    B --> C["Assign A,C,E to C1, B,D to C2"]
    C --> D["Recalculate C1=((25+30+28)/3, (30k+50k+40k)/3)"]
    D --> E["Recalculate C2=((40+50)/2, (80k+120k)/2)"]
    E --> F{"Converged?"}
    F -->|"No"| C
    F -->|"Yes"| G["Final Clusters: {A,C,E}, {B,D}"]

A. Partitioning Methods (Divide into K clusters)

1. K-means Clustering

How it works:

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

Advantages:

• Fast (O(n·iterations·K)).
• Works well for spherical clusters.

Disadvantages:

• Requires pre-specifying K (use Elbow Method or Silhouette Score).
• Fails on non-spherical clusters (e.g., crescent-shaped data).

Worked Example: K-means on Customer Data Data: 5 customers with (Age, Annual_Spending):

Steps:

1. Choose K=2 (young/old, low/high spenders).
2. Initialize centroids: C1 = (30, 50,000), C2 = (40, 80,000).
3. Assign points:
   • A, C, E → C1 (young/low spenders).
   • B, D → C2 (old/high spenders).
4. Recalculate centroids:
   • C1 = ((25+30+28)/3, (30,000+50,000+40,000)/3) = (27.67, 40,000).
   • C2 = ((40+50)/2, (80,000+120,000)/2) = (45, 100,000).
5. Repeat until convergence.

2. K-medoids (PAM)

• Uses actual data points (medoids) as centroids, not means.
• More robust to outliers than K-means.

B. Hierarchical Clustering

Builds a dendrogram (tree of clusters) either:

• Agglomerative (bottom-up): Start with each point as a cluster, merge closest pairs.
• Divisive (top-down): Start with one cluster, split recursively.

graph TD
    A["Root Cluster"] --> B["Cluster 1"]
    A --> C["Cluster 2"]
    B --> D["Subcluster 1.1"]
    B --> E["Subcluster 1.2"]
    C --> F["Subcluster 2.1"]

Advantages:

• No need to pre-specify K.
• Produces hierarchy (useful for nested data).

Disadvantages:

• Slow (O(n³) for agglomerative).
• Irreversible merges/splits.

Worked Example: Agglomerative Clustering Data: 4 cities with distances (km):

Steps:

1. Start with 4 clusters: {K}, {P}, {C}, {B}.
2. Merge closest pairs: C and B (distance = 80).
   • New cluster: {C,B} (representative = midpoint).
3. Next closest: K and B (distance = 100).
   • Clusters: {K,B}, {P}, {C} (but C is already merged).
4. Final merge: {K,B} and {P} (distance = 180).
   • Dendrogram shows {K,B} and {P,C} as two main clusters.

C. Density-Based: DBSCAN

Groups points in dense regions, marks outliers as noise. Parameters:

• ε (eps): Max distance between two points to be neighbors.
• minPts: Minimum points to form a dense region.

How it works:

1. Start with an unvisited point P.
2. If P has ≥ minPts neighbors within ε, form a cluster.
3. Expand to density-reachable points.
4. Mark points with < minPts neighbors as noise.

Advantages:

• Finds arbitrary-shaped clusters.
• Robust to noise.

Disadvantages:

• Struggles with varying densities.
• Requires tuning ε and minPts.

Worked Example: DBSCAN on Ncell Network Data Data: Network latency (ms) for 5 base stations:

Parameters: ε = 5, minPts = 3.

• Cluster 1: A, B, D, E (all within 5ms of each other).
• Noise: C (no neighbors within ε).

4. Choosing the Right Algorithm

5. Evaluating Clusters

A. Internal Metrics (No Ground Truth)

Worked Example: Silhouette Score For two clusters:

• Cluster 1: Points A, B (average distance to own cluster a = 2).
• Cluster 2: Points C, D (average distance to own cluster a = 3).
• Distance between clusters b = 10.

Silhouette for A: $s=\frac{10-2}{\max (2,10)}=\frac{8}{10}=0.8$ (good).

B. External Metrics (If Labels Exist)

• Purity: % of points in a cluster matching the true label.
• Rand Index: Agreement between true and predicted clusters.

6. Real-World Applications

A. E-Commerce: Daraz Customer Segmentation

Problem: Daraz wants to target promotions. Solution: Cluster users by (Age, Income, Purchase Frequency) using K-means.

• Cluster 1: Young (20-30), low income, frequent small purchases → Target with discounts.
• Cluster 2: Older (40+), high income, infrequent large purchases → Upsell premium products.

B. Finance: Ncell Fraud Detection

Problem: Detect unusual call patterns (e.g., SIM cloning). Solution: DBSCAN on call metadata (time, duration, location).

• Cluster 1: Normal users (dense region).
• Noise: Outliers with erratic call times → Flag for investigation.

C. Healthcare: Kathmandu Traffic Optimization

Problem: Reduce congestion on busy routes. Problem: Hierarchical clustering of GPS data from Pathao drivers.

• Cluster 1: High-traffic routes (Thapathali to Lakshmi Path).
• Cluster 2: Low-traffic routes (Boudhanath to Nagarjuna).
• Action: Prioritize signal optimization for Cluster 1.

7. Challenges & Solutions

8. Exam Tip

What Examiners Look For:

1. Algorithm Selection:

   • Justify why K-means is used for customer segmentation (scalability) vs. DBSCAN for fraud detection (noise handling).
   • Marks: 3–5 for correct choice + 2 for reasoning.

2. Distance Metrics:

   • Know when to use Euclidean (coordinates) vs. Cosine (text).
   • Marks: 2 for correct formula + 1 for example.

3. Evaluation:

   • Calculate Silhouette Score or interpret a dendrogram.
   • Marks: 3 for formula + 2 for interpretation.

4. Real-World Tie-Ins:

   • Link Khalti transactions to clustering for risk assessment.
   • Marks: 2 for application + 1 for technical detail.

Common Pitfalls:

• Forgetting to normalize data before clustering (Euclidean distance is scale-sensitive).
• Using K-means on non-spherical data (e.g., crescent-shaped clusters).
• Ignoring outliers in DBSCAN (they’re meaningful!).

Sample Exam Question: "Explain how DBSCAN would detect a fraudulent transaction in Ncell’s call records. Show the steps with ε=5 and minPts=3 for the given data: [5, 7, 100, 6, 8]."

Expected Answer:

1. Define ε=5, minPts=3.
2. Identify neighbors for each point (e.g., 5 has neighbors 6,7,8).
3. Form a cluster for {5,6,7,8} (all within ε).
4. Mark 100 as noise (no neighbors within ε).
5. Conclusion: 100 is fraudulent (outlier).

9. Summary Checklist

Before the exam, ensure you can:

• Define cluster, centroid, and outlier.
• List 3 distance metrics and their use cases.
• Explain K-means, Hierarchical, and DBSCAN with pros/cons.
• Calculate Silhouette Score for a given cluster.
• Apply clustering to 2 real-world scenarios (e.g., Daraz, Ncell).
• Troubleshoot curse of dimensionality and non-spherical clusters.