Phân cụm phân cấp

Phân cụm phân cấp là gì?

Phân cụm phân cấp xây dựng cây phân cụm (dendrogram) bằng cách lặp lại việc hợp nhất hai cụm gần nhất. Không cần chỉ định K trước và có thể cắt ở bất kỳ mức nào.

Phương pháp liên kết: đơn (khoảng cách tối thiểu, xu hướng chuỗi), hoàn chỉnh (tối đa, cụm gọn), trung bình (trung bình), Ward (tối thiểu phương sai, thường cân bằng nhất).

Bảng lịch sử hợp nhất ghi khoảng cách mỗi bước. Nhảy lớn trong khoảng cách gợi ý ranh giới cụm tự nhiên.

Formula: Liên kết đơn: d(A,B) = min{d(a,b) : a∈A, b∈B} Liên kết đầy đủ: d(A,B) = max{d(a,b) : a∈A, b∈B} Liên kết trung bình: d(A,B) = (1/|A||B|) ΣΣ d(a,b) Ward: ΔV = (nₐnᵦ)/(nₐ+nᵦ) ‖μₐ − μᵦ‖²

Ví dụ tính toán

Điểm: A(0,0), B(1,0), C(4,0), D(5,0). Liên kết đơn: Bước 1 A+B (khoảng cách=1), Bước 2 C+D (1), Bước 3 {A,B}+{C,D} (3). Cắt ở khoảng cách 2 → 2 cụm.

Khi nào sử dụng công cụ này

• Nhà nghiên cứu khám phá các nhóm tự nhiên trong dữ liệu mà không cần cố định trước số cụm — biểu đồ dendrogram tiết lộ cấu trúc ở mọi mức độ chi tiết
• Nhà tin sinh học phân cụm hồ sơ biểu hiện gen hoặc chuỗi protein dựa trên các thước đo độ tương đồng
• Nhà nghiên cứu thị trường nhóm sản phẩm hoặc khách hàng thành hệ phân loại với các danh mục con lồng nhau
• Chuyên viên phân tích dữ liệu cần so sánh cách các phương pháp liên kết khác nhau ảnh hưởng đến thành phần và cấu trúc cụm

Những sai lầm thường gặp

• Dùng liên kết đơn trên dữ liệu nhiễu — liên kết đơn dễ gặp 'hiệu ứng chuỗi' khi các điểm nhiễu bắc cầu giữa các cụm riêng biệt, gộp chúng quá sớm; hãy dùng Ward hoặc Liên kết đầy đủ cho hầu hết ứng dụng
• Không chuẩn hóa đặc trưng — phân cụm phân cấp dùng các thước đo khoảng cách nhạy với thang đo; các biến có khoảng giá trị lớn chi phối trừ khi mọi đặc trưng được chuẩn hóa
• Chọn số cụm mà không xem mẫu hình khoảng cách gộp — cắt tùy tiện tạo ra các cụm vô nghĩa; luôn xem biểu đồ dendrogram hoặc lịch sử khoảng cách gộp để tìm điểm ngắt tự nhiên
• Áp dụng phân cụm phân cấp cho tập dữ liệu rất lớn mà không lấy mẫu con — độ phức tạp bộ nhớ O(n2) và thời gian O(n3) khiến nó không khả thi với tập dữ liệu trên ~10,000 điểm; dùng K-Means hoặc cách tiếp cận mini-batch cho dữ liệu lớn

Cách diễn giải kết quả

• Bước nhảy lớn trong khoảng cách gộp ở bảng lịch sử gộp cho thấy ranh giới cụm tự nhiên — các cụm ngay trước một bước nhảy lớn là các nhóm có ý nghĩa
• Nếu phương pháp Ward và Liên kết đầy đủ cho ra các cụm tương tự, việc phân nhóm là vững chắc; nếu chúng khác nhau đáng kể, cấu trúc cụm có thể mơ hồ
• Các cụm có kích thước rất chênh lệch (ví dụ: một cụm chứa 90% số điểm) có thể cho thấy dữ liệu không có nhóm tự nhiên mạnh ở mức cắt đó — hãy thử số cụm khác

Tiêu chuẩn và tài liệu tham khảo

• Ward, J. H. (1963), 'Hierarchical Grouping to Optimize an Objective Function', Journal of the American Statistical Association — nguồn gốc của liên kết phương sai tối thiểu Ward
• Lance & Williams (1967), 'A General Theory of Classificatory Sorting Strategies', The Computer Journal — công thức truy hồi thống nhất bao quát liên kết đơn, hoàn chỉnh và trung bình
• Everitt, Landau, Leese & Stahl, Cluster Analysis (Wiley) — giáo trình chuẩn về các phương pháp kết tụ và diễn giải dendrogram

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

Nên dùng phương pháp liên kết nào?

Ward phổ biến nhất — tạo cụm gọn và đều. Tránh liên kết đơn vì dễ bị hiệu ứng chuỗi.

Cắt dendrogram ở đâu?

Tìm khoảng trống lớn nhất trong khoảng cách hợp nhất, hoặc dựa trên kiến thức chuyên môn, hoặc dùng hệ số bất nhất quán.