Clustering을 위한 Spectral 알고리즘

출퇴근길에 공부하는 머신러닝

들어가며

이번편은 스펙트럴 클러스터링(Spectral Clustering)에 대해서 알아보도록 하겠다. 스펙트럴 클러스터링은 다차원 공간에서의 데이터 집합을 서로 다른 그룹으로 분류할 수 있는 강력한 방법이다. 이 방법은 특히 복잡한 구조를 가진 데이터에서 군집을 찾는데 유용하게 사용된다.

스펙트럴 클러스터링을 시작하기

스펙트럴 클러스터링을 시작하려면 먼저 데이터를 그래프 형태로 변환해야 한다. 여기서 각 데이터 포인트는 노드가 되고, 데이터 포인트 간의 유사도는 엣지로 표현된다. 이를 위해 인접 행렬(Adjacency Matrix)을 생성하고, 이 행렬에 가우시안 커널(Gaussian kernel)등을 이용하여 계산된 유사도를 반영한다.

다양한 그래프 타입

Fully connected graph: 모든 노드가 서로 연결되어 있는 그래프이다.

ε-neighborhood graph: 특정 거리 ε 내의 노드만 연결하는 그래프로, 데이터의 지역적 밀도에 따라 엣지의 수가 달라진다.

K-NN Graph: 각 노드에서 가장 가까운 k개의 이웃만 연결하는 그래프이다.

그래프 컷(Graph Cut)

그래프 컷은 그래프를 여러 서브그래프(subgraph)로 나누는 과정이다. 스펙트럴 클러스터링에서는 이 서브그래프들이 바로 데이터의 군집이 된다. 여기서 중요한 것은 '컷'을 만드는 기준이 되는 가중치이다. 컷의 목표는 비슷한 데이터끼리는 같은 서브그래프에, 서로 다른 데이터는 다른 서브그래프에 배치하는 것이다.

최소 컷(Minimum Cut)

이 방법은 '컷'으로 인해 끊어지는 엣지들의 가중치 합이 최소가 되도록 그래프를 두 개 이상 그룹으로 나누는 것이다. 이 과정에서 각 그룹내의 데이터 포인트들은 서로 밀접한 관계를 맺게 된다.

스펙트럴 클러스터링의 핵심인 고유 분해(Eigen-decomposition)

스펙트럴 클러스터링의 마지막 단계는 인접 행렬의 고유값 분해를 통해 새로운 저차원 공간을 찾고, 이 공간에서 군집화를 수행한느 것이다. 고유벡터를 기반으로 데이터 포인트들을 새로운 공간에 매핑하고, 이를 통해 데이터 포인트들이 속한 군집을 결정한다.

마치며

스펙트럴 클러스터링은 그래프 이론을 기반으로 복잡한 데이터 집합 사이의 숨겨진 패턴을 찾아낸다. 이 방법은 데이터의 복잡한 관계를 고려하여 유사도를 기반으로 데이터를 그룹화하므로, 전통적인 클러스터링 방법으로는 해결하기 어려운 문제에 효과적이다. 다만, 올바른 그래프 구조 선택, 적절한 가중치 부여, 그리고 계산 비용 등을 고려해야 한다는 점을 명심해야할 것이다.