이번엔 비지도학습의 또 다른 예인 DBSCAN 클러스터링에 대해 알아본다.
■ 밀도 기반의 DBSCAN 클러스터링
DBSCAN의 경우 ‘밀도’ 기반으로 군집을 할당한다. 여기서 밀도 기반이란, 어떤 데이터 포인트에서의 x 반지름 내에 n개 이상의 포인트를 갖는 것을 하나의 군집으로 구분하는 것인데, 이 말인즉슨 K-Means와는 달리 군집의 개수 k를 미리 정의해놓을 필요는 없지만 반지름 x(Eps)과 한 군집 내에 최소 n개 포인트(Min Pts.)가 있어야 함으로 이 두개를 사전에 정의해야 한다.
DBSCAN 상에는 3개의 클래스가 나타날 수 있다. 바로 core point, border point, noise point이다. 그림으로 좀 더 살펴보자.
반지름이 2이고, 최소 6개의 포인트를 가질 때 1개의 군집으로 할당하고자 한다. 이 때 빨간 점은 해당 조건을 만족하여 코어포인트가 된다. 보더 포인트란 코어 포인트의 반지름 내에 걸쳐서 ‘이웃’하고 있으나 최소 포인트 개수를 충족시키지 못하는 경우(초록색)를 말하며, 노이즈 포인트는 코어포인트도 아니고 보더 포인트도 아닌 포인트를 말한다. 노이즈 포인트는 다른말로 “other”이나 “miscellaneous”라고 부르기도 한다.
위 그림은 하나의 예시이며, 모든 데이터 포인트에서 해당 점이 코어 포인트가 되는지 확인해가면서 군집을 할당하는 것이 DBSCAN 알고리즘의 핵심이다. 이를 정리하면 다음과 같다.
current_cluster_label <- 1
for all core points do
if the core point has no cluster label then
current_cluster_label <- current_cluster_label+1
Label the current core point with cluster label current_cluster_label
end if
for all points in the Eps-neighborhood, except i-th point itself do
if the point does not have a cluster label then
Label the point with cluster label current_cluster_label
end if
end for
end for
K-Means와 달리 어느 군집에도 속하지 않는 노이즈 포인트는 제외하며 남아있는 포인트를 중심으로 군집을 할당하는 것이 특징이다. 노이즈 포인트를 버리기 때문에 노이즈에 취약하지 않으며, 군집의 모양과 사이즈가 다양하게 나올 수 있다.(K-Means의 군집은 원형이다).
■ DBSCAN에서 최적의 반지름(Eps)과 최소 군집 개수(MinPts) 찾는 법
이제 최적의 반지름과 최소 군집 개수를 찾아보자. 이상적인 케이스를 생각하면, 하나의 군집 안에 있는 데이터 포인트의 거리는 가깝고, 노이즈 포인트와의 거리는 꽤 멀게 떨어져 있을 것이다.
이 아이디어에서 출발해서 어떤 군집 안에 있는 데이터 포인트들과 ‘k번째 인접한 이웃 데이터 포인트까지의 거리’를 계산해보며 반지름을 찾아나간다. 즉, 그 거리가 급격하게 늘어날 때까지의 점을 찾는다.
여기서 k는 최소 군집 개수이며, k번째 인접한 이웃 데이터 포인트까지의 거리는 반지름이 된다. 위 그림에서 최소 군집 개수는 4개고, 반지름은 파란 선의 기울기가 가파르게 증가하는 지점인 10이다.
■ DBSCAN의 단점 = 다른 밀도 분포 데이터와 차원의 저주!
DBSCAN의 단점은 다른 밀도 분포를 가진 데이터의 군집 분석을 잘 하지 못한다는 것이다. 오른쪽 DBSCAN 결과를 보면, 밀도가 높은 곳에 집중하다 보니 왼쪽에 밀도가 낮은 곳의 데이터를 하나의 군집으로 인식하지 못하고 노이즈 포인트로 구분해서 모두 버려버리는 결과를 낳았다.
또한, 모든 유클리디안 거리를 계산하는 알고리즘이 갖는 ‘차원의 저주’를 벗어나지 못한다. 차원의 저주는 고차원이 될 수록 각 데이터 포인트 사이의 거리가 늘어나 결국에는 매우 희소해지는 것을말하는데 상세 설명은 다음 사이트에서 살펴보면 이해가 쉽다.