brunch

You can make anything
by writing

C.S.Lewis

by 매스프레소 Oct 07. 2019

Spectral Clustering

Mathpresso가 문제를 연결하는 방법

콴다에서 사용되는 문제는 다양한 방식으로 DB화 되어 있습니다. 그 중 하나의 방식은 두 문제간의 관계를 바탕으로 정보를 Graph 형태로 저장하는 방식입니다. 하나의 문제를 Graph의 Node로 정의하고, 관련도가 높은 문제들을 이어줌으로써 Edge를 정의하면, 문제사이의 관계도를 형성할 수 있습니다.

비슷한 개체끼리는 한 그룹으로, 다른 개체는 다른 그룹으로 묶어내는 클러스터링(Clustering; 군집화) 기법을 활용하면 문제의 관계도로부터 유용한 정보를 추출할 수 있습니다. 추출된 정보는 필요한 문제를 추천해 주거나, 적절한 교육 컨텐츠를 제시하는 등 다양한 서비스에서 활용될 수 있습니다.

이번 포스트에서는 Graph기반의 군집화 기법인 Spectral Clustering을 이용하여 클러스터링을 진행하는 방법에 대하여 살펴보고자합니다. 또한 아래와 같은 문제간의 관계도가 형성되어 있을 때, 여기서 부터 어떤 식으로 유사한 문제 그룹을 추출해 낼 수 있는지 살펴보겠습니다.

DB상 문제 사이의 관계도

What is Clustering ?

클러스터링은 널리 사용되는 비지도학습 방법중 하나입니다. 서로 관련도가 높은 대상끼리 하나의 그룹으로, 관련도가 덜어지는 대상은 다른 그룹에 묶이도록 하는 것이 클러스터링의 주요 목적입니다. 클러스터링에는 넓게 두 가지 의 접근 방법이 있습니다.

1. Compactness

서로 가까이 있는 대상은 같은 그룹으로 묶이고, 그 그룹의 핵을 중심으로 같은 그룹에 포함된 대상들이 밀집되어 분포하도록 하는 방식입니다. 주로 두 대상간의 거리 ( 유클리드 거리 등 ) 가 대상간의 유사도를 측정하는 척도로 사용됩니다. K-Means 알고리즘이 이 분류의 알고리즘에 속합니다.

2. Connectivity

서로 연결되어 있거나 바로 옆에 있는 대상이 같은 그룹으로 묶입니다. 두 대상의 거리가 매우 가깝더라도 대상이 연결되어 있지 않다면 같은 그룹으로 묶이지 않습니다. Spectral Clustering 알고리즘이 이 방법을 사용한 클러스터링 알고리즘에 해당합니다.

https://slideplayer.com/slide/15538463/

How Spectral Clustering works ?

Spectral clustering 은 다음과 같은 단계를 거쳐 수행됩니다.

우선 데이터간의 거리에 기반한 유사도 행렬을 계산합니다. 유사도 행렬을 계산한 이후 각 노드는 각 그룹을 분리하기 쉬운 더 낮은 차원으로 이동하게됩니다. 사영된 낮은 차원의 공간에서의 거리를 기반으로 K-means와 같은 알고리즘을 통하여 각 클러스터를 생성하고 클러스터링 알고리즘은 종료됩니다.

1.Compute a similarity graph (데이터를 유사도 그래프로 변환하기 )

2.Project the data onto a lower-dimensional space & Create cluster
( 더 낮은 공간으로 데이터를 사영시키고 클러스터를 만들기 )

1. Compute a similarity graph

데이터로부터 유사도 행렬을 계산

상단 좌측 그림과 같이 유사한 성질을 가지는 세 그룹이 있다고 가정해봅시다. 각 그룹은 동인한 그룹에 속한 점들과는 가까운 거리를 가지고, 다른 색을 가지는 그룹과는 먼 거리를 가집다. 이 거리를 계산하여 상단 우측과 같은 유사도 행렬을 계산할 수 있습니다. 문제를 단순화하기 위해서 같은 그룹에 있는 대상간의 유사도는 1로, 서로 다른 그룹에 속한 대상간의 유사도는 0으로 가정하였습니다. 실제 유사도행렬을 계산 과정에서는 두 점사이의 거리와 가우시안 커널을 이용하는 등 다양한 방법을 이용하여 유사도를 계산합니다.

주성분 분석(PCA) 을 통하여 주성분을 추출

유사도 행렬을 계산하고 나면 유사도 행렬에서 주성분을 추출해냅니다. 서로 관련이 높은 대상끼리는 유사도가 높은 값을 가지기 때문에 좌측 상단과 같이 특정 블록(Block) 형태를 가지게 될 것이고, 이 블록을 구성하는 성분들이 유사도 행렬의 주요 성분이 될 것입니다.

※ 주성분 분석 (Principal Component Analysis )

주성분 분석은 통계학에 서 고차원의 데이터를 저차원의 데이터로 환원시키는 방법입니다. 데이터의 분산은 최대한 유지하되, 각 성분은 서로 선형연관성이 없는 공간으로 분해합니다. 아래 그림에서 2차원에서 흩뿌려진 데이터가 1차원 데이터( 분홍색 직선 ) 으로 압축 된 것을 확인할 수 있습니다.

https://stats.stackexchange.com/questions/2691/making-sense-of-principal-component-analysis-eigenvec

주성분분석에 관한 자세한 내용은 여기를 참조하시면 더욱 자세한 설명을 확인할 수 있습니다.

2. Project the data onto a lower-dimensional space & Create cluster

낮은 차원으로 사영시킨 데이터 / 비슷한 그룹은 비슷한 위치로 사영된다

이후 주성분으로 분리된 더 낮은 차원으로 각 점을 변환합니다. 이 과정에서 주성분을 나타내는 벡터가 서로 연관도가 높은 요소들로 구성되었기 때문에 각 축은 연관도가 높은 점들을 비슷한 위치로 이동시킵니다. 이후 저차원으로 이동된 점들에 대하여 K-Means 와 같은 clustering 알고리즘을 이용하여 클러스터를 만듭니다.

Spectral clustering이 진행되는 과정에 대한 전체적인 맥락은 위와 같지만, 실제 진행되는 과정과는 차이가 있습니다. 조금 더 자세한 설명은 여기를 참조하시면 좋겠습니다.

Spectral Clustering Algorithm 을 적용하여 얻어낸 유사한 문제의 그룹

Spectral clustering 알고리즘을 DB사이의 관계도에 적용하면 위와 같이 유사한 문제는 서로 유사한 그룹으로 나눠지는 것을 확인할 수 있습니다.

Pros & Cons on Spectral Clustering

1. Spectral clustering은 데이터의 분포에 대한 강한 가정을 하지 않습니다.

2. 구현이 쉽고 좋은 결과를 내는 방법입니다.

3. 몇 천개 수준의 Sparse한 데이터에 대해 충분히 합리적인 속도로 계산할 수 있습니다.

하지만

1. 마지막 단계에서 K-means 와 같은 Clustering 알고리즘을 사용하는데, 이는 항상 같은 결과를 보장하지는 않습니다.

2. 큰 데이터에 대하여 상당한 계산량을 요구합니다.

3. 몇 개의 그룹으로 쪼개어 지느냐에 따라 결과가 달라질 수 있습니다.

따라서 적용하고자 하는 데이터의 규모와 특성에 따라 그 성능이 차이가 있을 수 있습니다.

Estimate Optimal Number of Cluster

Spectral Clustering을 적용하기 위해서는 하나의 변수가 필요합니다. 몇 개의 Cluster로 Graph 쪼갤 것 인지를 결정하기위한 변수가 그것입니다. 비지도학습의 특성상 이에 대하여 명확한 정답은 없습니다. 하지만 대략적인 클러스터의 개수를 추측할 수 있는 어림짐작법에 ( Heuristic estimation ) 대하여 설명하고자 합니다.

A Tutorial on Spectral Clustering 에서는 EigenGap을 이용한 클러스터의 최적의 클러스터 개수 추정에 대한 방법이 기술되어 있습니다. EigenGap 어림짐작법은 Graph Laplacian 의 Eigenvalue를 크기가 작은 순서대로 나열했을 때 그 차이가 가장 큰 지점으로부터 적절한 클러스터의 개수를 추정할 수 있음을 의미합니다.

그럼 위의 그래프를 나누기 위한 최적의 클러스터의 개수는 어떻게 추정될까요? 아래 두 그래프는 위의 그래프를 Laplacian matrix로 표현하고 Eigenvalue를 구하여 그 차이 및 Eigenvalue를 계산한 것입니다. 가장 큰 gap이 8개에서 나타나고 이를 토대로 위 그래프를 8개로 쪼개는 것이 어림짐작한 최적의 클러스터 개수임을 알 수 있습니다.