Oké, kezdjünk el beszélni a DBSCAN-ról.
Az alkalmazások sűrűségalapú térbeli klaszterezése zajjal (DBSCAN) egy jól ismert adatklaszterező algoritmus, amelyet gyakran használnak az adatbányászatban és a gépi tanulásban.
A DBSCAN egy ponthalmaz alapján (gondolkodjunk kétdimenziós térben, ahogyan azt az ábra példázza) egy távolságmérés (általában euklideszi távolság) és egy minimális pontszám alapján csoportosítja az egymáshoz közeli pontokat. Emellett a kis sűrűségű régiókban lévő pontokat outliereknek jelöli.
Paraméterek:
A DBSCAN algoritmus alapvetően 2 paramétert igényel:
eps: megadja, hogy a pontoknak milyen közel kell lenniük egymáshoz ahhoz, hogy egy klaszter részének tekinthetők legyenek. Ez azt jelenti, hogy ha két pont közötti távolság kisebb vagy egyenlő, mint ez az érték (eps), akkor ezeket a pontokat szomszédosnak tekintjük.
minPoints: a pontok minimális száma ahhoz, hogy egy sűrű régiót alkossunk. Ha például a minPoints paramétert 5-re állítjuk, akkor legalább 5 pontra van szükségünk egy sűrű régió kialakításához.
Paraméterbecslés:
A paraméterbecslés minden adatbányászati feladatnál probléma. A jó paraméterek kiválasztásához meg kell értenünk, hogyan használják őket, és legalább alapvető előzetes ismeretekkel kell rendelkeznünk a felhasználandó adathalmazról.
eps: Ha az eps értéket túl kicsire választjuk, az adatok nagy része nem lesz klaszterezve. Kiugrónak fog minősülni, mert nem elégíti ki a sűrű régió létrehozásához szükséges pontok számát. Másrészt, ha a választott érték túl nagy, a klaszterek összeolvadnak, és az objektumok többsége ugyanabba a klaszterbe kerül. Az eps értéket az adathalmaz távolsága alapján kell megválasztani (ennek meghatározásához használhatunk k-távolsági gráfot), de általában a kis eps értékek előnyösebbek.
minPoints: Általános szabályként az adathalmaz dimenzióinak számából (D) levezethető egy minimális minPoints, mint minPoints ≥ D + 1. A nagyobb értékek általában jobbak a zajos adathalmazok esetében, és jelentősebb klasztereket képeznek. A minPoints minimális értéke 3 kell, hogy legyen, de minél nagyobb az adathalmaz, annál nagyobb minPoints értéket kell választani.
A paraméterbecslésről bővebben itt olvashat.
Miért használjuk a DBSCAN-t?
A DBSCAN algoritmust arra kell használni, hogy olyan összefüggéseket és struktúrákat találjunk az adatokban, amelyeket manuálisan nehéz megtalálni, de amelyek relevánsak és hasznosak lehetnek a minták megtalálása és a trendek előrejelzése szempontjából.
A klaszterezési módszereket általában a biológia, az orvostudomány, a társadalomtudományok, a régészet, a marketing, a karakterfelismerés, az irányítási rendszerek és így tovább használják.
Gondoljunk a DBSCAN gyakorlati felhasználására. Tegyük fel, hogy van egy e-kereskedésünk, és szeretnénk javítani az eladásainkat azáltal, hogy releváns termékeket ajánlunk a vásárlóinknak. Nem tudjuk pontosan, hogy a vásárlóink mit keresnek, de egy adathalmaz alapján megjósolhatjuk és ajánlhatunk egy adott vásárlónak egy releváns terméket. A DBSCAN-t alkalmazhatjuk az adathalmazunkra (az e-kereskedelmi adatbázis alapján), és klasztereket találhatunk a felhasználók által vásárolt termékek alapján. A klaszterek segítségével megtalálhatjuk a vásárlók közötti hasonlóságokat, például ha az A vásárló 1 tollat, 1 könyvet és 1 ollót vásárolt, a B vásárló pedig 1 könyvet és 1 ollót, akkor a B vásárlónak 1 tollat ajánlhatunk. Ez csak egy kis példa a DBSCAN használatára, de rengeteg alkalmazásban, számos területen használható.
Hogyan tudjuk könnyen implementálni?
Mint már írtam (tipp: ne higgy el mindent, amit írok), a DBSCAN egy jól ismert algoritmus, ezért nem kell aggódnod a saját implementálásával. Használhatod az interneten fellelhető könyvtárak/csomagok valamelyikét. Itt van egy lista azokról a linkekről, amelyeken megtalálhatja a DBSCAN implementációt: Matlab, R, R, Python, Python.
Egy alkalmazást is kifejlesztettem (portugál nyelven), amely didaktikusan elmagyarázza a DBSCAN működését. Az alkalmazás C++ nyelven íródott, és megtalálható a Githubon.