11. 군집화 (Clustering)

군집화란, 유사한 속성을 갖는 데이터를 $n$개의 군집으로 나누는 것이다.

좋은 군집화는 동일한 군집에 소속된 데이터는 서로 유사하게(inter-class similarity), 상이한 군집에 소속된 데이터는 서로 다르게(intra-class dissimilarity) 군집화하는 것이다.

분류와 군집화

분류는 사전 정의된 범주가 있는 데이터로부터 예측 모델을 학습하는, 지도 학습 문제이다. 반면 군집화는 사전 정의된 범주가 없는 데이터로부터 최적의 그룹을 찾아가는 비지도 학습 문제이다.

군집화 수행 시 주요 고려사항

• 어떤 거리 측도를 사용하여 유사도를 측정할 것인가? (Similarity Metric 선정)
• 어떤 군집화 알고리즘을 사용할 것인가?
• 어떻게 최적의 군집 수(K)를 결정할 것인가?
• 어떻게 군집화 결과를 측정/평가할 것인가?

유사도 척도^{Similarity Metric}

데이터 간의 유사도를 측정하는 기준이다.

유클리드 거리^{Euclidean Distance}

일반적으로 사용하는 거리 척도인, $L_2$거리이다. 두 관측치 사이의 직선 거리를 의미한다.

$$ L_2(x, y) = \sqrt{\sum_{i=0}^n(x_i - y_i)^2}$$

맨하탄 거리^{Manhattan Distance}

두 관측치 사이의 각 행의 차를 그저 더한 값. $L_1$거리라고도 한다.

$$ L_1(x,y) = \sum_{i=0}^n(x_i - y_i)^2 $$

마할라노비스 거리^{Mahalanobis Distance}

변수 내의 분산, 공분산을 모두 반영하여 X, Y간의 거리를 계산하는 방식이다. 데이터의 공분산 행렬이 항등 행렬이라면 유클리드 거리와 같다.

$$D(x, y) = \sqrt{(x-y)\sum^{-1}(x-y)}$$
이때, $\sum^{-1}$은 공분산 행렬이다.

군집화 알고리즘

• 계층적 군집화
  • 개체들을 가까운 집단부터 차근차근 묶어 나가는 방식
  • 군집화 결과 뿐만 아니라 유사한 개체들이 결합되는 덴그로그램 생성
• 분리형 군집화
  • 전체 데이터 영역을 특정 기준에 의해 동시에 구분
  • 각 객체들은 사전 정의된 개수의 군집 중 하나에 속하게 됨
• 분포 기반 군집화
  • 데이터의 분포를 기반으로 높은 밀도를 갖는 세부 영역들로 전체 영역을 구분
  • 일부 객체가 특정 분포에 속하지 않는 노이즈 처리될 수 있음

계층적 군집화

계층적 트리 모델을 이용하여 개별 개체들을 순차적/계층적으로 유사한 개체끼리 통합한다. 덴드로그램을 통해 시각화 가능하다. (덴드로그램: 개체들이 결합되는 순서를 나타내는 트리 형태의 구조)
사전에 군집의 수를 정하지 않아도 수행 가능하다.

과정

1. 모든 데이터 사이의 거리에 대한 유사도 행렬을 계산한다.
2. 거리가 인접한 데이터끼리 군집 형성
3. 유사도 행렬 갱신
4. 1-3을 반복. 원하는 수준에서 중단

군집과 군집의 거리를 계산할 때, 군집 내 데이터 간의 거리를 모두 계산하여 가장 작은/큰 거리값을 선택하거나, 평균값을 선택할 수도 있다. 혹은 군집의 중심의 거리를 비교할 수도 있다. 혹은 ward 거리 계산법도 있다.

Ward 거리 계산법

서로 다른 군집에 해당하는 모든 데이터를 포함한 중심을 구하고, 구한 중심과 서로 다른 군집에 포함되는 모든 데이터 사이의 거리를 구한다.

각 군집에 해당하는 데이터를 통해 중심을 구하고, 구한 중심과 군집 내 데이터 사이의 거리를 구한다.

최종 결과가 클 수록 서로 다른 군집은 유사도가 낮아 멀리 있고, 최종 결과가 작을 수록 서로 다른 군집의 유사도는 높아 가까이 있다.

분리형 군집화

K-Means Clustering

• 각 군집은 하나의 중심^centroid을 갖는다.
• 각 객체는 가장 가까운 중심에 할당되며, 같은 중심에 할당된 개체들이 모여 하나의 군집을 형성한다.
• 사전에 군집의 수 $K$가 정해져야 알고리즘을 수행할 수 있다.
• 초기에 랜덤으로 설정하는 중심이 결과에 영향을 미칠 수 있다.

과정

1. 임의의 K개의 중심을 생성
2. 생성된 중심을 기준으로 모든 데이터에 군집 할당
3. 각 군집의 중심 다시 계산
4. 중심이 변하지 않을 때까지 2-3 반복

랜덤 초기화 극복하기

여러 번 Kmeans 군집화를 수행하여 가장 여러 번 나타나는 군집을 사용하는 앙상블 방법이 일반적이다. 혹은, 데이터 분포 정보를 활용하여 초기화를 선정하기도 한다. (예를들어, 정규분포 데이터라면 중심을 초기값으로 선정)

데이터가 많다면, 샘플링 데이터를 활용하여 계층적 군집화를 수행한 후 초기 군집 중심으로 사용하기도 한다.

하지만, 많은 경우 초기 중심이 최종 결과에 영향을 크게 미치지는 않는다.

K 평균 군집화의 단점

• 서로 다른 크기의 군집을 잘 찾아내지 못함
• 서로 다른 밀도의 군집을 잘 찾아내지 못함
• 지역적 패턴이 존재하는 군집을 판별하기 어려움

K값 선정 방법

다양한 군집 수에 대한 성능 평가 지표를 통해 최적의 군집 수를 선택한다.
내부 평가는 Dunn Index, Sum of Squared Error(SSE), 외부 평가는 Rand Index, Jaccard Coefficient 등을 지표로 활용한다.

$$SSE = \sum_{i=1}^K \sum_{x\in C_i} \text{dist}(x, c_i)^2 $$

Silhouette 통계량

군집 내의 거리는 최소화하고, 군집 간의 거리는 최대화한다.

$a(i)$: $i$번째 데이터와 같은 군집 내에 있는 모든 데이터 사이의 평균 거리 (낮은게 좋음)
$b(i)$: $i$번째 데이터와 다른 군집 내에 있는 모든 데이터 사이의 최소 거리 (높은게 좋음)

일반적으로 $S$값이 0.5보다 크면 군집 결과가 타당하다고 판단한다. (1에 가까울 수록 좋고 -1에 가까울 수록 안좋다.)

$$ S(i) = \frac{b(i)-a(i)}{\max (a(i), b(i))}\\
S = \frac{1}{n} \sum_{i=1}^n s(i) $$

분포 기반 군집화

DBSCAN (Density Based Clustering)

높은 밀도를 가지고 모여있는 데이터들을 그룹으로 분류한다. 낮은 밀도를 가진 데이터는 이상치 또는 잡음으로 분류한다.

데이터의 $\epsilon$-neighborhood가 M개 이상의 데이터를 포함하는지 고려하여 분류한다. ($\epsilon$과 M은 분포 기반 군집화의 파라메터)

$\epsilon$-neighborhood가 M개 이상의 데이터를 포함하는 데이터를 핵심 자료(Core Point)로 분류한다.
핵심 자료는 아니지만 $\epsilon$-neighborhood에 핵심 자료를 포함하는 데이터를 주변 자료로 분류한다.

이외에 데이터들을 잡음 자료로 본다.

과정

1. 임의의 데이터를 선택하고 군집 1 부여
2. 임의 데이터의 $\epsilon$-NN을 구하고 데이터의 수가 M보다 작으면 잡음자료 부여한다.
3. M보다 크면 $\epsilon$-NN 모두 군집1 부여, 군집 1 모든 데이터의 $\epsilon$-NN의 크기가 M보다 큰 것이 없을 때까지 반복한다.
4. 군집 2에 대해 동일하게 반복한다.

파라메터 설정

$\epsilon$: 너무 작으면 많은 데이터가 잡음으로 분류되고 너무 크면 군집의 개수가 적어진다.

M: 일반적으로 특성 변수 개수 + 1을 사용한다.