Spectral Clustering
27 Apr 2017 | Clustering
이번 글에서는 그래프(graph) 기반 군집화 기법인 Spectral Clustering에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
그래프 인접행렬 구축
Spectral Clustering을 수행하려면 원데이터를 그래프로 변환하기 위해 인접행렬(Adjacency Matrix)을 만들어야 합니다. Spectral Clustering은 무방향 가중치 그래프(Undirected Weighted Graph)를 사용하는데요, 무방향 가중치 그래프와 인접행렬을 직관적으로 비교한 그림은 아래와 같습니다(출처).
원데이터에서 인접행렬을 만들 때는 보통 아래와 같이 가우시안 커널(Gaussian kernel)을 많이 사용합니다. 예컨대 벡터로 표현된 하나의 문서를 노드(node)라고 둘 때, 문서 간 거리가 멀리 떨어져 있을수록(=유사하지 않을수록) 그 가중치는 줄어듭니다. 아울러 가우시안 커널로 만들어진 인접행렬은 대칭행렬입니다.
\[{ W }_{ ij }=exp\left( -\frac { d{ ({ x }_{ i },{ x }_{ j }) }^{ 2 } }{ 2\sigma^{2} } \right)\]
문서를 그래프로 표현하는 방법에 대해서는 이곳을, 가우시안 커널로 인접행렬을 만드는 방법에 대해서는 이곳을 참고하시면 좋을 것 같습니다.
그래프 구축
fully connected graph란 모든 노드가 엣지로 연결돼 있는 그래프를 가리킵니다. ε-neighborhood graph란 거리가 $ε$보다 가까운 엣지들만 살리고 나머지 엣지는 끊어버린 그래프입니다. k-nearest neighbor graph는 각 노드 주변 $k$개 이웃들만 엣지로 연결하고 나머지 엣지는 끊어놓은 그래프입니다.
ε-neighborhood graph는 노드의 밀도가 높은 지역에선 엣지가 지나치게 많이 발생하고, 밀도가 낮은 지역에선 엣지가 하나도 없는 노드가 생길 수 있습니다. k-nearest neighbor graph는 끊기는 노드가 발생하진 않지만, 군집이 극단적으로 멀리 떨어져 있는 경우 군집과 군집 사이는 연결되지 않는 경우가 발생할 수 있습니다.
일반적으로 그래프를 구축할 때는 ε-neighborhood graph를 먼저 구축한 뒤 k-nearest neighbor graph를 적용해 엣지가 전혀 없는 노드도 연결해주는 방식을 씁니다. 그럼에도 불구하고 군집 사이가 너무 멀어서 연결 안되는 경우가 발생할 수 있는데 이럴 때는 minimum spanning tree 방법도 자주 사용됩니다.
그래프 컷 지표
그래프 컷은 그래프를 특정 기준에 의해 두 개 이상의 부그래프(subgraph)로 나누는 것입니다. 이 부그래프가 바로 Spectral Clustering 기법의 학습 결과물인 군집이 됩니다. 아래와 같은 무방향 가중치 그래프가 주어졌다고 합시다.
$Cut(A,B)$는 부그래프 $A$에서 $B$로 향하는 엣지들의 가중치 합입니다. 아래 식과 같습니다.
\[Cut(A,B)=\sum _{ i\in A,j\in B }^{ }{ { w }_{ ij } } =0.3\]
$Cut(A,A)$는 $A$에서 $A$로 향하는 엣지들의, $Cut(B,B)$는 $B$에서 $B$로 향하는 엣지들의 가중치 합입니다.
\[Cut(A,A)=\sum _{ i\in A,j\in A }^{ }{ { w }_{ ij } } =2.2\]
\[Cut(B,B)=\sum _{ i\in A,j\in B }^{ }{ { w }_{ ij } } =2.3\]
$Vol(A)$는 $A$에 속한 노드에 연결된 엣지들의 모든 가중치 합입니다. 위 그림에서 1번 노드에 연결된 엣지 세 개(0.8+0.6+0.1), 2번 노드에 연결된 엣지 두 개(0.8+0.8), 3번 노드에 연결된 엣지 세 개(0.8+0.6+0.2)를 모두 더한 값입니다. 따라서 $Vol(A)$는 $Cut(A,A)$의 두 배에 $Cut(A,B)$를 더해준 값과 같습니다. 이는 $Vol(B)$도 마찬가지입니다.
\[Vol(A)=\sum _{ i\in A }^{ }{ \sum _{ j }^{ }{ { w }_{ ij } } } =4.7\]
\[Vol(B)=\sum _{ i\in B }^{ }{ \sum _{ j }^{ }{ { w }_{ ij } } } =4.9\]
Minimum Cut method
이 기법은 원그래프를 $A$와 $B$라는 부그래프로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 합니다. 목적함수는 아래와 같습니다.
\[MinCut(A,B)=\min { \frac { 1 }{ 4 } { q }^{ T }(D-W)q }\]
여기에서 대각행렬 $D$와 벡터 $q$는 아래와 같습니다.
\[{ D }_{ ii }=\sum _{ j }^{ }{ { w }_{ ij } } \quad ,\quad { D }_{ ij }=0\quad if\quad i\neq j\\ { q }_{ i }=\begin{Bmatrix} 1\quad if\quad i\in A \\ -1\quad if\quad i\in B \end{Bmatrix}\]
$MinCut(A,B)$의 제약조건은 다음과 같습니다. 벡터 $q$의 각 요소를 제곱해 모두 더한 $q^Tq$가 그래프 전체의 노드수 $V$와 일치해야 한다는 겁니다. 벡터 $q$의 각 요소는 해당 노드가 $A$에 속해 있으면 1, $B$에 속해 있으면 -1의 값을 가지기 때문입니다.
\({ q }^{ T }q=\left| V \right|\)
이해를 돕기 위해 예를 들어보겠습니다. 아래와 같이 무방향 가중치 그래프가 주어졌고, 붉은색 선을 기준으로 부그래프가 두 개로 나뉜다고 합시다. 노드1와 노드2를 부그래프 $A$, 노드3와 노드4를 부그래프 $B$로 두겠습니다.
가중치 행렬 $W$는 아래와 같습니다.
\[W=\begin{bmatrix} { w }_{ 11 } & { w }_{ 12 } & 0 & { w }_{ 14 } \\ { w }_{ 21 } & { w }_{ 22 } & { w }_{ 23 } & 0 \\ 0 & { w }_{ 32 } & { w }_{ 33 } & { w }_{ 34 } \\ { w }_{ 41 } & 0 & { w }_{ 43 } & { w }_{ 44 } \end{bmatrix}\]
대각행렬 $D$는 아래와 같습니다.
\[D=\begin{bmatrix} { w }_{ 11 }+{ w }_{ 12 }+{ w }_{ 14 } & 0 & 0 & 0 \\ 0 & { w }_{ 21 }+{ w }_{ 22 }+{ w }_{ 23 } & 0 & 0 \\ 0 & 0 & { w }_{ 32 }+{ w }_{ 33 }+{ w }_{ 34 } & 0 \\ 0 & 0 & 0 & { w }_{ 41 }+{ w }_{ 43 }+{ w }_{ 44 } \end{bmatrix}\]
$(D-W)q$는 아래와 같습니다.
\[\begin{align*}
(D-W)q&=\begin{bmatrix} { w }_{ 12 }+{ w }_{ 14 } & -{ w }_{ 12 } & 0 & -{ w }_{ 14 } \\ -{ w }_{ 21 } & { w }_{ 21 }+{ w }_{ 23 } & { -w }_{ 23 } & 0 \\ 0 & -{ w }_{ 32 } & { w }_{ 32 }+{ w }_{ 34 } & -{ w }_{ 34 } \\ -{ w }_{ 41 } & 0 & -{ w }_{ 43 } & { w }_{ 41 }+{ w }_{ 43 } \end{bmatrix}\begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \end{bmatrix}\\ &=\begin{bmatrix} 2{ w }_{ 14 } \\ 2{ w }_{ 23 } \\ -2{ w }_{ 32 } \\ -2{ w }_{ 41 } \end{bmatrix}
\end{align*}\]
위 식을 정리하면 아래와 같습니다.
\[\frac { 1 }{ 4 } { q }^{ T }(D-W)q=\frac { 1 }{ 4 } \begin{bmatrix} 1 & 1 & -1 & -1 \end{bmatrix}\begin{bmatrix} 2{ w }_{ 14 } \\ 2{ w }_{ 23 } \\ -2{ w }_{ 32 } \\ -2{ w }_{ 41 } \end{bmatrix}={ w }_{ 14 }+{ w }_{ 23 }\]
최종적으로 도출된 $w_{14}$와 $w_{23}$은 원그래프에서 두 개 부그래프로 나눠질 때 끊어지는 가중치들입니다. 다시 말해 목적함수에 정의된 $1/4q^T(D-W)q$를 최소화한다는 것은 끊어지는 가중치들을 최소로 하겠다는 의미가 되는 것입니다.
목적함수 $1/4q^T(D-W)q$에 제약조건($q^Tq=V$)을 반영해 라그랑지안 문제로 변환하고, 식을 미지수 $q$로 미분해서 0으로 놓으면 아래와 같이 정리할 수 있습니다. ($q$가 미지수가 되는 이유는 각 노드가 $A$에 속하는지, $B$가 속하는지 정보가 이 벡터에 들어있기 때문입니다)
\[\begin{align*}
\frac { \partial C }{ \partial q } &=\frac { \partial \{ \frac { 1 }{ 4 } { q }^{ T }(D-W)q-\lambda ({ q }^{ t }q-\left| V \right| )\} }{ \partial q } \\ &=\frac { 1 }{ 2 } (D-W)q-\lambda q=0\\ &(D-W)q=\lambda q
\end{align*}\]
최종 도출된 식을 보면 우리가 찾고자 하는 $q$는 $D-W$ 행렬의 고유벡터(eigenvector)임을 알 수 있습니다. 다만 최소값을 찾는 것이 목적이므로 두번째로 작은 고유값에 해당하는 고유벡터를 취합니다(제일 작은 고유값은 0이기 때문에 무의미한 해입니다). 이 벡터의 각 요소 가운데 양수인 위치의 노드를 부그래프 $A$, 음수인 노드를 $B$로 할당하게 됩니다.
Minimum Cut method 적용 예시
예시 그림의 그래프를 인접행렬로 나타내면 다음과 같습니다.
구분
$x_1$
$x_2$
$x_4$
$x_3$
$x_5$
$x_6$
$x_1$
0
0.8
0
0.6
0.1
0
$x_2$
0.8
0
0
0.8
0
0
$x_3$
0.6
0.8
0.2
0
0
0
$x_4$
0.8
0
0
0.2
0.8
0.7
$x_5$
0.1
0
0.8
0
0
0.8
$x_6$
0
0
0.7
0
0.8
0
이로부터 $D-W$를 구합니다. 이를 고유분해한 결과가 아래와 같습니다. $Λ$는 $D-W$의 고유값들로 이뤄진 벡터, $V$는 열벡터가 고유벡터인 행렬입니다.
\[{ \Lambda }^{ T }=\begin{bmatrix} 0.0 & 0.3 & 2.2 & 2.3 & 2.5 & 3.0 \end{bmatrix}\\ X=\begin{bmatrix} 0.4 & 0.2 & 0.1 & 0.4 & -0.2 & -0.9 \\ 0.4 & 0.2 & 0.1 & 0.0 & 0.4 & 0.3 \\ 0.4 & 0.2 & -0.2 & 0.0 & -0.2 & 0.6 \\ 0.4 & -0.4 & 0.9 & 0.2 & -0.4 & -0.6 \\ 0.4 & -0.7 & -0.4 & -0.8 & -0.6 & -0.2 \\ 0.4 & -0.7 & -0.2 & 0.5 & 0.8 & 0.9 \end{bmatrix}\]
그렇다면 우리가 찾고자 하는 미지수 $q$는 $V$의 두번째 열이 됩니다. 여기에서 양수인 노드1 노드2 노드3은 부그래프 $A$, 음수인 노드4 노드5 노드6은 $B$에 할당하면 Spectral Clustering 절차가 끝납니다.
\[{ q }^{ T }=\begin{bmatrix} 0.2 & 0.2 & 0.2 & -0.4 & -0.7 & -0.7 \end{bmatrix}\]
다른 방법들
부그래프의 크기를 비슷하게 맞추는 방향으로 자르는 Ratio Cut, 엣지 가중치 합을 비슷하게 하여 부그래프를 자르는 Minmax Cut 기법이 있습니다. 식은 아래와 같습니다. (여기에서 $A$의 절대값 은 $A$의 노드 수를 뜻합니다)
\[RatioCut(A,B)=\min { \{ Cut(A,B)(\frac { 1 }{ \left| A \right| } +\frac { 1 }{ \left| B \right| } )\} }\]
\[MinMaxCut(A,B)=\min { \{ Cut(A,B)(\frac { 1 }{ Cut(A,A) } +\frac { 1 }{ Cut(B,B) } )\} }\]
Recursive bi-partitioning
지금까지 설명드린 Spectral Clustering은 원그래프를 두 개의 부그래프로 나누는 기법이었습니다. 그렇다면 여러 개 부그래프로 군집화하려면 어떻게 해야할까요? 지금까지 설명드렸던 기법을 반복적으로 수행하면 됩니다.
이번 글에서는 그래프(graph) 기반 군집화 기법인 Spectral Clustering에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
그래프 인접행렬 구축
Spectral Clustering을 수행하려면 원데이터를 그래프로 변환하기 위해 인접행렬(Adjacency Matrix)을 만들어야 합니다. Spectral Clustering은 무방향 가중치 그래프(Undirected Weighted Graph)를 사용하는데요, 무방향 가중치 그래프와 인접행렬을 직관적으로 비교한 그림은 아래와 같습니다(출처).
원데이터에서 인접행렬을 만들 때는 보통 아래와 같이 가우시안 커널(Gaussian kernel)을 많이 사용합니다. 예컨대 벡터로 표현된 하나의 문서를 노드(node)라고 둘 때, 문서 간 거리가 멀리 떨어져 있을수록(=유사하지 않을수록) 그 가중치는 줄어듭니다. 아울러 가우시안 커널로 만들어진 인접행렬은 대칭행렬입니다.
\[{ W }_{ ij }=exp\left( -\frac { d{ ({ x }_{ i },{ x }_{ j }) }^{ 2 } }{ 2\sigma^{2} } \right)\]문서를 그래프로 표현하는 방법에 대해서는 이곳을, 가우시안 커널로 인접행렬을 만드는 방법에 대해서는 이곳을 참고하시면 좋을 것 같습니다.
그래프 구축
fully connected graph란 모든 노드가 엣지로 연결돼 있는 그래프를 가리킵니다. ε-neighborhood graph란 거리가 $ε$보다 가까운 엣지들만 살리고 나머지 엣지는 끊어버린 그래프입니다. k-nearest neighbor graph는 각 노드 주변 $k$개 이웃들만 엣지로 연결하고 나머지 엣지는 끊어놓은 그래프입니다.
ε-neighborhood graph는 노드의 밀도가 높은 지역에선 엣지가 지나치게 많이 발생하고, 밀도가 낮은 지역에선 엣지가 하나도 없는 노드가 생길 수 있습니다. k-nearest neighbor graph는 끊기는 노드가 발생하진 않지만, 군집이 극단적으로 멀리 떨어져 있는 경우 군집과 군집 사이는 연결되지 않는 경우가 발생할 수 있습니다.
일반적으로 그래프를 구축할 때는 ε-neighborhood graph를 먼저 구축한 뒤 k-nearest neighbor graph를 적용해 엣지가 전혀 없는 노드도 연결해주는 방식을 씁니다. 그럼에도 불구하고 군집 사이가 너무 멀어서 연결 안되는 경우가 발생할 수 있는데 이럴 때는 minimum spanning tree 방법도 자주 사용됩니다.
그래프 컷 지표
그래프 컷은 그래프를 특정 기준에 의해 두 개 이상의 부그래프(subgraph)로 나누는 것입니다. 이 부그래프가 바로 Spectral Clustering 기법의 학습 결과물인 군집이 됩니다. 아래와 같은 무방향 가중치 그래프가 주어졌다고 합시다.
$Cut(A,B)$는 부그래프 $A$에서 $B$로 향하는 엣지들의 가중치 합입니다. 아래 식과 같습니다.
\[Cut(A,B)=\sum _{ i\in A,j\in B }^{ }{ { w }_{ ij } } =0.3\]$Cut(A,A)$는 $A$에서 $A$로 향하는 엣지들의, $Cut(B,B)$는 $B$에서 $B$로 향하는 엣지들의 가중치 합입니다.
\[Cut(A,A)=\sum _{ i\in A,j\in A }^{ }{ { w }_{ ij } } =2.2\] \[Cut(B,B)=\sum _{ i\in A,j\in B }^{ }{ { w }_{ ij } } =2.3\]$Vol(A)$는 $A$에 속한 노드에 연결된 엣지들의 모든 가중치 합입니다. 위 그림에서 1번 노드에 연결된 엣지 세 개(0.8+0.6+0.1), 2번 노드에 연결된 엣지 두 개(0.8+0.8), 3번 노드에 연결된 엣지 세 개(0.8+0.6+0.2)를 모두 더한 값입니다. 따라서 $Vol(A)$는 $Cut(A,A)$의 두 배에 $Cut(A,B)$를 더해준 값과 같습니다. 이는 $Vol(B)$도 마찬가지입니다.
\[Vol(A)=\sum _{ i\in A }^{ }{ \sum _{ j }^{ }{ { w }_{ ij } } } =4.7\] \[Vol(B)=\sum _{ i\in B }^{ }{ \sum _{ j }^{ }{ { w }_{ ij } } } =4.9\]Minimum Cut method
이 기법은 원그래프를 $A$와 $B$라는 부그래프로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 합니다. 목적함수는 아래와 같습니다.
\[MinCut(A,B)=\min { \frac { 1 }{ 4 } { q }^{ T }(D-W)q }\]여기에서 대각행렬 $D$와 벡터 $q$는 아래와 같습니다.
\[{ D }_{ ii }=\sum _{ j }^{ }{ { w }_{ ij } } \quad ,\quad { D }_{ ij }=0\quad if\quad i\neq j\\ { q }_{ i }=\begin{Bmatrix} 1\quad if\quad i\in A \\ -1\quad if\quad i\in B \end{Bmatrix}\]$MinCut(A,B)$의 제약조건은 다음과 같습니다. 벡터 $q$의 각 요소를 제곱해 모두 더한 $q^Tq$가 그래프 전체의 노드수 $V$와 일치해야 한다는 겁니다. 벡터 $q$의 각 요소는 해당 노드가 $A$에 속해 있으면 1, $B$에 속해 있으면 -1의 값을 가지기 때문입니다. \({ q }^{ T }q=\left| V \right|\)
이해를 돕기 위해 예를 들어보겠습니다. 아래와 같이 무방향 가중치 그래프가 주어졌고, 붉은색 선을 기준으로 부그래프가 두 개로 나뉜다고 합시다. 노드1와 노드2를 부그래프 $A$, 노드3와 노드4를 부그래프 $B$로 두겠습니다.
가중치 행렬 $W$는 아래와 같습니다.
\[W=\begin{bmatrix} { w }_{ 11 } & { w }_{ 12 } & 0 & { w }_{ 14 } \\ { w }_{ 21 } & { w }_{ 22 } & { w }_{ 23 } & 0 \\ 0 & { w }_{ 32 } & { w }_{ 33 } & { w }_{ 34 } \\ { w }_{ 41 } & 0 & { w }_{ 43 } & { w }_{ 44 } \end{bmatrix}\]대각행렬 $D$는 아래와 같습니다.
\[D=\begin{bmatrix} { w }_{ 11 }+{ w }_{ 12 }+{ w }_{ 14 } & 0 & 0 & 0 \\ 0 & { w }_{ 21 }+{ w }_{ 22 }+{ w }_{ 23 } & 0 & 0 \\ 0 & 0 & { w }_{ 32 }+{ w }_{ 33 }+{ w }_{ 34 } & 0 \\ 0 & 0 & 0 & { w }_{ 41 }+{ w }_{ 43 }+{ w }_{ 44 } \end{bmatrix}\]$(D-W)q$는 아래와 같습니다.
\[\begin{align*} (D-W)q&=\begin{bmatrix} { w }_{ 12 }+{ w }_{ 14 } & -{ w }_{ 12 } & 0 & -{ w }_{ 14 } \\ -{ w }_{ 21 } & { w }_{ 21 }+{ w }_{ 23 } & { -w }_{ 23 } & 0 \\ 0 & -{ w }_{ 32 } & { w }_{ 32 }+{ w }_{ 34 } & -{ w }_{ 34 } \\ -{ w }_{ 41 } & 0 & -{ w }_{ 43 } & { w }_{ 41 }+{ w }_{ 43 } \end{bmatrix}\begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \end{bmatrix}\\ &=\begin{bmatrix} 2{ w }_{ 14 } \\ 2{ w }_{ 23 } \\ -2{ w }_{ 32 } \\ -2{ w }_{ 41 } \end{bmatrix} \end{align*}\]위 식을 정리하면 아래와 같습니다.
\[\frac { 1 }{ 4 } { q }^{ T }(D-W)q=\frac { 1 }{ 4 } \begin{bmatrix} 1 & 1 & -1 & -1 \end{bmatrix}\begin{bmatrix} 2{ w }_{ 14 } \\ 2{ w }_{ 23 } \\ -2{ w }_{ 32 } \\ -2{ w }_{ 41 } \end{bmatrix}={ w }_{ 14 }+{ w }_{ 23 }\]최종적으로 도출된 $w_{14}$와 $w_{23}$은 원그래프에서 두 개 부그래프로 나눠질 때 끊어지는 가중치들입니다. 다시 말해 목적함수에 정의된 $1/4q^T(D-W)q$를 최소화한다는 것은 끊어지는 가중치들을 최소로 하겠다는 의미가 되는 것입니다.
목적함수 $1/4q^T(D-W)q$에 제약조건($q^Tq=V$)을 반영해 라그랑지안 문제로 변환하고, 식을 미지수 $q$로 미분해서 0으로 놓으면 아래와 같이 정리할 수 있습니다. ($q$가 미지수가 되는 이유는 각 노드가 $A$에 속하는지, $B$가 속하는지 정보가 이 벡터에 들어있기 때문입니다)
\[\begin{align*} \frac { \partial C }{ \partial q } &=\frac { \partial \{ \frac { 1 }{ 4 } { q }^{ T }(D-W)q-\lambda ({ q }^{ t }q-\left| V \right| )\} }{ \partial q } \\ &=\frac { 1 }{ 2 } (D-W)q-\lambda q=0\\ &(D-W)q=\lambda q \end{align*}\]최종 도출된 식을 보면 우리가 찾고자 하는 $q$는 $D-W$ 행렬의 고유벡터(eigenvector)임을 알 수 있습니다. 다만 최소값을 찾는 것이 목적이므로 두번째로 작은 고유값에 해당하는 고유벡터를 취합니다(제일 작은 고유값은 0이기 때문에 무의미한 해입니다). 이 벡터의 각 요소 가운데 양수인 위치의 노드를 부그래프 $A$, 음수인 노드를 $B$로 할당하게 됩니다.
Minimum Cut method 적용 예시
예시 그림의 그래프를 인접행렬로 나타내면 다음과 같습니다.
| 구분 | $x_1$ | $x_2$ | $x_4$ | $x_3$ | $x_5$ | $x_6$ |
|---|---|---|---|---|---|---|
| $x_1$ | 0 | 0.8 | 0 | 0.6 | 0.1 | 0 |
| $x_2$ | 0.8 | 0 | 0 | 0.8 | 0 | 0 |
| $x_3$ | 0.6 | 0.8 | 0.2 | 0 | 0 | 0 |
| $x_4$ | 0.8 | 0 | 0 | 0.2 | 0.8 | 0.7 |
| $x_5$ | 0.1 | 0 | 0.8 | 0 | 0 | 0.8 |
| $x_6$ | 0 | 0 | 0.7 | 0 | 0.8 | 0 |
이로부터 $D-W$를 구합니다. 이를 고유분해한 결과가 아래와 같습니다. $Λ$는 $D-W$의 고유값들로 이뤄진 벡터, $V$는 열벡터가 고유벡터인 행렬입니다.
\[{ \Lambda }^{ T }=\begin{bmatrix} 0.0 & 0.3 & 2.2 & 2.3 & 2.5 & 3.0 \end{bmatrix}\\ X=\begin{bmatrix} 0.4 & 0.2 & 0.1 & 0.4 & -0.2 & -0.9 \\ 0.4 & 0.2 & 0.1 & 0.0 & 0.4 & 0.3 \\ 0.4 & 0.2 & -0.2 & 0.0 & -0.2 & 0.6 \\ 0.4 & -0.4 & 0.9 & 0.2 & -0.4 & -0.6 \\ 0.4 & -0.7 & -0.4 & -0.8 & -0.6 & -0.2 \\ 0.4 & -0.7 & -0.2 & 0.5 & 0.8 & 0.9 \end{bmatrix}\]그렇다면 우리가 찾고자 하는 미지수 $q$는 $V$의 두번째 열이 됩니다. 여기에서 양수인 노드1 노드2 노드3은 부그래프 $A$, 음수인 노드4 노드5 노드6은 $B$에 할당하면 Spectral Clustering 절차가 끝납니다.
\[{ q }^{ T }=\begin{bmatrix} 0.2 & 0.2 & 0.2 & -0.4 & -0.7 & -0.7 \end{bmatrix}\]다른 방법들
부그래프의 크기를 비슷하게 맞추는 방향으로 자르는 Ratio Cut, 엣지 가중치 합을 비슷하게 하여 부그래프를 자르는 Minmax Cut 기법이 있습니다. 식은 아래와 같습니다. (여기에서 $A$의 절대값 은 $A$의 노드 수를 뜻합니다)
\[RatioCut(A,B)=\min { \{ Cut(A,B)(\frac { 1 }{ \left| A \right| } +\frac { 1 }{ \left| B \right| } )\} }\] \[MinMaxCut(A,B)=\min { \{ Cut(A,B)(\frac { 1 }{ Cut(A,A) } +\frac { 1 }{ Cut(B,B) } )\} }\]Recursive bi-partitioning
지금까지 설명드린 Spectral Clustering은 원그래프를 두 개의 부그래프로 나누는 기법이었습니다. 그렇다면 여러 개 부그래프로 군집화하려면 어떻게 해야할까요? 지금까지 설명드렸던 기법을 반복적으로 수행하면 됩니다.
Comments