연구 도중 그래프로만 표현되는 데이터를 클러스터링해야 하는 경우가 생겨 계층적 클러스터를 사용했다.
파이썬의 Scipy 모듈에 이러한 함수가 있는 모양이다.
다룰 것은 다음의 세 가지이다.
- distance matrix를 이용한 계층 클러스터링
- 위의 결과로부터 클러스터 정보 추출
- 클러스터 결과 시각화
Hierarchical Clustering with SciPy
굳이 계층적 군집화가 무엇인지 설명하지는 않겠다.
계층적 군집화는 연결 기반의 군집화 기법이기 때문에 distance matrix로부터 군집화를 할 때 매우 유용하다.
사용법은 간단하다.
from scipy.cluster.hierarchy import linkage linkage(distance_matrix, 'single')
scipy 모듈에서는 linkage라는 함수를 통해 계층적 군집화를 구현하였다.
doc에 의하면 linkage 함수는 노드간의 distance matrix를 인자로 받을 수 있다.
이 때 distance matrix는 Condensed Matrix여야 한다.
Condensed Matrix는 우상방의 삼각행렬 중 대각성분을 모두 제거한 행렬로
그 결과는 (노드 수)*(노드 수 – 1)/2 길이의 1차원 행렬로서 표현된다.
예를 들어 아래의 Redundant Matrix는 [1, 2, 3]의 Condensed Matrix와 동치이다.
linkage 함수는 결과를 dendrogram 형태로 반환하기 때문에, 결과값으로부터 클러스터 정보를 직관적으로 파악하기는 어렵다.
뭐 자세한건 docs를 참조하면 된다.
Cluster Extraction from Linkage Result
docs를 보면 알겠지만 구조가 꽤나 골때린다.
클러스터를 직접 구하라면 구할 순 있겠는데 귀찮다.
당연히 있겠지하고 찾아봤더니 역시 cut_tree 함수가 있었다. docs
cut_tree 함수는 linkage로부터 클러스터 정보를 반환해주는 함수이다.
정확히는 dendrogram으로부터 특정 레벨에서 가지치기를 하여 클러스터를 구별한다.
이름 그대로이다.
사용법은 간단하다.
from scipy.cluster.hierarchy import cut_tree num_of_cluster = 5 cluster_info = cut_tree(linkage_result, num_of_cluster)
이걸로 간단히 linkage로부터 클러스터 정보를 추출할 수 있다.
다만 아쉬운건 linkage 함수는 기본적으로 label을 지원하지 않기 때문에
cut_tree의 결과 또한 label이 없다.
애초에 distance matrix 자체에 label이 없기 때문에 당연한 일이다.
그러니 노드의 label을 별도로 들고있다가, cut_tree의 결과와 묶어 사용해야 한다.
순서는 distance matrix에서의 노드 순서와 동일하다.
Cluster Visualization
시각화는 dendrogram을 이용한다. docs
dendrogram은 matplotlib.pyplot을 이용하여 자동으로 plot된다.
from scipy.cluster.hierarchy import dendrogram dendrogram(result, leaf_rotation=90., truncate_mode='lastp', p=10) plt.show()
노드의 수가 많아지면 plot이 지저분해지므로, 최대 표시 클러스터를 10개로 설정했다.
이 경우 다음 그림과 같이 단일 클러스터는 숫자로, 중첩 클러스터는 괄호와 노드 개수로 표현된다.
나머지들은 단일 노드 클러스터이다.
크게 녹색 클러스터와 빨간색 클러스터로 나뉜다.
dendrogram 관련해서는 이 블로그가 도움이 참 많이 됐다.
Discussion
뭐 이것저것 했는데, 사실 Unsupervised Clustering은 개념상 무척 오래걸릴 수밖에 없다.
노드 수가 천개가 넘거나 하면 클러스터링에 많은 시간을 들여야 한다.
애초에 클러스터링은 np-hard이다..
linkage 함수도 docs에서 보면 O(n^3)라고 명시돼있다.
어차피 클러스터링이란게 하나의 방법으로 한번만 하는 것도 아니기 때문에
여러 방법을들 준비해서 병렬수행하는 것을 추천한다.
예를 들어 단일 작업은 아래의 세 단계로 나눌 수 있다.
- Distance Matrix 작성
- Clustering (by linkage function)
- Analysis (with linkage result) – cut_tree & dendrogram
그 후 위의 세 단계에 대해 case별로 병렬화하여 작업하면 된다.
그런데 사실 Distance Matrix 계산이 시간을 더 잡아먹는다..
예를 들어 시계열데이터의 경우 데이터의 길이를 정규화하지 않는다면
Dynamic Time Warp (DTW)같은 방법으로 Distance를 계산해야 하는데
DTW는 O(n^2)이다.
그리고 Distance Matrix 계산은 O(n^2)이다.
결과적으로 O((노드수)^2 * (노드A길이) * (노드B길이))가 되는데
대충 O(n^4)이다.
서버(HP DL380 Gen10)로
약 300 observation정도의 서로 다른 길이를 가진 410개 시계열데이터에 대해
1코어만 가지고 Distance Matrix를 계산하는데 약 4시간이 걸린다.
노드 수가 천개가 넘어가면 행렬 연산에도 반드시 병렬화를 시켜줘야 한다.