[단단한 머신러닝 - 연습문제 참고 답안]Chapter9 - 클러스터링 9.5

DBSCAN의 기본 정의에 기반해, x가 핵심 대상이라면 x 밀도에 의해 커버되는 모든 샘플로 구성된 집합을 X라 한다. X는 연속성(식 9.39)과 최대성(식 9.40)을 만족한다는 사실을 증명하라.

 

문제 정의에 의해 최대성은 만족.

 

연속성 만족 증명:

x_i를 핵심 대상이라고 가정한다면, x_j는 x_i밀도에 의해 density-reachable이다. 따라서 핵심 대상 x_k가 존재하고, 이는 x_i와 x_k에 direct density reachable이고, x_k와 x_j 의 direct density reachable이다.

x_k는 핵심 대상이기 때문에 x_k와 x_i는 direct density reachable이다. 

또한 direct density reachable 은 density reachable의 부분집합이기 때문에,

x_k와 x_j는 density reachable이다. 그리고 x_k와 xi는 density reachable이고 x_i와 x_j는 density connected 관계이다.

 

참고:

• Direct density reachable : 점 p가 점 q의 반경에 들어오고, 점 q가 코어점일 때, "점 p가 점 q로부터 직접적으로 밀도(기반)-도달가능한 관계에 있다"고 한다. 반대의 경우는 성립하지 않음.

• Density reachable : 점 p와 점 q 사이에 p1,p2,⋯,pn,p1=q,pn=pp1,p2,⋯,pn,p1=q,pn=p 들이 있고, 점 pi+1pi+1이 점 pipi로 부터 직접적으로 밀도(기반)-도달가능하다면, "점 p는 점 q로부터 밀도(기반)-도달가능한 관계에 있다."고 한다. 

 

 

• Density connected : 만약 두 점 p와 q가 모두 어떤 점 O로 부터 반경 내 MinPts 조건 하에 밀도(기반)-도달가능(density-reachable)하다면 "점 p는 점 q와 반경 내 MinPts 조건 하에 밀도(기반)-연결되었다."고 합니다.
  => (다르게 말하면, p가 O의 친구이고, q도 O의 친구이면, p와 q는 친구 O를 통해 서로 연결되었다고 보면 된다.)

 

설명 출처:

https://syj9700.tistory.com/40#:~:text=Direct%20density%20reachable%20%3A%20%EC%A0%90%20p,%EA%B4%80%EA%B3%84%EC%97%90%20%EC%9E%88%EB%8B%A4%22%EA%B3%A0%20%ED%95%9C%EB%8B%A4.