Clustering - Spectral Clustering

Spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions

KNN 그래프를 생성하여 데이터의 특징을 파악한 뒤 성능이 좋은 클러스터를 생성해주는 방법이다
대표적인 Graph Clustering 기법이다 (묶이는 대상이 subgraph)

Algorithm

이미지 출처: https://pizzathief.oopy.io/spectral-clustering

• 주어진 데이터를 그래프 모델로 해석하여, subgraph로 데이터를 나누는 것으로 묶어준다
• 각 데이터를 노드로 두고, 각 데이터로부터 e(입실론)보다 가까운 거리에 있는 노드들을 연결한 KNN Graph를 만든다
• 만든 그래프가 가장 잘 나눠지는 곳을 찾아 그래프를 2분할한다
• 원하는 개수의 클러스터(subgraph)가 생길 때까지 그래프를 분리한다
  (만약 원하는 클러스터가 5개라면 4번 분할)

장단점

장점

• 기존 공간에 구애받지 않고 데이터를 그래프 구조로 파악한다 (성능이 괜찮음)

단점

• KNN Graph를 만들고 min-cut을 찾는데에 시간이 오래 걸린다(O(N^3))