K-means 클러스터링
방대한 데이터에서 유의미한 패턴을 발견하기 어려운 경우, 특정 기준에 따라 데이터를 묶어내는 것만으로도 꽤 유용한 인사이트를 얻을 수 있다. 예를 들어, 온라인 쇼핑몰 고객을 구매 빈도나 구매 금액에 따라 세분화하면 각 그룹의 소비 성향을 보다 명확하게 분석할 수 있고, 시간대별 교통량 데이터를 활용하여 지역을 군집화하면 특정 시간대에 교통이 집중되는 구간을 식별할 수 있다. 이처럼 데이터 내 유사한 특성을 가진 개체들을 여러 그룹으로 분류하는 과정을 클러스터링(Clustering)이라고 한다. 그중에서도 가장 널리 사용되는 방법이 바로 K-means 클러스터링이다. K-means 알고리즘은 비교적 단순한 수학적 원리에 기반하여 계산 효율성이 높고, 다양한 도메인에서 안정적으로 작동하기 때문에 폭넓게 활용된다.
K-means 클러스터링
K-means 클러스터은 데이터를 K개의 클러스터로 나누는 비지도 학습 알고리즘이다. 개별 데이터들을 사전에 설정된 개수(K)에 맞게 파티셔닝하며, 이때 분할은 클러스터 중심(centroid)과의 거리 차이를 최소화하는 방식으로 이루어진다. 다시 말해, 각 데이터 포인트를 가장 가까운 클러스터에 할당함으로써 클러스터 내의 데이터 포인트들이 클러스터 중심과 가능한 최소한의 거리를 가지도록 하는 것이다. 그러므로 k-means는 데이터 포인트가 하나의 클러스터에만 존재할 수 있도록 규정하는 하드 클러스터링(Hard Clustering) 방법이다.
표준 알고리즘은 다음과 같다.
- 임의로 K개의 클러스터 중심(centroid)을 선택한다.
- 데이터 포인트로부터 각 클러스터 중심까지의 거리*를 계산하고, 가장 가까운 클러스터에 할당한다. *유클리드 거리(Euclidean distance) 기준
- 각 클러스터에 속한 데이터 포인트들의 평균 위치를 계산하여 새로운 클러스터 중심을 업데이트한다.
- 클러스터 중심이 더 이상 변화하지 않거나, 지정된 최대 반복 횟수에 도달할 때까지 2-3단계를 반복한다.
아래와 같이 iteration을 돌며 최적의 분할을 찾아간다.
수식으로 이해하기
k번째 클러스터의 중심을 $\mu_{k}$, 해당 클러스터에 속하는 점의 집합을 $C_{k}$라고 할 때, 클러스터 내 제곱합(WCSS), 즉 분산은 아래와 같이 표현할 수 있다.
$$W(C_k) = \sum_{i \in C_k} || x_{i} - \mu_{k} ||^2$$
그리고 K-means 알고리즘은 K개 군집의 총 분산을 최소화하는 문제와 동일하다.
$$\text{minimize}\sum_{k=1}^{K}W(C_{k})$$
장단점
장점 :
- 거리 기반 알고리즘이기 때문에 직관적이고 구현이 쉬움
- 계산량이 적어 큰 데이터셋에서도 빠른 속도를 보장
단점 :
- 초기값 선택에 민감 *Local Optimum 문제
- 비구형(non-spherical) 클러스터에 대해서는 성능이 떨어짐
- 이상치(outliers)에 민감
※ 고차원 데이터에서는 성능이 저하되므로 차원축소가 필수적이다. 이러한 점에서 유클리드 거리 대신 코사인 거리를 활용하기도 하는데, 이를 Spherical K-means라고 한다.
최적의 K 선택
K-means 알고리즘의 경우, K값을 사전에 지정해야 하므로 적절한 K를 선택하는 것이 중요하다.
- Elbow Method
군집 수(K)가 증가함에 따라 클러스터 내 잔차제곱합 (Within-cluster sum of squares, WCSS)이 감소하는 양상을 살펴보고, 감소폭이 급격히 줄어드는 지점을 최적의 K 값으로 판단한다.
- Silhouette
실루엣 점수(Silhouette score)는 각 데이터 포인트에 대해 계산되며, 이 값은 -1에서 1까지의 범위를 가진다. 값이 1에 가까우면 해당 데이터 포인트가 잘 군집화됨을 의미하고, 0에 가까우면 군집 경계에 위치한 데이터, -1에 가까우면 잘못 군집화된 데이터로 간주된다.
- Gap Statistics
실제 데이터와 무작위로 생성된 데이터에 대한 클러스터링 결과를 비교하여 최적의 K를 결정하는 방법. K 값에 대한 갭 통계가 최대가 되는 지점을 최적의 K로 선택한다. 무작위 데이터와의 비교를 통해 군집화의 품질을 평가하므로 더 신뢰성 있는 최적 K 값을 찾을 수 있다.
Reference
Gared James et al., An Introduction to Statistical Learning with Applications in R