클러스터링 (Clustering)

군집화라는 것은 말 그대로 어떤 데이터들을 몇 개의 군집으로 모으는 것을 의미한다. 쉽게는 그룹으로 나눈다고 이해하면 된다. 이는 참으로 많은 곳에 쓰인다. 그도 그럴 것이 수많은 데이터마다 따로따로 처리해줄 수는 없지 않은가. 수많은 데이터를 그룹으로 나눈 뒤에 특정 그룹별로 처리를 한다거나 그 그룹의 특성을 알아내는 것이 훨씬 더 쉽기에 데이터를 올바르고 빠르게 군집화하는 것은 머신러닝이나 빅데이터 분야에서 항상 중요한 문제로 다루어지고 있다. 이번에는 기본이 되는 군집화 알고리즘을 소개하고자 한다.

K 평균 군집화 (K-mean clustering)

대부분의 사람들이 군집화 알고리즘을 배울 때 가장 처음 접하는 K 평균 군집화 알고리즘이다. 데이터가 벡터로 표현되어 있을 때, 아래의 목적식을 최소화하도록 데이터들을 군집화하는 알고리즘을 말한다.

m은 군집의 평균을 의미한다.

즉, 어떤 군집을 형성했을 때, "그 군집의 평균과 그 군집에 속하는 데이터 간의 거리의 총합"이 가장 작게 만드는 것을 의미한다. 이것은 꽤나 간단한 방법으로 군집을 형성할 수 있다. 먼저, 군집의 평균을 무작위적으로 만든다. 그리고 각각의 데이터에 대해서 그 데이터와 가장 가까운 군집의 평균을 찾는다. 그리고 그 데이터를 그 군집에 포함시킨다. 이 과정을 할당 (assignment) 과정이라고 부른다. 그 후, 각각의 군집마다 그 군집에 포함된 데이터를 가지고 군집의 평균을 다시 구한다. 이 과정을 변화 (update) 과정이라고 부른다. 이 두 과정을 반복하다보면 데이터들을 군집화할 수 있게되고 이를 K평균 군집화 알고리즘이라고 한다.

알고리즘 자체가 간단하고 사용하고자하는 목적식이 직관적이기에 군집화 알고리즘을 배우는 입장에서 시작하기에 좋다는 장점이 있지만 여러 약점이 있다. 그 중 하나는 outlier에 취약하여 outlier가 존재할 경우 군집의 평균이 이상해질 수 있다. 하나의 데이터가 군집과는 멀리 떨어져 있다고 생각해보면 그 하나의 데이터까지 고려하기 위해서 평균이 이상한 곳에 생성될 수 있다.

평균 이동 알고리즘 (Mean shift algorithm)

Search window 안에 있는 점들의 평균을 계산한 뒤에 그 평균으로 search window의 중심을 이동한다. 이 과정을 충분히 반복하여 평균을 찾아나선다. 그래디언트 하강법과 같은 방식으로 진행한다. 이 알고리즘의 경우 search window 크기에 따라서 최종 평균값이 민감하게 변화하며 이것에 따라서 클러스터의 개수가 결정될 수 있다.

스펙트럼 군집화 (Spectral clustering)

위와 같은 군집화 알고리즘들은 대체적으로 군집이 원형의 모양을 띤다. 그러나 일반적인 데이터에서 항상 군집이 원형의 모양만 띠는 것은 아니다. 이를 보완하기 위한 알고리즘들이 있다. 그래프를 이용하여 모든 점들간의 거리나 유사도 관계를 설정하고 군집화를 진행하는 방법이 있으나 이는 계산 복잡도가 굉장히 커지므로 모두 연결된 그래프보다는 k개만 연결하거나 특정 길이 이하의 유사도만 연결하는 그래프를 만들기도 한다.