클러스터 분석이란?
클러스터 분석(Cluster Analysis)은 오랫동안 폭넓게 연구되어 온 통계학의 한 분야입니다. 이 기법의 가장 큰 장점은 개념 계층(concept hierarchy)과 같은 사전 배경 지식 없이도 데이터 자체에서 흥미로운 구조나 클러스터를 직접 발견할 수 있다는 점입니다.
다만 통계학에서 사용되는 PAM이나 CLARA 같은 클러스터링 알고리즘은 계산 복잡도 측면에서 비효율적이라는 지적을 받아 왔습니다. 이러한 효율성 문제를 해결하기 위해 CLARANS(Clustering Large Applications based upon Randomized Search)라는 새로운 알고리즘이 개발되었습니다.
PAM (Partitioning around Medoids)
n개의 객체가 있다고 가정할 때, PAM은 각 클러스터의 대표 객체를 먼저 찾는 방식으로 k개의 클러스터를 형성합니다. 이 대표 객체는 클러스터의 중심에 위치한 점으로, '메도이드(medoid)'라고 불립니다.
k개의 메도이드를 선택한 후, 알고리즘은 한 객체는 메도이드이고 다른 하나는 메도이드가 아닌 모든 가능한 객체 쌍을 분석하며 가장 최적의 메도이드 조합을 반복적으로 탐색합니다. 이때 각 조합마다 클러스터링 품질의 척도를 계산합니다.
한 번의 반복에서 가장 좋은 선택으로 판명된 점들이 다음 반복의 메도이드로 선정됩니다. 단일 반복의 비용은 O(k(n−k)2)이므로, n과 k의 값이 커질수록 계산상 상당히 비효율적이라는 한계가 있습니다.
CLARA (Clustering Large Applications)
PAM과 CLARA의 핵심적인 차이점은 CLARA가 샘플링에 기반한다는 것입니다. 실제 데이터 중 작은 부분만 샘플로 선택하여 전체 데이터를 대표하게 하고, PAM을 이용해 이 샘플로부터 메도이드를 선정합니다.
여기서 핵심 아이디어는, 샘플이 무작위로 적절하게 추출되었다면 전체 데이터셋을 올바르게 대표할 수 있고, 따라서 선택된 대표 객체(메도이드)도 전체 데이터셋에서 직접 선택한 것과 유사한 결과를 얻을 수 있다는 것입니다.
CLARA는 여러 개의 샘플을 추출한 뒤, 이 샘플들 중 가장 우수한 클러스터링 결과를 출력합니다. 덕분에 CLARA는 PAM보다 훨씬 큰 데이터셋을 처리할 수 있으며, 각 반복의 복잡도는 O(kS2+k(n−k))가 됩니다. 여기서 S는 샘플의 크기를 의미합니다.
CLARANS (Clustering Large Applications based upon RANdomized Search)
CLARANS 알고리즘은 PAM과 CLARA의 장점을 결합한 방식으로, 데이터셋의 부분 집합만을 검색하되 어느 시점에도 특정 샘플에 국한되지 않습니다. CLARA가 검색의 각 단계에서 고정된 샘플을 사용하는 반면, CLARANS는 검색의 매 단계마다 무작위성을 가진 샘플을 새로 추출합니다.
클러스터링 과정은 그래프 탐색 문제로 표현할 수 있으며, 그래프의 각 노드는 하나의 가능한 해, 즉 k개의 메도이드 집합에 해당합니다. 이때 하나의 메도이드를 교체하여 얻은 클러스터링을 현재 클러스터링의 '이웃(neighbor)'이라고 부릅니다.