K-Means 클러스터링은 원래 신호 처리에서 유래한 벡터 양자화 방법으로, 관측값 집합을 k개의 클러스터로 분할하며, 각 관측값은 클러스터 중심(centroid)으로 알려진 가장 가까운 평균을 가진 클러스터에 속한다. 이는 데이터 공간을 보로노이 셀로 분할하는 결과를 낳는다. 이 알고리즘은 기계 학습에서 고객 세분화, 이미지 압축, 패턴 인식과 같은 작업에 널리 사용되며, 인공 지능 및 데이터 분석의 기초 기법이다.
K-means의 목적은 클러스터 내 제곱합(WCSS)을 최소화하는 것으로, 이는 각 점과 해당 클러스터 중심 간의 제곱 유클리드 거리의 합이다. 이는 동일한 클러스터 내 점들의 쌍별 제곱 편차를 최소화하는 것과 동일하다. 그러나 k-means는 일반 유클리드 거리가 아닌 제곱 유클리드 거리를 최소화하며, 후자는 더 어려운 베버 문제를 해결해야 한다. 유클리드 거리 최소화의 경우 k-중앙값 또는 k-메도이드 같은 대안이 더 적합하다.
최적의 k-means 클러스터링을 찾는 문제는 계산적으로 어렵지만(NP-난해), 효율적인 휴리스틱 알고리즘은 국소 최적점에 빠르게 수렴한다. 가장 일반적인 접근 방식은 로이드 알고리즘으로, 점을 가장 가까운 중심에 반복적으로 할당한 다음 할당된 점의 평균으로 중심을 업데이트한다. 이러한 반복적 정제는 가우시안 혼합 모델에 사용되는 기대-최대화 알고리즘과 유사하지만, k-means는 비교적 유사한 공간적 범위의 클러스터를 찾는 경향이 있는 반면, 가우시안 혼합은 다양한 형태를 허용한다.
알고리즘 및 구현
표준 k-means 알고리즘은 초기 k개의 중심 집합으로 시작하며, 이는 무작위로 선택되거나 수렴을 개선하기 위해 k-means++와 같은 방법을 사용할 수 있다. 알고리즘은 수렴할 때까지 두 단계를 반복한다: 할당 단계에서는 각 관측값이 가장 가까운 중심을 가진 클러스터에 할당되고, 업데이트 단계에서는 각 중심이 해당 클러스터의 모든 점의 평균으로 재계산된다. 수렴은 일반적으로 할당이 더 이상 변경되지 않거나 WCSS 개선이 임계값 아래로 떨어질 때 감지된다.
대규모 데이터셋을 위한 미니 배치 k-means와 텍스트 데이터를 위한 구형 k-means를 포함한 여러 변형이 존재한다. k의 선택은 종종 엘보우 방법, 실루엣 분석 또는 갭 통계량을 사용하여 결정된다. 알고리즘의 시간 복잡도는 대략 O(nkd*i)이며, 여기서 n은 관측값 수, d는 차원 수, i는 반복 횟수이다.
다른 방법과의 관계
K-means는 비지도 알고리즘으로, 레이블이 지정된 데이터가 필요하지 않다. 이는 지도 기법인 k-최근접 이웃(k-NN) 분류기와 느슨한 관계를 가진다. k-means로 얻은 클러스터 중심에 1-최근접 이웃 분류기를 적용하면 새 데이터를 기존 클러스터로 분류하며, 이를 최근접 중심 분류기 또는 로치오 알고리즘이라고 한다. 이러한 연결은 비지도 클러스터링이 지도 작업을 지원할 수 있는 방법을 강조한다.
K-means는 가우시안 혼합 모델(GMM)과도 관련이 있다. 둘 다 클러스터 중심을 사용하여 데이터를 모델링하지만, GMM은 클러스터가 다양한 형태와 크기를 가질 수 있게 허용하는 반면, k-means는 유사한 분산을 가진 구형 클러스터를 가정한다. 결과적으로 k-means는 더 단순하고 빠르지만 덜 유연하다.
응용 및 한계
K-means는 여러 영역에서 사용된다. 아마존 웹 서비스와 구글 클라우드에서는 사용자 행동 분석과 리소스 할당 최적화를 위한 일반적인 도구이다. 컴퓨터 비전에서는 이미지 분할과 색상 양자화에 사용된다. 마케팅에서는 구매 패턴을 기반으로 고객을 세분화한다. 이 알고리즘은 또한 딥 러닝 특징 추출 및 생성형 AI 데이터 전처리와 같은 더 복잡한 방법의 구성 요소이기도 하다.
그러나 k-means에는 한계가 있다. 클러스터 수 k를 사전에 지정해야 하며, 이는 항상 알려져 있지 않다. 초기 중심 선택에 민감하지만, k-means++가 이를 완화한다. 클러스터가 볼록하고 등방성이라고 가정하며, 이는 실제 데이터에는 적용되지 않을 수 있다. 이상값은 중심을 왜곡할 수 있고, 알고리즘은 국소 최적점에 수렴할 수 있다. 이러한 문제에도 불구하고, 단순성과 효율성 덕분에 널리 선택되는 방법이다.
역사적 배경 및 발전
K-means 알고리즘은 1956년 휴고 슈타인하우스가 처음 제안했으며, 이후 1957년 벨 연구소의 스튜어트 로이드가 개선했다(1982년에 출판됨). "k-means"라는 이름은 1967년 제임스 맥퀸이 만들었다. 그 이후로 더 나은 초기화를 위한 k-means++와 확장성을 위한 미니 배치 변형을 포함한 수많은 개선이 개발되었다. 이 알고리즘은 기계 학습 교육 과정의 핵심 요소로 남아 있으며, scikit-learn 및 TensorFlow와 같은 주요 라이브러리에 구현되어 있다.