초록
스펙트럴 클러스터링은 비볼록이고 교차하지 않는 매니폴드를 효과적으로 분리할 수 있다는 점에서 많은 주목을 받았으나, 높은 계산 복잡도로 인해 적용 가능성이 크게 제한되어 왔다. Dhillon(2001)의 문서-단어 공동 클러스터링 프레임워크에 영감을 받아, 기준점(landmark) 기반의 확장 가능한 스펙트럴 클러스터링 방법을 제안한다. 본 방법은 먼저 선택된 기준점 집합과 주어진 데이터를 이용하여 이분 그래프(bipartite graph)를 구성하고, 이를 기반으로 확산 과정(diffusion process)을 수행하여 클러스터링을 위한 일련의 확산 좌표(diffusion coordinates)를 도출한다. 제안하는 알고리즘이 주어진 데이터와 선택된 기준점 간의 유사도 행렬(affinity matrix)에 대해 매우 효율적인 연산만으로 구현 가능함을 보이며, 대규모 데이터 처리에도 적합함을 입증한다. 마지막으로, 여러 벤치마크 데이터셋에서 최신의 확장 가능한 알고리즘들과의 비교를 통해 본 방법의 뛰어난 성능을 실험적으로 확인하였다.