ROCK 알고리즘의 정의
ROCK은 '링크를 활용한 견고한 군집화(Robust Clustering using Links)'의 약자로, 계층적 군집화(hierarchical clustering) 알고리즘의 하나입니다. 이 알고리즘은 범주형(categorical) 속성을 가진 데이터를 대상으로, 두 객체 간 공통 이웃 수를 의미하는 '링크(link)' 개념을 분석합니다. 단순한 거리 기반 측정만으로는 범주형 데이터를 고품질의 클러스터로 묶기 어렵다는 점을 보여준 것이 ROCK의 핵심 기여입니다.
기존 군집화 방식의 한계
대부분의 군집화 알고리즘은 군집화 과정에서 지점 간 유사도만 고려하는 '국소적(localized)' 접근 방식을 취합니다. 즉, 매 단계에서 서로 유사한 점들을 하나의 클러스터로 병합하는데, 이러한 방식은 오류에 취약합니다. 예를 들어, 서로 다른 두 클러스터가 소수의 점이나 이상치(outlier) 때문에 가까워 보일 수 있습니다. 이 경우 점 간 유사도에만 의존하여 군집화를 결정하면, 본래 분리되어야 할 두 클러스터가 잘못 병합될 위험이 있습니다.
전역적 관점의 접근
ROCK은 점들의 이웃(neighborhood)까지 함께 고려하는 보다 전역적(global)인 방식으로 군집화를 수행합니다. 두 점이 유사할 뿐만 아니라 주변 이웃 구조마저 비슷하다면, 이 두 점은 같은 클러스터에 속할 가능성이 높다고 판단하여 병합할 수 있습니다.
이웃과 링크의 수학적 정의
두 점 pi와 pj는 sim(pi, pj) ≥ θ를 만족할 때 서로 이웃이라고 정의합니다. 여기서 sim은 유사도 함수(similarity function)이며, θ는 사용자가 지정하는 임계값(threshold)입니다. sim은 거리 척도(distance metric)로 선택할 수도 있고, 값이 0과 1 사이로 정규화되어 값이 클수록 두 점이 더 유사함을 나타내는 비계량(nonmetric) 함수일 수도 있습니다.
pi와 pj 사이의 링크 수는 두 점이 공유하는 공통 이웃의 개수로 정의됩니다. 두 점 사이의 링크 수가 많을수록 같은 클러스터에 속할 가능성이 높습니다. 개별 점들 간의 관계에서 이웃 데이터 포인트를 함께 고려하기 때문에, 점 간 유사도에만 초점을 맞추는 표준 군집화 방법보다 ROCK이 더 강력한 성능을 발휘합니다.
예시: 장바구니(market basket) 데이터
범주형 속성을 가진 데이터의 대표적인 예가 시장 장바구니(market basket) 정보입니다. 이러한 데이터는 거래(transaction) 데이터베이스로 구성되며, 각 거래는 상품(item)들의 집합입니다. 거래는 불리언(Boolean) 속성을 가진 데이터로 취급되며, 각 속성은 빵이나 치즈와 같은 개별 상품에 해당합니다.
거래 데이터에서 특정 상품에 해당하는 속성은 그 거래에 해당 상품이 포함되어 있으면 참(true), 아니면 거짓(false)이 됩니다. 이와 같은 방식으로 범주형 속성을 가진 다양한 데이터셋을 처리할 수 있습니다. 두 '점', 즉 거래 Ti와 Tj 사이의 이웃 및 링크 개념은 자카드 계수(Jaccard coefficient)를 통해 다음과 같이 표현됩니다.
$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$$
ROCK의 작동 방식
ROCK은 먼저 유사도 임계값과 공통 이웃 개념을 활용하여 주어진 데이터 유사도 행렬로부터 희소 그래프(sparse graph)를 생성합니다. 그런 다음 이 희소 그래프 위에서 응집형 계층 군집화(agglomerative hierarchical clustering)를 수행합니다. 군집화 결과는 군집 적합도(goodness measure)를 통해 평가하며, 대규모 데이터셋으로 확장할 때는 무작위 샘플링(random sampling) 기법을 활용할 수 있습니다.
시간 복잡도
ROCK의 최악의 경우 시간 복잡도는 O(n2 + nmmma + n2log n)입니다. 여기서 mm과 ma는 각각 최대 이웃 수와 평균 이웃 수를, n은 객체의 수를 나타냅니다.