DBSCAN

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

DBSCAN(Density-based spatial clustering)은 ^[1]1996년 Martin Ester, Hans-Peter Kriegel, Jörg Sander 및 Xiaowei Xu가 제안한 데이터 클러스터링 알고리즘입니다.이것은 밀도 기반의 클러스터링 비파라미터 알고리즘입니다.일부 공간에 일련의 포인트가 주어지면 밀착되어 있는 점(많은 인접 라우터와 함께 점)을 그룹화하여 저밀도 영역(가장 가까운 인접 라우터가 너무 멀리 있는 경우)에 단독으로 존재하는 특이치 점으로 표시합니다.DBSCAN은 가장 일반적인 클러스터링 알고리즘 중 하나이며 과학 ^[2]문헌에서도 가장 많이 인용됩니다.

2014년, 이 알고리즘은 주요 데이터 마이닝 컨퍼런스인 ACM SIGKDD에서 Test of Time Award(^[3]이론과 실무에서 상당한 관심을 받은 알고리즘에 수여되는 상)를 수상했습니다. 2020년^[update] 7월 현재 후속 논문인 "DSCAN Revisited, Revisited:「^[4]DBSCAN을 사용하는 이유와 방법」은, 명망 있는 ACM Transactions on Database Systems(TODS)^[5] 저널에서 가장 많이 다운로드 된 8개의 기사 리스트에 표시됩니다.

역사

1972년, 로버트 F.링은 컴퓨터 저널의 "The The Theory and Construction of k-Clusters"^[6]에 O(n³)^[6]의 런타임 복잡도로 추정되며, DBSCAN의 데이터베이스 지향 범위 쿼리 공식은 인덱스 가속을 가능하게 한다.경계점 처리에서는 알고리즘이 약간 다릅니다.

예비

일부 공간의 점 집합을 군집화할 것으로 간주합니다.「 」는, 어느 점에 관한 네이버의 반경을 지정하는 파라메타로 합니다.DBSCAN 클러스터링을 위해 점은 다음과 같이 핵심점, (밀도) 도달 가능한 점 및 특이치로 분류됩니다.

• 포인트 p는 적어도 minPts 포인트가 그 거리θ(p를 포함한다) 내에 있는 경우 코어 포인트이다.
• 포인트 q가 코어 포인트 p에서 거리 θ 내에 있는 경우 포인트 q는 p에서 직접 도달 가능하다.포인트는 코어 포인트에서 직접 도달할 수 있다고만 합니다.
• p = p 및_n p = q인 경로₁₁ p, ..., p가_n 있는 경우 p에서 포인트q에 도달할 수 있습니다.여기서 각_i+1 p는 p에서_i 직접 도달할 수 있습니다.이는 q를 제외하고 경로상의 초기 포인트와 모든 포인트가 핵심 포인트여야 함을 의미합니다.
• 다른 점에서는 도달할 수 없는 모든 점이 특이치 또는 잡음 점입니다.

이제 p가 핵심 지점인 경우 p에서 도달할 수 있는 모든 지점(코어 또는 비코어)과 함께 클러스터를 형성합니다.각 클러스터에는 적어도1개의 핵심 포인트가 포함되어 있습니다.비핵심 포인트는 클러스터의 일부가 될 수 있지만 더 많은 포인트에 도달하는 데 사용할 수 없기 때문에 해당 "엣지"를 형성합니다.

도달가능성은 대칭관계가 아닙니다.정의상 핵심점만 비핵심점에 도달할 수 있습니다.그 반대는 사실이 아니기 때문에 비코어 포인트는 도달할 수 있지만 거기서 아무것도 도달할 수 없습니다.따라서 DBSCAN에 의해 검출된 클러스터의 범위를 정식으로 정의하려면 연결성에 대한 추가 개념이 필요합니다.p와 q가 모두 o에서 도달 가능한 점o가 있는 경우 2개의 p와 q는 밀도로 연결됩니다.밀도 연결성은 대칭입니다.

클러스터는 다음 두 가지 속성을 충족합니다.

1. 클러스터 내의 모든 점은 서로 밀도로 연결되어 있습니다.
2. 클러스터의 특정 지점에서 밀도에 도달할 수 있는 점은 클러스터의 일부이기도 합니다.

알고리즘.

원본 쿼리 기반 알고리즘

DBSCAN에는 2개의 파라미터가 필요합니다. ( ( eps )및 조밀한^[a] 영역(minPts)을 형성하는 데 필요한 최소 포인트 수.방문하지 않은 임의의 시작점부터 시작합니다.이 점의 --근접이 검색되어 충분한 수의 점이 포함되어 있으면 클러스터가 시작됩니다.그렇지 않으면 점이 노이즈로 라벨이 지정됩니다.이 점은 나중에 충분한 크기의 다른 점의 "환경"에서 발견되어 클러스터의 일부가 될 수 있습니다.

점이 클러스터의 밀도가 높은 부분인 것으로 확인되면 해당 점의 θ-근린도 해당 클러스터의 일부입니다.따라서 γ-근접 내에서 발견된 모든 점이 추가되며, γ-근접도 밀도가 높을 때 자신의 γ-근접도 추가된다.이 프로세스는 밀도 연결 클러스터를 완전히 찾을 때까지 계속됩니다.그런 다음 방문하지 않은 새 지점이 검색 및 처리되어 추가적인 클러스터 또는 노이즈가 발견됩니다.

DBSCAN은 모든 거리^[1][4] 함수(유사성 함수 또는 기타 술어)^[7]와 함께 사용할 수 있습니다.따라서 거리 함수(거리)는 추가 파라미터로 볼 수 있습니다.

알고리즘은 다음과 ^[4]같이 의사 코드로 표현할 수 있습니다.

데이터베이스 DB의 각 지점 P에 대한 DBSCAN(DB, distFunc, eps, minPts) { C : = 0 /* 클러스터 카운터 */ 레이블(P)이 정의되지 않은 경우 계속하십시오. /* 내부 루프 */ N : = RangeQuery(DB, distFunc, P, EPS/* 네이버 N)에서 이전에 처리되었습니다./* 밀도 검사 */ 라벨(P) : = 노이즈 /* 노이즈 */계속} C : = C + 1 /* 다음 클러스터 라벨 */ 라벨(P) : = C /* 라벨 초기점 */ 시드세트 S : = N \ {P}/* S { /*의 각 포인트 Q에 대해 */를 확장할 인접 라우터 라벨(Q) = 노이즈 다음 라벨(Q) := C /* 노이즈를 경계 포인트로 변경 라벨(Q) , 정의되지 않은 경우 /* 이전에 처리된 라벨(예: 경계 포인트) */(Q) :/* 인접 라우터 */ 인접 라우터 N := RangeQuery(DB, distFunc, Q, eps) /* 인접 라우터 찾기 */ N p minPts이면 {/* 밀도 검사(Q가 핵심 지점인 경우) */ S : = S ∪ N /* 시드 집합에 새 인접 라우터 추가 */} } } } } } }

성능 향상을 위해 데이터베이스 인덱스를 사용하거나 느린 선형 검색을 사용하여 RangeQuery를 구현할 수 있습니다.

RangeQuery(DB, distFunc, Q, eps) {Neighbors N : = 데이터베이스 { /* distFunc(Q, P) eps eps eps eps eps dist ilon 、 ilon ilon ilon ilon ilon ilon ilon 、 ilon ilon ilon ilon 、 ilon 、 ilon ilon ilon 、 、 、 、 ilon * * * * * * * * * * * * * * * * * * * * * * * * * * * p * 、 、 、 、 、 、 반환 N }

추상 알고리즘

DBSCAN 알고리즘은 다음 ^[4]단계로 추상화할 수 있습니다.

1. 각 포인트의 '(eps)' 네이버에서 포인트를 찾아 minPts 네이버가 넘는 핵심 포인트를 식별합니다.
2. 네이버 그래프에서 모든 비코어 포인트를 무시하고 코어 포인트의 연결된 컴포넌트를 찾습니다.
3. 클러스터가 '(eps) 네이버인 경우 각 비코어 포인트를 인근 클러스터에 할당하고 그렇지 않은 경우 노이즈에 할당합니다.

이를 단순하게 구현하려면 스텝1에서 네이버를 저장해야 하기 때문에 대용량의 메모리가 필요합니다.원래 DBSCAN 알고리즘에서는 이러한 단계를 한 번에 하나씩 수행하여 이 작업을 수행할 필요가 없습니다.

복잡성

DBSCAN은 데이터베이스의 각 지점을 여러 번 방문합니다(예: 다른 클러스터의 후보).그러나 실제적인 고려를 위해, 시간 복잡성은 대부분 지역 수에 의해 좌우된다.호출을 쿼리합니다.DBSCAN은 각 포인트에 대해 이러한 쿼리를 정확히 1개 실행하며, O(log n)에서 네이버 쿼리를 실행하는 인덱싱 구조를 사용하면 O(n log n)의 전체 평균 런타임 복잡도를 얻을 수 있다(파라미터 θ가 의미 있는 방법으로 선택된 경우, 즉 평균적으로 O(log n) 포인트만 반환된다).가속 지수 구조를 사용하지 않거나 퇴화된 데이터(예: θ 미만의 거리 내에 있는 모든 지점)에 대해 최악의 경우 실행 시간 복잡도는 O(n²)로 유지됩니다.(n²-n)/2 크기의 거리 매트릭스는 거리 재계산을 피하기 위해 구현될 수 있지만, 이것은 O(n²) 메모리가 필요한 반면, DBSCAN의 비매트릭스 기반 구현에는 O(n) 메모리만 필요합니다.

이점

1. DBSCAN에서는 데이터의 클러스터 수를 k-평균이 아닌 priori로 지정할 필요가 없습니다.
2. DBSCAN은 임의의 모양의 클러스터를 검색할 수 있습니다.완전히 다른 클러스터로 둘러싸인 클러스터(접속되어 있지 않은 클러스터)도 검출할 수 있습니다.MinPts 파라미터에 의해 이른바 싱글링크 효과(가느다란 점 선으로 서로 다른 클러스터가 연결됨)가 감소합니다.
3. DBSCAN에는 노이즈의 개념이 있으며 이상치에 대해 강력합니다.
4. DBSCAN은 2개의 파라미터만 필요로 하며 대부분 데이터베이스 내의 포인트 순서에 민감하지 않습니다.그러나 서로 다른 두 클러스터의 가장자리에 있는 점은 점의 순서가 변경되면 클러스터 멤버쉽을 스왑할 수 있으며 클러스터 할당은 동형사상까지만 고유합니다.
5. DBSCAN은 R* 트리를 사용하는 등 지역 쿼리를 가속화할 수 있는 데이터베이스와 함께 사용하도록 설계되었습니다.
6. minPts 및 can 파라미터는 데이터를 잘 이해하고 있는 경우 도메인 익스퍼트에 의해 설정할 수 있습니다.

단점들

1. DBSCAN은 완전히 확정적인 것은 아닙니다.데이터 처리 순서에 따라 여러 클러스터에서 도달할 수 있는 경계점이 두 클러스터의 일부가 될 수 있습니다.대부분의 데이터 세트와 도메인에서 이러한 상황은 자주 발생하지 않으며 클러스터링 ^[4]결과에 거의 영향을 미치지 않습니다. 핵심 지점과 노이즈 지점 모두에서 DBSCAN은 결정론적입니다.DBSCAN*^[8]은 경계점을 노이즈로 취급하는 변형입니다.이를 통해 완전히 결정론적 결과를 얻을 수 있을 뿐만 아니라 밀도 연결 구성요소의 통계적 해석도 보다 일관되게 이루어집니다.
2. DBSCAN의 품질은 기능 영역에서 사용되는 거리 측정에 따라 달라집니다.쿼리(P, ε)가장 일반적으로 사용되는 거리 측정 기준은 유클리드 거리입니다.특히 고차원 데이터의 경우, 이 메트릭은 소위 "차원의 저주"로 인해 거의 무용지물이 될 수 있기 때문에 making에 대한 적절한 값을 찾기 어렵다.그러나 이 효과는 유클리드 거리에 기초한 다른 알고리즘에서도 나타난다.
3. DBSCAN은 모든 클러스터에 대해 minPts-δ 조합을 적절하게 선택할 수 없기 때문에 밀도의 차이가 큰 데이터 ^[9]세트를 잘 클러스터링할 수 없습니다.
4. 데이터와 척도를 잘 이해하지 못하면 의미 있는 거리 임계값 θ를 선택하는 것이 어려울 수 있습니다.

이러한 문제에 대처하기 위한 알고리즘 변경에 대해서는, 다음의 확장 섹션을 참조해 주세요.

모수 추정

모든 데이터 마이닝 태스크에는 파라미터의 문제가 있습니다.모든 파라미터는 알고리즘에 특정 방법으로 영향을 줍니다.DBSCAN의 경우 파라미터 ' 및 minPts가 필요합니다.매개 변수는 사용자가 지정해야 합니다.이상적인 것은 해결해야 할 문제(예를 들어 물리적인 거리)에 의해 값이 주어지고 minPts는 바람직한 최소 클러스터 ^[a]크기입니다.

• MinPts: 경험적으로 최소 minPts는 데이터 세트 내의 치수 D의 수(minPts + D + 1)에서 도출할 수 있습니다.모든 점이 정의상 핵심점이므로 minPts = 1의 낮은 값은 의미가 없습니다.minPts 22의 경우, 그 결과는 단일 링크 메트릭을 사용한 계층형 클러스터링과 동일하며, 덴드로그램은 높이 ε로 절단됩니다.따라서 minPts를 3개 이상 선택해야 합니다.그러나 일반적으로 노이즈가 있는 데이터 집합에는 값이 클수록 좋으며 유의한 군집이 생성됩니다.경험적으로 minPts = 2·dim을 사용할 ^[7]수 있지만, 매우 큰 데이터, 노이즈가 많은 데이터 또는 ^[4]중복이 많은 데이터의 경우 더 큰 값을 선택해야 할 수 있습니다.
• θ: 다음으로 k-거리 그래프를 사용하여 가장 큰 값부터 가장 작은 ^[4]값까지 k = minPts-1 가장 가까운 이웃까지의 거리를 표시함으로써 θ 값을 선택할 수 있습니다.are의 값이 좋으면 이 그림에서 "팔꿈치"^[1][7][4]가 나타납니다. is를 너무 작게 선택하면 데이터의 많은 부분이 클러스터화되지 않습니다. 반면 ,의 값이 너무 높으면 클러스터가 병합되고 대부분의 개체가 동일한 클러스터 내에 있게 됩니다.일반적으로 θ의 작은 값이 바람직하며,^[4] 경험적으로 서로 이 거리 내에 있는 포인트는 극히 일부만 있어야 한다.또는 Optics 플롯을 사용하여 ,^[4]를 선택할 수도 있지만 Optics 알고리즘 자체를 사용하여 데이터를 클러스터할 수도 있습니다.
• 거리 함수:거리 함수의 선택은 ,의 선택과 밀접하게 연계되어 결과에 큰 영향을 미칩니다.일반적으로 파라미터 can를 선택하기 전에 먼저 데이터 세트에 대한 타당한 유사성 측정을 식별해야 합니다.이 파라미터에 대한 추정치는 없지만 데이터 세트에 대해 거리 함수를 적절하게 선택해야 합니다.예를 들어, 지리 데이터의 경우 대원 거리가 좋은 선택인 경우가 많습니다.

Optics는 DBSCAN의 일반화로서 퍼포먼스에 가장 큰 영향을 미치는 최대값으로 파라미터가 대체되는 것으로 볼 수 있습니다.MinPts는 기본적으로 검색할 최소 클러스터 크기가 됩니다.알고리즘은 DBSCAN보다 파라미터화하기가 훨씬 쉽지만 결과는 DBSCAN이 생성하는 단순한 데이터 파티셔닝 대신 계층형 클러스터링을 생성하기 때문에 조금 더 어렵습니다.

최근 DBSCAN의 원저작자 중 한 명이 DBSCAN과 Optics를 다시 방문하여 더 이상 경계점 개념이 없는 계층형 DBSCAN(HDBSCAN*)^[8]의 개량판을 발표했습니다.대신 핵심점만 클러스터를 형성합니다.

스펙트럼 클러스터링과의 관계

DBSCAN의 스펙트럼 구현은 연결된 그래프 구성 요소(가장자리를 절단하지 ^[10]않은 최적의 클러스터)를 결정하는 사소한 경우 스펙트럼 클러스터링과 관련이 있다.단, O${\displaystyle ({n\mathrm{}}^{}}$ 3$)({displaystyle$ O$(n^{3$까지 계산 부하가 높을 수 있습니다.또한 계산할 고유 벡터의 수를 선택해야 합니다.성능상의 이유로 원래 DBSCAN 알고리즘은 스펙트럼 구현보다 선호된다.

내선번호

Generalized DBSCAN(GDSCAN)^[7][11]은 동일한 작성자가 임의의 "네이버 후드" 및 "밀도" 술어로 일반화한 것입니다." 및 minPts 파라미터는 원래 알고리즘에서 삭제되어 술어로 이동합니다.예를 들어 폴리곤 데이터에서 "근린"은 교차하는 폴리곤일 수 있지만 밀도 술어는 개체 수 대신 폴리곤 영역을 사용합니다.

병렬화 방법, 파라미터 추정 방법 및 불확실한 데이터 지원을 포함하여 DBSCAN 알고리즘에 대한 다양한 확장이 제안되었습니다.기본 개념은 Optics 알고리즘에 의한 계층형 클러스터링으로 확장되었습니다.DBSCAN은 PreDeCon이나 SUBBU와 같은 서브스페이스 클러스터링 알고리즘의 일부로서도 사용됩니다^[8].HDBSCAN은 DBSCAN의 계층 버전으로 Optics보다 고속이며 ^[12]계층에서 가장 두드러진 클러스터로 구성된 플랫 파티션을 추출할 수 있습니다.

유용성

같은 알고리즘의 실장 마다 큰 퍼포먼스의 차이가 있는 것이 판명되었습니다.테스트 데이터 세트의 가장 빠른 것은 1.4초,^[13] 가장 느린 것은 13803초입니다.이러한 차이는 구현 품질, 언어 및 컴파일러의 차이, 가속을 위한 인덱스 사용에 기인할 수 있습니다.

• Apache Commons Math는 2차 시간으로 실행되는 알고리즘의 Java 구현을 포함합니다.
• ELKI는 DBSCAN 및 GDBSCAN 및 기타 변형 구현 기능을 제공합니다.이 구현은 서브 4차 런타임에 다양한 인덱스 구조를 사용할 수 있으며 임의 거리 함수 및 임의 데이터 유형을 지원하지만 소규모 데이터 세트에 대한 낮은 수준의 최적화된(및 전문화된) 구현에 의해 능가할 수 있습니다.
• MATLAB은 릴리스 R2019a 이후 "통계 및 기계 학습 도구 상자"에 DBSCAN을 구현했습니다.
• mlpack에는 듀얼 트리 범위 검색 기술로 가속화된 DBSCAN 구현이 포함되어 있습니다.
• Post GIS에는 ST_ClusterDB가 포함되어 있습니다.SCAN – R-tree 인덱스를 사용하는 DBSCAN의 2D 구현입니다.점, 선문자열, 폴리곤 등 모든 지오메트리 유형이 지원됩니다.
• R에는 dbscan 및 fpc 패키지에 DBSCAN 구현이 포함되어 있습니다.두 패키지 모두 거리 행렬을 통해 임의 거리 함수를 지원합니다.패키지 fpc는 인덱스를 지원하지 않으며(따라서 2차 런타임과 메모리 복잡성이 있음), R 인터프리터 때문에 다소 느립니다.패키지 dbscan은 k-d 트리(유클리드 거리 전용)를 사용한 고속 C++ 구현을 제공하며 DBSCAN*, HDBSCAN*, Optics, OpticsXi 및 기타 관련 메서드의 구현도 포함합니다.
• skikit-learn은 임의 Minkowski 메트릭에 대한 DBSCAN의 Python 구현을 포함합니다. 이 DBSCAN은 k-d 트리와 볼 트리를 사용하여 가속할 수 있지만 최악의 경우 2차 메모리를 사용합니다.skikit-learn에 대한 기여는 HDBSCAN* 알고리즘을 구현합니다.
• 파이클러스터링 라이브러리에는 Optics 알고리즘뿐만 아니라 유클리드 거리 전용 DBSCAN의 Python 및 C++ 구현이 포함되어 있습니다.
• SPMF는 유클리드 거리에 대해서만 k-d 트리를 지원하는 DBSCAN 알고리즘의 구현을 포함한다.
• Weka에는 (최신 버전에서는 옵션 패키지로) 2차 시간 및 선형 메모리에서 실행되는 DBSCAN의 기본 구현이 포함되어 있습니다.

메모들

레퍼런스