이등분 K-평균(Bisecting K-Means)이란?
이등분 K-평균(Bisecting K-Means)은 기본 K-평균(K-means) 알고리즘을 단순히 확장한 군집화 기법으로, 매우 직관적인 아이디어에 기반합니다. 즉, K개의 클러스터를 얻기 위해 전체 데이터 포인트 집합을 먼저 두 개의 클러스터로 분할하고, 그중 하나를 선택해 다시 둘로 나누는 과정을 반복하여 최종적으로 K개의 클러스터가 만들어질 때까지 진행하는 방식입니다.
K-평균 알고리즘의 기본 원리
K-평균 알고리즘은 입력 매개변수 k를 받아 n개의 객체를 k개의 클러스터로 나눕니다. 이때 목표는 클러스터 내부 유사도(intracluster similarity)는 높게, 클러스터 간 유사도(intercluster similarity)는 낮게 만드는 것입니다. 클러스터 유사도는 해당 클러스터에 속한 객체들의 평균값을 기준으로 평가되며, 이 평균값은 클러스터의 중심(centroid), 즉 무게중심(center of gravity)으로 볼 수 있습니다.
평균값의 초기값은 임의로 지정됩니다. 무작위로 선택할 수도 있고, 처음 k개 입력 객체의 값 자체를 초기 중심으로 사용할 수도 있습니다. 수렴 조건은 일반적으로 제곱 오차(squared error)를 기반으로 하지만 반드시 그래야 하는 것은 아닙니다. 예를 들어 하나의 객체가 여러 클러스터에 할당되도록 알고리즘을 변형할 수도 있으며, 고정된 반복 횟수를 종료 조건으로 삼거나, 수렴하지 않더라도 안전하게 종료할 수 있도록 최대 반복 횟수를 설정하는 방식도 활용됩니다.
이등분 K-평균 알고리즘의 절차
- 초기화: 모든 데이터 포인트를 포함하는 단일 클러스터로 클러스터 목록을 초기화합니다.
- 클러스터 선택: 클러스터 목록에서 분할 대상이 될 클러스터 하나를 꺼냅니다.
- 시험 이등분: 선택된 클러스터에 대해 여러 번의 "시험(trial)" 이등분을 수행합니다. 각 시험에서는 기본 K-평균 알고리즘을 이용해 해당 클러스터를 둘로 나눕니다.
- 최적 분할 선택: 여러 시험 결과 중 총 SSE(오차제곱합)가 가장 작은 분할, 즉 두 개의 클러스터를 선택합니다.
- 목록 갱신: 선택된 두 클러스터를 클러스터 목록에 다시 추가합니다.
- 종료 조건: 클러스터 목록에 K개의 클러스터가 포함될 때까지 위 과정을 반복합니다.
분할할 클러스터를 선택하는 기준
어떤 클러스터를 분할할지 결정하는 방법은 여러 가지가 있습니다. 매 단계에서 데이터 포인트가 가장 많은 클러스터를 선택할 수도 있고, SSE가 가장 큰 클러스터를 선택할 수도 있으며, 크기와 SSE를 모두 고려한 복합 기준을 사용할 수도 있습니다. 어떤 선택 기준을 적용하느냐에 따라 최종적으로 형성되는 클러스터의 형태가 달라질 수 있다는 점에 유의해야 합니다.
결과 클러스터의 후처리와 한계
이등분 K-평균으로 얻은 결과 클러스터는, 각 클러스터의 중심점(centroid)을 초기 중심값으로 사용하여 기본 K-평균 알고리즘을 한 번 더 적용함으로써 더욱 개선할 수 있습니다. 이 과정이 중요한 이유는 다음과 같습니다. 기본 K-평균 알고리즘은 SSE 관점에서 국소 최솟값(local minimum)에 해당하는 군집화 결과를 찾는 것이 보장되지만, 이등분 K-평균에서는 K-평균을 "국소적으로", 즉 개별 클러스터를 이등분하는 용도로만 사용하기 때문입니다. 따라서 최종적으로 얻어진 클러스터 집합은 전체 SSE 관점에서 국소 최솟값이 되는 군집화 결과를 보장하지 않습니다.
계층적 군집화로의 확장
마지막으로, K-평균이 클러스터를 이등분해 가는 과정에서 생성되는 일련의 군집화 결과를 순서대로 기록해 두면, 이등분 K-평균을 활용해 계층적 군집화(hierarchical clustering)를 수행할 수도 있습니다. 이처럼 이등분 K-평균은 단순하면서도 유연한 알고리즘으로, 대규모 데이터셋에서 효율적인 군집화 및 계층 구조 분석에 널리 활용됩니다.