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]방식으로 목적함수의 오차를 줄여나가며 최소값을 발견했을 때 알고리즘을 종료함으로써 근사 최적해를 구합니다.
활용분야
이미지분할, 벡터 양자화, 클러스터 분석 등