물리적 또는 추상적인 객체들의 집합을 서로 유사한 객체들끼리의 클래스로 묶는 과정을 클러스터링(군집화)이라고 합니다. 하나의 클러스터는 동일한 클러스터 내부에서는 서로 유사하고, 다른 클러스터의 객체들과는 상이한 데이터 객체들의 집합을 의미합니다. 여러 응용 분야에서 데이터 객체의 클러스터는 하나의 그룹으로 간주될 수 있으며, 군집 분석은 인간에게 매우 본질적인 활동 중 하나입니다.
클러스터링은 아웃라이어(outlier, 이상치)를 식별하는 데에도 유용합니다. 유사한 값들은 클러스터로 조직화되며, 어떤 클러스터에도 속하지 않는 값들은 아웃라이어로 분류됩니다. 클러스터링 기법은 데이터 튜플을 객체로 취급하며, 이 객체들을 그룹 또는 클러스터로 분할합니다. 이때 동일한 클러스터 내부의 객체들은 서로 '유사'하고, 다른 클러스터의 객체들과는 '상이'해야 합니다. 일반적으로 거리 함수(distance function)를 기준으로 공간상에서 객체들이 얼마나 '가까운지'를 통해 유사성을 정의합니다.
그래프 기반 클러스터링에는 다음과 같은 다양한 접근 방식이 있습니다.
1. 근접 그래프의 희소화(Sparsification)
근접 그래프(proximity graph)를 희소화하여 객체와 가장 가까운 이웃들 사이의 연결만 유지하는 방식입니다. 이러한 희소화는 노이즈와 아웃라이어를 처리하는 데 효과적이며, 희소 그래프(sparse graph)를 위해 개발된 고성능 그래프 분할 알고리즘을 활용할 수 있게 해줍니다.
2. 최근접 이웃 기반 유사도 측정
두 객체가 공유하는 최근접 이웃(nearest neighbors)의 수를 바탕으로 두 객체 간의 유사도를 정의할 수 있습니다. 한 객체와 그 객체의 가장 가까운 이웃들은 대체로 같은 클래스에 속한다는 관찰에 기반한 이 방식은, 고차원 문제와 밀도가 변화하는 클러스터 문제를 해결하는 데 유용합니다.
3. 코어 객체 중심의 밀도 기반 클러스터링
코어(core) 객체를 정의하고 그 주변으로 클러스터를 형성하는 방식입니다. 그래프 기반 클러스터링에서는 근접 그래프 또는 희소화된 근접 그래프를 기반으로 밀도(density) 개념을 도입하는 것이 필수적입니다. DBSCAN과 마찬가지로 코어 객체를 중심으로 클러스터를 구축하면 다양한 모양과 크기를 가진 클러스터를 발견할 수 있는 군집화 방식을 만들 수 있습니다.
4. 정교한 클러스터 병합 판단
근접 그래프의 데이터를 활용하면 두 클러스터를 병합해야 하는지 여부를 더욱 정교하게 계산할 수 있습니다. 특히, 병합된 결과 클러스터가 기존 두 클러스터와 유사한 특성을 가질 경우에만 두 클러스터를 병합하는 방식입니다.
5. MST와 Opossum
근접 그래프의 희소화에서 출발하여, 이 접근 방식에 기반한 클러스터링 기법의 두 가지 대표 사례를 살펴볼 수 있습니다. 단일 연결(single link) 클러스터링 알고리즘과 유사한 MST(최소 신장 트리) 기반 기법과 Opossum이 그 예입니다.
6. SNN 유사도와 Jarvis-Patrick 알고리즘
클러스터를 병합할지 여부를 결정하기 위해 자기 유사성(self-similarity) 개념이 필요한 계층적 군집화 알고리즘도 있습니다. 새로운 유사도 측정 방법인 SNN(Shared Nearest Neighbor, 공유 최근접 이웃) 유사도를 정의하고, 이 유사도를 활용하는 Jarvis-Patrick 클러스터링 알고리즘을 학습할 수 있습니다.