Clustering: Algorithms, Applications & Evaluation

TAKEAWAYS:

• Clustering groups unlabeled data into meaningful clusters based on similarity, requiring no predefined labels or target variables.
• K-means minimizes within-cluster variance by iteratively assigning points to centroids, but struggles with non-spherical clusters or varying densities.
• DBSCAN identifies clusters as dense regions separated by sparse areas, excelling at finding arbitrary shapes but sensitive to parameter choices (ε and minPts).
• Hierarchical clustering builds a tree-like structure (dendrogram) of nested clusters, offering interpretability but scaling poorly for large datasets.
• Evaluation metrics like Silhouette Score and Davies-Bouldin Index quantify cluster quality without ground truth labels.
• Real-world applications include customer segmentation (e.g., Daraz’s user groups), fraud detection (e.g., Ncell’s anomaly flags), and image compression (e.g., YouTube’s thumbnail generation).

1. Introduction to Clustering

Clustering is an unsupervised learning technique that organizes data into groups (clusters) based on similarity, without prior labels. Unlike supervised learning, clustering discovers hidden patterns in data, making it ideal for exploratory data analysis.

Key Characteristics of Clustering:

• No labeled data: Algorithms learn patterns from raw input.
• Similarity measure: Distance metrics (Euclidean, Manhattan, cosine) define cluster proximity.
• Objective: Maximize intra-cluster similarity and minimize inter-cluster similarity.

Applications in Nepal:

• E-commerce (Daraz): Groups users by purchasing behavior to personalize recommendations.
• Telecom (Ncell): Detects unusual call patterns to flag potential fraud.
• Healthcare: Classifies patient symptoms for disease outbreak prediction (e.g., COVID-19 clusters in Kathmandu).

2. Centroid-Based Clustering: K-means

K-means partitions data into K clusters by minimizing the within-cluster sum of squares (WCSS). It alternates between:

1. Assigning each point to the nearest centroid.
2. Recomputing centroids as the mean of assigned points.

How K-means Works (Step-by-Step)

1. Initialize: Randomly select K centroids.
2. Assign: Assign each data point to the nearest centroid.
3. Update: Recalculate centroids as the mean of assigned points.
4. Repeat: Stop when centroids stabilize or max iterations reach.

Worked Example: Customer Segmentation for a Kathmandu Café

Data: Monthly spending (Rs.) of 10 customers: [500, 1200, 800, 2000, 300, 1500, 900, 2500, 400, 1800] Goal: Segment customers into 2 groups (K=2) for targeted promotions.

graph TD
    A["Initialize centroids: C1=500, C2=2000"] --> B["Assign points to nearest centroid"]
    B --> C["Update centroids: C1=mean([500,300,400])=400, C2=mean([1200,800,1500,900,2500,1800])=1450"]
    C --> D["Reassign points"]
    D --> E["Check convergence (centroids unchanged)"]
    E -->|"Converged"| F["Final clusters: Low spenders (400), High spenders (1450)"]

Output Clusters:

Advantages and Limitations

Choosing K: The Elbow Method

Plot WCSS vs. K and select the "elbow" point where the rate of decrease slows.

# Pseudocode for Elbow Method
import matplotlib.pyplot as plt
wcss = []
for k in range(1, 11):
    kmeans = KMeans(n_clusters=k)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)
plt.plot(range(1, 11), wcss)
plt.xlabel('Number of clusters (K)')
plt.ylabel('WCSS')
plt.title('Elbow Method for Optimal K')

3. Density-Based Clustering: DBSCAN

DBSCAN groups data based on density connectivity, identifying clusters as dense regions separated by sparse areas. Key parameters:

• ε (eps): Maximum distance between two points to be considered neighbors.
• minPts: Minimum number of points to form a dense region (cluster).

How DBSCAN Works

1. Core Points: Points with ≥ minPts neighbors within ε.
2. Border Points: Points within ε of a core point but with < minPts neighbors.
3. Noise: Points not in any cluster.

Worked Example: Traffic Congestion Zones in Kathmandu

Data: GPS coordinates of traffic jams (simplified 2D grid). Goal: Identify dense congestion clusters (ε=0.5 units, minPts=3).

Advantages and Limitations

Real-World Use in Nepal: NTC’s Network Anomaly Detection

NTC uses DBSCAN to detect unusual call patterns in its network:

• ε: Maximum allowed deviation from normal call volume.
• minPts: Minimum calls to trigger an alert.
• Outcome: Flags potential fraud or equipment failures.

4. Hierarchical Clustering

Builds a dendrogram (tree of clusters) either:

• Agglomerative: Bottom-up (start with individual points, merge closest clusters).
• Divisive: Top-down (start with one cluster, split recursively).

Worked Example: Bank Loan Default Risk (Nepal Bank)

Data: Loan amounts (Rs. lakhs) and repayment history for 5 customers. Goal: Group similar risk profiles.

graph TD
    A["Start with 5 single-point clusters"] --> B["Merge closest pairs (Euclidean distance)"]
    B --> C["Merge {C1,C2} and {C3,C4}"] --> D["Final dendrogram with 2 clusters"]
    D --> E["Cut dendrogram at height=2 → High-risk and Low-risk groups"]

Advantages and Limitations

5. Spectral Clustering

Uses graph Laplacian to perform clustering on data represented as a similarity graph. Steps:

1. Construct a similarity graph (e.g., using Gaussian kernel).
2. Compute the graph Laplacian.
3. Apply eigenvalue decomposition to find clusters.

When to Use Spectral Clustering

• Data lies on a manifold (e.g., images, social networks).
• Clusters are non-convex or overlapping.

Example: YouTube’s video recommendation system uses spectral clustering to group similar videos based on user watch history.

6. Clustering Evaluation Metrics

Since ground truth labels are absent, use internal metrics:

Worked Example: Evaluating Café Clusters

For K=2 (from earlier), compute Silhouette Score:

• Cluster 1 (Low Spenders): Mean distance to other points = 0.2; to Cluster 2 = 1.0. Silhouette = (1.0 – 0.2) / max(1.0, 0.2) = 0.8.
• Cluster 2 (High Spenders): Similar calculation yields 0.75.
• Overall Score: (0.8 + 0.75) / 2 = 0.775 (good separation).

7. Real-World Applications

1. E-Sewa’s User Segmentation

• Algorithm: K-means (preprocessed transaction data).
• Output: 3 clusters (high-frequency, occasional, one-time users).
• Use: Tailor notification frequencies and discounts.

2. Pathao’s Driver Routing

• Algorithm: DBSCAN (GPS coordinates of drivers).
• Output: Dense driver clusters in busy areas (e.g., Thapathali, Lakshmi Marg).
• Use: Optimize ride-matching and surge pricing.

3. NEPSE Stock Analysis

• Algorithm: Hierarchical clustering (daily price movements of stocks).
• Output: Groups like "high-volatility" (e.g., NMB, NBL) vs. "stable" (e.g., NABIL, Gorkha Bank).
• Use: Portfolio diversification advice.

4. WhatsApp Chatbot for Ncell

• Algorithm: DBSCAN (user query patterns).
• Output: Clusters like "billing inquiries," "network issues," "data plans."
• Use: Route queries to specialized AI agents.

8. Choosing the Right Clustering Algorithm

## In the Real World

1. Khalti’s Fraud Detection:

   • Uses K-means to cluster transaction patterns.
   • How: Transactions with similar amounts, times, and locations are grouped. Clusters with unusually high frequency/amount trigger alerts.
   • Example: A cluster of Rs. 50,000 transfers at 3 AM from a single account flags potential money laundering.

2. Daraz’s Recommendation Engine:

   • Applies DBSCAN to user browsing history.
   • How: Dense regions in user-item interaction matrices identify "similar users." Recommendations are based on items popular in these clusters.
   • Example: A user buying electronics is grouped with others who also bought accessories, leading to "Frequently Bought Together" suggestions.

3. NTC’s Network Optimization:

   • Employs Hierarchical Clustering to analyze cell tower coverage.
   • How: Towers with similar signal strengths and call volumes are merged into "coverage zones." Helps in planning new tower placements.
   • Example: Clusters in Kathmandu’s old city show overlapping coverage, guiding NTC to optimize tower heights or frequencies.

## Exam Tip

1. Algorithm Selection:

   • K-means: Always ask about K and spherical clusters.
   • DBSCAN: Focus on ε and minPts; mention noise handling.
   • Hierarchical: Draw a dendrogram and explain the cut-off point.

2. Worked Examples:

   • Use small datasets (≤10 points) to show steps clearly.
   • For K-means, show centroid updates in a table.
   • For DBSCAN, label core, border, and noise points in the diagram.

3. Evaluation:

   • Calculate Silhouette Score for a given clustering.
   • Compare metrics (e.g., "K=3 gives a higher Silhouette Score than K=2").

4. Real-World Links:

   • Relate clustering to Nepali contexts (e.g., traffic, banking, e-commerce).
   • Example: "How would you use DBSCAN to detect fake reviews on Daraz?"

5. Common Pitfalls:

   • Scaling: Always normalize data before clustering (distance-sensitive algorithms).
   • Initialization: K-means’ sensitivity to initial centroids → use k-means++.
   • Interpretability: Hierarchical clustering’s dendrogram is often the key to full marks.