DBSCAN은 Density-Based Spatial Clustering of Applications with Noise의 약자입니다. 밀도 기반 클러스터링 알고리즘입니다. 이 알고리즘은 밀도가 충분히 높은 영역을 클러스터로 늘리고 노이즈가 있는 공간 데이터베이스에서 임의 아키텍처의 클러스터를 찾습니다. 밀도 연결 포인트의 최대 그룹으로 클러스터를 나타냅니다.
밀도 기반 클러스터링의 개념에는 다음과 같은 여러 가지 새로운 정의가 포함됩니다. -
-
주어진 개체의 반경 ε 내의 이웃은 개체의 ε이웃으로 알려져 있습니다.
-
객체의 ε-neighborhood가 최소 개수의 객체 MinPts를 포함하는 경우 해당 객체를 핵심 객체라고 합니다.
-
객체 세트 D가 주어지면 p가 q의 ε-이웃 내부에 있고 q가 핵심 객체인 경우 객체 p가 객체 q에서 직접 밀도 도달 가능하다고 말할 수 있습니다.
-
객체 p1의 체인이 있는 경우 객체 그룹 D의 ε 및 MinPts와 관련하여 객체 q에서 밀도 도달 가능 ,..., pn , 여기서 p1 =q 및 pn =p(pi 포함) +1은 pi에서 직접 밀도에 도달할 수 있습니다. ε 및 MinPts 관련, 1 ≤ i ≤ n, pi ε 디.
-
개체 p는 개체 그룹 D의 ε 및 MinPts에 관한 개체 q에 밀도 연결되어 있습니다. 개체 o ε D가 있는 경우 p와 q 모두 ε 및 MinPts에 관한 o에서 밀도 도달 가능합니다.
밀도 도달 가능성은 직접 밀도 도달 가능성의 전이 폐쇄이며 이 연결은 비대칭입니다. 상호 밀도에 도달할 수 있는 핵심 개체만 있습니다. 밀도 연결은 대칭 관계입니다.
밀도 기반 클러스터는 밀도 도달 가능성과 관련하여 최대인 밀도 연결 개체 그룹입니다. 클러스터에 포함되지 않은 각 개체는 노이즈로 처리됩니다.
DBSCAN은 데이터베이스의 모든 포인트의 ε-neighborhood를 테스트하여 클러스터를 검색합니다. 포인트 p의 ε-neighborhood가 MinPts 이상을 포함하는 경우, p를 핵심 객체로 하는 새로운 클러스터가 생성됩니다. DBSCAN은 몇 가지 밀도 도달 가능 클러스터의 병합을 포함할 수 있는 이러한 핵심 객체에서 직접 밀도 도달 가능 객체를 반복적으로 수집합니다. 클러스터에 새 포인트를 삽입할 수 없는 경우 프로세스가 제거됩니다.
공간 인덱스를 사용하는 경우 DBSCAN의 계산 복잡도는 O(nlogn)이며, 여기서 n은 데이터베이스 개체의 수입니다. 따라서 O(n 2 ). 사용자 표현 매개변수 ε 및 MinPts의 적절한 설정으로 알고리즘은 임의 모양의 클러스터를 발견하는 데 효율적입니다.