초대규모 스펙트럼 클러스터링 및 앙상블 클러스터링

본 논문은 제한된 자원을 가진 극단적으로 대규모 데이터셋에 대한 스펙트럼 클러스터링의 확장성과 견고성을 중점적으로 다룹니다. 두 가지 새로운 알고리즘이 제안되며, 이는 초확장 스펙트럼 클러스터링(Ultra-Scalable Spectral Clustering, U-SPEC)과 초확장 앙상블 클러스터링(Ultra-Scalable Ensemble Clustering, U-SENC)입니다. U-SPEC에서는 희소 친화도 부분 행렬을 구성하기 위해 하이브리드 대표 선택 전략과 K-최근접 대표자에 대한 빠른 근사 방법이 제안됩니다. 희소 부분 행렬을 이분 그래프로 해석하여, 효율적으로 그래프를 분할하고 클러스터링 결과를 얻기 위해 전송 절단(Transfer Cut)이 활용됩니다. U-SENC에서는 여러 개의 U-SPEC 클러스터링기가 앙상블 클러스터링 프레임워크에 통합되어 U-SPEC의 견고성을 강화하면서 높은 효율성을 유지합니다. 여러 U-SPEC을 통해 앙상블 생성을 기반으로 객체와 기본 클러스터 사이에서 새로운 이분 그래프가 구성되고, 이를 효율적으로 분할하여 합의 클러스터링 결과를 도출합니다. 주목할 만한 점은 U-SPEC과 U-SENC 모두 거의 선형 시간 복잡도와 공간 복잡도를 가지고 있으며, 64GB 메모리를 가진 PC에서 수백만 단위의 비선형 분리 가능 데이터셋을 견고하고 효율적으로 분할할 수 있다는 것입니다. 다양한 대규모 데이터셋에 대한 실험을 통해 본 알고리즘들의 확장성과 견고성이 입증되었습니다. MATLAB 코드와 실험 데이터는 https://www.researchgate.net/publication/330760669에서 확인할 수 있습니다.