K-means 클러스터링은 원래 신호 처리에서 유래한 벡터 양자화 방법으로, n개의 관측값을 k개의 클러스터로 분할하며, 각 관측값은 가장 가까운 평균(클러스터 중심 또는 중심점)을 가진 클러스터에 속한다. 이는 데이터 공간을 보로노이 셀로 분할하는 결과를 낳는다. 이 알고리즘은 머신 러닝에서 고객 세분화, 이미지 압축, 패턴 인식과 같은 비지도 데이터 분석에 널리 사용된다.
K-means는 클러스터 내 분산을 최소화하며, 이는 제곱 유클리드 거리로 측정되지만 일반 유클리드 거리는 아니다. 일반 유클리드 거리를 사용하면 더 어려운 베버 문제가 된다. 평균은 제곱 오차를 최적화하는 반면, 유클리드 거리를 최소화하는 것은 기하 중앙값뿐이다. 예를 들어, 더 나은 유클리드 해는 k-중앙값과 k-메도이드를 사용하여 찾을 수 있다.
이 문제는 계산적으로 어렵다(NP-난해). 그러나 효율적인 휴리스틱 알고리즘은 빠르게 지역 최적해에 수렴한다. 이러한 알고리즘은 일반적으로 가우시안 혼합 분포에 대한 기대값-최대화 알고리즘과 유사하며, k-means와 가우시안 혼합 모델링 모두에서 사용되는 반복적 정제 접근 방식을 따른다. 둘 다 클러스터 중심을 사용하여 데이터를 모델링하지만, k-means 클러스터링은 공간적으로 유사한 범위의 클러스터를 찾는 경향이 있는 반면, 가우시안 혼합 모델은 클러스터가 서로 다른 모양을 가질 수 있도록 허용한다.
비지도 k-means 알고리즘은 k-최근접 이웃 분류기와 느슨한 관계를 가지며, 이는 이름 때문에 k-means와 자주 혼동되는 인기 있는 지도 머신 러닝 분류 기법이다. k-means로 얻은 클러스터 중심에 1-최근접 이웃 분류기를 적용하면 새 데이터를 기존 클러스터로 분류하며, 이를 최근접 중심 분류기 또는 로치오 알고리즘이라고 한다.
공식 정의
관측값 집합 (x1, x2, ..., xn)이 주어졌을 때, 각 관측값은 d차원 실수 벡터이다. k-means 클러스터링은 n개의 관측값을 k(≤ n)개의 집합 S = {S1, S2, ..., Sk}로 분할하여 클러스터 내 제곱합(WCSS), 즉 분산을 최소화하는 것을 목표로 한다. 공식적으로, 목적은 다음을 찾는 것이다:
S에 대한 argmin, i=1부터 k까지의 합, x in Si에 대한 합, ||x - μi||^2,
여기서 μi는 Si에 있는 점들의 평균(중심점이라고도 함)이고, ||·||는 일반적인 L2 노름이다. 이는 동일한 클러스터에 있는 점들의 쌍별 제곱 편차를 최소화하는 것과 동일하며, 평균에 대한 제곱 거리의 합이 평균 쌍별 제곱 거리와 같다는 항등식으로 보여진다.
알고리즘
가장 일반적인 알고리즘인 로이드 알고리즘은 반복적 정제 접근 방식을 사용한다. 초기 k개의 중심점 집합으로 시작하여 할당 단계와 업데이트 단계를 번갈아 수행한다. 할당 단계에서는 각 관측값을 일반적으로 유클리드 거리를 사용하여 가장 가까운 중심점을 가진 클러스터에 할당한다. 업데이트 단계에서는 각 클러스터의 중심점을 할당된 점들의 평균으로 다시 계산한다. 이러한 단계는 할당이 더 이상 변경되지 않을 때까지 반복되며, 이는 지역 최적해에 수렴했음을 나타낸다.
초기화는 중요하다. 초기 중심점을 분산시키는 k-means++ 방법은 최종 클러스터링 품질을 개선하는 인기 있는 휴리스틱이다. 이 알고리즘은 k의 선택에 민감하며, 팔꿈치 방법이나 실루엣 분석과 같은 방법이 적절한 클러스터 수를 추정하는 데 사용된다.
속성 및 한계
K-means는 클러스터가 구형이고 유사한 크기라고 가정하므로, 복잡한 클러스터 모양을 가진 데이터에는 적용이 제한된다. 또한 평균이 극단값의 영향을 받기 때문에 이상치에 민감하다. 이 알고리즘은 지역 최적해에 수렴하며 반드시 전역 최적해는 아니므로, 다른 초기화는 다른 결과를 산출할 수 있다. 이러한 한계에도 불구하고, 단순성과 확장성 덕분에 대규모 데이터셋, 특히 데이터 증강 및 전처리 파이프라인에서 인기 있는 선택이다.
응용 분야
K-means는 다양한 분야에서 사용된다. 인공 지능에서는 클러스터링 작업의 기준선 역할을 한다. 컴퓨터 비전에서는 이미지 분할 및 색상 양자화에 사용된다. 마케팅에서는 구매 행동을 기반으로 고객을 세분화하는 데 도움을 준다. 자연어 처리에서는 문서나 단어 임베딩을 클러스터링할 수 있다. 이 알고리즘은 또한 딥 러닝 특징 학습 및 Generative AI 모델과 같은 더 고급 기술의 구성 요소이다.
다른 방법과의 관계
K-means는 가우시안 혼합 모델(GMM)과 관련이 있으며, 둘 다 반복적 정제와 클러스터 중심을 사용한다. 그러나 GMM은 클러스터가 서로 다른 모양과 공분산을 가질 수 있도록 허용하는 반면, k-means는 등방성 클러스터를 가정한다. k-means에서 파생된 최근접 중심 분류기는 간단한 지도 분류 방법이다. K-means는 종종 k-최근접 이웃(k-NN)과 혼동되지만, 이들은 구별된다. k-means는 비지도 학습이고 k-NN은 지도 학습이다.
역사 및 발전
K-means의 개념은 1956년 휴고 슈타인하우스가 처음 제안했으며, "k-means"라는 용어는 1967년 제임스 맥퀸이 만들었다. 1957년에 발표되었지만 1982년까지 널리 알려지지 않은 로이드 알고리즘은 표준 구현이다. 수년에 걸쳐 대규모 데이터용 미니 배치 k-means와 소프트 클러스터링용 퍼지 c-means와 같은 다양한 변형이 개발되었다.