DBSCAN

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 11 decembrie 2021; verificarea necesită 1 editare .

Gruparea spațială bazată pe densitate a aplicațiilor cu zgomot ( DBSCAN ) este un algoritm de grupare a datelor propus de Maritin Ester, Hans-Peter Kriegel, Jörg Sander și Xiaowei Su în 1996 [1] . Acesta este un algoritm de grupare bazat pe densitate - având în vedere un set de puncte într-un anumit spațiu, algoritmul grupează puncte care sunt strâns distanțate (puncte cu mulți vecini apropiați ), marcând ca valori aberante punctele care sunt singure în zone cu densitate scăzută. (cel mai apropiat ai cărui vecini sunt departe). DBSCAN este unul dintre algoritmii de clustering cei mai des utilizați și este cel mai frecvent menționat în literatura științifică [2] .

În 2014, algoritmul a primit premiul „time-tested” (un premiu acordat algoritmilor care au primit o atenție semnificativă în teorie și practică) la conferința de conducere privind data mining, KDD [3] .

Versiunile timpurii

În 1972, Robert F. Ling publicase deja un articol intitulat The Theory and Construction of k-Clusters [4] în The Computer Journal cu un algoritm similar cu o estimare a complexității computaționale [4] . DBSCAN are complexitatea în cel mai rău caz și formularea DBSCAN în termeni de interogări de interval orientați către baze de date $O(n^{3})$ $O(n^{2})$ [ clear ] permite accelerarea prin index. Algoritmii diferă în ceea ce privește gestionarea punctelor de margine.

Pregătire

Luați în considerare un set de puncte dintr-un anumit spațiu care necesită grupare. Pentru a realiza gruparea DBSCAN, punctele sunt împărțite în puncte de bază , accesibile prin densitatea punctelor și valori aberante , după cum urmează:

Un punct p este un punct principal dacă cel puțin minPți de puncte sunt la o distanță care nu depășește ( este raza maximă de vecinătate de la p ) până la acesta (inclusiv punctul p însuși ). Se spune că aceste puncte sunt accesibile direct din p . $\epsilon$ $\epsilon$
Un punct q este direct accesibil de la p dacă q se află la o distanță nu mai mare decât p de p și p trebuie să fie punctul de bază. $\epsilon$
Un punct A q este accesibil de la p dacă există o cale cu și , de unde fiecare punct este accesibil direct (toate punctele de pe cale trebuie să fie primare cu excepția q ). $p_{1},\dots,p_{n)$ $p_{1}=p$ $p_{n}=q$ $p_{{i+1}}$ $p_{i}$
Toate punctele care nu pot fi atinse din punctele centrale sunt considerate valori aberante .

Acum, dacă p este un punct central, atunci formează un grup împreună cu toate punctele (nucleu sau non-core) accesibile din acel punct. Fiecare grup conține cel puțin un punct principal. Punctele neesențiale pot face parte dintr-un cluster, dar formează „marginea” acestuia, deoarece nu pot fi folosite pentru a ajunge la alte puncte.

Atingerea nu este o relație simetrică deoarece, prin definiție, niciun punct nu poate fi atins dintr-un punct non-nucleu, indiferent de distanță (deci un punct non-nucleu poate fi atins, dar nu se poate ajunge la nimic din el). Prin urmare, conceptul suplimentar de conectivitate este necesar pentru definirea formală a zonei clusterelor găsite de algoritmul DBSCAN. Două puncte p și q sunt legate de densitate dacă există un punct o astfel încât atât p cât și q sunt accesibile de la o . Conectivitatea densității este simetrică.

Atunci clusterul satisface două proprietăți:

Toate punctele din cluster sunt conectate perechi ca densitate.
Dacă un punct are densitate accesibilă dintr-un punct din cluster, acesta aparține și clusterului.

Algoritm

Algoritmul original bazat pe interogări

DBSCAN necesită specificarea a doi parametri: și numărul minim de puncte care trebuie să formeze o regiune densă [5] (minPts). Algoritmul pornește dintr-un punct arbitrar care nu a fost încă vizualizat. Se alege o vecinătate a punctului și, dacă conține suficiente puncte, se formează un cluster, în caz contrar punctul este marcat ca zgomot. Rețineți că acest punct poate fi găsit mai târziu în vecinătatea altui punct și inclus într-un grup. $\epsilon$ $\epsilon$ $\epsilon$

Dacă un punct este găsit ca punct dens al unui cluster, vecinătatea sa este, de asemenea, parte a acestui cluster. Prin urmare, toate punctele găsite în - vecinătatea acestui punct sunt adăugate la cluster. Acest proces continuă până când este găsit un cluster conectat la densitate. Apoi este selectat și procesat un nou punct nevizitat, ceea ce duce la descoperirea următorului cluster sau zgomot. $\epsilon$ $\epsilon$

DBSCAN poate fi folosit cu orice funcție de distanță [1] [6] (precum o funcție de similaritate sau o condiție booleană) [7] . Funcția distanță (dist) poate fi deci considerată un parametru suplimentar.

Algoritmul poate fi scris în pseudocod după cum urmează [6] :

DBSCAN(DB, distFunc, eps, minPts) { C=0 /* Număr cluster */ pentru fiecare punct P din baza de date DB { dacă label(P) ≠ nedefinit , atunci continua /* Punctul a fost căutat în bucla interioară */ Neighbors N=RangeQuery(DB, distFunc, P, eps) / * Găsiți vecini */ if |N|< minPts then { /* Verificare densitate */ label(P)=Zgomot /* Marcați ca zgomot */ continua } C=C + 1 /* următoarea etichetă a grupului */ label(P)=C /* Etichetă punct de început */ Seed semințe S=N \ {P} /* Vecinii de extins */ pentru fiecare punct Q din S { /* Tratați fiecare punct de însămânțare */ dacă eticheta(Q)=Zgomot , atunci eticheta(Q)=C /* Schimbați eticheta Zgomot în Edge */ dacă eticheta(Q) ≠ nedefinită apoi continua /* A fost vizualizată */ eticheta(Q)= C /* Marcați vecinul */ Neighbors N=RangeQuery(DB, distFunc, Q, eps) /* Găsiți vecini */ dacă |N|≥ minPts , atunci { /* Verificați densitatea */ S=S ∪ N /* Adăugați vecini la stabiliți puncte rudimentare */ } } } }

unde RangeQuery poate fi implementat folosind un index al bazei de date pentru o performanță mai bună sau poate fi utilizată o căutare liniară lentă:

RangeQuery(DB, distFunc, Q, ) {

\epsilon

Vecini=lista goală pentru fiecare punct P din baza de date DB { /* Scanați toate punctele din baza de date */ if then { /* Calculați distanța și verificați epsilon */ Neighbors=Vecini ∪ {P} /* Adaugă la rezultat */

distFunc(Q,P)\leqslant \epsilon

} } se intoarce Vecinii }

Algoritm abstract

Algoritmul DBSCAN poate fi descompus în următorii pași [6] :

Găsim puncte în vecinătatea fiecărui punct și selectăm punctele principale cu mai mult de minPts vecini. $\epsilon$
Găsim componentele conexe ale punctelor principale pe graficul vecinilor, ignorând toate punctele care nu sunt de bază.
Atribuiți fiecare cluster cel mai apropiat nonprimar dacă clusterul este -neighbor, altfel considerați punctul ca zgomot. $\epsilon$

Implementarea naivă a algoritmului necesită memorarea vecinilor în pasul 1, deci necesită memorie semnificativă. Algoritmul DBSCAN original nu necesită acest lucru, făcând acești pași câte un punct.

Dificultate

DBSCAN vizitează fiecare punct al bazei de date, poate de mai multe ori (de exemplu, ca candidați pentru alte clustere). Cu toate acestea, din experiența operațională, complexitatea timpului este guvernată în principal de numărul de interogări regionQuery. DBSCAN execută exact o astfel de interogare pentru fiecare punct, iar dacă se utilizează o structură de index care completează interogarea de vecinătate în timp O(log n ) , complexitatea generală a timpului mediu este O( n log n ) (dacă parametrul este ales în mod sensibil, atunci este astfel încât numai O(log n ) puncte sunt returnate în medie). Fără utilizarea unei structuri de index accelerat sau pe date degenerate (de exemplu, când toate punctele sunt mai mici de ), timpul de rulare în cel mai rău caz rămâne . Matricea distanțelor de dimensiune poate fi calculată pentru a evita recalcularea distanțelor, dar aceasta necesită memorie , în timp ce o implementare DBSCAN fără o matrice de distanțe necesită doar memorie O( n ) . $\epsilon$ $\epsilon$ $O(n^{2})$ $(n^{2}-n)/2$ $O(n^{2})$

Beneficii

DBSCAN nu necesită specificarea numărului de clustere din date a priori , spre deosebire de metoda k-means .
DBSCAN poate găsi clustere de formă arbitrară. Poate găsi chiar și clustere complet înconjurate de (dar nu conectate la) alte clustere. Datorită parametrului MinPts, așa-numitul efect al unei conexiuni (conexiunea diferitelor grupuri cu o linie subțire de puncte) este redus.
DBSCAN are noțiunea de zgomot și este tolerant la valori aberante .
DBSCAN necesită doar doi parametri și este în mare parte insensibil la ordinea punctelor din baza de date . (Cu toate acestea, punctele care se află la granița a două grupuri diferite pot ajunge într-un alt grup dacă ordinea punctelor este schimbată, iar atribuirea clusterelor este unică până la izomorfism.)
DBSCAN este conceput pentru a fi utilizat cu baze de date care pot accelera interogările pe un interval de valori, cum ar fi cu un arbore R* .
MinP-urile și parametrii pot fi setați de experți în domeniul în cauză dacă datele sunt bine înțelese. $\epsilon$

Dezavantaje

DBSCAN nu este complet neechivoc - punctele de margine care pot fi atinse de la mai mult de un cluster pot aparține oricăruia dintre aceste clustere, în funcție de ordinea în care sunt vizualizate punctele. Pentru cele mai multe seturi de date, aceste situații apar rar și au un efect redus asupra rezultatului grupării [6] - punctele principale și zgomotul sunt procesate în mod unic de DBSCAN. DBSCAN* [8] este o variantă care tratează punctele de margine ca zgomot și obține astfel un rezultat complet lipsit de ambiguitate, precum și o interpretare statistică mai consistentă a componentelor conectate la densitate.
Calitatea DBSCAN depinde de măsurarea distanței utilizate în funcția regionQuery(P,ε). Cea mai des folosită metrică de distanță este metrica euclidiană . În special pentru gruparea datelor cu dimensiuni mari , această metrică poate fi aproape inutilă din cauza așa-numitului „blestem al dimensionalității” , ceea ce face dificilă găsirea unei valori adecvate . Acest efect, totuși, este prezent în orice alt algoritm bazat pe distanța euclidiană. $\epsilon$
DBSCAN nu poate grupa bine seturile de date cu diferențe mari de densitate, deoarece nu poate alege o combinație care este acceptabilă pentru toate clusterele [9] . $minPts-\epsilon$
Dacă datele și scara nu sunt bine înțelese, alegerea unui prag de distanță semnificativ poate fi dificilă. $\epsilon$

Consultați secțiunea de mai jos despre extensii pentru modificări algoritmice care se ocupă de aceste probleme.

Estimarea parametrilor

Orice sarcină de extragere a datelor are o problemă de parametri. Orice parametru are un efect specific asupra algoritmului. Algoritmul DBSCAN are nevoie de parametri și minPts . Parametrii trebuie definiți de utilizator. În mod ideal, valoarea este determinată de problema rezolvată (de exemplu, distanțele fizice), iar minPts determină apoi dimensiunea minimă dorită a clusterului [5] . $\epsilon$ $\epsilon$

MinPts : După cum arată experiența, valoarea minimă minPts poate fi obținută din dimensiunea D a setului de date ca . O valoare scăzută a minPts =1 nu are sens, deoarece atunci orice punct va fi un cluster. Pentru , rezultatul va fi același cu gruparea ierarhică cu metrica de conexiune unică cu tăierea dendrogramei la înălțime . Prin urmare, minPts ar trebui să fie de cel puțin 3. Cu toate acestea, pentru seturile de date zgomotoase, valorile mai mari sunt de obicei mai bune și produc clustere mai semnificative. Experiența sugerează că poate fi utilizată o valoare de [7] , dar poate fi necesar să alegeți o valoare mai mare pentru seturi de date mari, pentru date zgomotoase sau pentru date care conțin multe duplicate [6] . $minPts\geqslant D+1$ $minPts\leqslant 2$ $\epsilon$ $minPts=2\cdot dim$
$\epsilon$ : Valoarea poate fi aleasă folosind graficul k-distanță , trasând distanța până la ( ) cel mai apropiat vecin în ordine de la cel mai mare la cel mai mic [6] . Valorile bune sunt cele în care graficul are o „îndoire” [1] [7] [6] - dacă sunt alese prea mici, majoritatea datelor nu vor fi grupate, iar pentru valori prea mari, clusterele se vor îmbina și majoritatea dintre obiecte vor fi în același grup. De obicei, valorile mici sunt de preferat [6] și experiența arată că doar o mică proporție de puncte ar trebui să fie la această distanță unul de celălalt. Alternativ, o diagramă OPTICS poate fi utilizată pentru a selecta [6] , dar apoi algoritmul OPTICS însuși poate fi folosit pentru grupare. $\epsilon$ $k=minPts-1$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$
Funcția de distanță: alegerea funcției de distanță este strâns legată de alegere și are un impact mare asupra rezultatelor. De obicei, este necesar să se determine mai întâi măsuri rezonabile ale similarității unui set de date înainte de a selecta . Nu există estimări pentru acest parametru, dar funcțiile de distanță trebuie alese în funcție de setul de date. De exemplu, pentru datele geografice, distanța cercului mare este adesea o alegere bună. $\epsilon$ $\epsilon$

OPTICA poate fi gândită ca o generalizare a DBSCAN în care parametrul este înlocuit cu valoarea maximă care are cel mai mare impact asupra performanței. MinPts devine apoi dimensiunea minimă a clusterului. Deși algoritmul este substanțial mai simplu în domeniul selecției parametrilor decât DBSCAN, rezultatele sale sunt mai dificil de utilizat, deoarece de obicei produce clustering ierarhic în loc de partiționarea simplă pe care o produce DBSCAN. $\epsilon$

Recent, unul dintre autorii DBSCAN a revizuit DBSCAN și OPTICS și a publicat o versiune revizuită a DBSCAN ierarhic (HDBSCAN*) [8] , care nu mai are conceptul de puncte de margine. Doar punctele principale formează un grup.

Extensii

DBSCAN generalizat (GDBSCAN) [7] [10] este o generalizare a acelorași autori pentru expresiile booleene arbitrare „neighborhood” și „density”. Parametrii și minPts sunt eliminați din algoritm și transferați în condiții booleene. De exemplu, pe datele poligonale, „vecinătatea” poate fi orice intersecție de poligoane, în timp ce condiția de densitate folosește suprafața în loc de numărul de caracteristici. $\epsilon$

Au fost propuse diverse extensii ale algoritmului DBSCAN, inclusiv metode de paralelizare, estimare a parametrilor și suport pentru date discutabile. Ideea de bază a fost extinsă la gruparea ierarhică prin algoritmul OPTICS . Algoritmul DBSCAN a fost folosit și ca parte a algoritmilor de grupare subspațială precum PreDeCon și SUBCLU . HDBSCAN [8] este o versiune ierarhică a DBSCAN, care este, de asemenea, mai rapidă decât OPTICS, și în care o partiție plată poate fi extrasă din ierarhie, constând din cele mai vizibile clustere [11] .

Disponibilitate

S-au găsit diverse implementări ale algoritmului cu o diferență uriașă de performanță, cel mai rapid a finalizat lucrul asupra datelor de testare în 1,4 secunde, iar cel mai lent a petrecut 13803 secunde [12] . Diferența poate fi atribuită calității implementării, diferenței de limbi și compilatoare și utilizării indicilor pentru a accelera lucrurile.

Apache Commons Math conține o implementare Java a unui algoritm care rulează în timp pătratic.
ELKI oferă o implementare a DBSCAN, GDBSCAN și a altor variante. Această implementare poate folosi diferite structuri de index pentru a oferi timp de rulare subquadratic. Funcțiile de distanță arbitrară și tipurile de date arbitrare pot fi utilizate în această implementare, iar accelerarea poate fi obținută prin optimizare la nivel scăzut și folosind metode speciale pe seturi mici de date.
PostGIS include ST_ClusterDBSCAN, o implementare bidimensională a DBSCAN care utilizează un arbore R ca index. Este acceptat orice tip de geometrie, cum ar fi Punct, Linie, Poligon etc.
În limbajul R , pachetul fpc conține DBSCAN cu suport pentru o funcție de distanță arbitrară prin matrice de distanță. Cu toate acestea, implementarea nu acceptă indici (și, prin urmare, are timp de rulare pătratică și complexitate de timp), și trebuie spus că implementarea este lentă datorită utilizării interpretului R. O implementare C ++ mai rapidă folosind arbori kd (doar pentru distanțe euclidiene) este în pachetul R dbscan .
scikit-learn include o implementare Python a DBSCAN pentru metrici Minkowski arbitrare, care poate fi accelerată cu arbori kd și arbori bile , dar care utilizează memoria pătratică în cel mai rău caz. Pachetul suplimentar pentru scikit-learn oferă o implementare a algoritmului HDBSCAN*.
Biblioteca pyclustering include o implementare Python și C++ a DBSCAN numai pentru distanța euclidiană, precum și o implementare a algoritmului OPTICS.
SPMF include o implementare a algoritmului DBSCAN cu suport arbore kd numai pentru distanța euclidiană.
Weka conține (ca pachet opțional în cea mai recentă versiune) o implementare de bază DBSCAN care necesită memorie liniară și rulează în timp patratic.

Note

↑ 1 2 3 Ester, Kriegel, Sander, Xu, 1996 , p. 226–231.
↑ Microsoft Academic Search, 2010 .
↑ Premiul Test of Time, 2014 .
↑ 12 Ling , 1972 , p. 326–332.
↑ 1 2 În timp ce minPts este intuitiv dimensiunea minimă a clusterului, în unele cazuri DBSCAN poate produce clustere mai mici ( Schubert, Sander, Ester, Kriegel, Xu 2017 ). Un cluster DBSCAN este format din cel puțin un punct central . Deoarece alte puncte pot fi puncte de margine pentru mai mult de un cluster, nu există nicio garanție că cel puțin minPți de puncte sunt incluse în fiecare cluster.
↑ 1 2 3 4 5 6 7 8 9 Schubert, Sander, Ester, Kriegel, Xu, 2017 , p. 19:1–19:21.
↑ 1 2 3 4 Sander, Ester, Kriegel, Xu, 1998 , p. 169–194.
↑ 1 2 3 Campello, Moulavi, Zimek, Sander, 2015 , p. 1–51.
↑ Kriegel, Kröger, Sander, Zimek, 2011 , p. 231–240.
↑ Sander, 1998 .
↑ Campello, Moulavi, Zimek, Sander, 2013 , p. 344.
↑ Kriegel, Schubert, Zimek, 2016 , p. 341.

Literatură

Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. Un algoritm bazat pe densitate pentru descoperirea clusterelor în baze de date spațiale mari cu zgomot // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) / Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. - AAAI Press , 1996. - S. 226-231 . — ISBN 1-57735-004-9 .
Jörg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu. Clustering bazat pe densitate în baze de date spațiale: algoritmul GDBSCAN și aplicațiile sale // Data Mining și Knowledge Discovery. - Berlin: Springer-Verlag , 1998. - Vol. 2 , nr. 2 . — S. 169–194 . - doi : 10.1023/A:1009745219419 .

Căutare academică Microsoft . - 2010. Arhivat la 21 aprilie 2010. Cele mai citate articole de data mining de către Microsoft academic search; DBSCAN are 24 de poziții.
Premiul SIGKDD Test of Time 2014 . — ACM SIGKDD, 2014.
Ling RF Despre teoria și construcția k-clusterelor // The Computer Journal. - 1972. - T. 15 , nr. 4 . — ISSN 0010-4620 . - doi : 10.1093/comjnl/15.4.326 .
Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, Xiaowei Xu. DBSCAN revizuit, revizuit: de ce și cum ar trebui (încă) să utilizați DBSCAN // ACM Trans. Database Syst.. - 2017. - iulie ( vol. 42 , numărul 3 ). — ISSN 0362-5915 . - doi : 10.1145/3068335 .
Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek. Clustering bazat pe densitate // WIREs Data Mining și Knowledge Discovery. - 2011. - Vol. 1 , numărul. 3 . — S. 231–240 . - doi : 10.1002/widm.30 .
Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, Jörg Sander. Estimări de densitate ierarhică pentru gruparea datelor, vizualizarea și detectarea valorii aberante // Tranzacții ACM privind descoperirea cunoștințelor din date. - 2015. - T. 10 , nr. 1 . — ISSN 1556-4681 . - doi : 10.1145/2733381 .
George Sander. Clustering generalizat bazat pe densitate pentru extragerea datelor spațiale. - Herbert Utz Verlag, 1998. - ISBN 3-89675-469-6 .
Campello RJGB, Moulavi D., Zimek A., Sander J. Un cadru pentru extracția optimă semi-supravegheată și nesupravegheată a clusterelor din ierarhii // Data Mining and Knowledge Discovery. - 2013. - T. 27 , nr. 3 . - doi : 10.1007/s10618-013-0311-4 .
Hans-Peter Kriegel, Erich Schubert, Arthur Zimek. Arta (neagră) a evaluării timpului de execuție: comparăm algoritmi sau implementări? // Sisteme de cunoștințe și informații. - 2016. - T. 52 , nr. 2 . - S. 341 . — ISSN 0219-1377 . - doi : 10.1007/s10115-016-1004-2 .

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbarea medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG