K-평균 군집화

K-평균 군집화는 군집 중심점까지의 제곱 거리 합계를 최소화함으로써 관측치를 고정된 수의 군집으로 나눕니다.

Definition

K-평균 군집화는 관측치와 할당된 중심점 간의 총 제곱 유클리드 거리를 최소화하기 위해 정해진 수의 군집 중심을 배치하고 각 관측치를 가장 가까운 중심점에 할당하는 분할 방법입니다.

Scope

이 주제는 군집 내 제곱합 목표, 가장 가까운 중심점에 점을 할당하고 중심점을 재계산하는 과정을 번갈아 수행하는 반복적인 할당-업데이트 알고리즘, 초기화 의존성 및 그로 인한 지역 최적해, 군집 수 선택, 그리고 이 방법의 가정과 한계를 다룹니다.

Core questions

• 군집 내 분산을 최소화하기 위해 관측치를 어떻게 분할할 수 있는가?
• 알고리즘이 왜 지역 최적해에만 수렴하며, 이를 어떻게 완화할 수 있는가?
• 군집의 수는 어떻게 선택하는가?
• 이 방법은 어떤 군집 형태와 스케일을 암묵적으로 가정하는가?

Key theories

군집 내 제곱합 최소화

K-평균은 점들로부터 군집 중심까지의 총 제곱 거리를 최소화하는 분할 및 중심점 집합을 찾으며, 이 목표에 대해 교대 할당-업데이트 반복은 기준을 단조적으로 감소시킵니다.

지역 최적해 민감성

목표 함수가 비볼록(non-convex)이기 때문에, 알고리즘은 초기 중심점에 따라 달라지는 지역 최솟값으로 수렴하며, 이는 여러 번의 재시작과 신중한 시드(seeding)를 필요로 합니다.

Clinical relevance

K-평균은 대규모 데이터셋을 분할하는 데 빠르고 확장 가능한 기본 방법이며, 벡터 양자화, 이미지 색상 감소, 고객 세분화에 사용되고 더 복잡한 모델의 초기화에도 활용됩니다.

History

중심점 기반 분할 아이디어는 Lloyd의 초기 양자화 알고리즘을 기반으로 MacQueen이 1967년에 k-평균이라는 이름을 붙여 공식화했습니다. 이는 단순성과 속도 덕분에 가장 널리 사용되는 군집화 방법 중 하나가 되었습니다.

Debates

K-평균의 암묵적 가정

제곱 유클리드 거리를 최소화하는 것은 대략 구형이고 크기가 비슷한 군집에 유리하므로, 군집이 길쭉하거나 크기가 다르거나 비볼록(non-convex)인 경우 K-평균은 오해를 불러일으킬 수 있으며, 이는 모델 기반 또는 밀도 기반 대안을 모색하게 합니다.

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

K-평균이 실행할 때마다 다른 결과를 주는 이유는 무엇입니까?

목표 함수가 비볼록(non-convex)이므로, 알고리즘은 무작위 초기 중심점에 따라 달라지는 지역 최적해에 수렴합니다. 여러 번 실행하여 가장 좋은 결과를 선택하는 것이 일반적인 관행입니다.

군집의 수 k는 어떻게 선택합니까?

일반적인 휴리스틱(heuristics)으로는 군집 내 제곱합의 엘보(elbow) 방법, 갭 통계량(gap statistic), 평균 실루엣 너비(average silhouette width) 등이 있지만, 어느 것도 결정적이지 않으며 종종 도메인 지식이 선택에 영향을 미칩니다.