K-평균 군집화 (K-Means)

K-평균 군집화의 핵심 목표는 주어진 데이터 포인트들을 K개의 군집으로 나누는 것이다. 이 과정은 수학적으로 명확한 목적 함수를 최소화하는 최적화 문제로 공식화된다. 가장 일반적으로 사용되는 목적 함수는 왜곡(Distortion) 또는 제곱 오차 합(Sum of Squared Errors, SSE)으로, 각 데이터 포인트가 속한 군집의 중심(센트로이드)까지의 거리의 제곱 합을 의미한다.

목적 함수 *J*는 다음과 같이 정의된다.

$$J = \sum_{i=1}^{k} \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \mathbf{\mu}_i\|^2$$

여기서,

• $k$는 군집의 개수,

• $C_i$는 $i$번째 군집에 속한 데이터 포인트들의 집합,

• $\mathbf{\mu}_i$는 $C_i$ 군집의 센트로이드,

• $\|\mathbf{x} - \mathbf{\mu}_i\|$는 데이터 포인트 $\mathbf{x}$와 센트로이드 $\mathbf{\mu}_i$ 사이의 유클리드 거리이다.

이 함수 *J*를 최소화하는 것은 각 군집 내의 데이터 포인트들이 해당 군집의 중심에 최대한 가깝게 모여 있도록 하는 것을 의미한다. 그러나 이 최적화 문제는 NP-난해 문제로 알려져 있어, 모든 가능한 군집 할당에 대해 *J*를 계산하여 최솟값을 찾는 것은 현실적으로 불가능하다. 따라서 K-평균 알고리즘은 탐욕 알고리즘적 접근법을 사용한 효율적인 휴리스틱 방법을 제공한다.

알고리즘은 두 단계를 반복하여 목적 함수 *J*를 국소적으로 최소화한다.

1. 할당 단계: 각 데이터 포인트를 현재 센트로이드에서 가장 가까운 군집에 할당한다. 이는 주어진 센트로이드 $\mathbf{\mu}_i$에 대해 *J*를 최소화한다.

2. 갱신 단계: 새롭게 형성된 각 군집의 데이터 포인트들의 평균을 계산하여 새로운 센트로이드 $\mathbf{\mu}_i$로 갱신한다. 이는 주어진 군집 할당 $C_i$에 대해 *J*를 최소화한다.

이 두 단계를 반복할 때마다 목적 함수 *J*의 값은 감소하거나 변하지 않으며, 결국 수렴에 도달한다. 이 알고리즘은 좌표 하강법의 일종으로 볼 수 있으며, 일반적으로 국소 최적점에 빠지게 된다. 따라서 초기 센트로이드의 선택에 따라 최종 군집화 결과가 크게 달라질 수 있다.

K-평균 군집화 알고리즘은 주어진 데이터를 K개의 군집으로 나누기 위해 반복적으로 두 가지 주요 단계를 수행합니다. 이 단계들은 각각 할당 단계와 갱신 단계로 불리며, 알고리즘은 이 과정을 수렴할 때까지 반복합니다.

첫 번째 단계는 할당 단계입니다. 이 단계에서는 각 데이터 포인트를 가장 가까운 중심점에 할당하여 군집을 형성합니다. 거리 측정은 일반적으로 유클리드 거리를 사용합니다. 모든 데이터 포인트 $x_i$에 대해, $k$개의 중심점 $\mu_1, \mu_2, ..., \mu_k$ 중 가장 거리가 가까운 중심점의 군집에 소속됩니다. 수식으로 표현하면, 데이터 포인트 $x_i$는 다음 조건을 만족하는 군집 $S^{(t)}$에 할당됩니다.

$S^{(t)} = \{ x_i : \| x_i - \mu^{(t)}_k \|^2 \le \| x_i - \mu^{(t)}_j \|^2 \ \forall j, 1 \le j \le k \}$

여기서 $t$는 현재 반복 횟수를 나타냅니다.

두 번째 단계는 갱신 단계입니다. 할당 단계에서 형성된 새로운 군집을 바탕으로 각 군집의 중심점을 재계산합니다. 새로운 중심점은 해당 군집에 속한 모든 데이터 포인트의 좌표값의 평균으로 구해집니다. 군집 $S_k$에 대해 새로운 중심점 $\mu^{(t+1)}_k$는 다음과 같이 계산됩니다.

$\mu^{(t+1)}_k = \frac{1}{|S_k|} \sum_{x_i \in S_k} x_i$

이렇게 계산된 새로운 중심점들은 다음 할당 단계의 기준점이 됩니다.

이 두 단계는 알고리즘이 수렴 조건을 만족할 때까지 반복됩니다. 일반적인 수렴 조건은 중심점의 위치가 더 이상 변하지 않거나, 그 변화량이 미리 정해진 임계값보다 작아지는 것입니다. 할당 단계에서 군집 구성의 변화가 없을 때도 알고리즘은 종료됩니다. 이 과정을 통해 목적 함수인 군집 내 제곱 오차의 합이 국소 최소값에 도달하게 됩니다.

초기 중심점의 선택은 K-평균 군집화 알고리즘의 성능과 최종 군집 결과에 큰 영향을 미치는 중요한 단계이다. 임의로 선택된 중심점은 알고리즘이 지역 최적해에 빠지거나 수렴 속도가 느려지는 원인이 될 수 있다. 이를 완화하기 위해 여러 가지 개선된 초기화 방법이 제안되었다.

가장 기본적인 방법은 데이터 포인트 중에서 무작위로 K개의 샘플을 선택하는 것이다. 그러나 이 방법은 결과의 불안정성을 초래할 수 있어, 일반적으로 여러 번의 무작위 초기화를 수행하여 가장 좋은 결과를 선택하는 방식으로 보완한다. 보다 체계적인 방법으로는 K-평균++ 알고리즘이 널리 사용된다. K-평균++는 첫 번째 중심점을 무작위로 선택한 후, 다음 중심점을 선택할 때 현재까지 선택된 중심점들로부터 멀리 떨어진 데이터 포인트를 더 높은 확률로 선택하는 방식이다. 이는 중심점들이 서로 멀리 떨어지도록 하여 군집이 더 잘 분리되도록 유도한다.

다른 초기화 방법들도 존재한다. 데이터의 분포를 고려한 샘플링 방법이나, 계층적 군집화를 수행하여 얻은 결과를 초기 중심점으로 사용하는 방법 등이 있다. 또한, 데이터를 여러 개의 작은 서브셋으로 나누어 각 서브셋에서 K-평균을 실행한 후, 그 결과를 모아 전체 데이터에 대한 초기 중심점을 구성하는 방법도 연구되었다.

수렴 조건은 K-평균 군집화 알고리즘이 반복을 멈추고 최종 결과를 출력하는 기준을 정의한다. 일반적으로 두 가지 주요 조건이 사용된다.

첫 번째는 중심점의 이동이 매우 작아져서 더 이상 의미 있는 변화가 없을 때이다. 이는 각 반복(iteration)에서 계산된 새로운 중심점과 이전 중심점 사이의 거리(예: 유클리드 거리)를 모든 군집에 대해 합산하거나 최대값을 구하여, 이 값이 사전에 정의된 임계값(threshold)보다 작아지면 알고리즘을 종료하는 방식이다. 이 임계값은 보통 매우 작은 값(예: 1e-4, 1e-5)으로 설정하여 미미한 변동에 의해 무한 반복되는 것을 방지한다.

두 번째는 미리 정한 최대 반복 횟수에 도달했을 때이다. 이는 알고리즘이 너무 오랫동안 실행되는 것을 방지하는 안전 장치 역할을 한다. 중심점의 이동이 완전히 멈추지 않는 특이한 경우나 계산 시간을 제한해야 할 때 유용하다. 대부분의 구현에서는 두 조건을 함께 사용하며, 어느 하나라도 만족하면 알고리즘이 수렴했다고 판단하고 종료한다.

수렴 조건의 설정은 결과의 정밀도와 계산 비용 사이의 균형을 결정한다. 임계값을 너무 작게 설정하면 불필요한 반복이 증가하고, 너무 크게 설정하면 조기에 수렴하여 최적이 아닌 결과를 얻을 수 있다[6].

K-평균 군집화 알고리즘의 가장 큰 장점은 구현이 간단하고 직관적이며, 계산 효율이 매우 높다는 점이다. 알고리즘의 핵심 아이디어는 명확하여 이해하기 쉽고, 대규모 데이터셋에 대해서도 비교적 빠르게 실행된다. 이는 알고리즘의 복잡도가 데이터 포인트 수에 선형적으로 비례하기 때문이다.

다른 군집화 알고리즘에 비해 K-평균 군집화는 일반적으로 안정적인 결과를 제공하며, 군집이 구형(球形) 또는 등방성(等方性)을 가정할 때 효과적이다. 알고리즘이 널리 사용되면서 다양한 프로그래밍 언어와 머신러닝 라이브러리(scikit-learn, TensorFlow 등)에서 표준 구현체를 제공하여 접근성이 매우 높다.

이러한 특성들 덕분에 K-평균 군집화는 군집화 문제에 대한 기본적인 벤치마크 알고리즘이자, 실무에서 가장 먼저 고려되는 방법론 중 하나이다. 특히 초기 군집 중심을 무작위로 선택하는 특성 때문에, 여러 번 실행하여 가장 좋은 결과를 선택하는 방식으로 활용될 수 있다.

K-평균 군집화 알고리즘은 몇 가지 명확한 한계점을 지니고 있다. 첫째, 군집의 개수 K를 사전에 지정해야 한다는 점이다. 이는 데이터의 구조에 대한 사전 지식이 없을 경우 적절한 K 값을 결정하기 어렵게 만든다. K 값을 잘못 설정하면 과도하게 세분화되거나 지나치게 포괄적인 군집이 생성될 수 있다.

둘째, 초기 중심점(센트로이드)의 위치에 따라 최종 군집 결과가 크게 달라질 수 있다. 알고리즘이 국소 최적해(local optimum)에 빠질 가능성이 높기 때문에, 초기값에 민감하다는 단점이 있다. 이로 인해 동일한 데이터에 대해 서로 다른 실행 결과가 나올 수 있으며, 최적의 군집을 보장하지 못한다.

셋째, 군집의 모양에 제약이 있다. 알고리즘은 각 군집의 분산을 최소화하는 방식으로 동작하므로, 본질적으로 구형(spherical) 또는 등방성(isotropic)의 형태를 가진 군집을 잘 찾아내도록 설계되었다. 따라서 길쭉한 모양, 비선형 구조, 또는 밀도가 서로 다른 군집을 효과적으로 식별하지 못한다.

마지막으로, 알고리즘은 이상치에 매우 취약하다. 중심점은 소속 데이터 포인트들의 평균으로 계산되기 때문에, 극단적인 값을 가진 이상치가 존재하면 중심점이 해당 방향으로 끌려가 전체 군집 구조를 왜곡시킬 수 있다. 이는 K-메도이드 같은 변형 알고리즘이 개발되는 주요 동기가 되었다.

엘보우 방법은 K-평균 군집화 알고리즘에서 최적의 군집 수 K를 결정하기 위한 경험적 방법 중 하나이다. 이 방법은 군집 내 응집도를 나타내는 왜곡 지표를 K 값에 따라 시각화하여, 그래프 상에서 '팔꿈치'와 같이 꺾이는 지점을 최적의 K 값으로 선택한다.

주로 사용되는 왜곡 지표는 왜곡 또는 제곱 오차합이다. 이는 각 데이터 포인트가 속한 군집의 중심점까지의 거리의 제곱합을 의미하며, K 값이 증가할수록 일반적으로 이 값은 감소한다. 엘보우 방법에서는 K 값을 1부터 점차 증가시키면서 각 K에 대한 왜곡 값을 계산하고, 이를 그래프로 그린다. K 값이 증가함에 따라 왜곡의 감소 폭이 급격히 줄어드는 지점, 즉 그래프의 기울기가 크게 변화하는 '팔꿈치' 지점이 나타나는데, 이 지점의 K 값을 최적의 군집 수로 해석한다. 이는 군집 수를 더 늘려도 모델의 설명력이 크게 향상되지 않는 지점을 찾는 원리이다.

위 표와 같은 결과에서 K=3에서 K=4로 갈 때의 감소 폭(25.0)이 K=2에서 K=3으로 갈 때의 감소 폭(55.0)에 비해 현저히 줄어든다. 이 경우 K=3을 '팔꿈치' 지점으로 판단할 수 있다.

이 방법은 직관적이고 구현이 간단하다는 장점이 있지만, '팔꿈치' 지점이 명확하지 않거나 주관적으로 판단해야 하는 경우가 많다는 한계를 가진다. 또한 왜곡 지표는 군집의 크기나 밀도에 민감할 수 있다. 따라서 엘보우 방법은 실루엣 분석이나 겹정보기준과 같은 다른 방법과 함께 사용되어 최종 결정을 내리는 경우가 많다.

실루엣 분석은 K-평균 군집화를 포함한 다양한 군집 분석 알고리즘의 결과를 평가하고, 최적의 군집 수 K를 결정하는 데 사용되는 내부 평가 방법이다. 이 방법은 각 데이터 포인트가 자신이 속한 군집에 얼마나 잘 적합되어 있는지, 그리고 다른 군집과 얼마나 명확히 분리되어 있는지를 정량적으로 측정한다. 분석 결과는 실루엣 계수라는 단일 지표로 요약되며, 이 값은 -1부터 1 사이의 범위를 가진다.

실루엣 계수는 각 데이터 포인트 i에 대해 두 가지 거리 측정값을 기반으로 계산된다. 첫째, a(i)는 동일 군집 내의 다른 모든 포인트까지의 평균 거리로, 이 값이 작을수록 해당 포인트가 군집 내부에 잘 응집되어 있음을 의미한다. 둘째, b(i)는 해당 포인트에서 가장 가까운 다른 군집(이웃 군집) 내 모든 포인트까지의 평균 거리로, 이 값이 클수록 군집 간 분리가 잘 되었음을 나타낸다. 이 두 값을 사용하여 실루엣 계수 s(i)는 다음 공식으로 정의된다: s(i) = (b(i) - a(i)) / max{a(i), b(i)}.

전체 군집화 결과의 질은 모든 데이터 포인트의 실루엣 계수의 평균값으로 평가한다. 평균 실루엣 계수가 1에 가까울수록 군집 내 응집도는 높고 군집 간 분리도는 뚜렷한 우수한 군집화를 의미한다. 반면 0에 가까우면 군집 간 경계가 모호함을, 음수 값은 많은 포인트가 잘못된 군집에 할당되었을 가능성을 시사한다. 최적의 K 값을 선택하기 위해 서로 다른 K 값(예: 2, 3, 4, ...)에 대해 군집화를 수행하고 각각의 평균 실루엣 계수를 비교한다. 평균 실루엣 계수가 가장 높은 K를 선택하는 것이 일반적인 방법이다.

또한, 실루엣 다이어그램을 시각화하여 각 군집의 응집 상태와 상대적 크기를 한눈에 파악할 수 있다. 다이어그램에서 각 군집에 속한 포인트들의 실루엣 계수 값을 세로 막대 형태로 나열하며, 군집별 평균 계수의 차이와 함께 특정 군집 내에서 계수가 낮은 이상치 포인트를 식별하는 데 유용하다. 이 분석은 엘보우 방법이 주관적인 판단에 의존할 수 있는 점을 보완하며, 데이터의 실제 분포 구조에 기반한 객관적인 K 값 선정을 가능하게 한다[7].

K-메도이드는 K-평균 군집화 알고리즘의 대표적인 변형 중 하나이다. K-평균이 군집의 중심을 데이터 포인트들의 평균(mean)으로 정의하는 반면, K-메도이드는 실제 데이터셋에 존재하는 하나의 대표 객체(medoid)를 중심으로 선택한다. 이 차이로 인해 K-메도이드는 평균 계산이 어렵거나 의미 없는 범주형 데이터에 적용할 수 있으며, 평균에 비해 이상치(outlier)의 영향을 훨씬 덜 받는 강건한 특성을 가진다.

알고리즘의 핵심은 각 군집을 대표하는 메도이드를 찾는 것이다. 메도이드는 해당 군집 내의 모든 다른 점들까지의 거리 합이 최소가 되는 실제 데이터 포인트로 정의된다. 일반적인 K-메도이드 알고리즘인 PAM(Partitioning Around Medoids)은 다음과 같은 두 단계를 반복한다.

1. BUILD 단계: 초기 k개의 메도이드를 선택한다.

2. SWAP 단계: 현재 메도이드와 군집 내 다른 비메도이드 점을 교환해보며, 전체 비용(모든 점이 자신의 메도이드까지 가지는 거리의 총합)이 감소하는지 확인한다. 비용이 감소하면 교체를 수행한다.

이 과정은 더 이상의 교체가 전체 비용을 줄이지 못할 때까지 반복되어 최종 군집을 형성한다.

K-메도이드의 주요 장단점은 다음과 같이 정리할 수 있다.

이러한 특성으로 인해 K-메도이드는 생물정보학, 텍스트 마이닝, 이미지 분할 등 다양한 분야에서, 특히 데이터에 잡음이 많거나 거리 측정이 복잡한 경우에 유용하게 활용된다.

미니배치 K-평균(Mini-batch K-Means)은 대규모 데이터셋에 K-평균 군집화 알고리즘을 효율적으로 적용하기 위해 고안된 변형 알고리즘이다. 표준 K-평균 알고리즘은 매 반복마다 전체 데이터셋을 사용하여 중심점을 재계산하기 때문에 데이터 양이 많을수록 계산 비용이 크게 증가한다. 미니배치 K-평균은 이 문제를 해결하기 위해 확률적 경사 하강법의 아이디어를 차용하여, 매 반복마다 데이터의 무작위 하위 집합인 미니배치만을 사용하여 중심점을 업데이트한다.

알고리즘의 동작 방식은 다음과 같다. 먼저, 데이터셋에서 b개의 샘플로 구성된 미니배치를 무작위로 추출한다. 이 미니배치 내의 각 데이터 포인트를 가장 가까운 중심점에 할당한 후, 해당 중심점을 미니배치에 속한 데이터 포인트들의 평균으로 업데이트한다. 이때, 업데이트는 중심점의 이동 방향과 크기를 조절하는 학습률을 적용하여 점진적으로 수행된다. 이 과정을 미니배치를 바꿔가며 반복하여 중심점이 수렴할 때까지 진행한다.

이 방법은 계산 속도를 크게 향상시키며, 메모리 사용량도 줄일 수 있어 웹 스케일의 데이터 마이닝이나 온라인 학습 환경에 적합하다. 그러나 미니배치의 무작위성 때문에 알고리즘이 지역 최적해에 수렴할 가능성이 있으며, 최종 군집화 결과의 정확도가 표준 K-평균보다 약간 떨어질 수 있다는 단점이 있다.

K-평균 군집화의 성능은 입력 데이터의 특성에 크게 의존한다. 효과적인 군집화를 위해 데이터에 적절한 전처리를 적용하는 것이 필수적이다. 가장 중요한 전처리 단계는 특성 스케일링이다. K-평균 알고리즘은 중심점과 데이터 포인트 간의 유클리드 거리를 기반으로 하므로, 서로 다른 단위나 스케일을 가진 특성들이 존재할 경우 거리 계산에 큰 영향을 미친다. 예를 들어, '연봉'(백만 원 단위)과 '근속 연수'(년 단위)라는 두 특성을 사용할 때, 스케일링 없이는 연봉의 변동이 군집 형성을 지배하게 된다. 따라서 모든 특성이 동등한 중요도를 가지도록 표준화나 정규화를 수행하여 평균이 0이고 표준편차가 1이 되도록 조정하거나, 모든 값을 특정 범위(예: 0~1)로 변환하는 것이 일반적이다.

범주형 데이터를 처리할 때는 추가적인 변환이 필요하다. K-평균은 본질적으로 수치형 데이터에 대한 거리 계산을 전제로 하기 때문이다. 명목 척도 데이터(예: 직업, 도시)의 경우, 원-핫 인코딩을 통해 각 범주를 이진 특성으로 변환할 수 있다. 그러나 이렇게 생성된 많은 이진 특성은 군집화 결과에 과도한 영향을 미칠 수 있으므로 주의가 필요하다. 순서 척도 데이터는 적절한 수치 코드(예: 1, 2, 3)로 매핑하거나, 범주형 데이터와 유사한 인코딩 방식을 고려할 수 있다.

데이터의 차원과 분포도 중요한 고려 사항이다. 차원의 저주로 인해 고차원 데이터에서는 모든 점들 간의 거리가 비슷해져 군집화가 어려워질 수 있다. 이 경우 주성분 분석과 같은 차원 축소 기법을 적용하여 정보를 최대한 보존하면서도 의미 있는 저차원 공간으로 변환할 수 있다. 또한, 데이터에 이상치가 많이 포함되어 있으면 중심점의 위치가 크게 왜곡될 수 있다. K-평균은 이상치에 매우 민감한 알고리즘이다. 따라서 사전에 IQR 규칙이나 Z-점수 등을 이용한 이상치 탐지 및 제거 또는 조정 과정이 권장된다.

K-평균 군집화의 결과를 정량적으로 평가하기 위해 여러 지표가 사용된다. 이들 지표는 군집 내 응집도와 군집 간 분리도를 측정하여 군집화의 질을 평가하는 데 목적이 있다.

주요 내부 평가 지표로는 왜곡과 실루엣 계수가 있다. 왜곡은 각 데이터 포인트와 해당 군집 중심점 간 거리의 제곱합으로, 값이 작을수록 군집 내 응집도가 높음을 의미한다. 실루엣 계수는 개별 데이터 포인트가 자신이 속한 군집 내부에 얼마나 잘 응집되어 있고, 다른 군집과는 얼마나 잘 분리되어 있는지를 -1부터 1 사이의 값으로 나타낸다. 평균 실루엣 계수가 높을수록 전반적인 군집화 구조가 좋다고 해석한다. 이 외에도 데이비스-불딘 지수나 칼린스키-하라바츠 지수와 같은 복합 지표도 사용된다.

외부 평가 지표는 사전에 알려진 참조 클래스 레이블이 있을 때 사용된다. 대표적으로 정확도, 정밀도, 재현율과 같은 분류 지표를 적용하거나, 조정 랜드 지수나 조정 상호 정보량을 계산한다. 이 지표들은 군집 할당 결과와 실제 레이블 간의 일치 정도를 측정한다. 그러나 K-평균은 레이블 정보 없이 사용되는 경우가 대부분이므로, 내부 평가 지표가 더 보편적으로 활용된다. 모든 지표는 절대적인 기준보다는 서로 다른 K 값이나 초기화 방법을 비교하는 상대적 도구로 사용되는 경우가 많다.