Giới thiệu
Kỹ thuật phân cụm phân cấp gom nhóm đối tượng dữ liệu thành một cây các cụm (tree of clusters). Thuật toán phân cụm phân cấp hoặc top-down hoặc bottom-up. Chất lượng phương pháp phân cấp thuần túy suy giảm do không thể điều chỉnh sau khi quyết định gộp hoặc tách đã thực hiện.
Đo lường khoảng cách giữa cụm
Việc gộp cụm dựa trên khoảng cách giữa các cụm. Các thước đo phổ biến (mi là trung bình cụm Ci, ni số điểm trong Ci, |p - p'| khoảng cách hai điểm):
Hai loại phương pháp phân cụm phân cấp
1. Agglomerative Hierarchical Clustering (AHC) - Tự dưới lên (Bottom-up)
Cụm có cụm con, cụm con có cụm con con, v.v. Bắt đầu đặt mỗi đối tượng vào cụm riêng, sau đó gộp các cụm nguyên tử thành cụm lớn dần cho đến khi tất cả đối tượng trong một cụm duy nhất hoặc thỏa mãn điều kiện dừng. Đa số phương pháp phân cấp áp dụng loại này. Chỉ khác nhau ở định nghĩa độ tương đồng giữa cụm.
Ví dụ AGNES (Agglomerative Nesting): Sử dụng kỹ thuật single-link. Đối tượng ban đầu mỗi cái một cụm. Gộp từng bước theo nguyên tắc: gộp cụm có khoảng cách Euclidean tối thiểu giữa các đối tượng gần nhất trong cụm.
2. Divisive Hierarchical Clustering (DHC) - Tự trên xuống (Top-down)
Ít dùng hơn. Hoạt động tương tự agglomerative nhưng ngược chiều. Bắt đầu một cụm chứa tất cả đối tượng, sau đó tách liên tiếp cụm kết quả cho đến khi chỉ còn cụm đơn đối tượng hoặc thỏa mãn điều kiện dừng (số cụm mong muốn đạt được hoặc khoảng cách giữa hai cụm gần nhất vượt ngưỡng).
Phương pháp divisive hiếm có và ít dùng do khó khăn quyết định tách đúng ở cấp cao. DIANA (Divisive Analysis) là ví dụ: hoạt động ngược AGNES. Ban đầu tất cả đối tượng trong một cụm. Tách theo nguyên tắc: tách cụm theo khoảng cách Euclidean tối đa giữa các đối tượng láng giềng gần nhất trong cụm.