본문 바로가기
스터디/인공지능, 딥러닝, 머신러닝

[Clustering] Density-Based Methods, DBSCAN

by 궁금한 준이 2023. 5. 25.
728x90
반응형

 

Basic Concept of Density-Based Clustering

Major features

  • 임의의 모양에 대한 clustering이 가능 (arbitrary shape)
  • noise 조절
  • 1번만 조회 (one scan)
  • 종료 조건으로 density parameter가 필요함

density-based clustering으로 DBSCAN, OPTICS, DENCLUE, CLIQUE 등이 있고 DBSCAN에 대하여 알아보자.

 

DBSCAN

Density-Based Spatial Clustering of Applications with Noise

DBSCAN 알고리즘은 2014 KDD test of time award를 수상했다.

  • arbitrary shape
  • robust to noise
  • scales well to large databases

Two parameters

Eps (Epsilon): Maximum radius of the neighborhood

MinPts (Min-Points): eps-neighborhood 안에 있어야 하는 point의 최소 개수

 

eps-neighborhood은 다음과 같이 집합의 형태로 표기한다.

Neps(p)={qDdist(p,q)Eps}

 

Directly density-reachable (직접 밀도 도달가능)

p가 두 조건(pq의 반경안에 있고, q가 core point)을 만족하면 directly density-reachable 하다고 한다.

아래 그림을 예시로 들면, (1) pq의 이웃반경 안에 존재하고, (2) N(q)의 크기는 minpoint=5 보다 크기 때문에 q는 core-point이다. 따라서 pq로부터 직접밀도 도달가능한 관계이다.

Directly density-reachable

  • pNeps(q)
  • Core Point Condition: |Neps(q)|MinPts

Density-reachable (밀도 도달가능)

q=p1,p2,,pn1,pn=p에 대하여 pi+1pi로부터 직접밀도도달가능하면, pq로부터 밀도 도달가능하다고 한다.

Density-reachable

 

Density-connected (밀도 연결)

pq 모두 어떤 점 O로부터 density-reachable하면 pq와 밀도연결되었다고 한다.

Density-connected

Basic Concepts

(하나의) Cluster는 density-connected points의 극대 집합(maximal set)이다.

Border: Cluster에 속하지만 Core는 아니다. (MinPts를 만족하지 못한다.)

Outlier (Noise): 어떠한 클러스터에도 속하지 않는다.

Example for Border, Coer, and Outlier
Example for Border, Core and Noise (Outlier)

DBSCAN Algorithm

  1. 임의의 점 p를 선택한다.
  2. p로부터 density-reachable한 모든 점을 모은다.
  3. p가 core point라면, 클러스터가 형성된다.
  4. p가 border point라면 모든 점들이 p로부터 density-reachable하지 않으므로, 다음 point에 대하여 DBSCAN 알고리즘을 다시 시행한다.
  5. 모든 점이 process될 때까지 반복한다.

Pseudo-code for DBSCAN

DBSCAN Execution Example





epsilon=2이고 min-points=3으로 미리 파라미터가 세팅되어있고, 분홍색 점들은 아직 classified되지 않은 점들이라 하자.


현재 점(p1)을 붉은색이라 하고 이웃반경 N2(p1)를 녹색이라 하자.
|N2(p1)|=3이므로 p1은 core point이다.
density-reachable한 점들을 모으면 녹색이므로 p1은 클러스터 c1으로 분류한다.


|N2(p2)|=4이므로 p2은 core point이다.
density-reachable한 점들은 녹색이고, p2 역시 같은 클러스터 c1으로 분류한다.


|N2(p3)|=5이므로 p3은 core point이다.
density-reachable한 점들은 녹색이고, p3 역시 같은 클러스터 c1으로 분류한다.



(생략)


unvisited(unclassified) point에서 새로 시작한다.
이 점(p6)은  |N2(p6)|=1이므로 core point가 아니다.
따라서 NOISE(outlier)로 분류한다.


|N2(p7)|=3이므로 p7은 core point이다.
density-reachable한 점들은 녹색이고, p7은 새로운 클러스터 c2로 분류한다.

|N2(p8)|=3이므로 p8은 core point이다.
density-reachable한 점들은 녹색이고, p8은 클러스터 c2로 분류한다.


(생략)

(생략)
마지막 점 역시 c2로 분류한다.

최종적으로 2개의 cluster를 형성했고, 한 점은 outlier로 남아있다.

Example for DBSCAN procedure

반응형

Remarks

Complextity

일반적으로 O(n2)이지만 2차원 데이터에서 index를 사용하면 O(nlogn)도 가능하다.

Note: 원 논문에서는 index를 사용하면 O(nlogn)이라 주장했으나 후속 논문에 의해 dim2 조건이 필요함이 추가되었다.

Advantages

  • cluster 개수를 지정할 필요가 없다. (k-means는 클러스터 개수 k를 직접 지정해야 했다.)
  • 어떤 모양의 데이터든지 cluster를 형성할 수 있다. (k-means는 구 모양 처럼 convex-shaped만 가능했다.)
  • noise를 다룰 수 있다
  • data point의 순서에 영향을 받지 않는다. (BIRCH 알고리즘은 순서에 영향을 받는다.)

Disadvantages

  • 파라미터(eps, MinPts)의 적절한 값을 찾기 어렵다.
  • density가 많이 차이나는 데이터에는 적절하지 않다.

DBSCAN is sensitive to parameters (1)
DBSCAN is sensitive to parameters (2)

 

Determining the Parameters

DBSCAN 논문의 저자들은 heuristic한 방법을 제시했다.

thinnest cluster를 형성하는 parameter를 찾는 아이디어에서 착안했다.

Heuristic method

kdist: 각 점마다 k-nearest neighbor를 형성하는 최소 거리

 

MinPts: 고정된 값을 사용한다. 특히 2차원 데이터에 해아여 4를 이용할 것을 권장한다.

Eps: MinPts-dist 그래프에서 첫번째 꺾인 점(first valley)로 한다.

4dist for point p and q

 

Sorted k-dist graph

 

728x90
반응형