Phân cụm phân cấp Agglomerative là phương pháp phân cụm bottom-up (từ dưới lên) nơi 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 đặt mỗi đối tượng vào cụm của riêng 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 duy nhất hoặc cho đến khi đạt điều kiện dừng xác định. Một số phương pháp phân cụm phân cấp thuộc loại này. Chúng chỉ khác nhau ở định nghĩa độ tương đồng giữa các cụm.
Ví dụ, một phương pháp gọi là AGNES (Agglomerative Nesting) sử dụng kỹ thuật single-link và hoạt động như sau. Giả sử có các nhóm đối tượng đặt trong một hình chữ nhật. Ban đầu, mỗi đối tượng được đặt vào một cụm riêng. 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 có khoảng cách Euclid 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ị đồ họa bằng sơ đồ dạng cây gọi là dendrogram, cho thấy cả mối quan hệ cụm-cụm con và thứ tự các cụm được kết hợp (xem agglomerative) hoặc tách (xem divisive).
Thuật toán phân cụm phân cấp agglomerative cơ bản:
Tính ma trận gần kề, nếu cần thiết.
lặp lại
Hợp nhất hai cụm gần nhất.
Cập nhật ma trận gần kề để phản ánh sự gần kề giữa cụm mới và các cụm ban đầu.
cho đến khi chỉ còn một cụm.
Độ gần kề cụm thường được định nghĩa với một loại cụm cụ thể. Ví dụ, một số kỹ thuật phân cụm phân cấp agglomerative, bao gồm MIN, MAX, và Group Average, xuất phát từ quan điểm đồ thị về các cụm.
MIN định nghĩa độ gần kề cụm là độ gần kề giữa hai điểm gần nhất ở các cụm khác nhau, hoặc dùng phương pháp đồ thị, cạnh ngắn nhất giữa hai nút trong các tập con nút khác nhau.
Ngược lại, MAX lấy độ gần kề giữa hai điểm xa nhất trong các cụm khác nhau làm độ gần kề cụm, hoặc dùng phương pháp đồ thị, cạnh dài nhất giữa hai nút trong các tập con nút khác nhau.
Thuật toán phân cụm phân cấp agglomerative cơ bản được trình bày yêu cầu một ma trận gần kề. Điều này yêu cầu lưu trữ ½ m² độ gần kề (giả sử ma trận gần kề đối xứng) trong đó m là số điểm dữ liệu. Không gian cần để theo dõi các cụm tỷ lệ với số cụm, là m-1, không tính các cụm đơn. Do đó, độ phức tạp không gian tổng là O(m²).
Phân tích thuật toán phân cụm phân cấp agglomerative cơ bản cũng đơn giản về độ phức tạp tính toán. O(m²) thời gian cần để tính ma trận gần kề. Sau bước đó, có m-1 lần lặp chứa 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.