04. 군집화(2)-DBSCAN(Density-based spatial clustering of applications with noise)

군집화-Clustering

군집화는 주어진 데이터들을 비슷하거나 유사한 데이터끼리 그룹으로 묶는 비지도학습의 일종이다. 

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

 

(그림 : DBSCAN이 잘 처리하는 데이터 분포 VS DBSCAN 사용이 비효율적인 분포)

 DBSCAN은 군집화의 여러 방법 중 하나로, 노이즈에 대해 강건하며, K 평균에 비해 연산량은 많지만 K평균이 잘 처리하지 못하는 오목한 데이터세트에 대해 높은 처리 능력을 보여주는 방법이다.

 DBSCAN은 '노이즈가 있는 애플리케이션을 위한 밀도에 근거한 공간적인 군집화'의 줄임말이다. 이름만 들어선 왠지 데이터베이스를 스캔해야 할 것 같지만 데이터베이스와 DBSCAN은 별로 관계가 없다. 이름에서 알아챌 수 있듯, DBSCAN은 '밀도'를 기반으로 한 군집화 알고리즘이다. 그런 연유로 노이즈(동떨어진 데이터)의 처리에 대해 K 평균 대비 높은 성능을 보인다.

DBSCAN의 동작

 DBSCAN은 우선 데이터세트를 받아온다. 데이터세트의 모든 데이터에 대해 탐색을 수행하는데, 이 탐색의 과정은 상술했듯 '밀도'를 기반으로 '코어', '노이즈', '보더(경계)를 나누는 곳에서 시작한다.

.

코어는 일정 기준 이상의 밀도를 갖는 데이터(점)으로, 코어에서 코어로 탐색을 수행한다.

노이즈는 일정 기준 미만의 밀도를 갖고, 군집(클러스터)에도 소속되어 있지 않은 데이터이다.

보더는 일정 기준 미만의 밀도를 갖지만, 군집에 소속되어 있는 데이터이다. 보더를 만나면 그 군집에서의 탐색을 중지한다.

.

 우선 알고리즘은 탐색할 순서가 된 데이터가 방문한 데이터인지 알아보고, 방문하지 않은 데이터라면 탐색할 데이터에서부터 미리 정의한 거리 내에 있는 데이터들의 개수를 파악하고, 그 개수가 기준치 이상이면 이를 코어로 설정한다, 코어로 설정할 때, 군집을 설정한다. 혹 개수가 기준치 미만이라면, 그 데이터를 노이즈 혹은 보더로 정의한다(군집에 대해 탐색 중이었다면 보더, 아니라면 데이터) 코어로 설정한다면, 다시 일정 거리 안에 있는 모든 데이터들에 대해 똑같은 탐색을 실시한다. 코어에서 코어로 탐색을 실시하는 경우는 그 코어의 군집을 부여하며, 아니라면 새로운 군집에 소속되게끔 한다.

 의사 코드로 알아보자, 

for x는 X의 원소 에 대해 하나씩 2:     x가 방문한 데이터가 아니면(코어, 보더, 노이즈로 정의되지 않았다면) :         x의 주변이 임계치 미만의 밀도를 갖는다면 :             x는 노이즈 혹은 보더             루프를 계속한다.         x의 주변이 임계치 이상의 밀도를 갖는다면 :             x는 코어             x에 c 클러스터 할당             x의 주변 데이터 집합에 대해 (2) 반복 goto 2  # 재귀             이 코어에 대한 탐색이 끝났다면 다음 데이터는 새로운 군집으로 설정     x가 방문한 데이터이면:         다음 데이터로 이동한다

DBSCAN의 장점과 단점

 DBSCAN은 일정 밀도 이상을 가진 데이터를 기준으로 군집을 형성하기 때문에, 노이즈 처리에 강하다. 또한, 개수를 기준으로 점점 확장해가는 K 평균과 달리 밀도를 가진 코어들이 이어져가는 방식을 취하기 때문에, U자형과 같이 오목한 데이터, 혹은 H와 같은 모양을 띄는 데이터 분포도 잘 군집화할 수 있다.

 하지만, 많은 연산을 수행하기에 K 평균에 비해 그 속도가 느린것이 단점이며, 반지름과 임계치 설정에 많은 영향을 받는다는 단점 또한 존재한다. 그리고, 유클리드 제곱거리를 사용하는 모든 데이터 모델의 공통적인 단점인, 'Curse Of dimensionality 또한 존재한다, 이는 2차원이나 3차원 등 차원수가 낮은 데이터세트에는 문제가 되지 않지만, 고차원 데이터세트로 갈수록 필요한 학습 데이터 양이 급증하는 문제점이며, 이 때문에 많은 연산이 필요해진다는 단점이 있다.