[Density-based Clustering] OPTICS - Ordering Objects

OPTICS

= Ordering Points To Identify the Clustering Structure

 

특징

Cluster의 구조를 알기 위해 point를 순서화하여 시각화하는 preprocessing 도구이다.

 

• DBSCAN의 확장 버전으로 주로 좋은 Eps를 찾기 위해 사용한다.
  • MinPts를 고정하고 Eps를 변화시키면서 clustering을 함으로써 좋은 파라미터를 찾을 수 있다.
• Clustering-ordering 정보는 Eps에 대한 nested 관계를 보여준다.
• 그래프화/시각화를 통해 표현할 수 있다.
• 내제된 cluster의 구조를 찾으면서 automatic하고 interactive하게 cluster analysis를 할 수 있다.
  • 사용자가 적절한 Eps 값을 찾을 수 있게 시각화하기 때문에 사용자와 interactive하다.

 

개념

• nested density-based cluster
  • $\epsilon$이 커지더라도 기존에 같은 cluster로 묶인 것은 그대로 묶이고 다른 point가 추가적으로 묶인다.
  • 아래 그림에서 $Eps = \epsilon _2$을 사용한 clustering은 합쳐지며 추가적인 point가 묶여서 $Eps = \epsilon _1$의 결과가 만들어진다.

• core distance : 점 o를 core point로 만들어주는 distance의 최솟값을 점 o의 core distance라고 한다.
• reachability distance
  • $r(p, o) = max(core-distance(o), d(o, p))$
  • 점 o가 core-distance이어야 하기 때문에 max를 사용해야 한다.
  • 점 p를 점 o로부터 directly density-rechable하게 만들어주는 distance이다.
    • directly density-reachable의 조건
      • 점 o가 core point이어야 한다. → $N_{Eps}(o) \geq MinPts$ (MinPts는 주어진 상수)
      • $d(o, p) \leq Eps$

 

방법

1. 임의의 object o를 선택한다.
2. object o로부터 나머지 object까지의 reachability distance를 계산하고 가장 작은 value를 가진 object를 선택한다.
3. 새로 선택된 object에 대해 다른 object까지의 reachability distance를 계산하고 2와 비교해서 더 작은 값을 object에 대한 value로 사용한다.
4. 가장 작은 value를 가진 object를 선택하고 4의 과정을 반복한다.
5. Object가 선택된 순서대로 x축에 배치하고 각 object가 선택될 때의 value를 그래프의 y값으로 하여 그래프를 그린다.
   • 맨 처음 선택된 object에 대해서는 infinity의 값을 배정한다.

 

계산 Cost 줄이기

매번 나머지 object들과의 reachability distance를 계산해줘야 한다.

이로 인해 계산 cost가 너무 커진다.

 

계산 cost를 줄이기 위해서 max $\epsilon$을 설정해주고

reachability distance가 이보다 작은 object들에 대해서만 관리해준다.

즉, reachability distance가 $\epsilon$보다 큰 object는 버린다.

 

Practical하게는 충분히 괜찮은 결과를 얻을 수 있다.