A klaszteranalízis egy olyan dimenziócsökkentő eljárás, amellyel adattömböket tudunk homogén csoportokba sorolni, klasszifikálni. Ezeket a csoportokat nevezzük klasztereknek. Az egyes klasztereken belüli adatok valamilyen dimenzió szerint hasonlítanak egymáshoz, és e dimenzió mentén különböznek a többi klaszter elemeitől. A csoportok minél homogénebbek (azaz nagyobb az elemeik hasonlósága), és minél nagyobb közöttük a különbség, annál pontosabbnak mondható a klaszteranalízis maga. A csoportosítás alapját különböző távolság- vagy hasonlóságmértékek képezik.

Mivel az adatok értelmes szétválasztása, csoportba sorolása fontos célja számos tudomány-, üzleti- és informatikai területnek, azért a klaszteranalízis gyakran használt megoldása az adatbányászatnak, a minta felismerésnek, a képelemzésnek, az információ előhívásnak, a bioinformatikának, az adattömörítésnek és a számítógépes grafikának.

A klaszteranalízis nem egy bizonyos konkrét eljárás, hanem egy csoportosító megoldás ami az eredeti adatokat értelmes vagy hasznos csoportokra (klaszterekre) bontja – a kívánt végcéltől függően. (Fülöp, 2006) Ennek megfelelően a klaszterek kialakítására számos különböző, a klaszter fogalmát egymástól jelentősen eltérően definiáló eljárás használható. A népszerű klaszterelképzelések közé tartoznak az egymástól kis távolságra levő csoporttagokat tartalmazó klaszterek, a sűrűbben elhelyezkedő adatok halmazait bekerítő területek, szakaszok vagy bizonyos meghatározott statisztikai eloszlások. Így a klaszterezés többcélú optimizálási problémává tud válni. Az, hogy mi a megfelelő klaszterezési algoritmus és hogy milyen paramétereket javasolt használni (ide értve például a távolság funkciót, a sűrűségi határértéket, vagy azt, hogy mi az elvárt klaszter szám), attól függ, hogy mi az elérni kívánt szándék a klaszterezési eljárással. A klaszteranalízis nem egy automatizált feladat, hanem ismétlődő tudás kinyerésére irányuló vagy próbákat és kudarcokat is tartalmazó, interaktív optimalizáció folyamat.  Az alkalmazása alatt gyakran szükséges, hogy módosítva legyenek az adatok és a modell paraméterek egészen addig, amíg az eredmény a kívánt tulajdonságokat tükrözi. A lentebbi ábrán látható, az adatok egy tipikus halmaza – ezek különböző klaszterezési eljárásokkal különböző klaszterekbe sorolhatól, az eljárás előtt így fontos definiálni, hogy mi a célunk, mi a klaszter pontos fogalma számunkra.

344x344px|Cluster-1

A klaszterezés kifejezésen kívül még gyakran használt kifejezés erre az eljárásra az automatizált osztályozás, numerikus taxonómia és tipológiai analízis.

A klaszteranalízis megszületése Driver és Kroeber (1932) nevéhez köthető, míg pszichológiában ismertté Cattel (1943) tette a vonáselméleti klasszifikáció alkalmazása során.

Fogalom Azért is van annyi féle klaszterezési algoritmus, mivel a klaszter fogalmát nehéz precízen definiálni, azonban mindegyikben megtalálható egy közös nevező: az adatcsoportosítási cél csak az adatok tulajdonságai alapján. Az, hogy megértsük a különböző klasztermodellek alapelvét, elengedhetetlen ahhoz, hogy megértsük a különböző klaszterező algoritmusok közötti különbségeket.

Tipikus modellek közé tartoznak például (Fülöp, 2006 nyomán) :

Kapcsolódási (jól elkülönítő) modellek: távolsági kapcsolatokon alapuló modellek, amikben minden pont közelebb van minden, a pont klaszterében található ponthoz, mint bármely más klaszterben található más ponthoz Centroid (középpont alapú) modellek: minden klaszter egy átlagvektor alapján reprezentált; ezeknél a klasztereknél a klaszter prototípusa folytonos adatoknál a klaszter összes pontjának átlaga, míg kategorikus tulajdonságokkal is jellemző pontoknál azok mediodja, azaz legjellemzőbb pontja (jellemző algoritmus: megpróbálja megkeresni a felhasználó által megadott számú (K) klasztert, amelyeket a középpontjaik képviselnek) Gráf (szomszédság alapú) modellek: minden pont közelebb van legalább egy, a pont klaszterében található ponthoz, mint bármely más klaszterben található más ponthoz; ez a klaszterdefiníció akkor hasznos, amikor zajosak az adatok, összefonódók a klaszterek.  (Jellemző algoritmus: hierarchikus klaszterezés: kezdetben minden elem egy külön klaszterbe tartozik, és ezután minden lépésben a két legközelebbi klaszter kerül összevonásra egészen addig, amíg már csak egyetlen, minden elemet magába foglaló klaszter nem marad) Disztribúciós modellek: a klaszterek statisztikai eloszlásokat modelleznek (például többváltozós normál eloszlás) Sűrűségen alapuló modellek: itt a klaszterek olyan sűrű tartományai az adathalmaznak, amit egy kevésbé sűrű terület vesz körül (jellemző algoritmus: DBSCAN felosztó klaszterezést hajt végre, a klaszterek számát az algoritmus automatikusan határozza meg. Az alacsony sűrűségű tartományokba eső pontokat az eljárás zajként osztályozza és kihagyja, így nem generál teljes klaszterezést)

A klaszterezés szintén megkülönböztethető az alapján, hogy mennyire éles a klaszterek közötti választóvonal:

Kemény klaszterezés: minden elem egy bizonyos klaszterbe tartozik vagy nem tartozik bele Puha (fuzzy) klaszterezés: minden elem része valamilyen mértékben egy klaszternek; minden elem kap egy tagsági súlyt, melynek értéke 0 (egyáltalán nem tartozik bele a klaszterbe) és 1 (teljesen beletartozik) közé esik.

Léteznek ennél még finomabb különbségek:

Szigorú felosztó klaszterezés: minden elem pontosan egy klaszterbe tartozik Szigorú felosztó klaszterezés outlierekkel: vannak olyan elemek, amik egyetlen klaszterbe sem tartoznak és ezek az outlierek Átfedő klaszterezés: az elemek több, mint egy klaszterbe tartozhatnak (nem kizáró klaszterezésnek is hívják) Hierachikus klaszterezés: azok az elemek, amik egy részei egy halmaznak, részei az azt a halmazt tartalmazó halmaznak is; ennél  módszernél megengedjük, hogy a klasztereknek klasztereik lehessenek, de ha egy pontján elvágjuk a klaszterezési fát, akkor szintén szigorúan felosztó klaszterezéshez jutunk

Távolságmértékek

Láthattuk, hogy a különböző modellek szubjektíven értelmezik a hasonlóság fogalmát.  A hasonlóság gyakran van kis távolságként definiálva, ilyenkor szükséges az, hogy meghatározzuk a távolság mértékét.

A klaszteranalízis során használt távolságmérték kiválasztása kritikusan fontos lépés, mert ez alapján fogja a klaszterelemzés meghatározni, hogy két elem mennyire hasonló egymáshoz. Így a kiválasztott távolságmérték befolyásolja az eredményül kapott klaszterek alakját is.

Gyakori távolságmértékek

euklideszi távolság  – leggyakrabban használt távolságfüggvény, intervallum és arány  skálán mért metrikus adatoknál használható négyzetes euklideszi távolság Manhattan-távolság vagy abszolút eltérés Mahalanobis-távolság – általánosítja a standardizációs eljárást, figyelembe veszi a nem független változóknál a korreláció mértékét Hamming-féle távolság (a behelyettesítések minimális száma, amivel az egyik tag átváltható a másikba) Pearson-távolság – nem összemérhető változóknál, standardizálással számolva

Fontos szempont lehet a klaszterelemzés során, hogy szimmetrikus vagy aszimmetrikus távolságokat használunk-e. Az euklideszi távolság például szimmetrikus („A” távolsága „B”-től ugyanakkora, mint „B” távolsága „A”-tól). Más esetekben a távolság nem szimmetrikus (lásd például Prinzie & Van den Poel (2006)).

A klaszterelemzés fajtái

A klaszterelemzés algoritmusa lehet hierarchikus vagy nem hierarchikus. A hierarchikus algoritmus az új klasztereket az előzőleg kialakított klaszterek alapján keresi meg, míg a nem hierarchikus algoritmus egyszerre határozza meg az összes klasztert.

Hierarchikus klaszterelemzés

A hierarchikus klaszterezés lehet összevonó (Agglomerative) és felosztó (Divisive). Az összevonáson alapuló algoritmus először minden egyes elemet külön klaszternek tekint és összekapcsolja őket egyre nagyobb klaszterekbe, míg a végén egyetlen, az összes elemet tartalmazó klasztert kapunk. A felosztáson alapuló algoritmus ezzel ellentétben először az egész adattömböt egyetlen klaszternek tekinti és egyre kisebb klaszterekre osztja, míg a végén minden elem külön klasztert képez. Az eredményt általában egy fa (dendrogram) formájában szokták ábrázolni, ahol az egyik végén az egyes elemek találhatóak, a másik végén pedig egyetlen klaszter, ami az összes elemet tartalmazza. Az összevonáson alapuló algoritmus a fa tetején kezdi az elemzést, a felosztáson alapuló pedig a gyökereknél. Ha elvágjuk a fát egy bizonyos magasságban, akkor azon az adott ponton megpróbálhatjuk értelmezni a klaszterezés eredményét.

Példa az összevonáson alapuló hierarchikus klaszterezésre

Nézzük például az alábbi adatokat, melyeket csoportosítani szeretnénk:

középre|250px

Az alábbi dendrogramon látható, hogy ez a módszer úgy építi fel a hierarchiát az egyes elemekből, hogy egyre jobban összeolvasztja a klasztereket. Ebben a példában hat elem van: {a}, {b}, {c}, {d}, {e} és {f}. Az ábráról láthatjuk, hogy az algoritmus először összekapcsolta a két legközelebbi elemeket, a {b}-t és a {c}-t, valamint a {d}-t és az {e}-t. Ekkor a következő klasztereink vannak: {a}, {b, c}, {d, e} és {f}. Ezután a {d, e} klasztert a legközelebbi, leginkább hasonló elemmel, az {f}-fel kapcsolja össze. Ezen a szinten már csak három klaszterünk van: {a}, {b, c} és {d, e, f}.

középre|300px

A következő lépésben a {b, c} és a {d, e, f} klaszterek esnek a legközelebb egymáshoz, ezért ezekből jön létre egy új, nagy klaszter. Most már csak két klaszterünk van, az {a} és a {b, c, d, e, f}. Az összevonáson alapuló eljárás végeredményeként pedig egyetlen nagy klaszter jön létre, mely tartalmazza az összes elemet: {a, b, c, d, e, f}.

Korlátok A hierarchikus klaszterelemzésnek megvannak a saját korlátai. A legfontosabbak közé tartozik, hogy  két klaszter egyesítése nem visszafordítható, azaz utólag már nem módosítható. Ezenkívül a hierarchikus klaszterelemzés zaj és kiugró értékek iránti érzékenysége nagy, valamint nehezen kezeli a konvex alakú és a jelentősen eltérő méretű klasztereket, és a nagy klasztereket hajlamos feldarabolni (Dr. Obádovics Csilla, 2009 alapján). Végül, a hierarchikus klaszterelemzés csak folytonos, metrikus változókon alkalmazható (Venables and Ripley, 2002.)

Az összevonáson alapuló (agglomeratív) klaszterelemzés fajtái

Az összevonáson alapuló klaszterelemzésen belül különböző csoportosítási módszereket különböztetünk meg: a lánc-, a variancia- és a centroidmódszert.

’’’Egyszerű láncmódszer’’’ (Single linkage clustering): A legközelebbi szomszéd (:en: Nearest neighbor) elvén alapuló eljárás. Két klaszter közötti távolságot a két legközelebbi elem távolsága alapján számolja ki. ’’’Teljes láncmódszer’’’ (Complete linkage clustering): A legtávolabbi szomszéd (:en: Furthest neighbor) elvén alapuló eljárás. Két klaszter közötti távolságot a két legtávolabbi elem távolsága alapján határozza meg. ’’’Átlagos láncmódszer’’’ (Average linkage clustering): Két klaszter távolságát az összes elem páronkénti távolságának átlaga alapján határozza meg, ahol a pár egyik eleme az egyik klaszterbe, a másik eleme pedig a másik klaszterbe tartozik. Mivel ez az eljárás nem csak a legkisebb és legnagyobb távolságot használja fel, ezért általában előnyben részesítik a másik két láncmódszerrel szemben. ’’’Varianciamódszer’’’: A Ward-féle eljárás az egyik leggyakrabban alkalmazott módszer, mely azokat a klasztereket vonja össze, melyeknél az összevonás során a legkisebb lesz a belső szórásnégyzet növekedése. ’’’Centroidmódszer’’’: Két klaszter közötti távolságot a klaszterek centroidja alapján határozza meg. A klaszterek centroidját a klaszterben benne foglalt összes pont aritmetikai átlaga adja. Ezt a módszert is gyakran használják a klaszterelemzés során.

Nem hierarchikus klaszterelemzés K-közép klaszterelemzés

A nem hierarchikus klaszterelemzési módszerek közül a K-közép (:en: K-means) algoritmus a legnépszerűbb. A K-közép algoritmus minden egyes elemet ahhoz a klaszterhez sorol, amelyiknek a középpontja a legközelebb esik az adott elemhez.