4 / 10강

K-means로 중심을 옮기기

그룹 수 K를 먼저 정하고 각 그룹의 중심을 찾는 방법이 K-means입니다. 표준 K-means는 점과 중심 사이의 유클리드 거리 제곱 합을 줄이는 것을 목표로 합니다.

배정과 갱신을 반복합니다

1. K개의 초기 중심을 고릅니다.
2. 각 점을 가장 가까운 중심에 배정합니다.
3. 그룹에 배정된 점들의 평균으로 중심을 갱신합니다.
4. 배정이나 중심이 거의 변하지 않을 때까지 반복합니다.

values = [1, 2, 8, 9]
centers = [1, 9]
for _ in range(20):
    groups = [[], []]
    for value in values:
        closest = min(range(2), key=lambda i: (value - centers[i]) ** 2)
        groups[closest].append(value)
    updated = [sum(g) / len(g) if g else centers[i]
               for i, g in enumerate(groups)]
    if updated == centers:
        break
    centers = updated
print(centers)

출력은 [1.5, 8.5]입니다. 1과 2, 8과 9가 각각 묶입니다. 예제는 빈 그룹이 생기면 이전 중심을 유지하며 최대 20번만 반복합니다. 실제 구현에서는 수렴 허용 오차와 빈 그룹 처리 규칙을 정해야 합니다.

거리와 중심의 짝을 맞춥니다

제곱 거리 합을 최소화하는 중심은 평균입니다. 맨해튼 거리를 쓰면서 같은 목적을 기대한다면 중앙값을 쓰는 K-medians 등과 구분해야 합니다. 거리 이름만 바꾸고 같은 알고리즘이라고 설명하면 목적 함수가 어긋납니다.

K-means는 초기 중심에 따라 다른 지역 최솟값에 도달할 수 있습니다. 길게 늘어진 그룹이나 서로 다른 밀도의 그룹에서도 기대와 다르게 묶일 수 있습니다.

확인 문제

K를 데이터 수와 같게 하고 모든 점을 각자의 중심으로 만들면 거리 제곱 합은 얼마인가요? 그것이 늘 좋은 군집화일까요?