알고리즘 - Modeling - Kmeans

1. 개념

k-평균 알고리즘(K-means clustering algorithm)은 현재의 데이터를 k개의 클러스터로 묶어서 이행하는 알고리즘으로, 각 클러스터들과 거리 차이의 분산을 최소화하는 방법으로 구동한다. k-평균 알고리즘은 자율학습으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할도 한다. 이 알고리즘은 클러스터링과 비슷한 구조를 가지고 있다.

k-평균 클러스터링 알고리즘은 클러스터링 방법 중 분할법에 속한다.

분할법은 주어진 데이터를 여러 파티션 (그룹)으로 나누는 방법이다.

예를 들어 n개의 데이터 오브젝트를 입력받았다고 가정하자.

이 때 분할법은 입력 데이터를 n보다 작거나 같은 k개의 그룹으로 나누는데,

이 때 각 그룹은 클러스터를 형성하게 된다.

다시 말해, 데이터를 한 개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는 것이다.

이 때 그룹을 나누는 과정은 거리 기반의 그룹간 비유사도 (dissimilarity) 와 같은

비용 함수 (cost function) 을 최소화하는 방식으로 이루어지며,

이 과정에서 같은 그룹 내 데이터 오브젝트 끼리의 유사도는 증가하고,

다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소하게 된다.  

k-평균 알고리즘은 각 그룹의 중심 (centroid)과

그룹 내의 데이터 오브젝트와의 거리의 제곱합을 비용 함수로 정하고,

이 함수값을 최소화하는 방향으로 각 데이터 오브젝트의 소속 그룹을 업데이트 해 줌으로써 클러스터링을 수행하게 된다.

 

2. 알고리즘의 구동 과정

가. 입력값

1) k: 클러스터 수

2) D: n 개의 데이터 오브젝트를 포함하는 집합

 

나. 출력값: k 개의 클러스터

 

다. 알고리즘

1) 데이터 오브젝트 집합 D에서 k 개의 데이터 오브젝트를 임의로 추출하고,

이 데이터 오브젝트들을 각 클러스터의 중심 (centroid)으로 설정한다. (초기값 설정)

2) 집합 D의 각 데이터 오브젝트들에 대해 k 개의 클러스터 중심 오브젝트와의 거리를 각각 구하고,

각 데이터 오브젝트가 어느 중심점 (centroid) 와 가장 유사도가 높은지 알아낸다.

그리고 그렇게 찾아낸 중심점으로 각 데이터 오브젝트들을 할당한다.

3) 클러스터의 중심점을 다시 계산한다. 즉, 2에서 재할당된 클러스터들을 기준으로 중심점을 다시 계산한다.

4) 각 데이터 오브젝트의 소속 클러스터가 바뀌지 않을 때까지 2, 3 과정을 반복한다.

 

3. 한계점

k-평균 알고리즘은 몇 가지 한계점을 가지고 있다.

 

가. 클러스터 개수 k값을 입력 파라미터로 지정해주어야 한다.

알고리즘의 에러 수렴이 전역 최솟값이 아닌 지역 최솟값으로 수렴할 가능성이 있다.

이 알고리즘은 초기값을 어떻게 주느냐에 따라

최적화의 결과가 전역 최적값 (global optimum) 이 아닌 지역 최적값 (local optimum)으로 빠질 가능성이 있다.

 

즉, 비용 함수의 함수 공간에서 최적화를 시행할 때, 에러가 줄어드는 방향으로 최적해를 찾아가게 되는데, 전역이 아닌 지역 최솟값에 도달해도 알고리즘의 수렴 조건을 만족하게 되므로 더 이상 최적화를 진행하지 않게 된다. 따라서, 사용자가 기대한 결과를 얻지 못하게 되는 것이다. 이를 방지하기 위해  Simulated Annealing을 수행하여 의도적으로 에러가 줄어드는 방향을 피하는 방식을 이용하거나, 서로 다른 초기값으로 여러 번 시도해본 뒤 가장 에러값이 낮은 결과를 사용하는 기법 등을 이용함으로써 이 문제를 완화할 수 있다.

 

나.이상값 (outlier) 에 민감하다.

k-평균 알고리즘은 이상값 (outlier) 에 민감하게 반응한다.

이상값이란 다른 대부분의 데이터와 비교했을 때 멀리 떨어져 있는 데이터를 의미한다.

이러한 이상값은 알고리즘 내에서 중심점을 갱신하는 과정에서 클러스터 내의 전체 평균 값을 크게 왜곡시킬 수 있다.

따라서 클러스터의 중심점이 클러스터의 실제 중심에 있지 않고 이상값 방향으로 치우치게 위치할 수 있다.

 

다.구형 (spherical) 이 아닌 클러스터를 찾는 데에는 적절하지 않다.

k-평균 알고리즘은 비용 함수를 계산할 때 중심점과 각 데이터 오브젝트간의 거리를 계산하게 된다.

이 때 사용하는 거리는 유클리드 거리이다.

따라서, 알고리즘 수행 시 중심점으로부터 구형으로 군집화가 이루어지게 된다.

만약 주어진 데이터 집합의 분포가 구형이 아닐 경우에는 클러스터링 결과가 예상과 다를 수 있다. 

 

4. 클러스터의 수

주어진 데이터 집합에서 구하고자 하는 클러스터의 숫자를 설정할 때 다음의 방법론들을 이용할 수 있다.

 

가. Rule of thumb 

 

나. Elbow Method 

다. 정보 기준 접근법 (Information Criterion Approach)