Bài 33: Đánh giá clustering — Elbow Method và Silhouette Score

Trong supervised learning, có label \( y \) thật → so prediction với label, ra accuracy, F1, ROC-AUC. Trong clustering thì không có label — đó là điểm khác biệt cơ bản của unsupervised learning. Không có "đáp án đúng" để so sánh.

Hệ quả là hai câu hỏi cốt lõi của clustering không có lời giải trực tiếp:

• Chọn K bao nhiêu? — K-Means yêu cầu chỉ định trước số cluster. Lấy K = 3 hay K = 7 thì hợp lý?
• Kết quả clustering có "tốt" không? — Cluster có tách biệt rõ ràng hay chỉ là phân hoạch tuỳ tiện?

Phải dùng nhóm metric đặc thù cho clustering, dựa vào hình học của cluster chứ không phải so với label. Ý tưởng chung: cluster tốt nếu các điểm trong cùng cluster gần nhau (cohesion) và các cluster khác nhau cách xa nhau (separation).

Không metric nào là chuẩn vàng — mỗi metric có giả định riêng, dễ bị đánh lừa. Thực tế gần như luôn cần combine nhiều metric + domain knowledge.

Metric đánh giá clustering chia thành hai họ.

• Internal metric — chỉ dùng data \( X \) và cluster assignment, không cần label. Đo bằng hình học: cohesion + separation. Họ này phổ biến vì hầu hết bài toán clustering thực tế không có ground truth.
  • Silhouette Score — phổ biến nhất.
  • Davies-Bouldin Index.
  • Calinski-Harabasz Index.
• External metric — cần biết label ground truth để so. Đo độ trùng khớp giữa cluster assignment và label thật. Họ này dùng khi:
  • Có dataset đã gán nhãn để benchmark thuật toán (vd Iris, MNIST).
  • Có một phần data được gán nhãn manual để validate clustering trên toàn dataset.
  • So sánh hai phân hoạch clustering với nhau (coi một phân hoạch là "label").
  • Adjusted Rand Index (ARI).
  • Normalized Mutual Information (NMI).

Trong production thực tế, internal metric là loại dùng chính. External chỉ dùng được khi có label — và nếu đã có label thì thường đã chuyển sang bài toán supervised.

Phương pháp kinh điển để chọn K cho K-Means. Dựa vào đại lượng WCSS (Within-Cluster Sum of Squares) — cũng chính là inertia mà K-Means tối ưu (bài 32):

Trong đó \( C_k \) là cluster thứ \( k \) và \( \boldsymbol{\mu}_k \) là centroid của cluster đó. WCSS đo tổng bình phương khoảng cách từ mỗi điểm đến centroid cluster của nó — càng nhỏ nghĩa là điểm trong cluster càng chụm.

Quy trình Elbow:

1. Train K-Means với \( K = 1, 2, 3, \ldots, K_{\max} \) (thường \( K_{\max} = 10\text{–}15 \)).
2. Với mỗi \( K \), lưu WCSS (đọc qua model.inertia_ trong sklearn).
3. Plot WCSS theo \( K \).
4. Tìm elbow point — điểm khuỷu tay, nơi đường cong giảm chậm hẳn lại.

Bản chất: tăng K luôn làm WCSS giảm (K = n thì WCSS = 0 — mỗi điểm là một cluster). Nhưng từ một K nào đó, thêm cluster chỉ giảm WCSS một lượng nhỏ vì các cluster chính đã được tách. Elbow là chỗ trade-off đẹp giữa "đủ cluster" và "không over-split".

Elbow là heuristic, không phải metric chính xác. Vấn đề thường gặp:

• Elbow không rõ ràng — nhiều dataset thực tế cho đường cong gần tuyến tính, không có khuỷu rõ. Khi đó "chọn K bằng mắt" thành đoán mò.
• Subjective — hai người nhìn cùng một biểu đồ có thể chọn K khác nhau (ví dụ K = 3 vs K = 4).
• Phụ thuộc scale — feature chưa scale có thể làm WCSS bị chi phối bởi một vài feature lớn, cong đường cong bị méo.
• Chỉ áp dụng được cho thuật toán tối ưu inertia — K-Means có sẵn inertia_. DBSCAN không có khái niệm này.

Hai cách bổ trợ thường dùng:

• Kết hợp với Silhouette — plot cả WCSS và Silhouette theo K, chọn K cho cả hai metric đều "ổn".
• Kneedle algorithm (Satopää et al. 2011) — tự động detect knee/elbow từ một đường cong. Package kneed trong Python triển khai sẵn.

Coi Elbow là filter sơ bộ để loại các K rõ ràng quá nhỏ hoặc quá lớn, đừng coi là quyết định cuối.

Silhouette (Rousseeuw, 1987) là metric internal được dùng nhiều nhất. Với mỗi điểm \( i \), định nghĩa:

• \( a(i) \) — khoảng cách trung bình từ \( i \) đến mọi điểm khác trong cùng cluster. Đo cohesion.
• \( b(i) \) — khoảng cách trung bình từ \( i \) đến mọi điểm trong cluster gần nhất khác (nearest neighbour cluster). Đo separation.

Silhouette của điểm \( i \):

Giá trị \( s(i) \in [-1, 1] \). Cách đọc:

• \( s(i) \approx 1 \) — \( a(i) \ll b(i) \): điểm rất gần các điểm cùng cluster, xa cluster khác. Well-clustered.
• \( s(i) \approx 0 \) — \( a(i) \approx b(i) \): điểm nằm trên ranh giới giữa hai cluster, có thể thuộc về bên nào cũng được.
• \( s(i) < 0 \) — \( a(i) > b(i) \): điểm gần một cluster khác hơn là cluster đang được gán. Khả năng bị assign sai.

Overall Silhouette Score là trung bình \( s(i) \) trên toàn bộ điểm:

Khi so sánh nhiều giá trị K, chọn K cho \( S \) cao nhất (gần 1 nhất).

Lưu ý độ phức tạp: tính \( a(i), b(i) \) cần khoảng cách điểm-điểm, độ phức tạp \( O(n^2) \). Với dataset > 100k điểm, dùng sampling (silhouette_score(..., sample_size=10000) trong sklearn).

Sklearn cung cấp hai hàm:

from sklearn.metrics import silhouette_score, silhouette_samples

# Overall: tra ve 1 so duy nhat = trung binh
score = silhouette_score(X, labels)

# Per-sample: tra ve mang shape (n,) — silhouette cua tung diem
samples = silhouette_samples(X, labels)

Một số điểm cần lưu ý:

• labels là array shape \( (n,) \) chứa nhãn cluster của từng điểm (output của kmeans.predict hoặc kmeans.labels_).
• Cần ít nhất 2 cluster — \( K = 1 \) không tính được silhouette (\( b(i) \) không định nghĩa).
• Mặc định metric khoảng cách là Euclidean. Có thể đổi bằng tham số metric= (vd "cosine", "manhattan").
• Với dataset lớn, dùng sample_size để estimate score từ một subset random.

Quan trọng: silhouette không dùng centroid, nên hoạt động được với mọi thuật toán clustering (K-Means, hierarchical, DBSCAN), không bị giới hạn trong K-Means như WCSS.

Chỉ nhìn overall silhouette dễ bỏ sót thông tin per-cluster. Silhouette plot chia silhouette per-sample theo cluster, sort giảm dần trong từng cluster, vẽ thành bar ngang.

Cách đọc:

• Cluster tốt — bar dày (nhiều điểm), cao đều (silhouette gần 1), không có điểm âm.
• Cluster xấu — bar thấp, mỏng, hoặc có nhiều điểm silhouette < 0.
• Cluster có size lệch nhau lớn — vd 4 cluster với size 500, 480, 470 và 20 — có thể là dấu hiệu cluster nhỏ là noise hoặc K hơi lớn.
• Một số cluster có nhiều điểm dưới đường overall — overall score đang được "kéo lên" nhờ vài cluster tốt, K này không thực sự ổn.

Khi so K = 3, 4, 5, ngoài việc nhìn overall silhouette, nhìn plot per-cluster cho từng K để chọn K cho hình dạng "đều" nhất — overall cao mà mỗi cluster cũng tự cao, không có cluster nào tệ.

Sklearn có ví dụ chính thức plot_kmeans_silhouette_analysis — copy code làm template.

Davies-Bouldin (Davies & Bouldin, 1979) — viết tắt DB. Với mỗi cluster, tính tỷ lệ giữa scatter trong cluster và khoảng cách đến cluster gần nhất khác:

Trong đó \( \sigma_k \) là khoảng cách trung bình từ điểm trong cluster \( k \) đến centroid \( \boldsymbol{\mu}_k \), và \( d(\cdot,\cdot) \) là khoảng cách giữa hai centroid.

Ý nghĩa:

• DB thấp = tốt hơn — cluster chụm và cách xa nhau.
• Giá trị tối thiểu lý tưởng là 0, không có giới hạn trên.
• Không bị giới hạn trong [-1, 1] như Silhouette → khó so cross-dataset, chỉ dùng để so các K khác nhau trên cùng dataset.

from sklearn.metrics import davies_bouldin_score
db = davies_bouldin_score(X, labels)

Đặc điểm: tính nhanh hơn Silhouette nhiều (\( O(nK) \) thay vì \( O(n^2) \)), phù hợp dataset lớn. Bias nhẹ về phía cluster cầu (giống K-Means) — không hoàn toàn fair với cluster phi tuyến.

Calinski-Harabasz (Caliński & Harabasz, 1974) — còn gọi là Variance Ratio Criterion. Tỉ lệ giữa between-cluster dispersion và within-cluster dispersion:

Trong đó:

• \( B_K = \sum_k n_k (\boldsymbol{\mu}_k - \boldsymbol{\mu})(\boldsymbol{\mu}_k - \boldsymbol{\mu})^\top \) — between-cluster scatter (cluster nằm cách xa centroid chung bao nhiêu).
• \( W_K = \sum_k \sum_{\mathbf{x} \in C_k} (\mathbf{x} - \boldsymbol{\mu}_k)(\mathbf{x} - \boldsymbol{\mu}_k)^\top \) — within-cluster scatter (= WCSS dạng ma trận).
• Hệ số \( \tfrac{n - K}{K - 1} \) penalize K lớn.

Ý nghĩa:

• CH cao = tốt hơn — cluster cách xa nhau (B lớn) và mỗi cluster chụm (W nhỏ).
• Không có giới hạn — chỉ so trên cùng dataset, không so cross-dataset.
• Tính rất nhanh — \( O(nK) \), nhanh hơn cả Davies-Bouldin trên dataset lớn.

from sklearn.metrics import calinski_harabasz_score
ch = calinski_harabasz_score(X, labels)

Bias: ưa cluster cầu, cluster có size đều. Giống Silhouette và DB, không phù hợp lắm cho cluster phi tuyến hoặc density-based.

Khi có ground truth label, hai metric chính là ARI và NMI.

Adjusted Rand Index (ARI) — Hubert & Arabie (1985). Đo agreement giữa hai phân hoạch (predicted vs true) qua việc đếm cặp điểm:

• Cặp điểm cùng cluster ở cả hai phân hoạch.
• Cặp điểm khác cluster ở cả hai phân hoạch.

Chuẩn hoá để chance level = 0, perfect = 1.

• Range: thực tế \( (-1, 1] \). 0 = ngẫu nhiên. 1 = trùng khớp hoàn toàn (đến permutation label).
• Invariant với việc đánh số cluster — cluster 0/1/2 hay 2/0/1 không quan trọng, chỉ cần phân hoạch giống nhau.

from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score(y_true, labels)

Normalized Mutual Information (NMI) — chuẩn hoá mutual information về [0, 1]:

Trong đó \( I \) là mutual information và \( H \) là entropy.

• Range: \( [0, 1] \). 0 = không có thông tin chung. 1 = trùng khớp hoàn toàn.
• Có biến thể AMI (Adjusted MI) điều chỉnh cho chance, fair hơn khi K khác nhau.

from sklearn.metrics import normalized_mutual_info_score, adjusted_mutual_info_score
nmi = normalized_mutual_info_score(y_true, labels)
ami = adjusted_mutual_info_score(y_true, labels)

Khuyến nghị thực tế: dùng ARI hoặc AMI thay vì NMI thuần — NMI có bias khoái K lớn (split nhiều cluster tự nhiên ra NMI cao hơn).

Không có công thức cố định, nhưng một quy trình hợp lý:

1. Scale data trước (StandardScaler hoặc MinMaxScaler) — clustering dựa trên khoảng cách, scale ảnh hưởng trực tiếp.
2. Giới hạn K range: thường \( K \in [2, 20] \) đủ cho hầu hết business case. K > 20 hiếm khi có ý nghĩa interpret được.
3. Plot WCSS theo K — xác định vùng elbow sơ bộ.
4. Plot Silhouette theo K — tìm K có overall silhouette cao.
5. Tính thêm Davies-Bouldin và Calinski-Harabasz theo K — cross-check.
6. Inspect các K candidate: với mỗi K hợp lý (vd K = 3, 4, 5), nhìn silhouette plot per-cluster. Loại K nào có cluster tệ rõ rệt.
7. Kiểm tra interpretability: profile từng cluster (mean/median của feature gốc theo cluster). Cluster có ý nghĩa business không? Có cluster nào quá nhỏ (< 1% data) — nhiều khả năng là noise, không nên giữ.
8. Combine với domain knowledge: business stakeholder thường có kỳ vọng số segment trước (vd marketing muốn 3–5 segment để truyền thông). Metric chỉ chọn trong khoảng đó.

Khi các metric không đồng thuận (Elbow nói K = 4, Silhouette nói K = 6), không có "đúng tuyệt đối". Chọn K mà majority metric đồng ý + có ý nghĩa business. Ghi rõ trade-off vào tài liệu.

• Cluster cực kỳ imbalanced — một cluster chiếm 90% data, các cluster còn lại rất nhỏ. Silhouette overall vẫn có thể cao (vì cluster lớn dễ chụm), nhưng kết quả thực tế vô dụng. Luôn xem size distribution của cluster.
• Cluster phi tuyến — dataset hình moon, ring. K-Means + Silhouette gần như không phù hợp: K-Means giả định cluster cầu, Silhouette dựa Euclidean. Cần thuật toán density-based (DBSCAN, bài 35) hoặc spectral clustering, và metric tương ứng.
• Optimize 1 metric mà bỏ qua interpretation — silhouette = 0.8 nghe rất tốt, nhưng nếu cluster không map sang ý nghĩa business nào thì vô ích. Metric chỉ là điều kiện cần.
• Quên scale — chạy K-Means + Silhouette trên data có feature scale lệch nhau hàng nghìn lần → kết quả bị chi phối bởi feature lớn nhất.
• Curse of dimensionality — ở high-dimension (> 50 feature), mọi cặp điểm xấp xỉ cùng khoảng cách → silhouette mất discrimination. Cân nhắc PCA hoặc UMAP để giảm chiều trước (bài 36–37).
• Chỉ chạy 1 random_state — K-Means nhạy initialization. Chạy nhiều seed (hoặc n_init=10 trong sklearn) và lấy trung bình metric, không lấy 1 lần ăn may.

Generate dataset với 4 cluster, sweep K từ 2 đến 10, đo nhiều metric.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import (
    silhouette_score,
    davies_bouldin_score,
    calinski_harabasz_score,
    adjusted_rand_score,
)

X, y_true = make_blobs(
    n_samples=1000, centers=4, cluster_std=1.0, random_state=42
)

ks = list(range(2, 11))
wcss, sil, db, ch, ari = [], [], [], [], []

for k in ks:
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X)

    wcss.append(km.inertia_)
    sil.append(silhouette_score(X, labels))
    db.append(davies_bouldin_score(X, labels))
    ch.append(calinski_harabasz_score(X, labels))
    ari.append(adjusted_rand_score(y_true, labels))

# Cung K = 1 cho WCSS de ve elbow day du
km1 = KMeans(n_clusters=1, n_init=10, random_state=42).fit(X)
wcss_full = [km1.inertia_] + wcss
ks_full = [1] + ks

Plot 4 panel:

fig, axes = plt.subplots(2, 2, figsize=(12, 8))

axes[0, 0].plot(ks_full, wcss_full, "o-")
axes[0, 0].set(title="Elbow (WCSS)", xlabel="K", ylabel="WCSS")

axes[0, 1].plot(ks, sil, "o-")
axes[0, 1].set(title="Silhouette (cao = tot)", xlabel="K", ylabel="score")

axes[1, 0].plot(ks, db, "o-")
axes[1, 0].set(title="Davies-Bouldin (thap = tot)", xlabel="K", ylabel="DB")

axes[1, 1].plot(ks, ch, "o-")
axes[1, 1].set(title="Calinski-Harabasz (cao = tot)", xlabel="K", ylabel="CH")

plt.tight_layout()
plt.show()

So với label ground truth:

best_k_ari = ks[int(np.argmax(ari))]
best_k_sil = ks[int(np.argmax(sil))]
print(f"K toi uu theo ARI (co label): {best_k_ari}")
print(f"K toi uu theo Silhouette:     {best_k_sil}")

Quan sát điển hình trên make_blobs 4 cluster:

• WCSS có elbow rõ tại K = 4.
• Silhouette đạt max tại K = 4 (thường ~0.7–0.8).
• DB đạt min tại K = 4. CH đạt max tại K = 4.
• ARI cũng cao nhất tại K = 4 — confirm internal metric chọn đúng số cluster thật.

Trên data thực tế, 4 metric không bao giờ đồng thuận đẹp như vậy. Đó là lý do phải nhìn cả 4 + silhouette plot + domain knowledge.

Bài 1 — Tìm K cho make_blobs với 3 cluster. Generate make_blobs(n_samples=600, centers=3, cluster_std=1.2, random_state=0). Sweep K từ 2 đến 10. Plot WCSS, Silhouette, DB, CH. Cả 4 metric chọn K bằng nhau không? K nào hợp lý nhất? So với ground truth bằng ARI.

Bài 2 — Customer segmentation giả định. Generate dataset 800 sample, 5 feature số (giả định annual_income, spending_score, age, recency, frequency) bằng make_blobs với 4 centers. StandardScale, chạy K-Means với K = 3 và K = 5. So Silhouette overall, DB, và silhouette plot per-cluster. Cấu hình nào tốt hơn? Giả sử marketing muốn 4 segment — kết luận về tradeoff giữa metric và yêu cầu business.

Bài 3 — Implement Silhouette bằng tay. Dataset nhỏ 6 điểm 2D: [(1,1), (1,2), (2,1), (8,8), (8,9), (9,8)], label = [0, 0, 0, 1, 1, 1]. Tính tay \( a(i), b(i), s(i) \) cho điểm đầu tiên (1,1). So với silhouette_samples của sklearn — phải khớp.

Bài 4 — Silhouette plot. Trên Iris (loại bỏ label), chạy K-Means với K = 2, 3, 4. Vẽ silhouette plot per-cluster cho từng K (dùng template từ docs sklearn). K nào có cluster cân đối nhất? So với fact "Iris có 3 species" — Silhouette có chọn được K = 3 không, hay bị fool bởi 2 species gần nhau (versicolor, virginica)?

Bài 5 — Elbow không rõ ràng. Generate dataset bằng make_blobs với cluster_std=3.5 (cluster overlap nhiều). Plot WCSS theo K — đường cong có elbow rõ không? Silhouette có còn chọn được K đúng? Kết luận về tình huống cluster overlap.

Bài 34: Hierarchical Clustering — họ clustering khác hẳn K-Means: xây cây dendrogram thể hiện cấu trúc nested, không cần chỉ định K trước, cắt cây ở mức nào để có số cluster mong muốn. Linkage (single, complete, average, Ward), agglomerative vs divisive, và khi nào dùng thay K-Means.