분할 군집화 방법은 집합과 군집 중심 간의 거리를 최소화하기 때문에 바람직합니다. k-means 방법을 선택할 수 있는 경우 장애물이 있는 경우 클러스터 중심을 사용할 수 없습니다.
예를 들어, 클러스터는 호수 중앙에 있는 것으로 판명될 수 있습니다. 즉, k-medoids 방법은 클러스터 내부의 객체를 중심으로 선택하여 문제가 발생하지 않도록 보장합니다.
새로운 medoid가 선택될 때마다 각 객체와 새로 선택된 클러스터 중심 사이의 거리를 다시 계산해야 합니다. 두 객체 사이에 장애물이 있을 수 있기 때문에 두 객체 사이의 거리는 기하학적 계산(예:삼각 측량 포함)을 통해 도출할 수 있습니다.
엄청난 수의 개체와 장애물이 포함된 경우 계산 비용이 높아질 수 있습니다. 장애물이 있는 클러스터링 문제는 그래픽 설명을 사용하여 정의할 수 있습니다. 먼저, p와 q에 인접한 직선이 일부 장애물과 교차하지 않는 경우 영역 R의 다른 점 q에서 점 p가 명확해집니다.
가시성 그래프는 V G =(V, E) 그래프이며 장애물의 각 꼭짓점은 V에 등가 노드가 있고 두 개의 노드 v1이 있습니다. 및 v2 , V에서 정의하는 등가 정점이 서로 보이는 경우에만 E의 가장자리로 결합됩니다.
VG' =(V', E')를 V'에 두 개의 추가 점 p와 q를 삽입하여 VG에서 생성된 가시성 그래프라고 하자. E'는 두 점이 공동으로 보이는 경우 V0에 두 점을 추가하는 가장자리를 포함합니다.
두 세트의 객체 또는 점 사이의 거리 계산 비용을 줄이는 데 사용할 수 있으며 다중 전처리 및 최적화 접근 방식을 사용할 수 있습니다. 하나의 접근 그룹 포인트가 함께 모여 마이크로 클러스터로 되어 있습니다. 이것은 먼저 영역 R을 삼각형으로 삼각 측량한 다음 BIRCH 또는 DBSCAN과 유사한 접근 방식을 사용하여 유사한 삼각형의 인근 지점을 미세 클러스터로 결합하여 완료할 수 있습니다.
단일 포인트 대신 마이크로 클러스터를 처리함으로써 전체 계산이 줄어듭니다. 그 후, 최단 경로의 계산에 따라 두 가지 유형의 조인 인덱스를 구축하기 위해 사전 계산을 구현할 수 있습니다. -
-
일부 장애물 정점 쌍에 대한 VV 인덱스.
-
미세다발과 장애물 정점의 일부 쌍에 대한 MV 인덱스. 색인을 용이하게 하여 전반적인 성능을 최적화하는 데 도움이 됩니다.
이러한 사전 계산 및 최적화를 통해 두 점 사이의 거리(마이크로 클러스터의 세분성 접근 방식)를 효과적으로 계산할 수 있습니다. 따라서 클러스터링 프로세스는 CLARANS를 포함하는 일반적인 효과적인 k-medoids 알고리즘과 유사한 방식으로 구현될 수 있으며 방대한 데이터 세트에 대해 최상의 클러스터링 품질을 얻을 수 있습니다.