DBSCAN에서 경계 지점을 결정하는 방법은 무엇입니까?

Question

DBSCAN에서 핵심 포인트는 Eps 내에 MinPts 이상을 갖는 것으로 정의됩니다.

그래서 MinPts = 4 경우, 주당 순이익 총 5 점과 점은 확실히 핵심 포인트입니다. Eps에 4 점 (자체 포함)이있는 점은 어떻습니까? 핵심 포인트입니까, 경계 지점입니까?

Answer 1

테두리 포인트 (DBSCAN에서) 클러스터 일부인 점이지만 스스로 (하지 핵심 포인트, 즉 각 클러스터 멤버)를 조밀하지. 후속 알고리즘 HDBSCAN에서

는 경계 지점의 개념을 폐기 하였다.

캄 펠로, J. R. G. B .; Moulavi, D .; 샌더, 제. (2013).
계층 적 밀도 추정에 기반한 밀도 기반 클러스터링. 데이터베이스에서 지식 발견에 17 태평양 아시아 회의의
절차, 컴퓨터 과학 7819. 페이지에서 PAKDD 2013 년 강의 노트. (160) 도이 : 10.1007/978-3-642-37456-2_14

상태 :

우리의 새로운 정의

는 레벨 세트의 연결 구성 요소와 같은 클러스터의 통계적인 해석과 더 일치 밀도 [...] 경계 객체는 기술적으로 레벨 세트에 속하지 않습니다 (예상 밀도가 임계 값 미만 임).

Answer 2

이것은 주로 구현에 따라 다릅니다. 가장 좋은 방법은 직접 구현과 함께 플레이하는 것입니다. 일본어 DBSCAN ¹ 논문에서

은 핵심 포인트 조건 N_Eps 자체 N_Eps에서 제외되는 특정 데이터 포인트의 엡실론 동네 N_Eps> = MinPts로 주어진다. MinPts = 4 N_Eps = 3 (말 또는 4 자체 포함) 경우 예를 들어 다음

는

, 그들은 원래 종이에 따라 클러스터를 형성하지 않습니다. 한편 scikit-learn DBSCAN 구현은 다른 방식으로 작동합니다. 즉, 그룹을 형성하기위한 포인트 자체를 계산합니다. 따라서 MinPts = 4 인 경우 클러스터를 형성하려면 총 4 개의 포인트가 필요합니다.

[1] Ester, Martin; 한스 - 피터 크리 겔; Sander, Jörg; Xu, Xiaowei (1996). "노이즈가있는 대규모 공간 데이터베이스에서 클러스터를 검색하기위한 밀도 기반 알고리즘"

[2] http://scikit-learn.org

Answer 3

사실, 원래 종이를 다시 읽었고 정의 1은 핵심 포인트가 자체 eps 부근에 속한 것처럼 보입니다. 그래서 minPts가 4라면, 점은 점들의 이웃에 적어도 3 점이 필요합니다. | 정의 1

공지 사항 그들은 NEPS (P) = {q를 ∈D 말하는 것을 dist (p, q) ≤ Eps}. 그 점이 그것의 eps 이웃에서 제외 되었다면 NEps (p) = {q ∈D | dist (p, q) ≤ Eps and p! = q}. 여기서! =는 "같지 않음"입니다.

이

도 4 http://fogo.dbs.ifi.lmu.de/Publikationen/Papers/OPTICS.pdf

그래서 나는 SciKit 해석이 정확하고 위키 백과 그림 http://en.wikipedia.org/wiki/DBSCAN

에 오해의 소지가 있다고 생각 그림에 자신의 광학 논문에서 DBSCAN의 저자에 의해 강화된다