Vấn đề của PAM trên dữ liệu lớn
Thuật toán k-medoids phân vùng kinh điển như PAM (Partitioning Around Medoids) hoạt động hiệu quả cho tập dữ liệu nhỏ nhưng không mở rộng tốt cho tập dữ liệu lớn.
CLARA (Clustering Large Applications) - Dựa trên lấy mẫu
Ý tưởng: Nếu mẫu được chọn ngẫu nhiên hợp lý, nó đại diện tốt cho tập dữ liệu gốc. Các đối tượng đại diện (medoids) chọn được sẽ tương tự như chọn từ toàn bộ tập dữ liệu.
Quy trình: CLARA rút nhiều mẫu từ tập dữ liệu, áp dụng PAM trên mỗi mẫu, trả về phân cụm tốt nhất làm đầu ra.
Hiệu suất: Phụ thuộc vào kích thước mẫu. PAM tìm k medoids tốt nhất trong tập dữ liệu cho trước; CLARA tìm k medoids tốt nhất trong các mẫu được chọn.
CLARANS (Clustering Large Applications based on RANdomized Search)
Thuật toán k-medoids kết hợp lấy mẫu với PAM. Khác với CLARA có mẫu cố định ở mỗi giai đoạn tìm kiếm, CLARANS rút mẫu với ngẫu nhiên ở mỗi giai đoạn tìm kiếm.
Mô hình tìm kiếm dạng đồ thị:
- Mỗi nút = giải pháp tiềm năng (tập k medoids).
- Hai nút là láng giềng nếu tập khác nhau chỉ một đối tượng.
- Mỗi nút gán chi phí = tổng độ khác biệt giữa mỗi đối tượng và medoid của cụm nó.
So sánh chiến lược tìm kiếm:
- PAM: Xét TẤT CẢ láng giềng của nút hiện tại để tìm giải pháp chi phí tối thiểu. Thay nút hiện tại bằng láng giềng giảm chi phí mạnh nhất.
- CLARA: Hoạt động trên mẫu → xét ÍT láng giềng hơn, giới hạn tìm kiếm trong các đồ thị con nhỏ hơn đồ thị gốc.
- CLARANS: Rút mẫu ngẫu nhiên mỗi bước → hiệu quả hơn cả PAM và CLARANS (thực nghiệm).
Ưu điểm CLARANS
- Hiệu quả hơn PAM và CLARA (thực nghiệm).
- Khám phá số cụm "tự nhiên" nhất dùng hệ số silhouette (đặc tính đối tượng định nghĩa mức độ đối tượng thực sự thuộc cụm).
- Cho phép phát hiện giá trị ngoại lai (outliers).
Độ phức tạp và cải tiến
Độ phức tạp tính toán CLARANS: O(n²) với n = số đối tượng. Chất lượng phân cụm phụ thuộc phương pháp lấy mẫu. Khả năng xử lý đối tượng trên đĩa có thể cải tiến bằng phương pháp khám phá cấu trúc dữ liệu không gian (R*-trees).