이번 포스팅에서는 클러스터링 모델 중 하나로서 스펙트럴 클러스터링에 대해서 소개하려 한다. 여기서 스펙트럴(Spectral) 자체는 행렬의 고윳값(Eigenvalue)을 의미한다. 이는 추후에 고윳값을 어떻게 활용할 것이라는 걸 암시해주는 듯하다.
1. Parametric-based V.S Graph-based
기본적으로 클러스터링 알고리즘엔 Parametric-based 와 Graph-based 알고리즘이 존재한다. 이전에 우리가 배웠던 K-means 클러스터링같은 경우 Parametric-based 방법이라고 정의할 수 있다.(참고로 Knn(K-nearest Neighbors) 모델은 Non-parametric 클러스터링 모델이다.) 이번에는 Graph-based 방법인 Spectral Clustering 모델에 대해서 알아보자.
Graph-based 클러스터링 모델은 각 데이터의 점들과 다른 점 사이에 선을 긋고 두 데이터의 유사도에 따라 가중치를 부여한다. 이 때 가중치는 두 데이터간의 유사점이 많으면 큰 가중치값을, 유사점이 낮으면 작은 가중치값을 주어서 이를 기준으로 두 그룹으로 분류하도록 한다. Graph-based 클러스터링에서 두 그룹으로 나누는 방식으로는 Minimum out과 Normalized out 방법이 존재한다.
우선 주어진 데이터를 그래프인 유사도행렬로 어떻게 변환하는지에 대해서 알아보자. 이에 대해 참고할만한 강의는 하단 링크이며 사진은 해당 영상이 출처임을 밝힌다.
https://www.youtube.com/watch?v=kpdg7S0t0_s
위와 같이 파란색, 빨간색, 초록색 데이터가 있을 때 오른쪽과 같이 데이터간 유사도행렬(Affinity Matrix)을 만들어낼 수 있다. 그렇다면 이렇게 유사도행렬을 컴퓨터가 어떤 연산을 통해 만들어낼 수 있을까? 다음 수식을 보자.
2. Affinity Matrix(유사도 행렬)는 어떻게 만들까?
위 수식에서 w는 데이터 i와 j사이의 선(가중치)을 의미하며, ||xi - xj|| 는 데이터 xi 와 xj 사이의 거리를 나타낸다. 그리고 위 수식의 포인트는 σ이다. σ는 커널의 폭을 의미한다. 즉 σ는 각 데이터간의 거리 가중치인 w의 값에 영향을 미치는 변수로서 적절한 값을 설정해주면 각 그룹 사이의 간격을 적당하게 구분시켜준다. 아래 그림은 σ값이 작고 커짐에 따라 유사도가 어떻게 변화하는지 볼 수 있다.
위 그림을 보면 σ값이 작을수록 각 그룹을 세분하게 나누어주지만 데이터간의 간격이 일정보다 멀어진다면 유사도(Affinity)값이 급격히 작아지는 것을 볼 수 있다. 반대로 σ값이 커질수록 같은 그룹이지만 거리가 좀 멀리 떨어져 있는 데이터도 같은 그룹으로 분류하지만 그 범위안에 다른 그룹의 데이터가 존재할 수도 있는 제약이 있다. 그래서 σ값은 각 데이터 i와 j의 주변에서 2d+1 번째로 가까운 점 사이의 거리값으로 설정해줄 때 최적의 값이 된다고 한다. 여기서 d란, 데이터의 차원 즉, 데이터가 제공하는 정보의 개수를 의미한다.
이제 유사도행렬을 사용해 Spectral Clustering을 구현할 수 있다. 구현할 때는 2가지 기준에 따라야 한다. 먼저 같은 클러스터 내의 데이터끼리의 유사도는 큰 값을 갖는다. 두 번째로는 다른 클러스터에 속한 데이터끼리의 유사도는 작은 값을 갖는다.
3. 고유벡터를 활용한 Spectral Clustering 구현
그리고 유사도행렬에서 w값이 최대로 나오도록 하는 고유벡터를 구해야 한다. 이렇게 구한 여러 고유벡터들의 열(Column)부분에서 일반적으로 1번째 열은 구분이 모호하기 때문에 2번째 열부터 이용한다.
이렇게 고유벡터값들을 바탕으로 Spectral Clustering을 구현하는 알고리즘에는 이미 언급했듯이 Minimum out과 Normalized out이 존재하는데 Minimum out에 대해서 알아보자.
우선 동그라미(데이터)간을 이어주는 edge에 쓰여져 있는 수치들은 두 데이터간의 거리 즉, 유사도를 의미한다.(값이 높을수록 비슷한 데이터를 의미) Minimum out 방법은 주어진 데이터들 사이의 유사도 값들 중 가장 작은 값으로 각각의 클러스터로 나누어주는 기능을 한다. 위 그림에서는 가장 가중치값이 낮은 1, 2, 1 edge를 기준으로 클러스터를 구분했다. 이 때도 고윳값을 사용하며 첫 번째의 고윳값은 0이므로 무의미한 해이기 때문에 두 번째의 고윳값부터 사용하게 된다.
4. Minimum out의 단점
하지만 Minimum out 방법은 최소값을 찾는 과정을 거치기 때문에 만약 이상적인 방향으로 클러스터를 분류하는 가중치값들의 합보다 더 작은 가중치가 같은 클러스터안에 존재하게 된다면 분류의 방향이 잘못되게 된다. 밑의 그림이 바로 그러한 예시이다.
지금까지 Spectral Clustering에 대해서 얕은 깊이로 알아보았다. 더 깊은 내용을 직접 담고 싶었지만 아직 수학적인 이론부분에서 부족한 부분이 많은 것 같다. 앞으로 지속적으로 해당 글을 보완해야 할 것 같다.
참고문헌으로 Minimum out을 적용해보는 실제적인 예시에 대한 내용을 매우 잘 담고 있는 블로그를 소개하려고 한다. 필자의 글보다 하단의 훌륭한 글들을 통해서 이해하는 것이 더욱 더 효과적일 것 같다. 필자도 단 한 번에 이해하지 못하지만 계속적으로 다양한 관련 글을 읽고 이해해보려 한다.
# Spectral Clustering의 실제적인 예시 블로그
https://ratsgo.github.io/machine%20learning/2017/04/27/spectral/
Spectral Clustering · ratsgo's blog
이번 글에서는 그래프(graph) 기반 군집화 기법인 Spectral Clustering에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다. 그래�
ratsgo.github.io
Spectral Clustering 알고리즘 응용(Minimum Cut)
지난 포스팅에서 Spectral Clustering Algorithm(스펙트럼 군집화 알고리즘)의 정의와 원리에 대해 설명을 하였습니다. 이번 포스팅에서는 Spectral Cluster로 분류된 그래프 자료를 통해 각각의 집단 그룹�
elecs.tistory.com
#Spectral Clustering 참고 유투브(영어로 되어있지만 자막을 키고 본다면 100%는 아니더라도 어느정도 이해할 만하다. 교수님의 말씀이 빠른편이 아니라...)
https://www.youtube.com/watch?v=cxTmmasBiC8
'Data Science > Machine Learning' 카테고리의 다른 글
| [ML] Mean Shift, DBSCAN, and Silhouette metric (0) | 2020.08.14 |
|---|---|
| [ML] How to encode categorical variables (3) | 2020.07.19 |
| [ML] GA(Genetic Algorithm) (7) | 2020.07.08 |
| [ML] Hidden Markov Model(HMM) (0) | 2020.07.04 |
| [ML] EM Algorithm과 GMM(Gaussian Mixture Model) (0) | 2020.06.21 |
