Dokumentum klaszterizációs módszerek

Definíció szeritnt a klaszterizálás egy felügyeletlen (unsupervised), gépi úton történő automatikus osztályba sorolása adott mintáknak, észleléseknek, megfigyeléseknek, mérési pontoknak, vagy éppen dokumentumoknak valamilyen hasonlósági mérték alapján. A minták rendszereint valamilyen vektor formában adottak, mint egy többdimenziós tér pontjai. A térben alkalmazott hasonlósági metrikai a céljainktól függően változhat. Fontos kiemelni, hogy a klaszterizáció folyamata nem felügyelt, hanem felügyeletlen. A felügylet klaszterizációt osztályozásnak (classification, discriminant analysis) hívjuk, és abban az esetben rendelkezünk olyan tanító mintákkal, amelyek címkéit ismerjük. Az osztályozás feladata, hogy egy új mintához megtalálja a legmegfelelőbb címkét a tanító adatok alapján. A dokumentum klaszterizáció célja a (általában vektortér modellben reprezentált) dokumentumok klaszterekbe sorolása azzal az elvárással, hogy az ugyanazon klaszterbe tartozó dokumentumok egymáshoz képest igen hasonlóak legyenek, a klaszteren kívüli összes más dokumentumtól pedig nagymértékben különbözzenek. A klaszterizálás nagymértékben csökkenti egy adott problémakör komplexitását, ugyanis addig különálló entitásokat képesek leszünk a klaszterizálást követően egységesen kezelni. A klaszterizáció művelete alapvetően öt lépésből tevődik össze, ezek a következők.

Adatreprezentáció.  A szövegbányászati alkalmazásokban az adatreprezentáció során a vizsgált dokumentum korpuszt egy alkalmas vektortérbe transzformáljuk át, ahol lehetőség nyílik a szöveges dokumentumok számszerű adatokként való kezelése, ezáltal a többváltozós statisztikai módszerek alkalmazása. Az adat reprezentációval együtt járhat jellemvonás kiválasztás és jellemvonás kinyerés (feature extraction). Ezek során azt próbáljuk elérni, hogy a klaszterizálás során az adathalmaz minél hatékonyabb jellemvonásaira épülő klaszterizációt tudjunk végrehajtani. A jellemvonás kinyerés esetében meglévő jellemvonásokat alakítunk át annak érdekében, hogy a klaszterizáció a számunkra kívánatos módon történhessen meg.

Klaszter távolságfüggvény definiálása. Ez a mozzanat általában egy távolságfüggvény (pl. Minkowski) definiálását jelenti az adott adatpontok párjaira nézve. Az adatpontok egymáshoz képesti közelsége ezzel a távolságfüggvénnyel értelmezhető. Ugyan ez a távolságfüggvény nem csak adatpont párokra értelmezhető, hanem klasztrer-pont és klaszter-klaszter viszonlyatban is.

Klaszterizálás, csoportosítás. A klaszteritálás menete alapvetően két módon történhet. Az eltérés a két mód között abban mutatkozik meg, hogy a klaszterizálás az elemeket illetően kizárólagos tagságot eredményez-e. Az egyik esetben egy adott pontot csak egy klaszterhez rendelünk hozzá, és ekkor a többi klaszternek ez az adott pont nem eleme. Ez az úgynevezett erős klaszterizáció, vagy kizáró klaszterizáció. A másik esetben minden pont egy meghatározott tagsági fokig tagja egy adott klaszternek. Ez utóbbi az ún. fuzzy klasztering, amikor nincsenek éles határok a klaszterek között. Ezen kívül más szempontok alapján is csoportosíthatóak..

Adat absztrakció. Az adat absztrakció kettős célt szolgál. Egyrészt lehetővé teszi további gépi műveletek végrehajtását, másrészt megkönnyíti a felhasználó dolgát a klaszterizáció eredményének megértésében, ábrázolásában és továbbgondolásában. Az absztrakció során általában a klasztereket nevesítjük, érthető címkével látjuk el, a centriod értékével helyettesítjük, stb.

Kapott adatok értékelése. Utolsó lépésként a kapott adatok értékelése történik meg a klaszterizáció eredményének figyelembevételével. Alapvetően két területre terjedhet ki az elemzés: a bemenő adatokra vonatkozóan, illetve a klaszterizáció algoritmus hatékonyságára vonatkozóan.

Klaszterizáló módszerek típusai

A klaszterizációs technikák osztályozása több szempont alapján is történhet. Mindegyik módszernek meg van a maga tudományos megalapozottsága, hatékonyságuk és bonyolultságuk azonban különböző. A klaszterizáló algoritmusok csoportosítása az alábbi szempontok szerint történhet.

A módszerek alapvetően különböznek abban a tulajdonságukban, hogy végeredményként bináris vagy fuzzy kimenetet adnak. Bináris (hard, binary clustering) esetben egy adott szöveg csak egy klaszter tagja lehet, míg Fuzzy kimenet esetén tagsági függvényekről beszélünk, amikor minden szövegnek minden klaszterre vonatkozóan egy %-os értékben nyilvánul meg egy adott klaszterhez való tartozásának mértéke. A Fuzzy klasztering átalakítható bináris típusúvá, amennyiben minden mintához azt a klasztert rendeljük, amelyre vonatkozóan a tagsági függvény értéke a legmagasabb.

Egy más szempontú klaszterizáló algoritmus osztályozás aszerint különbözteti meg a klaszterizáló módszereket, hogy azok a klaszterek kialakításánál az összevó (agglomerative) vagy szétválasztó (participáló, partitional, divisive) lépéseket alkalmazzák-e. Az összevonó típusú klaszterizáló algoritmusok először minden bemeneti mintát egy külön klaszternek tekintenek, és lépésről-lépésre minden körben összevonja a legközelebbi két klasztert egy távolságfüggvény minimum értékének megahtározása alapján, amíg egy bizonyos leállási kritérium (stop criterion) nem teljesül. Ezzel ellentétben a szétválasztó logikát alkalmazó módszerek először az összes mintát egy nagy kiindulási klaszterként kezelik, és minden lépésben egy-egy klaszter szétválasztásával megosztja a legjobban megosztható klasztert, amíg egy leállási kritérium nem teljesül (pl. a maximális kívánt klaszterszámot eléri).

Egy további osztályozási szempont alapján a klaszterizáló algoritmusok egyik fajtája determinisztikus, a másik pedig sztochasztikus. Ez a megkülönböztetés elsősorban a particiónáló módszerek eseében értelmezhető, ahol valamilyen négyzetes hibafüggvény optimalizálását végezzük el. A determinisztikus, illetve sztochasztikus jelző itt arra utal, hogy az állapottér keresése determinisztikus módon történik-e, vagy sztochasztikus módszerek használatával.

Értelmezhető tovább a klaszterizáló algoritmusok osztályozása aszerint is, hogy jellegüket illetően monothetikusak (monothetic) vagy polythetikusak (polythetic). Ez a megkülönböztetés arra utal, hogy a jellemvonások (features) használata a klaszterizáció során szekvenciális-e vagy párhuzamos. A legtöbb klaszterizáló algoritmus potlithetikus, tehát minden jellemvonás egyszerre vesz részt a klaszterizáció során meghatározott távolságfüggvény kiértékelésekor, és a döntéshozatal ezen távolságok mérlegelésével születik.  A monothetikus esetben a jellemvonások alkalmazása nem egyszerre, hanem egymást követően, szekvenciálisan történik. A módszer lépésenként osztja klaszterekre a pontokat. Először egy klasztert az x jellemvonás mentén osztunk ketté, majd egy másik klasztert az x₂ jellemvonás alapján. A monothetikus módszerek legnagyobb problémája, hogy 2^d klaszter születik eredményül, ahol d a minták dimenziószáma. Nagy dimenziószám esetén a generált klaszterek száma olyan nagy, hogy a kezdeti minták semmitmondóan kis klaszterek sokaságába sorolódnak be.

Az utolsó osztályozási mód, ami ismertetésre kerül a klaszterizáló algoritmusokat illetően, az a módszerek  között azok inkrementális (incremental), illetve nem inkrementális (non-incremental) jellege szerint tesz különbséget. Ez az aspektus akkor kerül a figyelem középpontjába, amikor a klaszterizálni kívánt minták száma olyan nagy, hogy határt kell szabnunk vagy a tárhely felhasználásnak vagy pedig a futásidőnek. Napjaink fejlett klaszterizáló módszerei már ilyen értelemben előrébb járnak, mint a kezdeti módszerek, amelyek nem készültek fel nagy mennyiségű minta kezelésére. Az inkrementális módszerek ezzel ellentétben képesek a szükséges műveletek minimalizálására, illetve az adatstruktúrák méretének csökkentésére.

Vázsonyi Miklós