9. fejezet - Klaszteranalízis: További kérdések és algoritmusok
Vissza		Előre

9. fejezet - Klaszteranalízis: További kérdések és algoritmusok

Tartalom

Nagyszámú klaszterező algoritmust fejlesztettek ki különböző alkalmazási területekre. Ezen algoritmusok egyike sem alkalmas minden adat-, klaszter- és alkalmazás-típusra. Valójában úgy tűnik, hogy mindig marad tér az új klaszterező algoritmusoknak, amelyek hatékonyabbak, vagy jobban illeszkednek speciális adattípusokra, klaszterekre vagy alkalmazásokra. Ehelyett csak azt állíthatjuk, hogy olyan módszereink vannak, amelyek jól működnek bizonyos helyzetekben. Ennek az az oka, hogy sokszor szubjektív interpretáción múlik, hogy mit tekintünk jó klaszterhalmaznak. Továbbá, ha egy objektív mérőszámot alkalmazunk a klaszter precíz definíciójaként, akkor az optimális klaszterezés megtalálásának problémája gyakran megvalósíthatatlanul számításigényes.

Ez a fejezet a klaszteranalízis fontos kérdéseire koncentrál, és feltárja azokat a fogalmakat és megközelítéseket, amelyeket a megoldásukra fejlesztettek ki. A klaszteranalízis azon kulcskérdéseinek -- úgymint az adatok jellemzőinek, a klasztereknek és az algoritmusoknak -- a tárgyalásával kezdünk, amelyek erősen hatnak a klaszterezésre. Ezek a kérdések fontosak a klaszterező módszerek megértéséhez, leírásához és összehasonlításához, és annak a döntésnek az alapjául szolgálnak, hogy adott helyzetben melyik módszert is használjuk. Sok klaszterező algoritmus tár- vagy időbonyolultsága például O( m 2 ) ( m az objektumok száma), és így nem alkalmas nagy adathalmazokra. Ezek után további klaszterező módszereket tárgyalunk. Minden eljárásra megadjuk az algoritmust, beleértve, hogy milyen kérdéseket céloz meg, és hogy milyen módszereket használ a megoldásukra. A fejezetet az adott alkalmazáshoz megfelelő klaszterező algoritmus kiválasztására vonatkozó néhány általános irányelv megfogalmazásával zárjuk.

Az adatok, klaszterek és klaszterező algoritmusok jellemzői

Ez a szakasz az adatok, klaszterek és algoritmusok jellemzőihez kapcsolódó azon kérdéseket vizsgálja meg, amelyek fontosak a klaszteranalízis átfogó megértéséhez. Néhány ilyen kérdés, mint például a zaj és a kiugró értékek kezelése, kihívást is jelent. Más kérdések az egyes algoritmusoktól elvárt tulajdonságokra vonatkoznak, mint például annak a képessége, hogy ugyanazt az eredményt adják attól függetlenül, hogy az adatobjektumokat milyen sorrendben dolgozzuk fel. Ennek a szakasznak a tárgyalása, a különböző típusú klaszterezések a 8.1.2. szakaszban és a különböző klasztertípusok a 8.1.3. szakaszban bemutatott tárgyalásával együtt, több olyan ``dimenziót'' azonosít, amelyek használhatóak különböző klaszterező algoritmusok és az általuk előállított klaszterezések leírására és összehasonlítására. Ennek szemléltetéséhez a szakaszt egy példával kezdjük, ami az előző fejezetben bemutatott két klaszterező algoritmust, a DBSCAN-t és a K -közép eljárást hasonlítja össze. Ezt követi a klaszteranalízist befolyásoló adat-, klaszter- és algoritmus jellemzők részletes leírása.

Példa: a K -közép és DBSCAN összehasonlítása

Egyszerűsítendő az összehasonlítást, feltesszük, hogy nincsenek egyezések sem a K -közép, sem a DBSCAN által használt távolságértékek között, és hogy a DBSCAN mindig a legközelebbi belső ponthoz rendel hozzá egy olyan határpontot, amelyik több belső ponthoz is tartozik.

A DBSCAN és a K -közép egyaránt felosztó klaszterező algoritmusok, amelyek minden objektumot egy klaszterhez rendelnek, de a K -közép tipikusan minden objektumot klaszterez, míg a DBSCAN kihagyja azokat az objektumokat, amiket zajnak osztályoz.
A K -közép prototípus-alapú, míg a DBSCAN sűrűség-alapú klaszterfogalmat használ.
A DBSCAN különböző méretű és alakú klasztereket is kezelni tud, és nem különösebben érzékeny a zajra vagy a kiugró értékekre. A K -középnek nehézséget okoznak a nem gömb alakú klaszterek és a különböző méretű klaszterek. Mindkét algoritmus rosszul tud teljesíteni, ha a klaszterek nagyon különböző sűrűségűek.
A K -közepet csak olyan adatokra lehet használni, amelyeknek jól definiált középértéke van, mint például az átlag vagy a medián. A DBSCAN megköveteli, hogy értelmes legyen az adatokra a hagyományos euklideszi sűrűségfogalomra épülő sűrűség definíciója.
A K -közép alkalmazható ritka, sokdimenziós adatokra, mint például a dokumentum adatok. A DBSCAN tipikusan gyengén teljesít ilyen adatokon, mert a hagyományos euklideszi sűrűségfogalom nem működik jól sokdimenziós adatokra.
A K -közép és DBSCAN eredeti változatait euklideszi adatokra dolgozták ki, de mindkettőt kiterjeszették más típusú adatok kezelésére is.
A DBSCAN nem feltételez semmit az adatok eloszlásáról. Az elemi K -közép algoritmus ekvivalens azzal a statisztikai klaszterező megközelítéssel (keverék modell), ami feltételezi, hogy minden klaszter különböző várható értékű, de azonos kovarianciamátrixú szferikus Gauss eloszlásból származik. (Lásd a 9.2.2. szakaszt.)
A DBSCAN és a K -közép is úgy keres klasztereket, hogy minden attribútumot felhasználnak, azaz nem keresnek olyan klasztereket, amelyek csak az attribútumok egy részhalmazán alapulnak.
A K -közép meg tud találni olyan klasztereket, amelyek nem különülnek el jól, még akkor is, ha átfedőek (lásd a 8.2. (b) ábrát), azonban a DBSCAN összevonja az átfedő klasztereket.
A K -közép algoritmus időbonyolultsága O(m) , míg a DBSCAN O( m 2 ) időt igényel, eltekintve olyan speciális esetektől, mint például az alacsony dimenziós euklideszi adatok.
A DBSCAN futásról futásra ugyanazokat a klasztereket állítja elő, viszont a K -közép, amit tipikusan a középpontok véletlenszerű inicializásával használunk, nem.
A DBSCAN automatikusan meghatározza a klaszterek számát, a K -középnél a klaszterek számát paraméterként kell megadni. A DBSCAN-nek viszont két másik paramétere van ( Eps és MinPts ), amelyeket meg kell adni.
A K -közép klaszterezés tekinthető optimalizációs problémaként is -- azaz minimalizáljuk a pontoknak a legközelebbi középponttól vett négyzetes hibaösszegét --, és egy statisztikai klaszterező megközelítés különleges eseteként is (keverék modellek). A DBSCAN nem alapul semmilyen formális modellen.

Adatjellemzők

A következők olyan adatjellemzők, amelyek jelentősen befolyásolják a klaszteranalízist.

Nagy dimenziószám

Sokdimenziós adatokra értelmetlenné válik a hagyományos euklideszi sűrűségfogalom, az egységnyi térfogatra eső pontok száma. Hogy ezt belássuk, vegyük figyelembe, hogy a dimenziószám növekedtével a térfogat gyorsan nő, és hacsak a pontok halmaza nem nő exponenciálisan a dimenziószámmal, a sűrűség 0-hoz tart. (A térfogat exponenciális a dimenziószám függvényében. Egy r sugarú és d dimenziós hipergömb például r d -vel arányos térfogatú.) A szomszédság is egyre egyenletesebb lesz sokdimenziós terekben. Ezt a tényt más oldalról tekintve, több dimenzió (attribútum) járul hozzá két pont szomszédságához, és ez egyenletesebbé teszi a szomszédság-értékeket. Mivel a legtöbb klaszterező eljárás szomszédság- vagy sűrűség-alapú, gyakran nehézséget jelenthetnek számukra a sokdimenziós adatok. Az ilyen problémák kezelésének egyik módja dimenziócsökkentési módszerek alkalmazása. Egy másik megközelítés a közelség és a sűrűség fogalmának újradefiniálása, amit a 9.4.5. és a 9.4.7. szakaszok tárgyalnak.

Méret

Sok klaszterező algoritmus, ami jól működik kicsi vagy közepes méretű adathalmazokon, nem képes nagyobb adathalmazok kezelésére. Ezt a kérdést tovább vizsgáljuk a klaszterező algoritmusok jellemzőinek tárgyalásánál -- a skálázhatóság egy ilyen karakterisztika -- és a skálázható klaszterező algoritmusokat tárgyaló a 9.5. szakaszban.

Ritkaság

A ritka adatok gyakran aszimmetrikus attribútumokból állnak, ahol a nulla értékek nem olyan fontosak, mint a nullától különböző értékek. Ezért rendszerint olyan hasonlósági mértékeket használunk, melyek megfelelőek aszimmetrikus attribútumokhoz. Viszont felmerülnek további kapcsolódó kérdések is. Például, hogy lényeges-e a nem nulla értékek nagysága, vagy ezek eltorzítják a klaszterezést? Más szavakkal, a klaszterezés akkor működik-e a legjobban, ha csak két érték van, a 0 és az 1?

Zaj és kiugró értékek

Egy nem tipikus pont (kiugró érték) gyakran jelentősen le tudja rontani a klaszterező algoritmusok teljesítményét, különösen az olyan prototípus-alapú algoritmusokét, mint például a K -közép. Másrészt a zaj olyan klaszterek összevonását eredményezheti az olyan módszereknél, mint például az egyszerű kapcsolás, amiket nem kellene összevonni. Néhány esetben a zajt és kiugró értékeket eltávolító algoritmusokat alkalmazunk a klaszterező algoritmusok használata előtt. Más lehetőségként néhány algoritmus észlelni tudja a klaszterezési folyamat során a zajnak és kiugró értékeknek minősülő pontokat, ezután pedig törli őket, vagy más módon szünteti meg negatív hatásaikat. Az előző fejezetben láttuk például, hogy a DBSCAN zajként osztályozza az alacsony sűrűségű pontokat és kihagyja őket a klaszterezés folyamatából. A Chameleon (9.4.4. szakasz), az SNN sűrűség-alapú klaszterezés (9.4.8. szakasz) és a CURE (9.5.3. szakasz) három olyan algoritmus ebben a fejezetben, amelyek a klaszterezés során explicit módon foglalkoznak a zajjal és a kiugró értékekkel.

Az attribútumok és adathalmazok típusai

Ahogy a 2. fejezetben tárgyaltuk, az adathalmazok különböző típusúak lehetnek, mint például strukturáltak, gráfok vagy rendezettek, míg az attribútumok lehetnek kategorikusak (nominálisak vagy ordinálisak) vagy kvantitatívak (intervallum vagy arány típusúak), valamint binárisak, diszkrétek vagy folytonosak. Különböző szomszédsági és sűrűségmértékek megfelelőek a különböző adattípusokhoz. Egyes esetekben az adatok diszkretizálása vagy binarizálása lehet szükséges, hogy a kívánt szomszédsági mérték vagy klaszterező algoritmus használható legyen. További komplikációt jelenthet, ha az attribútumok nagyon különböző típusúak, például folytonosak és nominálisak. A szomszédságot és a sűrűséget sokkal nehezebb definiálni ilyen esetekben és ekkor gyakran ad hoc jellegűek. Végül speciális adatszerkezetekre és algoritmusokra lehet szükség bizonyos adattípusok hatékony kezeléséhez.

Skála

A különböző attribútumok, például a magasság és a súly, különböző skálákon mérhetőek. Ezek a különbségek erősen befolyásolhatják a két objektum közötti távolságot vagy hasonlóságot, következésképpen a klaszteranalízis eredményét is. Tekintsük egy embercsoport klaszterezését a méterben mért magasságuk és kilogrammban mért súlyuk alapján. Ha euklideszi távolságot használunk szomszédsági mértékként, akkor a magasságnak kis hatása lesz és az emberek főleg a súly attribútum alapján fognak klasztereződni. Ha viszont standardizáljuk az egyes attribútumokat, levonva belőlük az átlagukat és elosztva őket a szórásukkal, akkor elimináljuk a skálák különbözőségéből adódó hatásokat. Általánosabban a normalizáló eljárásokat, például a 2.3.7. szakaszban tárgyaltakat, használják tipikusan ezen problémák kezelésére.

Az adattér matematikai tulajdonságai

Bizonyos klaszterező eljárások pontcsoportok átlagát számítják ki vagy olyan egyéb matematikai műveletet használnak, amelyeknek csak az euklideszi térben vagy más speciális adatterekben van értelme. Más algoritmusoknak arra van szükségük, hogy a sűrűség definíciója értelmes legyen az adatokra.

Klaszterjellemzők

A különböző klasztertípusokat, mint a prototípus-, gráf- és sűrűség-alapú, a 8.1.3. szakaszban korábban tárgyaltuk. Most a klaszterek egyéb fontos jellemzőit írjuk le.

Adateloszlás

Bizonyos klaszterező eljárások speciális eloszlást feltételeznek az adatokon. Konkrétabban, gyakran feltételezik azt, hogy az adatok eloszlások keverékéből származóként modellezhetőek, ahol minden klaszter egy eloszlásnak felel meg. A keverék modelleken alapuló klaszterezést a 9.2.2. szakasz tárgyalja.

Alak

Néhány klaszter szabályos alakú, például téglalap vagy gömb alakú, de a klaszterek általában tetszőleges alakúak lehetnek. Az olyan módszerek, mint a DBSCAN és az egyszerű kapcsolás, tetszőleges alakú klasztereket tudnak kezelni, de a prototípus-alapú sémák és néhány hierarchikus eljárás, mint például a teljes kapcsolás és csoportátlag, erre már nem képesek. A Chameleon (9.4.4. szakasz) és a CURE (9.5.3. szakasz) olyan eljárásokra példák, amiket kifejezetten ennek a problémának a kezelésére terveztek.

Különböző méretek

Sok klaszterező eljárás, mint például a K -közép, nem működik jól, ha a klaszterek különböző méretűek. (Lásd a 8.2.4. szakaszt.) Ezt a témát tárgyalja tovább a 9.6. szakasz.

Különböző sűrűségek

A széles skálán változó sűrűségű klaszterek problémákat okozhatnak az olyan módszereknek, mint a DBSCAN és a K -közép. Az SNN sűrűség-alapú klaszterező eljárás foglalkozik ezzel a kérdéssel, amelyet a 9.4.8. szakasz mutat be.

Gyengén elkülönülő klaszterek

Ha a klaszterek érintkeznek vagy átfedőek, akkor néhány klaszterező eljárás összevon olyan klasztereket, amelyeket különállóként kellene tartani. Még a különálló klasztereket kereső módszerek is tetszőlegesen rendelnek hozzá pontokat az egyik vagy a másik klaszterhez. A fuzzy klaszterezés, amit a 9.2.1. szakaszban mutatunk be, az egyik olyan adatokra alkalmas módszer, amelyek nem alkotnak jól elkülönülő klasztereket.

Klaszterek közötti kapcsolatok

A legtöbb klaszterező eljárás nem veszi explicit módon figyelembe a klaszterek közötti olyan kapcsolatokat, mint például a relatív helyzetük. A 9.2.3. szakaszban bemutatásra kerülő önszervező háló (SOM -- self-organizing map) olyan klaszterező eljárás, amely a klaszterezés folyamatában közvetlenül figyelembe veszi a klaszterek közötti kapcsolatokat. Speciálisan, egy pont egy klaszterhez történő hozzárendelése befolyásolja a közeli klaszterek definícióját.

Altér klaszterek

Előfordulhat, hogy a klaszterek csak a dimenziók (attribútumok) egy részhalmazán léteznek, és a dimenziók egyik részhalmazán meghatározott klaszterek elég különbözőek lehetnek egy másik részhalmaz alapján meghatározott klaszterekhez képest. Bár ez a probléma felléphet már két dimenzióban is, sokkal kiélezettebbé válik a dimenziószám növekedtével, mert a dimenziók lehetséges részhalmazainak száma exponenciálisan nő a dimenziószám függvényében. Emiatt nem lehetséges egyszerűen a dimenziók minden lehetséges részhalmazára megkeresni a klasztereket, kivéve ha a dimenziószám viszonylag kicsi.

Egy megközelítés a jellemzők kiválasztása, amit a 2.3.4. szakaszban tágyaltunk. Viszont ez a megközelítés feltételezi, hogy a dimenzióknak csak egy olyan részhalmaza van, amiben a klaszterek léteznek. A valóságban a klaszterek sok különböző altérben (dimenzióhalmazban) létezhetnek, amelyek közül néhány átfedő lehet. A 9.3.2. szakasz olyan módszereket vizsgál, amelyek az altér klaszterezés általános problémáját célozzák meg, azaz mind a klaszterek, mind az általuk kifeszített altér megkeresését is.

A klaszterező algoritmusok általános jellemzői

A klaszterező algoritmusok igen eltérőek. Most a klaszterező algoritmusok fontos jellemzőinek általános tárgyalását adjuk, konkrétabb megjegyzéseket majd az egyes eljárások tárgyalásánál teszünk.

Rendezésfüggőség

Néhány algoritmusnál a klaszterek minősége és száma attól függően változhat (akár drámai mértékben), hogy milyen sorrendben történik az adatok feldolgozása. Bár kívánatosnak tűnne az ilyen algoritmusok elkerülése, néha a rendezésfüggőség viszonylag csekély, vagy az algoritmusnak egyéb kívánatos tulajdonságai lehetnek. A SOM (9.2.3. szakasz) egy példa rendezésfüggő algoritmusra.

Nemdetermináltság

Nem rendezésfüggőek az olyan klaszterező algoritmusok, mint például a K -közép, de különböző eredményt adnak minden egyes futásnál, mert egy véletlenszerű választást igénylő kezdőértékadási lépésre épülnek. Mivel a klaszterek minősége futásról futásra változhat, többszöri futtatásra lehet szükség.

Skálázhatóság

Nem szokatlan, hogy egy adathalmaz objektumok millióit tartalmazza. Az ilyen adathalmazokra használt klaszterező algoritmusok lineáris vagy közel-lineáris idő- és tárbonyolultságúak kell, hogy legyenek. Még az O( m 2 ) komplexitású algoritmusok sem praktikusak nagy adathalmazokra. Az adathalmazok klaszterező módszerei nem mindig tételezhetik fel továbbá azt, hogy minden adat elfér a központi memóriában, vagy hogy az adatelemek közvetlenül hozzáférhetőek. Az ilyen algoritmusok megvalósíthatatlanok nagy adathalmazokra. A 9.5. szakasz a skálázhatóság témakörével foglalkozik.

Paraméterválasztás

A legtöbb klaszterező algoritmusnak egy vagy több, felhasználó által beállítandó paramétere van. Nehéz lehet a megfelelő értékek megválasztása, ezért a hozzáállás többnyire a ``minél kevesebb a paraméter, annál jobb''. A paraméterértékek megválasztása még nagyobb kihívássá válik, ha a paraméterek kis változása jelentősen megváltoztatja a klaszterezés eredményét. Végül, hacsak nem áll rendelkezésre egy eljárás a paraméterértékek meghatározásához (melyhez szükség lehet felhasználói beavatkozásra), az algoritmus felhasználója kénytelen próbálgatásra hagyatkozni a megfelelő paraméterértékek megkereséséhez.

A legismertebb paraméter-kiválasztási probléma talán a ``helyes klaszterszám meghatározása'' a felosztó klaszterező algoritmusoknál, mint például a K -közép. Ennek a kérdésnek az egyik lehetséges megközelítését adta a 8.5.5. szakasz, míg a többi megoldáshoz az irodalmi megjegyzésekben adunk hivatkozásokat.

A klaszterezési probléma átalakítása más tartományba

Néhány klaszterező módszer azt a megközelítést alkalmazza, hogy a klaszterezés problémáját egy másik tartományon értelmezett problémára képezi le. Például a gráf-alapú klaszterezés a klaszterek megkeresésének problémáját a szomszédsági gráf összefüggő komponensekre történő felosztásának feladatára képezi le.

A klaszterezés optimalizálási problémaként kezelése

A klaszterezést gyakran optimalizálási problémaként tekintjük: osszuk fel a pontokat olyan módon klaszterekre, amely maximalizálja a kapott klaszterhalmaz jóságát egy, a felhasználó által meghatározott célfüggvény szerint mérve. A K -közép klaszterező algoritmus (8.2. szakasz) például azt a klaszterhalmazt próbálja megtalálni, amely a pontoknak a legközelebbi klaszterközépponttól vett távolságának négyzetösszegét minimalizálja. Elméletileg az ilyen problémák úgy oldhatók meg, hogy sorra vesszük az összes lehetséges klaszterhalmazt és kiválasztjuk azt, amire a célfüggvény értéke a legjobb, de ez a kimerítő megközelítés számításilag kivitelezhetetlen. Ezért sok klaszterező eljárás olyan heurisztikus megközelítéseken alapul, amelyek jó, de nem optimális klaszterezést állítanak elő. Egy másik megközelítés a célfüggvény mohón vagy lokálisan történő alkalmazása. Főleg a 8.3. szakaszban tárgyalt hierarchikus klaszterező módszerek haladnak lokálisan optimális (mohó) döntésekkel a klaszterező folyamat egyes lépéseiben.

Ütemterv

A klaszterező algoritmusok tárgyalását az előző fejezetéhez hasonlóan szervezzük, először aszerint csoportosítva a módszereket, hogy prototípus-alapúak, sűrűség-alapúak vagy gráf-alapúak-e. Külön tárgyaljuk azonban a skálázható klaszterező eljárásokat. A fejezetet a klaszterező algoritmus kiválasztásának tárgyalásával zárjuk.

Vissza		Előre
Feladatok	Főoldal	Prototípus-alapú klaszterezés