#3-(7) 군집 알고리즘 : DBSCAN

※ 이 글의 내용은 O'REILLY의 <파이썬 라이브러리를 활용한 머신러닝> 책을 기반으로 한다.

군집 알고리즘 : DBSCAN

• DBSCAN

 - DBSCAN(Density-Based Spatial Clustering of Applications with Noise) : DBSCAN은 밀도를 기반으로 하여 군집화하는 매우 유용한 군집 알고리즘이다. k-평균 군집이나 계층적 군집 알고리즘의 경우 데이터 간의 거리를 이용하여 클러스터를 나누는데에 반해, DBSCAN 알고리즘은 데이터 포인트가 세밀하게 몰려 있어 밀도가 높은 부분을 군집화하는 방식이다. 

 - 먼저 DBSCAN 알고리즘은 특성 공간(Feature Space)에서 데이터가 밀집해있는 지역의 포인트를 찾는다. 이러한 지역을 특성 공간의 밀집 지역(Dense Region)이라 한다. 이러한 데이터의 밀집 지역이 하나의 클러스터를 구성하며, 비교적 비어있는 지역을 경계로 다른 클러스터와 구분하는 것이다. 밀집 지역에 있는 포인트를 핵심 샘플(핵심 포인트)라고 하며, 임의로 선정한 하나의 데이터 포인트에서 지정 거리(eps) 안에 데이터가 최소 샘플 개수(min_samples)만큼 들어 있으면 이 데이터 포인트를 핵심 샘플로 분류한다. 따라서 지정해 준 거리보다 가까이 있는 핵심 샘플은 DBSCAN 알고리즘에 의해 동일한 클러스터로 합쳐진다. 간단하게 말해서, 어느 포인트를 기준으로 지정 반경 내에 데이터 포인트가 n개 이상 있으면 하나의 클러스터로 인식하는 방식이다.

 - 만약, 임의로 선정한 하나의 데이터 포인트에서부터 지정 거리 이내에 포인트 수가 최소 샘플 수보다 적다면 그 포인트는 어떤 클래스에도 속하지 않는 잡음(Noise)으로 레이블한다. 최소 샘플 수보다 많으면 그 포인트는 핵심 샘플로 레이블되고 새로운 클러스터 레이블을 할당한다. 그 다음 그 포인트의 지정 거리 안의 모든 이웃을 살핀다. 아직 어떤 클러스터에도 아직 할당되지 않았다면 바로 전에 만든 클러스터 레이블을 할당한다. 만약 이미 할당이 완료된 핵심 샘플이면 그것의 이웃 포인트로 넘어가서 일련의 과정을 반복한다. 이런 식으로 클러스터는 지정 거리 안에 더 이상 핵심 샘플이 없을 때까지 성장한다. 그 다음 방문하지 못한 밀집 지역의 포인트를 임의로 선정하여 같은 과정을 반복한다.

 - 최종적으로 데이터는 핵심 포인트, 경계 포인트(클러스터 내에 속하나 지정 반경 내 최소 샘플 개수를 만족하지 못한 포인트), 잡음 포인트 세 가지로 나뉜다. DBSCAN을 한 데이터 세트에 여러 번 실행하면 핵심 포인트의 클러스터는 항상 같고, 매번 같은 포인트를 잡음으로 레이블한다. 그러나 경계 포인트의 경우, 클러스터 핵심 샘플의 이웃이 중복될 수 있다. 따라서 임의의 포인트가 어디에서부터 선정되어 알고리즘이 적용되는지에 따라 경계 포인트가 어떤 클러스터에 속할지는 매번 달라진다. 일반적으로 경계 포인트는 많지 않으며 포인트 순서로 때문에 받는 영향도 적어서 중요한 문제는 아니다.

 - DBSCAN 알고리즘의 매개변수는 최소 샘플 개수(min_samples)와 지정 거리(eps)가 있다. 지정 거리가 증가하면 하나의 클러스터에 더 많은 포인트가 포함된다. 이는 클러스터를 커지게 하지만, 여러 클러스터를 하나로 합치게도 만든다. 일반적으로 지정 거리가 가까운 포인트의 범위를 결정하기 때문에 매우 중요하다. 지정 거리를 매우 작게 하면 어떤 포인트도 핵심 포인트가 되지 못하고, 모든 포인트가 잡음 포인트가 될 수 있다. 반대로 지정 거리를 매우 크게 하면 모든 포인트가 단 하나의 클러스터에 속하게 된다. 최소 샘플 개수 설정은 조밀하지 못한 지역에 있는 포인트들이 잡음 포인트가 될 것인지 하나의 클러스터가 될 것인지를 결정하는 데 중요한 역할을 한다. 

 - DBSCAN 방식은 클러스터의 개수를 미리 지정할 필요가 없으며, 계층적 군집이나 k-평균 군집과는 달리 복잡한 형상도 찾을 수 있다. 다만 지정 거리(eps)의 값이 간접적으로 몇 개의 클러스터가 만들어질지 제어하므로 적절한 지정 거리를 찾으려면 모든 특성의 스케일을 비슷한 범위로 조정해주는 것이 좋다.