K means Clustering - kumakuma34/DataAnalysis GitHub Wiki

K-means Clustering (K-평균 군집화)

알고리즘 개요

분리형 군집화 알고리즘 비지도학습 기법 중 하나로서, 데이터 셋에서 서로 유사한 관찰치들을 그룹으로 묶어 분류하여 몇가지 군집(cluster)을 찾아내는 것

• 각 군집은 하나의 중심(centroid) 을 가짐
• 개체는 각각 가장 가까운 중심에 할당되며, 같은 중심에 해당된 개체들이 모여 하나의 군집을 이룸
• 각 데이터들을 유클리디안 거리를 기반으로 가장 가까운 중심에 할당, 같은 중심에 모인 데이터 그룹들이 하나의 클러스터가 됨
• 사용자가 사전에 군집 수(k)를 정해야 알고리즘을 실행할 수 있음

학습 과정

EM 알고리즘을 기반으로 작동함

EM 알고리즘 : Expectation 스텝 + Maximization 스텝으로 나뉨. 이 스텝들을 수렴할 때 까지 반복(주로 어려운 문제를 풀 때 많이 사용됨)

1. Expectation 스텝 : 모든 개체를 가장 가까움 중심에 군집으로 할당
2. Maximization 스텝 : 중심을 군집 경계에 맞게 업데이트

이 과정들을 결과가 바뀌지 않게 되거나(= 해가 수렴) , 사용자가 정한 반복수를 모두 채우게 되면 학습이 끝남.

수학적 로직

• N개의 데이터가 있을 때 우리는 이것을 K개의 클러스터로 나누어야 한다. (K값은 미리 지정해주어야 함)
• 이를 위해 목적함수를 정의해주게 되는데, 이 함수를 **왜곡 측정함수(distortion measure)**함수라고 한다.
• J값이 최소가 될 떄의 값을 구해야 한다.
• 벡터가 K번째 클러스터에 속하는 경우 Uk로 표기하고, Uk는 k번째 클러스터의 정중앙에 놓인 벡터(무게중심)이라고 가정한다.
• 따라서 처음에는 이 Uk의 임의의 초기값을 줌으로서 클러스터의 중심을 임의로 잡는다
• 이후 Uk의 값을 고정한 채로 J를 최소화하는 rnk의 값을 구한다
• 이 때, rnk는 0 / 1인데 xn이 k번째 클러스터에 속하게 되는 경우 1 , 아닌 경우 0이 된다.
• rnk의 값이 구해지면 새롭게 얻어진 rnk의 값을 고정하고, 다시 uk를 구한다.
• 이 과정을 정해진 횟수만큼 반복하거나 더이상 학습해도 달라지지 않을 때 까지 반복한다.

특징과 단점

• 각 군집 중심의 초기값을 랜덤하게 정하는 알고리즘인데, 초기값의 위치에 따라 원하는 결과가 나오지 않을 수도 있음
• 군집의 크기가 다를 경우 제대로 동작하지 않을 수도 있음
• 군집의 밀도가 다를 경우에도 제대로 동작하지 않을 수도 있음
• 데이터 분포가 특이한 케이스도 군집이 잘 이루어지지 않음

이 문제들을 해결하기 위해 여러번 군집화를 수행해 가장 빈번하게 등장하는 군집에 할당하는 majority voting을 쓰는 경우가 많음

Reference

https://ratsgo.github.io/machine%20learning/2017/04/19/KC/ https://medium.com/@nsh235482/k-means-clustering-6ab85a2a32ad