Bài 34: Hierarchical Clustering — phân cụm phân cấp

Hierarchical Clustering là họ thuật toán clustering sinh ra một cây phân cấp (hierarchy) các cluster thay vì một partition phẳng. Cây này được gọi là dendrogram — biểu đồ thể hiện thứ tự merge/split và khoảng cách tại mỗi bước.

Điểm khác cốt lõi so với K-Means (Bài 32): không cần chỉ định trước số cluster \( K \). Thuật toán chạy ra toàn bộ cây từ \( n \) cluster (mỗi điểm 1 cluster) tới 1 cluster duy nhất; người dùng "cut" cây ở độ cao tuỳ ý để lấy số cluster mong muốn — quyết định này được hoãn lại sau khi đã nhìn thấy cấu trúc dữ liệu.

Đầu ra cũng là nested clustering: cluster ở mức 3 luôn là union của các cluster ở mức 5; cấu trúc phân cấp này có ý nghĩa thực tế trong sinh học (cây phân loại loài), tổ chức văn bản, customer segmentation đa cấp.

Hai hướng tiếp cận xây cây:

• Agglomerative (bottom-up) — xuất phát từ \( n \) cluster (mỗi điểm là 1 cluster), tại mỗi bước merge 2 cluster gần nhau nhất theo một tiêu chí linkage. Sau \( n - 1 \) bước còn lại 1 cluster lớn. Phổ biến gần như tuyệt đối trong thực hành; sklearn chỉ cài đặt hướng này.
• Divisive (top-down) — xuất phát từ 1 cluster lớn chứa toàn bộ dữ liệu, tại mỗi bước chia một cluster làm hai. Cần một thuật toán phụ (vd K-Means với \( K=2 \), hoặc DIANA) để quyết định cách chia. Tốn tính toán hơn, ít implement; chỉ dùng khi cấu trúc top-level rõ ràng và quan tâm nhánh trên cùng.

Bài này tập trung agglomerative — phần còn lại nếu không nói gì thêm đều giả định bottom-up.

Cho dataset \( X = \{\mathbf{x}_1, \ldots, \mathbf{x}_n\} \) và hàm khoảng cách \( d \) giữa 2 điểm (thường Euclidean):

• Init: mỗi điểm là 1 cluster — có \( n \) cluster \( C_1, \ldots, C_n \).
• Tính ma trận khoảng cách giữa mọi cặp cluster (ban đầu là khoảng cách giữa các điểm) — shape \( n \times n \), đối xứng.
• Lặp đến khi còn 1 cluster (hoặc đạt số cluster mong muốn):
  • Tìm cặp \( (C_i, C_j) \) có \( D(C_i, C_j) \) nhỏ nhất theo linkage criterion.
  • Merge \( C_i, C_j \) thành cluster mới \( C_{ij} \). Ghi lại độ cao merge = \( D(C_i, C_j) \).
  • Cập nhật ma trận khoảng cách: thay 2 hàng/cột của \( C_i, C_j \) bằng 1 hàng/cột của \( C_{ij} \), tính lại distance từ \( C_{ij} \) tới các cluster còn lại theo công thức linkage.

Sau \( n - 1 \) lần merge ta có toàn bộ cây. Mỗi merge tương ứng một nút trong dendrogram; độ cao của nút chính là \( D(C_i, C_j) \) tại bước đó. Vì merge không bao giờ bị huỷ, cấu trúc nested được đảm bảo về mặt định nghĩa.

Linkage quyết định "khoảng cách giữa 2 cluster" được suy từ khoảng cách giữa các điểm như thế nào. Bốn cách phổ biến:

Single linkage (min, nearest neighbor):

\[ D(A, B) = \min_{a \in A,\, b \in B} d(a, b) \]

Khoảng cách 2 cluster = cặp điểm gần nhất. Có thể tạo cluster hình "chuỗi" dài, dễ bị chaining effect: hai cụm tách biệt nhưng có một đường nối các điểm trung gian sẽ bị merge. Hiệu năng kém với noise, nhưng phát hiện được cluster phi cầu, dạng dây.

Complete linkage (max, farthest neighbor):

\[ D(A, B) = \max_{a \in A,\, b \in B} d(a, b) \]

Khoảng cách 2 cluster = cặp điểm xa nhất. Cluster sinh ra compact, đường kính nhỏ, gần dạng cầu. Nhạy với outlier vì một outlier kéo \( \max \) lên rất nhanh.

Average linkage (UPGMA):

\[ D(A, B) = \frac{1}{|A| \cdot |B|} \sum_{a \in A} \sum_{b \in B} d(a, b) \]

Trung bình mọi cặp. Cân bằng giữa single và complete; ít nhạy outlier hơn complete, ít chaining hơn single. Phổ biến trong phylogenetics.

Ward linkage: minimize sự tăng tổng variance (within-cluster sum of squares) sau merge. Tại mỗi bước, chọn cặp cluster \( (A, B) \) sao cho:

\[ D(A, B) = \frac{|A| \cdot |B|}{|A| + |B|} \, \lVert \boldsymbol{\mu}_A - \boldsymbol{\mu}_B \rVert^2 \]

với \( \boldsymbol{\mu}_A, \boldsymbol{\mu}_B \) là centroid. Đây là Lance–Williams formula cho Ward. Cluster sinh ra cân bằng kích thước, gần với K-Means. Recommended default khi dùng Euclidean distance — và Ward yêu cầu Euclidean (không định nghĩa được với metric khác).

Dendrogram là cây nhị phân biểu diễn lịch sử merge:

• Trục X: các điểm dữ liệu (leaf của cây), sắp xếp sao cho các nhánh không cắt nhau.
• Trục Y: độ cao merge — bằng \( D(C_i, C_j) \) tại bước hợp nhất.
• Mỗi đường ngang trong dendrogram là một bước merge; chiều dài đứng của nhánh trước khi gặp đường ngang phản ánh khoảng cách giữa nhánh con và phần còn lại.

Đọc dendrogram:

• Đường ngang cao = 2 cluster con khác nhau xa (merge muộn, ở độ cao lớn) → ranh giới cluster rõ.
• Đường ngang thấp = 2 cluster con tương tự (merge sớm, ở độ cao nhỏ) → ranh giới mờ.
• "Long branch" — nhánh đứng dài không bị merge trong khoảng cao dài, là dấu hiệu của một cluster ổn định, rõ ràng.

Kẻ một đường ngang ngang qua dendrogram tại độ cao \( h \) — số lần đường này cắt nhánh đứng chính là số cluster nếu cut tại \( h \).

Vì cây chứa mọi phân cấp, chọn \( K \) tương đương chọn vị trí cut. Các cách thông dụng:

• Cut tại long branch — chọn \( h \) trong khoảng cao dài nhất mà không có merge nào diễn ra. Cut ở đó giữ được các cluster tách biệt rõ. Phương pháp trực quan, làm bằng mắt trên dendrogram.
• Inconsistency coefficient — scipy inconsistent: với mỗi merge, so sánh độ cao của nó với trung bình + lệch chuẩn các merge bên dưới. Inconsistency lớn ở các merge "đột ngột" → cut ngay dưới điểm đó.
• Kết hợp với metric Bài 33 — chạy nhiều \( K \) khác nhau bằng cách cut ở nhiều độ cao, đo silhouette score, chọn \( K \) tốt nhất.
• Domain knowledge — sinh học, marketing thường có giả thuyết về số nhóm (3 species, 5 segment khách hàng).

Ưu điểm so với K-Means: chỉ chạy fit một lần, sau đó "cut" ở bao nhiêu \( K \) cũng được, không cần fit lại. Phù hợp khi thử nghiệm nhiều granularity.

API tối thiểu:

from sklearn.cluster import AgglomerativeClustering

model = AgglomerativeClustering(n_clusters=3, linkage="ward")
labels = model.fit_predict(X)

fit_predict trả về vector label kích thước \( n \), giá trị \( 0, 1, \ldots, K-1 \). Không có predict cho điểm mới — hierarchical clustering không "học" được hàm gán cluster; muốn gán điểm mới phải kết hợp với một classifier riêng hoặc tìm centroid gần nhất.

Khác với K-Means, không có khái niệm centroid được lưu sẵn (Ward có centroid logic nhưng không expose), không có inertia_. Có thể truy cập:

• model.labels_ — label sau fit.
• model.n_clusters_ — số cluster cuối cùng.
• model.children_ — ma trận shape \( (n - 1, 2) \), mỗi hàng là 2 ID con của merge thứ \( i \). ID \( < n \) là điểm gốc; ID \( \geq n \) là cluster trung gian.
• model.distances_ — độ cao mỗi merge (chỉ tính khi compute_distances=True hoặc distance_threshold được set).

• n_clusters (mặc định 2) — số cluster mong muốn. Đặt None nếu dùng distance_threshold.
• linkage (mặc định "ward") — "ward", "complete", "average", "single". Ward chỉ với Euclidean.
• metric (mặc định "euclidean") — hàm khoảng cách giữa các điểm: "euclidean", "manhattan", "cosine", "precomputed"... Với "precomputed", truyền vào X chính là ma trận khoảng cách \( n \times n \) tự tính sẵn.
• distance_threshold (mặc định None) — nếu set, không cần n_clusters; thay vào đó cut dendrogram tại độ cao này, ra số cluster tuỳ data. Hữu ích khi muốn cố định ngưỡng "khác biệt" thay vì cố định số nhóm.
• compute_distances (mặc định False) — bật để lưu distances_ phục vụ vẽ dendrogram trực tiếp từ sklearn model. Tốn thêm một chút bộ nhớ.
• connectivity — ma trận sparse mô tả các cặp được phép merge (vd: dựa trên k-nearest-neighbors graph). Buộc clustering tôn trọng cấu trúc địa lý/đồ thị; dùng khi clustering ảnh, lưới không gian.

Tham số đơn giản hơn K-Means nhiều — chủ yếu chọn linkage và metric. Không có random init, không cần n_init: kết quả deterministic với cùng input và cùng cấu hình.

sklearn không cung cấp hàm vẽ dendrogram sẵn. Thông lệ: dùng scipy.cluster.hierarchy:

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram

# Z shape (n-1, 4): [child1, child2, distance, sample_count]
Z = linkage(X, method="ward")

plt.figure(figsize=(10, 5))
dendrogram(Z, truncate_mode="lastp", p=30, leaf_rotation=90)
plt.xlabel("Sample index hoac (cluster size)")
plt.ylabel("Distance")
plt.title("Hierarchical Clustering Dendrogram (Ward)")
plt.tight_layout()
plt.show()

linkage() với cùng method sẽ cho cây tương đương AgglomerativeClustering. truncate_mode="lastp" chỉ hiển thị \( p \) nhánh gần root cùng — cần thiết khi \( n \) lớn, dendrogram đầy đủ rối không đọc nổi.

Để cut cây và lấy label:

from scipy.cluster.hierarchy import fcluster

labels = fcluster(Z, t=3, criterion="maxclust")       # cat thanh dung 3 cluster
labels_h = fcluster(Z, t=5.0, criterion="distance")   # cat tai do cao 5.0

Ưu điểm:

• Không cần chỉ định trước \( K \). Có thể quan sát dendrogram rồi chọn.
• Cây phân cấp cho phép phân tích đa cấp granularity từ cùng 1 lần fit.
• Deterministic — không có random init, không cần chạy nhiều lần.
• Linh hoạt với nhiều metric (Euclidean, Manhattan, cosine, precomputed) — chạy được trên data phi số nếu tự định nghĩa khoảng cách.
• Cho insight cấu trúc dữ liệu vượt qua chỉ partition — biết cluster nào "gần" cluster nào.

Nhược điểm:

• Độ phức tạp cao: cài đặt tổng quát \( O(n^3) \) thời gian, \( O(n^2) \) bộ nhớ (lưu ma trận khoảng cách). Ward và một số linkage có thuật toán nhanh hơn nhưng vẫn \( O(n^2 \log n) \). Không scale với dataset lớn — thực tế dùng giới hạn quanh vài chục nghìn sample.
• Quyết định merge là vĩnh viễn — sai merge sớm thì sai mãi. Không có cơ chế revert/refine.
• Single linkage dễ bị chaining; complete linkage nhạy outlier; chọn linkage sai cho data layout sai sẽ ra cluster vô nghĩa.
• Không có predict cho điểm mới ngoài tập train.
• Diễn giải dendrogram khó khi \( n \) lớn (>200) — phải truncate, mất chi tiết.

• Hierarchical — chọn khi: dataset nhỏ (<10k), chưa biết \( K \), cần xem cấu trúc đa cấp, cần khoảng cách tuỳ biến (vd cosine cho text).
• K-Means (Bài 32) — chọn khi: dataset lớn (hàng triệu), đã biết hoặc xác định được \( K \) bằng Elbow/Silhouette, cluster có dạng cầu và kích thước tương đương. Train rất nhanh, có predict cho data mới.
• DBSCAN (Bài 35) — chọn khi: cluster hình thù bất kỳ (vành khuyên, dạng dây), có nhiều noise/outlier cần đánh dấu, không biết \( K \), mật độ giữa các cluster đồng đều.

Quy tắc kinh nghiệm:

• \( n \leq 10\,000 \), cần insight cấu trúc → Hierarchical (Ward) trước.
• \( n \) lớn, cluster cầu → K-Means.
• Cần phát hiện outlier, cluster phi cầu → DBSCAN.
• Hierarchical Ward + Euclidean trên dữ liệu cầu thường ra kết quả gần K-Means; nếu khớp nhau là tín hiệu cấu trúc cluster ổn định.

• Phylogenetics / taxonomy — dựng cây phân loại loài, gen, protein dựa trên ma trận sequence similarity. UPGMA (average linkage) là phương pháp kinh điển trong sinh học tính toán.
• Customer segmentation phân cấp — chia khách hàng thành 4 segment lớn, mỗi segment lại có 2–3 sub-segment. Cây phân cấp giúp marketing chọn granularity tuỳ chiến dịch.
• Document/topic organization — clustering bài báo, văn bản theo similarity (TF-IDF + cosine) để dựng cây chủ đề.
• Image segmentation — phân vùng pixel theo màu/texture với connectivity constraint từ pixel grid.
• Gene expression analysis — heatmap với row/column dendrogram là chuẩn trong bài báo bioinformatics.
• Network/social graph community — clustering node bằng khoảng cách precomputed trên đồ thị.

Mọi linkage dựa trên khoảng cách Euclidean (Ward bắt buộc, single/complete/average mặc định) đều nhạy với scale. Feature có range lớn (income hàng nghìn đô) sẽ át feature range nhỏ (số con cái 0–5). Tương tự như K-Means (Bài 32), chuẩn hoá feature trước khi clustering là khuyến nghị mặc định.

from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering

X_scaled = StandardScaler().fit_transform(X)
labels = AgglomerativeClustering(n_clusters=3, linkage="ward").fit_predict(X_scaled)

Trường hợp dùng cosine distance (text embedding) thì normalize theo norm (\( \lVert \mathbf{x} \rVert = 1 \)) thay vì standardize — cosine không bị ảnh hưởng bởi scale tuyệt đối nhưng vẫn cần normalize để khoảng cách có ý nghĩa hình học.

Cây phân cấp có thể "tốt" hay "tệ" so với cấu trúc thực của dữ liệu. Cophenetic distance giữa 2 điểm \( a, b \) trong dendrogram = độ cao tại nút tổ tiên chung nhỏ nhất của \( a \) và \( b \). Tức là: khoảng cách mà cây khẳng định giữa 2 điểm đó.

Cophenetic Correlation Coefficient (CPCC):

\[ \rho_c = \frac{\sum_{i < j} (d_{ij} - \bar{d})(c_{ij} - \bar{c})}{\sqrt{\sum_{i < j} (d_{ij} - \bar{d})^2 \cdot \sum_{i < j} (c_{ij} - \bar{c})^2}} \]

với \( d_{ij} \) là khoảng cách gốc giữa \( \mathbf{x}_i, \mathbf{x}_j \), và \( c_{ij} \) là cophenetic distance trong dendrogram. Đây là tương quan Pearson giữa hai vector khoảng cách flatten.

• \( \rho_c \) gần 1: cây fit tốt cấu trúc khoảng cách gốc.
• \( \rho_c \) thấp (vd < 0.7): dendrogram bóp méo khoảng cách nhiều — linkage hoặc metric chưa hợp với data.

Dùng CPCC để so sánh các linkage method trên cùng dataset: chọn cái có \( \rho_c \) cao nhất.

from scipy.cluster.hierarchy import linkage, cophenet
from scipy.spatial.distance import pdist

D = pdist(X)               # vector khoang cach goc
Z = linkage(X, method="average")
c, coph_dists = cophenet(Z, D)
print(f"Cophenetic correlation: {c:.4f}")

Generate dữ liệu, fit Ward, vẽ dendrogram, so sánh với K-Means.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering, KMeans
from sklearn.metrics import adjusted_rand_score, silhouette_score
from scipy.cluster.hierarchy import linkage, dendrogram, cophenet
from scipy.spatial.distance import pdist

X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)
X = StandardScaler().fit_transform(X)

# 1. Agglomerative Ward
agg = AgglomerativeClustering(n_clusters=4, linkage="ward")
y_agg = agg.fit_predict(X)

# 2. K-Means de so sanh
km = KMeans(n_clusters=4, n_init=10, random_state=42)
y_km = km.fit_predict(X)

print(f"Agglomerative Ward")
print(f"  ARI vs ground truth : {adjusted_rand_score(y_true, y_agg):.4f}")
print(f"  Silhouette          : {silhouette_score(X, y_agg):.4f}")

print(f"K-Means")
print(f"  ARI vs ground truth : {adjusted_rand_score(y_true, y_km):.4f}")
print(f"  Silhouette          : {silhouette_score(X, y_km):.4f}")

print(f"Ward vs K-Means ARI   : {adjusted_rand_score(y_agg, y_km):.4f}")

Vẽ dendrogram và tính cophenetic correlation:

Z = linkage(X, method="ward")
D = pdist(X)
c, _ = cophenet(Z, D)
print(f"Cophenetic correlation (ward): {c:.4f}")

plt.figure(figsize=(12, 5))
dendrogram(Z, truncate_mode="lastp", p=30, leaf_rotation=90)
plt.axhline(y=15, color="red", linestyle="--", label="cut -> 4 cluster")
plt.xlabel("Sample (cluster size)")
plt.ylabel("Ward distance")
plt.legend()
plt.tight_layout()
plt.show()

So sánh 4 linkage:

for method in ["single", "complete", "average", "ward"]:
    Zm = linkage(X, method=method)
    cm, _ = cophenet(Zm, D)
    labels = AgglomerativeClustering(n_clusters=4, linkage=method).fit_predict(X)
    sil = silhouette_score(X, labels)
    ari = adjusted_rand_score(y_true, labels)
    print(f"{method:10s} cophenetic={cm:.4f}  silhouette={sil:.4f}  ARI={ari:.4f}")

Trên blob đều, Ward thường cho ARI cao nhất (gần 1.0) và kết quả gần như trùng với K-Means; single linkage có thể tụt do chaining nếu 2 cluster gần nhau.

Bài 1 — Hierarchical trên iris. Load load_iris(), standardize. Fit AgglomerativeClustering(n_clusters=3, linkage="ward"). So sánh label dự đoán với y_true bằng adjusted_rand_score. Vẽ scatter 2 feature (petal length, petal width) với màu theo cluster dự đoán và theo ground truth — có khớp không?

Bài 2 — So sánh 4 linkage. Trên iris đã standardize, fit lần lượt với linkage ∈ {single, complete, average, ward}, n_clusters=3. Tính (a) cophenetic correlation, (b) silhouette score, (c) ARI so với ground truth. Lập bảng và nhận xét: linkage nào tốt nhất cho iris và vì sao?

Bài 3 — Cut dendrogram ở threshold khác nhau. Trên iris, dùng scipy.cluster.hierarchy.linkage(X, method="ward") để có Z. Lặp với t ∈ {2, 4, 6, 8, 10, 15}, dùng fcluster(Z, t=t, criterion="distance") đếm số cluster ra. Cut ở threshold nào cho ra 3 cluster (khớp ground truth)?

Bài 4 — Chaining effect. Tạo dữ liệu artificial gồm 2 blob cách xa, nối bằng một "dây" 30 điểm trải đều (np.linspace giữa 2 tâm). Fit hierarchical với single linkage và với ward linkage, n_clusters=2. Vẽ scatter với màu theo cluster. Single có gộp "dây" vào với 1 trong 2 blob không? Ward thì sao?

Bài 5 — distance_threshold thay cho n_clusters. Trên make_blobs(n_samples=500, centers=5, random_state=42) standardize, fit AgglomerativeClustering(n_clusters=None, distance_threshold=t, linkage="ward") với t ∈ {3, 5, 8, 15}. Đếm model.n_clusters_ mỗi lần. Vẽ scatter cho từng \( t \). Quan sát: tăng threshold thì số cluster giảm như thế nào?

Bài 35: DBSCAN — density-based clustering: định nghĩa cluster theo mật độ điểm thay vì khoảng cách centroid. Tự động xác định số cluster, đánh dấu điểm noise/outlier, xử lý được cluster hình bất kỳ (vành khuyên, dây) mà K-Means và hierarchical Ward không làm nổi.