Series: Machine Learning Fundamentals – Bài 33
Ở các bài viết trước thuộc nhóm Học không giám sát (Unsupervised Learning), chúng ta đã tìm hiểu hai thuật toán phân nhóm phổ biến là K-Means (gom nhóm dựa trên tâm) và DBSCAN (gom nhóm dựa trên mật độ).
Tuy nhiên, cả hai thuật toán trên đều chỉ chia dữ liệu thành các cụm phẳng (Flat Clusters). Khi bạn muốn nhìn thấy mối quan hệ phân cấp dạng cây (Hierarchy) giữa các điểm dữ liệu và các cụm, Hierarchical Clustering (Phân cụm phân cấp) là lựa chọn tối ưu nhất.
Hierarchical Clustering là gì?
Hierarchical Clustering là một thuật toán học không giám sát dùng để nhóm các điểm dữ liệu tương đồng lại với nhau tạo thành một cấu trúc cây phân cấp (Tree-based Hierarchy).
Khác với K-Means, Hierarchical Clustering không yêu cầu khai báo trước số lượng cụm $K$. Kết quả của thuật toán được trực quan hóa thông qua một biểu đồ cây gọi là Dendrogram.
┌───────┴───────┐ <-- Cụm lớn (Gom tất cả điểm)
┌───┴───┐ ┌───┴───┐ <-- Các cụm trung gian
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
A B C D E F G H <-- Các điểm dữ liệu ban đầu
Tài liệu chính thức mô tả Hierarchical Clustering xây dựng các cụm nối tiếp nhau bằng cách hợp nhất hoặc chia nhỏ các cụm đã có. Xem thêm tại Scikit-Learn Hierarchical Clustering Documentation.
Hai chiến lược phân cấp chính
Thuật toán được chia thành 2 chiến lược phân chia chính:
1. Agglomerative Clustering (Từ dưới lên – Bottom-up)
-
Phổ biến nhất trong thực tế.
-
Ban đầu, coi mỗi điểm dữ liệu là một cụm riêng biệt ($N$ điểm = $N$ cụm).
-
Ở mỗi bước, thuật toán sẽ tìm và gộp 2 cụm gần nhau nhất lại thành một cụm lớn hơn.
-
Quá trình lặp lại liên tục cho đến khi toàn bộ dữ liệu gộp thành một cụm duy nhất.
2. Divisive Clustering (Từ trên xuống – Top-down)
-
Ban đầu, coi toàn bộ $N$ điểm dữ liệu là một cụm duy nhất.
-
Ở mỗi bước, thuật toán sẽ chia nhỏ cụm thành các cụm con ít tương đồng hơn.
-
Quá trình lặp lại cho đến khi mỗi điểm dữ liệu nằm trong một cụm riêng biệt.
Các phương pháp đo khoảng cách giữa các cụm (Linkage Metrics)
Để quyết định hai cụm nào sẽ được gộp lại với nhau, Hierarchical Clustering cần đo khoảng cách giữa 2 cụm tập hợp điểm. Thuật toán sử dụng các tiêu chuẩn đo khoảng cách (Linkage Criteria):
-
Single Linkage: Khoảng cách giữa 2 điểm gần nhất của 2 cụm.
-
Đặc điểm: Dễ tạo ra các cụm dài, uốn lượn (nhưng nhạy cảm với nhiễu và dễ bị hiện tượng “chuỗi” – Chaining Effect).
-
-
Complete Linkage: Khoảng cách giữa 2 điểm xa nhất của 2 cụm.
-
Đặc điểm: Tạo ra các cụm có đường kính compact, chặt chẽ và tương đồng về kích thước.
-
-
Average Linkage: Khoảng cách trung bình giữa tất cả các cặp điểm thuộc 2 cụm.
-
Đặc điểm: Cân bằng giữa Single và Complete Linkage, ít bị ảnh hưởng bởi Outliers.
-
-
Ward’s Linkage (Phổ biến nhất): Tối thiểu hóa tổng phương sai trong cụm (Within-Cluster Variance) sau khi gộp.
-
Đặc điểm: Tạo ra các cụm có kích thước đều đặn, rất giống cách gom nhóm của K-Means nhưng theo dạng phân cấp.
-
Biểu đồ Dendrogram và cách chọn số cụm
Dendrogram là công cụ trực quan hóa cốt lõi của Hierarchical Clustering, thể hiện toàn bộ lịch sử gộp/tách các cụm.
-
Trục hoành (X): Đại diện cho từng điểm dữ liệu đơn lẻ.
-
Trục tung (Y): Đại diện cho khoảng cách/độ không tương đồng (Euclidean Distance) giữa các cụm được gộp.
Khoảng cách (Y)
│ ┌───────────────┐
│ ┌───┴───┐ ┌───┴───┐
│── ──┼───────┼───────┼───────┼── ── (Cắt đường ngang tại đây -> Thu được 2 cụm)
│ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
└────A─B─────C─D─────E─F─────G─H──── Điểm dữ liệu (X)
Quy tắc chọn số cụm tối ưu từ Dendrogram:
-
Quan sát các đường liên kết thẳng đứng trên trục $Y$.
-
Tìm vị trí có khoảng cách dọc dài nhất mà không bị đường ngang nào cắt qua.
-
Kẻ một đường cắt ngang (Horizontal Cut) qua vị trí đó.
-
Số lượng đường dọc bị cắt chính là số cụm tối ưu.
Dữ liệu có cần Feature Scaling không?
CỰC KỲ BẮT BUỘC.
Hierarchical Clustering dựa hoàn toàn vào việc tính toán khoảng cách hình học giữa các điểm và các cụm dữ liệu. Nếu các đặc trưng có thang đo chênh lệch (ví dụ: Thu nhập hàng triệu và Tuổi từ 18–60), đặc trưng có quy mô lớn sẽ chiếm toàn bộ trọng số tính toán. Bắt buộc áp dụng StandardScaler hoặc MinMaxScaler trước khi thực hiện.
Độ phức tạp tính toán (Time & Space Complexity)
Đây là điểm bạn cần đặc biệt lưu ý khi lựa chọn thuật toán:
-
Time Complexity (Độ phức tạp thời gian): Thường là $O(N^3)$ cho thuật toán cơ bản, hoặc tối ưu đạt $O(N^2 \log N)$ đối với Agglomerative Clustering (với $N$ là số lượng mẫu dữ liệu). Do phải liên tục tính toán ma trận khoảng cách giữa tất cả các cặp cụm qua mỗi vòng lặp, thuật toán chạy rất chậm khi $N$ lớn.
-
Space Complexity (Độ phức tạp bộ nhớ): $O(N^2)$ do phải lưu trữ ma trận khoảng cách (Distance Matrix) trong RAM.
So sánh K-Means và Hierarchical Clustering
| Tiêu chí | K-Means Clustering | Hierarchical Clustering |
| Khai báo số cụm $K$ | Bắt buộc chọn trước | Không cần chọn trước (Quyết định sau qua Dendrogram) |
| Cấu trúc cụm | Cụm phẳng (Flat Clusters) | Cụm phân cấp dạng cây (Tree Hierarchy) |
| Độ phức tạp thời gian | $O(N)$ – Tốc độ rất nhanh | $O(N^2 \log N)$ đến $O(N^3)$ – Chậm trên dữ liệu lớn |
| Dung lượng Dataset | Hoạt động tốt trên Dataset lớn | Chỉ phù hợp Dataset vừa và nhỏ ($N < 10,000$) |
| Tính nhất quán | Khác nhau giữa các lần chạy (do khởi tạo tâm) | Kết quả giống nhau $100\%$ giữa các lần chạy |
Ưu điểm và Nhược điểm của Hierarchical Clustering
Ưu điểm
-
Không cần chọn trước số lượng cụm $K$ trước khi chạy mô hình.
-
Cung cấp biểu đồ Dendrogram trực quan hóa mối quan hệ phân cấp trực diện giữa các đối tượng.
-
Kết quả phân cụm hoàn toàn ổn định và có tính nhất quán (Determinism).
-
Linh hoạt với nhiều thước đo khoảng cách và tiêu chí gộp cụm (Linkage).
Nhược điểm
-
Chi phí tính toán và bộ nhớ lớn: Khó áp dụng cho Dataset lớn ($N > 10,000$ mẫu).
-
Khi hai cụm đã gộp lại với nhau ở một bước, nó không thể hoàn tác ở các bước tiếp theo (dễ bị tích tụ lỗi gộp sai từ bước đầu).
-
Nhạy cảm với Outliers (đặc biệt khi dùng Single Linkage).
Khi nào nên dùng Hierarchical Clustering?
-
Tập dữ liệu có kích thước nhỏ đến vừa ($N < 5,000$ mẫu).
-
Cần tìm mối quan hệ phân cấp giữa các nhóm (ví dụ: Phân loại chủng loài sinh học, xây dựng cây gia phả dữ liệu, phân cấp danh mục sản phẩm).
-
Muốn quan sát biểu đồ Dendrogram để khám phá cấu trúc dữ liệu trước khi quyết định chia bao nhiêu nhóm.
Tóm tắt
-
Hierarchical Clustering xây dựng cây phân cấp cụm thông qua biểu đồ Dendrogram.
-
Tiếp cận theo chiến lược Agglomerative (Gộp từ dưới lên) là phổ biến nhất.
-
Kẻ đường cắt ngang trên Dendrogram tại khoảng cách dọc lớn nhất để chọn số cụm tối ưu.
-
Thuật toán có độ phức tạp $O(N^2 \log N)$, chỉ thích hợp cho các bộ dữ liệu vừa và nhỏ.
-
Bắt buộc thực hiện Feature Scaling trước khi chạy thuật toán.
Tài liệu tham khảo
-
Scikit-Learn Documentation: Agglomerative Clustering in Scikit-Learn
-
Müllner (2011): Modern hierarchical, agglomerative clustering algorithms – Bài báo phân tích tối ưu độ phức tạp thời gian cho Hierarchical Clustering.
-
Ward (1963): Hierarchical Grouping to Optimize an Objective Function – Bài báo gốc về Ward’s Linkage.
Khóa học tại MCNA Technology School
Nếu bạn muốn thực hành Machine Learning, Python và xây dựng các mô hình trên dữ liệu thực tế, có thể tham khảo:
Tác giả: Bùi Đình Tuyển – Data Analyst tại MCNA Technology School
📞 Hotline: 0939.866.825 (Mr. Khang)
🌐 Website: MCNA Technology School
📍 Hà Nội: 30 Trung Liệt, Đống Đa | Liền kề 44B TT2 Văn Quán, Hà Đông
📍 TP.HCM: 50B Phan Tây Hồ, Cầu Kiệu
