Phân cụm phân cấp tổng hợp là cách tiếp cận phân cụm từ dưới lên trong đó các cụm có các cụm con, liên tiếp có các cụm con, v.v. Nó bắt đầu bằng cách định vị mọi đố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 cao hơn và cao hơn cho đến khi một số đối tượng trong một cụm đơn lẻ hoặc cho đến khi nó cần một điều kiện kết thúc xác định. Một số cách tiếp cận phân cụm phân cấp được sử dụng cho kiểu này. Chúng chỉ khác biệt trong mô tả về sự giống nhau giữa các cụm.
Ví dụ, một phương pháp có tên là AGNES (Agglomerative Nesting) cần các kỹ thuật liên kết đơn và hoạt động như sau. Xét có các nhóm đồ vật được đặt trong một hình chữ nhật. Ban đầu, mỗi đối tượng được định vị thành một cụm của riêng nó. Do đó, các cụm được kết hợp từng bước theo một số nguyên tắc liên quan đến việc hợp nhất các cụm với 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 cụm phân cấp được hiển thị bằng đồ thị bằng cách sử dụng sơ đồ giống cây được gọi là biểu đồ hình hạt, cho thấy cả các liên kết cụm-cụm con và thứ tự mà các cụm được kết hợp (chế độ xem tổng hợp) hoặc phân chia (chế độ xem chia).
Thuật toán phân nhóm phân cấp tích hợp cơ bản.
-
Tính toán ma trận tiệm cận, nếu cần.
-
lặp lại
-
Hợp nhất hai cụm gần nhất.
-
Làm mới ma trận vùng lân cận để phản ánh vùng lân cận giữa cụm mới và các cụm ban đầu.
-
cho đến khi chỉ còn lại một cụm.
Vùng lân cận của cụm thường được xác định với một loại cụm cụ thể. Ví dụ:một số kỹ thuật phân nhóm phân cấp tổng hợp, bao gồm MIN, MAX và Nhóm trung bình, đến từ chế độ xem dựa trên biểu đồ của các cụm.
MIN định nghĩa độ gần cụm là điểm gần giữa hai điểm đóng trong nhiều cụm hoặc sử dụng phương pháp đồ thị, cạnh ngắn nhất giữa hai nút trong một số tập hợp con của các nút.
Ngoài ra, MAX lấy khoảng cách giữa hai điểm xa nhất trong nhiều cụm làm điểm gần của cụm hoặc sử dụng phương pháp đồ thị, cạnh cao nhất giữa hai nút trong các tập con khác nhau của các nút.
Thuật toán phân cụm phân cấp theo khái niệm được trình bày yêu cầu một ma trận lân cận. Điều này yêu cầu kho chứa các tiệm cận $ \ mathrm {\ frac {1} {2} m ^ 2} $ (coi ma trận tiệm cận là đối xứng) trong đó m là nhiều điểm dữ liệu. Không gian cần thiết để duy trì theo dõi các cụm tỷ lệ với nhiều cụm, là m- 1, không bao gồm các cụm singleton. Do đó, tổng độ phức tạp của không gian là $ \ mathrm {O (m ^ 2)} $.
Việc phân tích thuật toán phân cụm phân cấp tích hợp cơ bản cũng dễ dàng liên quan đến độ phức tạp tính toán. $ \ mathrm {O (m ^ 2)} $ thời gian là cần thiết để tính toán ma trận tiệm cận. Sau bước đó, có m - 1 lần lặp chứa các bước 3 và 4 vì có m cụm ở đầu và hai cụm được hợp nhất trong mỗi lần lặp.