[연구일지] K-means VS HDBSCAN

대량의 텍스트 데이터를 클러스터링하는 연구를 하고 있다.

기존에는 K-means로, 가지고 있는 컴퓨팅 자원이 많지 않아 가장 가벼운 알고리즘을 사용하다가 HDBSCAN을 접하고 괜찮다고 생각하여 비교하는 글을 작성한다.

HDBSCAN 결과 예시, 출처: Top2Vec

 

1. 정의

K-means:

https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

k-평균 알고리즘 - 위키백과, 우리 모두의 백과사전

K-means는 클러스터 갯수를 k개로 하여 데이터를 분할했을 때, 가장 응집도가 높은 방향으로 클러스터링을 수행한다.

위 식은 k개의 클러스터로 나누었을 때, 클러스터링된 데이터의 중심과, 클러스터 내 데이터의 위치차의 제곱이 최소화(argmin)하는 알고리즘을 의미한다.

 

HDBSCAN(Hierarchical Density-Based Spatial Clustering of Applications with Noise):

https://github.com/scikit-learn-contrib/hdbscan

GitHub - scikit-learn-contrib/hdbscan: A high performance implementation of HDBSCAN clustering.

밀도 기반으로 클러스터링하는 DBSCAN에서 한 발짝 더 나아간, Hierarchical+DBSCAN인데,

DBSCAN과 독립적으로 설명하자면,

MST(Minumum Spanning Tree)를 그리고, 간선인 edge를 오름차순으로 하여 node끼리 클러스터를, 그리고 그 클러스터끼리 더 큰 클러스터를...

이러한 방식으로 hierarchical하게 그래프를 그린 후, 상위 클러스터에서 분할해가면서 최소 클러스터 크기 기준 (ex. 5)에 도달하지 못하면 noise로 처리하는 것이다.

 

2. 장단점

K-means:

장점:

• 계산 속도가 매우 빠르다. 하지만, HDBSCAN도 대부분의 경우에 K-means 급의 속도를 가지고 있으며, 데이터 수가 매우 커질 때, 상대적으로 약간 느려지는 수준이다.

단점:

• flat clustering을 의도하지 않는다. 즉, 겹치는 clusters들이 발생할 수 있다.
• cluster의 갯수인 k를 클러스터링 전에 설정하여야 한다. cluster의 label이 되는 topic 갯수가 정해지지 않은 경우 비효율적일 수 있다. 현재 연구적인 관점에서도 클러스터링 진행마다 k의 갯수가 달라야할 수 있는데 이를 hyper parameter로 일일히 테스트하면서 정하는 것은 scalable하지 않아 불가능하다고 할 수 있다. 
• 클러스터가 convex 형태일 때만, reasonable하게 작동한다.

make blobs로 생성한 가짜 데이터로 테스트한 클러스터 알고리즘 속도 비교, https://nbviewer.org/github/scikit-learn-contrib/hdbscan/blob/master/notebooks/How%20HDBSCAN%20Works.ipynb

HDBSCAN:

장점:

• 클러스터 수를 미리 지정할 필요가 없다.
• K-means보다 더 복잡한 형태의 데이터를 더 잘 클러스터링한다.
• noise 데이터를 구분한다.

단점:

• 데이터가 매우 많아지면 다소 연산 시간이 더 걸린다.

3. 결론

데이터 양이 매우 많아지면 그에 따라 다소 연산 시간이 길어질 수 있다는 점을 제하면,

1. noise 제외: 데이터에 noise가 있다는 것을 확인하긴 했다.
2. k 지정 미필요: k가 유동적으로 바뀌는 것이 필요했어서 오히려 좋다.
3. 합리적인 과정: 각각의 클러스터링 원리를 살펴보았을 때, HDBSCAN 쪽이 조금 더 합리적으로 느껴졌다.

HDBSCAN 써보자