iteration t = 0 · next:다음: Assign (z)할당 (z)
Point color = assigned cluster (hard)점 색 = 배정 군집 (하드)
×Centroid μₖ (draggable)중심 μₖ (드래그 가능)
Voronoi regionVoronoi 영역
Centroid trail중심 궤적
Distortion J/n — both half-steps (assign · update) step downward (manual moves may jump up)왜곡 J/n — 할당·갱신 두 반스텝 모두 계단으로 내려간다 (수동 이동은 튀어오를 수 있음)
J/n
Assign step할당 스텝
Update step갱신 스텝
Manual move수동 이동
Elbow method — lowest J per K (k-means++ · 6 restarts); look for the bend, not the minimum엘보 방법 — K별 최저 J (k-means++ · 재시작 6회), 최소가 아니라 꺾이는 지점을 찾는다
DISTORTION
Distortion · inertia왜곡 · inertia
J/n—
ΔJ/n (half-step)(반스텝)—
Lowest J/n (this data)최저 J/n (이 데이터)—
Finite number of partitions → must converge in a finite number of steps유한한 분할의 수 → 유한 스텝 안에 반드시 수렴
ASSIGN
zₙ = argminₖ ‖x−μₖ‖²
Reassigned points재할당된 점—
Cluster sizes Nₖ군집 크기 Nₖ—
Nearest-centroid assignment = Voronoi partition · 0 reassignments = converged최근접 중심 배정 = Voronoi 분할 · 재할당 0 = 수렴
UPDATE
μₖ = cluster mean군집 평균
Centroid movement중심 이동 Σ‖Δμ‖—
Empty-cluster reseeds (cumulative)빈 군집 재시드 (누적)—
The mean minimizes the sum of squared distances — guarantees J↓평균은 제곱거리 합의 최소자 — J↓ 보장
Formulas수식
$$J\big(\{z_n\},\{\mu_k\}\big)=\sum_{n}\big\|x_n-\mu_{z_n}\big\|^2=\sum_n\sum_k r_{nk}\,\|x_n-\mu_k\|^2,\qquad r_{nk}=\mathbb 1[z_n{=}k]$$
$$\textbf{Assign: }\ z_n=\arg\min_k\|x_n-\mu_k\|^2\ \ (\text{each term minimized}\ \Rightarrow\ J\downarrow)$$
$$\textbf{Update: }\ \mu_k=\frac{1}{N_k}\sum_{n:z_n=k}x_n\ \ (\text{mean minimizes squared distance}\ \Rightarrow\ J\downarrow)$$
$$\text{k-means++: }\ p(x_n\ \text{chosen as next seed})\ \propto\ D(x_n)^2,\qquad D(x_n)=\min_{j}\|x_n-\mu_j\|$$
$$\text{EM link: }\ \text{K-means}=\lim_{\sigma\to 0}\ \text{hard-EM with }\Sigma_k=\sigma^2 I\ \ (\text{isotropic}\cdot\text{equal-size assumption})$$
What to watch수업 관찰 포인트
- Both half-steps lower J: Assign minimizes each point's term individually; Update uses the mean, which is the minimizer of squared distance — the J curve steps down at every half-step (contrast with EM, where ℓ rose only at the M-step). Since the number of partitions is finite, it converges in a finite number of steps — 0 reassignments is the stopping condition.두 반스텝 모두 J↓: 할당은 각 점의 항을 개별 최소화, 갱신은 평균이 제곱거리의 최소자 — J 곡선이 매 반스텝 계단으로 내려간다 (EM에서 ℓ는 M-step에서만 오르던 것과 대비). 분할의 가짓수가 유한하므로 유한 스텝 수렴 — 재할당 0이 종료 조건.
- Initialization: Repeatedly re-initializing with random init lands on different local optima (compare against the best-J record). Switching to k-means++ gives a lower J from the very first step and sharply cuts the chance of falling into a bad solution — because D²-proportional sampling picks seeds that are far apart.초기화: 무작위 초기화로 재초기화를 반복하면 다른 국소 최적(최저 J 기록과 비교). k-means++로 바꾸면 첫 J부터 낮고 나쁜 해에 빠질 확률이 급감 — D² 비례 샘플링이 멀리 떨어진 씨앗을 고르기 때문.
- Drag a centroid directly — J jumps up (red dot), then the algorithm pulls it back down. Cramming two centroids into a single cluster also reproduces getting stuck in a local optimum where a cluster is split.중심을 직접 드래그해 보라 — J가 튀어오른 뒤(붉은 점) 알고리즘이 다시 끌어내린다. 한 군집에 중심 두 개를 몰아넣으면 군집이 쪼개진 국소 최적에 갇히는 것도 재현된다.
- Model assumptions: On elongated / unequal-size data the Voronoi boundaries are straight lines, so they cut through elongated clusters and carve up large ones — K-means is hard EM with a fixed σ²I and σ→0 (isotropic, equal-variance assumption). If you need a full Σ, use a GMM.모델 가정: 길쭉/크기 차이 데이터에서 Voronoi 경계는 직선이라 길쭉한 군집을 자르고 큰 군집을 나눠 갖는다 — K-means는 σ²I 고정, σ→0의 hard EM(등방·등분산 가정). Full Σ가 필요하면 GMM으로.
- Elbow: J decreases monotonically in K — chasing the minimum just gives K=n. On separated data it drops sharply at K=3 then flattens (the bend); on ring data the elbow itself is ambiguous — if the model is wrong, choosing K is meaningless too.엘보: J는 K에 대해 단조 감소 — 최소를 찾으면 K=n이 된다. 분리 데이터에선 K=3에서 급락 후 평평(꺾임), 고리 데이터에선 엘보 자체가 애매 — 모델이 틀리면 K 선택도 무의미하다.