K-평균 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

도입[편집]

역사[편집]

"K-평균"에 대한 개념은 1957년 Hugo Steinhaus에 의해 소개되었으나,[1] 용어 자체는 1967년에 James MacQueen에 의해 처음 사용되었다.[2] 현재 사용되고 있는 표준 알고리즘은 1957년에 Stuart Lloyd가 펄스 부호 변조(PCM)를 목적으로 처음으로 고안 하였으나 1982년이 되어서야 컴퓨터 과학 매거진에 처음 공개되었다.[3] 알고리즘이 공개되기 이전인 1965년에 E. W. Forgy 또한 같은 알고리즘을 제안하였다.[4] 차후 1975년과 1979년에 Hartigan과 Wong에 의해 거리 계산이 필요하지 않은 좀 더 효율적인 방법이 소개 되었다.[5][6]

개요[편집]

k-평균 클러스터링 알고리즘은 클러스터링 방법 중 분할법에 속한다. 분할법은 주어진 데이터를 여러 파티션 (그룹) 으로 나누는 방법이다. 예를 들어 n개의 데이터 오브젝트를 입력받았다고 가정하자. 이 때 분할법은 입력 데이터를 n보다 작거나 같은 k개의 그룹으로 나누는데, 이 때 각 군집은 클러스터를 형성하게 된다. 다시 말해, 데이터를 한 개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는 것이다. 이 때 그룹을 나누는 과정은 거리 기반의 그룹간 비유사도 (dissimilarity) 와 같은 비용 함수 (cost function) 을 최소화하는 방식으로 이루어지며, 이 과정에서 같은 그룹 내 데이터 오브젝트 끼리의 유사도는 증가하고, 다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소하게 된다.[7] k-평균 알고리즘은 각 그룹의 중심 (centroid)과 그룹 내의 데이터 오브젝트와의 거리의 제곱합을 비용 함수로 정하고, 이 함수값을 최소화하는 방향으로 각 데이터 오브젝트의 소속 그룹을 업데이트 해 줌으로써 클러스터링을 수행하게 된다.

목표[편집]

n개의 d-차원 데이터 오브젝트 (x1, x2, …, xn) 집합이 주어졌을 때, k-평균 알고리즘은 n개의 데이터 오브젝트들을 각 집합 내 오브젝트 간 응집도를 최대로 하는 k(<=n) 개의 집합 S = {S1S2, …, Sk} 으로 분할한다. 다시 말해, μi가 집합 Si의 중심점이라 할 때

\underset{\mathbf{S}} {\operatorname{arg\,min}}  \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2

각 집합별 중심점~집합 내 오브젝트간 거리의 제곱합을 최소로 하는 집합 S를 찾는 것이 이 알고리즘의 목표다. 이 목적 함수의 전역 최소값 (global minimum) 을 찾는 것은 NP-난해 문제이므로, 언덕 오르기 (hill climbing) 방식으로 목적 함수의 에러를 줄여나가며 지역 최솟값 (local minimum) 을 발견했을 때 알고리즘을 종료함으로써 근사 최적해를 구한다.

알고리즘[편집]

표준 알고리즘[편집]

i번째 클러스터의 중심을 \mu_i, 클러스터에 속하는 점의 집합을 S_i라고 할 때, 전체 분산은 다음과 같이 계산된다.

V = \sum_{i=1}^{k} \sum_{j \in S_i} |x_j - \mu_i |^2

이 값을 최소화하는 S_i을 찾는 것이 알고리즘의 목표가 된다.

알고리즘은 우선 초기의 \mu_i를 설정하는 것으로 시작한다. 이후 다음의 두 단계를 반복한다.

  • 클러스터 설정: 각 데이터로부터 각 클러스터들의  \mu_i 까지의 유클리드 거리를 계산하여, 해당 데이터에서 가장 가까운 클러스터를 찾아 데이터를 배당한다.
S^{(t)}_i = \{ x_p : |x_p - \mu_i^{(t)}|^2 \leq |x_p - \mu_j^{(t)}|^2 \forall j, 1 \leq j \leq k \}
  • 클러스터 중심 재조정: \mu_i를 각 클러스터에 있는 데이터들의 무게중심 값으로 재설정해준다.
\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum\limits_{x_j \in S^{(t)}_i} x_j
만약 클러스터가 변하지 않는다면 반복을 중지한다.

맨 처음, 각 들을 k집합으로 나눈다. 이때 임의로 나누거나, 어떤 휴리스틱 기법을 사용할 수도 있다. 그 다음 각 집합의 무게 중심을 구한다. 그 다음, 각각의 점들을 방금 구한 무게중심 가운데 제일 가까운 것에 연결지음으로써 새로이 집합을 나눌 수 있다. 이 작업을 반복하면 점들이 소속된 집합을 바꾸지 않거나, 무게중심이 변하지 않는 상태로 수렴될 수 있다.

kmeans_animation
입력값
  1. k: 클러스터 수
  2. D: n 개의 데이터 오브젝트를 포함하는 집합

출력값: k 개의 클러스터

알고리즘

 1) 데이터 오브젝트 집합 D에서 k 개의 데이터 오브젝트를 임의로 추출하고, 이 데이터 오브젝트들을 각 클러스터의 중심 (centroid) 으로 설정한다. (초기값 설정)
 2) 집합 D의 각 데이터 오브젝트들에 대해 k 개의 클러스터 중심 오브젝트와의 거리를 각각 구하고, 각 데이터 오브젝트가 어느 중심점 (centroid) 와 가장 유사도가 높은지 알아낸다. 그리고 그렇게 찾아낸 중심점으로 각 데이터 오브젝트들을 할당한다.
 3) 클러스터의 중심점을 다시 계산한다. 즉, 2)에서 재할당된 클러스터들을 기준으로 중심점을 다시 계산한다.
 4) 각 데이터 오브젝트의 소속 클러스터가 바뀌지 않을 때 까지 2), 3) 과정을 반복한다.

2)는 위의 클러스터 설정 과정에 해당하고, 3) 과정이 위의 클러스터 중심 재조정 과정에 해당한다.[7]

초기화 기법[편집]

무작위 분할 (Random Partition)[편집]

무작위 분할 알고리즘은 가장 많이 쓰이는 초기화 기법으로[8], 각 데이터들을 임의의 클러스터에 배당한 후, 각 클러스터에 배당된 점들의 평균 값을 초기  \mu_i 로 설정한다. 무작위 분할 기법의 경우 다른 기법들과는 달리 데이터 순서에 대해 독립적이다. 무작위 분할의 경우 초기 클러스터가 각 데이터들에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게중심들이 데이터 집합의 중심에 가깝게 위치하는 경향을 띈다. 이러한 특성 때문에 K-조화 평균이나 퍼지 K-평균에서는 무작위 분할이 선호된다.[9]

Forgy[편집]

Forgy 알고리즘은 1965년 Forgy에 의해 고안되었으며[10] 현재 주로 쓰이는 초기화 기법 중 하나로, 데이터 집합으로부터 임의의 k개의 데이터를 선택하여 각 클러스터의 초기  \mu_i 로 설정한다. 무작위 분할 기법과 마찬가지로 Forgy 알고리즘은 데이터 순서에 대해 독립적이다.[8] Forgy 알고리즘의 경우 초기 클러스터가 임의의 k개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향을 띈다. 이러한 특성 때문에 EM 알고리즘이나 표준 K-평균 알고리즘에서는 Forgy 알고리즘이 선호된다.[9]

MacQueen[편집]

1967년 MacQueen에 의해 고안된 MacQueen 알고리즘은[2] Forgy 알고리즘과 마찬가지로 데이터 집합으로 부터 임의의 k개의 데이터를 선택하여 각 클러스터의 초기  \mu_i 로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 해당 점으로부터 가장 가까운 클러스터를 찾아 데이터를 배당한다. 모든 데이터들이 클러스터에 배당되고 나면 각 클러스터의 무게중심을 다시 계산하여 초기  \mu_i 로 다시 설정한다. MacQueen 알고리즘의 경우 최종 수렴에 가까운 클러스터를 찾는 것은 비교적 빠르나, 최종 수렴에 해당하는 클러스터를 찾는 것은 매우 느리다.[11]

Kaufman[편집]

1990년에 Kaufman과 Rousseeuw에 의해 고안된 Kaufman 알고리즘[12]은 전체 데이터 집합 중 가장 중심에 위치한 데이터를 첫번째  \mu_i 로 설정한다. 이후 선택되지 않은 각 데이터들에 대해, 가장 가까운 무게중심 보다 선택되지 않은 데이터 집합에 더 근접하게 위치한 데이터를 또 다른  \mu_i 로 설정하는 것을 총 k개의  \mu_i 가 설정될 때 까지 반복한다. 무작위 분할과 마찬가지로, Kaufman 알고리즘은 초기 클러스터링과 데이터 순서에 대해 비교적 독립적이기 때문에 해당 요소들에 의존적인 다른 알고리즘들 보다 월등한 성능을 보인다.[8]

복잡도[편집]

K-평균 알고리즘의 계산 복잡도에 크게 영향을 미치는 요소 두가지는 유클리드 공간 d와 클러스터의 수 k이다. 클러스터의 수가 작더라도, 일반적인 유클리드 공간 d에서 K-평균 알고리즘의 최적 해를 찾는 것은 NP-난해이다.[13][14] 반대로 낮은 차원의 유클리드 공간일지라도, k개의 클러스터에 대해 최적 해를 찾는 것 또한 NP-난해이다.[15]

이러한 이유로 K-평균 알고리즘에서는 위와 같은 휴리스틱 기법을 주로 사용한다. Lloyd 알고리즘의 경우, 시간 복잡도는 클러스터의 수, 데이터 벡터의 차원, 데이터 벡터의 수에 각각 비례한다. 또한 알고리즘이 해가 수렴하기까지 반복되므로, 알고리즘이 반복된 횟수에도 비례한다. 즉, n개의 d-차원 데이터 벡터들을 i번의 반복을 통해 k개의 클러스터로 묶는데 걸리는 시간은 O(nkdi)이다. 보통 데이터 오브젝트의 개수보다 클러스터의 개수가 훨씬 적으므로 k<<n이고, 알고리즘 반복 횟수 역시 데이터 오브젝트 개수보다 훨씬 적으므로 i<<n이다. 따라서, K-평균 알고리즘은 많은 환경에서 빠르게 수렴하고, 대규모 데이터를 처리하는데 적합하므로 널리 사용된다.

  • Smoothed analysis 경우의 복잡도는 다항 시간이다. [0, 1]^d내의 임의의 n개의 점들의 집합에 대해, 집합 내의 각 점들이 평균0, 분산\sigma^2의 정규분포를 이룬다면, 해당 집합을 k개의 클러스터로 묶는데 걸리는 시간이 O(n^{34}k^{34}d^8log^4(n)/\sigma^2)임이 증명된 바 있다.[16]
  • 다항을 넘는(superpolynomial) 시간(2^{\Omega(\sqrt{n})})이 걸리는 경우도 존재한다.[17]
  • 공간 복잡도의 경우, 알고리즘은 각 클러스터의 무게중심 벡터들에 대한 정보를 추가로 저장해야 하고, 이 무게중심 벡터들은 매 반복마다 독립적이기 때문에, K-평균 알고리즘은 O((n+k)d)공간 복잡도를 가진다.

한계점[편집]

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


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

이 알고리즘은 k값에 따라 결과값이 완전히 달라진다. 예를 들어, 실제 데이터가 4개의 클러스터를 가지고 있는데, k=3으로 입력했다고 가정하자. 그러면 아래와 같은 결과가 나올 수 있다.

k가 작을 때

이는 실제 클러스터의 수 보다 k값이 작을 때 발생하는 현상이다. 반대로, 실제 클러스터가 5개인데 k=8을 입력했다고 가정하자. 결과는 아래와 같다.

k가 클 때

따라서, K값을 어떻게 주느냐에 따라 클러스터링의 결과가 극명하게 달라지며, 좋지 못한 결과를 보여줄 가능성이 있다.


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

이 알고리즘은 초기값을 어떻게 주느냐에 따라 최적화의 결과가 전역 최적값 (global optimum) 이 아닌 지역 최적값 (local optimum) 으로 빠질 가능성이 있다. 예를 들어, 실제 데이터는 3개의 클러스터를 가지고 있고, k도 3이라고 하자. 데이터와 초기 중심값의 분포는 아래와 같다.

초기 상태

그러나 알고리즘을 수행하면서 비용 함수 최소화를 진행하면 아래와 같이 지역 최솟값에 빠져 그대로 수렴하게 된다.

결과

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


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

k-평균 알고리즘은 이상값 (outlier) 에 민감하게 반응한다. 이상값이란 다른 대부분의 데이터와 비교했을 때 멀리 떨어져 있는 데이터를 의미한다. 이러한 이상값은 알고리즘 내에서 중심점을 갱신하는 과정에서 클러스터 내의 전체 평균 값을 크게 왜곡시킬 수 있다. 따라서 클러스터의 중심점이 클러스터의 실제 중심에 있지 않고 이상값 방향으로 치우치게 위치할 수 있다. 아래의 경우를 살펴보면

클러스터에서 크게 멀어진 중심점

실제 데이터 클러스터는 오른쪽 중간에 위치해있는데 반해 클러스터의 중심은 클러스터로부터 왼쪽으로 상당히 떨어진 지점에 위치한다. 이는 실제 클러스터 외부에 퍼져 있는 이상값들이 중심점 계산에 있어 그 값을 크게 왜곡시켰기 때문이다. 이를 방지하기 위해 k-평균 알고리즘을 실시하기 전에 이상값을 제거하는 프로세스를 먼저 실행하거나, 분할법의 일종인 k-대푯값 알고리즘 (k-medoids algorithm) 을 이용하면 이상값의 영향을 줄일 수 있다.


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

k-평균 알고리즘은 비용 함수를 계산할 때 중심점과 각 데이터 오브젝트간의 거리를 계산하게 된다. 이 때 사용하는 거리는 유클리드 거리 이다. 따라서, 알고리즘 수행 시 중심점으로부터 구형으로 군집화가 이루어지게 된다. 만약 주어진 데이터 집합의 분포가 구형이 아닐 경우에는 클러스터링 결과가 예상과 다를 수 있다. 아래의 경우를 살펴보자.

비구형 클러스터

위의 경우에는 총 4개의 클러스터가 존재하는데, 구형인 클러스터는 2개만 존재한다. 위와 같은 경우 클러스터링을 시행하면 중심점으로부터 가까이 있는 데이터 오브젝트들을 한 그룹으로 묶게 되는데, 그러면 얼굴 형상의 데이터 분포를 고르게 4 조각으로 자르는 형상이 나오게 된다. 이는 알고리즘 사용자가 원하는 결과와는 크게 다르다. 위와 같은 경우에는 비슷한 밀도를 가진 데이터 군집을 하나의 클러스터링으로 묶는 방법인 DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 알고리즘이나 mean-shift 클러스터링 알고리즘을 사용하면 원하는 결과를 얻을 수 있다.

응용[편집]

k-평균 알고리즘은 시장 분할, 컴퓨터 비전, 지질통계학, 천문학 및 농업 등 광범위한 분야에 적용될 수 있다. 이 기법은 주로 어떤 알고리즘을 수행하기 전 데이터를 전처리 (pre-processing) 하는 용도로 많이 쓰인다.

이미지 분할[편집]

컴퓨터 비전 분야에서 이미지 분할 (image segmentation) 은 디지털 이미지를 여러 개의 부분 (segments), 즉 픽셀들의 집합 (통칭 superpixel) 으로 나누는 과정이다. 좀 더 자세히 말하자면, 이미지 분할은 각 픽셀에 어떤 레이블을 붙여줌으로써 비슷한 성질을 가진 픽셀 끼리 같은 레이블을 가지게 하는 것이다. 이미지 분할의 목표는 주어진 이미지를 단순화하고 이미지 표현 방식을 단순화하여 이미지를 좀 더 분석하기 편한 형태로 만드는 것이다.

이미지 분할의 결과물은 전체 이미지를 모두 포함하는 부분 (segments) 들의 집합 혹은 이미지로부터 추출한 윤곽선들의 집합이다. 오른쪽 결과물은 SLIC (Simple Linear Iterative Clustering)[18] 기법을 이용하여 이미지를 분할한 결과물로, k-평균 알고리즘을 기반으로 한 이미지 분할 기법이다. 이미지 분할을 통해 이미지 내 비슷한 색상 및 위치에 있는 픽셀들 끼리 하나의 부분 (segment) 로 묶을 수 있고, 이를 통해 이미지를 크게 단순화할 수 있다.

Lena: segmentation with SLIC

의사 코드[편집]

k-평균 알고리즘 메인 함수

def kmeans(dataSet, k):  
   # Initialize centroids randomly
   numFeatures = dataSet.getNumFeatures()
   centroids = getRandomCentroids(numFeatures, k)
   
   # Initialize book keeping vars.
   iterations = 0
   oldCentroids = None
   
   # Run the main k-means algorithm
   while not shouldStop(oldCentroids, centroids, iterations):
       # Save old centroids for convergence test. Book keeping.
       oldCentroids = centroids
       iterations += 1
       
       # Assign labels to each datapoint based on centroids
       labels = getLabels(dataSet, centroids)
       
       # Assign centroids based on datapoint labels
       centroids = getCentroids(dataSet, labels, k)
       
   # We can get the labels too by calling getLabels(dataSet, centroids)
   return centroids


k-평균 종료 조건 만족 여부 함수

def shouldStop(oldCentroids, centroids, iterations):
   if iterations > MAX_ITERATIONS: return True
   return oldCentroids == centroids


클러스터 설정 함수

def getLabels(dataSet, centroids):


중심점 재계산 함수

def getCentroids(dataSet, labels, k):

[19]

바깥 고리[편집]

참고 문헌[편집]

  • D. Arthur, S. Vassilvitskii (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
  • H.-H. Bock (2007) : " Clutering Methods: A History of k-Means Algorithms", Proceedings of Selected Contributions in Data Analysis and Classification, 2:161-172
  • Han Jiawei, Jian Pei and Micheline Kamber (2012). 《Data Mining: Concepts and Tech-niques》. Morgan Kaufmann

각주[편집]

  1. Steinhaus, H. (1957). “Sur la division des corps matériels en parties” (French). 《Bull. Acad. Polon. Sci.》 4 (12): 801–804. MR 0090073. Zbl 0079.16403. 
  2. MacQueen, J. B. (1967). 《Some Methods for classification and Analysis of Multivariate Observations》. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability 1. University of California Press. 281–297쪽. MR 0214227. Zbl 0214.46201. 2009년 4월 7일에 확인함. 
  3. Lloyd, S. P. (1957). “Least square quantization in PCM”. 《Bell Telephone Laboratories Paper》.  Published in journal much later: Lloyd., S. P. (1982). “Least squares quantization in PCM”. 《IEEE Transactions on Information Theory28 (2): 129–137. doi:10.1109/TIT.1982.1056489. 2009년 4월 15일에 확인함. 
  4. E.W. Forgy (1965). “Cluster analysis of multivariate data: efficiency versus interpretability of classifications”. 《Biometrics》 21: 768–769. 
  5. J.A. Hartigan (1975). 《Clustering algorithms》. John Wiley & Sons, Inc. 
  6. Hartigan, J. A.; Wong, M. A. (1979). “Algorithm AS 136: A K-Means Clustering Algorithm”. 《Journal of the Royal Statistical Society, Series C28 (1): 100–108. JSTOR 2346830. 
  7. Han Jiawei, Jian Pei and Micheline Kamber (2012). 《Data Mining: Concepts and Tech-niques》. Morgan Kaufmann. 451쪽. 
  8. J.M. Peña, J.A. Lozano, P. Larrañaga (1999). “An empirical comparison of four initialization methods for the K-Means algorithm”. 
  9. Hamerly, G. and Elkan, C. (2002). 〈Alternatives to the k-means algorithm that find better clusterings〉. 《Proceedings of the eleventh international conference on Information and knowledge management (CIKM)》. 
  10. M. R. Anderberg (1973). 《Cluster Analysis for Applications》. Academic Press. 
  11. Qiang Du, Tak-win Wong (2002). “Numerical Studies of MacQueen’s k-Means Algorithm for Computing the Centroidal Voronoi Tessellations”. 
  12. L. Kaufman, P. J. Rousseeuw (1990). 《Finding Groups in Data. An Introduction to Cluster Analysis》. Wiley, Canada. 
  13. Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). “NP-hardness of Euclidean sum-of-squares clustering”. 《Machine Learning75: 245–249. doi:10.1007/s10994-009-5103-0. 
  14. Dasgupta, S. and Freund, Y. (July 2009). “Random Projection Trees for Vector Quantization”. 《Information Theory, IEEE Transactions on》 55: 3229–3242. arXiv:0805.1390. doi:10.1109/TIT.2009.2021326. 
  15. Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). “The Planar k-Means Problem is NP-Hard”. 《Lecture Notes in Computer Science5431: 274–285. doi:10.1007/978-3-642-00202-1_24. 
  16. Arthur, D.; Manthey, B.; Roeglin, H. (2009). 〈k-means has polynomial smoothed complexity〉. 《Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS)》. 
  17. Vattani., A. (2011). “k-means requires exponentially many iterations even in the plane”. 《Discrete and Computational Geometry45 (4): 596–616. doi:10.1007/s00454-011-9340-1. 
  18. Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., & Süsstrunk, S. (2010). Slic superpixels (No. EPFL-REPORT-149300)
  19. http://stanford.edu/~cpiech/cs221/handouts/kmeans.html