Clustering - 스펙트럴 클러스터링
스펙트럴 클러스터링(Spectral Clustering)은 그래프 이론과 선형 대수를 활용하여 데이터를 클러스터링하는 기법이다. 이 방법은 고유값(eigenvalues)과 고유벡터(eigenvectors)를 사용하여 데이터의 구조적 특성을 파악하고, 이를 기반으로 클러스터링을 한다.
스펙트럼의 정의
스펙트럼은 행렬 A의 모든 고유값의 집합을 의미한다.
그래프 라플라시안의 스펙트럼
그래프 이론에서 라플라시안 행렬의 고유값과 고유벡터는 그래프의 클러스터링, 커뮤니티 구조, 연결성 등을 분석하는 데 사용된다
라플라시안 행렬 \(L\)의 고유값
- 첫 번째 고유값 \(\lambda_0\)항상 0이다. 이 고유값에 대응하는 고유벡터는 모든 요소가 동일한 값인 벡터이다 (예: [1, 1, 1, \(\dots\)]).
- 두 번째 고유값 \(\lambda_1\)
Fiedler 값이라고도 하며, 이 값이 작을수록 그래프가 잘 클러스터링된 구조를 가진다. 이 고유값에 대응하는 고유벡터(Fiedler 벡터)는 그래프를 두 개의 클러스터로 나누는 최적의 방법을 제공한다.
관련포스트 라플라시안 행렬의 Fiedler Value - 나머지 작은 고유값들
이 값들과 그에 대응하는 고유벡터들도 그래프의 클러스터 구조를 나타내는 데 유용하다.
스펙트럴 클러스터링의 단계
- Constructing the Similarity Graph
데이터 포인트들을 노드, 노드 간의 유사성을 엣지로 표현한 그래프를 만든다. 유사성 그래프는 보통 인접 행렬 \(A\)로 표현된다.
유사성 그래프를 구성하는 방법:- k-nearest neighbors graph: 각 노드를 그 노드와 가장 가까운 k개의 노드에 연결한다
- Fully connected graph: 모든 노드를 서로 연결한다. 엣지 가중치는 유사성 함수(예: Gaussian kernel)를 사용하여 계산한다
- ε-neighborhood graph: 거리가 ε 이하인 노드들을 연결한다
- Computing the Laplacian Matrix
유사성 그래프의 라플라시안 행렬을 계산한다. 일반적인 라플라시안 행렬 \(L\), 정규화된 라플라시안 행렬 \(L_{\text{sym}}\) 또는 랜덤워크 라플라시안 행렬 \(L_{\text{rw}}\) 중 하나를 선택할 수 있다. 일반적으로 정규화된 라플라시안 행렬 \(L_{\text{sym}}\)을 사용한다. 관련포스트 라플라시안 행렬 - Computing Eigenvalues and Eigenvectors
라플라시안 행렬의 가장 작은 \(k\)개의 고유값과 대응하는 고유벡터를 계산한다. - Clustering the Rows of U
\(U\)는 가장 작은 \(k\)개의 고유값과 대응하는 고유벡터를 열로 갖는 행렬로 \(n \times k\) 크기의 행렬이다( \(n\)은 데이터 포인트의 수)
\(U\)의 각 행을 데이터 포인트로 간주하고, 이를 \(\mathbb{R}^k\) 공간에서 클러스터링한다.
작은 고유값에 대응하는 고유벡터들은 데이터 포인트 간의 유사성을 반영하여 저차원 공간에서 클러스터링을 수행할 수 있게 한다
이는 고차원의 데이터에서 주요 정보만을 유지하면서 계산 효율성을 높이고 노이즈에 덜 민감하게 클러스터를 식별할 수 있다. - Assigning Original Points to Clusters
\(U\)의 행 클러스터링 결과를 바탕으로 원래 데이터 포인트에 클러스터를 할당한다.
예시
\[ L = \begin{bmatrix}2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{bmatrix} \]
고유값: \( \lambda_0 = 0 \), \( \lambda_1 \approx 1 \), \( \lambda_2 \approx 3 \), \( \lambda_3 \approx 4 \)
고유벡터: \( \quad \mathbf{v}_0 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \end{bmatrix} \)
가장 작은 두 개의 고유값 \(\lambda_0\)와 \(\lambda_1\)에 대응하는 고유벡터 \(\mathbf{v}_0\)과 을 선택하여 행렬 \(U\)를 구성하고 행렬 \( U \) 행을 클러스터링한다.
\( \quad U = \begin{bmatrix}1 & 1 \\ 1 & 1 \\ 1 & -1 \\ 1 & -1 \end{bmatrix} \)