DBSCAN

A Dbscan (alkalmazások sűrűségalapú térbeli klaszterezése zajjal ) egy algoritmus az adatok felosztására, amelyet 1996-ban Martin Ester, Hans-Peter Kriegel, Jörg Sander és Xiaowei Xu javasolt. Ez egy sűrűség-in-algoritmus, amely a klaszterek becsült sűrűségére támaszkodik a particionálás elvégzéséhez.

Általános elv

A DBSCAN algoritmus 2 paramétert használ: a távolságot és a minimális pontok számát, amelynek sugárban kell lennie ahhoz, hogy ezeket a pontokat fürtnek lehessen tekinteni. A bemeneti paraméterek tehát a klaszterek pontsűrűségének becslései. Az algoritmus alapgondolata az, hogy egy adott pont esetében helyreállítsa a szomszédságát, és ellenőrizze, hogy tartalmaz-e pontokat vagy többet. Ez a pont akkor tekinthető egy klaszter részének. Ezután lépésről lépésre haladunk át a környéken , hogy megtaláljuk a klaszter összes pontját. ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}

Algoritmus

DBSCAN(D, eps, MinPts) C = 0 pour chaque point P non visité des données D marquer P comme visité PtsVoisins = epsilonVoisinage(D, P, eps) si tailleDe(PtsVoisins) < MinPts marquer P comme BRUIT sinon C++ etendreCluster(D, P, PtsVoisins, C, eps, MinPts) etendreCluster(D, P, PtsVoisins, C, eps, MinPts) ajouter P au cluster C pour chaque point P' de PtsVoisins si P' n'a pas été visité marquer P' comme visité PtsVoisins' = epsilonVoisinage(D, P', eps) si tailleDe(PtsVoisins') >= MinPts PtsVoisins = PtsVoisins U PtsVoisins' si P' n'est membre d'aucun cluster ajouter P' au cluster C epsilonVoisinage(D, P, eps) retourner tous les points de D qui sont à une distance inférieure à epsilon de P

Megoldás szerkezete

Az adatkészlet pontjai 3 típusra vannak felosztva:

• A központi pontok ( fő pont )
• Határpontok ( határpont )
• A kiugró ( a zajjal kapcsolatos problémák )

A központi pontok

Azt mondják, hogy az adatkészlet egy pontja központi, ha:

1. Szomszédsága sűrű

Ezek a pontok összekapcsolt összetevőket alkotnak, függetlenül az adatkészlet feltárásának sorrendjétől.

Határpontok

Az adatkészlet egy pontja határnak mondható, ha:

1. Ez nem központi pont
2. Egy központi pont szomszédságába tartozik

Ezek a pontok a csatlakoztatott komponensek köré csoportosulva csoportokat alkotnak. Ezeket a csoportokat általában angol nevükön hívják: Clusters .

A csatlakoztatott komponensektől eltérően a klaszterek kialakulása az adatkészlet feltárásának sorrendjétől függ. Valóban egy határpontot rendelnek hozzá a bővítési lépés során felmerült első fürthöz. A feltárás sorrendje mellett ezek a pontok érzékenyek a DBSCAN algoritmus különböző megvalósításaira.

A kiugró értékek

Az adatkészlet egy pontja kiugrónak mondható, ha:

1. Ez nem központi pont
2. Ez nem határpont

Ezek a pontok tehát az adatkészlet összes többi pontja.

Vigyázz, az ezeknek a pontoknak a neve félrevezető lehet, mert megnevezésük a választott paraméterektől függ.

Matematikai fogalmak

Egy pont szomszédsága

A szomszédság fogalma elemi fogalom a DBSCAN módszer alapjaként. Ez lehetővé teszi a sűrű környékek matematikai meghatározását, amelyeket a központi pontok lokalizálására és a klaszterek bővítésére használnak.

A pontok közötti távolság

A matematika , hívjuk távolság egy sor E semmilyen térkép d határozzák meg a termék E 2 = E × E és értékek a beállított ℝ + a pozitív valós számok ,

d:E×E→R+{\ displaystyle d: E \ -szerese E \ -nek \ mathbb {R} ^ {+}}

a következő tulajdonságok ellenőrzése

Vezetéknév	Ingatlan
szimmetria	∀(nál nél,b)∈E2, d(nál nél,b)=d(b,nál nél){\ displaystyle \ forall (a, b) \ E ^ -ban {2}, \ d (a, b) = d (b, a)}
elválasztás	∀(nál nél,b)∈E2, d(nál nél,b)=0⇔nál nél=b{\ displaystyle \ forall (a, b) \ E ^ -ban {2}, \ d (a, b) = 0 \ Balra mutató nyíl a = b}
háromszög egyenlőtlenség	∀(nál nél,b,vs.)∈E3, d(nál nél,vs.)≤d(nál nél,b)+d(b,vs.){\ displaystyle \ forall (a, b, c) \ E ^ -ben {3}, \ d (a, c) \ leq d (a, b) + d (b, c)}

A pontok közötti távolság megválasztása implicit paraméter a DBSCAN módszerben.

A DBSCAN esetében általában az euklideszi távolságot használják.

Epsilon ray nyitott labda

A szokásos térben, mint bármely metrikus térben  : (E,d){\ displaystyle (E, d)}

A nyitott labda a tér azon pontjainak halmaza , amelyek távolsága a ponttól szigorúan kisebb, mint  : B(o,ϵ){\ displaystyle B (p, \ epsilon) \,}M{\ displaystyle M}E{\ displaystyle E}o{\ displaystyle p}ϵ{\ displaystyle \ epsilon}

B(o,ϵ)={M∈E∣d(M,o)<ϵ}{\ displaystyle B (p, \ epsilon) = \ bal \ {M \ E-ben, \ mid \, d (M, p) <\ epsilon \ right \}}

A lényeg ezután úgynevezett közepén a nyílt labdát , és hívják a sugara a nyílt labdát . o{\ displaystyle p}B(o,ϵ){\ displaystyle B (p, \ epsilon) \,}ϵ{\ displaystyle \ epsilon}B(o,ϵ){\ displaystyle B (p, \ epsilon) \,}

A gömbök jellemzői két elemtől függenek:

1. A golyók alakja összefügg a távolsággal (a DBSCAN implicit paramétere).d{\ displaystyle d}
2. A lefedett terület a választott sugártól függ (a DBSCAN számára kifejezett paraméter).ϵ{\ displaystyle \ epsilon}

A középponttal és sugárral ellátott nyitott gömbbel szemben kétdimenziós térben, euklideszi távolságra van ábrázolva . A kék felület a nyitott labdát jelöli : Ez megfelel a DBSCAN algoritmus szomszéd keresési területének. o{\ displaystyle p}ϵ{\ displaystyle \ epsilon}d{\ displaystyle d}B(o,ϵ){\ displaystyle B (p, \ epsilon) \,}

Epsilon-szomszédság

A környéken egy pont van a pontok halmaza az adathalmazban található a nyitott labdát középre és sugár  : ϵ{\ displaystyle \ epsilon}Vϵ(o){\ displaystyle V _ {\ epsilon} (p)}o{\ displaystyle p}q{\ displaystyle q}D{\ displaystyle D}o{\ displaystyle p}ϵ{\ displaystyle \ epsilon}

Vϵ(o)={q∈D∣d(q,o)<ϵ}{\ displaystyle V _ {\ epsilon} (p) = \ left \ {q \ in D \, \ mid \, d (q, p) <\ epsilon \ right \}}

A kiválasztott adatkészlet pontok a nyitott golyókon alapulnak, ezért a következő paraméterektől függenek:

1. A pontok és a távolságd{\ displaystyle d}o{\ displaystyle p}q{\ displaystyle q}
2. A keresési sugár a pont körülϵ{\ displaystyle \ epsilon}o{\ displaystyle p}

Szemben a pont szomszédságát a 2. dimenzió térében ábrázolták euklideszi távolsággal. A piros pontok az adatkészlet azon pontjai , amelyek a pont szomszédságához tartoznak, az indigó színű pontok pedig az adatkészlet olyan pontjait jelentik , amelyek nem tartoznak a pont szomszédságához . A DBSCAN algoritmus szempontjából a piros pontok száma a fontos. ϵ{\ displaystyle \ epsilon}o{\ displaystyle p}q{\ displaystyle q}D{\ displaystyle D}ϵ{\ displaystyle \ epsilon}o{\ displaystyle p}q{\ displaystyle q}D{\ displaystyle D}ϵ{\ displaystyle \ epsilon}o{\ displaystyle p}

Epsilon-sűrű környék

Egy környékről azt mondják, hogy sűrű, ha annak számossága nagyobb vagy egyenlő . ϵ{\ displaystyle \ epsilon}Vϵ(o){\ displaystyle V _ {\ epsilon} (p)}ménnemPts{\ displaystyle minPts}

∣Vϵ(o)∣⩾ménnemPts{\ displaystyle \ mid V _ {\ epsilon} (p) \ mid \ geqslant minPts}

Ez a meghatározás az első, amely a DBSCAN 3 paraméterétől függ:

1. A sűrűnek jelölendő környék minimális pontszáma .ménnemPts{\ displaystyle minPts}
2. A figyelembe vett pont körüli környék sugara .ϵ{\ displaystyle \ epsilon}o{\ displaystyle p}
3. A pontok közötti távolság .d{\ displaystyle d}

Az előző ábra segítségével rögzített. Ha 3 ponton van rögzítve, akkor az adott szomszédság egyértelműen sűrű. Ezzel szemben, ha 50 pontra van állítva, akkor a környék nyilvánvalóan nem sűrű. ϵ{\ displaystyle \ epsilon}ménnemPts{\ displaystyle minPts}ménnemPts{\ displaystyle minPts}

Sűrűség alapú kapcsolatok

Az ezt követő bináris relációkat a DBSCAN módszer bemutatására használják, és általánosabban a sűrűségen alapuló felügyelet nélküli tanulásban.

Közvetlenül elérhető sűrűséggel

Az adatkészlet egy pontja sűrűséggel közvetlenül elérhető egy másik pontról, ha: q{\ displaystyle q}D{\ displaystyle D}o{\ displaystyle p}

1. Vϵ(o){\ displaystyle V _ {\ epsilon} (p)} sűrű
2. q∈Vϵ(o){\ displaystyle q \ in V _ {\ epsilon} (p)}

Más szavakkal, a sűrűség által közvetlenül elérhető pontok egy sűrű szomszédság pontjai.

Egy ilyen viszonyt grafikusan ábrázol egy nyíl, amely a ponttól a pontig halad . o{\ displaystyle p}q{\ displaystyle q}

Sűrűség szerint elérhető

Az adatkészlet egy pontja sűrűséggel érhető el egy másik pontról, ha a pontok sorrendje létezik , például: q{\ displaystyle q}D{\ displaystyle D}o{\ displaystyle p}(o1,o2,...,onem){\ displaystyle (p_ {1}, p_ {2}, ..., p_ {n})}

1. o1=o{\ displaystyle p_ {1} = p}
2. oén+1{\ displaystyle p_ {i + 1}} közvetlenül elérhető sűrűséggel oén{\ displaystyle p_ {i}}
3. onem=q{\ displaystyle p_ {n} = q}

Egy pont sűrűséggel elérhető egy másik pontról, ha van egy nyílút a férgek felé . q{\ displaystyle q}o{\ displaystyle p}o{\ displaystyle p}q{\ displaystyle q}

Sűrűn kapcsolódik

Az adatkészlet egy pontja sűrűn kapcsolódik egy másik ponthoz, ha: q{\ displaystyle q}D{\ displaystyle D}o{\ displaystyle p}

1. o∈D{\ displaystyle o \ D-ben}
2. o{\ displaystyle p} sűrűséggel elérhető innen: o{\ displaystyle o}
3. q{\ displaystyle q} sűrűséggel elérhető innen: o{\ displaystyle o}

Egy pont és egy pontot sűrűn kötve, ha van két nyíl utakat indul ugyanarról a helyről , és menj a pontokat , és rendre . q{\ displaystyle q}o{\ displaystyle p}o{\ displaystyle o}o{\ displaystyle p}q{\ displaystyle q}

Paraméterbecslés

A paraméterek becslése és ez nem könnyű probléma, mert ez a két érték elválaszthatatlanul kapcsolódik a felosztandó tér topológiájához. Túl alacsony és / vagy túl nagy értéke megakadályozhatja az algoritmus terjesztését a fürtökben. Ezzel szemben a túl nagy és / vagy a túl alacsony érték ahhoz vezethet, hogy az algoritmus csak zajt ad vissza. Heurisztikát, amely lehetővé teszi a közös és egy adott tér meghatározását, az alábbiak adhatják meg: ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}

• ϵ{\ displaystyle \ epsilon} : számítsuk ki a tér minden pontjára a legközelebbi szomszédhoz való távolságot. Vegyük úgy, hogy a pontok "kellően nagy" részének távolsága a legközelebbi szomszédhoz kevesebb legyen ;ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}
• MénnemPts{\ displaystyle MinPts} : számítsa ki minden pontra a szomszédainak számát egy sugarú körzetben (a szomszédságának nagysága ). Vegyük úgy, hogy a pontok "kellően nagy" részének több pontja legyen a szomszédságában.ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}MénnemPts{\ displaystyle MinPts}MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}

A "kellően nagy" kifejezésen például a pontok% -át vagy % -át értjük . 95{\ displaystyle 95}90{\ displaystyle 90}

Egy másik heurisztikus 2D esetekben (meghatározott eredeti DBSCAN cikket) az, hogy az értéket a 4, és ábrázoljuk a görbe (csökkenő sorrendben) a távolságok minden egyes pont a 4 -én , plusz közeli szomszéd. Ezután a grafikonon megadott "küszöbpont" értékére állítjuk be. Ha ez a küszöb nem határozható meg egyértelműen, a felhasználó meg tudja javítani százalékának becslésével a zaj az adathalmaz: tehát, hogy csak a zaj szempontjából olyan távolságban van, hogy a 4 -én a legközelebbi szomszéd-nél nagyobb . MénnemPts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}

Előnyök és hátrányok

Az algoritmus nagyon egyszerű, és nem igényli, hogy meghatározzuk a megtalálni kívánt fürtök számát. Képes kezelni a kiugró értékeket úgy, hogy eltávolítja őket a particionálási folyamatból. A klasztereknek nem kell lineárisan elválaszthatóknak lenniük (csakúgy, mint például a k-mean algoritmus esetében). Nem képes azonban különböző sűrűségű klaszterek kezelésére.

Kapcsolódó cikkek

• OPTIKA

Hivatkozások

1. M. Ester, H.-P. Kriegel, J. Sander és X. Xu, „Sűrűségalapú algoritmus fürtök felfedezéséhez nagy térbeli, zajjal rendelkező területi adatbázisokban”, a 2. Nemzetközi Tudáskonferencia anyagában. Discovery and Data mining, 1996, pp. 226-231.
2. (in) Michael Hahsler Matthew Piekenbrock és Derek Doran , "  dbscan: Gyors sűrűség alapú klaszterezés R  ' , Journal of Statistical Software , vol.  91, n o  1,2019( ISSN  1548-7660 , DOI  10.18637 / jss.v091.i01 , online olvasás , hozzáférés : 2020. március 9. )
3. alitouka , spark_dbscan: DBSCAN fürtözési algoritmus az Apache Spark tetején ,2017. augusztus 18( online olvasás )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">