m개의 데이터 포인트에 대한 m×m 근접 행렬(proximity matrix)은 하나의 밀집 그래프(dense graph)로 정의할 수 있습니다. 이 그래프에서 각 노드는 다른 노드들과 연결되어 있으며, 노드 그룹 사이의 엣지(edge) 가중치는 해당 노드 쌍의 근접도(pairwise proximity)를 따릅니다. 모든 객체가 서로에 대해 어떤 방식으로든 유사성을 지니지만, 대부분의 데이터셋에서 객체들은 소수의 객체와만 매우 유사하고 나머지 대다수 객체와는 약한 유사성만 보입니다.
이러한 특성을 활용하면 실제 클러스터링 과정을 시작하기 전에 유사도가 낮은(비유사도가 높은) 값들을 0으로 설정함으로써 근접 그래프(행렬)를 희소화할 수 있습니다. 희소화는 예를 들어 정의된 임계값 미만(초과)의 유사도(비유사도)를 가진 모든 링크를 제거하는 방식, 또는 각 점의 k개 최근접 이웃에 대한 링크만 유지하는 방식으로 구현할 수 있습니다. 후자의 방법으로 만들어진 그래프를 k-최근접 이웃 그래프(k-nearest neighbor graph)라고 부릅니다.
희소화의 주요 이점
1. 데이터 크기 감소
클러스터링을 위해 처리해야 하는 데이터의 양이 크게 줄어듭니다. 희소화를 통해 근접 행렬 내 항목의 99% 이상을 제거할 수 있으며, 이에 따라 처리 가능한 문제의 규모가 확대됩니다.
2. 클러스터링 성능 향상
희소화 기법은 객체의 가장 가까운 이웃들과의 연결은 유지하면서, 상대적으로 거리가 먼 객체들과의 연결은 제거합니다. 이는 '객체의 최근접 이웃들은 객체 자신과 동일한 클래스(클러스터)에 속한다'는 최근접 이웃 원칙(nearest neighbor principle)과 일치합니다. 그 결과 노이즈와 이상치(outlier)의 영향이 줄어들고 클러스터 간의 구분이 더욱 명확해집니다.
3. 그래프 분할 알고리즘 활용 가능
희소 그래프의 최소 컷(min-cut) 분할을 찾기 위한 휴리스틱 알고리즘에 관한 연구가 활발히 진행되어 왔으며, 특히 병렬 컴퓨팅과 집적 회로 설계 분야에서 두드러집니다. 근접 그래프를 희소화하면 클러스터링 단계에서 그래프 분할 알고리즘을 활용할 수 있습니다. 실제로 Opossum과 Chameleon과 같은 클러스터링 알고리즘은 그래프 분할을 필요로 합니다.
희소화와 클러스터링 알고리즘의 관계
근접 그래프의 희소화는 실제 클러스터링 알고리즘을 적용하기 전에 수행하는 사전 단계로 간주되어야 합니다. 이상적인 희소화라면 근접 행렬이 원하는 클러스터에 해당하는 연결 요소(connected components)로 분리되겠지만, 실제로는 그렇게 깔끔하게 나누어지지 않습니다.
실제 환경에서는 하나의 엣지가 서로 다른 두 클러스터를 연결하거나, 하나의 클러스터가 여러 개의 비연결 하위 클러스터로 나뉘는 경우가 발생합니다. 실제로 Jarvis-Patrick이나 SNN처럼 밀도 기반 클러스터링을 사용하는 경우, 희소 근접 그래프를 변형하여 새로운 근접 그래프를 만들어내며, 이 새로운 근접 그래프 역시 다시 희소화될 수 있습니다. 최종적으로 클러스터링 알고리즘은 이러한 모든 전처리 과정을 거친 결과물인 근접 그래프를 대상으로 작동합니다.