K-평균 알고리즘

역사

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

개요

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

목표

n개의 d-차원 데이터 오브젝트 (x₁, x₂, …, xₙ) 집합이 주어졌을 때, k-평균 알고리즘은 n개의 데이터 오브젝트들을 각 집합 내 오브젝트 간 응집도를 최대로 하는  개의 집합 S = {S₁, S₂, …, Sₖ} 으로 분할한다. 다시 말해, μᵢ가 집합 Sᵢ의 중심점이라 할 때
각 집합별 중심점~집합 내 오브젝트간 거리의 제곱합을 최소로 하는 집합 S를 찾는 것이 이 알고리즘의 목표다. 이 목적 함수의 전역 최솟값 (global minimum) 을 찾는 것은 NP-난해 문제이므로, 언덕 오르기 (hill climbing) 방식으로 목적 함수의 오차를 줄여나가며 지역 최솟값 (local minimum) 을 발견했을 때 알고리즘을 종료함으로써 근사 최적해를 구한다.

무작위 분할 (Random Partition)

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

Forgy

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

MacQueen

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

Kaufman

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

클러스터의 수

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

Elbow Method

클러스터의 수를 순차적으로 늘려가면서 결과를 모니터링 한다. 만약 하나의 클러스터를 추가했을 때 이전보다 훨씬 더 나은 결과를 나타내지 않는다면, 이전의 클러스터의 수를 구하고자 하는 클러스터의 수로 설정한다.

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

클러스터링 모델에 대해 가능도를 계산하는 것이 가능할 때 사용하는 방법으로, 베이지안 정보 기준 등이 있다. k-평균 클러스터링 모델의 경우 가우시안 혼합 모델에 가깝기 때문에, 가우시안 혼합 모델에 대한 가능도를 만들어 정보 기준 값을 설정할 수 있다.

클러스터링 평가 척도

클러스터링이 얼마나 잘 되었는가를 측정하는 방법으로 내부 평가 혹은 외부 평가, 크게 2가지 방법론을 이용할 수 있다.

내부 평가

내부 평가 (internal evaluation) 은 데이터 집합을 클러스터링한 결과 그 자체를 놓고 평가하는 방식이다. 이러한 방식에서는 클러스터 내 높은 유사도 (high intra-cluster similarity) 를 가지고, 클러스터 간 낮은 유사도 (low inter-cluster similarity) 를 가진 결과물에 높은 점수를 준다. 이와 같은 평가 방법은 오로지 데이터를 클러스터링한 결과물만을 보고 판단하기 때문에, 평가 점수가 높다고 해서 실제 참값 (ground truth) 에 가깝다는 것을 반드시 보장하지는 않는다는 단점이 있다.

외부 평가

외부 평가 방식 (external evaluation)에서 클러스터링의 결과물은 클러스터링에 사용되지 않은 데이터로 평가된다. 다시 말해, 클러스터링의 결과물을 전문가들이 미리 정해높은 모범답안 혹은 외부 벤치마크 평가 기준 등을 이용해서 클러스터링 알고리즘의 정확도를 평가하는 것이다. 이러한 평가 방식은 클러스터링 결과가 미리 정해진 결과물과 얼마나 비슷한지를 측정한다.

응용

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

이미지 분할

컴퓨터 비전 분야에서 이미지 분할 (image segmentation) 은 디지털 이미지를 여러 개의 부분 (segments), 즉 픽셀들의 집합 (통칭 superpixel) 으로 나누는 과정이다. 좀 더 자세히 말하자면, 이미지 분할은 각 픽셀에 어떤 레이블을 붙여줌으로써 비슷한 성질을 가진 픽셀 끼리 같은 레이블을 가지게 하는 것이다. 이미지 분할의 목표는 주어진 이미지를 단순화하고 이미지 표현 방식을 단순화하여 이미지를 좀 더 분석하기 편한 형태로 만드는 것이다.
이미지 분할의 결과물은 전체 이미지를 모두 포함하는 부분 (segments) 들의 집합 혹은 이미지로부터 추출한 윤곽선들의 집합이다. 오른쪽 결과물은 SLIC (Simple Linear Iterative Clustering) 기법을 이용하여 이미지를 분할한 결과물로, k-평균 알고리즘을 기반으로 한 이미지 분할 기법이다. 이미지 분할을 통해 이미지 내 비슷한 색상 및 위치에 있는 픽셀들 끼리 하나의 부분 (segment) 로 묶을 수 있고, 이를 통해 이미지를 크게 단순화할 수 있다.

벡터 양자화

k-평균 알고리즘은 신호 처리 분야에서 나온 것이며, 여전히 그 분야에서 사용되고 있다. 예를 들어 컴퓨터 그래픽스 분야에서는, 색상 양자화를 하는데 k-평균 알고리즘이 사용된다. 색상 양자화는 이미지에 사용된 색의 종류를 k개의 색으로 줄이는 과정이다. 예를 들어, 원래 색상이 65536개의 스펙트럼으로 이루어져 있다고 가정할 때, 이것을 256개 씩 묶게 되면 256개의 색상 스펙트럼으로 줄일 수 있는 것이다.

클러스터 분석

클러스터 분석 시, k-평균 알고리즘은 입력 데이터를 k개의 파티션 (클러스터) 으로 나누는 데 사용될 수 있다. 그러나 순수 k-평균 알고리즘은 사용에 있어 적용성이 떨어진다. 위의 한계점에서 다루었듯이 k 값을 정하기 어렵고, 비 수치 데이터를 입력으로 받았을 때나 임의의 거리 측도를 이용해야 할 때는 사용될 수 없다. 이러한 경우에는 일반적으로 k-평균 알고리즘 이외의 다른 알고리즘을 사용한다.

EM 알고리즘

가우시안 혼합 모델을 이용한 EM 알고리즘 (기댓값 최대화 알고리즘) 과 k-평균 알고리즘을 비교했을 때 이 둘은 밀접한 연관성을 가지고 있다. k-평균 알고리즘은 각 데이터 오브젝트를 클러스터에 강하게 결속시킨다. 다시 말해, 데이터 오브젝트는 오로지 하나의 클러스터에만 속하게 되는데, 이를 hard assignment라고 한다. 반면에, EM 알고리즘은 데이터 오브젝트를 클러스터링할 때 클러스터에의 소속 여부를 해당 클러스터에서 데이터 오브젝트가 나타날 확률값으로 표현한다. 즉, 데이터 오브젝트들이 k-평균 알고리즘과 다르게 어느 한 클러스터에만 결속되지 않게 된다. 이러한 클러스터링 방식을 soft assignment라고 한다.
공분산 행렬을 단위 행렬 (identity matrix)에 ε을 곱한 (εΙ) 가우시안 혼합 모델을 가정해보자. 이 때 ε은 분산값을 조절하는 파라미터로, 모든 식의 구성요소가 공유한다. 그렇다면 가우시안 혼합 모델이 주어졌을 때 데이터 오브젝트가 나타날 우도 확률은 아래와 같이 주어진다.
이 식에서 EM 알고리즘을 k 개의 가우시안 혼합 모델에 적용할 때, ε값을 추정해야 할 값으로 보지 않고 고정된 값으로 만들자. 한편, 데이터 오브젝트 에 대한 가우시안 혼합 모델에서의 사후 확률은 아래와 같이 주어진다.
만약 ε값을 0에 근접시키면, 분모의 가 가장 작을 때, 0으로 가장 천천히 근접해갈 것이다. 따라서, 그 경우에 데이터 오브젝트 의 사후 확률값 은 j값 이외의 경우 모두 0으로 근접하게 된다. 즉, 에서 분모에 데이터 오브젝트로부터 가장 가까운 평균값일때만 1이 되고, 그 이외의 경우는 0이 되는 것이다. 결과적으로, 데이터 오브젝트의 사후 확률은 하나의 클러스터에만 1의 값을 가지고, 나머지 클러스터에서는 0의 값을 가지게 된다. 따라서, 데이터 오브젝트 들은 가장 가까운 평균점에 hard-clustering이 되고, 이는 k-평균 알고리즘의 결과와 일치한다.
참고로, k-평균 알고리즘에서 클러스터 설정 과정은 EM 알고리즘에서의 E-step에 해당하고, 클러스터 중심 재조정 과정은 M-step에 해당한다.

평균점 이동 클러스터링

기본적인 평균점 이동 클러스터링 (mean-shift clustering) 알고리즘은 비모수적인 클러스터링 방법으로, 데이터 오브젝트들의 분포에서 그 밀도가 가장 높은 곳 (mode - 최빈값) 을 찾는 방식으로 그룹화를 수행한다. 간단히 설명하자면, 이 알고리즘은 각 데이터 오브젝트에서 미리 지정된 크기의 윈도우 이내의 데이터 오브젝트들을 찾고, 윈도우 내의 평균 값을 구한다. 그리고, 다시 그 평균값에서 같은 크기의 윈도우 이내의 데이터 오브젝트들을 찾고, 윈도우 내의 평균 값을 구한다. 이 방식을 계속하면 데이터 오브젝트들의 지역 밀도가 최대인 곳에서 윈도우의 움직임이 멈추게 된다. 이곳이 데이터 오브젝트 밀도의 지역 최댓값 (최빈값) 이다. 이런 방식으로 모든 데이터 오브젝트에 대해 지역 최댓값을 알아낸다. 이 때, 같은 최빈값으로 수렴한 데이터 오브젝트는 같은 클러스터로 간주하고, 한 클러스터로 묶어준다.
평균점 이동 클러스터링은 k-평균 알고리즘과 다르게 k값을 필요로 하지 않는다는 장점이 있다. 하지만 모든 데이터 오브젝트로부터 무게 중심 이동 과정을 수렴할 때 까지 거쳐야 하므로 k-평균 알고리즘보다 수행 시간이 훨씬 오래 걸린다.
참고로, 평균점 이동 클러스터링은 컴퓨터 비전 및 이미지 프로세싱 분야에서 주로 사용되며, 이미지 분할, 객체 추적 등에 이용된다.

의사 코드

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):
  dataSet.label = reassignToNearestCentroid(dataSet, centroids)
  return dataSet.label
중심점 재계산 함수
def getCentroids(dataSet, labels, k):
   newCentroids = computeCentroids(dataSet, labels, k)
   return newCentroids

k-중앙값 클러스터링

k-중앙값 클러스터링 은 각 클러스터의 무게중심을 구하기 위해 평균을 사용하는 대신 중앙값을 사용한다.  거리를 최소화하는 k-평균과는 달리, k-중앙값 클러스터링은  거리를 최소화 한다.