본문 바로가기
DataScience/MachineLearning

[Clustering] Spectral Clustering의 직관적 의미

by mkk4726 2023. 8. 1.

그림1. 그래프 기반 클러스터링

Spectral Clustering은 그래프 기반의 군집화 방법입니다.

점 사이에 유사도를 구해 그래프를 구성하고 군집을 잘 구분하는 기준에 따라 잘라내는 방식입니다.

 

이 때 유사도 또는 가중치는 점 사이의 거리를 기반으로 구합니다.

더보기
그림2. 가우시안 커널

이 때 가우시안 커널을 사용하는데 다음과 같은 특징이 있습니다.

- 값이 0~1 사이의 값을 갖는다

- 거리가 멀 수록 작은 값을 가지고, 거리가 가까울 수록 큰 값을 가진다.

- $\sigma$에 따라 거리의 분포가 달라진다.

 

첫 번째와 두 번째는 직관적이며, 세번째 부분에 대해 추가로 정리하자면 아래와 같은 특징을 가집니다.

그림3. 시그마에 따라 유사도의 변화

- $\sigma$ 가 작을 수록 세밀하게 군집을 나눌 수 있으나 같은 군집 내에 있더라도 거리가 조금이라도 멀어지면 유사도가 급격히 낮아짐

- $\sigma$ 가 클수록 군집 내에 멀리 떨어져있는 점들도 같은 군집으로 포함시킬 수 있으나, 다른 군집에 있는 점도 같은 군집으로 포함하게 됨

- 즉, 그림 3처럼 $\sigma$ 에 따라 거리에 따른 유사도 계산에 차이가 발생

- $\sigma$ = 각 데이터 i와 j의 주변 점에서 (2d+1)번째로 가까운 점 사이의 거리 , 일 때 사용할 경우 최적의 값이라고 소개 됨

 

Spectral Clustering의 핵심 컨셉은 가중치의 손실이 가장 적도록 그래프를 잘라내는 것입니다.

 

그림4. 그래프 예시

그림 4와 같은 그래프가 있을 때, 군집을 생성하기 위해서는 엣지를 잘라내야합니다. 

이때 잘린 엣지의 가중치 합이 최소가 되도록 자르는 것이 Spectral Clustering의 핵심 아이디어입니다.

그림5. Graph Cut

그림 5와 같이 잘랐을 때는 (1번, 2번)이 군집이 되고 (3번, 4번, 5번, 6번) 이 군집이 형성됩니다.

그리고 손실된 엣지의 가중치 합은 0.8 + 0.6 + 0.1이 됩니다.

그림6. Graph Cut

그림 6과 잘랐을 때는 (1번, 2번, 3번) 이 군집이 되고 (4번, 5번, 6번)이 군집이 형성됩니다.

이 때 가중치 손실은 0.1 + 0.2로 그림5의 경우보다 작게 되고, 가장 최소의 손실이 됩니다.

이렇게 가중치 손실이 최소가 되도록 그래프를 잘랐을 때 형성된 군집이 가장 잘 구분되었음을 직관적으로 알 수 있습니다.

 

이를 통해 2개의 군집을 형성할 수 있고 이를 반복하면 여러 개의 군집을 형성할 수 있습니다. 

 

 


Reference

https://elecs.tistory.com/167

https://techblog-history-younghunjo1.tistory.com/93

https://ratsgo.github.io/machine%20learning/2017/04/27/spectral/

댓글