Phương pháp phân cụm phân vùng được mong muốn vì nó giảm thiểu khoảng cách giữa các tập hợp và trung tâm cụm của chúng. Nếu nó có thể chọn phương pháp k-means, thì không thể có trung tâm cụm nếu tồn tại các chướng ngại vật.
Ví dụ, cụm có thể nằm ở trung tâm của một cái hồ. Nói cách khác, phương pháp k-medoids chọn một đối tượng bên trong cụm làm trung tâm và do đó đảm bảo rằng vấn đề không thể xuất hiện.
Tại mỗi thời điểm một medoid mới được chọn, khoảng cách giữa mỗi đối tượng và trung tâm cụm mới được chọn của nó phải được tính toán lại. Bởi vì có thể có chướng ngại vật giữa hai đối tượng, khoảng cách giữa hai đối tượng có thể được tính toán hình học (ví dụ:liên quan đến phép toán tam giác).
Chi phí tính toán có thể cao nếu chứa một số lượng lớn các đối tượng và chướng ngại vật. Vấn đề phân cụm với các chướng ngại vật có thể được xác định bằng cách sử dụng mô tả đồ họa. Đầu tiên, một điểm, p, là biểu kiến từ một điểm khác, q, trong vùng, R, nếu đường thẳng liền kề p và q không giao nhau với một số chướng ngại vật.
Biểu đồ khả năng hiển thị là biểu đồ, V G =(V, E), bao gồm mỗi đỉnh của chướng ngại vật có một nút tương đương ở V và hai nút, v 1 và v 2 , trong V được kết hợp bởi một cạnh trong E nếu và chỉ khi các đỉnh tương đương mà chúng xác định có thể nhìn thấy nhau.
Gọi VG ’=(V’, E ’) là một đồ thị khả năng hiển thị được tạo ra từ VG bằng cách chèn thêm hai điểm, p và q, trong V’. E ’bao gồm một cạnh cộng hai điểm trong V0 nếu hai điểm đó cùng nhìn thấy.
Nó có thể được sử dụng để giảm chi phí tính toán khoảng cách giữa hai tập hợp đối tượng hoặc điểm bất kỳ, nhiều phương pháp tiền xử lý và tối ưu hóa có thể được sử dụng. Có một nhóm phương pháp tiếp cận các điểm gần nhau thành các nhóm nhỏ. Điều này có thể được hoàn thành bằng cách đầu tiên tam giác vùng R thành các tam giác, sau đó kết hợp các điểm lân cận trong tam giác tương tự thành các cụm vi mô, sử dụng cách tiếp cận tương tự như BIRCH hoặc DBSCAN.
Bằng cách xử lý các vi cụm thay vì các điểm đơn lẻ, việc tính toán hoàn chỉnh được giảm bớt. Sau đó, tính toán trước có thể được thực hiện để xây dựng hai loại chỉ số kết hợp phụ thuộc vào việc tính toán các đường đi ngắn nhất -
-
Chỉ số VV, đối với một số cặp đỉnh chướng ngại vật.
-
Chỉ số MV, cho một số cặp vi lớp và đỉnh chướng ngại vật. Nó có thể tạo điều kiện cho các chỉ số giúp tối ưu hóa hơn hiệu suất tổng thể.
Với tính toán trước và tối ưu hóa như vậy, khoảng cách giữa hai điểm bất kỳ (ở cách tiếp cận chi tiết của microcluster) có thể được tính toán một cách hiệu quả. Do đó, quá trình phân nhóm có thể được thực hiện theo cách tương tự như thuật toán k-medoids hiệu quả điển hình, bao gồm CLARANS và đạt được chất lượng phân nhóm tốt nhất cho các tập dữ liệu khổng lồ.