Dasein's ‎Archive

3. 계층적 클러스터링

* 계층적 클러스터링(hierarchical clustering)

- K 평균 대신 사용하는 클러스터링 방법으로 K 평균과는 아주 다른 결과를 보여준다.

- K 평균보다 유연하고, 수치형 변수가 아니라도 쉽게 적용이 가능하다.

- 특잇점이나 비정상적인 그룹이나 레코드를 발견하는 데 민감한다. 또한, 직관적인 시각화가 가능하여 클러스터를 해석하기가 수월하다

※ 계층적 클러스터링의 유연성에는 비용이 따른다.

→ 수백만 개의 레코드가 있는 대규모 데이터에는 적용할 수 없다. 따라서 계층적 클러스터링은 대부분 상대적으로 데이터 크기가 작은 문제에 주로 적용된다.

1) 간단한 예제

  $n$개의 레코드와 $p$개의 변수가 있는 일반적인 데이터에 대해 적용한 계층적 클러스터링은 아래 두 가지 기본 구성 요소를 기반으로 한다.

• 두 개의 레코드 $i$와 $j$ 사이의 거리를 측정하기 위한 거리 측정 지표 $d_{i,j}$
• 두 개의 클러스터 $A$와 $B$ 사이의 차이를 측정하기 위한, 각 클러스터 구성원 간의 거리 $d_{i,j}$를 기반으로 한 비유사도 측정지표 $D_{A,B}$

- 계층적 클러스터링은 각 레코드 자체를 개별 클러스터로 설정하여 시작하고 가장 가까운 클러스터를 결합해나가는 작업을 반복한다.

- R에서는 hclust 함수를 사용하여 계층적 클러스터링을 수행할 수 있다.

2)  덴드로그램

- 계층적 클러스터링은 트리 모델과 같이 자연스러운 시각적 표현이 가능하며, 이를 덴드로그램 이라고 한다.

- R에서는 plot 명령을 사용하여 이를 생성할 수 있다.

- 트리의 잎은 각 레코드들을 의미하며, 트리의 가지 길이는 해당 클러스터 간의 차이 정도를 나타낸다.

- K 평균과 달리 클러스터의 수를 미리 지정할 필요는 없다. cutree 함수를 사용하면 원하는 개수의 클러스터를 추출할 수 있다.

3) 병합 알고리즘

- 계층적 클러스터링에서 가장 중요한 알고리즘은 병합(agglomerative) 알고리즘이다.

- 병합 알고리즘은 단일 레코드로 구성된 클러스터에서 시작하여 점점 더 큰 클러스터를 만든다.

< 알고리즘 >

1. 데이터의 모든 레코드에 대해, 단일 레코드로만 구성된 클러스터들로 초기 클러스터 집합을 만든다.
2. 모든 쌍의 클러스터 $k,l$ 사이의 비유사도 $D(C_k, C_l)$을 계산한다.
3. $D(C_k, C_l)$에 따라 가장 가까운 두 클러스터 $C_k$와 $C_l$을 병합한다.
4. 둘 이상의 클러스터가 남아 있으면 2단계로 다시 돌아간다. 그렇지 않고 클러스터가 하나 남는다면 알고리즘을 멈춘다.

4) 비유사도 측정

- 각 레코드 쌍 $(x_1, x_2, \cdot\cdot\cdot, x_p)$와 $(y_1, y_2, \cdot\cdot\cdot, y_p)$에 대해 거리지표를 사용하여 두 레코드 사이의 거리 $d_{x,y}$를 측정한다. 예를 들어 아래의 유클리드 거리를 사용할 수 있다.

$d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdot\cdot\cdot+(x_p-y_p)^2}$

* 완전연결(complete linkage) 방식

- A와 B 사이의 모든 레코드 쌍의 최대 거리를 사용한다.

$D(A,B) = max d(a_i, b_j)$ 모든 $i,j$ 쌍에 대해

* 단일연결(single linkage) 방식

- 두 클러스터의 레코드 간 최소 거리를 사용한다.

$D(A,B) = min d(a_i, b_j)$ 모든 $i,j$ 쌍에 대해

* 평균연결(average linkage) 방식

- 모든 거리 쌍의 평균을 사용하는 방법으로 이는 단일 연결과 완전연결 방법 사이를 절충한 방법이다.

* 최소분산(minimum varuance) 방식 = 워드 기법(Ward's method)

- 클러스터 내의 제곱합을 최소화하므로 K 평균과 유사하다고 할 수 있다.

· 모든 레코드를 각각 자체 클러스터로 할당하여 알고리즘을 시작한다.
· 클러스터들은 모든 레코드가 하나의 클러스터에 속할 때까지 가까운 클러스터와 계속해서 연결된다(병합 알고리즘).
· 병합 과정은 내역이 남고 시각화할 수 있으며, 사용자가 미리 클러스터 수를 지정하지 않더라도 여러 단계에서 클러스터의 수와 구조를 시각화할 수 있다.
· 클러스터 간 거리는 모든 레코드 간 거리 정보를 사용하여 여러 가지 다른 방식으로 계산할 수 있다.

4. 모델 기반 클러스터링

- 계층적 클러스터링과 K 평균 같은 클러스터링 방법들은 모두 휴리스틱한 방법이다.

1) 다변량정규분포

- 다변량정규분포(multivariate normal distribution)는 $p$개의 변수집합 $X_1, X_2, \cdot\cdot\cdot, X_p$에 대해 정규분포를 일반화한 것이다.

- 분포는 평균 집합 $\mu=\mu_1,\mu_2,\cdot\cdot\cdot,\mu_p$과 공분산행렬 $\sum\로 정의된다.

- 공분산행렬 $\sum$는 $p$개의 분산 $\sigma_1^2,\sigma_2^2,\cdot\cdot\cdot,\sigma_p^2$과 $i\neq j$인 모든 변수 쌍에 대한 공분산$\sigma_{i,j}$로 구성된다.

$(X_1, X_2, \cdot\cdot\cdot, X_p)\tilde{N_p}(\mu,\sum)$

이 기호는 변수들이 모두 정규분포를 따른다는 뜻이며, 전체 분포가 변수의 평균 벡터와 공분산행렬에 의해 완벽히 설명된다는 것을 나타낸다.

2) 정규혼합

- 모델 기반 클러스터링의 핵심 아이디어는 각 레코드가 K개의 다변량정규분포 중 하나로부터 발생했다고 가정하는 것이다.

- R에서는 모델 기반 클러스터링을 위해 mclust라는 패키지를 제공한다.

- 모델 기반 클러스터링의 목적은 사실 데이터를 가장 잘 설명하는 다변량정규분포를 찾는 것이다.

3) 클러스터 개수 설정하기

- mclust는 베이즈 정보기준(BIC; Bayesian information criteria) 값이 가장 큰 클러스터의 개수를 선택하도록 동작하기 때문에 클러스터 수를 자동으로 선택한다.

< 모델 기반 클러스터링 기술의 한계 >

- 기본적으로 데이터들이 모델을 따른다는 가정이 필요하다.

- 필요한 계산량 역시 계층적 클러스터링보다 높다.

- 다른 방법들보다 알고리즘이 더 복잡하고 이용하기가 어렵다.

· 클러스터들이 각자 서로 다른 확률분포로부터 발생한 것으로 가정한다.
· 분포(일반적으로 정규분포) 개수에 대한 가정에 따라 서로 다른 적합한 모델이 있다.
· 이 방법은 너무 많은 파라미터(오버피팅의 원인이 될 수 있다)를 사용하지 않으면서도 데이터에 대한 적합한 모델(그리고 연관된 클러스터 개수)을 선택한다.

5. 스케일링과 범주형 변수

- 비지도 학습 기술을 이용할 때는 일반적으로 데이터를 적절하게 스케일해야 한다.

- 범주형 데이터는 일부 클러스터링 과정에서 특별한 문제를 일으킬 수 있으므로, 순서가 없는 요인변수는 일반적으로 원-핫 인코딩을 사용하여 이진(0/1) 변수 집합으로 변환한다.

1) 변수 스케일링

- 매우 다른 스케일 및 단위를 갖는 변수는 클러스터링 절차를 적용하기 전에 적절히 정규화해야 한다.

- 표준화 또는 정규화는 변수를 스케일링하는 일반적인 방법이다.

$z=\frac{x-\bar{x}}{s}$

2) 지배 변수

- 변수들이 서로 동일한 규모로 측정되고 상대적 중요성을 정확하게 반영하는 경우조차도 변수의 스케일을 재조정하는 것이 유용할 수 있다.

- 특정 주성분에 의해 지배되고 있는 경우에는 변수를 스케일링해서 포함하거나, 특정 지배 변수를 전체 분석에서 제외하고 별도로 처리할 수도 있다.

→ 어떤 방법이 항상 옳다고는 할 수 없으며 응용 분야에 따라 달라진다.

3) 범주형 데이터와 고워 거리

- 범주형 데이터가 있는 경우에는 순서형(정렬된 요인) 변수 또는 이진형(더미) 변수를 사용하여 수치형 데이터로 변환해야 한다.

- 데이터를 구성하는 변수들에 연속형과 이진형 변수가 섞여 있는 경우에는 비슷한 스케일이 되도록 변수의 크기를 조정해야 한다.

→ 이를 위한 대표적인 방법은 고워 거리를 사용하는 것이다.

고워 거리의 기본 아이디어는 각 변수의 데이터 유형에 따라 거리 지표를 다르게 적용하는 것이다.

• 수치형 변수나 순서형 요소에서 두 레코드 간의 거리는 차이의 절댓값(맨하탄 거리)으로 계산한다.
• 범주형 변수의 경우 두 레코드 사이의 범주가 서로 다르면 거리가 1이고 범주가 동일하면 거리는 0이다.

< 고워 거리의 계산 >

1. 각 레코드의 변수 $i$와 $j$의 모든 쌍에 대해 거리 $d_{i,j}$를 계산한다.
2. 각 $d_{i,j}$의 크기를 최솟값잉 0이고 최댓값이 1이 되도록 스케일을 조정한다.
3. 거리 행렬을 구하기 위해 변수 간에 스케일된 거리를 모두 더한 후 평균 혹은 가중평균을 계산한다.

- cluster 패키지의 daisy 함수를 사용하면 고워 거리를 계산할 수 있다.

4) 혼합 데이터의 클러스터링 문제

- K 평균과 PCA는 연속형 변수에 가장 적합하다.

- 데이터 집합의 크기가 더 작아질수록 고워 거리를 사용하여 계층적 클러스터링을 하는 것이 좋다.

- 실무에서는 K 평균과 PCA를 이진형 데이터와 함께 사용하는 것은 어려울 수 있다.

· 스케일이 서로 다른 변수들을 스케일이 비슷하도록 변환하여, 스케일이 알고리즘에 큰 영향을 미치지 않도록 한다.
· 일반적인 스케일링 방법은 각 변수에서 평균을 빼고 표준편차로 나눠주는 정규화(표준화) 방법이다.
· 또 다른 방법은 고워거리를 사용하는 것이다. 이 방법은 모든 변수를 0~1  범위로 스케일링한다(수치형과 범주형 데이터가 서로 혼합된 경우에 많이 사용된다).

- 주성분분석과 K 평균 클러스터링은 수치형 데이터의 차원을 축소하기 위해 주로 사용되는 방법이다.

- K 평균은 매우 큰 데이터로 확장이 가능하고 이해하기 쉽다.

- 계층적 클러스터링은 수치형과 범주형이 혼합된 데이터 유형에 적용이 가능하며 직관적인 시각화 방법(댄드로그램)이 존재한다.

- 모델 기반 클러스터링은 휴리스틱한 방법들과 달리 통계 이론에 기초를 두고 있으며 더 엄밀한 접근 방식을 제시한다.

→ 그러나 데이터가 커지면 K 평균이 가장 많이 사용되는 방법이다.

< 참고자료 >
1. Peter Brucs & Andrwe Brucs(2018). 데이터 과학을 위한 통계. 한빛미디어. 이용준 옮김