K-평균 군집화(K-means Clustering)
19 Apr 2017 | Clustering
이번 글에서는 K-평균 군집화(K-means Clustering)에 대해 살펴보겠습니다. (줄여서 KC라 부르겠습니다) 이번 글은 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
알고리즘 개요
KC는 대표적인 분리형 군집화 알고리즘 가운데 하나입니다. 각 군집은 하나의 중심(centroid)을 가집니다. 각 개체는 가장 가까운 중심에 할당되며, 같은 중심에 할당된 개체들이 모여 하나의 군집을 형성합니다. 사용자가 사전에 군집 수($k$)가 정해야 알고리즘을 실행할 수 있습니다. $k$가 하이퍼파라메터(hyperparameter)라는 이야기입니다. 이를 수식으로 적으면 아래와 같습니다.
\[X={ C }_{ 1 }{ \cup C }_{ 2 }{ ...\cup C }_{ K },\quad { C }_{ i }\cap { C }_{ j }=\phi \\ \\ argmin_{ C }{ \sum _{ i=1 }^{ K }{ \sum _{ { x }_{ j }\in { C }_{ i } }^{ }{ { \left\| { x }_{ j }-{ c }_{ i } \right\| }^{ 2 } } } }\]
학습 과정
KC는 EM 알고리즘을 기반으로 작동합니다. EM알고리즘은 크게 Expectation 스텝과 Maximization 스텝으로 나뉘는데요. 이를 수렴할 때까지 반복하는 방식입니다. 동시에 해를 찾기 어려운 문제를 풀 때 많이 사용되는 방법론입니다. KC의 경우 (1) 각 군집 중심의 위치 (2)각 개체가 어떤 군집에 속해야 하는지 멤버십, 이 두 가지를 동시에 찾아야 하기 때문에 EM 알고리즘을 적용합니다.
군집 수 $k$를 2로 정했습니다. 우선 군집의 중심(빨간색 점)을 랜덤 초기화합니다.
모든 개체들(파란색 점)을 아래 그림처럼 가장 가까운 중심에 군집(녹색 박스)으로 할당합니다. 이것이 Expectation 스텝입니다.
이번엔 중심을 군집 경계에 맞게 업데이트해 줍니다. 이것이 Maximization 스텝입니다.
다시 Expectation 스텝을 적용합니다. 바꿔 말해 모든 개체들을 가장 가까운 중심에 군집(보라색 박스)으로 할당해주는 작업입니다.
Maximization 스텝을 또 적용해 중심을 업데이트합니다. Expectation과 Maximization 스텝을 반복 적용해도 결과가 바뀌지 않거나(=해가 수렴), 사용자가 정한 반복수를 채우게 되면 학습이 끝납니다.
KC의 특징과 단점
KC는 각 군집 중심의 초기값을 랜덤하게 정하는 알고리즘인데요. 아래 그림처럼 초기값 위치에 따라 원하는 결과가 나오지 않을 수도 있습니다.
군집의 크기가 다를 경우 제대로 작동하지 않을 수 있습니다.
군집의 밀도가 다를 경우에도 마찬가지입니다.
데이터 분포가 특이한 케이스도 군집이 잘 이루어지지 않습니다.
이 때문에 KC를 실제 문제에 적용할 때는 여러번 군집화를 수행해 가장 빈번히 등장하는 군집에 할당하는 majority voting 방법을 쓰는 경우가 많다고 합니다. KC의 계산복잡성은 $O(n)$으로 계층적 군집화(Hiarchical clustering)와 비교해 그리 무겁지 않은 알고리즘이기 때문입니다.
이번 글에서는 K-평균 군집화(K-means Clustering)에 대해 살펴보겠습니다. (줄여서 KC라 부르겠습니다) 이번 글은 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
알고리즘 개요
KC는 대표적인 분리형 군집화 알고리즘 가운데 하나입니다. 각 군집은 하나의 중심(centroid)을 가집니다. 각 개체는 가장 가까운 중심에 할당되며, 같은 중심에 할당된 개체들이 모여 하나의 군집을 형성합니다. 사용자가 사전에 군집 수($k$)가 정해야 알고리즘을 실행할 수 있습니다. $k$가 하이퍼파라메터(hyperparameter)라는 이야기입니다. 이를 수식으로 적으면 아래와 같습니다.
\[X={ C }_{ 1 }{ \cup C }_{ 2 }{ ...\cup C }_{ K },\quad { C }_{ i }\cap { C }_{ j }=\phi \\ \\ argmin_{ C }{ \sum _{ i=1 }^{ K }{ \sum _{ { x }_{ j }\in { C }_{ i } }^{ }{ { \left\| { x }_{ j }-{ c }_{ i } \right\| }^{ 2 } } } }\]학습 과정
KC는 EM 알고리즘을 기반으로 작동합니다. EM알고리즘은 크게 Expectation 스텝과 Maximization 스텝으로 나뉘는데요. 이를 수렴할 때까지 반복하는 방식입니다. 동시에 해를 찾기 어려운 문제를 풀 때 많이 사용되는 방법론입니다. KC의 경우 (1) 각 군집 중심의 위치 (2)각 개체가 어떤 군집에 속해야 하는지 멤버십, 이 두 가지를 동시에 찾아야 하기 때문에 EM 알고리즘을 적용합니다.
군집 수 $k$를 2로 정했습니다. 우선 군집의 중심(빨간색 점)을 랜덤 초기화합니다.
모든 개체들(파란색 점)을 아래 그림처럼 가장 가까운 중심에 군집(녹색 박스)으로 할당합니다. 이것이 Expectation 스텝입니다.
이번엔 중심을 군집 경계에 맞게 업데이트해 줍니다. 이것이 Maximization 스텝입니다.
다시 Expectation 스텝을 적용합니다. 바꿔 말해 모든 개체들을 가장 가까운 중심에 군집(보라색 박스)으로 할당해주는 작업입니다.
Maximization 스텝을 또 적용해 중심을 업데이트합니다. Expectation과 Maximization 스텝을 반복 적용해도 결과가 바뀌지 않거나(=해가 수렴), 사용자가 정한 반복수를 채우게 되면 학습이 끝납니다.
KC의 특징과 단점
KC는 각 군집 중심의 초기값을 랜덤하게 정하는 알고리즘인데요. 아래 그림처럼 초기값 위치에 따라 원하는 결과가 나오지 않을 수도 있습니다.
군집의 크기가 다를 경우 제대로 작동하지 않을 수 있습니다.
군집의 밀도가 다를 경우에도 마찬가지입니다.
데이터 분포가 특이한 케이스도 군집이 잘 이루어지지 않습니다.
이 때문에 KC를 실제 문제에 적용할 때는 여러번 군집화를 수행해 가장 빈번히 등장하는 군집에 할당하는 majority voting 방법을 쓰는 경우가 많다고 합니다. KC의 계산복잡성은 $O(n)$으로 계층적 군집화(Hiarchical clustering)와 비교해 그리 무겁지 않은 알고리즘이기 때문입니다.
Comments