DBSCAN: Mi ez? Mikor kell használni? Hogyan kell használni.

A DBSCAN (zajszélesség-alapú alkalmazások zajszintű csoportosítása) egy népszerű, nem felügyelt tanulási módszer, amelyet modellezési és gépi tanulási algoritmusokban használnak. Mielőtt továbbmennénk, meg kell határoznunk, mi a „felügyelet nélküli” tanulási módszer. Nem felügyelt tanulási módszerek akkor vannak, amikor nincs egyértelmű cél vagy eredmény, amelyet meg akarunk találni. Ehelyett az adatokat egymásba csoportosítottuk a megfigyelések hasonlósága alapján. A tisztázás kedvéért példa a Netflix. A korábban a múltban megtekintett műsorok alapján a Netflix javasolja a következő műsorok megtekintését. Bárki, aki valaha nézte a Netflixet, látta az alábbi képernyőt ajánlásokkal (Igen, ez a kép közvetlenül a Netflix-fiókomból készül, és ha még soha nem figyeltél a Shameless-t, azt javaslom, hogy lépjen rá az ASAP-ra).

Mivel a 'Shameless' nézegettem, a Netflix számos hasonló műsort is ajánl. De honnan gyűjti a Netflix ezeket az ajánlásokat? Tekintettel arra, hogy megpróbálja megjósolni a jövőt azzal a műsorral, amelyet majd fogok nézni, a Netflixnek nincs semmi, amelyre az előrejelzéseket vagy ajánlásokat alapozni tudja (nincs egyértelmű, végleges cél). Ehelyett a Netflix más felhasználókra néz, akik a múltban szintén figyelték a „szégyentelen” szót, és megnézi, hogy ezek a felhasználók a „szégyentelen” mellett nézték meg. Ezzel a Netflix az érdeklődés hasonlósága alapján a felhasználókat csoportosítja. Pontosan így működik a felügyelet nélküli tanulás. A megfigyelések egyszerűen csoportosítása a hasonlóság alapján, abban reménykedve, hogy a klaszterek alapján pontos következtetéseket vonnak le.

Vissza a DBSCAN-hez. A DBSCAN egy klaszterezési módszer, amelyet a gépi tanulásban használnak a nagy sűrűségű klaszterek és az alacsony sűrűségű klaszterek elválasztására. Tekintettel arra, hogy a DBSCAN egy sűrűség alapú klaszterezési algoritmus, nagy munkát végez az olyan területek keresésekor az adatokban, amelyek sűrű megfigyelésekkel rendelkeznek, szemben az adatok olyan területeivel, amelyek nem nagyon sűrűek a megfigyelésekkel. A DBSCAN az adatokat különböző alakú klaszterekbe is rendezheti, ez egy másik nagy előnye. A DBSCAN mint ilyen működik:

  • Az adatkészletet n dimenzióra osztja
  • Az adatkészlet minden egyes pontjára a DBSCAN n dimenziós alakzatot alkot az adatpont körül, majd megszámolja, hogy hány adatpont tartozik az alakhoz.
  • A DBSCAN ezt a formát fürtnek tekinti. A DBSCAN iteratíven kibővíti a fürtöt azáltal, hogy átjárja a fürtön belüli egyes pontokat, és megszámolja a közeli más adatpontok számát. Vegyünk példát az alábbi ábráról:

A fent említett folyamat lépésről lépésre haladva a DBSCAN az adatok n dimenziókra osztásával kezdődik. Miután a DBSCAN megtette, véletlenszerűen indul (ebben az esetben feltételezzük, hogy ez volt az egyik piros pont), és kiszámítja, hogy hány más pont van a közelben. A DBSCAN mindaddig folytatja ezt a folyamatot, amíg nincs más adatpont a közelben, majd második fürtöt fog létrehozni.

Mint a grafikából már észrevette, van néhány paraméter és specifikáció, amelyeket meg kell adnunk a DBSCAN-nek, mielőtt működik. A két paraméter, amelyet meg kell határoznunk, mint ilyen:

Mennyi minimális adatpont szükséges az egyetlen fürt meghatározásához?
Mennyire lehet egy pont a következő ponttól ugyanazon klaszterben?

Visszatérve a képre, az epsilon az az adatpont közötti távolság tesztelésére megadott sugár. Ha egy pont egy másik pont epsilon távolságán belül esik, akkor ez a két pont ugyanabban a klaszterben lesz.

Ezenkívül ebben a forgatókönyvben a szükséges minimális pontszámot 4-re állítják. Ha az egyes adatpontokon áthalad, mindaddig, amíg a DBSCAN 4 pontot talál egymástól epsilon távolságon belül, klaszter jön létre.

FONTOS: Ahhoz, hogy egy pontot „törzspontnak” lehessen tekinteni, annak tartalmaznia kell az epsilon távolságon belüli minimális pontszámot. Ergo, a megjelenítésnek valójában csak KÉT alappontja van. Tekintse meg itt a dokumentációt, és különösen a min_samples paramétert.

Azt is észreveszi, hogy a grafika kék pontja nem található egyetlen klaszterben sem. A DBSCAN NEM feltétlenül kategorizálja az összes adatpontot, ezért félelmetes az adatkészletben szereplő outlierek kezelésekor. Vizsgáljuk meg az alábbi ábrát:

A bal oldali kép egy hagyományosabb fürtözési módszert ábrázol, amely nem veszi figyelembe a többdimenziós dimenziót. Míg a jobb oldali kép azt mutatja, hogy a DBSCAN hogyan alakíthatja az adatokat különböző formákba és méretekbe hasonló klaszterek megtalálása érdekében.

A bal oldali kép olyan tradicionálisabb klaszterezési módszert ábrázol, mint például a K-Means, amely nem veszi figyelembe a többdimenziós dimenziót. Míg a jobb oldali kép azt mutatja, hogy a DBSCAN hogyan alakíthatja az adatokat különböző formákba és méretekbe hasonló klaszterek megtalálása érdekében. A jobb oldali képen azt is észrevesszük, hogy az adatkészlet külső széle mentén lévő pontok nem vannak besorolva, ami arra utal, hogy az adatok között túlságosan nagyok.

A DBSCAN előnyei:

  • Nagyon jó a nagy sűrűségű klaszterek és az alacsony sűrűségű klaszterek elválasztásában egy adott adatkészletben.
  • Nagyon jó, ha az adathalmazon kívül eső adatokat kezel.

A DBSCAN hátrányai:

  • Nem működik jól, ha különböző sűrűségű klaszterekkel foglalkozik. Míg a DBSCAN nagyszerűen elválasztja a nagy sűrűségű klasztereket az alacsony sűrűségű klaszterektől, addig a DBSCAN hasonló sűrűségű klaszterekkel küzd.
  • Harcol a nagy dimenziós adatokkal. Tudom, hogy az egész cikkben kifejtettem, hogy a DBSCAN mennyire képes az adatokat különböző méretekre és formákra tömöríteni. A DBSCAN azonban csak ilyen messzire haladhat, ha túl sok dimenziós adatot kap, a DBSCAN szenved

Az alábbiakban ismertettem, hogyan lehet a DBSCAN-t Pythonban megvalósítani, amelyben utána elmagyarázom a mutatókat és a DBSCAN-modell kiértékelését.

DBSCAN megvalósítás Pythonban

1. Az adatok hozzárendelése X értékekhez
Ne feledje, mivel ez nem felügyelet nélküli tanulás, nem állíthatunk be egyértelmű y értéket.
2. A DBSCAN modell inicializálása. Az alábbi kódban az epsilon = 3 és a min_samples a pontok minimális száma, amely a klaszter létrehozásához szükséges.
3. A DBSCAN által létrehozott címkék tárolása
4. Annak meghatározása, hogy mely pontok képezik „alappontjainkat”
5. A klaszterek számának kiszámítása
6. A sziluett pontszám kiszámítása

A DBSCAN teljesítményének mérési mutatói:

Sziluett pontszám: A sziluett pontszámot a pontok közötti átlagos klaszteren belüli távolság és az átlagos legközelebbi klaszter távolság felhasználásával számítják ki. Például egy olyan fürtnek, amelyben nagyon sok adatpont található nagyon közel egymáshoz (nagy sűrűségű), és messze van a következő legközelebbi fürttől (ami arra utal, hogy a klaszter nagyon egyedi a következő legközelebbihez viszonyítva), erős sziluett pontszámmal bír . A sziluett pontszám -1 és 1 között van, ahol -1 a lehető legrosszabb és 1 a legjobb. A 0 sziluett pontszáma az átfedő klaszterekre utal.

Inertia: A tehetetlenség a belső klaszter négyzetek összegét méri (a négyzetek összege az összes maradék összegét jelenti). Az inerciát annak mérésére használják, hogy a rokon klaszterek hogyan vannak egymás között, minél alacsonyabb a tehetetlenség pontszám, annál jobb. Fontos azonban megjegyezni, hogy a tehetetlenség nagymértékben azon a feltételezésen alapul, hogy a klaszterek domborúak (gömb alakúak). A DBSCAN nem feltétlenül osztja az adatokat gömbös klaszterekre, tehát a tehetetlenség nem jó mutató a DBSCAN modellek értékeléséhez (ezért a tehetetlenséget nem vettem be a fenti kódba). Az inerciát gyakran használják más klaszterezési módszerekben, például a K-eszköz klaszterezésében.

Egyéb források:

A Naftali Harris blogja hatalmas kiegészítő forrás a további információkhoz