Hierarchical clustering
এই পাঠে যা শিখবেন
- Agglomerative ও divisive — দু'টি দৃষ্টিভঙ্গি
- চারটি linkage criteria — কখন কোনটি
- Dendrogram — কীভাবে পড়ি, কোথায় cut
- scipy ও sklearn-এ implementation
- Bangladesh-এর জেলাগুলোকে অর্থনৈতিক similarity-তে cluster
১ · কেন hierarchical?
K-Means-এর দু'টি বড় সমস্যা — $k$ আগে দিতে হয়, এবং spherical assumption। Hierarchical clustering দু'টিরই সমাধান (আংশিক)। আউটপুট একটি গাছ — দেখে আপনি যেকোনো level-এ cut করে যেকোনো $k$ পেতে পারেন। এবং linkage criterion-এর মাধ্যমে non-spherical shape-ও handle।
Bangladesh-এ ৬৪টি জেলাকে অর্থনৈতিক indicator-এ cluster করতে চান। K-Means-এ আগে $k$ বাছতে হবে। কিন্তু আপনি জানেন না — ৩টি tier (low/mid/high), নাকি ৭টি (region-by-region)? Hierarchical গাছ দেখে — সব level-এর pattern একসাথে।
Agglomerative (bottom-up): ৬৪টি জেলা শুরুতে ৬৪টি ক্লাস্টার। সবচেয়ে কাছের দু'টি merge → ৬৩। আবার নিকটতম দু'টি → ৬২। এভাবে ১টি বাকি না থাকা পর্যন্ত। অধিকাংশ লাইব্রেরিতে এটাই default।
Divisive (top-down): সব ৬৪ একটি ক্লাস্টার। K-Means দিয়ে ২ ভাগ। প্রতিটি ভাগ আবার ২ ভাগ। Recursively।
২ · Linkage — দু'টি cluster-এর "দূরত্ব"
দু'টি cluster $A$ ও $B$-এর মধ্যে দূরত্ব কীভাবে? Point-to-point দূরত্ব Euclidean সরল, কিন্তু cluster-to-cluster — অনেকভাবে define করা যায়:
-
Single linkage (nearest): $d(A, B) = \min_{a \in A, b \in B} \|a - b\|$।
সবচেয়ে কাছের দু'টি point-এর দূরত্ব। "Chaining" prone — long thin cluster তৈরি। -
Complete linkage (farthest): $d(A, B) = \max_{a \in A, b \in B} \|a - b\|$।
সবচেয়ে দূরের জোড়ার দূরত্ব। Compact, spherical cluster তৈরি। Outlier-এ sensitive। -
Average linkage: $d(A, B) = \frac{1}{|A||B|} \sum_{a, b} \|a - b\|$।
গড়। Single ও complete-এর মাঝামাঝি — robust। - Ward linkage: দু'টি cluster merge করলে total within-cluster variance কতটা বাড়ে — সেটাই দূরত্ব। K-Means-এর মত spherical bias, কিন্তু hierarchical structure।
linkage="ward"। তবে Ward শুধু Euclidean দূরত্বের সাথে কাজ করে।
৩ · Algorithm — agglomerative
- প্রতিটি point একটি cluster। Pairwise distance matrix তৈরি ($O(n^2)$)।
- সবচেয়ে কাছের দু'টি cluster খুঁজে merge ($O(n)$ স্ক্যান)।
- Merge-এর height (distance) record।
- Distance matrix update — নতুন cluster-এর সাথে অন্যদের।
- একটি cluster বাকি না থাকা পর্যন্ত পুনরাবৃত্তি।
Total complexity: $O(n^3)$ naive, $O(n^2 \log n)$ optimized (priority queue)। তাই ১০K-এর বেশি sample-এ slow। Mini-batch বা K-Means → হবে।
৪ · Dendrogram — গাছ পড়া
Dendrogram = merge-এর গাছ। X-axis-এ point, Y-axis-এ merge height (linkage distance)। দু'টি branch যেখানে join করছে — সেই height-ই তাদের cluster-হওয়ার "cost"। Y উঁচুতে cut করলে কম cluster, নিচু-তে কাটলে বেশি।
$k$ কত হবে? "Largest gap" rule — dendrogram-এ horizontal line যেখানে সবচেয়ে বড় vertical jump-এর মধ্যে দিয়ে cut করা যায়। সেই cut-এ যত branch — তত cluster।
৫ · কখন কোন linkage
- Ward: default, balanced cluster, K-Means-similar fashion। Production-এ usually ভাল।
- Complete: compact cluster চাই, outlier পরিষ্কার ছেড়ে দিতে চাই।
- Average: robust, biological taxonomy-তে জনপ্রিয়।
- Single: chain-like, manifold-like data। Galaxy distribution, social network। সাধারণ data-তে avoid।
৬ · scipy দিয়ে dendrogram — Bangladesh district
৮টি জেলার synthetic অর্থনৈতিক feature: GDP per capita, literacy %, poverty %, urbanization %।
import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.preprocessing import StandardScaler
districts = ["Dhaka", "Chittagong", "Rajshahi", "Sylhet",
"Khulna", "Barisal", "Rangpur", "Mymensingh"]
# [GDP/capita (BDT k), literacy %, poverty %, urban %]
X = np.array([
[180, 78, 12, 90], # Dhaka
[120, 72, 18, 65], # Chittagong
[85, 74, 22, 30], # Rajshahi
[95, 68, 25, 35], # Sylhet
[80, 71, 24, 28], # Khulna
[70, 68, 30, 25], # Barisal
[55, 62, 38, 18], # Rangpur
[65, 65, 32, 22], # Mymensingh
])
X_s = StandardScaler().fit_transform(X)
# Ward linkage matrix
Z = linkage(X_s, method="ward")
print("Linkage matrix (idx_a, idx_b, dist, count):")
print(Z.round(2))
# 3 cluster cut
labels = fcluster(Z, t=3, criterion="maxclust")
for d, c in zip(districts, labels):
print(f"{d:12s} → cluster {c}")৭ · sklearn-এ AgglomerativeClustering
from sklearn.cluster import AgglomerativeClustering
ac = AgglomerativeClustering(n_clusters=3, linkage="ward")
labels = ac.fit_predict(X_s)
print("sklearn labels:", labels)
# linkage compare
for link in ["ward", "complete", "average", "single"]:
ac = AgglomerativeClustering(n_clusters=3, linkage=link)
print(f"{link:9s}:", ac.fit_predict(X_s))৮ · কখন hierarchical, কখন না
- Best-fit: ছোট data (<10K), $k$ অজানা, taxonomy/তthical exploration, dendrogram visualization দরকার।
- Avoid: million-row data ($O(n^2)$ memory), online streaming, exact $k$ already known।
- Comparison: K-Means দ্রুত কিন্তু $k$ ও spherical assume; hierarchical slower কিন্তু flexible।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ Single linkage "chaining" করে কেন? কোথায় এটা ভাল আর কোথায় বিপজ্জনক?
Single linkage-এর behavior intuitive বুঝলে hierarchical clustering-এর soul ধরা পড়ে।
Mechanism:
- $d(A, B) = \min_{a, b} \|a - b\|$ — শুধু নিকটতম জোড়া matter।
- একটি ক্লাস্টার বড় হোক বা ছোট — যদি একটি point কাছে — দু'টি cluster merge।
- "Chain" তৈরি — একটি ক্লাস্টার আরেকটি ক্লাস্টারের সাথে যুক্ত হয় শুধু একটি bridge point থাকলেই।
চিত্রিত উদাহরণ: দু'টি pure dense ক্লাস্টার আছে। মাঝে noise point ছড়ানো। Single linkage প্রথমে noise point-গুলোকে merge, তারপর সেগুলোর সাথে দু'টো dense cluster merge — সব একসাথে। যা চাইছিলেন তা না।
কোথায় ভাল:
- Manifold-like data: স্প্রিং, ring, spiral — এদের topology natural।
- Galaxy filament: astrophysics-এ চমৎকার — galaxy chain কে বুঝতে।
- Social network: connection graph clustering — single linkage-এর spirit।
- Genetic distance: evolutionary tree (UPGMA-এর precursor)।
কোথায় বিপজ্জনক:
- Noisy data: bridge point একটিও যথেষ্ট সব merge করতে।
- Customer segmentation: two distinct group-এ যদি একজন মাঝামাঝি গ্রাহক থাকে — ভেঙে পড়বে।
- Outlier: outlier-ই merge trigger।
- Gaussian-like cluster: Ward বা complete অনেক ভাল।
Theoretical:
- Single linkage = minimum spanning tree (MST)-এর equivalent।
- প্রতিটি merge step MST-এর next edge।
- Graph-theoretically elegant।
Bangladesh examples:
- Padma-Meghna riverbank villages — naturally chained — single linkage suit।
- Dhaka customer dataset — Ward better।
- Disease spread network — single linkage natural।
মূল উপলব্ধি: Linkage choice domain-এ নির্ভর। "একটি bridge enough" — এটা যদি বাস্তব সম্পর্ক হয়, single। নাহলে — Ward।
প্র ০২ Hierarchical-এর $O(n^2)$ memory bottleneck production-এ কীভাবে handle করেন?
প্রকৃত production challenge। Memory সমাধানে বহু কৌশল আছে।
(১) Sample then cluster:
- ১ লাখ থেকে ১০K random sample।
- Hierarchical চালান।
- প্রতিটি cluster-এর centroid বের করে — full data assign করুন nearest centroid-এ।
- Approximate কিন্তু practical।
(২) BIRCH:
- Balanced Iterative Reducing — large data-এর জন্য specialized।
- CF-tree (clustering feature) দিয়ে compress।
- Memory-bounded, single pass।
- sklearn-এ
Birch।
(৩) Bisecting K-Means:
- Top-down divisive approach।
- প্রতিটি step-এ সবচেয়ে বড় cluster K-Means দিয়ে দু'ভাগ।
- Hierarchical-এর benefit, K-Means-এর speed।
- sklearn-এ
BisectingKMeans।
(৪) HDBSCAN:
- DBSCAN + hierarchical hybrid।
- Memory-efficient indexing।
- Density-based — outlier handle।
(৫) Approximate nearest neighbor:
- Full pairwise matrix কখনো compute না।
- প্রতিটি point-এর top-$k$ nearest find — sparse graph।
- Graph-based clustering (community detection)।
(৬) Two-stage:
- Stage 1: K-Means ১০০-৫০০ cluster।
- Stage 2: hierarchical এ centroid-গুলোর উপর।
- Best of both — production gold standard।
Cloud option:
- Spark, Dask — distributed memory।
- GPU + cuML — 10-100× speedup, memory limited।
- FAISS — Facebook-এর nearest-neighbor library।
মূল উপলব্ধি: Pure agglomerative ১০K-এর বেশি rare। Production-এ hybrid pipeline standard — sample/aggregate first, hierarchical-এর interpretability পরে।
প্র ০৩ Dendrogram-এ "কোথায় cut" — পুরোটাই subjective? Statistical guidance কোনো আছে?
Dendrogram interpretation — clustering-এর সবচেয়ে artistic অংশ। কিন্তু statistical guidance আছে।
Visual heuristics:
- Largest gap: dendrogram-এ সবচেয়ে বড় vertical jump-এর মাঝে cut।
- Inconsistency coefficient: প্রতিটি merge-এর height-এর deviation থেকে। scipy
inconsistent()। - Cluster count target: business-এ আগে fix — domain-driven।
Statistical methods:
- Silhouette across k: ভিন্ন cut-এ silhouette compute, max।
- Gap statistic: Tibshirani — clusterability test।
- Calinski-Harabasz: cut-এ between/within variance ratio।
- Bootstrap stability: resample data, cluster, agreement (ARI) maximize।
Information criteria:
- BIC/AIC — যদি model-based (e.g., GMM-equivalent)।
- Each cut → likelihood → BIC।
- Penalized for cluster count।
Domain knowledge:
- Bangladesh district economy — ৩-৫ tier (low/mid/high) policy-driven।
- Marketing — ৪-৭ persona।
- Biology taxonomy — domain expert dependency।
Multi-resolution:
- Hierarchical-এর সবচেয়ে বড় benefit — যেকোনো level-এ cut।
- "৩-cluster broad strategy + ৭-cluster tactical detail" — দু'টিই same data থেকে।
- K-Means-এ এটা impossible।
Best practice:
- Multiple criteria (silhouette + gap + visual)।
- Stability check (bootstrap)।
- Domain validation।
- Multi-resolution presentation — stakeholder-দের যেকোনো level দেখান।
Caveats:
- "Best $k$" — statistical artifact, business reality নয়।
- Different linkage → different dendrogram → different cuts।
- Reproducibility — random seed, data shuffle-এ stability।
মূল উপলব্ধি: Cut subjective নয়, multi-criteria। Statistical guidance + domain — দু'টি একসাথে decision। Hierarchical-এর true power — multi-resolution exploration।
প্র ০৪ Bangladesh-এ ৫০০ NGO-কে cluster করতে চান — donor strategy-র জন্য। Hierarchical clustering pipeline ডিজাইন করুন।
Real Bangladesh impact — NGO ecosystem analysis। BRAC, Grameen-সহ ৫০০ NGO-র donor allocation। Pipeline complete:
(১) Feature engineering:
- Mission area: education, health, microfinance, gender (one-hot)।
- Annual budget (log-transform — heavy tail)।
- Geographic spread (number of districts active)।
- Beneficiary count (log-transform)।
- Years of operation।
- Funding sources (foreign vs domestic ratio)।
- Impact metrics (if available — proxy: peer rating)।
(২) Preprocessing:
- StandardScaler — অপরিহার্য।
- Missing impute — sector median।
- One-hot for categorical (mission area)।
- ৫০০ × ৩০ feature → manageable।
(৩) Distance metric:
- Euclidean — Ward linkage-এর জন্য।
- Mixed type হলে Gower distance বিবেচনা।
- Jensen-Shannon divergence — যদি probability distribution থাকে।
(৪) Clustering:
- Ward linkage primary।
- Complete linkage সাথে compare।
- Dendrogram inspect — multi-resolution view।
(৫) Cut selection:
- Strategic level: ৩-৫ cluster (broad donor strategy)।
- Tactical level: ১০-১৫ cluster (specific NGO grouping)।
- Silhouette + domain expert review।
(৬) Cluster characterization:
- প্রতিটি cluster-এর mean feature → "persona"।
- Cluster name: "Large grassroots health" (BRAC-like), "Microfinance specialist" (Grameen-like), "Rural education focused"।
- Donor mapping — কোন cluster-এ কোন donor type fit।
(৭) Validation:
- Bootstrap — sample subset, cluster again, agreement।
- Hold-out new NGO — assigned cluster reasonable?
- Sector expert qualitative review।
(৮) Ethics:
- "Cluster" labeling stigmatize করতে পারে — careful naming।
- Small NGO disadvantage না হয় — equity check।
- Religious/political affiliation feature নয় — bias-prone।
(৯) Deployment:
- Static — yearly recluster (NGO-এর evolution slow)।
- Donor portal — cluster-based filter।
- Funding dashboard — cluster-wise allocation insight।
(১০) Iteration:
- Q1: feature added — re-cluster।
- Annual review — new mission area emerge?
- Donor feedback loop।
মূল উপলব্ধি: Real-world clustering pipeline = ১০% algorithm + ৯০% feature engineering + domain validation + ethics। Bangladesh NGO-র মত mission-driven sector-এ — ML-এর responsibility আরও বেশি।
অনুশীলন
-
হিসাব করুন: চারটি 1-D point — ${1, 2, 5, 10}$। Single linkage agglomerative, প্রথম দু'টি merge step ও height।
- Pairwise: |1-2|=1, |1-5|=4, |1-10|=9, |2-5|=3, |2-10|=8, |5-10|=5।
- সবচেয়ে কাছ — 1 ও 2, distance 1। Merge {1,2}, height=1।
- নতুন distance: {1,2}-5 = min(4,3)=3; {1,2}-10 = min(9,8)=8; 5-10=5।
- সবচেয়ে কাছ — {1,2} ও 5, distance 3। Merge {1,2,5}, height=3।
-
scipy-তে চেষ্টা: ৫টি point ও তাদের dendrogram তৈরি করুন।
import numpy as np from scipy.cluster.hierarchy import linkage, dendrogram X = np.array([[1.0], [2.0], [5.0], [10.0], [11.0]]) Z = linkage(X, method="single") print("Z:", Z.round(2)) # Z এর row: [idx_a, idx_b, height, count] # (Plot skip, but linkage matrix-ই তথ্য বহন করে) -
ভাবুন: Bangladesh-এর ৬৪টি জেলা-কে cluster করছেন agriculture similarity-তে (rice yield, soil type, rainfall, irrigation %)। কোন linkage বাছবেন? Cut কোথায়?
- Linkage: Ward — balanced cluster, agriculture data approximately gaussian-like।
- Scaling: obligatory — yield (ton/ha) vs rainfall (mm) ভিন্ন scale।
- Cut: ৪-৫ cluster — Bangladesh-এর agro-ecological zone (terai, char, haor, hilly, plain) প্রায় ৫টি — domain knowledge align।
- Validation: agricultural extension officer-এর সাথে review।
- Use: seed distribution, fertilizer subsidy targeted।
- Caveat: char এলাকা outlier-ই থাকতে পারে — separate cluster।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পাঠ ৩৩ · DBSCAN পরবর্তী পাঠ Density-based — non-spherical cluster ও noise auto-detect।
- পাঠ ৩১ · K-Means আগের পাঠ Hierarchical-এর সাথে compare করতে দেখুন।
- পাঠ ৩৪ · PCA এই পাঠের সাথে সম্পর্কিত High-D হলে hierarchical-এর আগে PCA।
- সব AI Courses ABCL TECH Python, ML, DL, NLP, CV, GenAI, RL, MLOps।