클러스터 분석은 수년 동안 널리 연구되어 온 통계의 한 분야입니다. 이 기술을 사용하는 이점은 개념 계층과 같은 배경 지식을 활용하지 않고도 데이터에서 흥미로운 구조 또는 클러스터를 직접 발견할 수 있다는 것입니다.
PAM 또는 CLARA와 같은 통계에 사용되는 클러스터링 알고리즘은 계산 복잡성 관점에서 비효율적인 것으로 보고됩니다. 효율성 문제에 따라 클러스터 분석을 위해 CLARANS(무작위 검색 기반 클러스터링 대형 애플리케이션)라는 새로운 알고리즘이 개발되었습니다.
PAM(메도이드 주변 분할) − n개의 객체가 있다고 가정하고, PAM은 먼저 각 클러스터에 대한 대표 객체를 찾아 k개의 클러스터를 찾습니다. 클러스터의 중앙에 위치한 이러한 대표자를 메도이드라고 합니다.
k개의 medoids를 선택한 후 알고리즘은 한 객체는 medoid이고 다른 객체는 그렇지 않도록 가능한 모든 객체 쌍을 분석하여 최상의 medoids 선택을 생성하려고 반복적으로 시도합니다. 클러스터링 품질의 측정값은 이러한 각 조합에 대해 계산됩니다.
한 번의 반복에서 좋은 점을 선택하면 다음 반복의 메도이드로 선택됩니다. 단일 반복의 비용은 O(k(n−k) 2 입니다. ) . 따라서 n과 k의 큰 값에 대해 계산적으로 매우 비효율적입니다.
CLARA(대규모 애플리케이션 클러스터링) − PAM 알고리즘과 CLARA 알고리즘의 차이점은 다음과 같은 알고리즘이 샘플링 기반이라는 점입니다. 실제 데이터의 작은 영역만 데이터의 대표로 선택되고 PAM을 사용하여 이 샘플에서 medoids가 선택됩니다.
아이디어는 샘플이 상당히 무작위적인 방식으로 선택되면 전체 데이터 세트를 올바르게 나타내므로 선택된 대표 개체(medoids)가 전체 데이터 세트에서 선택된 것처럼 유사하다는 것입니다.
CLARA는 여러 샘플을 추출하고 이 샘플에서 좋은 클러스터링을 출력합니다. CLARA는 PAM보다 높은 데이터 세트를 처리할 수 있습니다. 각 반복의 복잡성은 이제 O(kS 2 가 됩니다. +k(n−k)), 여기서 S는 샘플의 크기입니다.
CLRANS(무작위 검색 기반 대규모 애플리케이션 클러스터링) − CLARANS 알고리즘은 데이터 세트의 하위 집합만 검색하여 PAM과 CLARA를 결합하며 주어진 시간에 일부 샘플에 제한되지 않습니다. CLARA는 검색의 각 단계에서 일정한 샘플을 가지고 있지만 CLARANS는 검색의 모든 단계에서 임의의 샘플을 그립니다.
클러스터링 단계는 각 노드가 가능한 솔루션, 즉 k 개의 medoids 집합인 그래프를 검색하는 것으로 표시될 수 있습니다. 단일 메도이드를 교체하여 얻은 클러스터링을 현재 클러스터링의 이웃이라고 합니다.