PAM(Partitioning Around Medoids)과 같은 고전적인 k-medoids 분할 알고리즘은 소규모 데이터셋에서는 효율적으로 작동하지만, 방대한 규모의 데이터셋에는 적합하지 않습니다. 다행히 샘플링 기반 기법을 활용하면 더 큰 데이터셋도 처리할 수 있는데, 대표적인 방법이 바로 CLARA(Clustering Large Applications)입니다.
CLARA의 접근 방식
CLARA의 핵심 아이디어는 다음과 같습니다. 데이터셋에서 충분히 무작위로 표본을 추출하면, 그 표본은 원본 데이터셋을 충실히 반영하게 됩니다. 따라서 표본에서 선택된 대표 객체(메도이드, medoids)는 전체 데이터셋에서 선택했을 때와 유사한 결과를 보이게 됩니다.
구체적으로 CLARA는 데이터셋에서 여러 개의 표본을 추출하고, 각 표본마다 PAM을 적용한 뒤, 가장 우수한 군집화 결과를 최종 출력으로 반환합니다.
CLARA의 한계
CLARA의 성능은 표본 크기에 크게 좌우됩니다. PAM이 주어진 데이터셋 전체에서 최적의 k개 메도이드를 탐색하는 반면, CLARA는 선택된 표본 범위 안에서만 최적의 메도이드를 찾습니다. 즉, 좋은 표본이 추출되지 않으면 전체 데이터 기준으로는 최적에 못 미치는 결과가 나올 수 있습니다.
CLARANS: 무작위화 검색 기반의 개선 알고리즘
이러한 한계를 보완하기 위해 CLARANS(Clustering Large Applications based upon RANdomized Search)라는 k-medoids 계열 알고리즘이 제안되었습니다. CLARANS는 샘플링 기법과 PAM을 결합하면서도, CLARA가 탐색의 매 단계마다 고정된 표본을 사용하는 것과 달리, 탐색의 모든 단계에서 어느 정도의 무작위성을 가진 표본을 새로 추출합니다.
그래프 탐색 관점에서 본 군집화
군집화 과정은 그래프 탐색으로 해석할 수 있습니다. 그래프의 각 노드는 하나의 잠재적 해답, 즉 k개 메도이드의 집합에 해당합니다. 두 노드의 메도이드 집합이 단 하나의 객체만 다를 경우, 이 둘은 이웃(그래프상 호(arc)로 연결된 관계)이라고 정의합니다. 또한 각 노드에는 비용(cost)이 부여되며, 이 비용은 각 객체와 해당 객체가 속한 클러스터의 메도이드 사이 비유사도(dissimilarity)의 총합으로 표현됩니다.
탐색 과정에서 PAM은 최소 비용 해답을 찾기 위해 현재 노드의 모든 이웃을 평가하고, 비용 감소 폭이 가장 큰 이웃으로 현재 노드를 교체합니다. 반면 CLARA는 전체 데이터셋의 표본 위에서 작동하기 때문에 평가하는 이웃 수가 적고, 탐색 범위도 초기 그래프보다 작은 부분 그래프로 제한됩니다.
CLARANS의 장점과 특징
실험 결과에 따르면 CLARANS는 PAM과 CLARA보다 모두 더 효율적인 성능을 보입니다. 또한 실루엣 계수(silhouette coefficient)를 활용해 가장 '자연스러운' 클러스터 개수를 발견할 수 있습니다. 실루엣 계수는 특정 객체가 자신이 속한 클러스터에 얼마나 실질적으로 속해 있는지를 나타내는 지표입니다. 나아가 CLARANS는 이상치(outlier) 탐지에도 활용할 수 있습니다.
CLARANS의 계산 복잡도는 O(n²)입니다(n은 객체 수). 군집화 품질 역시 사용된 샘플링 방법에 영향을 받습니다. 디스크에 저장된 데이터 객체를 다루는 능력은 R*-tree와 같은 공간 데이터 구조를 탐색하는 기법을 도입함으로써 더욱 향상시킬 수 있습니다.