Dbscan

DBSCAN ( Density-Based Spatial Clustering of Applications with Noise ) este o metodă de clusterizare propusă în 1996 de Martin Ester, Hans-Peter Kriegel, Jörg Sander și Xiaowei Xu. Se bazează pe densitate deoarece conectează regiuni de puncte cu densitate suficient de mare. DBSCAN este algoritmul cel mai frecvent utilizat și este, de asemenea, cel mai citat în literatura științifică.

Ideea fundamentală

Punctul A și celelalte puncte roșii sunt puncte centrale . Punctele B și C sunt accesibile din densitate de la A și, prin urmare, fiind conectate la densitate, aparțin aceluiași cluster. Punctul N este un punct zgomotos, deoarece nu este nici un punct central , nici nu este accesibil densității. (MinPts = 3 sau MinPts = 4)

DBSCAN utilizează o definiție de cluster bazată pe noțiunea de accesibilitate a densității . Un punct $q$ ${\ displaystyle q}$ $q$ este direct accesibil dintr-un punct $p$ ${\ displaystyle p}$ $p$ dacă distanța lor este mai mică decât una atribuită $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ (adică face parte din al său $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ -închide) și dacă $p$ ${\ displaystyle p}$ $p$ atunci este înconjurat de un număr suficient de puncte $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ pot fi considerate parte a unui cluster. Ideea $q$ ${\ displaystyle q}$ $q$ este accesibil din densitate din $p$ ${\ displaystyle p}$ $p$ dacă există o succesiune $p_{1},\ldots ,p_{n}$ ${\ displaystyle p_ {1}, \ ldots, p_ {n}}$ ${\ displaystyle p_ {1}, \ ldots, p_ {n}}$ de puncte cu $p_{1}=p$ ${\ displaystyle p_ {1} = p}$ ${\ displaystyle p_ {1} = p}$ Și $p_{n}=q$ ${\ displaystyle p_ {n} = q}$ ${\ displaystyle p_ {n} = q}$ unde fiecare $p_{i+1}$ ${\ displaystyle p_ {i + 1}}$ ${\ displaystyle p_ {i + 1}}$ este accesibil densității direct din $p_{i}$ ${\ displaystyle p_ {i}}$ $p_ {i}$ . Rețineți că relația densitate-accesibilă nu este simetrică din moment ce $q$ ${\ displaystyle q}$ $q$ ar putea fi localizat la periferia clusterului, având un număr insuficient de vecini pentru a-l considera un element autentic al clusterului. În consecință, noțiunea conectată la densitate devine: colon $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ sunt conectate la densitate dacă există un punct $sau$ ${\ displaystyle o}$ $sau$ astfel încât este $sau$ ${\ displaystyle o}$ $sau$ Și $p$ ${\ displaystyle p}$ $p$ este $sau$ ${\ displaystyle o}$ $sau$ Și $q$ ${\ displaystyle q}$ $q$ sunt accesibile la densitate.

Un cluster, care este un subset al punctelor bazei de date, îndeplinește două proprietăți:

Toate punctele din cluster sunt conectate reciproc la densitate.
Dacă un punct este dens-conectat la un alt punct din cluster, acesta face parte, de asemenea, din cluster.

Algoritm

DBSCAN are nevoie de doi parametri: $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ (eps) și numărul minim de puncte necesare pentru a forma un cluster (minPts). Începem cu un loc aleatoriu care nu a fost încă vizitat. Al lui este calculat $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ -închide și dacă conține suficiente puncte se creează un nou cluster. Dacă nu este cazul, punctul este etichetat ca zgomot și poate fi găsit ulterior într-un $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ - suficient de mare aproape de un punct diferit atunci când vă alăturați unui cluster.

Dacă un punct este asociat cu un cluster, de asemenea, punctele sale $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ -închide fac parte din cluster. În consecință, toate punctele găsite în interiorul său $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ -Închidere sunt adăugate la cluster, la fel ca și ale lor $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ - Vino mai aproape. Acest proces continuă până la finalizarea clusterului. Procesul continuă până când toate punctele au fost vizitate.

Pseudo cod

 DBSCAN (D, eps, MinPts)
   C = 0
   Pentru fiecare punct P care nu a fost vizitat în setul de date D
      marchează P ca vizitat
      N = getVicini (P, eps)
      dacă dimensiuneaOf (N) <MinPts
         marchează P ca Zgomot
      in caz contrar
         C = următorul cluster
         expandCluster (P, N, C, eps, MinPts)

expandCluster (P, N, C, eps, MinPts)
   adăugați P la clusterul C.
   pentru fiecare punct P 'din N 
      dacă P 'nu a fost vizitat
         marchează P 'ca vizitat
         N '= getVicini (P', eps)
         dacă sizeOf (N ')> = MinPts
            N = N alăturat cu N '
      dacă P 'nu este încă membru al unui cluster
         adăugați P 'la clusterul C

Complexitate

DBSCAN vizitează fiecare punct al bazei de date, chiar de mai multe ori în cazul punctelor care sunt candidați pentru diferite clustere. Cu toate acestea, pentru considerații practice, complexitatea temporală este în mare parte guvernată de numărul de invocații către getVicini, cu referire la pseudo-codul de mai sus. DBSCAN efectuează exact o invocație pentru fiecare punct și dacă este utilizată o structură indexată, efectuează o interogare de vecinătate în $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ , se obține un timp total de execuție egal cu $O(n\cdot \log n)$ ${\ displaystyle O (n \ cdot \ log n)}$ ${\ displaystyle O (n \ cdot \ log n)}$ . Fără utilizarea structurilor de index, timpul de execuție este egal cu $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ . Adesea matricea dimensiunii se distanțează $(n^{2}-n)/2$ ${\ displaystyle (n ^ {2} -n) / 2}$ ${\ displaystyle (n ^ {2} -n) / 2}$ este creat pentru a evita recalcularea distanțelor prin reducerea timpului de procesare în detrimentul memoriei utilizate egale cu $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ .

Beneficii

DBSCAN are următoarele avantaje:

nu necesită cunoașterea numărului de clustere a priori, spre deosebire de algoritmul K-means ;
poate găsi grupuri de forme arbitrare. De asemenea, poate găsi un cluster complet înconjurat de un cluster diferit la care nu este conectat (dat fiind parametrul MinPts, așa-numitul efect de legătură simplă, diferite clustere conectate printr-o linie subțire de puncte, este redus);
posedă noțiunea de zgomot;
necesită doar doi parametri și este în mare parte insensibilă la ordinea punctelor din baza de date: doar punctele plasate pe arc între două clustere diferite își pot schimba calitatea de membru dacă ordinea punctelor este schimbată în timp ce atribuirea la clustere este unică numai pe izomorfisme.

Dezavantaje

Calitatea clusterizării generate de DBSCAN depinde de măsurarea distanței sale care poate fi atribuită funcției getVicini (P, epsilon). Cea mai comună măsură utilizată este distanța euclidiană . În special pentru datele de înaltă dimensiune , această măsură a distanței devine aproape inutilă, atât de mult încât este numită „ Blestemul dimensionalității ”; de fapt devine dificil să găsești o valoare adecvată pentru epsilon. Cu toate acestea, acest efect este prezent și în alți algoritmi euclidieni bazați pe distanță.
DBSCAN nu poate clasifica seturile de date cu diferențe mari în densități, deoarece combinația minPts-epsilon nu poate fi aleasă în mod corespunzător pentru toate clusterele.

Consultați secțiunea de mai jos despre extensiile de modificare algoritmică care gestionează aceste caracteristici. ^{[ Neclar ]}

Cea mai apropiată detectare a cartierului

Cel mai apropiat vecinătate este detectat în funcția getVicini (P, epsilon). Pentru fiecare punct P, se determină toate celelalte puncte care se află în intervalul epsilon, pe baza funcției de distanță utilizate în algoritm. Analiza necesită calcularea unei matrici de distanță pentru întregul set de date. Generarea matricei la distanță are o complexitate de $O((n^{2}-n)/2)$ ${\ displaystyle O ((n ^ {2} -n) / 2)}$ ${\ displaystyle O ((n ^ {2} -n) / 2)}$ întrucât este nevoie doar de o matrice triunghiulară superioară. În matricea distanțelor, vecinătatea cea mai apropiată poate fi calculată prin selectarea tuplului care are ca valori minimul funcțiilor de pe rând și coloană. Cercetările au determinat detectarea cartierelor, în bazele de date tradiționale, pentru a îmbunătăți viteza. Acestea din urmă rezolvă problema utilizând indici special concepuți pentru acest tip de aplicație.

Estimarea parametrilor

Fiecare proces de extragere a datelor are problema parametrilor. Fiecare parametru afectează algoritmul într-un mod specific. Pentru DBSCAN sunt necesari parametrii epsilon și MinPnts. Parametrii trebuie specificați de utilizator, deoarece fiecare set de date necesită parametri diferiți. O valoare inițială pentru $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ poate fi determinat ca un grafic de distanță k . Conform regulilor generale, $k$ ${\ displaystyle k}$ $k$ poate fi derivat din numărul de dimensiuni din setul de date $D.$ ${\ displaystyle D}$ $D.$ ca $k=|D|+1$ ${\ displaystyle k = | D | +1}$ ${\ displaystyle k = | D | +1}$ . Cu toate acestea, valorile mai mari sunt de obicei mai bune pentru seturile de date zgomotoase.

Chiar dacă această estimare a parametrilor returnează un set suficient de parametri, clasificarea rezultată se poate dovedi a fi diferită de ceea ce vă așteptați, astfel că căutarea a efectuat optimizarea incrementală a parametrilor pe anumite valori.

Alte

Pentru fiecare obiect se găsesc vecinii care se încadrează pe o rază dată ca parametru de intrare; dacă numărul acestor vecini este mai mare decât un factor de prag, furnizat și ca intrare în algoritm , atunci aceste puncte fac parte din același cluster ca cel al obiectului observat și în acest caz punctul se numește punct de bază .

La sfârșitul algoritmului pot exista unele puncte care nu aparțin clusterelor catalogate ca zgomot .

Dacă există un lanț de obiecte de traversare (cu constrângerile uzuale) pentru a ajunge la un punct q dintr - un p, atunci q va fi pur și simplu spus să fie urmărite.

Ultimul caz este acela în care se spune că sunt conectate două obiecte „p” și „q”: pentru a fi definit în acest fel, trebuie să existe un al treilea punct o , astfel încât „p” și „q” să fie urmărite.

Portal IT

Portalul de matematică

V · D · M Învățare automată
Probleme	Clasificarea · Regresie · asociere Reguli · Învățare nesupravegheați · Supravegheat de învățare · Reinforcement Learning · învățare profundă
Învățare nesupravegheată	Clustering · clustering Ierarhica · K mijloace · Așteptarea maximizare · DBSCAN · schimbare medie · antagonist generativă rețea (CGAN · cycleGAN VAE-GAN)
Învățare supravegheată	Arborele decizional · Pădure aleatorie · CRF · HMM · KNN · Clasificator bayesian · Rețea neuronală artificială · Regresie liniară · Regresie logistică · PGM · SVM
Consolidarea învățării	Q-learning · SARSA · TD
Reducerea dimensiunii	Analiza factorilor · CCA · ICA · LDA · PCA · Selectați caracteristici · Extracție caracteristici · t-SNE
Rețele neuronale artificiale	Perceptron · RBF · N · FFN · Rețea Hopfield · MLP · RNN ( LSTM ) · RBM · SOM · CNN · TDNN · SNN
Software	Keras · Microsoft Cognitive Toolkit · scikit-learn · TensorFlow · Theano · Torch · Weka
Alte	Algoritm genetic · PSO · Caracteristică