Nem rossz idő adatfeldolgozónak lenni. Komoly emberek érdeklődését keltheti fel, ha a “Big Data” felé tereled a beszélgetést, a bulizó társaság többi tagja pedig kíváncsi lesz, ha a “mesterséges intelligenciát” és a “gépi tanulást” említed. Még a Google is úgy gondolja, hogy nem vagy rossz, és hogy egyre jobb leszel. Rengeteg “okos” algoritmus segíti az adattudósok varázslását. Mindez bonyolultnak tűnhet, de ha egy kicsit megértjük és rendszerezzük az algoritmusokat, még csak nem is olyan nehéz megtalálni és alkalmazni azt, amire szükségünk van.
Az adatbányászatról vagy gépi tanulásról szóló tanfolyamokat általában a klaszterezéssel kezdik, mert ez egyszerre egyszerű és hasznos. Ez egy fontos része a felügyelet nélküli tanulás némileg tágabb területének, ahol a leírni kívánt adatok nincsenek címkézve. A legtöbb esetben ez az, amikor a felhasználó nem sok információt adott nekünk arról, hogy mi a várt kimenet. Az algoritmus csak az adatokkal rendelkezik, és a lehető legjobbat kell tennie. Esetünkben klaszterezést kell végeznie – az adatokat olyan csoportokba (klaszterekbe) kell szétválasztania, amelyek hasonló adatpontokat tartalmaznak, miközben a csoportok közötti különbözőség a lehető legnagyobb. Az adatpontok bármit képviselhetnek, például az ügyfeleinket. A klaszterezés hasznos lehet, ha például hasonló felhasználókat akarunk csoportosítani, majd az egyes klaszterekre különböző marketingkampányokat futtatni.
K-Means klaszterezés
Az adatbányászati tanfolyamok a szükséges bevezető után mindig a K-Means-szel folytatódnak; egy hatékony, széles körben használt, mindenre kiterjedő klaszterező algoritmussal. Mielőtt ténylegesen futtatnánk, meg kell határoznunk egy távolságfüggvényt az adatpontok között (például az euklideszi távolságot, ha a pontokat térben akarjuk klaszterezni), és meg kell adnunk a kívánt klaszterek számát (k).
Az algoritmus azzal kezdődik, hogy k pontot választunk ki kezdő centroidnak (“klaszterek középpontjának”). Kiválaszthatunk akármilyen k véletlenszerű pontot, vagy használhatunk más megközelítést is, de a véletlenszerű pontok kiválasztása jó kezdet. Ezután iteratívan megismételjük a két lépést:
-
Kiosztási lépés: az adathalmazunk m pontjainak mindegyikét egy olyan klaszterhez rendeljük, amelyet a k centroidok közül a legközelebbi képvisel. Minden egyes ponthoz kiszámítjuk az egyes centroidoktól való távolságokat, és egyszerűen kiválasztjuk a legkisebb távolságot.
-
Frissítési lépés: minden klaszterhez új centroidot számítunk a klaszterben lévő összes pont átlagaként. Az előző lépésből megvan a pontok halmaza, amelyeket egy klaszterhez rendelünk. Most minden ilyen halmazra kiszámítunk egy átlagot, amelyet a klaszter új centroidjának nyilvánítunk.
Minden egyes iteráció után a centroidok lassan elmozdulnak, és az egyes pontok teljes távolsága a hozzájuk rendelt centroidtól egyre kisebb lesz. A két lépést a konvergenciáig váltogatjuk, vagyis addig, amíg a klaszterkiosztás nem változik tovább. Számos iteráció után minden egyes centroidhoz ugyanazok a pontok lesznek hozzárendelve, így ismét ugyanazokhoz a centroidokhoz vezetnek. A K-Means garantáltan egy lokális optimumhoz konvergál. Ez azonban nem feltétlenül kell, hogy a legjobb általános megoldás (globális optimum) legyen.
A kezdeti centroidok kiválasztásától függhet a klaszterezés végeredménye, ezért sokat gondolkodtunk ezen a problémán. Az egyik egyszerű megoldás az, hogy a K-Means-t néhányszor lefuttatjuk véletlenszerű kezdeti hozzárendelésekkel. Ezután kiválaszthatjuk a legjobb eredményt úgy, hogy azt vesszük, amelyiknek az egyes pontok és a klaszterük közötti távolságok összege a legkisebb – ez az a hibaérték, amelyet eleve minimalizálni próbálunk.
A kezdeti pontok kiválasztásának más megközelítései is támaszkodhatnak a távoli pontok kiválasztására. Ez jobb eredményekhez vezethet, de problémánk lehet a kiugró értékekkel, azokkal a ritka, egyedül álló pontokkal, amelyek egyszerűen csak “nem stimmelnek”, amelyek esetleg csak néhány hibát jelentenek. Mivel messze vannak minden értelmes klasztertől, minden ilyen pont végül saját “klasztert” alkothat. Jó egyensúlyt jelent a K-Means++ változat , amelynek inicializálása továbbra is véletlenszerű pontokat választ ki, de a korábban kijelölt centroidoktól való négyzetes távolsággal arányos valószínűséggel. A távolabbi pontok nagyobb valószínűséggel lesznek kiválasztva kezdő centroidnak. Következésképpen, ha van egy pontcsoport, akkor a valószínűsége annak, hogy a csoportból egy pont kerül kiválasztásra, szintén nagyobb lesz, ahogy a valószínűségeik összeadódnak, megoldva az említett kiugró problémát.
A K-Means++ a Python Scikit-learn K-Means implementációjának alapértelmezett inicializálása is. Ha Pythont használsz, akkor ez lehet az általad választott könyvtár. Java esetén a Weka könyvtár lehet jó kiindulási alap:
Java (Weka)
// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}Python (Scikit-learn)
> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)A fenti Python példában egy szabványos ‘Iris’ példaadatkészletet használtunk, amely három különböző íriszfaj virágszirom és sziromlevél méreteit tartalmazza. Ezeket három klaszterbe csoportosítottuk, és a kapott klasztereket összehasonlítottuk a tényleges fajokkal (célfajokkal), hogy lássuk, tökéletesen egyeznek-e.
Ez esetben tudtuk, hogy három különböző klaszter (faj) van, és a K-Means helyesen felismerte, hogy melyek tartoznak össze. De hogyan válasszuk ki általában a k klaszterek jó számát? Az ilyen jellegű kérdések elég gyakoriak a gépi tanulásban. Ha több klasztert kérünk, akkor azok kisebbek lesznek, és így a teljes hiba (a pontok és a hozzájuk rendelt klaszterek közötti távolságok összege) is kisebb lesz. Tehát jó ötlet, ha csak nagyobb k-t állítunk be? Lehet, hogy végül k = m lesz, vagyis minden pontnak saját centroidja van, és minden klaszterhez csak egy pont tartozik. Igen, a teljes hiba 0, de nem kaptunk egyszerűbb leírást az adatainkról, és nem is elég általános ahhoz, hogy lefedjen néhány új, esetleg megjelenő pontot. Ezt nevezik túlillesztésnek, és ezt nem akarjuk.
A probléma kezelésének egyik módja, hogy a nagyobb számú klaszterekért valamilyen büntetést írunk elő. Így most már nem csak a hibát, hanem a hiba + büntetést próbáljuk minimalizálni. A hiba csak konvergálni fog a nulla felé, ahogy növeljük a klaszterek számát, de a büntetés nőni fog. Bizonyos pontokon az újabb klaszter hozzáadásából származó nyereség kisebb lesz, mint a bevezetett büntetés, és megkapjuk az optimális eredményt. Az X-Means nevű megoldás, amely a Bayes-i információs kritériumot (BIC) használja erre a célra .
A másik dolog, amit megfelelően meg kell határoznunk, az a távolságfüggvény. Néha ez egyszerű feladat, az adatok természetéből adódóan logikus. Térbeli pontok esetén az euklideszi távolság kézenfekvő megoldás, de bonyolult lehet különböző “egységű” jellemzők, diszkrét változók stb. esetén. Ehhez sok tartományi ismeretre lehet szükség. Vagy segítségül hívhatjuk a gépi tanulást. Valójában megpróbálhatjuk megtanulni a távolságfüggvényt. Ha van egy gyakorló ponthalmazunk, amelyről tudjuk, hogyan kell csoportosítani őket (azaz a klaszterükkel megjelölt pontokat), akkor felügyelt tanulási technikákkal találhatunk egy jó függvényt, majd alkalmazhatjuk azt a még nem klaszterezett célhalmazunkra.
A K-Meansben használt módszer a két váltakozó lépéssel hasonlít az Expectation-Maximization (EM) módszerre. Valójában az EM egy nagyon egyszerű változatának tekinthető. Nem szabad azonban összetéveszteni a bonyolultabb EM klaszterezési algoritmussal, még akkor sem, ha egyes alapelvei megegyeznek.
EM klaszterezés
A K-Means klaszterezésnél tehát minden pont csak egyetlen klaszterhez van rendelve, és egy klasztert csak a centroidja ír le. Ez nem túl rugalmas, mivel problémáink lehetnek az egymást átfedő, vagy nem kör alakú klaszterekkel. Az EM klaszterezéssel most egy lépéssel tovább mehetünk, és minden klasztert leírhatunk a centroidjával (átlaga), kovarianciájával (így elliptikus klasztereket kaphatunk) és súlyával (a klaszter mérete). Annak valószínűségét, hogy egy pont egy klaszterhez tartozik, most egy többváltozós Gauss valószínűségi eloszlás adja meg (többváltozós – több változótól függő). Ez azt is jelenti, hogy kiszámíthatjuk annak a valószínűségét, hogy egy pont egy Gauss-“harang” alatt van, vagyis annak a valószínűségét, hogy egy pont egy klaszterhez tartozik.
Az EM-eljárást most azzal kezdjük, hogy minden egyes pontra kiszámítjuk annak a valószínűségét, hogy az aktuális klaszterek mindegyikéhez tartozik (amelyek az elején ismét véletlenszerűen jöhetnek létre). Ez az E-lépés. Ha egy klaszter valóban jó jelölt egy pontra, akkor annak valószínűsége közel egy lesz. Azonban két vagy több klaszter is lehet elfogadható jelölt, így a pontnak van egy klaszterek közötti valószínűségeloszlása. Az algoritmusnak ezt a tulajdonságát, hogy a pontok nem tartoznak korlátozottan egy klaszterhez, “lágy klaszterezésnek” nevezzük.
Az M-lépés most újraszámítja az egyes klaszterek paramétereit, felhasználva a pontoknak az előző klaszterkészlethez való hozzárendelését. Egy klaszter új átlagának, kovarianciájának és súlyának kiszámításához minden egyes pont adatát az előző lépésben kiszámított klaszterhez tartozás valószínűségével súlyozzuk.
A két lépés váltakozása a teljes log-likelihoodot növeli, amíg az konvergál. A maximum ismét lokális lehet, ezért az algoritmust többször is lefuttathatjuk, hogy jobb klasztereket kapjunk.
Ha most minden egyes ponthoz egyetlen klasztert akarunk meghatározni, egyszerűen kiválaszthatjuk a legvalószínűbbet. A valószínűségi modell birtokában hasonló adatok generálására is használhatjuk, azaz több olyan pontot mintavételezhetünk, amelyek hasonlóak az általunk megfigyelt adatokhoz.
Affinitási terjedés
Affinitási terjedést (AP) Frey és Dueck publikálta 2007-ben, és egyszerűsége, általános alkalmazhatósága és teljesítménye miatt csak egyre népszerűbb. Státusát a technika állása helyett de facto standarddá változtatja.
A K-Means és a hasonló algoritmusok fő hátránya, hogy meg kell választani a klaszterek számát, és ki kell választani a kezdeti ponthalmazt. Az Affinity Propagation ehelyett bemenetként az adatpontpárok közötti hasonlósági mértékeket veszi, és egyidejűleg minden adatpontot potenciális példának tekint. Az adatpontok között valós értékű üzenetek cserélődnek, amíg fokozatosan ki nem alakul a példaképek és a megfelelő klaszterek jó minőségű halmaza.
Az algoritmus bemenetként két adathalmazt kér tőlünk:
-
Az adatpontok közötti hasonlóságok, amelyek azt mutatják, hogy egy pont mennyire alkalmas arra, hogy egy másiknak a példaképe legyen. Ha két pont között nincs hasonlóság, mivel nem tartozhatnak ugyanahhoz a klaszterhez, akkor ez a hasonlóság a megvalósítástól függően elhagyható vagy -Infinity-re állítható.
-
Preferenciák, amelyek az egyes adatpontok példaként való alkalmasságát reprezentálják. Előzetes információval rendelkezhetünk arról, hogy mely pontok lehetnek előnyösek erre a szerepre, így ezt preferenciákon keresztül reprezentálhatjuk.
A hasonlóságokat és a preferenciákat gyakran egyetlen mátrixon keresztül reprezentáljuk, ahol a főátló értékei a preferenciákat képviselik. A mátrix reprezentáció sűrű adathalmazok esetén jó. Ha a pontok közötti kapcsolatok ritkák, praktikusabb, ha nem a teljes n x n mátrixot tároljuk a memóriában, hanem a kapcsolódó pontokhoz tartozó hasonlóságok listáját tartjuk meg. A színfalak mögött a “pontok közötti üzenetváltás” ugyanaz, mint a mátrixok manipulálása, és ez csak nézőpont és megvalósítás kérdése.
Az algoritmus ezután több iteráción keresztül fut, amíg konvergál. Minden iteráció két üzenetátviteli lépésből áll:
-
A felelősségek kiszámítása: A felelősség r(i, k) azt a felhalmozott bizonyítékot tükrözi, hogy a k pont mennyire alkalmas arra, hogy az i pont példaképeként szolgáljon, figyelembe véve az i pont más lehetséges példaképeit is: Az a(i, k) elérhetőség azt a felhalmozott bizonyítékot tükrözi, hogy mennyire lenne megfelelő az i pont számára, hogy a k pontot válassza példaként, figyelembe véve a többi pont által nyújtott támogatást arra vonatkozóan, hogy a k pont legyen a példa. Az elérhetőséget a k mintajelölt pontból küldjük az i pontnak.
A felelősségek kiszámításához az algoritmus az eredeti hasonlóságokat és az előző iterációban kiszámított elérhetőségeket használja (kezdetben minden elérhetőséget nullára állítunk). A felelősségek az i pont és a k pont mint példakép közötti bemeneti hasonlóság, mínusz az i pont és a többi példaképjelölt közötti hasonlóság és rendelkezésre állás összegének legnagyobb értéke. A logika annak kiszámítása mögött, hogy egy pont mennyire alkalmas példaképnek, az, hogy nagyobb előnyben részesül, ha a kezdeti a priori preferencia magasabb volt, de a felelősség alacsonyabb lesz, ha van egy hasonló pont, amely jó jelöltnek tartja magát, így a kettő között “verseny” folyik, amíg valamelyik iterációban el nem dől az egyik.
A rendelkezésre állás kiszámítása tehát a kiszámított felelősségeket használja bizonyítékként arra, hogy az egyes jelöltek jó példaképek lennének. Az a(i, k) elérhetőséget az r(k, k) önfelelősséggel és azoknak a pozitív felelősségeknek az összegével állítjuk be, amelyeket a k példajelölt más pontoktól kap.
Végül az eljárás befejezéséhez különböző megállási kritériumokat alkalmazhatunk, például ha az értékek változása valamilyen küszöbérték alá esik, vagy ha elérjük az iterációk maximális számát. Az Affinity Propagation eljárás során bármely ponton a Felelősség (r) és az Elérhetőség (a) mátrixok összegzése megadja a szükséges klaszterezési információt: az i pont esetében a maximális r(i, k) + a(i, k) értékkel rendelkező k jelenti az i pont példányát. Vagy, ha csak a példaképek halmazára van szükségünk, akkor a főátlót pásztázhatjuk. Ha r(i, i) + a(i, i) > 0, akkor az i pont egy példány.
Láttuk, hogy a K-Means és hasonló algoritmusok esetében a klaszterek számának eldöntése trükkös lehet. Az AP esetében ezt nem kell explicit módon megadni, de még mindig szükség lehet némi hangolásra, ha vagy több vagy kevesebb klasztert kapunk, mint amennyit esetleg optimálisnak találunk. Szerencsére egyszerűen a preferenciák beállításával csökkenthetjük vagy növelhetjük a klaszterek számát. A preferenciák magasabb értékre állítása több klasztert eredményez, mivel minden egyes pont “biztosabb” abban, hogy alkalmas arra, hogy példakép legyen, és ezért nehezebb “legyőzni” és valamely más pont “uralma” alá vonni. Ezzel szemben az alacsonyabb preferenciák beállítása kevesebb klasztert eredményez; mintha azt mondanák, hogy “nem, nem, kérlek, te jobb példa vagy, csatlakozom a te klaszteredhez”. Általános szabályként minden preferenciát beállíthatunk a medián hasonlóságra közepes vagy nagyszámú klaszter esetén, vagy a legalacsonyabb hasonlóságra közepes számú klaszter esetén. Azonban néhány futtatásra lehet szükség a preferenciák beállításával, hogy pontosan a mi igényeinknek megfelelő eredményt kapjuk.
A hierarchikus affinitáskiterjesztést is érdemes megemlíteni, mint az algoritmus egy olyan változatát, amely úgy kezeli a négyzetes komplexitást, hogy az adathalmazt több részhalmazra osztja, ezeket külön-külön klaszterezi, majd elvégzi a klaszterezés második szintjét.
A végén…
A klaszterező algoritmusok egész sora létezik, mindegyiknek megvannak az előnyei és hátrányai aszerint, hogy milyen típusú adatokkal, milyen időbonyolultsággal, gyengeségekkel és így tovább. Hogy több algoritmust említsek, ott van például a Hierarchical Agglomerative Clustering (vagy Linkage Clustering), ami akkor jó, ha nem feltétlenül kör alakú (vagy hipergömb alakú) klaszterekkel rendelkezünk, és nem tudjuk előre a klaszterek számát. Úgy indul, hogy minden pont egy külön klaszter, és úgy működik, hogy minden lépésben két legközelebbi klasztert egyesít, amíg minden egyetlen nagy klaszterbe nem kerül.
A hierarchikus agglomeratív klaszterezéssel utólag könnyen eldönthetjük a klaszterek számát, ha a dendrogramot (fa diagramot) vízszintesen vágjuk, ahol megfelelőnek találjuk. Ez is megismételhető (mindig ugyanazt a választ adja ugyanarra az adathalmazra), de a komplexitása is nagyobb (négyzetes).
A DBSCAN (Density-Based Spatial Clustering of Applications with Noise) szintén egy említésre méltó algoritmus. A szorosan egymás mellett elhelyezkedő pontokat csoportosítja, a klasztereket minden olyan irányba kiterjeszti, ahol közeli pontok vannak, így kezeli a klaszterek különböző formáit.
Ezek az algoritmusok külön cikket érdemelnek, és később egy külön bejegyzésben is megvizsgálhatjuk őket.
Az, hogy tudjuk, mikor érdemes egyik vagy másik algoritmust használni, némi próbálkozással és tévedéssel járó tapasztalatot igényel. Szerencsére számos implementáció áll rendelkezésünkre különböző programozási nyelveken, így a kipróbálásukhoz csak egy kis játékkedvre van szükség.