PROCLUS의 개요
PROCLUS는 Projected Clustering(투영 클러스터링)의 약자로, 널리 사용되는 차원 축소 기반 부분공간(subspace) 클러스터링 기법입니다. 개별 저차원 공간에서 출발하는 대신, 고차원 속성 공간 전체에서 클러스터의 초기 근사치를 먼저 찾는 것이 특징입니다.
각 클러스터에는 차원별 가중치가 부여되며, 갱신된 가중치는 다음 반복 단계에서 클러스터를 재구성하는 데 활용됩니다. 이러한 방식 덕분에 적절한 차원 수를 가진 모든 부분공간에서 밀집 영역을 탐색할 수 있고, 낮은 차원의 투영 공간에서 과도하게 많은 중복 클러스터가 생성되는 문제를 방지할 수 있습니다.
핵심 메커니즘
PROCLUS는 CLARANS에서 사용되는 것과 유사한 hill-climbing 방식으로 최적의 medoid 집합을 탐색하지만, 이를 투영 클러스터링에 맞게 일반화하여 적용합니다. 또한 적절한 차원 집합에 대한 맨해튼 거리로 정의되는 맨해튼 구분 거리(Manhattan segmental distance)라는 거리 측정 방식을 채택합니다.
PROCLUS 알고리즘의 3단계 프로세스
PROCLUS 알고리즘은 초기화(initialization), 반복(iteration), 클러스터 정제(cluster refinement)의 세 단계로 구성됩니다.
1. 초기화 단계
초기화 단계에서는 탐욕(greedy) 알고리즘을 사용하여 서로 멀리 떨어진 초기 medoid 집합을 선택합니다. 이를 통해 선택된 집합 안에 최소 하나 이상의 객체가 각 클러스터를 정의하도록 보장합니다.
구체적으로는, 생성해야 할 클러스터 수에 비례하는 데이터 포인트의 무작위 샘플을 먼저 추출한 뒤, 탐욕 알고리즘을 통해 더 작은 최종 부분집합을 얻어 다음 단계에 사용합니다.
2. 반복 단계
반복 단계에서는 축소된 medoid 집합에서 k개의 medoid를 무작위로 선택하고, 클러스터링 품질이 향상되는 경우 '나쁜(bad)' medoid를 무작위로 선정한 새로운 medoid로 교체합니다.
또한 각 medoid에 대해 평균 거리가 수학적 기대값보다 작은 차원들의 집합을 선택합니다. medoid와 관련된 차원의 총 수는 k×l이며, 여기서 l은 클러스터 부분공간의 평균 차원 수를 결정하는 입력 매개변수입니다.
3. 클러스터 정제 단계
정제 단계에서는 발견된 클러스터를 기반으로 각 medoid에 대한 새로운 차원 집합을 계산하고, 데이터 포인트를 medoid에 재할당하며, 이상치(outlier)를 제거합니다. PROCLUS는 고차원 클러스터를 발견하는 데 있어 효과적이면서도 확장 가능한 방법임이 입증되어 있습니다.
CLIQUE와의 비교
CLIQUE가 다수의 중복 클러스터를 출력하는 것과 달리, PROCLUS는 데이터 포인트들의 비중복(non-overlapped) 분할을 찾습니다. 따라서 발견된 클러스터는 고차원 데이터를 더 깊이 이해하는 데 도움을 주며, 이후의 후속 분석에도 유용하게 활용될 수 있습니다.
한편 CLIQUE는 고밀도 클러스터가 유지되는 가장 높은 차원의 부분공간을 반드시 찾아낸다는 장점이 있습니다. 입력 객체의 순서에 영향을 받지 않고, 특정 정준(canonical) 데이터 분포를 가정하지 않으며, 입력 크기에 대해 선형적으로 확장됩니다. 또한 데이터의 차원 수가 증가하더라도 우수한 확장성을 유지합니다.