A mai bejegyzésben klasztereket fogunk keresni. A blogon korábban már volt szó egy klaszteranalízisre használt eljárásról. Az Elvárás-maximalizáló algoritmus abból a feltételezésből indul ki, hogy az egyes homogén csoportok jól meghatározható eloszlásból származnak. A mai bejegyzésben egy olyan eljárást fogunk megvizsgálni, ami nem ezt feltételezi. Ez lesz a Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN).
Sűrűség alapú csoportosítás
A cél, hogy ne legyen szükségünk egy konkrét eloszlás megadására amikor csoportosítunk. Nézzük meg a következő példa megfigyeléseket:
A fenti ábrán három egymástól jól elkülönülő csoport biztosan van: van két kisebb, kb. kör alakú a bal alsó és felső sarkokban, és egy nagyobb kereszt alakú középen. Miből gondoljuk ezt? Természetes intuíció, hogy az egymáshoz közelebbi pontok szorosabb kapcsolatban állnak egymással, tehát sűrűbben fognak a térben elhelyezkedni. Az is természetesnek tűnik, hogy ha két csoport nincs egymással kapcsolatban, akkor egy üres tér (vagy legalábbis ritkább sűrűségű) fogja őket elválasztani. Az ezen az intuíción alapuló klaszterizációs eljárásokat “sűrűség-alapú” algoritmusoknak nevezzük.
A legelső ilyen sűrűség alapú eljárás a DBSCAN volt, amit 1996-ban fejlesztett ki Martin Ester, Hans-Peter Kriegel, Jörg Sander és Xiaowei Xu. 2015-ben Jörg Sander, Ricardo Campello, Davoud Moulavi és Arthur Zimek ezt továbbfejlesztett és publikálták a mai bejegyzés tárgyát képező HDBSCAN-t.
Szigetek és a tenger
Hogy pontosan megértsük, hogyan is működik a HDBSCAN ábrázoljuk az 1. tulajdonság tengelyére vetítve az adatok sűrűség függvényét:
A csúcsok a nagyobb sűrűségű területek, míg a völgyek a kisebbek. A korábban említett intuícióból kiindulva nagy valószínűséggel a csúcsok lesznek a csoportjaink központjai. Akkor most készítsük el az osztályainkat. Hogyan? Csak húzzunk egy vízszintes vonalat. Pepe Berba egy nagyon ötletes analógiát használ a helyzet szemléltetésére: képzeljük el a fenti sűrűségfüggvényt mint egy tengerpart szárazföldi részét, az osztályokat létrehozó vonalat meg mint a vízszintet. Ha dagály van, csak a legmagasabb csúcsok látszanak ki a tengerből:
Ha apály akkor szinte minden:
Félidőben meg valahol a kettő között:
Mint fentebb látható: attól függően, hogy hol van a tengerszint más-más mennyiségű csoportot tudunk létrehozni. Mit is jelképez ez a “vízszint”? Ez a csoportok valószínűsége. Ha magasabban van akkor csak azokat a csoportokat fogadjuk el létezőnek, amik nagyon valószínűek. Minél lentebb ereszkedik, annál jobban növekszik a bizonytalanságunk is az egyes csoportok létezésében. Jogos a kérdés: mi az a bizonytalanság amit még el tudunk fogadni? Vagyis hol legyen az optimális vízszint?
A HDBSCAN ehhez egy hierarchikus láncba rendezi a lehetséges megoldásokat. Valahogy így:
Ezt a hagyomány szerint fejtetőre szokták állítani:
Számszerűsítés
A fenti analógia szerintem jól megmutatja a HDBSCAN működési elvét, most nézzük meg egy kicsit a konkrét megvalósítást. Az algoritmusnak az alábbi lépési vannak:
- Tér átalakítása a sűrűségnek megfelelően
- Optimális sűrűségű kapcsolati háló építése
- Hierarchikus fa építése
- Hierarchikus fa metszése
- Optimális csoportszám megkeresése
Nézzük ezeket a lépéseket egyesével:
1. Tér átalakítása a sűrűségnek megfelelően
Ugye az eredeti megfigyeléseink nem írják le menyire vannak az egyes pontok egymáshoz közel, tehát át kell alakítanunk az adatokat úgy, hogy ezt az információt megismerjük. Értelemszerűen az nem elég, ha csak fogjuk a pontok egymástól való távolságát. Azért nem, mert ebben nincs információ arra nézve, hogy egy pont mennyire sűrű területen helyezkedik el. Ezért a HDBSCAN a következő formulát alkalmazza:
Ahol:
— távolság
— a és b pont közötti “mutual reachability” távolsága, a távolság amit a HDBSCAN a későbbiekben használni fog
— a és b pont euklidészi távolsága
— k számú legközelebbi szomszéd
— az a pont távolsága k számú szomszédjától
Ez talán elsőre nem világos kifejezés, de egy ábra gyorsan megvilágítja. Tegyük fel, hogy k az 3, ebben az esetben az alábbi ábrán a 
2. Optimális sűrűségű kapcsolati háló építése
Rendben, tehát a fenti lépésben kiszámoltuk, hogy milyen távolságra van egymástól minden pont. Most ideje megkeresni a “szigeteket”, vagyis azokat a pontokat amik közel helyezkednek el egymáshoz. Ehhez gráfként fogjuk ábrázolni a megfigyeléseket (ezek lesznek a csúcsok) és a távolságukat (ezek lesznek az élek súlyai). A “tengerszint” pedig egy szűrő lesz: csak azokat az éleket ábrázoljuk amik súlya nagyobb mit a tengerszint aktuális értéke. Ez számítástechnikailag elég drága, szerencsére a gráfelmélet segítségünkre van és a minimális feszítőfa alkalmazásával csökkenti lehet a számítási igényt. Ugye az a fa tartalmazza az összes csúcsot és azokat az éleket, amivel a legkisebb összsúlyt tudjuk elérni.
3. Hierarchikus fa építése
A minimális feszítőfa megtalálása után már elég könnyű kialakítani a hierarchikus kapcsolatot. Növekvő sorrendbe rendezzük az élsúlyt és csúcsokat, összevonjuk őket ahogy haladunk felfelé. A HDBSCAN erre Disjoint-set_data_structure-t használ. Ez a fenti példánál így fog kinézni:
4. Hierarchikus fa metszése
A hierarchikus fa ideális esetben elég információt szolgáltat arra nézve mennyi csoportot szeretnénk létrehozni, de őszintén szólva nagy adatmennyiségnél elég használhatatlan. Ezért a következő lépésünk a fa egyszerűsítése , “metszése”. A cél ezzel az, hogy egy olyan fát hozzunk létre ami jól kezelhető, és csak a szűkséges információkat tartalmazza. Erre a célra a “minimális csoport méret” (angolul: minimal cluster size) hiperparamétert használja a HDBSCAN. Ennek az értéknek az ismeretében szépen végiglépkedünk a fánkon és minden elágazásnál megnézzük, hogy az ott lévő ágak mindegyike a minimális csoportméretnél nagyobb csoportot tartalmaz e. Ha nem, akkor azokat a pontokat, amik túl kicsi csoportba kerülnek “kiesett pontoknak” jelöljük, és megjegyezzük mi volt a távolság ahol kiestek. Mire végighaladunk az eredeti hierarchikus fán, egy sokkal egyszerűbb fához fogunk eljutni:
5. Optimális csoportszám megkeresése
Most már csak azt kell eldöntenünk, hogy menyi csoportot szeretnénk létrehozni. A hierarchikus fáknál ismert módon azokat a csoportokat szeretjük amik hosszú életűek, vizuálisan amik vertikálisan magasak. A hosszú élet mellett a második amit szeretünk egy csoportnál, ha sok pontot tartalmaz, ez lényegében a “kiesett pontok” száma. Ennek megfelelően azt a “vízszintett” keressük, ami a legmagasabb és legtöbb pontot tartalmazó ágakat tudja összekötni. A HDBSCAN ezt a feladatot a következő módon oldja meg. Először is bevezet egy 
Értelemszerűen minden csoport magasságát le tudjuk írni a 
Ahol:
- c — az adott csoport
- p — a csoportba tartozó megfigyelés
Ha ezzel az eljárással végiglépkedünk az egész fán, akkor minden
Python megvalósítás
Pythonban én a hdbscan csomagot használtam eddig, a fenti ábrák egy részét is ezzel készítettem. Használata triviális, tehát nem is részletezném csak ide rakok egy példa kódot:
import hdbscan
# modell
clusterer = hdbscan.HDBSCAN(min_cluster_size=2, min_samples=10)
# adatok illesztése és a oszálycímkék lekérdezése
labels = clusterer.fit_predict(X)
# metszett fa és optimális oszályok ábrázolása
import seaborn as sns
clusterer.condensed_tree_.plot(select_clusters=True, selection_palette=sns.color_palette())
# ábra
colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(set(labels)))]
plt.clf()
fig = plt.figure()
ax = fig.add_subplot()
plt.scatter(x1,x2, color=[ colors[i] for i in labels ])
# square plot
ax.set_aspect('equal', adjustable='box')
plt.legend()
plt.xlabel("1. tulajdonság")
plt.ylabel("2. tulajdonság")
plt.show()Ami eredménye:
Ne lepjen meg senkit, hogy a fenti ábrán 4 csoportot láthatunk. Igazából 3 van meg, a -1 értékűek amik a kiugró értékek, azok a megfigyelések amiket nem lehetett besorolni egyik csoportba se.
Irodalom
- Pepe Berba: Understanding HDBSCAN and Density-Based Clustering
- Leland McInnes, John Healy és Steve Astels Revision: How HDBSCAN Works
Sajó Zsolt Attila 