[Density-based Clustering] DBSCAN

DBSCAN

= Densit Based Spatial Clustering of Applications with Noise

 

Distance-based가 아니기 때문에 noise를 가진 spatial db에서 어떠한 모양의 cluster더라도 발견해낼 수 있다.

다만 parameter(Eps, MinPts)에 대해 sensitive하다.

 

• core
  • 주변에 충분한 neighbor들이 존재하는 점
  • $N_{Eps} \geq MinPts$
•  cluster
  • 어떤 점으로부터 최대한 density-connected한 points들의 집합
  • maximal set of density-connected points
• outlier
  • 주변에 충분히 density한 점들이 없는 점
  • $N_{Eps}(p) < MinPts$

 

방법

1. 임의의 점 p를 선택한다.
2. 점 p로부터 주어진 Eps와 MinPts에 대해 density-reachable한 모든 점들을 찾는다.
3. 점 p가
   • core point이면 cluster가 형성된다.
   • border point이면 DB에서 다음 점을 선택한다.
     • 충분한 density를 확보하지 못한 점
     • = p로부터 density-reachable한 점이 없는 경우
4. 주어진 모든 점에 대해 위 과정을 반복한다.