Phân tích cụm là một nhánh của thống kê đã được nghiên cứu rộng rãi trong vài năm. Lợi ích của việc sử dụng kỹ thuật này là các cấu trúc hoặc cụm thú vị có thể được khám phá trực tiếp từ dữ liệu mà không cần sử dụng bất kỳ kiến thức nền tảng nào, chẳng hạn như phân cấp khái niệm.
Các thuật toán phân cụm được sử dụng trong thống kê, như PAM hoặc CLARA, được báo cáo là không hiệu quả theo quan điểm độ phức tạp tính toán. Theo mối quan tâm về hiệu quả, một thuật toán mới có tên CLARANS (Phân cụm các ứng dụng lớn dựa trên Tìm kiếm ngẫu nhiên) đã được phát triển để phân tích cụm.
PAM (Phân vùng xung quanh Medoid) - Giả sử rằng có n đối tượng, PAM tìm k cụm bằng cách đầu tiên tìm một đối tượng đại diện cho mỗi cụm. Một đại diện như vậy, là điểm nằm ở trung tâm trong một cụm, được gọi là medoid.
Sau khi chọn k medoid, thuật toán lặp lại cố gắng tạo ra lựa chọn medoid tốt nhất phân tích tất cả các cặp đối tượng khả thi sao cho một đối tượng là medoid và đối tượng kia thì không. Phép đo chất lượng phân nhóm được tính toán cho mỗi sự kết hợp như vậy.
Lựa chọn tốt các điểm trong một lần lặp được chọn làm điểm trung bình cho lần lặp sau. Chi phí của một lần lặp lại là O (k (n − k) 2 ). Do đó, nó khá kém hiệu quả về mặt tính toán đối với các giá trị lớn của n và k.
CLARA (Nhóm các ứng dụng lớn) - Sự khác biệt giữa thuật toán PAM và CLARA là thuật toán sau dựa trên lấy mẫu. Chỉ có một phần nhỏ dữ liệu thực được chọn làm đại diện cho dữ liệu và các medoid được chọn từ mẫu này bằng cách sử dụng PAM.
Ý tưởng là nếu mẫu được chọn theo cách khá ngẫu nhiên, thì mẫu đó đại diện chính xác cho toàn bộ tập dữ liệu và do đó, các đối tượng đại diện (medoid) được chọn sẽ tương tự như được chọn từ toàn bộ tập dữ liệu.
CLARA lấy một số mẫu và đưa ra phân nhóm tốt từ các mẫu này. CLARA có thể xử lý tập dữ liệu cao hơn PAM. Độ phức tạp của mỗi lần lặp bây giờ trở thành O (kS 2 + k (n-k)), trong đó S là kích thước của mẫu.
CLARANS (Nhóm các ứng dụng lớn dựa trên Tìm kiếm theo miền) - Thuật toán CLARANS kết hợp cả PAM và CLARA bằng cách chỉ tìm kiếm tập con của tập dữ liệu và nó không tự ràng buộc vào một số mẫu tại bất kỳ thời điểm nào. Trong khi CLARA có một mẫu không đổi ở mỗi giai đoạn của tìm kiếm, CLARANS lấy một mẫu với một số ngẫu nhiên trong mọi giai đoạn của tìm kiếm.
Giai đoạn phân cụm có thể được trình bày dưới dạng tìm kiếm một đồ thị trong đó mỗi nút là một giải pháp khả thi, tức là một tập hợp các k medoid. Phân cụm thu được sau khi thay thế một medoid duy nhất được gọi là lân cận của phân cụm hiện tại.