DBSCAN

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. december 2021; verifikation kræver 1 redigering .

Tæthedsbaseret rumlig clustering af applikationer med støj ( DBSCAN  ) er en dataklyngealgoritme foreslået af Maritin Ester, Hans-Peter Kriegel, Jörg Sander og Xiaowei Su i 1996 [1] . Dette er en tæthedsbaseret klyngealgoritme - givet et sæt af punkter i et eller andet rum, samler algoritmen punkter, der er tæt adskilte (punkter med mange tætte naboer ), og markerer punkter, der er ensomme i områder med lav tæthed (nærmeste hvis naboer er langt væk). DBSCAN er en af ​​de mest brugte klyngealgoritmer og er den hyppigst nævnte i den videnskabelige litteratur [2] .

I 2014 modtog algoritmen prisen "tidstestet" (en pris givet til algoritmer, der har fået betydelig opmærksomhed i teori og praksis) ved den førende konference om data mining, KDD [3] .

Tidlige versioner

I 1972 havde Robert F. Ling allerede publiceret en artikel med titlen The  Theory and Construction of k-Clusters [4] i The Computer Journal med en lignende algoritme med et estimat af beregningsmæssig kompleksitet [4] . DBSCAN har worst-case kompleksitet og formulering af DBSCAN i databaseorienterede termer af rækkeforespørgsler[ clear ] tillader fremskyndelse af indeks. Algoritmerne adskiller sig i deres håndtering af kantpunkter.

Forberedelse

Overvej et sæt punkter i nogle rum, der kræver klyngedannelse. For at udføre DBSCAN-klyngning opdeles punkter i kernepunkter , der kan nås med punkttæthed , og outliers som følger:

Nu, hvis p er et kernepunkt, danner det en klynge sammen med alle punkter (kerne eller ikke-kerne), der kan nås fra det punkt. Hver klynge indeholder mindst ét ​​hovedpunkt. Ikke-essentielle punkter kan være en del af en klynge, men de danner dens "kant", fordi de ikke kan bruges til at nå andre punkter.

Reachability er ikke en symmetrisk relation, fordi der pr. definition ikke kan nås noget punkt fra et ikke-kernepunkt, uanset afstand (så et ikke-kernepunkt kan nås, men intet kan nås fra det). Derfor er det yderligere begreb om tilslutning nødvendig for den formelle definition af området af klynger fundet af DBSCAN-algoritmen. To punkter p og q er tæthedsrelaterede, hvis der er et punkt o , således at både p og q kan nås fra o . Tæthedsforbindelsen er symmetrisk.

Så opfylder klyngen to egenskaber:

  1. Alle punkter i klyngen er parvis forbundet i tæthed.
  2. Hvis et punkt er tæthed, der kan nås fra et punkt i klyngen, hører det også til klyngen.

Algoritme

Den originale forespørgselsbaserede algoritme

DBSCAN kræver, at to parametre angives: og det mindste antal punkter, der skal danne et tæt område [5] (minPts). Algoritmen starter fra et vilkårligt punkt, som endnu ikke er blevet set. Et -nabolag til punktet vælges, og hvis det indeholder nok punkter, dannes en klynge, ellers markeres punktet som støj. Bemærk, at dette punkt senere kan findes i -nabolaget til et andet punkt og inkluderet i en klynge.

Hvis et punkt findes som et tæt punkt i en klynge, er dets -kvarter også en del af denne klynge. Derfor føjes alle punkter, der findes i -nabolaget til dette punkt, til klyngen. Denne proces fortsætter, indtil der findes en tæthedsforbundet klynge. Derefter vælges og behandles et nyt ubesøgt punkt, hvilket fører til opdagelsen af ​​den næste klynge eller støj.

DBSCAN kan bruges med enhver afstandsfunktion [1] [6] (såvel som en lighedsfunktion eller en boolsk tilstand) [7] . Afstandsfunktionen (dist) kan derfor betragtes som en ekstra parameter.

Algoritmen kan skrives i pseudokode som følger [6] :

DBSCAN(DB, distFunc, eps, minPts) { C=0 /* Cluster count */ for hvert punkt P i databasen DB { if label(P) ≠ undefined then continue /* Punktet blev slået op i den indre sløjfe */ Neighbors N=RangeQuery(DB, distFunc, P, eps) / * Find naboer */ hvis |N|< minPts derefter { /* Density check */ label(P)=Støj /* Marker som støj */ fortsæt } C=C + 1 /* næste klyngemærke */ etiket(P)=C /* Etiketstartpunkt */ Frøsæt S=N \ {P} /* Naboer, der skal udvides */ for hvert punkt Q i S { /* Behandl hvert frøpunkt */ hvis label(Q)=Støj så label(Q)=C /* Skift labelstøj til kant */ hvis label(Q) ≠ udefineret så fortsæt /* Er blevet set */ label(Q)= C /* Marker nabo */ Naboer N=RangeQuery(DB, distFunc, Q, eps) /* Find naboer */ hvis |N|≥ minPts så { /* Tjek tæthed */ S=S ∪ N /* Tilføj naboer til sæt rudimentære punkter */ } } } }

hvor RangeQuery kan implementeres ved hjælp af et databaseindeks for bedre ydeevne, eller lineært langsomt opslag kan bruges:

RangeQuery(DB, distFunc, Q, ) { Naboer=tom liste for hvert punkt P i databasen DB { /* Scan alle punkter i databasen */ hvis så { /* Beregn afstand og tjek epsilon */ Neighbors=Naboer ∪ {P} /* Tilføj til resultat */ } } tilbagevenden Naboer }

Abstrakt algoritme

DBSCAN-algoritmen kan dekomponeres i følgende trin [6] :

  1. Vi finder punkter i nærheden af ​​hvert punkt og vælger hovedpunkterne med mere end minPts naboer.
  2. Vi finder de forbundne komponenter af hovedpunkterne på grafen over naboer og ignorerer alle ikke-grundlæggende punkter.
  3. Tildel hver ikke-primær nærmeste klynge, hvis klyngen er -nabo, ellers betragte punktet som støj.

Den naive implementering af algoritmen kræver at huske naboerne i trin 1, så det kræver betydelig hukommelse. Den originale DBSCAN-algoritme kræver ikke dette ved at udføre disse trin et punkt ad gangen.

Sværhedsgrad

DBSCAN besøger hvert databasepunkt, måske flere gange (f.eks. som kandidater til andre klynger). Ud fra driftserfaring er tidskompleksiteten dog hovedsageligt styret af antallet af regionQuery-forespørgsler. DBSCAN udfører præcis én sådan forespørgsel for hvert punkt, og hvis der bruges en indeksstruktur, der fuldender naboskabsforespørgslen i O(log n ) tid, er den samlede gennemsnitlige tidskompleksitet O( n log n ) (hvis parameteren er valgt fornuftigt, så er det sådan, at kun O(log n ) point i gennemsnit returneres). Uden brug af en accelererende indeksstruktur eller på degenererede data (f.eks. når alle punkter er mindre end ), forbliver den værst tænkelige køretid . Afstandsmatrixen af ​​størrelse kan beregnes for at undgå genberegning af afstandene, men dette kræver hukommelse , mens en DBSCAN-implementering uden en afstandsmatrix kun kræver O( n ) -hukommelse.

Fordele

  1. DBSCAN kræver ikke specificering af antallet af klynger i dataene a priori , i modsætning til k-means- metoden .
  2. DBSCAN kan finde vilkårlige formede klynger. Den kan endda finde klynger helt omgivet af (men ikke forbundet med) andre klynger. Takket være MinPts-parameteren reduceres den såkaldte effekt af én forbindelse (forbindelsen af ​​forskellige klynger med en tynd linje af prikker).
  3. DBSCAN har begrebet støj og er tolerant over for outliers .
  4. DBSCAN kræver kun to parametre og er for det meste ufølsom over for rækkefølgen af ​​punkterne i databasen . (Punkter, der er på grænsen til to forskellige klynger, kan dog ende i en anden klynge, hvis rækkefølgen af ​​punkterne ændres, og tildelingen af ​​klynger er unik op til isomorfi.)
  5. DBSCAN er designet til brug med databaser, der kan fremskynde forespørgsler over en række værdier, såsom med et R*-træ .
  6. MinPts og parametre kan indstilles af eksperter på det pågældende område, hvis dataene er godt forstået.

Ulemper

  1. DBSCAN er ikke helt entydig - kantpunkter, der kan nås fra mere end én klynge, kan tilhøre enhver af disse klynger, afhængig af den rækkefølge, punkterne ses i. For de fleste datasæt forekommer disse situationer sjældent og har ringe effekt på resultatet af clustering [6]  - hovedpunkterne og støjen behandles unikt af DBSCAN. DBSCAN* [8] er en variant, der behandler kantpunkter som støj og dermed opnår et helt entydigt resultat, samt en mere konsistent statistisk fortolkning af tæthedsforbundne komponenter.
  2. Kvaliteten af ​​DBSCAN afhænger af afstandsmålingen, der bruges i regionQuery(P,ε)-funktionen. Den mest almindeligt anvendte afstandsmetrik er den euklidiske metrik . Især til clustering af højdimensionelle data , kan denne metrik være næsten ubrugelig på grund af den såkaldte "curse of dimensionality" , som gør det vanskeligt at finde en passende værdi . Denne effekt er imidlertid til stede i enhver anden algoritme baseret på euklidisk afstand.
  3. DBSCAN kan ikke klynge datasæt med store tæthedsforskelle godt, fordi det ikke kan vælge en kombination, der er acceptabel for alle klynger [9] .
  4. Hvis data og skala ikke er godt forstået, kan det være svært at vælge en meningsfuld afstandstærskel .

Se afsnittet nedenfor om udvidelser for algoritmiske ændringer, der omhandler disse problemer.

Parameter Estimation

Enhver datamining-opgave har et parameterproblem. Enhver parameter har en specifik effekt på algoritmen. DBSCAN-algoritmen har brug for parametre og minPts . Parametrene skal defineres af brugeren. Ideelt set bestemmes værdien af ​​det problem, der løses (f.eks. fysiske afstande), og minPts bestemmer derefter den mindste ønskede klyngestørrelse [5] .

OPTICS kan opfattes som en generalisering af DBSCAN, hvor parameteren erstattes af den maksimale værdi, der har størst indflydelse på ydeevnen. MinPts bliver så den mindste klyngestørrelse. Selvom algoritmen er væsentligt enklere i parameterudvælgelsesdomænet end DBSCAN, er dens resultater sværere at bruge, da den normalt producerer hierarkisk klyngedannelse i stedet for den simple partitionering, som DBSCAN producerer.

For nylig reviderede en af ​​forfatterne af DBSCAN DBSCAN og OPTICS og udgav en revideret version af den hierarkiske DBSCAN (HDBSCAN*) [8] , som ikke længere har begrebet kantpunkter. Kun hovedpunkterne danner en klynge.

Udvidelser

Generaliseret DBSCAN (GDBSCAN) [7] [10] er en generalisering af de samme forfattere for vilkårlige booleske udtryk "naboskab" og "densitet". Parametrene og minPts fjernes fra algoritmen og overføres til booleske forhold. På polygonale data kan "naboskab" f.eks. være et hvilket som helst skæringspunkt mellem polygoner, mens tæthedsbetingelsen bruger areal i stedet for træktælling.

Forskellige udvidelser til DBSCAN-algoritmen er blevet foreslået, herunder metoder til parallelisering, parameterestimering og understøttelse af tvivlsomme data. Den grundlæggende idé er blevet udvidet til hierarkisk klyngedannelse ved hjælp af OPTICS- algoritmen . DBSCAN-algoritmen er også blevet brugt som en del af subspace clustering-algoritmer som PreDeCon og SUBCLU . HDBSCAN [8] er en hierarkisk version af DBSCAN, som også er hurtigere end OPTICS, og hvor en flad partition kan udtrækkes fra hierarkiet, bestående af de mest synlige klynger [11] .

Tilgængelighed

Forskellige implementeringer af algoritmen blev fundet med en enorm forskel i ydeevne, den hurtigste fuldførte arbejdet med testdata på 1,4 sekunder, og den langsomste brugte 13803 sekunder [12] . Forskellen kan tilskrives kvaliteten af ​​implementeringen, forskellen i sprog og compilere og brugen af ​​indekser til at fremskynde tingene.

Noter

  1. ↑ 1 2 3 Ester, Kriegel, Sander, Xu, 1996 , s. 226-231.
  2. ↑ Microsoft Academic Search, 2010 .
  3. ↑ Test of Time Award, 2014 .
  4. ↑ 12 Ling , 1972 , s. 326-332.
  5. ↑ 1 2 Mens minPts intuitivt er den mindste klyngestørrelse, kan DBSCAN i nogle tilfælde producere mindre klynger ( Schubert, Sander, Ester, Kriegel, Xu 2017 ). En DBSCAN-klynge består af mindst ét ​​kernepunkt . Da andre punkter kan være kantpunkter på mere end én klynge, er der ingen garanti for, at mindst minPts af punkter er inkluderet i hver klynge.
  6. ↑ 1 2 3 4 5 6 7 8 9 Schubert, Sander, Ester, Kriegel, Xu, 2017 , s. 19:1–19:21.
  7. ↑ 1 2 3 4 Sander, Ester, Kriegel, Xu, 1998 , s. 169-194.
  8. ↑ 1 2 3 Campello, Moulavi, Zimek, Sander, 2015 , s. 1-51.
  9. ↑ Kriegel, Kröger, Sander, Zimek, 2011 , s. 231-240.
  10. ↑ Sander, 1998 .
  11. ↑ Campello, Moulavi, Zimek, Sander, 2013 , s. 344.
  12. ↑ Kriegel, Schubert, Zimek, 2016 , s. 341.

Litteratur