K-Means Algorithm(K-평균 알고리즘)

K-평균 알고리즘은 간단한 방법으로 주어진 데이터를 지정한 군집(cluster) 개수($K$)로 그룹화하는 방법으로 1957년 후고 스테인하우스에 의해 소개되었고 용어 자체는 1967년 제임스 매퀸에 의해 처음 사용되었다. 데이터를 한 개 이상의 데이터 오브젝트로 구성된 $K$개의 그룹으로 나누는 것으로 거리기반의 그룹간 비유사도(dissimilarity)와 같은 비용 함수을 최소화하는 방식으로 이루어집니다.

알고리즘의 결과는 중심(centroid)이라고 부르는 $K$개의 점으로서 이들은 각기 다른 그룹의 중심점을 나타내며 데이터들은 $K$개의 군집 중 하나에만 속할 수 있습니다. 한 군집 내의 모든 데이터들은 다른 어떤 중심들보다 자기 군집 중심과의 거리가 더 가깝습니다. 그래서 K-평균 알고리즘은 각 그룹의 중심과 그 그룹 내의 데이터 오브젝트와의 거리의 제곱합을 비용함수로 정하고 이 함수값을 최소화하는 방향으로 각 데이터 오브젝트의 소속 그룹을 업데이트 해 줌으로써 군집화를 합니다.

이 기법은 대체로 세 개의 단계로 나뉩니다.

  • 초기단계(0단계) : $K$개 중심의 초기 집합을 결정
  • 클러스터설정(1단계) : 각 데이터를 가장 가까운 군집에 할당
  • 클러스터 중심 재조정(2단계) : 각 그룹에 대해 새로운 중심을 계산

$K$개 중심의 초기 값을 정하는 방법에는 몇 가지가 있습니다. 그 중 하나는 데이터 중 $K$개를 임의로 선택하여 중심으로 삼는 것입니다.

할당 단계와 수정 단계는 알고리즘이 수렴되었다고 간주될 때까지 루프를 통해 반복합니다. 예를 들어 군집 내 데이터의 변화가 없을 때 알고리즘이 수렴되었다고 간주합니다.

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

그래서 군집을 구성할 때 직접 오차함수를 최소화하려면 계산비용이 매우 많이 듭니다.
따라서 언덕오르기(hill climbing)[2]방식으로 목적함수의 오차를 줄여나가며 최소값을 발견했을 때 알고리즘을 종료함으로써 근사 최적해를 구합니다.

활용분야

이미지분할, 벡터 양자화, 클러스터 분석 등

예제

참고자료


  1. 보통 입력 값이 많아질수록 알고리즘을 수행하는데 걸리는 시간이 늘어나게 됩니다. 입력($n$)이 늘어남에 따라 어떤 다항식만큼의 시간 안에 풀수 있는 문제는 P, 풀 수 있을지 모르는 문제를 NP문제라고 합니다. 오차함수를 최소화하려고 일일이 모든 경우의 수를 다 확인해보는 것은 NP 난해 문제로 알려져 있습니다. ↩︎

  2. 최적의 해를 찾아 값이 증가하는 방향이나 감소하는 방향으로 계속 이동하는 방식 ↩︎