Mathpresso가 문제를 연결하는 방법
콴다에서 사용되는 문제는 다양한 방식으로 DB화 되어 있습니다. 그 중 하나의 방식은 두 문제간의 관계를 바탕으로 정보를 Graph 형태로 저장하는 방식입니다. 하나의 문제를 Graph의 Node로 정의하고, 관련도가 높은 문제들을 이어줌으로써 Edge를 정의하면, 문제사이의 관계도를 형성할 수 있습니다.
비슷한 개체끼리는 한 그룹으로, 다른 개체는 다른 그룹으로 묶어내는 클러스터링(Clustering; 군집화) 기법을 활용하면 문제의 관계도로부터 유용한 정보를 추출할 수 있습니다. 추출된 정보는 필요한 문제를 추천해 주거나, 적절한 교육 컨텐츠를 제시하는 등 다양한 서비스에서 활용될 수 있습니다.
이번 포스트에서는 Graph기반의 군집화 기법인 Spectral Clustering을 이용하여 클러스터링을 진행하는 방법에 대하여 살펴보고자합니다. 또한 아래와 같은 문제간의 관계도가 형성되어 있을 때, 여기서 부터 어떤 식으로 유사한 문제 그룹을 추출해 낼 수 있는지 살펴보겠습니다.
클러스터링은 널리 사용되는 비지도학습 방법중 하나입니다. 서로 관련도가 높은 대상끼리 하나의 그룹으로, 관련도가 덜어지는 대상은 다른 그룹에 묶이도록 하는 것이 클러스터링의 주요 목적입니다. 클러스터링에는 넓게 두 가지 의 접근 방법이 있습니다.
서로 가까이 있는 대상은 같은 그룹으로 묶이고, 그 그룹의 핵을 중심으로 같은 그룹에 포함된 대상들이 밀집되어 분포하도록 하는 방식입니다. 주로 두 대상간의 거리 ( 유클리드 거리 등 ) 가 대상간의 유사도를 측정하는 척도로 사용됩니다. K-Means 알고리즘이 이 분류의 알고리즘에 속합니다.
서로 연결되어 있거나 바로 옆에 있는 대상이 같은 그룹으로 묶입니다. 두 대상의 거리가 매우 가깝더라도 대상이 연결되어 있지 않다면 같은 그룹으로 묶이지 않습니다. Spectral Clustering 알고리즘이 이 방법을 사용한 클러스터링 알고리즘에 해당합니다.
Spectral clustering 은 다음과 같은 단계를 거쳐 수행됩니다.
우선 데이터간의 거리에 기반한 유사도 행렬을 계산합니다. 유사도 행렬을 계산한 이후 각 노드는 각 그룹을 분리하기 쉬운 더 낮은 차원으로 이동하게됩니다. 사영된 낮은 차원의 공간에서의 거리를 기반으로 K-means와 같은 알고리즘을 통하여 각 클러스터를 생성하고 클러스터링 알고리즘은 종료됩니다.
1.Compute a similarity graph (데이터를 유사도 그래프로 변환하기 )
2.Project the data onto a lower-dimensional space & Create cluster
( 더 낮은 공간으로 데이터를 사영시키고 클러스터를 만들기 )
상단 좌측 그림과 같이 유사한 성질을 가지는 세 그룹이 있다고 가정해봅시다. 각 그룹은 동인한 그룹에 속한 점들과는 가까운 거리를 가지고, 다른 색을 가지는 그룹과는 먼 거리를 가집다. 이 거리를 계산하여 상단 우측과 같은 유사도 행렬을 계산할 수 있습니다. 문제를 단순화하기 위해서 같은 그룹에 있는 대상간의 유사도는 1로, 서로 다른 그룹에 속한 대상간의 유사도는 0으로 가정하였습니다. 실제 유사도행렬을 계산 과정에서는 두 점사이의 거리와 가우시안 커널을 이용하는 등 다양한 방법을 이용하여 유사도를 계산합니다.
유사도 행렬을 계산하고 나면 유사도 행렬에서 주성분을 추출해냅니다. 서로 관련이 높은 대상끼리는 유사도가 높은 값을 가지기 때문에 좌측 상단과 같이 특정 블록(Block) 형태를 가지게 될 것이고, 이 블록을 구성하는 성분들이 유사도 행렬의 주요 성분이 될 것입니다.
※ 주성분 분석 (Principal Component Analysis )
주성분 분석은 통계학에 서 고차원의 데이터를 저차원의 데이터로 환원시키는 방법입니다. 데이터의 분산은 최대한 유지하되, 각 성분은 서로 선형연관성이 없는 공간으로 분해합니다. 아래 그림에서 2차원에서 흩뿌려진 데이터가 1차원 데이터( 분홍색 직선 ) 으로 압축 된 것을 확인할 수 있습니다.
주성분분석에 관한 자세한 내용은 여기를 참조하시면 더욱 자세한 설명을 확인할 수 있습니다.
이후 주성분으로 분리된 더 낮은 차원으로 각 점을 변환합니다. 이 과정에서 주성분을 나타내는 벡터가 서로 연관도가 높은 요소들로 구성되었기 때문에 각 축은 연관도가 높은 점들을 비슷한 위치로 이동시킵니다. 이후 저차원으로 이동된 점들에 대하여 K-Means 와 같은 clustering 알고리즘을 이용하여 클러스터를 만듭니다.
Spectral clustering이 진행되는 과정에 대한 전체적인 맥락은 위와 같지만, 실제 진행되는 과정과는 차이가 있습니다. 조금 더 자세한 설명은 여기를 참조하시면 좋겠습니다.
Spectral clustering 알고리즘을 DB사이의 관계도에 적용하면 위와 같이 유사한 문제는 서로 유사한 그룹으로 나눠지는 것을 확인할 수 있습니다.
1. Spectral clustering은 데이터의 분포에 대한 강한 가정을 하지 않습니다.
2. 구현이 쉽고 좋은 결과를 내는 방법입니다.
3. 몇 천개 수준의 Sparse한 데이터에 대해 충분히 합리적인 속도로 계산할 수 있습니다.
하지만
1. 마지막 단계에서 K-means 와 같은 Clustering 알고리즘을 사용하는데, 이는 항상 같은 결과를 보장하지는 않습니다.
2. 큰 데이터에 대하여 상당한 계산량을 요구합니다.
3. 몇 개의 그룹으로 쪼개어 지느냐에 따라 결과가 달라질 수 있습니다.
따라서 적용하고자 하는 데이터의 규모와 특성에 따라 그 성능이 차이가 있을 수 있습니다.
Spectral Clustering을 적용하기 위해서는 하나의 변수가 필요합니다. 몇 개의 Cluster로 Graph 쪼갤 것 인지를 결정하기위한 변수가 그것입니다. 비지도학습의 특성상 이에 대하여 명확한 정답은 없습니다. 하지만 대략적인 클러스터의 개수를 추측할 수 있는 어림짐작법에 ( Heuristic estimation ) 대하여 설명하고자 합니다.
A Tutorial on Spectral Clustering 에서는 EigenGap을 이용한 클러스터의 최적의 클러스터 개수 추정에 대한 방법이 기술되어 있습니다. EigenGap 어림짐작법은 Graph Laplacian 의 Eigenvalue를 크기가 작은 순서대로 나열했을 때 그 차이가 가장 큰 지점으로부터 적절한 클러스터의 개수를 추정할 수 있음을 의미합니다.
그럼 위의 그래프를 나누기 위한 최적의 클러스터의 개수는 어떻게 추정될까요? 아래 두 그래프는 위의 그래프를 Laplacian matrix로 표현하고 Eigenvalue를 구하여 그 차이 및 Eigenvalue를 계산한 것입니다. 가장 큰 gap이 8개에서 나타나고 이를 토대로 위 그래프를 8개로 쪼개는 것이 어림짐작한 최적의 클러스터 개수임을 알 수 있습니다.
같은 방식으로 하단의 그래프에 대한 최적의 클러스터개수를 추정해보면,
최적의 클러스터의 개수는 2개입니다. 실제 하단의 그래프는 밀집된 상단의 클러스터와 하단의 밀집된 클러스터로 분해되는 것이 합리적으로 보입니다.
Mathpresso에서는 위와 같은 클러스터링 알고리즘을 비롯한 다양한 방법을 이용하여 문제와 문제와 문제, 문제와 컨텐츠간의 연결을 만들어 나가고 있습니다. Mathpresso는 이런 방법들을 통하여 교육에서의 새로운 가치를 만들어내고자 합니다.
Resources
https://arxiv.org/pdf/0711.0189.pdf
https://ratsgo.github.io/machine%20learning/2017/04/27/spectral/
https://towardsdatascience.com/spectral-clustering-aba2640c0d5b
https://calculatedcontent.com/2012/10/09/spectral-clustering/