[Cluster Analysis] Density-Based Clustering

Density-Based Clustering

일정 이상의 density를 가지는 점들을 같은 cluster로 취급한다.

Distance-based가 아닌 density-based이다.

 

특징

• Shape of cluster
  • 어떤 모양의 cluster이든 발견할 수 있다.
  • K-Means는 긴 것은 자르는 경향이 있고 원 모양대로 묶인다.
  • Density-based는 별모양이든 반원 모양이든 모양대로 묶을 수 있다.
• Robust
  • Noise에 견딜 수 있다.
  • K-means는 noise에 의해 중심이 이동되기 때문에 noise에 영향을 받는다.
• 1 DB scan
  • 1번의 scan으로 clustering이 가능하기 때문에 효율적이다.
• Density threshold
  • 묶을 density의 threshold를 정해주어야 한다.
  • Threshold에 sensitive하기 때문에 좋은 특성은 아니다.

 

2 Parameter : Eps, MinPts

Density를 구하기 위해 영역이 정의되어야 한다.

이를 위해 2개의 파라미터가 필요하다.

• Eps : 반경
  • neighbor로 취급할 최대 거리(반경)
  • eps 내부에 있는 object들은 neighbor가 된다.
  • $N_{Eps}(p) : \{ q \; belongs; to \; D | dist(p, q) \leq Eps \}$
    • p의 Eps-neighborhood : p와 거리가 eps보다 작은 점들의 집합
• MinPts : 최소한의 eps-neighrbor 수 
  • Cluster로 묶기 충분하다고 판단할 최소한의 neighbor 수

 

Density-Reachable, Density-Connected

• Directly density-reachable
  • not symmetric : p가 q로부터 directly density-reachable하더라도 q는 p로부터 directly density-reachable하지 않을 수 있다.
  • 아래 조건을 만족하면 p는 q로부터 directly density-reachable하다.
    • p는 q의 Eps-neighbor이다. → p가 $N_{Eps}(q)$에 속한다.
    • q가 core point이다. = q가 충분한 density를 가지고 있다. → $|N_{Eps}(q)| \geq MinPts$

• Density-reachable
  • directly는 아니지만 desity-reachable 할 수 있다.
  • 간접적으로 directly density-reachable하게 연결되어있으면 density-reachable하다고 한다.
    • $p_1, ..., p_n$이 있을 때 $p_{i+1}$은 $p_i$로부터 directly density-reachable 하다.
    • → 간접적으로 directly density-reachable하게 연결되어있으면 된다.

• Density-connected
  • 제 3의 point로부터 서로 density-reachable하면 p와 q는 density-connected하다고 한다.

 

종류

• DBSCAN
• OPTICS
• CLIQUE