스펙트럼 군집화 (spectral clustering)
쉽게 풀면
점들 사이의 유사도를 간선의 굵기로 삼아 그래프를 만든 뒤, 그 그래프를 가장 약한 지점에서 잘라 덩어리를 나누는 발상입니다. 잘 자르는 방향을 직접 찾는 대신 그래프를 요약한 행렬의 고유벡터를 구해 그 좌표계에 점을 옮기면, 원래는 얽혀 있던 덩어리들이 단순한 모양으로 펼쳐집니다. 그 다음에 흔한 군집화를 적용합니다.
왜 중요한가
초승달 모양이나 동심원처럼 덩어리가 볼록하지 않은 데이터에서 기존 방법이 실패하는 문제를 해결해 줍니다. 이미지 분할, 사회연결망의 공동체 탐지, 유전자 발현 자료 분석 등 유사도 행렬을 자연스럽게 정의할 수 있는 분야에서 널리 쓰입니다. 그래프 이론과 선형대수를 군집화에 연결한 대표 사례이기도 합니다.
논문에서는 이렇게 쓰입니다
덩어리 모양이 단순하지 않은 자료에서 이 방법이 기존 군집화보다 정답 구조를 잘 찾았다는 뜻입니다.
조금 더 깊게 보면
먼저 가우시안 커널 등으로 유사도 행렬을 만들고, 차수 행렬에서 유사도 행렬을 뺀 그래프 라플라시안을 구성합니다. 가장 작은 고유값들에 대응하는 고유벡터 몇 개를 열로 모아 각 점을 저차원 좌표로 표현한 뒤 k-평균 군집화를 적용합니다. 이 절차는 정규화 절단 같은 그래프 분할 목적함수를 연속 완화해서 푸는 것에 해당하며, 라플라시안의 0 고유값 개수가 연결 성분의 수와 같다는 성질이 이론적 근거가 됩니다.
주의할 점
유사도를 정의하는 커널의 폭 같은 설정에 결과가 민감하고, 고유분해 비용 때문에 표본 수가 매우 클 때는 근사 기법이 필요합니다. 계층적 군집분석이 거리 기준으로 순차적으로 묶어 나가는 것과 달리, 이 방법은 그래프 절단이라는 전역적 기준을 한 번에 최적화합니다.