Summary

본 내용은 MIT 18.065 의 강의35번 내용 중 일부 정리입니다. 자세한 내용은 해당 강의를 참고하세요.

머신러닝의 비지도 학습의 한 종류인 클러스터링은 여러 가지 방법이 존재한다. 대표적으로는 k-Means 가 있고, 그 다음으로 Spectral clustering 을 들 수 있다.

Spectral clustering 는 graph Laplacian 행렬의 고유값을 이용한다. graph Laplacian matrix 는 Incidency Matrix 인 A 를 이용해서 구할 수 있고, Degree matrix - Adjacency matrix 로도 구할 수 있다.

\(L = A^TA = D - B\)

L 의 0 이 아닌 가장 작은 고유값을 먼저 구하고 이 고유값에 해당하는 고유벡터가 Fiedler vector 라고 부른다. 그리고 이 벡터의 성분들에 대한 각 부호(+, -) 로 클러스터링을 구분한다.

절차

여기서는 igraph 패키지를 이용해서 그래프로 표시하고, Degree matrix 와 Adjacency matrix 를 구해서 graph Laplacian matrix 를 구한다.

그래프는 다음과 같다.

library(igraph)

g <- graph( edges=c(1,2, 2,3, 1,3, 1,4, 2,4), n=4, directed=FALSE)
plot(g)

# Degree matrix D 를 구한다.
D <- diag(degree(g))
D
##      [,1] [,2] [,3] [,4]
## [1,]    3    0    0    0
## [2,]    0    3    0    0
## [3,]    0    0    2    0
## [4,]    0    0    0    2
# Adjacency matrix B 를 구한다.
B <- get.adjacency(g, sparse = FALSE) # matrix array 형태로 출력, edge 없으면 0으로 표시
B
##      [,1] [,2] [,3] [,4]
## [1,]    0    1    1    1
## [2,]    1    0    1    1
## [3,]    1    1    0    0
## [4,]    1    1    0    0
# graph Laplacian matrix L 을 구한다.
L <- D - B
L
##      [,1] [,2] [,3] [,4]
## [1,]    3   -1   -1   -1
## [2,]   -1    3   -1   -1
## [3,]   -1   -1    2    0
## [4,]   -1   -1    0    2
# L을 고유값 분해한다.
ev <- eigen(L)
ev
## eigen() decomposition
## $values
## [1] 4.000000e+00 4.000000e+00 2.000000e+00 2.664535e-15
## 
## $vectors
##            [,1]       [,2]       [,3] [,4]
## [1,]  0.8660254  0.0000000  0.0000000 -0.5
## [2,] -0.2886751  0.8164966  0.0000000 -0.5
## [3,] -0.2886751 -0.4082483 -0.7071068 -0.5
## [4,] -0.2886751 -0.4082483  0.7071068 -0.5
# Fiedler vector 를 구한다.
x2 <- ev$vectors[,3]
x2
## [1]  0.0000000  0.0000000 -0.7071068  0.7071068

군집 1은 node 1, 2, 4 로 구분할 수 있고, 군집 2는 3 이 된다.