# 개요
1. 랜덤하게 선정된 $K$개의 **centroids** $\{\mu_k\}$에서 시작한다.
2. **Assignment Step** : 주어진 $\mu$에 대해 최적의 할당 $r$을 찾는다.
3. **Update Step** : 주어진 $r$에 대해 centroid $\mu$를 찾는다.
4. 수렴할때까지 2, 3를 반복한다.

![image.png](https://supernotes-resources.s3.amazonaws.com/image-uploads/51ccc7fc-e34c-47c6-8bf7-dcafba775ae9--image.png)

# 상세
랜덤하게 $K$개의 centroids $\{\mu_k\}$가 선정되었다고 하자.

## Assignment Step
각 데이터 포인트에 대해 가장 가까운 레퍼런스 포인트 $\mu$로 할당 $r$을 부여한다.

$$r_{ik}=\begin{cases}1&\text{if }k=\argmin_k||x_i-\mu_k||^2_2\\0&\text{otherwise}\end{cases}$$

## Update Step
각 할당된 $\mu$를 따라 해당 소속 데이터 포인트의 평균점으로 $\mu$를 업데이트한다.

$$\mu_k=\frac{\sum_ir_{ik}x_i}{\sum_ir_{ik}}\text{ a.k.a. centroid}$$

[Cost Function](^fcc48d98-9c40-4c59-9eae-3d95f53ef9f9)에서 나온 식과 연관지어 보면, **해당 식의 gradient를 0으로 만들도록 하는 업데이트**이다.

- 해당 식의 미분 $= \sum_ir_{ik}(x_i-\mu_k)\cdot 2=0$
- 위 식을 정리하면 업데이트 스텝의 식과 동일

# 이외 정보
- K-means는 로컬 옵티멈을 찾는 것이다.
- 유한한 iteration 안에 수렴하는 것이 보장된다.
- 계산 복잡도는 Assignment Step에 $O(KND)$, Update Step에 $O(N)$이다.

# Variant : K-means++
K-means에서 $\mu$를 initialization하는 방법만이 차이가 난다.

1. 첫 번째 centroid를 무작위로 선정한다.
2. $||x_i-\mu_k||^2_2$를 계산하여 확률에 비례하게 새로운 centroid를 선정한다.
3. $K$개의 centroid가 나올 때까지 2를 반복한다.
4. 이후 K-means를 수행한다.

# Variant : Soft K-means
Assignment Step만이 차이난다.

$$r_{ik}=\frac{\exp(-\beta||x_i-\mu_k||^2)}{\sum_{l\in[K]}\exp(-\beta||x_i-\mu_l||^2)}$$

### $\beta$ : temperature parameter
$\beta=1/\text{temperature}$이다. $\beta=0$일 때는 **uniform assignment**라 하여 $\text{temperature}$가 $\infty$가 되고, 따라서 균일하게 분포한다는 그런 느낌이다. $\beta=\infty$일 때는 **hard assignment**라 하여 $\text{temperature}$가 $0$이 되어 각 클러스터에 더욱 sticky하게 할당하게 된다.

## Soft K-means 해석
다음의 최적화이다.

$$\min \mathcal J_\text{soft}=\sum_{i\in[N]}\sum_{k\in[K]}r_{ik}||x_i-\mu_k||^2-\frac{1}{\beta}\sum_{i \in [N]}\sum_{k \in [K]}r_{ik}\log_{1}{r_{ik}}$$

여기서 두번째 텀은 **"entropy"** 로 불리며, 얘들이 커질수록 assignment가 클러스터 전반에 골고루 퍼지도록 한다.