Cluster Analysis: Methods, Algorithms & Applications

TAKEAWAYS:

• Clustering groups unlabeled data into meaningful clusters based on similarity, requiring no predefined classes.
• Key algorithms include partitioning (K-means), hierarchical (agglomerative/dendrogram), density-based (DBSCAN), and grid-based (STING) methods.
• Distance metrics (Euclidean, Manhattan, cosine) and similarity measures (Jaccard, Pearson) define how data points are compared.
• Real-world uses include customer segmentation (e.g., Daraz’s recommendation systems), fraud detection (e.g., Ncell’s anomaly clustering), and medical imaging (e.g., tumor classification in hospitals).
• Challenges include scalability (large datasets), determining the optimal number of clusters, and handling noise/outliers.
• Evaluation metrics like silhouette score, Davies-Bouldin index, and elbow method help assess clustering quality.

1. Introduction to Cluster Analysis

Cluster analysis is an unsupervised learning technique that groups similar data points together without prior knowledge of labels. Unlike supervised learning (e.g., classification), clustering discovers hidden patterns in data, making it useful for exploratory data analysis.

Key Characteristics of Clustering

• No predefined classes: Algorithms learn patterns from data.
• Similarity-based grouping: Points in the same cluster are more similar to each other than to points in other clusters.
• Applications:
  • Market segmentation (e.g., Daraz grouping customers by purchasing behavior).
  • Image segmentation (e.g., separating objects in satellite imagery).
  • Anomaly detection (e.g., Ncell identifying unusual call patterns).

Types of Clustering Algorithms

Clustering algorithms can be categorized based on their approach:

2. Partitioning Methods: K-means Clustering

K-means is the most widely used clustering algorithm, especially for large datasets. It partitions data into k clusters by minimizing within-cluster variance.

How K-means Works

1. Initialize: Randomly select k centroids (cluster centers).
2. Assign: Assign each data point to the nearest centroid.
3. Update: Recalculate centroids as the mean of all points in the cluster.
4. Repeat: Iterate until centroids stabilize (convergence).

Worked Example: Customer Segmentation for Daraz

Suppose Daraz wants to segment customers based on purchase frequency (X) and average spending (Y). We use K-means with k=3 on the following data:

Step-by-Step Trace:

1. Initialize centroids: Suppose we start with centroids at (5,200), (10,500), and (3,100).
2. Assign points:
   • A → Cluster 1 (nearest to (5,200))
   • B → Cluster 2 (nearest to (10,500))
   • C → Cluster 3 (nearest to (3,100))
   • D → Cluster 1 (distance to (5,200) < distance to others)
   • E → Cluster 2
3. Update centroids:
   • Cluster 1: Mean of A(5,200) and D(8,300) → (6.5, 250)
   • Cluster 2: Mean of B(10,500) and E(12,600) → (11, 550)
   • Cluster 3: C(3,100) → remains (3,100)
4. Reassign and repeat until centroids converge.

Final Clusters:

• Cluster 1 (Low-frequency, moderate spend): A, D
• Cluster 2 (High-frequency, high spend): B, E
• Cluster 3 (Low-frequency, low spend): C

Visualization of Clusters:

Advantages and Limitations of K-means

Choosing the Optimal k (Elbow Method)

To determine the best k, plot the within-cluster sum of squares (WCSS) for different k values. The "elbow" point (where the rate of decrease slows) is the optimal k.

Example: For Daraz’s data, the elbow occurs at k=3, confirming our choice.

3. Hierarchical Clustering

Hierarchical clustering builds a dendrogram (tree-like structure) to represent nested clusters. It can be agglomerative (bottom-up) or divisive (top-down).

Agglomerative Hierarchical Clustering (Bottom-Up)

1. Treat each point as a cluster.
2. Merge the two closest clusters iteratively.
3. Stop when all points are in a single cluster or a threshold is met.

Worked Example: Traffic Route Optimization for Kathmandu

Suppose NTC wants to cluster traffic routes based on congestion levels (X) and average speed (Y). Data:

Dendrogram Construction:

1. Start with single-point clusters: {A}, {B}, {C}, {D}.
2. Merge B and D (smallest distance: Euclidean distance between (5,30) and (3,40) = 10.4).
3. Merge A and C (distance between (8,20) and (7,25) = 5.4).
4. Finally, merge {A,C} and {B,D}.

Advantages and Limitations

4. Density-Based Clustering: DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups points based on density, making it ideal for clusters of arbitrary shapes and identifying outliers.

Key Concepts

• ε-neighborhood: All points within distance ε of a given point.
• Core point: A point with at least minPts neighbors within ε.
• Border point: A point within ε of a core point but not a core point itself.
• Noise: Points that are neither core nor border points.

Worked Example: Fraud Detection in Ncell Transactions

Ncell wants to detect fraudulent transactions using DBSCAN. Suppose:

• ε = 10 (distance threshold)
• minPts = 3 (minimum points to form a cluster)

Data (Transaction Amount vs. Frequency):

Clustering Steps:

1. Core Points: A, B, C (all within ε=10 of each other in frequency).
2. Noise: D, E (isolated high-amount transactions → potential fraud).
3. Border Point: F (within ε of A but not a core point).

Visualization:

graph TD
    A["A(500,1)"] -->|"Core"| C1["Cluster 1"]
    B["B(500,2)"] -->|"Core"| C1
    C["C(500,3)"] -->|"Core"| C1
    D["D(5000,1)"] -->|"Noise"| N["Noise"]
    E["E(5000,1)"] -->|"Noise"| N
    F["F(500,100)"] -->|"Border"| C1

Advantages and Limitations

5. Grid-Based Clustering: STING

STING (Statistical Information Grid) divides space into a grid and clusters dense cells. It is efficient for spatial data (e.g., GPS coordinates).

How STING Works

1. Divide space into rectangular cells.
2. Compute statistics (e.g., mean, count) for each cell.
3. Merge cells with similar densities into clusters.

Example: Location-Based Marketing for Pathao

Pathao wants to cluster high-demand areas in Kathmandu based on latitude (X) and longitude (Y). Suppose the grid is divided into 4 cells:

Clustering:

• Cells 1 and 3 have high demand → merged into a "High-Demand Cluster."
• Cells 2 and 4 → "Low-Demand Cluster."

Advantages and Limitations

6. Model-Based Clustering: Gaussian Mixture Models (GMM)

GMM assumes data is generated from a mixture of Gaussian distributions. It uses Expectation-Maximization (EM) to estimate parameters.

Example: Stock Price Analysis for NEPSE

Suppose NEPSE wants to cluster daily stock price changes into volatility patterns. Data (Daily Return % vs. Volume):

GMM fits a mixture of Gaussians to identify:

• High-volatility, high-return cluster (Day 3).
• Low-volatility, stable cluster (Days 1, 2, 4).

Advantages and Limitations

7. Clustering Evaluation Metrics

To assess clustering quality, use:

Example: For Daraz’s K-means clustering, a silhouette score of 0.65 indicates reasonably good separation.

8. Applications of Cluster Analysis

In the Real World

1. E-commerce (Daraz, Amazon):

   • Use: Customer segmentation based on purchase history.
   • How: K-means clusters users into "high-spenders," "bargain hunters," and "occasional buyers" to personalize recommendations.

2. Telecom (Ncell, NTC):

   • Use: Fraud detection in call data.
   • How: DBSCAN identifies unusual call patterns (e.g., sudden high-frequency calls from a single SIM).

3. Healthcare (Hospitals):

   • Use: Disease outbreak prediction.
   • How: Hierarchical clustering groups regions by infection rates to allocate resources.

4. Finance (Banks):

   • Use: Credit risk assessment.
   • How: GMM clusters loan applicants into "low-risk," "medium-risk," and "high-risk" groups.

5. Social Media (WhatsApp, YouTube):

   • Use: Community detection.
   • How: DBSCAN groups users into "active communities" based on interaction patterns.

9. Challenges in Clustering

• Scalability: Algorithms like hierarchical clustering struggle with large datasets.
• Determining k: No universal method; elbow method or silhouette score helps.
• Noise and Outliers: DBSCAN handles noise, but K-means is sensitive to outliers.
• High-Dimensional Data: Distance metrics become less meaningful (e.g., "curse of dimensionality").
• Interpretability: Clusters may not align with business logic (e.g., "Cluster 2" may not have a clear name).

Exam Tip

For TU/PU/NEB exams, focus on:

1. Definitions: Clearly distinguish between partitioning, hierarchical, density-based, and grid-based clustering.
2. Algorithms: Know the steps of K-means, DBSCAN, and hierarchical clustering inside out.
3. Worked Examples: Be ready to apply K-means or DBSCAN to a small dataset (e.g., 5-6 points).
4. Evaluation Metrics: Explain silhouette score and elbow method with an example.
5. Real-World Applications: Link clustering to e-commerce (Daraz), fraud detection (Ncell), or healthcare.
6. Limitations: Discuss why K-means fails for non-spherical clusters and how DBSCAN handles noise.

Common Exam Questions:

• "Explain K-means clustering with a step-by-step example."
• "How does DBSCAN differ from K-means?"
• "What is the elbow method, and how is it used?"
• "Apply hierarchical clustering to the given dataset."
• "Discuss the applications of clustering in Nepalese industries (e.g., banking, telecom)."

Visual Summary of Clustering Algorithms: