PAM과 같은 고전적인 k-medoid 분할 알고리즘은 작은 데이터 세트에서는 효율적으로 작동하지만 거대한 데이터 세트에서는 잘 확장되지 않습니다. 더 높은 데이터 세트를 처리할 수 있으며 CLARA(Clustering Large Applications)로 알려진 샘플링 기반 방법을 사용할 수 있습니다.
CLARA의 접근 방식은 다음과 같습니다. 샘플이 상당히 무작위로 선택된 경우 원본 데이터 세트를 밀접하게 정의해야 합니다. 선택된 대표 객체(medoids)는 전체 데이터 세트에서 선택되었을 객체와 유사합니다. CLARA는 데이터 세트의 여러 샘플을 추출하고 각 샘플에 PAM을 적용하고 최상의 클러스터링을 출력으로 반환합니다.
CLARA의 성능은 샘플 크기를 기반으로 합니다. PAM은 주어진 데이터 세트 사이에서 가장 좋은 k개의 메도이드를 검색하는 반면, CLARA는 데이터 세트의 선택된 샘플 사이에서 가장 좋은 k개의 메도이드를 검색하는 것으로 관찰됩니다. CLRANS(Clustering Large Applications 의존 RANdomized Search)로 알려진 k-medoids 유형 알고리즘이 제안되었습니다. 샘플링 방법을 PAM과 연결할 수 있습니다. CLARA는 검색의 모든 단계에서 고정된 샘플을 가지고 있지만 CLARANS는 검색의 모든 단계에서 임의의 샘플을 그립니다.
클러스터링 절차는 각 노드가 가능한 솔루션(k개의 medoids 집합)인 그래프를 통한 검색으로 볼 수 있습니다. 두 노드는 집합이 하나의 개체만 다른 경우 이웃(특히 그래프에서 호로 연결된)입니다. 각 노드에는 각 개체와 해당 클러스터의 메도이드 간의 총 비유사도로 표시되는 비용이 할당될 수 있습니다.
각 단계에서 PAM은 최소 비용 솔루션을 검색할 때 최신 노드의 모든 이웃을 결정합니다. 그런 다음 최신 노드는 비용이 가장 큰 이웃으로 교체됩니다. CLARA는 전체 데이터 세트의 샘플에서 작동하기 때문에 더 적은 수의 이웃을 결정하고 초기 그래프보다 작은 하위 그래프로 검색을 제한합니다.
CLARANS는 PAM 및 CLARA보다 더 효율적인 것으로 실험적으로 입증되었습니다. 개체가 클러스터에 실제로 적용되는 정도를 정의하는 개체의 실루엣 계수 속성을 사용하여 가장 "자연스러운" 클러스터 수를 찾는 데 사용할 수 있습니다. CLARANS는 또한 이상값의 발견을 허용합니다.
CLARANS의 계산 복잡도는 O(n 2 입니다. ) 여기서 n은 개체 수입니다. 또한 클러스터링 품질은 사용된 샘플링 방법을 기반으로 합니다. 디스크에 있는 데이터 개체를 관리하는 CLARANS의 기능은 R* 트리를 포함하여 공간 데이터 구조를 탐색하는 방법에 집중함으로써 더욱 향상될 수 있습니다.