DBSCAN

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. december 11-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az alkalmazások sűrűség alapú térbeli klaszterezése zajjal ( DBSCAN  ) egy adatfürtöző algoritmus , amelyet Maritin Ester, Hans-Peter Kriegel, Jörg Sander és Xiaowei Su javasolt 1996-ban [ 1] . Ez egy sűrűség alapú klaszterező algoritmus – adott térben egy ponthalmaz, az algoritmus összegyűjti azokat a pontokat, amelyek közel vannak egymáshoz (sok közeli szomszédos pontok ), kiugró pontokként megjelölve azokat a pontokat, amelyek magányosak az alacsony sűrűségű területeken (amelyeknek a legközelebbi szomszédai messze vannak). A DBSCAN az egyik leggyakrabban használt klaszterező algoritmus, és a tudományos irodalomban a leggyakrabban említett [2] .

Az algoritmus 2014-ben megkapta az "időtesztelt" díjat (az elméletben és a gyakorlatban jelentős figyelmet kapott algoritmusok díját) a vezető adatbányászati ​​konferencián, a KDD-n [3] .

Korai verziók

1972-ben Robert F. Ling már publikált egy cikket The  Theory and Construction of k-Clusters [4] címmel a The Computer Journal folyóiratban , hasonló algoritmussal, a számítási komplexitás becslésével [4] . A DBSCAN a legrosszabb eset bonyolultságával rendelkezik , és a DBSCAN megfogalmazása adatbázis-orientált kifejezésekkel rendelkezik a tartománylekérdezéseknél[ clear ] lehetővé teszi az index szerinti gyorsítást. Az algoritmusok különböznek az élpontok kezelésében.

Előkészítés

Tekintsünk egy olyan ponthalmazt valamilyen térben, amely klaszterezést igényel. A DBSCAN-fürtözés végrehajtásához a pontokat alappontokra osztják, amelyek pontsűrűség szerint érhetők el , és a kiugró értékeket az alábbiak szerint:

Most, ha p egy magpont, akkor egy klasztert alkot az összes ponttal (mag- vagy nem maggal), amely ebből a pontból elérhető. Minden klaszter legalább egy fő pontot tartalmaz. A nem esszenciális pontok lehetnek egy klaszter részei, de ezek képezik annak "élét", mert nem használhatók más pontok elérésére.

Az elérhetőség nem szimmetrikus reláció, mert definíció szerint nem magpontból távolságtól függetlenül egyetlen pont sem érhető el (tehát egy magon kívüli pont is elérhető, de onnan semmi sem érhető el). Ezért a DBSCAN algoritmus által talált klaszterek területének formális meghatározásához szükség van a további kapcsolódási koncepcióra. Két p és q pont sűrűségfüggő, ha van olyan o pont , amelynél p és q is elérhető o -ból . A sűrűség kapcsolat szimmetrikus .

Ekkor a klaszter két tulajdonságot teljesít:

  1. A klaszter összes pontja páronként sűrűn kapcsolódik.
  2. Ha egy pont a klaszter valamely pontjáról elérhető sűrűségű, akkor az is a klaszterhez tartozik.

Algoritmus

Az eredeti lekérdezés alapú algoritmus

A DBSCAN két paraméter megadását igényli: és azon pontok minimális számát, amelyeknek sűrű régiót kell alkotniuk [5] (minPts). Az algoritmus egy tetszőleges pontból indul, amelyet még nem tekintettek meg. Kiválasztjuk a pont szomszédságát, és ha az elegendő pontot tartalmaz, akkor egy klaszter jön létre, ellenkező esetben a pont zajként lesz megjelölve . Ne feledje, hogy ez a pont később egy másik pont szomszédságában található, és bekerülhet valamelyik klaszterbe.

Ha egy pontot egy klaszter sűrű pontjaként találunk, akkor a -szomszédsága is ennek a klaszternek a része. Ezért a pont -szomszédságában található összes pont hozzáadódik a fürthöz. Ez a folyamat addig folytatódik, amíg egy sűrűséghez kapcsolódó klasztert nem találunk. Ezután egy új meg nem látogatott pont kerül kiválasztásra és feldolgozásra, ami a következő klaszter vagy zaj felfedezéséhez vezet.

A DBSCAN bármilyen távolságfüggvénnyel használható [1] [6] (valamint hasonlósági függvénnyel vagy logikai feltétellel) [7] . A távolságfüggvény (dist) ezért további paraméternek tekinthető.

Az algoritmus pszeudokódban a következőképpen írható [6] :

DBSCAN(DB, distFunc, eps, minPts) { C=0 /* Klaszterek száma */ minden P ponthoz a DB adatbázisban { if label(P) ≠ undefined then folytatás /* A pontot a belső ciklusban kerestük */ Neighbors N=RangeQuery(DB, distFunc, P, eps) / * Szomszédok keresése */ if |N|< minPts then { /* Sűrűségellenőrzés */ label(P)=Zaj /* Megjelölés zajként */ folytatás } C=C + 1 /* következő fürtcímke */ címke(P)=C /* Címke kezdőpontja */ Magkészlet S=N \ {P} /* Kibontandó szomszédok */ minden egyes Q ponthoz S { /* Az egyes magpontok kezelése */ ha címke(Q)=Zaj , akkor címke(Q)=C /* Zaj címke módosítása Edge-re */ ha címke(Q) ≠ nincs meghatározva , akkor folytassa /* Megtekintve */ címke(Q)= C /* Szomszéd megjelölése */ Szomszédok N=RangeQuery(DB, distFunc, Q, eps) /* Szomszédok keresése */ if |N|≥ minPts then { /* Sűrűség ellenőrzése */ S=S ∪ N /* Szomszédok hozzáadása kezdetleges pontok meghatározása */ } } } }

ahol a RangeQuery megvalósítható adatbázis-index segítségével a jobb teljesítmény érdekében, vagy lineáris lassú keresés használható:

RangeQuery(DB, distFunc, Q, ) { Szomszédok=üres lista minden P ponthoz a DB adatbázisban { /* Az adatbázis összes pontjának vizsgálata */ if then { /* Távolság számítása és epsilon ellenőrzése */ Szomszédok=Szomszédok ∪ {P} /* Hozzáadás az eredményhez */ } } vissza Szomszédok }

Absztrakt algoritmus

A DBSCAN algoritmus a következő lépésekre bontható [6] :

  1. Minden pont közelében pontokat találunk, és kiválasztjuk azokat a fő pontokat, amelyeknek több mint minPts szomszédjuk van.
  2. A főpontok összefüggő összetevőit a szomszédok gráfján találjuk meg, figyelmen kívül hagyva az összes nem alappontot.
  3. Minden nem elsődleges legközelebbi fürt hozzárendelése, ha a fürt -szomszéd, ellenkező esetben tekintse a pontot zajnak.

Az algoritmus naiv megvalósítása megköveteli a szomszédok memorizálását az 1. lépésben, tehát jelentős memóriát igényel. Az eredeti DBSCAN algoritmus ezt nem követeli meg, ha ezeket a lépéseket egyenként hajtja végre.

Nehézség

A DBSCAN minden adatbázispontot felkeres, esetleg többször is (például más fürtök jelöltjeként). A működési tapasztalatok alapján azonban az időbonyolultságot főként a regionQuery lekérdezések száma határozza meg. A DBSCAN pontosan egy ilyen lekérdezést hajt végre minden ponthoz, és ha olyan indexstruktúrát használunk, amely az szomszédsági lekérdezést O(log n ) idő alatt fejezi be , akkor a teljes átlagos időbonyolultság O( n log n ) (ha a paraméter ésszerűen választott, akkor olyan, hogy átlagosan csak O(log n ) pontot adunk vissza). Gyorsuló indexstruktúra használata nélkül vagy degenerált adatokon (például amikor minden pont kisebb, mint ), a legrosszabb eset futási ideje marad . A méret távolságmátrixa kiszámítható a távolságok újraszámításának elkerülése érdekében, de ehhez memória szükséges , míg a távolságmátrix nélküli DBSCAN megvalósítás csak O( n ) memóriát igényel.

Előnyök

  1. A DBSCAN nem követeli meg a klaszterek számának előzetes megadását az adatokban , ellentétben a k-means módszerrel .
  2. A DBSCAN tetszőleges alakú klasztereket találhat. Még olyan klasztereket is találhat, amelyeket teljesen körülvesznek (de nem kapcsolódnak) más klaszterek. A MinPts paraméternek köszönhetően csökken egy kapcsolat úgynevezett hatása (különböző klaszterek összekapcsolása vékony pontvonallal).
  3. A DBSCAN rendelkezik a zaj fogalmával, és tűri a kiugró értékeket .
  4. A DBSCAN csak két paramétert igényel, és többnyire érzéketlen az adatbázisban lévő pontok sorrendjére . (A két különböző klaszter határán lévő pontok azonban egy másik klaszterbe kerülhetnek, ha a pontok sorrendjét megváltoztatjuk, és a klaszterek hozzárendelése az izomorfizmusig egyedi.)
  5. A DBSCAN-t olyan adatbázisokkal való használatra tervezték, amelyek felgyorsíthatják a lekérdezéseket számos értéktartományban, például egy R*-fával .
  6. A minPt-eket és a paramétereket a kérdéses terület szakértői állíthatják be, ha az adatok jól értelmezhetők.

Hátrányok

  1. A DBSCAN nem teljesen egyértelmű – az egynél több klaszterből elérhető élpontok bármelyik fürthöz tartozhatnak, attól függően, hogy a pontokat milyen sorrendben nézzük. A legtöbb adatkészlet esetében ezek a helyzetek ritkán fordulnak elő, és csekély hatásuk van a klaszterezés eredményére [6]  – a fő pontokat és a zajt a DBSCAN egyedileg dolgozza fel. A DBSCAN* [8] egy olyan változat, amely az élpontokat zajként kezeli, és így teljesen egyértelmű eredményt, valamint a sűrűséghez kapcsolódó komponensek konzisztensebb statisztikai értelmezését éri el.
  2. A DBSCAN minősége a regionQuery(P,ε) függvényben használt távolságméréstől függ. A leggyakrabban használt távolságmérő az euklideszi metrika . Különösen nagy dimenziós adatok klaszterezésekor ez a mérőszám szinte használhatatlan lehet az úgynevezett "dimenziós átka" miatt, ami megnehezíti a megfelelő érték megtalálását . Ez a hatás azonban minden más euklideszi távolságon alapuló algoritmusban jelen van.
  3. A DBSCAN nem tudja jól klaszterezni a nagy sűrűségkülönbséggel rendelkező adatkészleteket, mert nem tud olyan kombinációt választani, amely minden klaszter számára elfogadható [9] .
  4. Ha az adatokat és a léptéket nem értjük jól, nehéz lehet értelmes távolsági küszöböt választani.

Tekintse meg az alábbi szakaszt a bővítményekről az ezekkel a problémákkal foglalkozó algoritmikus módosításokról.

Paraméterbecslés

Minden adatbányászati ​​feladatnak paraméterproblémája van. Bármely paraméter specifikus hatással van az algoritmusra. A DBSCAN algoritmushoz paraméterek és minPts szükséges . A paramétereket a felhasználónak kell meghatároznia. Ideális esetben az értéket a megoldandó probléma (pl. fizikai távolságok) határozza meg, majd a minPts meghatározza a minimálisan kívánt klaszterméretet [5] .

Az OPTICS a DBSCAN általánosításaként fogható fel, amelyben a paramétert az a maximális érték váltja fel, amely a legnagyobb hatással van a teljesítményre. A MinPts ekkor a minimális fürtméret lesz. Bár az algoritmus a paraméterkiválasztási tartományban lényegesen egyszerűbb, mint a DBSCAN, eredményeit nehezebb használni, mivel általában hierarchikus klaszterezést hoz létre a DBSCAN által előállított egyszerű particionálás helyett.

A közelmúltban a DBSCAN egyik szerzője átdolgozta a DBSCAN-t és az OPTICS-t, és közzétette a hierarchikus DBSCAN (HDBSCAN*) [8] átdolgozott változatát , amely már nem tartalmazza az élpontok fogalmát. Csak a fő pontok alkotnak klasztert.

Kiterjesztések

Az általánosított DBSCAN (GDBSCAN) [7] [10] ugyanazon szerzők általánosítása tetszőleges logikai "környéki" és "sűrűség" kifejezésekre. A paraméterek és a minPts eltávolításra kerülnek az algoritmusból, és átkerülnek logikai feltételekre. Például a sokszögű adatokon a "szomszédság" a sokszögek tetszőleges metszéspontja lehet, míg a sűrűségfeltétel a területet használja a jellemzők száma helyett.

A DBSCAN algoritmus különféle kiterjesztését javasolták, beleértve a párhuzamosítási módszereket, a paraméterbecslést és a megkérdőjelezhető adatok támogatását. Az alapötletet az OPTICS algoritmus kiterjesztette a hierarchikus klaszterezésre . A DBSCAN algoritmust olyan altér klaszterezési algoritmusok részeként is használták, mint a PreDeCon és a SUBCLU . A HDBSCAN [8] a DBSCAN hierarchikus változata, amely az OPTICS-nál is gyorsabb, és amelyben a hierarchiából kivonható egy lapos partíció, amely a legláthatóbb klaszterekből áll [11] .

Elérhetőség

Az algoritmus különféle implementációit óriási teljesítménykülönbséggel találták meg, a leggyorsabbak 1,4 másodperc alatt végezték el a tesztadatokkal kapcsolatos munkát, a leglassabbak pedig 13803 másodpercet töltöttek el [12] . A különbség a megvalósítás minőségének, a nyelvek és fordítók különbségének, valamint az indexek használatának a felgyorsítására vezethető vissza.

Jegyzetek

  1. ↑ 1 2 3 Ester, Kriegel, Sander, Xu, 1996 , p. 226–231.
  2. ↑ Microsoft Academic Search, 2010 .
  3. ↑ Időpróba díj, 2014 .
  4. ↑ 12. Ling , 1972 , p. 326–332.
  5. ↑ 1 2 Míg a minPts intuitív módon a minimális klaszterméret, bizonyos esetekben a DBSCAN kisebb klasztereket is képes előállítani ( Schubert, Sander, Ester, Kriegel, Xu 2017 ). Egy DBSCAN-fürt legalább egy magpontból áll . Mivel más pontok egynél több klaszter élpontjai is lehetnek, nincs garancia arra, hogy minden klaszterben legalább minPts pont szerepel.
  6. ↑ 1 2 3 4 5 6 7 8 9 Schubert, Sander, Ester, Kriegel, Xu, 2017 , p. 19:1–19:21.
  7. ↑ 1 2 3 4 Sander, Ester, Kriegel, Xu, 1998 , p. 169–194.
  8. ↑ 1 2 3 Campello, Moulavi, Zimek, Sander, 2015 , p. 1–51.
  9. ↑ Kriegel, Kröger, Sander, Zimek, 2011 , p. 231–240.
  10. ↑ Sander, 1998 .
  11. ↑ Campello, Moulavi, Zimek, Sander, 2013 , p. 344.
  12. ↑ Kriegel, Schubert, Zimek, 2016 , p. 341.

Irodalom