Thuật toán phân vùng k-medoids cổ điển như PAM hoạt động hiệu quả đối với các tập dữ liệu nhỏ nhưng không chia tỷ lệ tốt cho các tập dữ liệu lớn. Nó có thể xử lý các tập dữ liệu cao hơn, có thể sử dụng phương pháp dựa trên lấy mẫu, được gọi là CLARA (Clustering Large Applications).
Cách tiếp cận đằng sau CLARA như sau:Nếu mẫu được chọn một cách khá ngẫu nhiên, nó phải xác định chặt chẽ tập dữ liệu ban đầu. Các đối tượng đại diện (medoid) được chọn sẽ tương tự như những đối tượng sẽ được chọn từ toàn bộ tập dữ liệu. CLARA vẽ một số mẫu của tập dữ liệu, áp dụng PAM trên mỗi mẫu và trả về phân cụm tốt nhất của nó làm đầu ra.
Hiệu suất của CLARA dựa trên kích thước mẫu. Theo quan sát, PAM tìm kiếm k medoid tốt nhất giữa một tập dữ liệu nhất định, trong khi CLARA tìm kiếm k medoid tốt nhất giữa các mẫu được chọn của tập dữ liệu. Một thuật toán loại k-medoids được gọi là CLARANS (Phân cụm các ứng dụng lớn phụ thuộc vào Tìm kiếm được phân vùng) đã được đề xuất. Nó có thể kết nối các phương pháp lấy mẫu với PAM. Trong khi CLARA có một mẫu cố định ở 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.
Quy trình phân cụm có thể được xem như một tìm kiếm thông qua một đồ thị, trong đó mỗi nút là một nghiệm có thể xảy ra (một tập hợp các k medoid). Hai nút là hàng xóm của nhau (đặc biệt, được liên kết bởi một cung trong biểu đồ) nếu tập hợp của chúng chỉ khác nhau một đối tượng. Mỗi nút có thể được chỉ định một chi phí được thể hiện bằng tổng sự khác biệt giữa mỗi đối tượng và trung bình của cụm của nó.
Ở mỗi bước, PAM xác định tất cả các lân cận của nút mới nhất trong quá trình tìm kiếm giải pháp chi phí tối thiểu. Sau đó, nút mới nhất được thay thế bằng nút lân cận có chi phí cao nhất. Vì CLARA hoạt động trên một mẫu của toàn bộ tập dữ liệu, nó xác định ít vùng lân cận hơn và hạn chế tìm kiếm đối với các đồ thị con nhỏ hơn đồ thị ban đầu.
CLARANS đã được thực nghiệm chứng minh là hiệu quả hơn cả PAM và CLARA. Nó có thể được sử dụng để khám phá số lượng cụm "tự nhiên" nhất bằng cách sử dụng hệ số hình bóng, một thuộc tính của đối tượng xác định mức độ mà đối tượng thực sự áp dụng cho cụm. CLARANS cũng cho phép phát hiện ra các ngoại lệ.
Độ phức tạp tính toán của CLARANS là O (n 2 ) với n là số đối tượng. Hơn nữa, chất lượng phân nhóm của nó dựa trên phương pháp lấy mẫu được sử dụng. Hơn nữa, khả năng CLARANS quản lý với các đối tượng dữ liệu nằm trên đĩa có thể được cải thiện bằng cách tập trung vào các phương pháp khám phá cấu trúc dữ liệu không gian, bao gồm R * -trees.