k-Means

k-Means

---

• 정의 : 중심점 기반 배타적 분리형 군집화 알고리즘

  

• 목표 : 각 군집에 대하여, 관측치와 중심점(Centroid) 간 평균 거리(Means)를 최소화함

  \[\min_{\overrightarrow{\mu}_{i}}{\sum_{i=1}^{k}\sum_{\overrightarrow{x}_{j} \in C_{i}}{\Vert\overrightarrow{x}_{j}-\overrightarrow{\mu}_{i}\Vert^2}}\]

Centroid Search Process

---

1. 군집 갯수를 설정함

   \[X=C_{1} \cup C_{2} \cup \cdots \cup C_{k}\\ \\ C_{i} \cap C_{j \ne i} = \emptyset\]

2. $k$ 개의 초기 군집 중심 벡터 $\overrightarrow{c}$ 를 임의로 선정함

   \[M=\{\overrightarrow{\mu}_{1},\overrightarrow{\mu}_{2},\cdots,\overrightarrow{\mu}_{k}\}\]

3. 모든 관측치 벡터 $\overrightarrow{x}$ 를 가장 가까운 거리에 위치한 중심 벡터 $\overrightarrow{\mu}$ 의 군집에 배타적으로 할당함

   \[\overrightarrow{x}_{j} \rightarrow C_{i}\\ \begin{aligned} \\\text{s.t.} \quad & i=\text{arg} \min_{i}{\Vert\overrightarrow{x}_{j}-\overrightarrow{\mu}_{i}\Vert^2}\\ &\overrightarrow{\mu}_{i} \in C_{i} \end{aligned}\]

4. 각 군집별 할당된 관측치 벡터들의 평균 벡터로 군집 중심 벡터를 갱신함

   \[\begin{aligned} \overrightarrow{\mu}_{i} &=\displaystyle\frac{1}{\vert C_{i} \vert}\sum_{\overrightarrow{x}_{j}\in C_{i}}{\overrightarrow{x}_{j}} \end{aligned}\]

5. ③, ④의 과정을 반복하여 최적의 군집 중심 벡터 집합 $\hat{M}$ 을 탐색함

   \[\begin{aligned} \hat{M} &= \{\overrightarrow{\mu}_{i} \mid \text{arg} \min_{\overrightarrow{\mu}_{i}}{\sum_{i=1}^{k}\sum_{\overrightarrow{x}_{j} \in C_{i}}{\Vert\overrightarrow{x}_{j}-\overrightarrow{\mu}_{i}\Vert^2}}\} \end{aligned}\]

Limitation

---

• 초기 군집 중심에 민감함

  

• 이상치에 민감함

  

• 구형이 아닌 형태의 군집을 탐지하기 어려움

  

• 서로 다른 규모의 군집을 탐지하기 어려움

  

• 서로 다른 밀도의 군집을 탐지하기 어려움

  

---

이미지 출처

• https://ai-times.tistory.com/158
• https://github.com/pilsung-kang/multivariate-data-analysis/blob/master/09%20Clustering/09-2_K-Means%20Clustering.pdf
• https://github.com/lovit/python_ml_intro/blob/master/lecture_notes/10_clustering.pdf
• https://paulvanderlaken.com/2018/12/12/visualizing-the-inner-workings-of-the-k-means-clustering-algorithm/