클러스터링 #2 - Hierarchical clustering (계층 분석)

Hierarchical clustering을 이용한 데이타 군집화

조대협 (http://bcho.tistory.com)

Hierarchical clustering (한글 : 계층적 군집 분석) 은 비슷한 군집끼리 묶어 가면서 최종 적으로는 하나의 케이스가 될때까지 군집을 묶는 클러스터링 알고리즘이다.

군집간의 거리를 기반으로 클러스터링을 하는 알고리즘이며, K Means와는 다르게 군집의 수를 미리 정해주지 않아도 된다. 참고로 이 글에서 사용된 예제 코드는 https://github.com/bwcho75/dataanalyticsandML/blob/master/Clustering/3.%20Hierarchical%20clustering-IRIS%204%20feature.ipynb 에 저장되어 있다.

예를 들어서 설명해보자

“진돗개,세퍼드,요크셔테리어,푸들, 물소, 젖소" 를 계층적 군집 분석을 하게 되면

첫번째는 중형견, 소형견, 소와 같은 군집으로 3개의 군집으로 묶일 수 있다.

이를 한번 더 군집화 하게 되면 [진돗개,셰퍼드] 와 [요크셔테리어,푸들] 군집은 하나의 군집(개)로 묶일 수 있다.

마지막으로 한번 더 군집화를 하게 되면 전체가 한군집(동물)으로 묶이게 된다.

이렇게 단계별로 계층을 따라가면서 군집을 하는 것을 계층적 군집 분석이라고 한다.

계층적 군집 분석은 Dendrogram이라는 그래프를 이용하면 손쉽게 시각화 할 수 있다.

계층형 군집화에 대한 좀 더 상세한 개념은 https://www.slideshare.net/pierluca.lanzi/dmtm-lecture-12-hierarchical-clustering?qid=94d8b25a-8cfa-421c-9ed5-03c0b33c29fb&v=&b=&from_search=1 를 보면 잘 나와 있다.

skLearn을 이용한 계층 분석 모델 구현

개념을 잡았으면 실제로 계층 분석 모델을 구현해보자.

데이타는 K Means에서 사용했던 IRIS 데이타를 똑같이 사용한다.

이번에는 4개의 피쳐를 이용해서 사용한다.

from sklearn import datasets
import pandas as pd
iris = datasets.load_iris()

labels = pd.DataFrame(iris.target)
labels.columns=['labels']
data = pd.DataFrame(iris.data)
data.columns=['Sepal length','Sepal width','Petal length','Petal width']
data = pd.concat([data,labels],axis=1)

다음은 IRIS 데이타를 이용하여 dendrogram을 그려보자

# Perform the necessary imports
from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

# Calculate the linkage: mergings
mergings = linkage(data,method='complete')

# Plot the dendrogram, using varieties as labels
plt.figure(figsize=(40,20))
dendrogram(mergings,
          labels = labels.as_matrix(columns=['labels']),
          leaf_rotation=90,
          leaf_font_size=20,
)
plt.show()

먼저 linkage 함수를 import 한 다음 linkage 함수에 data를 넘겨주면 Hierarchical clustering을 수행한다. 이때 method=’complete’로 정했는데, 이 부분은 뒤에서 설명한다.

Hierarchical clustering 한 결과를 dendrogram 함수를 이용하여 dendrogram 그래프를 표현해 보면 다음과 같이 출력된다.

계층 분석 방식

앞의 코드에서, linkage 함수에서 method 를 사용했다. 이에 대해서 알아보자.

Hierachical clustering의 기본 원리는 두 클러스터 사이의 거리를 측정해서 거리가 가까운 클러스터끼리 묶는 방식이다.  그러면 두 클러스터의 거리를 측정할때 어디를 기준점으로 할것인가를 결정해야 하는데 다음 그림을 보자.

출처 : https://www.multid.se/genex/onlinehelp/hs515.htm

앞의 코드에서 사용한 complete linkage 방식은 두 클러스터상에서 가장 먼 거리를 이용해서 측정하는 방식이고 반대로  single linkage 방식은 두 클러스터에서 가장 가까운 거리를 사용하는 방식이다.

average linkage 방식은 각 클러스터내의 각 점에서 다른 클러스터내의 모든 점사이의 거리에 대한 평균을 사용하는 방식이다.

이 linkage 방식에 따라서 군집이 되는 모양이 다르기 때문에, 데이타의 분포에 따라서 적절한 linkage  방식을 변화 시켜가면서 적용해가는 것이 좋다.

계층 분석을 통한 군집의 결정

계층 분석은 최종적으로 1개의 군집으로 모든 데이타를 클러스터링 하는데, 그렇다면 n개의 군집으로 나누려면 어떻게 해야 하는가?

아래 dendrogram을 보자 y축이 각 클러스터간의 거리를 나타내는데, 위로 올라갈 수 록 클러스터가 병합되는 것을 볼 수 있다.

즉 적정 y 값에서 클러스터링을 멈추면 n개의 군집 까지만 클러스터링이 되는데, 위의 그림은 y 값을 3에서 클러스터링을 멈춰서 총 3개의 클러스터로 구분을 한 결과이다.

이렇게 계층형 분석에서 sklearn을 사용할 경우 fcluster 함수를 이용하면, 특정 y값에서 클러스터링을 멈출 수 있다. 다음 코드를 보자.

from scipy.cluster.hierarchy import fcluster

predict = pd.DataFrame(fcluster(mergings,3,criterion='distance'))
predict.columns=['predict']
ct = pd.crosstab(predict['predict'],labels['labels'])
print(ct)

앞의 코드에서 계층형 클러스터링을 한 mergings 변수를 fcluster 함수에 전달하고 두번째 인자에 y의 임계값을 3으로 지정하였다. Predict 컬럼에는 원본 입력데이타에 대한 예측 결과 (어느 클러스터에 속해있는지를 0,1,2로 입력 데이타의 수만큼 리턴한다.)를 리턴한다.

이를 원본 데이타의 라벨인 labels[‘label’]값과 Cross tabulation 분석을 해보았다.

세로축이 예측 결과, 가로측이 원래 값이다.

원래 label이 0인 데이타와 1인 데이타는 각각 잘 분류가 되었고, 2인 데이타는 34개만 정확하게 분류가 되었고 16개는 원본 레이블이 1인 데이타로 분류가 되었다.

지금까지 Hierachical clustering model에 대해서 알아보았다. K Means와 같은 군집화 모델이라도 내부 알고리즘에 따라서 군집화 결과가 다르기 때문에, 샘플 데이타의 분포를 보고 적절한 클러스터링 모델을 고르는 것이 필요하다. 다행이 sklearn의 경우 복잡한 수식 이해 없이도 간단한 라이브러리 형태로 다양한 클러스터링 모델 사용할 수 있도록 해놨기 때문에, 여러 모델을 적용해가면서 적정한 데이타 분류 방식을 찾아보는 것이 어떨까 한다.