K-Means 군집화 — 중심점을 반복 갱신해 K개 그룹으로 나누는 법

K개의 군집 수를 미리 정하고 시작한다는 점이 K-Means를 다른 군집화 기법과 가른다. 비지도 학습의 대표 격인 이 알고리즘은 데이터 포인트와 군집 중심점(centroid) 사이의 거리를 기준으로, 중심점을 반복해서 옮겨가며 군집을 형성한다. 이름의 K는 사용자가 미리 지정해야 하는 군집 수, Means는 각 군집에 속한 데이터 포인트들의 평균 위치를 중심점으로 쓴다는 뜻이다.

중심점이 자리를 잡아가는 절차

K-Means는 다음 단계를 거치며 동작한다.

초기화 단계: K개의 중심점(Centroid)을 무작위로 선택한다.
할당 단계: 각 데이터 포인트를 가장 가까운 중심점에 할당하여 K개의 군집을 형성한다.
업데이트 단계: 각 군집에 할당된 데이터 포인트들의 평균 위치로 중심점을 재계산한다.
수렴 단계: 중심점의 위치가 더 이상 변하지 않거나 미리 정한 반복 횟수에 도달할 때까지 2~3단계를 반복한다.

⤢✕

거리는 어떻게 재고, 무엇을 최소화하는가

가장 일반적으로 쓰이는 거리 측정법은 유클리드 거리(Euclidean Distance)다. 2차원 공간에서 두 점 간의 유클리드 거리는

d(x, y) = √[(x₁ - y₁)² + (x₂ - y₂)²]

로 쓰고, 다차원 공간으로 확장하면

d(x, y) = √[∑(xᵢ - yᵢ)²], i=1,2,...,n

이 된다. 그 밖에 맨해튼 거리(Manhattan Distance) d(x, y) = ∑|xᵢ - yᵢ|와, 벡터 간의 각도를 기반으로 한 코사인 유사도(Cosine Similarity)도 쓸 수 있다.

K-Means는 다음 목적 함수를 최소화하는 방향으로 작동한다.

J = ∑ᵏⱼ₌₁ ∑ᵢ∈Cⱼ ‖xᵢ - μⱼ‖²

여기서 J는 목적 함수(비용 함수), k는 군집의 수, Cⱼ는 j번째 군집, xᵢ는 i번째 데이터 포인트, μⱼ는 j번째 군집의 중심점이며, ‖xᵢ - μⱼ‖²은 데이터 포인트와 중심점 간의 유클리드 거리의 제곱이다. 이 목적 함수는 각 데이터 포인트와 그것이 속한 군집의 중심점 간의 거리 제곱의 합을 나타낸다.

적정 K값을 찾는 방법

적절한 K 값을 선정하는 것은 K-Means의 성능에 중요한 영향을 미친다.

**엘보우 방법(Elbow Method)**은 다양한 K 값에 대해 WCSS(Within-Cluster Sum of Squares, 각 군집 내 데이터 포인트들과 중심점 간의 거리 제곱 합)를 계산한다. K를 증가시키면 WCSS는 감소하는 경향을 보이는데, WCSS가 급격히 감소하다가 완만해지는 '엘보우(팔꿈치)' 지점을 최적 K 값으로 본다.

⤢✕

**실루엣 방법(Silhouette Method)**은 각 데이터 포인트에 대한 실루엣 계수를 계산한다. 실루엣 계수는 -1에서 1 사이의 값으로, 1에 가까울수록 군집화가 잘 되었음을 의미하며, 평균 실루엣 계수가 가장 높은 K 값을 선택한다.

**갭 통계량(Gap Statistic)**은 관측된 군집화 결과와 무작위 분포에서 예상되는 결과 간의 차이를 측정해, 갭 통계량이 가장 큰 K 값을 선택하는 방식이다.

장점과 한계

구현이 간단하고 계산 효율성이 높으며, 대용량 데이터에도 확장 가능하다. 선형 시간 복잡도 O(n·k·d·i)(n: 데이터 포인트 수, k: 군집 수, d: 차원 수, i: 반복 횟수)를 가져 다양한 도메인에 적용할 수 있는 범용성도 갖췄다.

반면 초기 중심점 선택에 따라 결과가 달라지는 불안정성이 있고, 최적의 K 값을 사전에 결정해야 하는 어려움이 있다. 구형(spherical) 군집 형태에 최적화되어 있어 복잡한 형태의 군집 탐지에 취약하고, 이상치(Outlier)에 민감하게 반응하며, 군집의 크기가 불균형한 경우 성능이 떨어진다.

표준 K-Means의 변형들

**K-Means++**는 초기 중심점 선택 방법을 개선한 알고리즘이다. 첫 번째 중심점은 무작위로 선택하고, 이후 중심점들은 기존 중심점으로부터 거리가 먼 데이터 포인트를 확률적으로 선택해, 초기 중심점들이 서로 멀리 떨어지게 함으로써 더 안정적인 결과를 이끌어낸다.

**미니 배치 K-Means(Mini-Batch K-Means)**는 전체 데이터셋 대신 무작위로 선택된 소규모 배치에 대해 학습을 진행한다. 대규모 데이터셋에서 계산 효율성을 높이고 메모리 사용량을 줄이며 실행 속도를 향상시킨다.

**퍼지 K-Means(Fuzzy K-Means)**는 데이터 포인트가 단일 군집에만 속하는 것이 아니라 여러 군집에 소속 확률을 부여하는 방식으로, 군집 간 경계가 명확하지 않은 경우에 유용하다.

고객 세분화부터 문서 군집화까지

**고객 세분화(Customer Segmentation)**에서는 구매 패턴, 인구통계 정보 등을 기반으로 고객 그룹을 식별해 마케팅 전략 수립과 타깃 광고 최적화에 활용한다. 예를 들어 온라인 쇼핑몰에서는 구매 이력, 방문 빈도, 평균 지출액 등의 지표로 고객 그룹을 분류한다.

**이미지 압축(Image Compression)**에서는 이미지의 색상 팔레트를 K개의 대표 색상으로 줄이는 데 K-Means를 쓴다. RGB 색상 공간에서 주요 색상 군집을 식별해, 예컨대 24비트 컬러 이미지(16,777,216가지 색상)를 8비트(256가지 색상)로 압축한다.

**이상 탐지(Anomaly Detection)**는 정상 데이터 포인트들의 군집을 식별한 후, 어떤 군집에도 속하지 않거나 중심점과의 거리가 먼 데이터 포인트를 이상치로 탐지한다. 네트워크 트래픽 패턴 분석을 통한 침입 탐지 시스템이 대표적이다.

**문서 군집화(Document Clustering)**는 텍스트 데이터를 벡터화한 후 K-Means를 적용해 유사한 주제의 문서들을 그룹화한다. 뉴스 기사 자동 분류, 검색 엔진 결과 그룹화 등에 쓰인다.

이 밖에 데이터 거버넌스 전략 수립 시 데이터 특성에 따른 분류·관리 정책 결정, 정보시스템 사용자 행동 패턴 분석을 통한 UI/UX 최적화, 시스템 로그 분석을 통한 보안 위협 탐지, 조직 내 지식 관리 시스템에서의 문서 자동 분류, 대용량 데이터 처리 아키텍처 설계 시 데이터 특성 기반 파티셔닝 전략 수립에도 K-Means가 쓰인다.

구현할 때 챙길 것들

K-Means는 거리 기반 알고리즘이므로 특성 스케일링(Feature Scaling)으로 특성들의 스케일을 통일하는 것이 중요하다. 결측치는 K-Means가 직접 처리하지 못하므로 사전에 대체하거나 제거해야 하고, 고차원 데이터라면 PCA 등을 통한 차원 축소를 고려한다.

최적화 단계에서는 다양한 초기 중심점으로 여러 번 실행해 최적 결과를 고르는 여러 초기값 실행(Multiple Restarts), 무작위 초기화 대신 K-Means++를 적용하는 방법, 중심점 이동이 미미할 때 알고리즘을 조기 종료하는 방법을 쓸 수 있다.

결과 평가에는 각 데이터 포인트와 해당 군집 중심점 간의 거리 제곱 합인 군집 내 분산(Inertia), 군집 내 응집도와 군집 간 분리도를 종합 평가하는 실루엣 점수(Silhouette Score), 군집 내 유사성과 군집 간 차이를 기반으로 한 Davies-Bouldin 지수를 쓴다.