8. fejezet - Klaszteranalízis: Alapvető fogalmak és algoritmusok

A klaszteranalízis adatobjektumokat csoportosít kizárólag azon információk alapján, amelyeket azokban az adatokban talál, melyek az objektumokat valamint a köztük fennálló kapcsolatokat írják le. A cél az, hogy az egy csoporton belüli objektumok hasonlóak legyenek egymáshoz (vagy kapcsolat legyen közöttük), és különbözőek legyenek más csoportok objektumaitól (vagy ne álljanak ezekkel kapcsolatban). Minél nagyobb a hasonlóság (vagy homogenitás) a csoportokon belül és minél nagyobb a különbség az egyes csoportok között, annál jobb vagy pontosabb a klaszterezés.

Számos alkalmazásban nincs jól meghatározva a klaszter fogalma. Azért, hogy jobban megértsük annak a döntésnek a nehézségét, hogy mi alkot egy klasztert, tekintsük a 8.1. ábrát, amely húsz pontot ábrázol, valamint azok klaszterekre osztásának három különböző módját mutatja. A jelek alakjai a klasztertagságot jelzik. A 8.1. (b) és a 8.1. (d) ábrák kettő illetve hat részre osztják az adatokat. Lehetséges azonban, hogy a két nagyobb klaszter mindegyikének látszólagos felbomlása három alklaszterre egyszerűen az emberi látórendszer hibája. Hasonlóan lehet, hogy nem ésszerűtlen azt mondani, hogy a pontok négy klasztert alkotnak, ahogy azt a 8.1. (c) ábra mutatja. Ez az ábra azt szemlélteti, hogy a klaszterek definíciója pontatlan, és hogy a legjobb definíció az adatok természetétől és a kívánt eredménytől függ.

A klaszteranalízis más, adatobjektumokat csoportokba soroló módszerekkel is kapcsolatban áll. A klaszterezést tekinthetjük például az osztályozás egy olyan formájának, amely az objektumokhoz osztálycímkéket (klasztercímkéket) rendel. Ezt a címkézést azonban csak az adatok alapján végzi. Ezzel szemben az osztályozás a 4. fejezet értelmében felügyelt osztályozás (supervised classification), azaz egy új címkézetlen objektumhoz úgy rendel címkét, hogy egy, ismert osztálycímkéjű objektumokból felépített, modellt használ. Emiatt a klaszteranalízist néha felügyelet nélküli osztályozásnak (unsupervised classification) is nevezik. Amennyiben az osztályozás fogalom jelző nélkül merül fel adatbányászati környezetben, akkor az jellemzően felügyelt osztályozásra utal.

Míg a szegmentálás (segmentation) és a particionálás (partitioning) kifejezéseket néha szintén a klaszterezés szinonimáiként használják, ezeket a kifejezéseket gyakrabban használják a klaszteranalízis hagyományos határain kívül. A particionálás kifejezést például gyakran használják gráfokat algráfokra osztó módszerek esetében, amelyek azonban nem kötődnek szorosan a klaszterezéshez. A szegmentálás gyakran egyszerű, adatokat csoportokba osztó módszerekre utal, például egy kép szegmensekre bontható csak a pixel-intenzitás és a szín alapján, vagy az emberek csoportosítóak a jövedelmük szerint. Ennek ellenére egyes munkák a gráfparticionálás és kép- illetve piacszegmentálás területén kapcsolódnak a klaszteranalízishez.

Klaszterek egy teljes gyűjteményére általában klaszterezés néven hivatkoznak, és ebben a szakaszban különböző típusú klaszterezéseket különböztetünk meg: hierarchikus (egymásba ágyazott) vagy felosztó (nem egymásba ágyazott), kizáró, átfedő vagy fuzzy, valamint teljes vagy részleges.

Hierarchikus kontra felosztó

A leggyakrabban tárgyalt megkülönböztetés a különböző típusú klaszterezések között az, hogy vajon a klaszterek egymásba ágyazottak, vagy nem egymásba ágyazottak, hagyományosabb terminológiával hierarchikusak vagy felosztóak. Felosztó (partitional) klaszterezés alatt egyszerűen az adathalmaz olyan, nem átfedő alcsoportokra bontását értjük, hogy mindegyik adatobjektum pontosan egy részhalmazba kerül. Egyenként véve mindegyik klasztercsoport egy felosztó klaszterezés a 8.1. (b--d) ábrán.

Amennyiben megengedjük, hogy a klasztereknek alklasztereik lehessenek, akkor hierarchikus (hierarchical) klaszterezést kapunk, amely nem más, mint egymásba ágyazott klaszterek egy fába rendezett halmaza. A fa minden csúcsa (klasztere), a levélcsúcsokat kivéve, a gyermekei (alklaszterei) uniója, és a fa gyökere az összes objektumot tartalmazó klaszter. Gyakran, de nem minden esetben, a fa levelei egyetlen adatobjektumot tartalmazó egyelemű klaszterek. Amennyiben megengedjük, hogy a klaszterek egymásba ágyazottak legyenek, akkor a 8.1. (a) ábrát értelmezhetjük úgy is, hogy két alklasztert ábrázolnak (8.1. (b) ábra), amelyeknek további három-három alklasztere van (8.1. (d) ábra). A 8.1. (a--d) ábrán látható klaszterek, amikor ebben a sorrendben tekintjük őket, az egyes szinteken egyenként 1, 2, 4 és 6 klasztert tartalmazó hierarchikus klaszterezést alkotnak. Végül megjegyezzük, hogy egy hierarchikus klaszterezésre tekinthetünk úgy, mint felosztó klaszterezések egy sorozatára, és fordítva, egy felosztó klaszterezéshez jutunk, ha ennek a sorozatnak egy tetszőleges tagját vesszük, azaz egy adott szinten elvágjuk a hierarchikus fát.

Kizáró kontra átfedő kontra fuzzy

A 8.1. ábrán látható összes klaszterezés kizáró (exclusive), mivel mindegyik objektumot csak egyetlen klaszterhez rendelik hozzá. Gyakran előfordul, hogy egy pont több klaszterbe is beleillik, ezeket az eseteket nem-kizáró klaszterezésnek nevezzük. Általános értelemben az átfedő (overlapping), vagy nem-kizáró (non-exclusive) klaszterezés kifejezést olyan esetekben használják, amikor egy objektum egyszerre egynél több csoporthoz (osztályhoz) is tartozhat. Egy személy egy egyetemen például egyaránt lehet egy beiratkozott hallgató és az egyetem alkalmazottja. A nem-kizáró klaszterezést gyakran használják olyan esetekben is, amikor egy objektum két vagy több klaszter ``között'' helyezkedik el, és így bármelyik klaszterbe besorolható lenne. Képzeljünk el egy pontot félúton a 8.1. ábra két klasztere között. Ahelyett, hogy ezt az objektumot némiképp tetszőlegesen egyetlen klaszterhez rendelnénk, az ``egyformán jó'' klaszterek mindegyikében elhelyezzük.

Fuzzy klaszterezés esetén minden objektum minden klaszterbe beletartozik egy tagsági súly erejéig, melynek értéke 0 (egyáltalán nem tartozik bele) és 1 (teljesen beletartozik) közé esik. Más szóval a klasztereket fuzzy halmazokként kezeljük. (Matematikailag a fuzzy halmaz egy olyan halmaz, amelyben egy objektum bármelyik halmazba egy bizonyos súllyal tartozik bele, amely értéke 0 és 1 közé esik. Fuzzy klaszterezés esetén még azt a megkötést szokták alkalmazni, hogy a súlyok összege eggyel kell, hogy egyenlő legyen mindegyik objektum esetén.) Hasonlóan, a valószínűségi klaszterező módszerek minden ponthoz kiszámolják annak a valószínűségét, hogy az egyes pontok az egyes klaszterekbe tartoznak, és ezeknek a valószínűségeknek az összege is egy kell, hogy legyen minden pont esetén. Mivel a tagsági súlyok vagy valószínűségek összege 1 bármelyik objektumnál, egy fuzzy vagy valószínűségi klaszterezést nem azonosíthatunk valódi többosztályos helyzetként, mint a hallgatói dolgozó esetét, ahol egy objektum több osztályhoz tartozik. Ezek a megközelítések inkább arra a legalkalmasabbak, hogy elkerüljük egy objektum csak egy klaszterhez való hozzárendelésének tetszőlegességét akkor, amikor lehet, hogy több klaszterhez is közel van. A gyakorlatban egy fuzzy vagy valószínűségi klaszterezést gyakran kizáró klaszterezéssé konvertálnak úgy, hogy mindegyik objektumot abba a klaszterbe sorolják be, amelynél a legnagyobb a tagsági súlya vagy a valószínűsége.

Teljes kontra részleges

A teljes (complete) klaszterezés mindegyik elemet hozzárendeli valamelyik klaszterhez, míg a részleges (partial) klaszterezés nem. A részleges klaszterezés oka, hogy az adathalmaz egyes objektumai nem tartoznak jól meghatározott csoportokba. Az adathalmazbeli objektumok sokszor zajt, kiugró értéket vagy ``érdektelen hátteret'' képviselnek. Bizonyos újságcikkeknek például egy olyan közös témája lehet, mint a globális felmelegedés, míg más cikkek általánosabbak vagy egyedi eseteket dolgoznak fel. Így ha meg szeretnénk találni az elmúlt hónap cikkeinek fontos témáit, akkor csak dokumentumok olyan klasztereiben szabad keresnünk, melyek szorosan kapcsolódnak egy közös téma révén. Más esetekben célszerű az objektumok teljes klaszterezése. Egy olyan alkalmazásnak például, amely klaszterezést alkalmaz dokumentumok böngészési célú szervezésére, biztosítania kell, hogy minden dokumentum böngészhető legyen.

A klaszterezés célja objektumok hasznos csoportjainak (klasztereinek) keresése, ahol a hasznosságot az adatelemzés célja határozza meg. Nem meglepő, hogy több különböző klaszterfogalom bizonyult hasznosnak a gyakorlatban. Ezen klasztertípusok között fennálló különbségek képi szemléltetése érdekében a 8.2. ábrán látható kétdimenziós adatpontokat használjuk mint adatobjektumokat. Hangsúlyozzuk azonban, hogy az itt leírt klasztertípusok ugyanúgy érvényesek más jellegű adatoknál is.

Jól elkülönülő klaszterek

Egy klaszter objektumoknak egy olyan halmaza, melyben minden klaszteren belüli objektum közelebb van (jobban hasonlít) minden más klaszteren belüli objektumhoz, mint bármelyik klaszteren kívüli objektumhoz. Néha egy küszöbértéket használunk annak pontosabb meghatározására, hogy egy klaszteren belül található objektumoknak milyen közel kell lenniük (mennyire kell hasonlítaniuk) egymáshoz. A klaszter ezen idealista definíciójának azonban csak abban az esetben lehet eleget tenni, amikor az adatok természetes klasztereket tartalmaznak, amelyek egymástól távol helyezkednek el. A 8.2. (a) ábra egy olyan példát mutat jól elkülönülő klaszterekre, amelyek pontok két csoportjából állnak a kétdimenziós térben. Bármely két különböző csoportban lévő pont közötti távolság nagyobb bármely két egy csoportba tartozó pont közötti távolságnál. A jól elkülönülő klasztereknek nem feltétlenül kell gömbalakúaknak lenniük, bármilyen alakban előfordulhatnak.

Prototípus-alapú klaszterek

Egy klaszter olyan objektumokat tartalmazó halmaz, amelynek mindegyik objektuma közelebb van (jobban hasonlít) a klasztert definiáló prototípushoz, mint bármelyik másik klaszter prototípusához. Folytonos attribútumokkal bíró adatok esetén egy klaszter prototípusa gyakran egy középpont, azaz a klaszterben található összes pont átlaga. Amikor a középpont nem értelmezhető, mint amikor adatoknak kategorikus attribútumaik is vannak, akkor a prototípus a medoid, azaz a klaszter legjellemzőbb pontja. Sokféle adattípus esetén prototípusként a leginkább középponti elhelyezkedésű elemre tekintünk, és ilyen esetekben a prototípuson alapuló klaszterekre rendszereint középpont-alapú (central-based) klaszterekként hivatkozunk. Nem meglepő módon az ilyen típusú klaszterek hajlamosak gömb alakot felvenni. A 8.2. (b) ábra egy példát mutat a középpont-alapú klaszterekre.

Gráf-alapú klaszterek

Amennyiben az adatokat gráfként ábrázoljuk, ahol a csúcsok az objektumokat, az élek pedig az objektumok közötti kapcsolatokat képviselik (lásd a 2.1.2. szakaszt), akkor egy klasztert definiálhatunk úgy, mint egy összefüggő komponenst, azaz olyan objektumok csoportját, melyek kapcsolódnak egymáshoz, viszont nem kapcsolódnak csoporton kívüli objektumokhoz. A gráf-alapú klaszterek egy fontos példáját jelentik a szomszédság-alapú klaszterek (contiguity-based clusters), ahol két objektum csak akkor van összekötve, amikor egy meghatározott távolságon belül találhatóak. Ebből következik, hogy egy szomszédság-alapú klaszterben található minden pont közelebb van minden, a klaszteren belüli ponthoz, mint bármely más klaszterben található ponthoz. Ilyen klaszterekre mutat egy kétdimenziós példát a 8.2. (c) ábra. A klaszter ezen definíciója akkor hasznos, amikor a klaszterek szabálytalanok vagy összefonódóak, azonban a zaj jelenléte gondot okozhat, amint ezt a 8.2. (c) ábra két gömb alakú klasztere szemlélteti, egy vékony híd összevonhat két tisztán elkülönülő klasztert.

A gráf-alapú klasztereknek más típusai is lehetségesek. Az egyik ilyen megközelítés (8.3.2. szakasz) egy klasztert klikkként (clique) definiál, azaz csúcsok olyan halmazaként a gráfban, amelyek teljes mértékben kapcsolódnak egymáshoz. Speciálisan, ha az objektumok egymástól vett távolságaik sorrendje alapján hozunk létre kapcsolatokat, akkor abban az esetben jön létre egy klaszter, amikor az objektumok klikket alkotnak. Akárcsak a prototípus-alapú klaszterek, az ilyen klaszterek is hajlamosak gömb alakot felvenni.

Sűrűség-alapú klaszterek

Egy klaszter objektumoknak egy olyan sűrű tartománya, amelyet egy alacsony sűrűségű tartomány vesz körül. A 8.2. (d) ábra néhány sűrűség-alapú klasztert mutat azokra az adatokra, melyet a 8.2. (c) ábra adataiból zaj hozzáadásával kaptunk. A két kör alakú klaszter nem egyesül úgy, mint ahogy azt a 8.2. (c) ábra mutatja, mivel a közöttük lévő híd beleolvad a zajba. A 8.2. (c) ábrán látható hullám is hasonlóképpen tűnik el a zajban, és nem alkot önálló klasztert a 8.2. (d) ábrán. A klaszter sűrűség-alapú definícióját leggyakrabban akkor alkalmazzuk, amikor a klaszterek szabálytalanok vagy összefonódóak, és amikor zaj vagy kiugró értékek vannak jelen. Ezzel szemben a klaszter szomszédság-alapú definíciója nem működne jól a 8.2. (d) ábra adatain, mivel a zaj hajlamos hidakat képezni a klaszterek között.

Fogalmi klaszterek

Általánosabban egy klasztert úgy is definiálhatunk, mint közös tulajdonságú elemek egy halmazát. Ez a definíció magába foglalja a klaszter minden korábbi definícióját, például egy középpont-alapú klaszter objektumai abban a tulajdonságban osztoznak, hogy mindannyian ugyanahhoz a középponthoz vagy medoidhoz vannak a legközelebb. A tulajdonságban osztozás megközelítése azonban újabb típusú klasztereket is magába foglal. Tekintsük a 8.2. (e) ábrán látható klasztereket. Egy háromszög alakú terület (klaszter) egy téglalap alakúval határos, valamint két összefonódó kör (klaszter) látható. Mindkét esetben a klaszter nagyon egyedi fogalmára lenne szükség, hogy egy klaszterező algoritmus sikeresen megtalálja ezeket a klasztereket. Azt a folyamatot, mely során ilyen klaszterek megtalálása a cél, fogalmi klaszterezésnek (conceptual clustering) nevezzük. A klaszter túlságosan kifinomult fogaloma azonban már az alakfelismerés területére vezetne, és így ebben a könyvben csupán az egyszerűbb klasztertípusokkal foglalkozunk.

Ütemterv

Ebben a fejezetben három egyszerű, ám fontos módszert használunk annak érdekében, hogy a klaszteranalízis különböző megközelítéseit bemutassuk.