Spectral Clustering - graph Laplacian matrix

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 라고 부른다. 그리고 이 벡터의 성분들에 대한 각 부호(+, -) 로 클러스터링을 구분한다.

절차

Incidencey matrix A 를 구한다.
graph Laplacian matrix L 을 구한다.
L을 고유값 분해한다.
고유값 중 0 이 아닌 가장 작은 고유값 \(\lambda_2\)을 구한다.
위의 \(\lambda_2\) 에 해당하는 고유벡터 \(x_2\) 를 구한다. (Fiedler vector)
고유벡터의 +, - 성분으로 클러스터링을 구분한다.

그래프는 다음과 같다.

# Incidency matrix A 를 구한다.
A <- matrix(c(-1, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 1, 0, 1, -1, 0, -1, 0, 0, 1), nrow=5, byrow=T)
A

##      [,1] [,2] [,3] [,4]
## [1,]   -1    1    0    0
## [2,]   -1    0    1    0
## [3,]    0   -1    0    1
## [4,]    0    1   -1    0
## [5,]   -1    0    0    1

# graph Laplacian matrix L 을 구한다.
L <- t(A) %*% A
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

# 또는 아래 방법을 사용한다.
k   <- 2
Z   <- ev$vectors[,(ncol(ev$vectors)-k+1):(ncol(ev$vectors)-1)]
Z

## [1]  0.0000000  0.0000000 -0.7071068  0.7071068

library(stats)
km <- kmeans(Z, centers=k, nstart=5)
km

## K-means clustering with 2 clusters of sizes 3, 1
## 
## Cluster means:
##         [,1]
## 1 -0.2357023
## 2  0.7071068
## 
## Clustering vector:
## [1] 1 1 1 2
## 
## Within cluster sum of squares by cluster:
## [1] 0.3333333 0.0000000
##  (between_SS / total_SS =  66.7 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

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

Spectral Clustering - graph Laplacian matrix

Kong, Seokkyu

2020-08-23

Summary