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를 통해 서로 연결되었다고 보면 된다.)