k-평균 군집화

목표: 데이터를 두 개 이상의 클러스터로 분할한다.

k-평균 군집화의 기본 아이디어는 데이터 집합을 분석해 데이터 내부에 자연스럽게 존재하는 클러스터(관련된 객체들의 그룹)가 있는지 파악하는 것이다.

k-평균 알고리즘은 비지도 학습 알고리즘이다. 데이터에 어떤 패턴이 있는지 미리 알지 못한다. 즉, 데이터에 공식적인 분류가 없다. 하지만 데이터를 어떤 방식으로든 그룹으로 나누고자 한다.

예를 들어, k-평균을 사용해 이미지에서 가장 두드러지는 3가지 색상을 찾을 수 있다. 이를 위해 픽셀을 색상 값을 기준으로 3개의 클러스터로 그룹화하도록 지시한다. 또는 관련된 뉴스 기사를 미리 카테고리를 정하지 않고 그룹화할 수도 있다. 알고리즘이 자동으로 가장 적합한 그룹을 찾아준다.

k-평균에서 "k"는 숫자를 의미한다. 알고리즘은 데이터 내부에 k개의 중심점이 존재하며, 다양한 데이터 요소들이 이 중심점 주위에 흩어져 있다고 가정한다. 이 센트로이드에 가장 가까운 데이터들이 같은 그룹으로 분류된다.

k-평균은 각 데이터 그룹의 분류 기준을 알려주지 않는다. 뉴스 기사를 그룹으로 나눈 후, 그룹 1이 과학, 그룹 2가 연예인, 그룹 3이 다가오는 선거에 관한 것이라고 말하지 않는다. 단지 관련된 뉴스 기사들이 함께 모여 있다는 사실만 알 수 있을 뿐, 그 관계가 무엇을 의미하는지는 알려주지 않는다. k-평균은 잠재적으로 존재하는 클러스터를 찾는 데 도움을 줄 뿐이다.

알고리즘

k-Means 알고리즘은 핵심적으로 매우 간단하다.

먼저, 초기 중심점(centroid)으로 k개의 임의 데이터 포인트를 선택한다. 그런 다음 클러스터를 찾을 때까지 다음 두 단계를 반복한다:

각 데이터 포인트에 대해 가장 가까운 중심점을 찾는다. 각 포인트를 가장 가까운 중심점에 할당한다.
중심점을 해당 클러스터 내 데이터 포인트의 평균으로 업데이트한다. 중심점을 클러스터의 실제 중심에 위치하도록 이동시킨다.

중심점을 이동시키면 해당 클러스터에 속하는 데이터 포인트가 바뀌기 때문에 이 과정을 여러 번 반복해야 한다. 이 과정은 모든 것이 안정될 때까지 반복된다. 이때 "수렴(convergence)"에 도달한다. 즉, 중심점이 더 이상 움직이지 않게 된다.

k-Means에 필요한 주요 파라미터는 다음과 같다:

k: 찾으려는 중심점의 개수다. 예를 들어 뉴스 기사를 그룹화하려면, 찾고자 하는 그룹의 수가 된다.
수렴 거리(convergence distance): 특정 업데이트 단계 후 모든 중심점이 이 거리보다 적게 움직이면 알고리즘을 종료한다.
거리 함수(distance function): 데이터 포인트가 중심점으로부터 얼마나 떨어져 있는지 계산해 가장 가까운 중심점을 찾는다. 다양한 거리 함수를 사용할 수 있지만, 일반적으로 유클리드 거리 함수가 적합하다(피타고라스 정리). 그러나 고차원 데이터에서는 수렴에 도달하지 못할 수 있다.

예제를 통해 자세히 살펴보자.

좋은 클러스터링 예제

이 첫 번째 예제는 k-Means가 세 개의 클러스터를 모두 찾아내는 과정을 보여준다. 이 예제에서 원은 데이터 포인트를 나타내고 별은 중심점(centroid)을 나타낸다.

첫 번째 반복에서 세 개의 데이터 포인트를 무작위로 선택하고 중심점을 그 위에 배치한다. 이후 각 반복에서 중심점과 가장 가까운 데이터 포인트를 찾고, 중심점을 해당 데이터 포인트들의 평균 위치로 이동시킨다. 이 과정은 중심점이 더 이상 움직이지 않는 균형 상태에 도달할 때까지 반복된다.

초기 중심점 선택이 운이 좋았다! 왼쪽 아래 클러스터(빨간색으로 표시)를 찾았고, 중앙과 왼쪽 위 클러스터도 꽤 잘 찾아냈다.

참고: 이 예제는 k-Means의 정확한 동작과 클러스터를 찾는 과정을 보여주기 위해 고안되었다. 이 예제의 클러스터는 인간의 눈으로도 쉽게 식별할 수 있다: 왼쪽 아래, 오른쪽 위, 그리고 중앙에 각각 하나씩 있다. 그러나 실제 데이터는 여러 차원을 가질 수 있고 시각화가 불가능할 수도 있다. 이런 경우 k-Means가 인간의 눈보다 훨씬 더 나은 성능을 발휘한다!

잘못된 클러스터링

다음 두 예제는 k-Means 알고리즘의 예측 불가능성과 항상 최적의 클러스터링을 찾지 못하는 경우를 보여준다.

이 예제에서 볼 수 있듯이, 초기 중심점들이 서로 너무 가깝게 위치했고, 파란색 중심점은 적절한 위치로 이동하지 못했다. 수렴 거리를 조정하면 데이터에 맞는 더 나은 중심점을 찾을 수 있다.

이 예제에서는 파란색 클러스터가 빨간색 클러스터와 완전히 분리되지 못하고, 결국 아래쪽에 붙어버린 상황이다.

잘못된 클러스터링 개선하기

이 예제에서 "잘못된" 클러스터링은 알고리즘이 지역 최적점에 갇힌 경우다. 클러스터를 찾기는 하지만 데이터를 나누는 최적의 방법은 아니다. 성공 확률을 높이려면 알고리즘을 여러 번 실행하고, 매번 다른 점을 초기 중심점으로 설정한다. 그중 가장 좋은 결과를 보여주는 클러스터링을 선택한다.

클러스터링이 얼마나 "좋은지" 계산하려면 각 데이터 포인트에서 해당 클러스터까지의 거리를 구하고, 이 거리들을 모두 더한다. 이 숫자가 작을수록 더 좋은 결과다! 이는 각 클러스터가 데이터 포인트 그룹의 정중앙에 위치하고, 모든 클러스터가 대체로 비슷한 크기이며 균등하게 분포한다는 의미다.

코드 설명

다음은 Swift로 구현한 알고리즘 예제다. points 배열은 입력 데이터를 Vector 객체로 담고 있다. 결과는 발견된 클러스터를 나타내는 Vector 객체 배열이다.

func kMeans(numCenters: Int, convergeDistance: Double, points: [Vector]) -> [Vector] {
 
  // 입력 데이터에서 무작위로 k개의 객체를 선택해 초기 중심점을 만든다.
  var centers = reservoirSample(points, k: numCenters)

  // 중심점이 이전 반복 대비 convergeDistance보다 적게 이동할 때까지 반복한다.
  var centerMoveDist = 0.0
  repeat {
    // 각 반복에서 중심점을 새로운 위치로 이동시킨다.
    // newCenters 배열은 새로운 위치를 담는다.
    let zeros = [Double](count: points[0].length, repeatedValue: 0)
    var newCenters = [Vector](count: numCenters, repeatedValue: Vector(zeros))

    // 각 중심점에 속한 데이터 포인트의 수를 추적해 평균을 계산한다.
    var counts = [Double](count: numCenters, repeatedValue: 0)

    // 각 데이터 포인트에 대해 가장 가까운 중심점을 찾는다.
    // 해당 중심점에 속한 데이터 포인트를 더해 평균을 계산한다.
    for p in points {
      let c = indexOfNearestCenter(p, centers: centers)
      newCenters[c] += p
      counts[c] += 1
    }
    
    // 각 중심점에 속한 데이터 포인트의 평균을 계산한다.
    // 이렇게 해서 중심점을 새로운 위치로 이동시킨다.
    for idx in 0..<numCenters {
      newCenters[idx] /= counts[idx]
    }

    // 이전 반복 대비 각 중심점이 얼마나 이동했는지 계산한다.
    // 이동 거리가 작으면 반복을 종료한다.
    centerMoveDist = 0.0
    for idx in 0..<numCenters {
      centerMoveDist += centers[idx].distanceTo(newCenters[idx])
    }
    
    centers = newCenters
  } while centerMoveDist > convergeDistance

  return centers
}

참고: KMeans.swift 파일의 코드는 위 예제보다 조금 더 고급 기능을 포함한다. 클러스터에 라벨을 할당하고 몇 가지 추가 기법도 사용한다. 확인해 보자!

성능

k-Means는 NP-Hard 유형의 문제로 분류된다. 이는 최적의 해를 찾는 것이 거의 불가능하다는 것을 의미한다. 초기 중심점의 선택은 최종 클러스터가 어떻게 형성될지에 큰 영향을 미친다. 정확한 해를 찾는 것은 2차원 공간에서도 어려운 일이다.

위 단계에서 볼 수 있듯이, 복잡도는 그렇게 나쁘지 않다. 일반적으로 **O(kndi)**로 간주되며, 여기서 k는 중심점의 수, n은 d차원 벡터의 수, i는 수렴을 위한 반복 횟수를 나타낸다.

데이터의 양은 k-Means의 실행 시간에 선형적인 영향을 미치지만, 중심점이 수렴할 거리를 조정하는 것은 반복 횟수에 큰 영향을 줄 수 있다. 일반적으로 k는 벡터의 수에 비해 상대적으로 작아야 한다.

더 많은 데이터가 추가되면 두 중심점 사이의 경계에 위치한 점들이 생길 수 있다. 이러한 경우 중심점이 앞뒤로 계속 튕길 수 있으므로, 수렴 거리를 조정해 이를 방지해야 한다.

함께 보기

위키백과의 K-평균 클러스터링

작성: John Gill, Matthijs Hollemans