Melyik klaszterező algoritmust válasszuk?

Számos tényezőt kell figyelembe vennünk, amikor arról döntünk, hogy melyik klaszterező módszert használjuk. Ezek közül sokat -- ha nem mindet -- megtárgyaltunk valamilyen mélységben ebben és az előző fejezetben. Ebben a szakaszban az a célunk, hogy tömören összefoglaljuk ezeket a tényezőket úgy, hogy némileg megvilágítsuk, melyik klaszterező algoritmus lehet megfelelő egy konkrét klaszterezési feladatra.

A klaszterezés típusa

Az algoritmus által előállítandó klaszterezés típusa az egyik fontos tényező annak megállapításánál, hogy a klaszterezés típusa megfelel-e a tervezett felhasználásnak. Bizonyos alkalmazásoknál, mint például a biológiai taxonómiák létrehozásánál, előnyös a hierarchia. Az összegzésre használt klaszterezésnél a felosztó klaszterezés a tipikus. Más alkalmazásoknál mindkettő hasznos lehet.

A legtöbb klaszterező alkalmazásnál fontos az összes (vagy majdnem az összes) objektum klaszterezése. Ha például dokumentumok tallózási célú rendszerezésére használjuk a klaszterezést, akkor azt szeretnénk, hogy a legtöbb dokumentum beletartozzon egy csoportba. Ha viszont a legfontosabb témát keressük egy dokumentumhalmazban, akkor egy olyan klaszterező sémát részesíthetünk előnyben, amely csak erősen összetartozó klasztereket állít elő, még akkor is, ha sok dokumentum klaszterezetlen marad.

Végül, a legtöbb klaszterező alkalmazás feltételezi, hogy minden objektumot hozzárendelünk egy klaszterhez (vagy egy klaszterhez a hierarchikus sémák adott szintjén). Ahogy láttuk, a valószínűségi és a fuzzy sémák viszont súlyokat adnak, amelyek a különböző klaszterekhez tartozás fokát vagy valószínűségét adják meg. Más módszerek, mint a DBSCAN és az SNN sűrűség-alapú klaszterezés, az egy klaszterhez erősen kötődő belső pontok fogalmát használják. Ilyen fogalmak hasznosak lehetnek bizonyos alkalmazásoknál.

A klaszter típusa

Egy másik kulcskérdés, hogy vajon a klaszter típusa megfelel-e a kívánt alkalmazásnak. A klasztereknek három gyakran előforduló típusa van: prototípus-, gráf- és sűrűség-alapú. A prototípus-alapú klaszterező sémák, csakúgy mint néhány gráf-alapú klaszterező séma -- a teljes kapcsolás, a középpont, és a Ward --, hajlamosak olyan gömb alakú klaszterek kialakítására, amelyekben minden egyes objektum elég közel van a klaszter prototípusához vagy a klaszter más objektumaihoz. Ha például az adatokat úgy szeretnénk összefoglalni, hogy csökkentsük azok méretét, és ezt a lehető legkisebb hibával szeretnénk megtenni, akkor ezen típusú módszerek valamelyike lenne a legmegfelelőbb. Ezzel szemben a sűrűség-alapú klaszterező módszerek és néhány gráf-alapú klaszterező eljárás, mint például az egyszerű kapcsolás, tipikusan nem gömb alakú klasztereket hoznak létre, ezért sok olyan objektumot tartalmaznak, amelyek nem nagyon hasonlóak egymáshoz. Ha a klaszterezést arra használjuk, hogy egy földrajzi területet összefüggő részekre osszunk fel a földtakaró típusa alapján, akkor ezen eljárások egyike megfelelőbb lesz az olyan prototípus-alapú sémáknál, mint például a K -közép.

A klaszterek jellemzői

A klaszter általános típusa mellett más klaszterjellemzők is fontosak. Ha az eredeti adattér altereiben szeretnénk klasztereket találni, akkor egy olyan algoritmust kell választanunk, mint a CLIQUE, ami kimondottan ilyen klasztereket keres. Hasonlóan, ha a klaszterek közötti térbeli kapcsolat kialakítása érdekel bennünket, akkor a SOM vagy valamilyen rokon megközelítés lenne a megfelelő. Nagyon eltérőek a klaszterező algoritmusok abban is, hogy képesek-e kezelni a különböző alakú, méretű és sűrűségű klasztereket.

Az adathalmazok és attribútumok jellemzői

A bevezetésben tárgyaltak szerint az adathalmazok és attribútumok típusa megszabhatják a használandó algoritmus típusát. A K -közép algoritmus például csak olyan adatokra használható, amelyekre rendelkezésre áll egy megfelelő viszonymérték, amely lehetővé teszi, hogy értelmesen kiszámítsuk egy klaszter középpontját. Más klaszterező módszerek esetén, mint például sok agglomeratív hierarchikus megközelítésnél, az adathalmazok és az attribútumok kevésbé fontosak, feltéve, hogy alkotható egy szomszédsági mátrix.

Zaj és kiugró értékek

A zaj és a kiugró értékek különösen fontos aspektusai az adatoknak. Az egyes klaszterező algoritmusok tárgyalása esetén törekedtünk a zaj és a kiugró értékek hatásának jelzésére. A gyakorlatban viszont nehéz lehet meghatározni az adathalmazban a zaj mennyiségét vagy a kiugró értékek számát. Sőt, ami zaj vagy kiugró érték valaki számára, az érdekes lehet másvalaki számára. Ha például egy terület különböző népességsűrűségű részekre bontására használunk klaszterezést, akkor nem szeretnénk olyan sűrűség-alapú klaszterező eljárást alkalmazni, mint a DBSCAN, ami feltételezi, hogy zaj vagy kiugró érték az a tartomány vagy pont, amelynek sűrűsége alacsonyabb egy globális küszöbnél. Egy másik példa az olyan hierarchikus klaszterező séma, mint a CURE, ami gyakran kidobja azokat a pontokat, amelyek klaszterei lassan nőnek, mert ezek a csoportok sokszor kiugró értékeket jellemeznek. Néhány olyan alkalmazásnál viszont, mint például a piacszegmentálás, leginkább a kis klaszterek érdekelnek bennünket, mert ezek a klaszterek reprezentálhatják a legjövedelmezőbb fogyasztókat.

Az adatobjektumok száma

Az előző szakaszokban meglehetős részletességgel megvizsgáltuk, hogy a klaszterezést hogyan befolyásolja az adatobjektumok száma. Megismételjük, hogy ez a faktor gyakran fontos szerepet kap a használt klaszterező algoritmus típusának megválasztásánál. Tegyük fel, hogy egy adathalmaz hierarchikus klaszterezését szeretnénk előállítani. Nem érdekel bennünket egy teljes hierarchia, ami egészen az egyes objektumok szintjéig elér, csak addig a pontig, amíg néhány száz klaszterre nem bontjuk az adatokat. Ha az adathalmaz nagyon nagy, nem alkalmazhatunk egy összevonó hierarchikus klaszterező eljárást közvetlenül. Használhatunk viszont egy olyan felosztó klaszterező eljárást, mint például a minimális feszítőfa (MST) algoritmus. Ez a felosztó megfelelője az egyszerű kapcsolás eljárásnak, de ez csak akkor működik, ha az adathalmaz nem túl nagy. A kettéosztó K -közép sok adathalmazra működik, de ha az adathalmaz elég nagy ahhoz, hogy ne férjen be teljes egészében a memóriába, akkor az ilyen séma is problémákba ütközik. Ebben az esetben hasznosabb lesz egy olyan eljárás, mint a BIRCH, amihez nem szükséges, hogy minden adat a központi memóriában legyen.

Az attribútumok száma

A fentiekben meglehetősen hosszan tárgyaltuk a dimenziószám hatását. Ismét annak megértése kulcsfontosságú, hogy hiába működik jól egy algoritmus kis vagy közepes számú dimenzióban, lehet, hogy nem fog jól működni nagy számú dimenzióra. Ahogy sok más esetben is, amikor a klaszterező algoritmust nem megfelelően alkalmazzák, a klaszterező algoritmus lefuthat és előállíthat klasztereket, de ezek a klaszterek nem biztos, hogy az adatok valódi szerkezetét reprezentálják.

Klaszterleírás

A klaszterező eljárások egyik gyakran figyelmen kívül hagyott vonatkozása az, hogy miképpen írják le az eredményül kapott klasztereket. A prototípus klasztereket tömören írja le klaszter prototípusok egy kis halmaza. A keverék modellek esetén a klasztereket kis elemszámú paraméterhalmazok adják meg, mint például a várható érték vektor és a kovarianciamátrix. Ez egy nagyon tömör és érthető leírás. A SOM-nál a klaszterek közötti kapcsolat tipikusan egy kétdimenziós ábrán jeleníthető meg, ahogy az a 9.8. ábrán látható. A gráf- és sűrűség-alapú klaszterező megközelítéseknél viszont a klaszterek tipikusan a klaszter elemeinek halmazaként vannak megadva. Mindazonáltal, a CURE-nál a klaszterek leírhatóak reprezentáns pontok egy (viszonylag) kis halmazával. A rács-alapú klaszterező sémáknál, mint a CLIQUE, ugyancsak tömörebb leírás állítható elő a klaszterhez tartozó rácspontokat leíró attribútumértékekre vonatkozó feltételekkel.

Algoritmikus meggondolások

Az algoritmusoknak is vannak figyelmet igénylő aspektusai. Nemdeterminisztikus vagy rendezésfüggő-e az algoritmus? Automatikusan meghatározza-e az algoritmus a klaszterek számát? Van-e módszer a különböző paraméterek értékének meghatározására? Sok klaszterező algoritmus úgy próbálja megoldani a klaszterezés problémáját, hogy egy célfüggvényt optimalizál. A célfüggvény jól megfelel-e az alkalmazás céljainak? Ha nem, akkor az algoritmus hiába dolgozik jól és talál az adott célfüggvény szerint optimális vagy közel optimális megoldást, az eredmény nem lesz értelmes. A legtöbb célfüggvény ugyancsak a nagyobb klasztereket preferálja a kisebbek rovására.

Összefoglalás

A megfelelő klaszterező algoritmus kiválasztása az összes előző kérdés, valamint további, témakör-specifikus témák vizsgálatát is jelenti. Nincs recept a legmegfelelőbb módszer kiválasztására. A rendelkezésre álló klaszterező eljárások általános ismerete és a fentiekben említett kérdések megvizsgálása a célul kitűzött alkalmazásra való koncentrálással együtt mégis lehetővé kell, hogy tegye az adatelemzőnek, hogy megalapozott döntést hozzon arról, hogy melyik klaszterező módszert (vagy módszereket) próbálja ki.