CURE 클러스터링 알고리즘이란?
CURE(Clustering Using REpresentatives)는 대규모 데이터셋, 이상치(outlier), 비구형(non-spherical) 구조를 가진 군집, 크기가 균일하지 않은 군집까지 효과적으로 처리할 수 있도록 여러 기법을 결합한 클러스터링 알고리즘입니다. CURE는 하나의 중심점만 사용하는 기존 기법과 달리, 각 군집에서 추출한 여러 개의 대표점(representative points)으로 군집을 정의한다는 점에서 차별화됩니다.
대표점 선택 방식
대표점들은 군집의 형태와 구조를 잘 반영하도록 선택됩니다. 첫 번째 대표점은 군집 중심으로부터 가장 먼 점으로 지정되며, 이후의 대표점들은 이미 선택된 모든 점들로부터 가장 멀리 떨어진 점 순서로 선정됩니다. 이러한 방식 덕분에 대표점들이 군집 전반에 고르게 분포될 수 있습니다.
선택하는 대표점의 개수는 사용자가 지정하는 매개변수입니다. 실험 결과에 따르면 일반적으로 10개 이상을 사용했을 때 좋은 성능을 보이는 것으로 알려져 있습니다.
수축 인자(𝛼)를 통한 이상치 영향 완화
대표점들이 선택된 후에는 수축 인자(shrinkage factor) 𝛼를 적용하여 군집 중심 방향으로 일정 비율만큼 당겨집니다. 이 과정은 이상치의 영향을 완화하는 데 도움이 됩니다. 이상치는 일반적으로 중심에서 멀리 떨어져 있기 때문에 상대적으로 더 많이 수축되기 때문입니다.
예를 들어, 중심에서 10단위 떨어진 대표점은 𝛼 = 0.7인 경우 3단위만큼 이동하고, 중심에서 1단위 떨어진 대표점은 0.3단위만 이동합니다.
두 단계의 이상치 제거
CURE는 계층적 군집화 과정의 특성을 활용하여 군집화 단계에서 두 시점에 걸쳐 이상치를 제거합니다.
첫 번째 제거 단계: 어떤 군집의 크기가 느리게 증가한다면, 그 군집이 대부분 이상치로 구성되어 있을 가능성이 높습니다. 이상치는 정의상 다른 데이터들과 멀리 떨어져 있어 다른 점들과 자주 병합되지 않기 때문입니다. CURE에서 이 첫 번째 이상치 제거는 일반적으로 군집 수가 초기 데이터 포인트 수의 1/3이 되는 시점에 수행됩니다.
두 번째 제거 단계: 군집 수가 원하는 최종 군집 수 K 수준에 가까워질 때 수행됩니다. 이 시점에서 크기가 지나치게 작은 군집들을 이상치로 판단하여 제거합니다.
계산 복잡도와 속도 개선 기법
CURE의 최악의 경우 시간 복잡도는 O(m²logm)로, 이를 그대로 대규모 데이터셋에 적용하기는 어렵습니다. 이를 해결하기 위해 CURE는 군집화 과정의 속도를 높이는 두 가지 방법을 사용합니다.
첫 번째 방법 — 무작위 샘플링: 데이터셋에서 무작위 표본을 추출한 뒤, 샘플링된 데이터 포인트에 대해 계층적 군집화를 수행합니다. 이후 마지막 패스(final pass)를 통해 나머지 모든 데이터 포인트를 가장 가까운 대표점을 가진 군집에 할당합니다.
두 번째 방법 — 파티션 기반 사전 군집화: 경우에 따라 필요한 샘플의 크기가 너무 커서 추가적인 기법이 필요할 수 있습니다. 이때 CURE는 샘플 데이터를 여러 파티션으로 나누고, 각 파티션 내의 점들을 개별적으로 군집화합니다(사전 군집화). 이후 중간 군집들에 대한 군집화를 진행하고, 마지막 패스를 통해 데이터셋의 모든 점을 최종 군집에 할당합니다.