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

공대생의 팁 2015. 12. 28. 17:41

 오늘날은 인터넷을 통해 수많은 정보를 얻을 수 있는 빅데이터 시대에 도래하였습니다. 정보의 양이 매우 방대하다 보니 데이터 하나 하나 마다 개별로 의미를 찾아보기 보다는 전체 데이터의 특성을 분류하여 의미를 찾기 위해 사용되는 정교한 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
2
3
4
5
6
1    1
1    2
3    1
3    2
5    1
5    2
cs


 위 입력값을 직관적인 관점에서 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의 고유벡터를 구하면 아래와 같은 값이 도출됩니다. 

1
2
3
4
5
6
[[ -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]]
cs


 고유벡터의 열(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

  • 윤시기 2019.01.11 21:06 ADDR 수정/삭제 답글

    안녕하세요 글 너무나 잘읽고 도움 많이 받았습니다.
    clustering 기법들에 관심을 갖고 검색하다가 늦깎이 공대생님의 블로그를 보게 되었습니다.
    혹시나 위에서 eigenvector 2개를 선정한 이유와 "첫 번째 cluster인 (1,2) 그룹의 경우 (-0.5, -0.3)으로, (3,4) 그룹의 경우 ( 0, 0.5), (5,6) 그룹의 경우 (0.5, -0.3)으로 뚜렷이 구분되고 있음을 확인하실 수 있습니다." 이 문장을 조금만더 설명해 주실수 있나요? 이해력이 좋지않아 잘 이해가 되지 않습니다..

    • Justin T. 2019.01.11 21:47 신고 수정/삭제

      주어진 자료에서 cluster는 3개로 분류될 수 있을 것으로 예측할 수 있습니다. 이 때 k는 3이 되겠지요.
      일반적으로 Eigen Vector를 사용하였을 때 첫 번째 Column의 값은 모호한 경우가 있기 때문에 2번째부터 k번째 column으로 각 cluster를 구분하게 되는데 주어진 예제에서 cluster의 갯수는 3개이므로 2번째와 3번째 column으로 cluster를 분류하는 것입니다.
      우리의 직관으로 보았을 때 3개의 클러스터는 각각 [1,2], [3,4]와 [5,6]으로 나눌 수 있으리라 생각합니다. 이 때 2번째와 3번째 column값을 확인해보면 각각 (-0.50, -0.35), (0.00, 0.51), 그리고 (0.50, -0.35)로 구분되어 위의 좌표값으로 나타남을 확인하실 수 있습니다.

    • 윤시기 2019.01.11 22:05 수정/삭제

      감사합니다.
      저도 대학원 1년 이제 끝낸 공대생이지만 제가 너무 부끄러울 정도로 엄청난 블로그를 운영하시고 계시군요.. 감탄했습니다.

      자주 정보 얻으러 오겠습니다. 좋은 정보 감사하고 친절한 답변 많은 도움 되었습니다. 좋은 하루 되세요

  • dbscan은 2020.03.19 23:25 ADDR 수정/삭제 답글

    좋은글 감사 합니다. 내용중 [Parametric Model-based]에 DBSCAN이라는 밀집도 기반 방식도 포함될까요? 파라미터가 정확히 무엇을 의미 하나요? 어느 정보라도 주어지면(중앙좌표, 그룹으로 간주할 거리 정보, 등) 이쪽에 속한다고 보면 되나요?

    • Justin T. 2020.03.20 01:16 신고 수정/삭제

      파라미터란 우리말로 매개변수로서 어느 한 변수가 다른 변수에 영향을 주는 경우 해당 변수를 특정하는 용어라고 이해하시면 될 것 같습니다.
      위에서 설명드린 K-means 알고리즘은 대표적인 Parametric based 알고리즘으로서 주어진 데이터 상호간의 연관성을 가지고 중심점을 찾아내는 방식으로서 단 하나의 데이터가 아닌 모든 데이터의 분포 정보를 알고 있어야 사용할 수 있는 알고리즘입니다.
      반면에 질문에서 언급하셨던 DBSCAN은 대표적인 Nonparametric based 모델로서 특정한 한 점에서 주어진 거리 내의 점의 갯수를 분석함으로서 그룹을 찾아내는 알고리즘입니다. 여기서 DBSCAN은 주어진 모든 데이터의 정보를 알지 못하고 단 하나의 데이터를 중심으로 가장 가까운 데이터를 분석하는 방식이기 때문에 이를 비매개변수 방식의 알고리즘이라고 하지요.

  • dbscan은 2020.03.20 11:29 ADDR 수정/삭제 답글

    친절한 답변 갑사 합니다. Parametric와 Nonparametric를 비교 하는 키워드로 [사전에 전체 데이터의 분포를 알고있다/가정하고 있다]의 유무로 보면 될까요?

    ps. 공학적으로 Parametric와 paramter는 다른걸로 이해 해야 할까요?
    https://wikidiff.com/parametric/parameter