Spectral Clustering 알고리즘 응용(Minimum Cut)

 지난 포스팅에서 Spectral Clustering Algorithm(스펙트럼 군집화 알고리즘)의 정의와 원리에 대해 설명을 하였습니다. 이번 포스팅에서는 Spectral Cluster로 분류된 그래프 자료를 통해 각각의 집단 그룹으로 나누어주는 알고리즘인 Minimum cut에 대해 알아보도록 하겠습니다.

 본 포스팅에서는 이전 포스팅에서 설명하였던 Spectral Clustering 알고리즘을 숙지하고 이를 통해 구하게 되는 유사도 행렬(Affinity Matrix)를 알고 있다는 전제하에 설명할 것입니다. Spectral Clustering에 대해 자세히 알고자 하시는 분께서는 아래 포스팅을 참고해 주시길 바랍니다.

Spectral Clustering Algorithm(스펙트럼 군집화 알고리즘)

http://elecs.tistory.com/167

 지난 포스팅에서 다루었던 각 Cluster 그래프를 한 번 더 보도록 합시다.

 위 그래프는 같은 Cluster에 속한 데이터끼리는 굵은 선으로, 서로 다른 Cluser에 속한 데이터끼리는 가느다란 선으로 표시되어 있습니다. 위 데이터를 Spectral Clustering을 통해 Affinity Matrix로 각 데이터 사이의 유사값을 구함으로서 각 Cluster가 서로 구분될 수 있도록 수치화 하였습니다.

 각 데이터간의 유사도를 표현한 Affinity Matrix를 가지고 위 데이터를 명확하게 나눌 수 있는 방법은 존재할까요? Minimum cut 알고리즘은 주어진 데이터 사이의 유사도 값 중 가장 작은 값으로 각 Cluster 그룹을 나누어주는 기능을 합니다. 위의 그래프를 보았을 때 가느다란 선으로 연결된 데이터 사이를 나누게 되면 각 그룹이 뚜렷다게 구분되는 것을 보실 수 있습니다.

 예시를 통해 자세히 알아보도록 하겠습니다. 아래는 데이터 사이의 선분 vertex 사이에 유사값을 부여한 그래프입니다.

 직관상으로 보았을 때 Minimum cut 알고리즘을 적용하게 된다면 유사도 1과 2로 되어있는 부분을 나누면 두 개의 Cluster로 분별될 수 있다는 것을 직감하실 수 있습니다. 아래는 위의 그림에 Minimum cut을 적용한 그림입니다.

 위 그림대로 각 Cluster 사이의 vertex를 자름으로서 두 개의 Cluster로 분류된 것을 확인할 수 있습니다. 이를 식으로 구현하기 위해서는 어떻게 진행하게 될까요? Minimum Cut 알고리즘은 다음과 같은 해법을 제시합니다.

 아래 식에서 A와 B는 2개의 Cluster를 말하며, w는 Affinity Matrix(유사도 행렬)의 요소 중 하나입니다.

 위 식의 결과값은 두 cluster를 나눌 때 잘리는 부분의 유사값 w를 모두 합한 값입니다. 즉 결과값은 두 Cluster로 분리하기 위해 자르는 유사값의 총 합이 최소가 될 경우 위 식이 성립된다는 것을 알 수 있습니다.

 위 식을 증명하는 방법을 알아보겠습니다. 이전 포스팅(Spectral Clustering 알고리즘)에서 서로 다른 Cluster를 분류할 때 다음 두 조건을 만족해야 한다고 하였습니다.

1. 같은 Cluster 내의 요소끼리의 유사도는 큰 값을 갖는다.

2. 다른 Cluster에 속한 요소끼리의 유사도는 작은 값을 갖는다.

 위 조건을 식으로 나타내면 다음과 같습니다.

 위의 식을 설명하자면 각 Cluster 그룹 A와 B에 속하는 affinity matrix 요소의 값을 모두 더한 후 A와 B 사이를 연결하는 affinity matrix 요소의 값을 모두 더한 값의 2배를 뺀 결과값이 최대가 되는 경우를 나타낸 것입니다. 위 식을 응용하면 아래와 같은 식을 만들 수 있습니다.

 위 식은 affinity matrix 내의 모든 값들을 더한 후 이를 위에서 구했던 식을 뺀 값이 최소가 되는 경우를 식으로 표현한 것입니다. 위 식이 maximum이 되는 값을 찾는 경우이므로 아래의 식은 minimum이 된다는 것을 유추할 수 있습니다.

 유도한 식을 구하기 위해 이를 실제 Affinity Matrix 행렬을 통해 설명해보겠습니다. 아래는 Affinity Matrix인 W를 나타냅니다.

 위의 모든 행렬요소의 값을 구합니다. 이는 아래의 과정을 나타내는 것입니다.

 다음으로 각 행렬 내에서 같은 Cluster 그룹에 속하는 요소들을 모두 더합니다.

위에서 붉은 색으로 강조한 부분을 모두 더합니다. 이는 아래의 과정을 나타낸 것입니다.

끝으로 각 행렬 내에서 다른 Cluster 그룹끼리 연결된 요소들의 값을 모두 더합니다.

 위에서 파란 색으로 강조한 부분을 모두 더합니다. 이는 아래의 과정을 나타낸 것입니다.

 위 과정의 계산을 모두 수행하게 되면 최종값은 붉은 색으로 강조한 부분이 빠지고 파란 색으로 강조한 부분이 두드러지게 됨을 알 수 있습니다. 즉, 각 Cluster 사이에서 cut 되는 부분에 해당되는 요소값이 남는다는 것을 알 수 있습니다. 즉 위의 식은 아래와 같은 원리의 값이 됨을 알 수 있습니다.

 그렇다면 주어진 Affinity Matrix 값을 사용하여 어떻게 최소값을 구할 수 있을까요? 이전 포스팅에서 설명드렸던 고유벡터를 사용하면 행렬의 minimum값을 구할 수 있습니다. 그럼 위 Affinity Matrix를 사용하여 고유벡터를 구하는 과정을 보겠습니다.

 위 식에서 주어진 각 값을 행렬 D와 W로 나누어봅니다. 이때 행렬 D는 대각행렬(Diagonal Matrix)로서 각 대각행렬의 행은 Affinity Matrix의 같은 행 내의 모든 값의 합을 나타냅니다. 아래는 이를 정의한 내용입니다.

 위에서 구한 행렬 (D-W) 행렬의 최소값은 아래의 식과 같이 고유벡터 x를 구함으로서 알 수 있습니다.

이 때 나오게 되는 고유벡터에서 2번째로 작은 고유벡터를 통해 Minimum Cut를 구할 수 있습니다. 이는 이전 포스팅에서 언급한 바와 같이 1번째로 작은 고유벡터를 사용할 경우 각 Cluster 그룹의 분리가 눈에 띄게 나타나지 않기 때문입니다.

 지금까지 Minimun Cut을 사용하여 Spectral Cluster 알고리즘을 나타내는 과정을 살펴보았습니다. 그런데 우리가 지금까지 언급하였던 Minimun Cut 알고리즘에는 단점이 하나 존재합니다. Minimum Cut의 경우 무조건 최소값을 찾는 과정을 거치기 때문에 우리들이 바라는 바와 같이 각 Cluster 그룹이 나누어지지 않는 경우가 발생하는데 아래는 그러한 사례 중 하나를 나타낸다.

 이상적인 방향으로 보았을 때 위의 경우처럼 다른 색깔로 분류된 Cluster 그룹끼리 나누어 지는 것이 맞으나 실제로는 이보다 더 작은 최소값을 갖고 있는 부분에서 나누어지는 것을 볼 수 있습니다. 이처럼 우리의 의도적으로 알고리즘이 적용되지 않는 이유는 Outliar와 같이 해당 cluster에서 다소 거리가 있는 부분에 있는 데이터가 있어 이 부분이 의도치않게 나누어져서 하나의 Cluster가 분류되지 않고 쪼개져 버리는 것을 보실 수 있습니다.

 이러한 Minimum Cut을 대체하게 된 것이 바로 Normalized Cut입니다. Normalized Cut 알고리즘에 대한 자세한 사항은 다음 포스팅에서 이어가도록 하겠습니다.