Phân tích cụm (Cluster analysis) là nhánh thống kê được nghiên cứu rộng rãi nhiều năm. Lợi ích dùng kỹ thuật này: cấu trúc hoặc cụm thú vị có thể khám phá trực tiếp từ dữ liệu không dùng kiến thức nền như phân cấp khái niệm.
Thuật toán phân cụm dùng trong thống kê như PAM hoặc CLARA, báo cáo kém hiệu quả từ góc độ độ phức tạp tính toán. Về mặt hiệu suất, thuật toán mới CLARANS (Clustering Large Applications based upon Randomized Search) phát triển cho phân tích cụm.
PAM (Partitioning around Medoids) – Giả sử n đối tượng, PAM tìm k cụm bằng cách trước tìm đối tượng đại diện cho mỗi cụm. Đại diện này, điểm vị trí trung tâm trong cụm, gọi là medoid.
Sau chọn k medoids, thuật toán lặp lại cố gắng tạo lựa chọn tốt nhất medoids phân tích tất cả cặp đối tượng khả thi: một đối tượng là medoid, một không. Đồ lường chất lượng cụm tính cho mỗi tổ hợp. Lựa chọn điểm tốt trong một lần lặp chọn làm medoids cho lần lặp tiếp theo. Chi phí một lần lặp O(k(n−k)2). Do đó tính toán khá kém hiệu quả cho n và k lớn.
CLARA (Clustering Large Applications) – Khác biệt PAM và CLARA: CLARA dựa trên lấy mẫu (sampling). Chỉ một phần nhỏ dữ liệu thật chọn làm đại diện dữ liệu và medoids chọn từ mẫu này dùng PAM.
Ý tưởng: nếu mẫu chọn ngẫu nhiên đủ tốt, nó đại diện đúng toàn bộ tập dữ liệu, do đó đối tượng đại diện (medoids) chọn sẽ tương tự như chọn từ toàn bộ tập dữ liệu. CLARA vẽ nhiều mẫu và xuất cụm tốt nhất từ các mẫu này. CLARA xử lý tập dữ liệu lớn hơn PAM. Độ phức tạp mỗi lần lặp thành O(kS2+k(n−k)), S là kích thước mẫu.
CLARANS (Clustering Large Applications based upon RANdomized Search) – CLARANS kết hợp PAM và CLARA bằng cách chỉ tìm kiếm tập con tập dữ liệu và không giới hạn mình trong mẫu nào tại thời điểm cho trước. Trong khi CLARA có mẫu hằng số mỗi giai đoạn tìm kiếm, CLARANS vẽ mẫu với ngẫu nhiên mỗi giai đoạn tìm kiếm.
Giai đoạn phân cụm có thể trình bày như tìm kiếm đồ thị nơi mỗi nút là giải pháp khả thi, tức là tập k medoids. Phân cụm sau khi thay thế một medoid đơn lẻ gọi là neighbor của phân cụm hiện tại.