DBSCAN clustering 이해하기(밀도기반 알고리즘)

DBSCAN의 개념

DBSCAN은 Density-Based Spatial Clustering of Applications with Noise의 약자로, 한국말로 풀이하면 노이즈를 적용한 밀도 기반 공간 클러스터링이라고 해석할 수 있다. 한마디로 Density-Based 알고리즘이기 때문에, "밀도 기반"으로 클러스터링을 하게 된다는 의미이다.

 

K-Means의 문제점

DBSCAN을 이해하기에 앞서, 대표적인 클러스터 알고리즘인 K-Means을 떠올려보자. K-Means은 이상치(outlier)가 있어도 이상치 값을 이해 할 수 없으며, 이상치가 심지어 K-Means를 자신의 주변으로 끌고 와서 centroid값을 바꿔버릴 수 있다. 이는 클러스터의 품질을 심하게 망칠 수 있는 critical risk이다.

 

K-Means는 이 문제를 극복하기 위해서 클러스터링을 하기 전에 outlier의 존재를 인지해야 하며, 클러스터의 품질을 위해 이상치를 제거해야 하는 과정이 필요할 수 있다.

 

DBSCAN의 설정

DBSCAN은 특정 요소가 클러스터에 속하는 경우 해당 클러스터 내 다른 많은 요소와 가까운 위치에 있어야 한다는 아이디어를 전제로 하며, 이 계산을 위해 직경(Radius)와 최소 요소(Minimum points)를 사용한다.

R(Radius of neighborhoood)

- Radius(R)은 특정 데이터 요소를 기준으로 반경을 정한다. 이를 밀도 영역(dense area)이라고 한다.

M(Min number of neighbors)

- M은 핵심 요소를 지정하기 위해 핵심 요소 주변으로 요소가 몇개 있는지 지정한다.

 

데이터세트의 각 요소는 핵심(core), 경계(border), 이상치 요소(outlier point)로 구분된다.

 

 

DBSCAN의 프로세스

Fig. 1. DBSCAN 데이터 예시

 

Fig. 1 처럼 총 요소가 10개가 존재한다고 해보자, K-Means였다면 여기에 클러스터를 몇개 할지 K개를 설정하고, 그 K개에 맞게 어떻게든 클러스터링 구현했을 것이다. DBSCAN의 장점은 우선 K개를 설정할 필요가 없다는 것이다.

 

Fig. 2. Radius 설정과 Core Point

 

Fig. 2에서 붉은색으로 칠한 요소를 기준으로 R의 값을 반영해보면, Radius에 겹치는 요소가 3개가 있다. 여기 M=3이라고 한다면, 현재 기준으로 되는 요소는 core point가 되며, 나머지 Radius안에 겹치는 요소들은 border point가 된다.

 

Fig. 3. 클러스터 구성

 

Fig. 3을 보면 M=3인 요소를 찾아보니, 우측의 중앙에 있는 요소도 core point이기 때문에 위와 같은 모습의 클러스터가 만들어졌다. 

 

Fig. 4. Outlier 지정

 

Fig. 4를 보면 검정색으로 표시한 point가 있는데 어느 클러스터에도 속하지 않은 point로 noise point가 되고 곧 outlier로 인식하게 된다. 마지막으로는 클러스터간에 radius가 겹치는 구간이 있다면 해당 클러스터는 서로간에 합치게 된다. 

 

Fig. 5. 최종적인 DBSCAN 모습과 설명

 

Fig. 5는 위 알고리즘을 설명하기 쉽게 클러스터별로 color를 다르게 하였고, color별로 point 설명을 추가하였다.

 

 

최종적으로 위 내용들을 정리하자면, 아래와 같다.

 

1. 요소별로 R의 크기를 체크하여, 주변의 요소가 몇개 있는지를 탐색한다.

2. R 크기 안에 M개수 이상의 요소가 존재하면, 해당 요소는 Core point가 된다. 

3. Core point 안에 있는 요소는 Border point가 된다.

4. Core point 안에 속하지 못한 요소는 Noise point=outlier가 되며 클러스터에서 제외가 된다.

5. Core Point 사이의 거리가 R안에 속할 경우, 서로 같은 클러스터로 묶이게 된다.

 

DBSCAN은 Core Point끼리 묶이기 모습 때문에 K-Means와는 전혀 다른 클러스터링을 만들 수 있는데 아래와 모양의 클러스터가 가능해진다.

 

DBSCAN의 독특한 클러스터링 모습 [2]

 

 

위의 데이터를 K-Means로 구현했다면, 마치 피자를 자른 모양처럼 클러스터가 됐을텐데 DBSCAN은 이렇게 땅따먹기 형태로 클러스터가 되기에 전혀 다른 클러스터를 구현할 수 있다.

 

DBSCAN을 구현하고 싶다면 아래 포스팅을 보도록 하자

DBSCAN Clustering 구현하기

 

References

[1] Coursera IBM, Machine Learning with Python

[2] https://www.digitalvidya.com/blog/the-top-5-clustering-algorithms-data-scientists-should-know/

연관자료

K-means clustering 구현하기

KNN(k최근접) 알고리즘 설명 및 구현하기

DBSCAN Clustering 구현하기