DBSCAN

DBSCAN 

• Density based clustering technique이다.
• 비공식적 가정 : 클러스터는 높은 밀도 지역에 존재하고, 다른 낮은 밀도 지역과는 분리되어 있다.
• DBSCAN의 목적
  - 임의의 모양의 cluster를 찾을 수 있다
  - outlier/noise에 강하다

DBSCAN algorithm

• 2개의 parameter 존재
  - 이웃의 크기 : ε
  - 이웃 내에 있는 최소의 포인트 개수 : MinPts
• 각 포인트의 이웃은 ε보다 더 작은 거리에 있는 모든 다른 점들로 구성된다
• DBSCAN은 포인트를 3개 포인트의 그룹으로 분류함으로써 작동한다
  - Core point : 만약에 이웃이 적어도 MinPts개의 포인트를 포함한다면
  - Border point : core point는 아니지만, core point의 이웃인 것
  - Noise point : core/border가 아닌 point들

 

1단계 : 모든 포인트들을 core, border, noise 포인트로 라벨링하라

2단계 : core point들의 그룹을 만들어라 : ε 내에 있는 코어 포인트들로 cluster를 할당하라

3단계 : 각각의 border 포인트를 그것과 관련된 코어 포인트의 클러스터로 할당하라

 

- 실제적으로, 계산적인 코스트를 줄이기 위해 알고리즘은 다르게 수행된다. 

- 클러스터에 대한 border point의 할당은 unique하지 않다. 즉, border 포인트는 하나 이상의 core point과 관련될 수 있다.

-  Euclidean 거리가 아닌 다른 거리 함수 사용할 수 있다.

 

Tuning of hyper-parameter

• 초기 파라미터를 찾는 전략 : k-NN 거리를 계산하라.
  (k-NN 거리는 하나의 포인트에서 k개의 가까운 이웃들 사이의 거리이다.)

1단계 : 초기 k 값을 지정하라. 경험적으로, $k >= d+1$ 이다. 여기서 d는 데이터 차원이다. 예를 들어, d=2이면 k=4 이런 식으로 잘 작동한다.

2단계 : 각각의 포인트에 대해서 k-NN 거리를 계산한다.

3단계 : increasing order로 나열하고 plotting 해라.

4단계 : sharp change인 포인트를 찾고, 그 때의 거리를 ε 로 지정해라. 그리고 그 때의 k를 MinPts로 지정해라.
         만약, 그러한 elbow point가 보이지 않으면, k를 바꿔라.

 

- 만약 ε 이 너무 크거나 MinPts가 너무 작으면, 모든 포인트가 core point로 라벨링 된다. 그리고 종종 단일 크러스터를 얻게 된다.

- 만약 ε 이 너무 작거나 MinPts가 너무 크면, 모든 포인트가 noise point로 라벨링 된다. 

 

 

Pros and Cons

• 장점
  - 클러스터의 수가 정해지지 않아도 된다.
  - 아웃라이어에 robust하고, outlier를 찾는 tool로 사용될 수 있다.
  - 임의적인 형태의 클러스터를 찾을 수 있다.

 

• 단점
  - Hyper-parameter를 결정하기 어렵고, 파라미터의 선택에 민감하다.
  - 클러스터들이 다양한 밀도를 가지면, 알고리즘은 어려움을 가진다.
  - 만약에 차원이 크면 (대부분의 클러스터링 알고리즘은 고차원 데이터에 대해서 어려움을 가진다) 어려움을 가진다.

 

R에서는 dbscan 패키지에 있는 dbscan() 함수나 kNNdistplot() 함수를 사용해서 DBSCAN을 수행할 수 있다.

 

DBSCAN을 포함한 밀도 기반 clustering 기법은 대개 parameter에 매우 민감하다.

 

 

[참조] https://m.blog.naver.com/sw4r/221034800194 를 요약한 것입니다.