Bỏ qua đến nội dung chính
Mục lục

Hierarchical clustering: dendrogram, AgglomerativeClustering

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 3/7 · Chương 8

Học không giám sát

  • 9 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Hierarchical clustering (phân cụm phân cấp) bắt đầu với mỗi điểm là một cụm, rồi mỗi bước nhập hai cụm sát nhau nhất làm một, tới lúc cả bảng chung một cụm. Thứ tự và độ cao các lần nhập vẽ thành một cây gọi là dendrogram, và cắt cây ở một độ cao cho ra số cụm bạn cần mà không phải chạy lại thuật toán.

Cần biết trước: K-means, chọn số cụm K và lấy mẫu dòng bằng sample.

Gộp dần từng cặp: tính tay single linkage

Câu hỏi đầu tiên là khoảng cách giữa hai cụm đo thế nào. Cách đơn giản nhất, single linkage, lấy khoảng cách giữa hai điểm gần nhau nhất của hai cụm:

d(A,B)=min ∣a−b∣d(A, B) = \text{min} \, \lvert a - b \rvert

Trong đó:

  • A, B: hai cụm đang xét.

  • a, b: một điểm bất kỳ của A và một điểm bất kỳ của B; lấy giá trị nhỏ nhất trên mọi cặp.

  • d(A, B): khoảng cách single linkage giữa hai cụm, cũng là độ cao của lần gộp trên dendrogram.

Năm khách có số đơn 12 tháng là 1, 2, 4, 8, 9. Gộp tay:

Lần gộp

Hai cụm được gộp

Khoảng cách

Cỡ cụm mới

1

{1} và {2}

1

2

2

{8} và {9}

1

2

3

{1, 2} và {4}

2

3

4

{1, 2, 4} và {8, 9}

4

5

Ở lần 3, khoảng cách từ 4 tới cụm {1, 2} là 2 (tới điểm 2), nhỏ hơn 4 (tới cụm {8, 9}). linkage của SciPy trả đúng bảng này, mỗi dòng một lần gộp:

python
import numpy as np
from scipy.cluster.hierarchy import linkage

x = np.array([[1], [2], [4], [8], [9]])
print(linkage(x, method="single"))

KẾT QUẢ

[[0. 1. 1. 2.]
 [3. 4. 1. 2.]
 [2. 5. 2. 3.]
 [6. 7. 4. 5.]]

Hai cột đầu là số thứ tự hai cụm được gộp: 0 tới 4 là năm điểm gốc, 5 là cụm tạo ở lần gộp đầu, 6 ở lần thứ hai. Cột ba là khoảng cách, cột bốn là cỡ cụm mới. Đổi "single" thành "complete" rồi chạy lại: complete linkage lấy cặp xa nhất, nên lần gộp cuối in 8..

Dendrogram: cây các lần gộp

Trên bảng chi_tieu_khach_hang.csv (số giả lập của AIDev, khách của chuỗi Sóc Nhanh), khối dưới lấy 12 khách bằng sample, log và scale như bài K-means, rồi vẽ dendrogram với cách gộp ward. Mỗi bước, ward chọn cặp cụm mà khi nhập lại thì tổng bình phương khoảng cách tới tâm tăng ít nhất, cùng thước đo với inertia của K-means:

python
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.preprocessing import StandardScaler

kh = pd.read_csv("chi_tieu_khach_hang.csv")
kh = kh.sample(12, random_state=5)
X = kh.drop(columns="ma_kh")
X[X.columns[:4]] = np.log1p(X[X.columns[:4]])
cay = linkage(StandardScaler().fit_transform(X), method="ward")
fig, ax = plt.subplots(figsize=(7, 4), layout="constrained")
dendrogram(cay, labels=list(kh["ma_kh"]), leaf_rotation=90, ax=ax)
ax.set(title="Dendrogram 12 khách (ward)", ylabel="khoảng cách gộp")
plt.show()
Dendrogram của 12 khách: nhóm năm khách bên trái gộp xong dưới độ cao 2,3; bảy khách bên phải gộp thành hai nhánh rồi nối ở độ cao khoảng 5; hai nhóm lớn nối nhau ở độ cao gần 10.

Mỗi chữ U nối hai nhánh ở độ cao bằng khoảng cách của lần gộp đó. Kẻ một đường ngang ở độ cao nào thì số nhánh đường ấy cắt qua là số cụm. Chỗ hai lần gộp liên tiếp cách nhau xa trên trục dọc là chỗ cắt dễ bảo vệ, vì nhích ngưỡng lên xuống một chút vẫn ra cùng số cụm. Ở hình này, khoảng trống lớn nhất nằm giữa độ cao khoảng 5 và gần 10, nên cắt ở đó cho 2 cụm; cắt quanh độ cao 3 cho 3 cụm.

AgglomerativeClustering: cắt cây trên cả bảng

AgglomerativeClustering của scikit-learn làm cùng việc và trả nhãn cho từng dòng. Tham số linkage= chọn cách đo khoảng cách giữa hai cụm: "ward" (mặc định), "complete" (cặp xa nhất), "average" (trung bình mọi cặp), "single" (cặp gần nhất). Khối dưới cắt cả 1.500 khách thành 4 cụm bằng từng cách, rồi so với K-means 4 cụm bằng adjusted_rand_score():

python
import numpy as np
import pandas as pd
from sklearn.cluster import AgglomerativeClustering, KMeans
from sklearn.metrics import adjusted_rand_score
from sklearn.preprocessing import StandardScaler

kh = pd.read_csv("chi_tieu_khach_hang.csv").drop(columns="ma_kh")
kh[kh.columns[:4]] = np.log1p(kh[kh.columns[:4]])
Z = StandardScaler().fit_transform(kh)
km = KMeans(n_clusters=4, n_init=10, random_state=0).fit_predict(Z)
for cach in ["ward", "complete", "average", "single"]:
    nhan = AgglomerativeClustering(n_clusters=4,
                                   linkage=cach).fit_predict(Z)
    ari = adjusted_rand_score(km, nhan)
    print(cach, np.bincount(nhan), round(ari, 3))

KẾT QUẢ

ward [286 393 399 422] 0.853
complete [812 399 264  25] 0.658
average [397 814 264  25] 0.654
single [  25 1473    1    1] 0.007

ARI (adjusted Rand index) đếm các cặp khách mà hai cách chia cùng xếp chung hoặc cùng xếp riêng, rồi trừ phần trùng do may rủi: 1 là khớp hoàn toàn, quanh 0 là không hơn ngẫu nhiên. Ward cho bốn cụm cỡ gần nhau và khớp K-means nhiều nhất. Single linkage nối dần qua các khách nằm giữa hai nhóm như mắt xích, nên gần hết khách rơi vào một cụm và hai cụm chỉ có một khách.

Cắt theo độ cao thay vì theo số cụm

Thay cho n_clusters, có thể đặt n_clusters=None và distance_threshold=: mọi lần gộp có khoảng cách từ ngưỡng trở lên bị bỏ, và thuộc tính n_clusters_ cho biết còn lại bao nhiêu cụm. Cách này giống kẻ đường ngang trên dendrogram:

python
import numpy as np
from sklearn.cluster import AgglomerativeClustering

x = np.array([[1], [2], [4], [8], [9]])
for nguong in [1.5, 3, 5]:
    m = AgglomerativeClustering(n_clusters=None, linkage="single",
                                distance_threshold=nguong).fit(x)
    print(nguong, m.n_clusters_, m.labels_)

KẾT QUẢ

1.5 3 [2 2 1 0 0]
3 2 [0 0 0 1 1]
5 1 [0 0 0 0 0]

Ngưỡng 1,5 chỉ cho phép hai lần gộp khoảng cách 1, ngưỡng 3 thêm lần gộp khoảng cách 2, ngưỡng 5 gộp hết. Khớp đúng bảng tính tay ở đầu bài.

Kiểm tra nhanh

  1. Với năm khách 1, 2, 4, 8, 9 đơn và complete linkage, lần gộp thứ ba có khoảng cách bao nhiêu?

    • 3
    • 2
    • 4
    • 7
  2. Kẻ một đường ngang trên dendrogram thì đọc được gì?

    • Số khách trong cụm lớn nhất
    • Số cụm, bằng số nhánh mà đường ngang cắt qua
    • Silhouette của cách chia
  3. Những câu nào đúng về adjusted_rand_score(a, b)?

    • Đổi tên cụm trong b mà không đổi cách chia thì ARI không đổi
    • Bằng 1 khi hai cách chia giống hệt nhau
    • Cần a và b có cùng số thứ tự cho cùng một cụm
    • ARI cao chứng minh các cụm là nhóm khách có thật
  4. Vì sao single linkage trên bảng khách cho một cụm 1.473 khách?

    • Vì single linkage không dùng được dữ liệu đã scale
    • Vì 4 cụm là quá ít cho 1.500 khách
    • Vì hai cụm chỉ cần một cặp điểm gần nhau là gộp, nên các khách nằm giữa nối các nhóm lại thành chuỗi
Đúng hết lần đầu +15 XP

Bài tập

Đếm số cụm khi cắt cây

X là mảng NumPy hai chiều, mỗi dòng một điểm; nguong là độ cao cắt cây; cach_noi là một trong "ward", "complete", "average", "single". Viết thân hàm so_cum_khi_cat(X, nguong, cach_noi): phân cụm phân cấp bằng AgglomerativeClustering với n_clusters=None, distance_threshold=nguong, linkage=cach_noi, rồi đếm số cụm. Hàm không sửa mảng X của nơi gọi.

Trả về: số cụm, một int.

Ví dụ: với tám điểm (1; 1), (1,5; 1,2), (2; 0,8), (6; 1), (6,4; 1,5), (9; 5), (9,3; 5,4), (5; 6), ngưỡng 5 và "ward" cho 3.

python
import numpy as np
from sklearn.cluster import AgglomerativeClustering

def so_cum_khi_cat(X, nguong, cach_noi):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Phân cụm phân cấp bắt đầu với mỗi điểm một cụm rồi mỗi bước nhập hai cụm gần nhau nhất; linkage của SciPy ghi mỗi lần gộp thành một dòng.

  • Dendrogram vẽ các lần gộp theo độ cao; kẻ đường ngang ở đâu thì số nhánh bị cắt là số cụm.

  • AgglomerativeClustering(linkage=) chọn cách đo khoảng cách giữa hai cụm; ward cho cụm cỡ đều, single dễ nối thành chuỗi.

  • n_clusters=None cùng distance_threshold= cắt cây theo độ cao, đọc số cụm ở n_clusters_.

  • So hai cách chia bằng adjusted_rand_score(), vì số thứ tự cụm của hai thuật toán không khớp nhau.

  • Model này không có predict: nó chỉ chia các dòng đã có.

Câu hỏi thường gặp

Hierarchical clustering và K-means khác nhau ở đâu?

K-means cần chọn K trước và mỗi lần chạy cho một cách chia; phân cụm phân cấp dựng một cây, cắt ở đâu ra số cụm đó, và không phụ thuộc tâm ban đầu nên chạy lại vẫn ra cùng kết quả. Đổi lại, nó cần khoảng cách giữa mọi cặp điểm, nên chậm và tốn bộ nhớ khi bảng có hàng chục nghìn dòng.

Nên chọn linkage nào?

Với bảng khách hàng đã scale, ward thường cho các cụm cỡ đều và dễ đọc nhất. complete và average hợp khi muốn cụm gọn theo khoảng cách lớn nhất hay trung bình. single hợp với cụm có hình dải dài, nhưng dễ tạo một cụm khổng lồ khi có điểm nằm giữa các nhóm.

Dendrogram với hàng nghìn khách có đọc được không?

Không: lá cây chồng lên nhau thành một dải đen. Hãy vẽ trên một mẫu vài chục khách, hoặc dùng truncate_mode="lastp" của dendrogram để chỉ vẽ vài chục nhánh trên cùng.

Chủ đề

hierarchical clustering

Dữ liệu của bài

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập