본문 바로가기

ML & DM/Clustering

DBSCAN(Density-based spatial clustering of applications with noise) Algorithm

DBSCAN에 대한 이 글은 http://deepcumen.com/2015/04/clustering/ 여기에 잘 설명되어 있어서 여기있는 내용의 일부를 첨부하였고 위키피디아에 있는 설명을 좀 덧붙였다. 

DBSCAN(Density-based spatial clustering of applications with noise)은 Density model들중 하나이고 K-Means와 같이 데이터의 위치정보를 이용한다. 하지만 K-Means 처럼 데이터의 분포(평균과의 거리가 얼마나 떨어져 있는지로 군집을 결정 했으므로) 를 통해 군집을 정하는 것이 아니라, 데이터들의 밀도를 이용한다. 같은 군집내의 데이터들은 밀도가 높게 위치해 있을것이라는 가정이다. 즉 주변데이터들의 밀도를 이용해 군집을 생성해 나가는 방식이다.


일단 이 알고리즘에서는 두가지 파라미터의 정의가 필요하다.

첫째는 주변 공간에대한 정의가 필요하며 두번째는 그 주변공간에 몇개의 데이터가 존재하야 군집으로 설정할 것인지에 대한 정의가 필요하다. 

첫째 주변공간에 대한 정의다.

우선 주변공간을 정의하는 각 데이터 벡터들로 부터의 반경을 이라고 하자, 다음으로 군집으로 인정하기 위한 반경 이내의 최소 갯수를 n 이라고 하자. 이 두개의 파라미터는 모델을 설계할 당시 정해주어야 하는 값이다. 이 2개를 정하는 기준에 대해서는 뒷쪽에 가서 다루겠다.


2개의 파라미터를 이용해 아래와 같은 개념들을 정의 한다.



  • 이웃벡터: 한 데이터 벡터로부터 거리  내에 위치한 다른 데이터 벡터들을 이웃벡터로 부르자.

  • 핵심벡터(core points): n개 이상의 이웃벡터를 갖는 데이터벡터를 핵심벡터로 부르자.

  • 직접 접근 가능한(directly density-reachable): 어떠한 핵심벡터 p와 p의 한 이웃벡터 q에 대해서 q는 p에 대해서 직접 접근 가능하다(p→q). 반대로 q가 핵심백터가 아니라면 p는 q로부터 직접 접근 가능하지 않다.

  • 접근 가능한(density-reachable): 어떠한 데이터 벡터 p와 q에 대해서 직접 접근 가능한 데이터 벡터 배열 {p= p1→p2 , ... , →q }가 있다면 q는 p로부터 접근 가능하다(p⇒q).

  • 연결된(density-connected): 어떠한 벡터 p와 q에 대해서 p와 q에 접근 가능한 벡터 o가 존재 한다면(o⇒p,o⇒q), p와 q는 서로 연결되어 있다(p⇔q).

  • 군집(Cluster): 한 핵심벡터 p에 대해서 접근 가능한 모든 데이터 벡터들의 집합을 군집으로 정의하며, 한 군집내의 모든 데이터 벡터들은 서로 연결되어 있다.

  • 노이즈(Noise): 어떠한 군집에도 속하지 않는 데이터들은 노이즈이다.



DBSCAN은 위의 개념들을 이용해서 군집과 노이즈를 분류하는 알고리즘 이다. 

위에서 군집은 한 핵심벡터로부터 접근 가능한 모든 데이터 벡터들의 집합이라고 정의했다. 즉 군집은 핵심벡터를 중심으로 생성된다. 또한 핵심벡터에서 접근이 가능하지만 핵심벡터는 아닌, '외곽벡터'가 존재한다. 또한 어떠한 핵심 벡터로부터도 접근 가능하지 않은 '노이즈'가 존재한다. 따라서 DBSCAN은 모든 데이터벡터 각각에 대해서 다음 아래로 분류하는 작업과 같다. 


핵심벡터: 한 데이터 벡터로 부터 거리 ϵϵ 내에 위치한 다른 데이터 벡터들의 수가 n보다 클 경우 하나의 군집으로 생성하며 중심이 된 벡터는 핵심벡터로 분류한다.

외곽벡터: 핵심벡터로 부터 거리 내에 위치해서 같은 군집으로 분류되나, 그 자체로는 핵심벡터가 아닌, 즉 군집의 외곽을 형성하는 벡터를 외곽벡터로 분류한다.

노이즈 벡터: 핵심벡터도 아니며 외곽벡터도 아닌, 즉 거리 이내에 n개 미만의 벡터가 있으며, 그 벡터들 모두 핵심벡터가 아닐 경우, 어떠한 군집에도 속하지 않는 노이즈 벡터로 분류한다.


예제를 보자 

n=5인 경우이다. 

포인트 벡터 p1은 거리 내 5개의 이웃벡터를 갖기 때문에 안심벡터이며 하나의 군집을 생성하며, p1의 직접 접근 가능한 다른 핵심벡터 p2 또한 같은 군집에 소속된다.


위 푸른색으로 표시한 데이터 벡터들은 이웃벡터의 수가 5개 미만으로 핵심벡터는 아니지만 핵심벡터의 이웃 벡터로써 핵심벡터와 같은 군집의 외곽벡터를 형성한다.


위의 회색으로 표시한 데이터 벡터들은 이웃벡터의 수가 5개 미만이며 이웃벡터에 핵심 벡터가 아니므로(어떠한 벡터로부터 접근이 불가하기 때문에), 군집에 포함되지 않는 노이즈로 분류한다. 

위와 같이 데이터들 각각에 대해서 분류를 하므로 위와 같은 군집을 생성할 수 있다. DBSCAN은 주어진 데이터들에 대해 각각의 데이터들을 세가지로 분류하는 것으로써 K-Means에 비교해 작동 방식은 상당히 명확하다.  (엄밀한 수식적 유도가 필요하지 않는다. ) 실제로 각각의 데이터들에 대해서 거리내의 다른데이터들의 숫자와 그 데이터 들의 구분을 이용해 분류해 나가면 된다.

k-means와 비교한 DBSCAN의 장점은 바로 군집의 갯수를 미리 정해줄 필요가 없다는 것이다. 각각의 데이터들에 대해서 밀도를 계산해서 군집을 생성하는 DBSCAN은 따로 군집의 갯수를 정의할 필요가 없다. 또한 그런 방식으로 군집을 생성하기 때문에 비선형 경계의 군집을 구하는 것도 가능하다. 또한 K-means 마지막에 언급한 `노이즈'에 관련된 문제도 DBSCAN은 노이즈 데이터를 따로 분류하므로써 노이즈 데이터들이 군집에 영향을 주지 않는다는 장점이 있다. DBSCAN은 n개수 때문에 소위 single-link효과(point들의 얄은 선에 의해 다른 클러스터들과 연결되는것)가 줄어든다 ( 클러스터의 경계에서 줄타기하는 점이 줄어든다는 말인듯).

 



물론 단점들 또한 존재하는데, 바로 연산에서 데이터들을 사용하는 순서에 따라서 군집화가 결정적이지 않다는 것이다. 의 거리 내에 n개 이상의 데이터는 없지만 핵심벡터가 존재할 경우, 해당 군집에 포함시키고 외곽벡터로 한다고 위에서 정의하였는데, 2개 이상의 각기 다른 군집의 핵심벡터가 있을 경우, 연산하는 데이터의 순서에 따라서 해당 외곽벡터는 다른 군집에 포함되는 문제가 발생할 수 있다. 하지만 다행인 것은, 이 문제는 그렇게 자주 발생하는 문제는 아니며 또한 그렇다 하더라도 군집 자체에 큰 영향을 주는 문제는 아니라는 것이다.  또한 어떠한 거리측정법을 사용하느냐에 따라 고차원데이터에서 차원의 저주에 걸려 적절한 을 찾는데 어려워진다. 


그렇다면 이제는 파라미터들(, n)에 대한 설명을 해보겠다.


  • 클러스터내의 최소 데이터 갯수(n) : n은 데이터셋에서 차원의 수로부터 도출될 수 있다. 그러나 n=1인 것, 모든 점이 클러스터가 된다는 말이므로 말이 되고, n ≤ 2 이게 되면 single link 계산법으로 구한 계층적 군집방법과 같아지므로  n은 적어도 3은 되어야 한다. 보통 더 많은 데이터셋일 수록 , 더 많은 n이 선택되어야 한다. 

  • 핵심벡터로부터의 반경() : 는 k-distance graph를 사용해 이웃한 n개의 점들과의 거리를 그래프에 그림으로써 결정될 수 있다.  좋은 값은 강력한 유대를 보인(거리가 가깝다는 말인듯) 것이다. 값이 극단적으로 작다면, 대부분의 데이터는 클러스터링이 안될 것이고, 반대로 극단적으로 크다면 모두가 한 군집이 될 것이다. 일반적으로 작은 값을 선호한다. 

  • 거리함수 : 거리함수의 선정은 의 선택과 밀접하게 연관되고, 결과에 큰 영향을 미친다. 일반적으로, 가 결정되기 전에 데이터 셋에서 합리적인 유사도 측정을 알아내는 것이 필요할 것이다.


OPTICS 은 DBSCAN의 일반화이다. OPTIC은 를 성능에 가장 영향을 미치는 최고값으로 교체했다. 따라서 n은 필수적으로 찾아야할 군집크기가 최소화 된다. 알고리즘에서 파라미터화 하기 더 쉬워진 반면, 결과를 사용하는 것이 더 어려워 졌다. 이것은 보통 DBSCAN이 생성한 간편한 데이터 분할 대신 계층적 군집을 생성해 낼 것이다. 최근 DBSCAN을 만든 사람이 더 이상 경계점들의 정의가 없는 HDBSCAN(hierarchical DBSCAN)을 개재 했다.



'ML & DM > Clustering' 카테고리의 다른 글

Clustering Evaluation and assessment  (0) 2016.04.07
PAM (Partitioning Around Medroid)  (0) 2016.04.06
K-Means Algorithm  (0) 2016.02.03
Clustering  (0) 2016.02.02