[KC] K-means Clustering

K-means Clustering

저자: James MacQueen

발행년도: 1967년

인용수: 50000회

arXiv ID: 2310.01195

---

K-means Clustering: 군집화의 시작점이 된 단순하지만 강력한 알고리즘

문제 정의 (Problem Definition)

1967년, James MacQueen은 데이터 과학 분야의 가장 근본적인 질문 중 하나에 답하려 했다. "구조화되지 않은 데이터에서 어떻게 의미 있는 그룹을 찾을 것인가?"

당시 통계학과 컴퓨터 과학이 만나는 지점에서, 연구자들은 대량의 데이터 포인트들을 유사성에 기반해 자동으로 분류하는 방법을 찾고 있었다. 레이블이 없는 데이터에서 패턴을 발견하는 것은 시장 세분화부터 생물학적 분류까지 다양한 분야에서 필수적인 작업이었다.

MacQueen이 주목한 핵심 문제는 계산 가능성과 해석 가능성의 균형이었다. 데이터를 K개의 군집으로 나누되, 각 군집 내의 점들이 서로 가깝고 다른 군집과는 멀리 떨어져 있어야 했다. 동시에 이 과정이 컴퓨터로 효율적으로 계산될 수 있어야 했다.

실제 데이터 환경에서는 여러 도전 과제가 있었다. 데이터의 차원이 높아질수록 거리의 의미가 희석되고, 이상치가 군집 형성을 방해하며, 적절한 군집 수 K를 미리 알기 어렵다는 문제가 있었다. 또한 초기 조건에 따라 결과가 달라질 수 있다는 불확실성도 해결해야 했다.

기존 방법의 한계 (Motivation)

K-means 이전의 군집화 방법들은 주로 계층적 접근법(hierarchical clustering)에 의존했다. 모든 데이터 포인트 쌍의 거리를 계산하고, 가장 가까운 것부터 순차적으로 병합하거나 분할하는 방식이었다. 이 방법은 직관적이었지만 O(n²) 이상의 계산 복잡도로 대규모 데이터셋에는 적용하기 어려웠다.

또 다른 접근법은 밀도 기반 방법들이었다. 데이터가 밀집된 영역을 찾아 군집으로 정의하는 방식인데, 밀도의 임계값을 설정하는 것이 주관적이고 고차원에서는 밀도 추정 자체가 어려웠다. 무엇보다 군집의 모양이 구형이 아닌 경우 성능이 떨어졌다.

그래프 기반 방법들도 존재했다. 데이터 포인트를 노드로, 유사성을 간선으로 표현한 뒤 그래프 분할 알고리즘을 적용하는 방식이었다. 하지만 그래프 구성 자체에 O(n²) 시간이 걸리고, 최적 분할을 찾는 것은 NP-hard 문제였다.

출처: ar5iv (Figure 3)

> 흥미롭게도 MacQueen은 이러한 기존 방법들을 자세히 비교하지 않았다. 논문에서는 주로 자신의 방법론 설명에 집중했는데, 이는 당시 학술적 관행이었을 수도 있지만 현대적 관점에서는 아쉬운 부분이다.

제안 방법의 핵심 아이디어 (Key Idea)

K-means의 핵심 아이디어는 놀랍도록 단순했다. "각 군집을 대표하는 중심점을 설정하고, 데이터 포인트들을 가장 가까운 중심점에 할당한 후, 중심점을 다시 계산하는 과정을 반복한다."

이를 축구팀 주장 선출에 비유할 수 있다. K명의 임시 주장을 정하고, 각 선수는 자신과 가장 잘 맞는 주장의 팀에 들어간다. 그 후 각 팀에서 모든 선수의 중간 위치에 있는 사람을 새 주장으로 선출한다. 이 과정을 팀 구성이 변하지 않을 때까지 반복하는 것이다.

기존 방법들과의 핵심 차이는 반복적 최적화 접근법이었다. 전역 최적해를 한 번에 찾으려 하지 않고, 지역적으로 개선하는 단계를 반복함으로써 계산 효율성을 크게 높였다. 각 반복에서 O(nK) 시간만 필요했고, 실제로는 적은 수의 반복으로 수렴했다.

출처: ar5iv (Figure 5)

> 이 아이디어가 정말 혁신적이었는지는 의문이다. EM 알고리즘과의 유사성이나, 물리학의 평형 상태 개념과의 연관성을 고려하면 다양한 분야의 아이디어가 융합된 것으로 보인다.

아키텍처 설명 (Architecture)

K-means 알고리즘의 전체 파이프라인은 다음과 같이 구성된다.

먼저 K개의 초기 중심점을 선택한다. MacQueen은 데이터셋에서 무작위로 K개 점을 선택하는 방법을 제안했다. 각 데이터 포인트 x_i에 대해 모든 중심점 μ_j까지의 거리를 계산하고, 가장 가까운 중심점의 군집에 할당한다.

# K-means 핵심 로직 (pseudo-code)

![Figure 6](https://ar5iv.org/html/2310.01195/assets/x3.png)
*출처: ar5iv (Figure 6)*
def k_means(data, K, max_iter=100):
    # 1. 초기화
    centers = randomly_select(data, K)
    
    for iteration in range(max_iter):
        # 2. 할당 단계
        clusters = [[] for _ in range(K)]
        for point in data:
            nearest = argmin([distance(point, c) for c in centers])
            clusters[nearest].append(point)
        
        # 3. 갱신 단계
        new_centers = []
        for cluster in clusters:
            if len(cluster) > 0:
                new_centers.append(mean(cluster))
            else:
                new_centers.append(randomly_select(data, 1))
        
        # 4. 수렴 확인
        if centers == new_centers:
            break
        centers = new_centers
    
    return clusters, centers

할당 단계에서는 각 점을 가장 가까운 중심점의 군집에 배치한다. 이는 보로노이 다이어그램을 형성하는 과정과 동일하다. 갱신 단계에서는 각 군집에 속한 점들의 평균을 계산해 새로운 중심점으로 설정한다.

이 구조가 문제 해결에 적합한 이유는 제곱오차합(SSE)을 단조 감소시키기 때문이다. 각 단계가 목적함수를 개선하므로 알고리즘은 반드시 수렴한다. 다만 전역 최적해는 보장되지 않는다.

접근 방법의 특징 및 설계 의도 (Design Choices)

K-means의 주요 설계 선택들을 살펴보면 실용성에 대한 고려가 돋보인다.

유클리드 거리 사용은 계산이 간단하고 기하학적 해석이 명확하다는 장점이 있었다. 하지만 이는 모든 특징이 동등한 중요도를 가진다고 가정하며, 범주형 변수에는 적용하기 어렵다는 한계가 있다.

평균을 중심점으로 사용하는 것은 제곱오차를 최소화하는 자연스러운 선택이었다. 하지만 이는 군집이 구형이고 크기가 비슷하다는 암묵적 가정을 내포한다. 또한 이상치에 민감하여 중앙값 기반 방법(K-medoids)이 대안으로 제시되기도 했다.

하드 클러스터링 방식, 즉 각 점이 정확히 하나의 군집에만 속하도록 하는 설계는 해석이 명확하다는 장점이 있다. 하지만 경계에 있는 애매한 점들을 처리하기 어렵고, 이는 후에 퍼지 K-means로 확장되는 계기가 되었다.

> MacQueen은 이러한 설계 선택에 대한 ablation study를 제공하지 않았다. 다른 거리 척도나 중심점 계산 방법과의 비교가 없어 아쉽다. 현대적 관점에서는 각 설계 요소의 영향을 실험적으로 검증하는 것이 필수적이다.

실험 결과 분석

논문에서 제시된 실험은 현대 기준으로는 매우 제한적이었다. 주로 2차원이나 3차원의 합성 데이터셋에서 알고리즘의 동작을 시각적으로 확인하는 수준이었다.

수렴 속도에 대한 분석에서는 대부분의 경우 10-20회 반복 내에 수렴한다고 보고했다. 하지만 이는 데이터셋의 특성과 초기값 선택에 크게 의존하며, worst-case 분석이 부족했다.

초기값 민감성 문제는 언급되었지만 체계적으로 다루지 않았다. 여러 번 실행해서 가장 좋은 결과를 선택하라는 제안은 있었지만, 이에 대한 이론적 근거나 실험적 검증이 부족했다.

> 가장 큰 문제는 다른 군집화 방법들과의 정량적 비교가 전무하다는 점이다. 계산 시간, 군집화 품질, 확장성 등 다양한 측면에서의 비교 실험이 있었다면 논문의 설득력이 훨씬 높아졌을 것이다.

총평: 개인적 해석과 후속 연구 방향

K-means는 단순함의 힘을 보여주는 알고리즘이다. 복잡한 최적화 문제를 간단한 반복 과정으로 풀어냈고, 이는 실용적인 도구로서 광범위한 채택을 이끌어냈다. 하지만 동시에 많은 한계점도 명확하다.

실제 프로젝트 적용 시 K-means는 빠른 프로토타이핑과 초기 데이터 탐색에 유용하다. 계산이 빠르고 결과 해석이 직관적이기 때문이다. 하지만 최종 모델로 사용하기에는 군집 모양 가정, K값 선택, 초기값 민감성 등의 문제가 있다.

만약 내가 이 연구를 발전시킨다면 다음 방향들을 탐구하고 싶다. 첫째, 적응적 K 선택 메커니즘을 개발해 데이터에서 자동으로 최적의 군집 수를 찾는 방법을 연구할 것이다. 둘째, 제약 조건을 포함한 K-means를 개발해 도메인 지식을 알고리즘에 통합하는 방법을 찾을 것이다. 셋째, 온라인 K-means 알고리즘을 개발해 스트리밍 데이터 환경에서도 효율적으로 동작하도록 할 것이다.

K-means의 진정한 기여는 알고리즘 자체보다도 비지도 학습 문제를 최적화 관점에서 바라보는 프레임워크를 제시했다는 점이다. 이는 후속 연구들이 더 정교한 목적함수와 최적화 기법을 개발하는 토대가 되었다.