Free Press

A gépi tanulással kapcsolatos feladat nem feltétlenül lineáris, de számos jól ismert lépésből áll:

• Probléma meghatározása.
• Adatok előkészítése.
• A mögöttes modell megtanulása.
• A mögöttes modell javítása mennyiségi és minőségi értékelésekkel.
• A modell bemutatása.

Az új probléma feldolgozásának egyik jó módja, ha a probléma azonosításán és meghatározásán keresztül a lehető legjobban dolgozunk, és megtanulunk egy olyan modellt, amely értelmes információkat ragad meg az adatokból. Bár a mintafelismerés és a gépi tanulás problémái különböző típusúak lehetnek, nagyjából három kategóriába sorolhatók:

• Supervised Learning:
  A rendszernek bemeneti példákat és azok kívánt kimeneteit adják meg egy “tanár”, és a cél egy általános szabály megtanulása, amely a bemeneteket a kimenetekhez rendeli.
• Unsupervised Learning:
  Nem adnak címkéket a tanuló algoritmusnak, így az magára hagyja, hogy struktúrát találjon a bemenetben. A felügyelet nélküli tanulás lehet öncélú (rejtett minták felfedezése az adatokban) vagy eszköz egy cél felé (jellemzőtanulás).
• Kényszerített tanulás:
  A rendszer kölcsönhatásba lép egy dinamikus környezettel, amelyben egy bizonyos célt kell teljesítenie (például járművet vezet vagy játékot játszik egy ellenféllel szemben). A rendszer visszajelzést kap jutalmak és büntetések formájában, miközben navigál a problématérben.

A felügyelt és a felügyelet nélküli tanulás között helyezkedik el a félig felügyelt tanulás, ahol a tanár hiányos képzési jelet ad: olyan képzési halmazt, amelyből hiányzik néhány (gyakran sok) célkimenet. Ebben a blogbejegyzésben a felügyelet nélküli tanulásra és az adatok klaszterezésére fogunk összpontosítani.

Felügyelet nélküli tanulás

Némely mintafelismerési problémában a képzési adatok x bemeneti vektorok halmazából állnak, a megfelelő célértékek nélkül. Az ilyen felügyelet nélküli tanulási problémákban a cél lehet az adatokon belül a hasonló példák csoportjainak felfedezése, amit klaszterezésnek nevezünk, vagy annak meghatározása, hogy az adatok hogyan oszlanak el a térben, amit sűrűségbecslésnek nevezünk. Egyszerűbben fogalmazva, egy n mintavételű x1-től xn-ig terjedő térben a valódi osztálycímkék nem állnak rendelkezésre minden egyes mintához, ezért tanító nélküli tanulásnak nevezzük.

A felügyelet nélküli tanulással kapcsolatos problémák:

• A felügyelet nélküli tanulás nehezebb a felügyelt tanulási feladatokhoz képest.
• Honnan tudjuk, hogy az eredmények értelmesek-e, mivel nem állnak rendelkezésre válaszcímkék?
• Hagyjuk, hogy a szakértő megnézze az eredményeket (külső értékelés)
• Meghatározunk egy objektív függvényt a klaszterezésre (belső értékelés)

Miért van szükség a felügyelet nélküli tanulásra a fenti problémák ellenére?

• A nagy adathalmazok jegyzetelése nagyon költséges, ezért csak néhány példát tudunk manuálisan címkézni. Példa: Beszédfelismerés
• Létezhetnek olyan esetek, amikor nem tudjuk, hogy hány/milyen osztályra oszlanak az adatok. Példa: Adatbányászat
• Elképzelhető, hogy klaszterezéssel szeretnénk betekintést nyerni az adatok szerkezetébe, mielőtt osztályozót terveznénk.

A felügyelet nélküli tanulás két további kategóriába sorolható:

• Parametrikus felügyelet nélküli tanulás
  Ez esetben az adatok parametrikus eloszlását feltételezzük. Feltételezi, hogy a mintaadatok egy olyan populációból származnak, amely egy rögzített paraméterkészleten alapuló valószínűségi eloszlást követ. Elméletileg egy normális eloszláscsaládban minden tag azonos alakú, és az átlag és a szórás által paraméterezett. Ez azt jelenti, hogy ha ismerjük az átlagot és a szórást, és tudjuk, hogy az eloszlás normális, akkor ismerjük bármely jövőbeli megfigyelés valószínűségét. A parametrikus felügyelet nélküli tanulás Gauss-keverék modellek konstruálását és az Expectation-Maximization algoritmus használatát jelenti a kérdéses minta osztályának előrejelzésére. Ez az eset sokkal nehezebb, mint a hagyományos felügyelt tanulás, mivel nem állnak rendelkezésre válaszcímkék, és így nem áll rendelkezésre megfelelő pontossági mérőszám az eredmény ellenőrzésére.
• Nem paraméteres felügyelet nélküli tanulás
  A felügyelet nélküli tanulás nem paraméteres változatában az adatokat klaszterekbe csoportosítjuk, ahol minden klaszter (remélhetőleg) mond valamit az adatokban jelen lévő kategóriákról és osztályokról. Ezt a módszert általában kis mintanagyságú adatok modellezésére és elemzésére használják. A parametrikus modellekkel ellentétben a nemparametrikus modellek nem igénylik, hogy a modellező bármilyen feltételezést tegyen a populáció eloszlásáról, ezért néha eloszlásmentes módszernek is nevezik.

Mi a klaszterezés?

A klaszterezés a legfontosabb nem felügyelt tanulási problémának tekinthető; tehát, mint minden más ilyen jellegű probléma, ez is egy struktúra megtalálásával foglalkozik a címkézetlen adatok gyűjteményében. A klaszterezés laza definíciója lehetne “az objektumok csoportokba szervezésének folyamata, amelyek tagjai valamilyen módon hasonlóak”. Egy klaszter tehát olyan objektumok gyűjteménye, amelyek “hasonlóak” egymáshoz, és “nem hasonlóak” a más klaszterekhez tartozó objektumokhoz.

Távolság alapú klaszterezés.

Adott ponthalmaz, a pontok közötti távolság fogalmával, a pontok csoportosítása bizonyos számú klaszterbe, úgy, hogy

• a belső (klaszteren belüli) távolságok legyenek kis i.azaz a klaszterek tagjai közel állnak/hasonlóak egymáshoz.
• a külső (klaszteren belüli) távolságoknak nagynak kell lenniük, azaz a különböző klaszterek tagjai nem hasonlóak.

A klaszterezés céljai

A klaszterezés célja egy címkézetlen adathalmazban a belső csoportosítás meghatározása. De hogyan döntsük el, hogy mi a jó klaszterezés? Kimutatható, hogy nincs olyan abszolút “legjobb” kritérium, amely független lenne a klaszterezés végső céljától. Következésképpen a felhasználónak kell megadnia ezt a kritériumot, mégpedig úgy, hogy a klaszterezés eredménye megfeleljen az igényeinek.

A fenti képen honnan tudjuk, hogy mi a legjobb klaszterezési megoldás?

Az adott klaszterezési megoldás megtalálásához , meg kell határoznunk a klaszterek hasonlósági mértékeit.

Proximity Measures

A klaszterezéshez két adatponthoz meg kell határoznunk egy közelségi mértéket. A közelség itt azt jelenti, hogy a minták mennyire hasonlítanak/nem hasonlítanak egymáshoz.

• Hasonlósági mérték S(xi,xk): nagy, ha xi,xk hasonlóak
• Dissimilaritási (vagy távolsági) mérték D(xi,xk): kicsi, ha xi,xk hasonlóak

Változatos hasonlósági mértékeket használhatunk.

• Vektorok:

• Sorozatok: Jaccard távolság

• Pontok: Euklideszi távolság
  q=2

A “jó” közelségmérő nagyon is alkalmazásfüggő. A klasztereknek invariánsnak kell lenniük a probléma szempontjából “természetes” transzformációk alatt. Továbbá klaszterezés közben nem tanácsos olyan adatokat normalizálni, amelyek több eloszlásból származnak.

Klaszterező algoritmusok

A klaszterező algoritmusok az alábbiak szerint osztályozhatók:

• Kizárólagos klaszterezés
• Átfedő klaszterezés
• Hierarchikus klaszterezés
• Probabilisztikus klaszterezés

Az első esetben az adatokat kizárólagos módon csoportosítják, tehát ha egy adott adatpont egy meghatározott klaszterbe tartozik, akkor nem kerülhet más klaszterbe. Erre egy egyszerű példát mutat az alábbi ábra, ahol a pontok szétválasztását egy kétdimenziós síkon egy egyenes vonallal érjük el.

A második típus, az átfedő klaszterezés ezzel szemben az adatok klaszterezésére fuzzy halmazokat használ, így minden pont két vagy több klaszterhez is tartozhat különböző mértékű tagsággal. Ebben az esetben az adatok egy megfelelő tagsági értékhez lesznek hozzárendelve.

A hierarchikus klaszterezési algoritmus a két legközelebbi klaszter egyesítésén alapul. A kezdeti feltétel úgy valósul meg, hogy minden adatpontot klaszterként határozunk meg. Néhány iteráció után eléri a kívánt végső klasztereket.

Végül az utolsó fajta klaszterezés egy teljesen valószínűségi megközelítést alkalmaz.

Ebben a blogban a négy leggyakrabban használt klaszterező algoritmusról lesz szó:

• K-means
• Fuzzy K-means
• Hierarchikus klaszterezés
• Gaussians keveréke

Mindegyik algoritmus a fent felsorolt klaszterezési típusok egyikéhez tartozik. Míg a K-means egy kizárólagos klaszterező algoritmus, a Fuzzy K-means egy átfedő klaszterező algoritmus, a hierarchikus klaszterezés nyilvánvaló és végül a Mixture of Gaussians egy valószínűségi klaszterező algoritmus. Az egyes klaszterezési módszereket a következő bekezdésekben tárgyaljuk.

K-Means klaszterezés

A K-means az egyik legegyszerűbb felügyelet nélküli tanulási algoritmus, amely a jól ismert klaszterezési problémát oldja meg. Az eljárás egy egyszerű és könnyű módszert követ egy adott adathalmaz osztályozására egy bizonyos számú klaszteren keresztül (feltételezzük, hogy k klaszter), amely a priori rögzített. Az alapötlet az, hogy k központot határozunk meg, minden klaszterhez egyet. Ezeket a középpontokat okos módon kell elhelyezni, mert a különböző elhelyezkedés eltérő eredményt eredményez. Ezért jobb választás, ha minél távolabb helyezzük el őket egymástól. A következő lépés az, hogy az adott adathalmazhoz tartozó minden egyes pontot a legközelebbi centroidhoz rendelünk. Ha nincs függőben lévő pont, akkor az első lépés befejeződik, és egy korai csoportosítás történik. Ekkor újra ki kell számolnunk k új centroidot, mint az előző lépésből származó klaszterek barycentrumát. Miután megvan ez a k új centroid, új kötést kell végezni ugyanazon adathalmaz pontjai és a legközelebbi új centroid között. Egy hurok keletkezett. E hurok eredményeként észrevehetjük, hogy a k centroid lépésről lépésre változtatja a helyét, amíg több változás nem történik. Más szóval a centroidok nem mozognak tovább.

Végezetül ez az algoritmus egy célfüggvény, jelen esetben egy hiba négyzetfüggvény minimalizálására törekszik. A célfüggvény

ahol

egy xi adatpont és a cj klaszterközpont között választott távolságmérték, az n adatpontnak az adott klaszterközépponttól való távolságának mutatója.

Az algoritmus a következő lépésekből áll:

• Legyen X = {x1,x2,x3,……..,xn} az adatpontok halmaza és V = {v1,v2,…….,vc} a klaszterközpontok halmaza.
• Véletlenszerűen válasszunk “c” klaszterközpontot.
• Kalkuláljuk ki az egyes adatpontok és a klaszterközpontok közötti távolságot.
• Az adatpontot rendeljük ahhoz a klaszterközponthoz, amelynek távolsága a klaszterközponttól az összes klaszterközpont közül a legkisebb.
• Újraszámítsuk ki az új klaszterközpontot a következők segítségével:

ahol, ‘ci’ az i-edik klaszterben lévő adatpontok számát jelenti.

• Újraszámítsuk ki az egyes adatpontok és az újonnan kapott klaszterközpontok közötti távolságot.
• Ha egyetlen adatpontot sem rendeltünk át, akkor álljunk meg, ellenkező esetben ismételjük meg a 3) lépéstől.

Bizonyítható ugyan, hogy az eljárás mindig befejeződik, de a k-means algoritmus nem feltétlenül találja meg a globális célfüggvényminimumnak megfelelő legoptimálisabb konfigurációt. Az algoritmus jelentősen érzékeny a kezdeti véletlenszerűen kiválasztott klaszterközpontokra is. A k-means algoritmus többször is lefuttatható ennek a hatásnak a csökkentése érdekében.

A k-means egy egyszerű algoritmus, amelyet számos problématerületre adaptáltak. Mint látni fogjuk, jó jelölt a kiterjesztésére, hogy fuzzy jellemzővektorokkal is dolgozhasson.

A k-means eljárás egy mohó algoritmusnak tekinthető, amely az n mintát k klaszterre osztja fel úgy, hogy a klaszterközpontoktól mért négyzetes távolságok összegét minimalizálja. Van néhány gyengesége:

• Az átlagok inicializálásának módja nem volt megadva. Az egyik népszerű indítási mód a minták közül k véletlenszerű kiválasztása.
• Megtörténhet, hogy a mi-hez legközelebbi minták halmaza üres, így a mi nem frissíthető. Ezt a problémát az implementáció során kezelni kell, de általában figyelmen kívül hagyják.
• Az eredmények a k értékétől függnek, és nincs optimális módja a legjobb “k” leírásának.

Ez utóbbi probléma különösen problémás, mivel gyakran nem tudjuk, hány klaszter létezik. A fenti példában ugyanazzal az algoritmussal ugyanazokra az adatokra alkalmazva a következő 3-means klaszterezést kapjuk. Ez jobb vagy rosszabb, mint a 2-means klaszterezés?

Az optimális klaszterszám megtalálására bármely adott adathalmaz esetében sajnos nincs általános elméleti megoldás. Egy egyszerű megközelítés az, hogy több, különböző k osztályú futtatás eredményeit összehasonlítjuk, és egy adott kritérium alapján kiválasztjuk a legjobbat, de óvatosnak kell lennünk, mert a k növelése definíció szerint kisebb hibafüggvényértékeket eredményez, de növeli a túlillesztés kockázatát is.

Fuzzy K-Means Clustering

A fuzzy klaszterezésben minden pontnak van egy valószínűsége, hogy minden klaszterhez tartozik, és nem tartozik teljesen egyetlen klaszterhez, mint a hagyományos k-means esetében. A fuzzy k-means kifejezetten azt a problémát próbálja kezelni, amikor a pontok kissé a középpontok között helyezkednek el, vagy más módon nem egyértelműek, a távolságot valószínűséggel helyettesítve, amely természetesen lehet a távolság valamilyen függvénye, például a távolság inverzéhez viszonyított valószínűség. A Fuzzy k-means e valószínűségek alapján súlyozott centroidot használ. Az inicializálási, iterációs és befejezési folyamatok megegyeznek a k-meansben használtakkal. Az így kapott klaszterek a címkék kemény hozzárendelése helyett inkább valószínűségi eloszlásokként elemezhetőek. Tudnunk kell, hogy a k-means a fuzzy k-means speciális esete, amikor a használt valószínűségi függvény egyszerűen 1, ha az adatpont a legközelebb van a centroidhoz, és 0 egyébként.

A fuzzy k-means algoritmus a következő:

• Tegyük fel, hogy a klaszterek száma K.
• Inicializálás: Véletlenszerűen inicializáljuk a klaszterekhez tartozó k-means μk-t, és kiszámítjuk annak a valószínűségét, hogy minden Xi adatpont egy adott K klaszter tagja,
  P(PointXiHasLabelK|Xi,K).
• Iteráció: A klaszter középpontjának újraszámítása súlyozott középpontként az összes Xi adatpont tagságának valószínűségei alapján :

• Befejezés:

A jobb megértéshez nézzük meg ezt az egyszerű egydimenziós példát. Adott egy bizonyos adathalmaz, tegyük fel, hogy azt egy tengelyen elosztva ábrázoljuk. Az alábbi ábra ezt mutatja:

Az ábrára nézve két klasztert azonosíthatunk a két adatkoncentráció közelében. Ezekre az “A” és a “B” jelzővel fogunk hivatkozni. A bemutatott első megközelítésben – a k-means algoritmusban – minden egyes adatpontot egy adott centroidhoz társítottunk, ezért ez a tagsági függvény így nézett ki:

A Fuzzy k-means megközelítésben ehelyett ugyanaz az adott adatpont nem tartozik kizárólagosan egy jól meghatározott klaszterhez, hanem középen helyezkedhet el. Ebben az esetben a tagsági függvény egy simább vonalat követ, ami azt jelzi, hogy minden adatpont több klaszterhez is tartozhat különböző mértékű tagsággal.

A fenti ábrán a pirosan jelölt pontként megjelenő adatpont inkább a B, mint az A klaszterhez tartozik. Az “m” 0,2 értéke az ilyen adatpont A-hoz való tartozás mértékét jelzi.

Hierarchikus klaszterezési algoritmusok

Megadva egy N darab klaszterezendő elemkészletet és egy N*N távolság (vagy hasonlóság) mátrixot, a hierarchikus klaszterezés alapvető folyamata a következő:

• Kezdésként minden elemet egy klaszterhez rendelünk, így ha N elemünk van, akkor N klaszterünk van, amelyek mindegyike csak egy elemet tartalmaz. A klaszterek közötti távolságok (hasonlóságok) legyenek azonosak a bennük lévő elemek közötti távolságokkal (hasonlóságokkal).
• Keresd meg a legközelebbi (leghasonlóbb) klaszterpárt, és egyesítsd őket egyetlen klaszterbe, így most egy klaszterrel kevesebb lesz.
• Kalkuláld ki az új klaszter és az egyes régi klaszterek közötti távolságokat (hasonlóságokat).
• Ismételd meg a 2. és 3. lépést, amíg minden elem egyetlen N méretű klaszterbe nem kerül.

Clustering as a Mixture of Gaussians

A klaszterezési problémák kezelésének van egy másik módja is: a modellalapú megközelítés, amely abból áll, hogy bizonyos modelleket használunk a klaszterekre, és megpróbáljuk optimalizálni az adatok és a modell közötti illeszkedést.

A gyakorlatban minden klaszter matematikailag reprezentálható egy parametrikus eloszlással, például egy Gauss-eloszlással. A teljes adathalmazt tehát ezen eloszlások keveréke modellezi.
A nagy valószínűségű keverékmodell általában a következő tulajdonságokkal rendelkezik:

• a komponenseloszlásoknak magas “csúcsai” vannak (az adatok egy klaszterben szorosak);
• a keverékmodell jól “lefedi” az adatokat (az adatok domináns mintáit a komponenseloszlások megragadják).

A modellalapú klaszterezés fő előnyei:

• jól tanulmányozott statisztikai következtetési technikák állnak rendelkezésre;
• rugalmasság a komponenseloszlás kiválasztásában;
• sűrűségbecslést kapunk minden klaszterre;
• “puha” osztályozás áll rendelkezésre.

Gaussok keveréke
A legelterjedtebb ilyen jellegű klaszterezési módszer Gaussok keverékének tanulásán alapul:

A keverékmodell k komponenseloszlás keveréke, amelyek együttesen f(x) keverékeloszlást alkotnak:

Az αk a k-adik komponens hozzájárulását jelenti az f(x) megalkotásában. A gyakorlatban gyakran használnak parametrikus eloszlásokat (pl. gaussok), mivel sok munkát végeztek a viselkedésük megértése érdekében. Ha minden egyes fk(x)-et gaussal helyettesítünk, akkor úgynevezett gauss keverékmodelleket (GMM) kapunk.

Az EM-algoritmus

A várakozásmaximalizálás feltételezi, hogy az adataink többszörös többváltozós normális eloszlásokból állnak (megjegyezzük, hogy ez egy nagyon erős feltételezés, különösen, ha a klaszterek számát rögzítjük!). Másképpen fogalmazva, az EM egy algoritmus a valószínűségi függvény maximalizálására, amikor a modellünkben szereplő változók egy része megfigyeletlen (azaz amikor látens változókkal rendelkezünk).
Joggal kérdezhetnénk, hogy ha csak egy függvényt akarunk maximalizálni, miért nem használjuk egyszerűen a függvény maximalizálására meglévő gépezetet. Nos, ha ezt úgy próbáljuk maximalizálni, hogy deriváltakat veszünk és nullára állítjuk, akkor azt találjuk, hogy sok esetben az elsőrendű feltételeknek nincs megoldása. Van egy tyúk-tojás probléma, hogy a modellparaméterek megoldásához ismerni kell a megfigyeletlen adatok eloszlását; de a megfigyeletlen adatok eloszlása a modellparaméterek függvénye.

A várakozás-maximalizálás ezt úgy próbálja megkerülni, hogy iteratív módon kitalál egy eloszlást a megfigyeletlen adatokra, majd a modellparamétereket úgy becsüli meg, hogy maximalizál valamit, ami a tényleges valószínűségi függvény alsó korlátja, és ezt ismétli a konvergenciáig:

A várakozás-maximalizáló algoritmus

• A modellparaméterek értékeinek kitalálásával kezdjük
• E-lépés: Minden olyan adatpont esetében, amelyhez hiányzó értékek tartoznak, a modellegyenleted segítségével oldd meg a hiányzó adatok eloszlását a modellparaméterekre vonatkozó aktuális becslésed és a megfigyelt adatok ismeretében (vedd figyelembe, hogy minden egyes hiányzó érték eloszlását oldod meg, nem a várható értékét). Most, hogy megvan az eloszlás minden egyes hiányzó értékre, kiszámíthatjuk a valószínűségi függvény várakozását a megfigyeletlen változók tekintetében. Ha a modellparaméterre vonatkozó tippünk helyes volt, akkor ez a várható valószínűség lesz a megfigyelt adataink tényleges valószínűsége; ha a paraméterek nem voltak helyesek, akkor ez csak egy alsó korlát lesz.
• M-lépés:
• Ismételjük meg a konvergenciáig.

A klaszterezéssel kapcsolatos problémák

A klaszterezéssel kapcsolatban számos probléma merül fel. Ezek közül:

• a nagyszámú dimenzió és nagyszámú adatelem kezelése az időbonyolultság miatt problémás lehet;
• a módszer hatékonysága a “távolság” definíciójától függ (távolság alapú klaszterezés esetén). Ha nem létezik egyértelmű távolságmérték, akkor azt “definiálnunk” kell, ami nem mindig egyszerű, különösen többdimenziós terekben;
• a klaszterező algoritmus eredménye (ami sok esetben maga is tetszőleges lehet) többféleképpen értelmezhető.

Megvalósítható alkalmazások

A klaszterező algoritmusok számos területen alkalmazhatók, például:

• marketing: hasonló viselkedésű vásárlók csoportjainak megtalálása a vásárlók tulajdonságait és korábbi vásárlási adatait tartalmazó nagy adatbázis alapján;
• biológia: növények és állatok osztályozása a tulajdonságaik alapján;
• biztosítás:
• Földrengéskutatás: a megfigyelt földrengés epicentrumok klaszterezése a veszélyes zónák azonosítására;
• World Wide Web: dokumentumosztályozás; weblog adatok klaszterezése a hasonló hozzáférési minták csoportjainak felfedezésére.