Ha az adatobjektumok jól szeparált csoportokba vannak elosztva, akkor ideális megközelítésnek tűnik az objektumok diszjunkt klaszterekbe történő éles osztályozása. A legtöbb esetben viszont az adathalmaz objektumai nem oszthatóak jól szeparált klaszterekbe, és lesz egy bizonyos önkényesség egy objektum egy konkrét klaszterhez rendelésekor. Tekintsünk egy olyan objektumot, ami két klaszter határának közelében fekszik, de kicsit közelebb van az egyikükhöz. Sok ilyen esetben megfelelőbb lehet súlyt rendelni minden egyes objektumhoz és minden egyes klaszterhez, ami azt jelzi, hogy az objektum milyen mértékben tartozik a klaszterhez. Matematikailag, legyen w ij annak a súlya, hogy az x i objektum a C j klaszterhez tartozik.

Ahogy a következő részben megmutatjuk, valószínűségi megközelítések is adhatnak ilyen súlyokat. Bár a valószínűségi megközelítések sok helyzetben hasznosak, vannak olyan esetek, amikor nehéz meghatározni a megfelelő statisztikai modellt. Ilyen esetekben hasonló képességek biztosításához nem valószínűségi klaszterező módszerekre van szükség. A fuzzy klaszterező módszerek a fuzzy halmazelméleten alapulnak és természetes módszert adnak olyan klaszterezés előállítására, ahol a tagság súlyainak (a w ij értékeknek) természetes (de nem valószínűségi) interpretációja van. Ez a rész a fuzzy klaszterezés általános megközelítési módját írja le és egy konkrét példát is ad a fuzzy c -közép (fuzzy K -közép) módszer képében.

Fuzzy halmazok

Lotfi Zadeh 1965-ben vezette be a fuzzy halmazelméletet és a fuzzy logikát, mint a pontatlanság és bizonytalanság kezelésének eszközét. Röviden, a fuzzy halmazelmélet megengedi, hogy egy objektum 0 és 1 közötti szinten tartozzon egy halmazhoz, míg a fuzzy logika megengedi, hogy egy állítás 0 és 1 közötti bizonyossággal legyen igaz. A hagyományos halmazelmélet és logika speciális esetei a fuzzy megfelelőiknek, amelyek a halmazhoz tartozás vagy a bizonyosság szintjének csak a 0 vagy az 1 értéket engedik meg. A fuzzy fogalmakat sok területen alkalmazzák, beleértve a szabályozó rendszereket, mintázat felismerést és adatelemzést (osztályozást és klaszterezést).

Tekintsük a következő példát a fuzzy logikára. Annak az állításnak az igazsága, hogy ``felhős az idő'', definiálható az égbolt felhőborítottságának százalékos arányaként. Ha például az égbolt 50%-át borítják felhők, akkor a ``felhős az idő'' állításhoz a 0,5 igazság-szintet rendelhetjük. Ha két halmazunk van, a ``felhős napok '' és a ``felhőtlen napok,'' akkor hasonlóan rendelhetünk hozzá minden egyes naphoz egy tagsági (hozzátartozási) szintet a két halmazban. Tehát ha egy nap 25%-ban volt felhős, akkor 25% tagsági szintű a ``felhős napok'', és 75% tagsági szintű a ``felhőtlen napok'' halmazban.

Fuzzy klaszterek

Tegyük fel, hogy adott adatpontok egy X={ x 1 ,…, x m } halmaza, ahol minden x i pont egy n -dimenziós vektor, azaz x i =( x i1 ,…, x in ) . A C 1 , C 2 , … , C k fuzzy klaszterek egy összessége X összes lehetséges fuzzy részhalmazainak egy részhalmaza. (Ez egyszerűen azt jelenti, hogy a tagság w ij súlya (foka) 0 és 1 közötti értékű minden x i pontra és minden C j klaszterre.) Viszont a következő ésszerű feltételeket is meg szeretnénk követelni a klaszterekre annak biztosításához, hogy a klaszterek úgynevezett fuzzy pszeudo-partíciót alkossanak.

1. Adott x i pont súlyainak összege 1:

∑ j=1 k w ij =1

2. Minden C j klaszter nem nulla súllyal tartalmaz legalább egy pontot, de nem tartalmazza egy súllyal az összes pontot:

0≤ ∑ i=1 m w ij ≤m

Fuzzy c -közép

Bár sok típusa van a fuzzy klaszterezésnek -- valójában sok adatelemző algoritmus ``fuzzy-asítható'' -- mi csak a K -közép módszer fuzzy változatát tekintjük, amit fuzzy c -középnek neveznek. A klaszterezési szakirodalomban néha c -közép módszerként hivatkoznak a K -közép módszer azon változatára, amely nem frissíti növekményesen a klaszterközéppontokat, és ezt a kifejezést adaptálta a fuzzy közösség a K -közép módszer fuzzy változatára. A 9.1. algoritmus adja meg a fuzzy c -közép algoritmust, melyet néha FCM-nek is neveznek.

A kezdőértékadás után az FCM ismételten kiszámolja az egyes klaszterek középpontjait és a fuzzy pszeudo-partíciót, amíg a partíció már nem változik. Az FCM hasonló szerkezetű a K -közép algoritmushoz, amely inicializás után a középpontokat újraszámoló és az egyes objektumokat a legközelebbi középponthoz hozzárendelő lépés között alternál. Speciálisan, a fuzzy pszeudo-partíció kiszámítása ekvivalens a hozzárendelő lépéssel. A K -közép módszerhez hasonlóan az FCM is magyarázható úgy, mint egy kísérlet a négyzetes hibaösszeg (SSE -- sum of squared error) minimalizálására, bár az FCM az SSE egy fuzzy változatán alapul. Valójában a K -közép tekinthető az FCM speciális esetének és a két algoritmus viselkedése is meglehetősen hasonló. Az FCM részleteit az alábbiakban írjuk le.

Az SSE kiszámítása

A négyzetes hibaösszeg (SSE) definíciója az alábbiak szerint módosul:

SSE( C 1 , C 2 ,…, C k )= ∑ j=1 k ∑ i=1 m w ij p dist ( x i , c j ) 2 , (9.1)

ahol c j a j -edik klaszter középpontja, az 1 és ∞ közötti értékű p pedig a súlyok hatását meghatározó kitevő. Megjegyezzük, hogy ez az SSE csupán a (8.1) képlettel megadott hagyományos K -közép SSE súlyozott változata.

Kezdőértékadás

Gyakran használunk véletlen kezdőértékadást. Konkrétan, a súlyokat választjuk véletlenszerűen úgy, hogy bármely objektumhoz tartozó súlyok összege 1 legyen. Ahogy a K -közép módszernél is, a véletlen inicializálás egyszerű, de gyakran vezet olyan klaszterezéshez, amely az SSE tekintetében egy lokális minimumnak felel meg. A K -középhez a kiinduló középpontok választásának tárgyalását tartalmazó 8.2.1. szakasz az FCM szempontjából is lényeges.

Középpontok kiszámítása

A (9.2) egyenlettel adott középpont-definíció megkapható úgy, hogy megkeressük azt a középpontot, amely a (9.1) összefüggéssel megadott fuzzy SSE értékét minimalizálja. (Lásd a 8.2.6. szakasz megközelítését.) A C j klaszterhez tartozó c j középpontot a következő egyenlet definiálja:

c j = ∑ i=1 m w ij p x i / ∑ i=1 m w ij p . (9.2)

A fuzzy középpont definíciója hasonló a hagyományos definícióhoz, kivéve azt, hogy minden pontot figyelembe veszünk (bármely pont bármely klaszterhez tartozhat, legalábbis valamelyest) és az egyes pontok hozzájárulása a középponthoz a tagságuk fokával van súlyozva. A hagyományos, ``éles'' halmazokra, ahol minden w ij értéke 0 vagy 1, ez a definíció a középpont hagyományos definíciójára egyszerűsödik.

A p értékének megválasztásakor célszerű néhány megfontolást tekintetbe venni. A p = 2 választás leegyszerűsíti a súlymódosítás formuláját, lásd (9.4) képletet. Ha azonban p értékét 1-hez közelinek választjuk, akkor a fuzzy c -közép hasonlóan viselkedik, mint a hagyományos K -közép. A másik irányba elmozdulva, p növekedtével minden klaszterközéppont az összes adatpont globális középpontjához közelít. Más szavakkal, a partíció elmosódottabbá válik, ahogy p növekszik.

A fuzzy pszeudo-partíció frissítése

Mivel a fuzzy pszeudo-partíciót a súlyok definiálják, ez a lépés magában foglalja az i -edik ponthoz és j -edik klaszterhez kapcsolódó w ij súlyok módosítását. A (9.3) egyenletben megadott súlymódosító formulát az SSE (9.1) képletéből azon feltétel mellett történő minimalizálással lehet megkapni, hogy a súlyok összege 1 legyen:

w ij = ( 1/dist ( x i , c j ) 2 ) 1 p−1 / ∑ q=1 k ( 1/dist ( x i , c q ) 2 ) 1 p−1 . (9.3)

Ez a képlet kicsit misztikusnak tűnhet. Meg kell jegyeznük azonban, hogy a p=2 esetben visszakapjuk a (9.4) egyenletet, ami valamelyest egyszerűbb. Egy intuitív magyarázatot adunk a (9.4) egyenletre, ami kis módosítással a (9.3) képletre is vonatkozik:

w ij =1/dist ( x i , c j ) 2 / ∑ q=1 k 1/dist ( x i , c q ) 2 . (9.4)

Intuitív módon, a w ij súly, ami az x i pont C j klaszterhez tartozásának fokát mutatja, viszonylag nagy kell, hogy legyen, ha x i közel van a c j középponthoz (ha dist( x i , c j ) kicsi), és viszonylag kicsi, ha x i messze van a c j középponttól (ha dist( x i , c j ) nagy). Ha w ij =1/dist ( x i , c j ) 2 , ami a (9.4) képlet számlálója, akkor valóban ez lesz a helyzet. Viszont egy pont tagsági súlyainak összege nem lesz egy, hacsak nem normalizáljuk őket, azaz el nem osztjuk az összes súly összegével, mint a (9.4) képletben. Összefoglalva, egy pont adott klaszterre vonatkozó tagsági súlya éppen a pont és a klaszterközéppont közötti távolság négyzetének reciproka osztva az adott pont összes tagsági súlyának összegével.

Tekintsük most az 1/(p−1) kitevő hatását a (9.3) képletben. Ha p≥2 , akkor ez a kitevő csökkenti a ponthoz közeli klaszterekhez rendelt súlyt. Valóban, ha p végtelenhez tart, akkor a kitevő 0-hoz tart, a súlyok pedig az 1/k értékhez. Másrészt, ha p 1-hez közelít, a kitevő növeli a ponthoz közeli klaszterekhez rendelt tagsági súlyt. Ha p 1-hez tart, akkor a tagsági súly 1-hez tart a legközelebbi klaszterre, és 0-hoz az összes többi klaszterre. Ez megfelel a K -közép eljárásnak.

9.1. Példa.

(Fuzzy c -közép három kör alakú klaszterre) A 9.1. ábra mutatja a fuzzy c -közép eredményeként megtalált három klasztert egy 100 pontból álló kétdimenziós adathalmazra. Minden pontot ahhoz a klaszterhez rendeltük, amelyikben a legnagyobb volt a tagsági súlya. Az egyes klaszterekhez tartozó pontokat különböző jelekkel ábrázoltuk, míg a klaszterekre a tagsági súlyt az árnyékolás mutatja. Minél sötétebbek a pontok, annál erősebb a tagságuk abban a klaszterben, amelyhez hozzárendeltük őket. A klaszterhez tartozás a klaszter középpontja közelében a legerősebb, és azokra a pontokra a leggyengébb, amelyek klaszterek között helyezkednek el.

Erősségek és korlátok

Az FCM pozitív tulajdonsága, hogy olyan klaszterezést állít elő, ami azt is jelzi, hogy az egyes pontok milyen mértékben tartoznak az egyes klaszterekhez. Egyébként leginkább ugyanazok az erősségei és gyengeségei, mint a K -középnek, bár valamivel számításigényesebb.

Ez a szakasz a statisztikai modelleken alapuló klaszterezést tekinti át. Gyakran kényelmes és hatékony azt feltételezni, hogy az adatok generálása egy statisztikai folyamat eredményeként történt, az adatokat pedig a legjobban illeszkedő statisztikai modellel kívánjuk leírni, ahol a statisztikai modell egy eloszlással és a hozzá tartozó paraméterekkel van megadva. Magas szinten ez a folyamat magában foglalja a döntést az adatokra vonatkozó statisztikai modellről és a modell paramétereinek becslését az adatok alapján. Ez a szakasz egy konkrét statisztikai modell-típust ír le, a keverék modellt, ami több statisztikai eloszlással modellezi az adatokat. Minden eloszlás egy klaszternek felel meg, az egyes eloszlások paraméterei pedig megadják a hozzájuk tartozó klaszter leírását, tipikusan a középpontjának és szóródásának függvényében.

A szakasz tárgyalása a következőképpen folytatódik. A keverék modellek leírása után megvizsgáljuk, hogy a statisztikai adatmodellek paramétereit hogyan lehet becsülni. Először leírjuk, hogyan lehet a maximum likelihood becslés (MLE -- maximum likelihood estimation) nevű eljárást egyszerű statisztikai modellek paramétereinek becslésére használni, ezután pedig azt tárgyaljuk, hogy miképpen lehet ezt a megközelítést általánosítani keverék modellek paramétereinek becslésére. Nevezetesen a jól ismert EM (Expectation-Maximization) algoritmust írjuk le, ami először kiinduló becslést ad a paraméterekre, majd pedig iteratív módon javítja ezeket a becsléseket. Példákat adunk arra, hogyan használható az EM algoritmus az adatok klaszterezésére a keverék modell paramétereinek becslése révén, valamint megtárgyaljuk a módszer erősségeit és korlátait.

Ezen szakasz megértéséhez lényeges a statisztika és a valószínűség 13. függelékben leírt fogalmainak biztos ismerete. A kényelem kedvéért a következő tárgyalás során egyaránt a valószínűség szót használjuk, hogy a valószínűségre és a valószínűségi sűrűségre hivatkozzunk.

Keverék modellek

A keverék modellek úgy tekintenek az adatokra, mint különböző valószínűségeloszlások keverékéből származó megfigyeléshalmazra. A valószínűségeloszlások tetszőlegesek lehetnek, de gyakran többdimenziós Gauss (normális) eloszlásnak tekintjük őket, mivel ez az eloszlástípus jól ismert, matematikailag könnyű vele dolgozni, valamint kimutatták, hogy sok esetben jó eredményeket ad. Ezek az eloszlástípusok ellipszoid alakú klasztereket tudnak modellezni.

A keverék modellek fogalmilag a következő adatgeneráló folyamatnak felelnek meg. Legyen adva több eloszlás, általában ugyanabból a típusból, de különböző paraméterekkel, és válasszunk véletlenszerűen ezekből az eloszlásokból egyet és generáljunk egy objektumot belőle. Ismételjük meg a folyamatot m -szer, ahol m az objektumok száma.

Formálisabban, tegyük fel, hogy K számú eloszlás és m számú objektum van, valamint X={ x 1 ,…, x m } . Jelölje a j -edik eloszlás paramétereit θ j , Θ pedig legyen az összes paraméter halmaza, azaz Θ={ θ 1 ,…, θ K } . Ekkor P( x i | θ j ) az i -edik objektum valószínűsége, ha a j -edik eloszlásból származik. Annak a valószínűsége, hogy a j -edik eloszlást választottuk az objektum generálására, a w j ( 1≤j≤K ) súlyokkal adható meg, ahol ezekre a súlyokra (valószínűségekre) az a feltétel vonatkozik, hogy az összegük egy, azaz ∑ j=1 K w j =1 . Ekkor az x objektum valószínűsége a (9.5) képlettel adható meg:

P(x|Θ)= ∑ j=1 K w j p j (x| θ j ). (9.5)

Ha az objektumokat egymástól függetlenül generáljuk, akkor a teljes objektumhalmaz valószínűsége éppen az egyes x i egyedek valószínűségeinek szorzata:

P(X|Θ)= ∏ i=1 m P( x i |Θ)= ∏ i=1 m ∑ j=1 K w j p j ( x i | θ j ). (9.6)

Keverék modelleknél minden egyes eloszlás egy különböző csoportot, azaz különböző klasztert ír le. Statisztikai módszerek alkalmazásával becsülhetjük ezeknek az eloszlásoknak a paramétereit az adatokból, és így leírhatjuk ezeket az eloszlásokat (klasztereket). Azonosítani tudjuk, hogy mely objektumok mely klaszterekhez tartoznak. Ugyanakkor a keverék-modellezés nem állítja elő az objektumok éles hozzárendelését a klaszterekhez, hanem inkább az objektumok egy bizonyos klaszterhez tartozásának a valószínűségét adja meg.

9.2. Példa.

(Egydimenziós Gauss keverék) A keverék modell egy konkrét szemléltetését adjuk a Gauss eloszlások segítségével. Az egydimenziós Gauss eloszlás valószínűségi sűrűségfüggvénye egy x pontban

P( x i |Θ)= 1 2π σ e − (x−μ) 2 2 σ 2 . (9.7)

A Gauss eloszlás paraméterei θ=(μ,σ) , ahol μ az eloszlás várható értéke, σ pedig a szórása. Tegyük fel, hogy két Gauss eloszlásunk van, egyformán 2 szórással és −4 , illetve 4 várható értékkel. Azt is tegyük fel, hogy a két eloszlást azonos valószínűséggel választjuk, azaz w 1 = w 2 =0,5 . Ekkor a (9.5) képlet a következő lesz:

P(x|Θ)= 1 2 2π e − (x+4) 2 8 + 1 2 2π e − (x−4) 2 8 . (9.8)

A 9.2. (a) ábra a valószínűségi sűrűségfüggvény grafikonját mutatja erre a keverék modellre, míg a 9.2. (b) ábrán az ebből a keverék modellből generált 20 000 pont hisztogramja látható.

A modell paramétereinek maximum likelihood becslése

Ha adott egy statisztikai modell az adatokra, meg kell becsülni a modell paramétereit. Erre a célra a standard megközelítés a maximum likelihood becslés, amit most magyarázunk el.

Először tekintsünk egy m pontból álló halmazt, amelyet egydimenziós Gauss eloszlásból generáltunk. Feltételezve, hogy a pontokat egymástól függetlenül generáltuk, a pontok valószínűsége éppen az egyesével vett valószínűségeik szorzata. (Bár ezúttal is valószínűségi sűrűségekkel dolgozunk, a szóhasználatot egyszerűsítendő valószínűségekről beszélünk.) A (9.7) képlet alapján ezt a valószínűséget felírhatjuk a (9.9) alakban. Mivel ez a valószínűség egy nagyon kicsi szám lenne, tipikusan a valószínűség logaritmusával dolgozunk, ahogy ez a (9.10) képletben látható.

P(X|Θ)= ∏ i=1 m 1 2π σ e − ( x i −μ) 2 2 σ 2 (9.9)

logP(X|Θ)=− ∑ i=1 m ( x i −μ) 2 2 σ 2 −0,5m log 2π−m log σ (9.10)

Egy eljárást szeretnénk találni az ismeretlen μ és σ paraméterek becslésére. Egy megközelítés azon paraméterértékek választása, amelyekre az adatok a legvalószínűbbek (legnagyobb a likelihood értékük). Más szavakkal, válasszuk azt a μ és σ értéket, ami maximalizálja a (9.9) képlet értékét. A statisztikában ezt a megközelítést maximum likelihood elvnek nevezik, és a maximum likelihood becslés (MLE) az a folyamat, ami ezt az elvet alkalmazza a statisztikai eloszlás paramétereinek a becslésére az adatok alapján.

Az elvet maximum likelihood elvnek nevezzük, mert adott adatokra az adatok a paraméterek függvényeként tekintett valószínűségét likelihood függvénynek nevezzük. Ennek szemléltetéséhez a (9.9) képletet a (9.11) alakba írjuk át, hogy kihangsúlyozzuk azt, hogy a μ és σ statisztikai paramétereket tekintjük a változóinknak, és hogy az adatokat konstansnak tekintjük. Praktikus okokból gyakrabban használják a loglikelihoodot^[7]. A loglikelihood függvényt a valószínűség logaritmusának a (9.10) képletéből számolva a (9.12) képlet adja meg. Megjegyezzük, hogy azok a paraméterértékek, amelyek a loglikelihoodot maximalizálják, egyúttal a likelihoodot is maximalizálják, mert a logaritmus monoton növekvő függvény.

likelihood(Θ|X)=L(Θ|X)= ∏ i=1 m 1 2π σ e − ( x i −μ) 2 2 σ 2 (9.11)

loglikelihood(Θ|X)=ℓ(Θ|X)=− ∑ i=1 m ( x i −μ) 2 2 σ 2 −0,5m log 2π−m log σ (9.12)

9.3. Példa.

(Paraméterbecslés maximum likelihood módszerrel) Egy konkrét példát adunk a MLE paraméterértékek megkeresésére történő alkalmazására. Tegyük fel, hogy 200 pontunk van, amelyek hisztogramját a 9.3. (a) ábra mutatja. A 9.3. (b) ábra mutatja a maximum loglikelihood ábrát a vizsgált 200 pontra. A μ=−4,1 és a σ=2,1 paraméterekre maximális a loglikelihood, ezek közel vannak az adatokat generáló Gauss eloszlás paraméterértékeihez, amelyek μ=−4,0 és σ=2,0 .

Az adatok valószínűségét nem praktikus a paraméterek különböző értékeire ábrázolni, legalábbis ha kettőnél több paraméter van. Ezért egy statisztikai paraméter maximum likelihood becslésének kiszámításához a standard statisztikai eljárás a loglikelihood függvény deriváltját venni a paraméter szerint, az eredményt egyenlővé tenni 0-val, és ezt megoldani. Konkrétan, a Gauss eloszlásra meg lehet mutatni, hogy a mintaelemek átlaga és szórása az eloszlás paramétereinek maximum likelihood becslése. (Lásd a 9. példát a 670. oldalon.) Valóban pontosan a 200 pont átlaga és szórása -- azaz μ=−4,1 és σ=2,1 -- voltak a példánkban tekintett 200 pontra azok a paraméterértékek, amelyek maximalizálták a loglikelihoodot.

Keverék modell paramétereinek becslése maximum likelihood módszerrel: az EM algoritmus

A maximum likelihood megközelítést a keverék modell paramétereinek becslésére is használhatjuk. A legegyszerűbb esetben tudjuk, hogy melyik adatobjektum melyik eloszlásból származik, és a probléma visszavezetődik arra, amikor egy eloszlás paramétereit kell becsülnünk az ebből az eloszlásból származó adott adatok alapján. A legtöbb tipikus eloszlásra a paraméterek maximum likelihood becslését az adatokat használó egyszerű képletekből kaphatjuk meg.

Egy általánosabb (és realisztikusabb) helyzetben nem tudjuk, hogy melyik pontot melyik eloszlás generálta. Így nem tudjuk közvetlenül számolni az egyes adatpontok valószínűségét, ezért úgy tűnik, hogy a maximum likelihood elvet sem tudjuk használni a paraméterek becslésére. Erre a problémára az EM algoritmus a megoldás, amit a.9.2. algoritmus mutat be. Röviden, ha van egy becslésünk a paraméterértékekre, az EM algoritmus kiszámolja annak a valószínűségét, hogy a pontok az egyes eloszlásokhoz tartoznak, majd ezeket a valószínűségeket használja a paraméterek új becsléséhez. (Ezek a paraméterek maximalizálják a likelihoodot.) Ezt az iterációt addig folytatjuk, míg a paraméterbecslések vagy nem változnak, vagy csak nagyon kicsit. Tehát továbbra is a maximum likelihood becslést használjuk, de egy iteratív keresésen keresztül.

[1]

Az EM algoritmus hasonló a 8.2.1. szakaszban megadott K -közép algoritmushoz. Valójában, euklideszi adatokra a K -közép algoritmus speciális esete az EM algoritmusnak, térbeli, azonos kovarianciamátrixú, de különböző várható értékű Gauss eloszlásokkal. Az E lépés megfelel annak a K -közép lépésnek, amelyben minden objektumot egy klaszterbe sorolunk. Ehelyett minden objektumot valamilyen valószínűséggel rendelünk az egyes klaszterekhez (eloszlásokhoz). Az M lépés megfelel a klaszterközéppontok kiszámításának. Ehelyett az eloszlások paramétereit és a súlyparamétereket is úgy választjuk, hogy maximalizálják a likelihoodot. Ez az eljárás gyakran magától értetődő, mert a paramétereket tipikusan a maximum likelihood becslésből származó képletekkel lehet számolni. Egyetlen Gauss eloszlásra például a várható érték ML becslése az eloszlásból származó objektumok átlaga. A keverék modellek és az EM algoritmus esetén az átlag számítását módosítani kell amiatt a tény miatt, hogy minden objektum csak bizonyos valószínűséggel tartozik egy eloszláshoz. Ezt szemlélteti tovább a következő példa.

9.4. Példa.

(Egyszerű példa az EM algoritmusra) Ez a példa mutatja, hogyan működik az EM algoritmus a 9.2. ábra adataira. Azért, hogy a példa a lehető legegyszerűbb legyen, feltesszük, hogy tudjuk, hogy mindkét eloszlás szórása 2,0 , és hogy a pontokat a két eloszlásból egyenlő valószínűséggel generáltuk. A baloldali és a jobboldali eloszlásra 1-es illetve 2-es eloszlásként hivatkozunk.

Az EM algoritmust a μ 1 és μ 2 paraméterekre vonatkozó kezdeti becslések megadásával kezdjük, legyen például μ 1 =−2 és μ 2 =3 . Így a kezdeti θ=(μ,σ) paraméterek a két eloszlásra θ 1 =(−2;2) illetve θ 2 =(3;2) . Az egész keverék paraméterei Θ={ θ 1 , θ 2 } . Az EM E lépésében ki szeretnénk számolni annak a valószínűségét, hogy egy pont adott eloszlásból származik, azaz P(1.eloszlás| x i ,Θ) és P(2.eloszlás| x i ,Θ) értékét. Ezeket az értékeket a következő egyenletből fejezhetjük ki, ami a Bayes szabály magától értetődő alkalmazása (lásd 13. függeléket):

P(j.eloszlás| x i ,θ)= 0,5P( x i | θ j ) 0,5P( x i | θ 1 )+0,5P( x i | θ 2 ) , (9.13)

ahol 0,5 az egyes eloszlások valószínűsége (súlya), j pedig 1 vagy 2.

Tegyük fel például, hogy az egyik pont a 0. (9.7) képlettel megadott Gauss sűrűségfüggvény alapján ki tudjuk számolni, hogy P(0| θ 1 )=0,12 és P(0| θ 2 )=0,06 . (Valójában ismét valószínűségi sűrűségeket számolunk.) Ezeket az értékeket és (9.13) képletet használva azt kapjuk, hogy P(1.eloszlás|0,Θ)=0,12/(0,12+0,06)=0,67 és hogy P(2.eloszlás|0,Θ)=0,06/(0,12+0,06)=0,33 . Ez azt jelenti, hogy a paraméterértékekre vonatkozó aktuális feltételezések mellett a 0 kétszer akkora eséllyel tartozik az 1-es eloszláshoz, mint a 2-eshez.

A klaszterhez tartozási valószínűséget mind a 20 000 pontra kiszámolva új becsléseket számolunk μ 1 -re és μ 2 -re (a (9.14) és (9.15) képleteket használva) az EM algoritmus M (maximalizáló) lépésénél. Jegyezzük meg, hogy az eloszlás várható értékére az új becslés éppen a pontok súlyozott átlaga, ahol a súlyok a pontok adott eloszláshoz tartozásának a valószínűségei, azaz a P( j .eloszlás| x i ) értékek.

μ 1 = ∑ i=1 20000 x i P(1.eloszlás| x i ,Θ) ∑ i=1 20000 P(1.eloszlás| x i ,Θ) (9.14)

μ 2 = ∑ i=1 20000 x i P(2.eloszlás| x i ,Θ) ∑ i=1 20000 P(2.eloszlás| x i ,Θ) (9.15)

Addig ismételjük ezt a két lépést, amíg a μ 1 és μ 2 becslései vagy nem változnak, vagy csak nagyon kicsit. A 9.1. táblázat az EM algoritmus első néhány lépését adja meg, amikor azt a 20 000 pontból álló halmazra alkalmazzuk. Erre az adatsorra tudjuk, hogy melyik eloszlás melyik pontot generálta, így mindkét eloszlásra ki tudjuk számolni a pontok átlagát is: μ 1 =−3,98 és μ 2 =4,03 .

9.5. Példa.

(Az EM algoritmus minta adathalmazokon) Három példát mutatunk be, amelyek az EM algoritmus keverék modellek használatával történő alkalmazását szemléltetik klaszterek megtalálására. Az első példa a fuzzy c -közép algoritmus szemléltetésére használt adatokon alapul (lásd a 9.1. ábrát). Ezeket az adatokat három, különböző várható értékű és megegyező kovarianciamátrixú kétdimenziós Gauss eloszlás keverékével modelleztük. Ezután az adatokat az EM algoritmus segítségével klasztereztük. Az eredményeket a 9.4. ábra mutatja. Minden pontot ahhoz a klaszterhez rendeltük hozzá, amelynél a legnagyobb volt a tagsági súlya. Az egyes klaszterekhez tartozó pontokat különböző alakú jelek ábrázolják, míg a klaszterhez tartozás fokát a színezés mutatja. A klaszterhez tartozás viszonylag gyenge azokra a pontokra, amelyek két klaszter határán helyezkednek el, de erős máshol. Érdekes összehasonlítani a tagsági súlyokat és a valószínűségeket a 9.4. és a 9.1. ábrákon. (Lásd a 11. feladatot a 670. oldalon.)

Második példánkban a keverék modell klaszterezést olyan adatokra alkalmazzuk, amelyek különböző sűrűségű klasztereket tartalmaznak. Az adatok két természetes klaszterből állnak, mindegyik nagyjából 500 pontot tartalmaz. Ezeket az adatokat két Gauss eloszlású adathalmaz kombinálásával állítottuk elő, az egyik középpontja (−4;1) , szórása 2, a másik középpontja (0;0) , szórása pedig 0,5 . A 9.5. ábra mutatja az EM algoritmus által eredményezett klaszterezést. A sűrűségkülönbségek ellenére az EM algoritmus meglehetősen sikeres az eredeti klaszterek azonosításában.

Harmadik példánkban a keverék modell klaszterezést egy olyan adathalmazra alkalmazzuk, amit a K -közép nem tud megfelelően kezelni. A 9.6. (a) ábra mutatja a keverék modell algoritmus által előállított klaszterezést, míg a 9.6. (b) ábra ugyanennek az 1000 pontnak a K -közép klaszterezését. A keverék modell klaszterezésnél minden pontot ahhoz a klaszterhez rendeltük, amelynek a legnagyobb a valószínűsége. Mindkét ábrán különböző jeleket használtunk a klaszterek megkülönböztetésére. Ne keverjük össze a ``+'' és ``x'' jeleket a 9.6. (a) ábrán.

Az EM algoritmust használó keverék modell klaszterezés előnyei és korlátai

Számos előnye és hátránya van annak a klaszterező megközelítésnek, amely az adatokat keverék modellekkel írja le, és ezen modellek paramétereit EM algoritmussal becsli. A negatív oldalon szerepel, hogy az EM algoritmus lassú lehet, nem praktikus nagy számú komponenst tartalmazó modellek esetén, és nem működik jól, amikor a klaszterek csak néhány adatpontot tartalmaznak, vagy amikor az adatpontok közel kollineárisak. A klaszterszám becslése, vagy általánosabban a használt modell pontos formájának meghatározása is problémát jelent. Ezt a problémát tipikusan a Bayes-féle megközelítés alkalmazásával oldják meg, ami lényegében egy modell esélyét adja meg egy másikhoz képest az adatokból kapott becslés alapján. A keverék modelleknek nehézséget okozhatnak a zaj és a kiugró értékek is, bár születtek eredmények ezen problémák megoldása irányában.

Előnyük, hogy a keverék modellek általánosabbak, mint a K -közép vagy a fuzzy c -közép, mert különböző eloszlástípusokat tudnak használni. Ennek eredményeként a (Gauss eloszláson alapuló) keverék modellek meg tudják találni a különböző méretű és tojásdad alakú klasztereket. A modell-alapú megközelítés az adatokban rejlő bonyolultság egy részének megalapozott eltávolítására is módot ad. Az adatokban rejlő mintázatok feltárásához gyakran szükséges az adatok egyszerűsítése, és erre jó az adatok egy megfelelő modellhez való illesztése. Könnyű továbbá jellemezni a kapott klasztereket, mivel néhány paraméterrel írhatóak le. Végül, sok adathalmaz valóban véletlen folyamat eredménye és ezért ki kell elégíteniük ezen modellek statisztikai feltevéseit.

A Kohonen-féle önszervező jellemzőháló (SOFM vagy SOM -- Self-Organizing Feature Map) egy neurális háló nézőpontú klaszterező és adatvizualizációs módszer. Neurális hálós eredete ellenére a SOM könnyebben ismertethető -- legalábbis ennek a szakasznak a szövegkörnyezetében -- a prototípus-alapú klaszterezés egy változataként. A középpont-alapú klaszterezés más típusaihoz hasonlóan a SOM célja a középpontok (a SOM terminológiában referencia vektorok) egy halmazának kijelölése és az adathalmaz minden egyes objektumának hozzárendelése ahhoz a középponthoz, amelyik az adott objektum legjobb approximációját adja. Neurális háló terminológiában fogalmazva minden egyes középponthoz egy neuron tartozik.

Az növekményes K -középhez hasonlóan itt is egyesével dolgozzuk fel az adatobjektumokat és a legközelebbi középpontot frissítjük. A K -középpel ellentétben a SOM a középpontok egy topografikus rendezését írja elő és a közeli középpontokat is frissíti. A SOM nem tartja nyilván továbbá egy objektum aktuális klaszterét és a K -középpel ellentétben nem frissíti explicit módon a régi klaszterközéppontot, ha egy objektum klasztert vált. A régi klaszter természetesen lehet az új klaszter szomszédságában, ezért frissítésre kerülhet. A pontok feldolgozása addig folytatódik, amíg el nem érünk valamilyen előre meghatározott határértéket, vagy a középpontok már nem változnak sokat. A SOM módszer végső eredménye a középpontok halmaza, amely implicit módon definiálja a klasztereket. Minden egyes klaszter az adott középponthoz legközelebbi pontokból áll. A következő szakasz ennek a folyamatnak a részleteit vizsgálja.

A SOM algoritmus

A SOM ismertetőjele, hogy a középpontok (neuronok) topografikus (térbeli) szerveződését írja elő. A 9.7. ábra egy kétdimenziós SOM-ra mutat példát, ahol a középpontokat négyzetrács szerkezetbe rendezett csomópontok reprezentálják. Minden középponthoz egy (i,j) koordinátapárt rendelünk hozzá. Egy ilyen hálózatot néha úgy rajzolnak fel, hogy összekötik a szomszédos csomópontokat, de ez félrevezető lehet, mert egy középpont hatása egy másikra a koordináták, nem pedig a kapcsolatok segítségével van definiálva. Sok típusa van a SOM neurális hálóknak, de mi a tárgyalásunkat a kétdimenziós, a középpontokat négyzetrácsba vagy hatszögrácsba szervező SOM-okra korlátozzuk.

Bár a SOM hasonló a K -középhez vagy más prototípus-alapú megközelítésekhez, van egy alapvető különbség. A SOM-ban használt középpontoknak egy előre meghatározott topográfiai rendezési kapcsolatrendszere van. A tanulási folyamat során a SOM minden adatpontot felhasznál a legközelebbi középpont és a topográfiai rendezés szerint közeli középpontok frissítésénél. A SOM ilyen módon középpontok egy rendezett halmazát állítja elő minden adathalmazra. Más szavakkal, azok a középpontok, amelyek egymáshoz közel vannak a SOM rácsában, szorosabb kapcsolatban vannak egymással, mint a távolabbi középpontok. Emiatt a megszorítás miatt a kétdimenziós SOM középpontjait úgy lehet tekinteni, mint amelyek egy, az n -dimenziós adatokra a lehető legjobban illeszkedő kétdimenziós felületen helyezkednek el. A SOM középpontokra az adatpontokra vonatkozó nemlineáris regresszió eredményeként is gondolhatunk.

Magasabb szinten a SOM módszert használó klaszterezés 9.2. algoritmusban leírt lépésekből áll.

Kezdőértékadás

Ez a lépés (1. sor) többféleképpen hajtható végre. Az egyik megközelítés az, hogy egy középpont minden egyes koordinátáját véletlenszerűen választjuk az illető koordináta adatokban megfigyelt értékeinek tartományából. Bár ez a megközelítés működik, nem szükségszerűen a legjobb eljárás, különösen akkor nem, ha gyors konvergenciát szeretnénk. Egy másik módszer a kezdeti középpontok véletlenszerű választása a rendelkezésre álló adatpontok közül. Ez nagyon hasonló a K -közép módszer véletlenszerű középpont-választásához.

Az objektum kiválasztása

A ciklus első lépése (3. sor) a következő objektum kiválasztása. Ez meglehetősen magától értetődő, de van néhány nehézség. Mivel a konvergenciához sok lépésre lehet szükség, minden adatobjektumot többször kellhet használni, különösen akkor, ha kicsi az objektumok száma. Ha viszont nagy az objektumok száma, akkor nem minden objektumot szükséges használni. Az objektumok bizonyos csoportjainak hatását is lehet növelni a tanulóhalmazbeli gyakoriságuk növelésével.

Besorolás

A legközelebbi középpont meghatározása (4. sor) szintén magától értetődő, bár szükség van hozzá egy távolság-metrika megadására. Gyakran használjuk az euklideszi távolság-metrikát, ahogy a skalárszorzat metrikát is. Amikor a skalárszorzat metrikát alkalmazzuk, az adatvektorokat előzőleg tipikusan normáljuk, a referenciavektorokat viszont minden egyes lépésben normáljuk. Ezekben az esetekben a skalárszorzat metrika alkalmazása ekvivalens a koszinusz mérték használatával.

Frissítés

A frissítési lépés (5. sor) a legbonyolultabb. Legyenek m 1 ,…, m k a középpontok. (Megjegyezzük, hogy egy négyzetrács esetén k a sorok számának és az oszlopok számának a szorzata.) A t -edik lépésben legyen p(t) az aktuális objektum (pont) és tegyük fel, hogy m j a p(t) -hez legközelebbi középpont. Ekkor a (t+1) -edik időpillanatban a következő összefüggés segítségével frissítjük a j -edik középpontot. (Rövidesen látni fogjuk, hogy a frissítés valójában azokra a középpontokra korlátozódik, amelyek neuronjai m j egy kis környezetében vannak.)

m j (t+1)= m j (t)+ h j (t)(p(t)− m j (t)) (9.16)

Azaz a t -edik időpontban az m j (t) középpontot egy h j (t)(p(t)− m j (t)) tag hozzáadásával frissítjük, ami a p(t) aktuális objektum és az m j (t) középpont közötti p(t)− m j (t) eltéréssel arányos. A h j (t) határozza meg a p(t)− m j (t) különbség hatását, és úgy kell megválasztani, hogy (1) csökkenjen az idő függvényében és (2) kikényszerítse a szomszédsági hatást, azaz azt, hogy egy objektum hatása az m j középponthoz legközelebbi középpontokra legyen a legerősebb. Itt a rácsbeli távolságra, nem pedig az adattérbeli távolságra gondolunk. A h j (t) -t tipikusan az alábbi két függvény valamelyikének választjuk:

h j (t)=α(t)exp(−dist ( r j , r k ) 2 /(2 σ 2 (t))    (Gauss függvény)

h j (t)=α(t),had( r j , r k )≤küszöb,0 egyébként        (lépcsős függvény)

Ezek a függvények bővebb magyarázatot igényelnek. Az α(t) a tanulási tényező paraméter, ahol 0≤α(t)≤1 , és amely monoton csökken az idő függvényében és a konvergencia sebességét szabályozza. Az r k =( x k , y k ) a k -adik középpont rácskoordinátáit megadó kétdimenziós pont, d( r j , r k ) pedig a két középpont rácsbeli helyének euklideszi távolsága, azaz ( x j − x k ) 2 + ( y j − y k ) 2 . Következésképpen azokra a középpontokra, amelyek rácshelye távol van az m j középpont rácshelyétől, a p(t) objektum hatása nagyon lecsökken vagy megszűnik. Végül megjegyezzük, hogy σ a tipikus Gauss-féle szórás paraméter, ami a szomszédság szélességét szabályozza, azaz kis σ kicsi környezetet eredményez, míg egy nagy σ széles környezetet. A lépcsős függvényhez használt küszöbérték szintén a környezet méretét határozza meg.

Ne felejtsük el, hogy a szomszédság frissítési módszer az, ami kikényszeríti a szomszédos neuronokhoz tartozó középpontok közötti kapcsolatot (rendezést).

Leállás

Egy fontos kérdés annak eldöntése, hogy mikor vagyunk elég közel a középpontok egy stabil halmazához. Az iterációnak elméletileg addig kellene folytatódnia, amíg be nem következik a konvergencia, azaz addig, amikor a referencia vektorok már nem változnak, vagy csak nagyon keveset. A konvergencia sebessége több tényezőtől is függ, így például az adatoktól és az α(t) -tól. Nem tárgyaljuk tovább ezeket a kérdéseket, kivéve azt a megjegyzést, hogy a konvergencia általában lassú lehet és nem is mindig garantált.

9.6. Példa.

(Dokumentum-adatok) Két példát mutatunk be. Az elsőben a SOM módszert egy 4×4 -es hatszög alapú ráccsal dokumentum adatokra alkalmazzuk. A Los Angeles Times 3204 újságcikkét klasztereztük, melyek 6 különböző rovatból származnak (szórakozás, pénzügy, külügy, hely, belügy és sport). A 9.8. ábra mutatja a SOM rácsot. Hatszögű rácsot használtunk, amely lehetővé teszi, hogy minden középpontnak hat közvetlen szomszédja legyen négy helyett. Minden SOM rácscellát (klasztert) a hozzárendelt pontok többségi osztálycímkéjével jelöltük meg. Minden egyes kategória klaszterei összefüggő csoportokat alkotnak, és a többi klaszter kategóriához képest elfoglalt relatív helyzetük további információkat nyújt, például azt, hogy a helyi rovat az összes többi rovathoz kapcsolódó cikkeket tartalmaz.

9.7. Példa

(Kétdimenziós pontok) A második esetben egy négyzetrács alapú SOM-ot és egy kétdimenziós ponthalmazt használunk. A 9.9. (a) ábra mutatja a pontokat és a SOM által előállított (x-ekkel ábrázolt) 36 referencia vektor elhelyezkedését. A pontok sakktábla-szerűen helyezkednek el és öt csoportba soroljuk őket: körök, háromszögek, négyzetek, rombuszok és hatszögek (csillagok). A középpontok egy 6×6 -os kétdimenziós négyzetrácsát használtuk véletlenszerű inicializálással. Ahogy azt a 9.9. (a) ábra mutatja, a középpontok a sűrű területekre helyezik el magukat. A 9.9. (b) ábra az adott középponthoz tartozó pontok többségi osztályát mutatja. A háromszög jelű pontoknak megfelelő klaszterek egy összefüggő részben vannak, éppen úgy, ahogy a másik négy fajta pontnak megfelelő klaszterek. Ez a SOM által kikényszerített szomszédsági megszorítások eredménye. Bár mind az öt csoportban ugyanannyi pont van, vegyük észre, hogy a középpontok nem egyenletesen oszlanak el. Ez köszönhető részben a pontok általános eloszlásának, részben pedig egy technikai hibának, miszerint minden egyes középpontot egy külön klaszterbe tettünk.

Alkalmazások

Ha már megtaláltuk a SOM vektorokat, a klaszterezésen kívül sok más célra is használhatjuk őket. Egy kétdimenziós SOM segítségével például különböző mennyiségeket lehet hozzárendelni az egyes középpontokhoz (klaszterekhez) tartozó rácspontokhoz, az eredményeket pedig különböző típusú ábrák segítségével lehet megjeleníteni. Az egyes klaszterekhez tartozó pontok számát kirajzolva például egy olyan ábrát kapunk, ami a pontok klaszterek közötti eloszlását fedi fel. A kétdimenziós SOM az eredeti valószínűségeloszlás-függvény egy két dimenzióra történő nemlineáris vetítése. Ez a projekció megkísérli a topológiai jellemzők megőrzését, így a SOM az adatok szerkezetének megőrzésére irányuló felhasználását egy virág lepréselésének folyamatához hasonlíthatjuk.

Erősségek és korlátok

A SOM olyan klaszterező módszer, amely szomszédsági kapcsolatokat kényszerít ki az eredményül kapott klaszterközéppontok között. Emiatt azok a klaszterek, amelyek szomszédok, szorosabb kapcsolatban állnak egymással, mint azok, amelyek nem. Az ilyen kapcsolatok megkönnyítik a klaszterezés eredményének értelmezését és megjelenítését. A SOM ezen aspektusát valóban sok területen aknázták ki, mint például webes dokumentum vagy génszekvencia adatok megjelenítése.

A SOM-nak számos korlátja is van, ezeket soroljuk fel az alábbiakban. A felsorolt korlátok némelyike csak akkor érvényes, ha a SOM-ot standard klaszterező módszernek tekintjük, amelynek az adatok valódi klasztereinek megtalálása a célja, nem pedig a klaszterezést az adatok szerkezetének feltárásához felhasználó módszernek. Ezen korlátok közül néhánnyal a SOM kiterjesztései vagy a SOM által inspirált klaszterező algoritmusok foglalkoznak. (Lásd az irodalmi megjegyzéseket.)