Clustering Algorithms

Clustering is an unsupervised learning technique that groups data points into clusters based on similarity — without using predefined labels. It's used for customer segmentation, anomaly detection, document grouping, and more.

Setup

Dataset: Customer Segmentation

K-Means Clustering

Finding the Optimal K — Elbow Method

Visualizing Clusters with PCA

Hierarchical Clustering

DBSCAN — Density-Based Clustering

Gaussian Mixture Models (GMM)

Cluster Evaluation Metrics

Customer Segment Profiling

Summary

In this lesson, you learned:

• ✅ K-Means clustering and the k-means++ initialization
• ✅ Finding optimal k with Elbow method and Silhouette analysis
• ✅ Visualizing clusters with PCA dimensionality reduction
• ✅ Hierarchical/Agglomerative Clustering with dendrograms
• ✅ DBSCAN for density-based and arbitrary-shape clusters
• ✅ Gaussian Mixture Models with soft assignment
• ✅ Cluster evaluation metrics (silhouette, Davies-Bouldin, Calinski-Harabasz)
• ✅ Practical customer segmentation and profiling

📤 Expected Outputs

Dataset Creation Output

Dataset shape: (500, 6)

Segment distribution:
true_segment
Mainstream         180
Budget Shoppers    150
High Value         100
Senior Modest       70
Name: count, dtype: int64

         age  annual_income  spending_score  num_purchases  avg_purchase_value
count  500.0          500.0           500.0          500.0               500.0
mean    36.8        63284.2          4012.5           27.3               401.3
std     13.2        28145.6          2891.4           12.8               289.1
min     12.0        20000.0           100.0            5.0                10.0
25%     27.0        40125.0          1750.0           16.0               175.0
50%     34.0        60500.0          3500.0           27.0               350.0
75%     44.0        82000.0          5800.0           38.0               580.0
max     78.0       165000.0         14500.0           49.0              1450.0

Scaled features shape: (500, 5)

K-Means Clustering Output

Inertia (within-cluster sum of squares): 1245.67
Number of iterations: 7

Cluster sizes:
0    180
1    150
2    100
3     70
dtype: int64

=== CLUSTER PROFILES ===
         age  annual_income  spending_score  num_purchases
cluster
0       35.2        65200.0          4050.3           27.5
1       25.1        35100.5          1520.8           26.8
2       45.3       110500.2          9020.1           28.1
3       60.2        50200.8          2510.5           27.0

Elbow Method Output

k=2: inertia=2850, silhouette=0.3012
k=3: inertia=1890, silhouette=0.3845
k=4: inertia=1245, silhouette=0.4523
k=5: inertia=1100, silhouette=0.4201
k=6: inertia=985, silhouette=0.3950
k=7: inertia=890, silhouette=0.3678
k=8: inertia=810, silhouette=0.3412
k=9: inertia=745, silhouette=0.3190
k=10: inertia=690, silhouette=0.2985

Best k by silhouette: 4 (score = 0.4523)

PCA Visualization Output

Explained variance ratio: [0.4215 0.2873]
Total variance explained: 70.9%

Hierarchical Clustering Output

K-Means vs HAC cluster sizes:
hac_cluster   0    1    2    3
cluster
0           175    3    2    0
1             2  145    1    2
2             0    1   98    1
3             1    2    0   67

Silhouette - KMeans: 0.4523, HAC: 0.4398

DBSCAN Output

DBSCAN found 4 clusters
Noise points: 35 (7.0%)
Cluster distribution:
dbscan_cluster
 0    178
 1    148
 2     95
 3     44
-1     35
Name: count, dtype: int64

eps=0.3: 8 clusters, 120 noise points
eps=0.5: 4 clusters, 35 noise points
eps=0.7: 3 clusters, 15 noise points
eps=1.0: 2 clusters, 5 noise points
eps=1.5: 1 clusters, 2 noise points

GMM Output

GMM converged: True
GMM log-likelihood: -3.2145

Cluster assignment confidence:
  High (>90%): 385 samples (77.0%)
  Medium (70-90%): 82 samples
  Low (<70%): 33 samples

Best number of components by BIC: 4

Cluster Evaluation Output

=== CLUSTERING EVALUATION ===

Algorithm              Silhouette   Davies-Bouldin   Calinski-H
--------------------------------------------------------------
K-Means                  0.4523          0.8912       512.3
HAC                      0.4398          0.9234       489.1
DBSCAN                   0.3856          1.0512       345.7
GMM                      0.4467          0.9045       498.6

Metric interpretation:
  Silhouette: -1 to 1, higher = better
  Davies-Bouldin: lower = better
  Calinski-Harabasz: higher = better

Customer Segment Profiling Output

=== CUSTOMER SEGMENT PROFILES ===

CLUSTER 0 — 180 customers (36.0%)
  Avg Age:      35 years
  Avg Income:   $65,200
  Avg Spending: $4,050
  Purchases:    28/year
  Marketing Strategy: Value deals

CLUSTER 1 — 150 customers (30.0%)
  Avg Age:      25 years
  Avg Income:   $35,100
  Avg Spending: $1,521
  Purchases:    27/year
  Marketing Strategy: Value deals

CLUSTER 2 — 100 customers (20.0%)
  Avg Age:      45 years
  Avg Income:   $110,500
  Avg Spending: $9,020
  Purchases:    28/year
  Marketing Strategy: Premium campaigns

CLUSTER 3 — 70 customers (14.0%)
  Avg Age:      60 years
  Avg Income:   $50,201
  Avg Spending: $2,511
  Purchases:    27/year
  Marketing Strategy: Value deals

⚠️ Common Mistakes

1. Feature scaling भूल जाना 🔴 — K-Means और distance-based algorithms features को scale किए बिना use करना सबसे बड़ी गलती है। Income (thousands) dominate कर लेगा age (tens) को अगर StandardScaler use नहीं किया।

1. Random K choose करना without Elbow/Silhouette — बहुत लोग n_clusters=3 randomly set कर देते हैं। हमेशा Elbow method + Silhouette score use करो optimal k find करने के लिए।

1. DBSCAN में eps और min_samples randomly set करना — ये hyperparameters बहुत sensitive हैं। Wrong eps → या तो सब एक cluster में या सब noise। k-distance plot use करो eps choose करने के लिए।

1. Clustering results को ground truth मानना 🔴 — Clustering unsupervised है, results हमेशा interpretation need करते हैं। Cluster labels arbitrary हैं (Cluster 0 ≠ "best segment")। Domain knowledge से validate करो।

1. High dimensional data पर directly clustering apply करना — Curse of dimensionality! 50+ features पर directly K-Means poor results देगा। PCA/t-SNE से dimensionality reduce करो पहले।

1. DBSCAN के noise points को ignore करना — -1 label वाले points outliers/anomalies हो सकते हैं जो business के लिए important हैं (fraud detection, unusual customers)। इन्हें analyze ज़रूर करो।

1. एक ही algorithm सबके लिए use करना — K-Means spherical clusters assume करता है, DBSCAN arbitrary shapes handle करता है, GMM soft assignments देता है। Problem के nature के according algorithm choose करो।

✅ Key Takeaways

• 🎯 Clustering unsupervised learning है — कोई labels नहीं चाहिए, algorithm खुद groups find करता है based on similarity
• 📊 K-Means सबसे popular है — fast, scalable, लेकिन spherical clusters assume करता है और k पहले से decide करना पड़ता है
• 📈 Elbow Method + Silhouette Score — optimal k find करने के दो most reliable methods हैं, दोनों together use करो
• 🌳 Hierarchical Clustering dendrogram provide करता है — visual representation of cluster hierarchy, कोई k specify नहीं करना पड़ता
• 🔵 DBSCAN density-based है — arbitrary shape clusters find कर सकता है और automatically outliers detect करता है (label = -1)
• 🎲 GMM soft clustering देता है — probability of belonging to each cluster, uncertainty quantify कर सकते हो
• 📏 Feature Scaling mandatory है — StandardScaler use करो clustering से पहले, otherwise distance calculations biased होंगे
• 🏆 Multiple metrics use करो evaluation में — Silhouette (higher=better), Davies-Bouldin (lower=better), Calinski-Harabasz (higher=better)
• 🔍 PCA visualization — high dimensional clusters को 2D में visualize करके validate करो कि clusters meaningful हैं
• 💼 Real-world application — Customer segmentation, anomaly detection, document grouping, image segmentation में clustering extensively use होता है

❓ FAQ

Q1: K-Means और DBSCAN में क्या main difference है?

Answer: K-Means spherical/round clusters assume करता है और आपको k (number of clusters) पहले से specify करना पड़ता है। DBSCAN density-based है — arbitrary shape clusters find कर सकता है, k specify नहीं करना पड़ता, और automatically outliers detect करता है। अगर data में irregular shapes हैं या noise है तो DBSCAN better है।

Q2: Silhouette Score negative कब आता है?

Answer: Silhouette score negative तब आता है जब कोई point अपने cluster से ज्यादा दूसरे cluster के close है — यानी wrong cluster में assign हो गया। Score -1 to +1 range में होता है। Negative = poor clustering, 0 = overlapping clusters, +1 = perfectly separated clusters।

Q3: GMM और K-Means में choose कैसे करें?

Answer: अगर आपको hard assignment चाहिए (each point belongs to exactly one cluster) और clusters roughly spherical हैं → K-Means। अगर आपको probability/uncertainty चाहिए (70% Cluster A, 30% Cluster B) या clusters overlapping/elliptical हैं → GMM। GMM ज्यादा flexible है but computationally expensive भी है।

Q4: Elbow method में clear elbow नहीं दिख रहा, क्या करें?

Answer: यह common problem है! Solutions: (1) Silhouette score use करो — highest score = best k, (2) Gap statistic try करो, (3) Domain knowledge apply करो — business ने कितने segments define किए हैं, (4) Multiple methods combine करो और consensus लो।

Q5: Clustering से पहले PCA करना ज़रूरी है?

Answer: PCA mandatory नहीं है clustering से पहले, but highly recommended जब: (1) Features बहुत ज्यादा हैं (>20), (2) Features correlated हैं, (3) Visualization करना है। PCA noise reduce करता है और clustering performance improve करता है। But अगर features कम हैं और independent हैं तो directly cluster कर सकते हो।

Q6: DBSCAN में eps value कैसे choose करें?

Answer: k-distance plot method use करो: (1) Each point के k-nearest neighbor (k=min_samples) distance calculate करो, (2) Distances को sort करके plot करो, (3) Plot में जहाँ sharp bend/elbow दिखे, वो eps value use करो। Typically min_samples = 2*n_features good starting point है।

Q7: Clustering results business team को कैसे explain करें?

Answer: (1) Cluster profiles बनाओ — each cluster की average characteristics table में दिखाओ, (2) Meaningful names दो — "Budget Shoppers", "Premium Buyers" etc., (3) Visualization use करो — PCA scatter plots, radar charts, (4) Actionable recommendations दो — each segment के लिए marketing strategy suggest करो। Technical metrics (silhouette etc.) avoid करो business presentation में।

Q8: Categorical features के साथ clustering कैसे करें?

Answer: K-Means directly categorical data handle नहीं कर सकता। Options: (1) K-Modes algorithm use करो (categorical के लिए designed), (2) K-Prototypes — mixed data (numerical + categorical) के लिए, (3) One-hot encoding करके K-Means use करो (but high dimensionality हो सकती है), (4) Gower distance with hierarchical clustering use करो।

🎯 Interview Questions

Q1: K-Means algorithm step by step explain करो। Time complexity क्या है?

Answer: K-Means steps: (1) Initialization — k centroids randomly select करो (या k-means++ use करो better initialization के लिए), (2) Assignment — each point को nearest centroid assign करो (Euclidean distance), (3) Update — each cluster का new centroid calculate करो (mean of all points in cluster), (4) Repeat — steps 2-3 repeat करो until convergence (centroids don't change) या max iterations reach हो जाएं।

Time Complexity: O(n × k × d × i) where n = data points, k = clusters, d = dimensions, i = iterations. Space: O(n × d + k × d).

Q2: K-Means++ initialization regular random initialization से better क्यों है?

Answer: Random initialization में problem है: अगर initial centroids close हैं तो algorithm poor local optimum में converge होता है। K-Means++ smartly centroids choose करता है: (1) First centroid randomly select, (2) अगला centroid उस point को choose करो जो existing centroids से maximum distance पर है (probability proportional to distance²), (3) Repeat until k centroids selected। यह ensures centroids spread out हैं, faster convergence और better final result मिलता है।

Q3: Silhouette Score कैसे calculate होता है? Formula बताओ।

Answer: Each point i के लिए: s(i) = (b(i) - a(i)) / max(a(i), b(i))

Where:

• a(i) = average distance of i to all other points in same cluster (intra-cluster distance)
• b(i) = minimum average distance of i to points in nearest other cluster (inter-cluster distance)

Interpretation: s(i) close to +1 → point well clustered, close to 0 → on boundary, close to -1 → probably wrong cluster. Overall silhouette = mean of all points' scores.

Q4: DBSCAN K-Means से किन scenarios में better है?

Answer: DBSCAN better है जब: (1) Clusters non-spherical/irregular shape के हैं (moon, ring shapes), (2) Outliers/noise present है — DBSCAN automatically detect करता है, K-Means force-assigns, (3) Number of clusters unknown — DBSCAN automatically determine करता है, (4) Clusters of different densities (with some tuning), (5) Data has spatial structure — geographic clustering, density variations। K-Means better है जब clusters spherical, similar size, no noise, और k known है।

Q5: Hierarchical Clustering के different linkage methods explain करो।

Answer: Linkage methods define करते हैं कि two clusters के बीच distance कैसे measure करें:

• Single linkage — minimum distance between any two points (can create elongated clusters, chaining effect)
• Complete linkage — maximum distance between any two points (compact clusters, sensitive to outliers)
• Average linkage — average distance between all pairs (compromise between single and complete)
• Ward's linkage — minimizes within-cluster variance increase when merging (tends to create equal-sized, spherical clusters, most commonly used)

Ward's generally best results देता है balanced clusters के लिए।

Q6: GMM में BIC और AIC क्या है? Model selection में कैसे use करते हैं?

Answer: BIC (Bayesian Information Criterion) = -2 × log-likelihood + k × ln(n), AIC (Akaike Information Criterion) = -2 × log-likelihood + 2k। दोनों model complexity penalize करते हैं। Lower value = better model.

BIC ज्यादा strongly penalize करता है complex models को (ज्यादा components), इसलिए simpler models prefer करता है। Practice में: different n_components के लिए BIC calculate करो, minimum BIC वाला n_components optimal है। BIC generally preferred है clustering के लिए क्योंकि overfitting avoid करता है।

Q7: Curse of Dimensionality clustering को कैसे affect करती है?

Answer: High dimensions में: (1) Distances become meaningless — सभी points लगभग equidistant हो जाते हैं (distance concentration), (2) Volume grows exponentially — data sparse हो जाता है, (3) K-Means fails — clusters overlap, centroids meaningful नहीं रहते, (4) DBSCAN fails — eps parameter work नहीं करता uniformly।

Solutions: PCA/t-SNE/UMAP से dimensionality reduce करो, feature selection करो, या specifically high-dimensional clustering algorithms (Subspace clustering, Spectral clustering) use करो।

Q8: Real-world customer segmentation project में clustering pipeline कैसी होगी?

Answer: Complete pipeline: (1) Data Collection — transactions, demographics, behavior data, (2) Preprocessing — missing values handle, outliers treat, (3) Feature Engineering — RFM features (Recency, Frequency, Monetary), derived metrics, (4) Feature Scaling — StandardScaler, (5) Dimensionality Reduction — PCA if features > 15, (6) Algorithm Selection — multiple algorithms try करो, (7) Optimal k — Elbow + Silhouette + business context, (8) Evaluation — internal metrics + domain expert validation, (9) Profiling — each segment name, characteristics, size, (10) Actionable Strategy — marketing recommendations per segment, (11) Monitoring — re-cluster periodically as customer behavior changes.

Q9: K-Means किन assumptions पर depend करता है? कब fail करता है?

Answer: K-Means assumptions: (1) Clusters spherical/isotropic shape के हैं, (2) Clusters similar size (number of points) के हैं, (3) Clusters similar density के हैं, (4) Features continuous हैं (categorical directly handle नहीं कर सकता)।

Fail cases: (1) Concentric circles/rings — DBSCAN better, (2) Elongated/non-spherical clusters — GMM/Spectral better, (3) Very different cluster sizes — larger cluster split हो सकता है, (4) High noise/outliers — outliers centroids pull करते हैं, (5) Very high dimensions — distances meaningless हो जाते हैं।

Q10: Clustering model production में deploy कैसे करते हैं?

Answer: Production deployment steps: (1) Save trained model — joblib.dump(kmeans, 'model.pkl') + scaler भी save करो, (2) Prediction pipeline — new customer आए → scale features → model.predict() → cluster assign, (3) API endpoint — Flask/FastAPI से REST API बनाओ, (4) Monitoring — cluster distributions track करो, अगर shift हो तो retrain, (5) Periodic retraining — monthly/quarterly नया data include करके re-cluster, (6) A/B testing — cluster-based marketing strategies test करो, (7) Data drift detection — input features की distribution monitor करो।

*Next Lesson: Model Evaluation →*