Hierarchical clustering: dendrogram, AgglomerativeClustering
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
Trong bài này · 11
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:
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:
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:
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()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():
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.007ARI (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:
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
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
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
Những câu nào đúng về
adjusted_rand_score(a, b)?- Đổi tên cụm trong
bmà 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
avàbcó 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
- Đổi tên cụm trong
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
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.
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àyTó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;
linkagecủ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;wardcho cụm cỡ đều,singledễ nối thành chuỗi.n_clusters=Nonecùngdistance_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ủ đề
Dữ liệu của bài
- Tải xuống
chi_tieu_khach_hang.csv
CSV · 41.72 KB
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
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.