07. [Clustering] DBSCAN

1. DBSCAN 이란?

• 밀도 기반 클러스터링
• 밀도가 높은 부분을 군집화
• 임의의 모양의 클러스터도 찾아낼 수 있음
• 클러스터의 수 지정할 필요 X
• 어느점부터 시작해도 상관없는 편

 

 

2. 방법

• 점 P로부터 eps (반경) 내에 minPts 개 존재하면 하나의 군집으로 인식
• 그 점을 중심으로 군집이 되며 그 점을 core point라고 함
• core point가 서로 다른 core point의 군집 일부가 되면 그 군집을 서로 연결되어 있다고 하며 하나의 군집으로 연결
• border point : 군집에는 속하지만 core point는 안되는 점 (eps 내에 minPts 만족 X)
• noise point : 어느 군집에도 속하지 못하는 점

 

 

3. 용어 설명 및 방법

   1) directly density-reachable

       : 점 q 주변 eps내에 minPts 이상의 데이터 포인터가 존재하는 경우

 

   2) density - reachable

       : directly density-reachable 하지 않지만, 중간에 매개체가 있다면 density - reachable 하다!

   3) density - connected

• directly density reachable 한 지점들을 연결 →   density - reachable  한 점이 생김!
• density reachable 한 지점들을 연결 →  density - connected 하다!!
  : density - connected 로 양쪽의 border 포인트를 연결 가능!
    더이상 density - connected 된 점이 없다면 종료, 다음 클러스터를 만들며 밀도 낮은 곳에 홀로 고립된 데이터는 noise로 취급된다!