..

DBSCAN 정리

DBSCAN

강병규

얼마 전 팀 내 스터디로 들은 DBSCAN에 대한 간단한 정리.

들어가며

클러스터링은 대표적인 비지도 학습 방법 중에 하나이다. 2차원 공간을 생각해보면 데이터들을 좌표평면 위에 점의 형태로 나타낼 수 있을 것이다. 가능한 유사한 데이터끼리 묶어주어 데이터들 간의 일종의 그룹 - 클러스터를 만들어내고 이들 간의 알지 못했던 관계를 찾아내기 위해 사용하는 것이 클러스터링이다. 이때 학습하는 파라미터가 존재하지 않으므로 비지도 학습인 것이다.

통상적으로 흔히 생각하는 클러스터링 방법은 중심 기반의 클러스터링이다. 비슷한 관계를 가지는 점(혹은 데이터)끼리는 특정한 중심을 기준으로 가까이에 위치할 것이라는 가정을 할 수가 있다. 이를 바탕으로 특정 중심으로부터 클러스터 “내의” 점들끼리의 거리는 “최소화”히고, 클러스터 “끼리의” 거리는 가능한 “최대화”하도록 데이터를 묶는다.

특정 중심으로부터 일정한 거리 내의 있는 점들을 묶어내기 때문에 이들은 원의 형태로 결과가 만들어지는 경우가 일반적이다.

이때 아래와 같은 데이터를 생각해보자.

image

중심점의 개수를 두 개로 하고 중심 기반의 클러스터링인 K-means를 수행한 결과이다. 가까이 있는 점들이 서로 다른 클러스터로 묶인 것을 확인할 수 있다. 과연 이러한 결과가 진정 우리가 원하는 결과인가?

DBSCAN은 이러한 문제를 해결하기 위한 방법 중 하나다. 이전의 중심 기반 클러스터링과 다르게, 밀도 기반의 클러스터링을 수행한다. 같은 클러스터에 속하는 점들이 서로 근접하게 분포할 것이라 가정하는 것이다.

DBSCAN

점들이 근접하게 분포하는지 확인하는 가장 쉬운 방법은 특정 점에서 일정한 반지름을 가지는 원을 그려보는 것이다. 이 원 안에 다른 점들이 존재한다면 이들은 근접하게 분포하고 있다고 생각할 수 있다. 이것이 DBSCAN의 기본적인 아이디어다.

점 하나를 기준으로 $epsilon$의 길이를 가지는 원을 그린다. 이 원 안에 $n$개 이상의 점이 존재한다면 이들이 하나의 군집으로 속해있다고 생각하는 것이다. 데이터가 한 두개가 아닐테니 많은 원들이 그려질 것이다. n개를 채우지 못한 점들은 노이즈라고 생각하고, n개를 채운 점들만 생각해보자.

이 원 각각이 클러스터라고 생각하는 것은 무리가 있다. 이렇게 되면 어떤 점을 먼저 중심점으로 잡았느냐에 따라 다른 결과가 나오게 될 것이다. 이들끼리 다시 묶어주는 작업을 거쳐 더 큰 클러스터로 만들어준다.

위키피디아를 보면 reachable, direct reachable에 대한 얘기가 나오는데, 사실 단순하게 생각해도 된다. 그냥 각각의 점들을 중심으로 한 원을 그렸을 때-두 원 모두 n개 이상의 점을 가진다고 하자-교집합이 존재한다면 이들을 묶어 더 큰 클러스터를 만들어주는 것이다. 이러한 밀도 기반의 클러스터링을 이용하면 위의 문제를 해결할 수 있게 된다.