Kỹ thuật phân cụm phân cấp hoạt động bằng cách kết hợp các đối tượng dữ liệu thành một cây các cụm. Các thuật toán phân cụm theo thứ bậc là từ trên xuống hoặc từ dưới lên. Chất lượng của một phương pháp phân nhóm phân cấp xác thực sẽ giảm đi do không có khả năng thực hiện điều chỉnh sau khi hoàn thành quyết định hợp nhất hoặc tách.
Việc hợp nhất các cụm dựa trên khoảng cách giữa các cụm. Các thước đo được sử dụng rộng rãi cho khoảng cách giữa các cụm như sau, trong đó mi là giá trị trung bình của cụm Ci, ni là số điểm trong Ci và | p - p ’| là khoảng cách giữa hai điểm p và p '.
Các loại phương pháp phân cụm theo thứ bậc
Có hai loại phương pháp phân cụm phân cấp như sau -
Phân cụm phân cấp tổng hợp (AHC) - AHC là một phương pháp phân cụm từ dưới lên trong đó các cụm có các cụm con, lần lượt có các cụm con, v.v. Nó bắt đầu bằng cách định vị từng đối tượng trong cụm của nó và sau đó kết hợp các cụm nguyên tử này thành các cụm lớn hơn và lớn hơn cho đến khi tất cả các đối tượng nằm trong một cụm đơn lẻ hoặc cho đến khi nó thỏa mãn điều kiện kết thúc cụ thể. Hầu hết các phương pháp phân cụm phân cấp đều được áp dụng cho kiểu này. Chúng chỉ khác biệt trong định nghĩa của chúng về sự giống nhau giữa các cụm.
Ví dụ, một phương pháp được gọi là AGNES (Agglomerative Nesting), sử dụng các kỹ thuật liên kết đơn và hoạt động như sau. Xem xét có một tập hợp các đối tượng nằm trong một hình chữ nhật. Ban đầu, mỗi đối tượng được đặt vào một cụm của riêng nó. Sau đó, các cụm được kết hợp từng bước theo một số nguyên tắc bao gồm hợp nhất các cụm có khoảng cách Euclide tối thiểu giữa các đối tượng gần nhất trong cụm.
Phân nhóm phân chia thứ bậc (DHC) - DHC là cách tiếp cận từ trên xuống và ít được sử dụng hơn. Nó hoạt động theo các phương pháp tương tự như phân cụm tích tụ nhưng theo hướng ngược lại. Phương pháp này bắt đầu với một cụm duy nhất bao gồm tất cả các đối tượng, sau đó tách liên tiếp các cụm kết quả cho đến khi chỉ còn lại các cụm đối tượng đơn lẻ hoặc cho đến khi nó thỏa mãn điều kiện kết thúc cụ thể, bao gồm số lượng cụm mong muốn thu được hoặc khoảng cách giữa hai cụm gần nhất là trên a khoảng cách ngưỡng cụ thể.
Phương pháp chia thường không thể truy cập được và hiếm khi được sử dụng vì khó tạo ra quyết định chia đúng ở mức cao. DIANA (Phân tích số chia) là một ví dụ về phương pháp phân nhóm phân cấp có thể chia hết. Nó hoạt động theo thứ tự ngược lại. Ban đầu, tất cả các đối tượng đều nằm trong một cụm. Do đó, cụm được phân chia theo một số nguyên tắc, bao gồm việc tách các cụm theo khoảng cách Euclid tối đa giữa các đối tượng lân cận gần nhất trong cụm.