Spectral Clustering Algorithm(스펙트럼 군집화 알고리즘)

 

 오늘날은 인터넷을 통해 수많은 정보를 얻을 수 있는 빅데이터 시대에 도래하였습니다. 정보의 양이 매우 방대하다 보니 데이터 하나 하나 마다 개별로 의미를 찾아보기 보다는 전체 데이터의 특성을 분류하여 의미를 찾기 위해 사용되는 정교한 Clustering(군집화) 알고리즘이 필요하게 되었습니다.

 Clustering 알고리즘의 핵심은 주어진 데이터들을 유사한 특성을 가진 데이터들끼리 분류하여 이를 하나의 같은 그룹으로 만들어 주는 기능입니다. 이러한 Clustering 알고리즘의 특성 덕분에 빅데이터 내의 수많은 정보들을 특정한 카테고리나 클래스로 분류할 수 있는 것이지요.

 본 포스팅에서는 이러한 Clustering 알고리즘 중 하나인 Spectral Clustering 알고리즘에 대해 알아보도록 하겠습니다.

 

1. Data Clustering(자료 군집화)

  초기에 주어지는 데이터는 단순히 자신이 가지고 있는 정보를 그저 나열하고 있는 모습을 띄고 있습니다. 이를 하나의 그룹으로 분류하기 위해 서로 유사한 데이터끼리 묶어주는 작업을 하는 것이 Clustering 알고리즘의 목적입니다.

 

 위의 그림에서 보시는 바와 같이 단순히 나열되어 있던 각 데이터들이 유사한 3개의 그룹으로 나누어지게 된 것을 보실 수 있습니다. 여기서 유사하다는 것은 점 사이의 거리로 나타냅니다. 즉, 서로 가까운 점들끼리 묶어보니 3개의 그룹이 만들어지게 된 것이지요.

 그렇다면 이러한 클러스터링 알고리즘은 어떠한 방식이 있는 것일까요?

 

 

 각 그룹을 분류하는 Clustering 알고리즘은 2가지 접근 방법이 있습니다. 하나는 매개변수 모델 기반 방식(Parametric Model-based)과 그래프 기반 방식(Graph-based) 방식이 있습니다. 매개변수 모델 기반 방식의 경우 말 그대로 주어진 데이터를 가지고 임의의 그룹 중심점을 찾은 다음 반복적으로 그룹의 중심점을 찾아가는 과정입니다. k-Means 알고리즘이 이를 사용한 알고리즘으로서, 반복적인 연산을 통해 결과를 얻어냅니다.

 위의 그림과 같이 거리상으로 떨어져있는 2개의 그룹이 존재한다고 하였을 때 임의의 중심점 2개를 잡은 후 해당 점에서 가까운 데이터들을 그룹으로 만든 후 새로 만들어진 그룹 내의 중심점을 잡고, 다시 만든 중심점에서 가까운 데이터들을 그룹으로 만드는 방식을 반복하다 보면 위의 그림과 같이 한 점으로 수렴하게 됩니다. 이러한 매개변수 모델 기반 방식의 최대 단점은 결과가 항상 일정하지 않으며 가끔씩 잘못된 그룹으로 분류되는 경우가 발생할 수 있다는 점입니다.

 

 그래프 기반 방식은 각 데이터의 점들과 다른 점 사이에 선을 긋고 두 데이터 사이의 유사도에 따라 비중을 부여하는 방식입니다. 그래프 기반 방식에 따르면 두 데이터의 유사점이 많으면 비중을 키우고, 유사점이 낮으면 비중을 낮추는 식으로 하여 이를 기준으로 별개의 그룹으로 나누는 방식입니다. 이 방식을 사용하면 매개변수 모델 기반 방식보다 비교적으로 결과값이 거의 일정하게 나온다는 장점이 있습니다. 두 그룹으로 나누는 데 사용하는 방식으로는 Minimum cut과 Normalized cut이 있습니다.

 

2. Segmentation by Graph Partitioning(그래프 클러스터링)

 설명하기에 앞서 Spectral Clustering을 간단하게 설명해주는 동영상을 참고해봅시다. 바로 이해하기 어려우시겠지만 영상으로 한 번 보는 것이 이어서 설명하는 데에 도움이 될 것입니다.

 

 

 

 위 동영상을 시청하셧다면 이제 설명을 해드리도록 하겠습니다. 아래와 같이 9개의 점들이 3개의 그룹을 이루고 있는 데이터가 있다고 가정해봅니다.

 

 이제 Spectral Clustering 알고리즘을 사용하여 위 그림의 데이터들을 Graph로 표현해보도록 하겠습니다. 이들을 그래프로 나타나기 위해서는 유사도 행렬(Affinity Matrix)를 통해 이를 표현해야 합니다.

 아래의 그림은 위 데이터를 유사도 행렬(Affinity Matrix)로 표현한 것입니다. 각 색깔에 맞추어 유사도 행렬을 만든 점을 주목해 주시길 바랍니다.

 

 이제 적용된 유사도 행렬에서 처럼 위 데이터를 그래프로 나타내봅니다. 색깔로 칠해진 부분은 1로 굵은 선으로, 색깔이 칠해지지 않은 부분은 0으로 가느다란 선으로 표시합니다.

 

 어떤가요? 위와 같이 각 데이터를 그래프로 표현하니 눈에띄게 구분이 되고 있는 것을 알 수 있습니다.

 

 지금까지 우리의 시각에서 판단해서 Spectral Clustering 알고리즘을 수행하였습니다. 그렇다면 컴퓨터를 통해 이를 직접 구현하려면 어떠한 방식으로 해야할까요? 각 데이터의 유사도를 사람처럼 판단해서 위와 같은 그래프로 표현할 수 있는 방법은 있는걸까요?

 

3.Affinity Matrix(유사도 행렬 만들기)

 두 데이터의 유사도가 높을수록 최대한 높은 값을 가지게 하고 반대로 유사도가 낮을수록 최대한 0에 가깝게 값을 만든다면 위의 유사도 행렬(Affinity Matrix)과 비슷한 모양의 행렬이 만들어 질 수 있으리라 생각됩니다. 이를 위해 가우시안 커널 σ을 사용하는데 그 공식은 아래와 같습니다. 이 때 w는 데이터 i, j 사이의 선, σ는 커널의 폭, x는 데이터 i, j의 거리 정보로서 두 데이터 i, j 사이의 거리를 나타낸다 볼 수 있겠습니다.

 이 식에서 가장 중요한 부분은 바로 σ입니다. σ는 각 데이터의 거리간격 w의 결과에 지대한 영향을 미치는 변수로 적절한 값으로 이를 설정하여주면 각 그룹 사이의 간격을 적당하게 구분시켜줄 수 있게 됩니다.  아래의 표는 σ의 크기에 따른 유사도 값 w의 크기의 변화를 나타낸 것입니다.

 

 

 위의 그래프에서 볼 수 있는 바와 같이 σ의 값이 작을수록 각 그룹을 세분하게 나누어줄 수 있으나 자칫하면 같은 그룹에 속하는 데이터 사이의 간격이 조금이라도 멀어지면 w값(affinity)이 급격하게 줄어드는 것을 보실 수 있습니다. 반면, σ의 값이 클수록 다소 멀리 떨어져 있는 같은 그룹 내의 데이터를 포함시킬 수 있으나 자칫하면 비교적 거리가 가까운 다른 그룹의 데이터까지 포함해버리는 경우가 발생하게 됩니다. 아래 Reference에 따르면 σ의 값을 각 데이터 i와 j의 주변 점에서 (2d+1)번째로 가까운 점 사이의 거리를 σ로 사용할 경우 최적의 값을 구할 수 있다고 소개하고 있습니다. 이 때 d는 데이터의 차원을 의미합니다. 데이터가 제공하는 정보가 1개라면 3번째로, 2개라면 5번째, 3개라면 7번째로 가까운 점 사이의 거리를 사용해 각 σi와 σj를 구하면 적합한 값 w를 얻을 수 있을 것입니다.

 

 

4. Spectral Clustering 구현하기

 다음과 같은 데이터가 입력값으로 주어졌다고 가정해 봅시다.

1    1
1    2
3    1
3    2
5    1
5    2

 

 위 입력값을 직관적인 관점에서 3개의 cluster로 구분한다면 (1,2), (3,4), (5,6)이 될 것으로 기대할 수 있습니다.

 위 데이터를 Affinity Matrix로 나타내면 다음과 같습니다. 여기서 가우시안 커널 σ은 임의로 설정된 값으로 하여 데이터가 충분히 구분될 수 있도록 하였습니다.

 

 

 주어진 데이터는 총 6개이므로 6X6 크기의 Affinity Matrix가 만들어집니다. 각 행렬의 i열은 위 입력 데이터의 i번째 줄의 데이터를 의미합니다. 자신의 데이터 사이의 거리는 1이며 자신에게 가까운 값일수록 1에 가깝고 멀어질수록 0으로 수렴하고 있는 것을 보실 수 있습니다. 위 데이터를 기준으로 본다면 0.5 이상의 값은 1로, 0.5 이해의 값은 0으로 한다면 위에서 설명하였던 이상적인 Affinity Matrix가 그려지는 것을 알 수 있습니다.

 

 위와 같이 주어진 Affinity Matrix를 사용하여 Spectral Clustering을 구현해봅시다. Spectral Clustering을 구현함에 있어서의 기준은 다음과 같습니다.

 

1. 같은 Cluster 내의 요소끼리의 유사도는 큰 값을 갖는다.

2. 다른 Cluster에 속한 요소끼리의 유사도는 작은 값을 갖는다.

 

 이를 구하기 위해서는 위에서 구한 Affinity Matrix 값 W의 값이 최대로 나오는 Vector 행렬을 구해야 합니다. W와 행렬곱을 하였을 때 최대값이 나오게 하는 벡터를 고유벡터(eigenvector)라 칭합니다. 고유벡터에 대해 알기 위해서는 대학 학부 수준의 선형대수에 대한 기초적인 지식이 있어야 이해할 수 있습니다. 고유벡터에 대해 자세히 알고 싶으신 분은 아래의 블로그 포스팅을 참조하시면 이해하는 데에 도움이 될 것입니다.

 

고유값과 고유벡터[다크 프로그래머]

http://darkpgmr.tistory.com/105

 

 Affinity Matrix 값 W의 고유벡터를 구하면 아래와 같은 값이 도출됩니다. 

[[ -3.58906456e-01  -5.00000000e-01  -3.48118020e-01   3.58906456e-01    3.48118020e-01   5.00000000e-01]
 [ -3.58906456e-01  -5.00000000e-01  -3.48118020e-01  -3.58906456e-01   -3.48118020e-01  -5.00000000e-01]
 [ -4.92313226e-01   2.79483017e-16   5.07570377e-01   4.92313226e-01   -5.07570377e-01  -4.52681896e-16]
 [ -4.92313226e-01   9.86999413e-17   5.07570377e-01  -4.92313226e-01    5.07570377e-01   4.79275406e-16]
 [ -3.58906456e-01   5.00000000e-01  -3.48118020e-01   3.58906456e-01    3.48118020e-01  -5.00000000e-01]
 [ -3.58906456e-01   5.00000000e-01  -3.48118020e-01  -3.58906456e-01   -3.48118020e-01   5.00000000e-01]]

 

 고유벡터의 열(Column) 부분을 보시면 값이 서로 구분되고 있는 것을 보실 수 있습니다. 일반적으로 1번째 Column은 구분이 모호하기 때문에 2번째 Column부터 사용하게 됩니다.

  k 개의 그룹 cluster가 존재할 때 이들을 분별하기 위해서는 Affinity Matrix의 고유벡터의 2번째부터 k번째 column 부분만 보고 분별을 하게 됩니다. 즉 위의 예제의 경우 3개의 cluster로 구분되고 있으니 2,3번째 column만 사용하면 되겠습니다. 이 경우 첫 번째 cluster인 (1,2) 그룹의 경우 (-0.5, -0.3)으로, (3,4) 그룹의 경우 ( 0, 0.5), (5,6) 그룹의 경우 (0.5, -0.3)으로 뚜렷이 구분되고 있음을 확인하실 수 있습니다. 이를 이미지로 표현하면 다음과 같다 볼 수 있겠습니다.

 

 

 

 위에서 보시는 바와 같이 각 그룹이 고유벡터 내의 성분대로 분류하면 뚜렷하게 분류가 되는 것을 확인하실 수 있습니다.

 

 고유벡터값을 토대로 Spectral Clustering을 구현하는 알고리즘으로는 Minimum Cut과 Normalized Cut을 사용하게 되는데요 위 알고리즘은 다음 포스팅에서 이어서 설명을 하도록 하겠습니다.

 

Spectral Cluster 알고리즘 응용(Minimum Cut)

http://elecs.tistory.com/169

 

- Reference

허경용, 김광백, 우영운 (2008), "스펙트럼 군집화에서 블록 대각 형태의 유사도 행렬 구성", 한국멀티미디어학회논문지, 11(9), 1302-1309.

http://www.dbpia.co.kr/Article/NODE01605020

스펙트럼 군집화에서 블록 대각 형태의 유사도 행렬 구성

※2020년 8월 5일 수정

기존의 유튜브 영상이 나오지 않아 새로운 영상으로 변경하였습니다.