확장 가능한 랜덤 바이닝 특성을 이용한 스펙트럼 클러스터링

스펙트럼 클러스터링은 데이터에서 숨겨진 클러스터 구조를 포착하는 가장 효과적인 클러스터링 접근법 중 하나입니다. 그러나 유사성 그래프를 구성하고 후속 고유값 분해를 계산하는 과정에서 이차 복잡도를 가지기 때문에 대규모 문제에 잘 확장되지 않습니다. 스펙트럼 클러스터링을 가속화하기 위한 여러 방법이 제안되었지만, 대부분의 방법은 계산상의 병목 현상을 줄이는 대신 원래 데이터의 상당한 정보 손실을 감수해야 합니다. 본 논문에서는 유사성 그래프 구성과 고유값 분해를 동시에 가속화하기 위해 랜덤 바이닝 특징(Random Binning features, RB)을 사용한 새로운 확장 가능한 스펙트럼 클러스터링 방법을 제시합니다. 구체적으로, RB로 생성된 큰 희소 특징 행렬의 내적을 통해 그래프 유사성(커널) 행렬을 암시적으로 근사합니다. 그런 다음 최신 SVD 솔버를 도입하여 이 큰 행렬의 고유벡터를 효율적으로 계산하여 스펙트럼 클러스터링을 수행합니다. 이러한 두 가지 구성 요소를 사용하여 데이터 포인트 수에 대한 계산 비용을 이차에서 선형으로 줄이면서 유사한 정확도를 달성할 수 있습니다. 우리의 이론적 분석은 RB를 통한 스펙트럼 클러스터링이 표준 랜덤 특징 근사보다 더 빠르게 정확한 스펙트럼 클러스터링에 수렴함을 보여줍니다. 8개 벤치마크에 대한 광범위한 실험 결과는 제안된 방법이 정확도와 실행 시간 측면에서 기존 최신 방법들을 능가하거나 일치함을 입증하였습니다. 또한, 우리의 방법은 데이터 샘플 수와 RB 특징 수 모두에서 선형 확장성을 보입니다.