Klaszteranalízis

A Wikipédiából, a szabad enciklopédiából

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 csoportosítás alapját különböző távolság- vagy hasonlóságmértékek képezik.

Távolságmértékek[szerkesztés | forrásszöveg szerkesztése]

A klaszter-analí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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

Clusters.PNG

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}.

Hierarchical clustering diagram.png

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}.

Az összevonáson alapuló (agglomeratív) klaszterelemzés fajtái[szerkesztés | forrásszöveg szerkesztése]

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ódszerrrel 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 bennefoglalt összes pont aritmetikai átlaga adja. Ezt a módszert is gyakran használják a klaszterelemzés során.

Nem hierarchikus klaszterelemzés[szerkesztés | forrásszöveg szerkesztése]

K-közép klaszterelemzés[szerkesztés | forrásszöveg szerkesztése]

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.

Az algoritmus lépései a következőek (MacQueen, 1967):

  • Kiválasztja a klaszterek számát (k).
  • Véletlenszerűen létrehoz k számú klasztert, és meghatározza minden klaszter közepét, vagy azonnal létrehoz k véletlenszerű klaszter középpontot.
  • Minden egyes pontot abba a klaszterbe sorol, amelynek középpontjához a legközelebb helyezkedik el.
  • Kiszámolja az új klaszter középpontokat.
  • Addig ismétli az előző két lépést (iterál), amíg valamilyen konvergenia kritérium nem teljesül (általában az, hogy a besorolás nem változik).

Az algoritmus legnagyobb előnye az egyszerűsége és a sebessége, ami lehetővé teszi az alkalmazását nagy adattömbön is. Hátránya viszont, hogy nem ugyanazt az eredményt adja különböző futtatások után, mert a klaszterezés eredményét befolyásolja a kezdeti random besorolás. Minimálisra csökkenti a klasztereken belüli varianciát, de nem eredményezi összességében a legkisebb varianciát.

Hierarchikus vagy nem hierarchikus klaszterezést használjunk? (Sajtos és Mitev (2007) alapján)[szerkesztés | forrásszöveg szerkesztése]

A nem hierarchikus módszereket akkor érdemes használni, ha sok adatunk van és a kapott eredmények kevésbé függnek a kiugró adatoktól és a kiválasztott távolságmértéktől. Ha azonban nem hierarchikus módszert választunk, előre meg kell adni a klaszterek számát és a klaszterközéppontokat. A hierarchikus módszerek végrehajtása nagy adatbázis esetében hosszadalmas lehet, és e módszerek érzékenyebbek a kiugró értékekre. Előnye azonban, hogy lehetővé teszi a klaszterek grafikus megjelenítését dendrogram formájában, ami jelentős segítséget nyújt a klaszterek számánál kiválasztásánál és az eredmények értelmezésénél. Ajánlott a hierarchikus és a nem hierarchikus módszereket egyszerre alkalmazni. Például először egy hierarchikus algoritmussal meghatározzuk a klaszterek számát, a klaszterközéppontokat, kiszűrjük a kiugró adatokat, majd a nem hierarchikus eljárással újracsoportosítjuk az adatokat.

A klaszterelemzés alkalmazási területei[szerkesztés | forrásszöveg szerkesztése]

Biológia[szerkesztés | forrásszöveg szerkesztése]

A klaszterelemzés rendkívül népszerű eljárás, melyet gyakran használnak például az ökológiában növény- és állatközösségek csoportosítására heterogén környezetben, növényrendszertanban egyedek csoportjainak meghatározására faj, család stb. szintjén. A bioinformatikán belül például a hasonló expressziós mintázatot létrehozó gének klaszterezésénál alkalmazzák.

Társadalomtudomány[szerkesztés | forrásszöveg szerkesztése]

A piackutatásban gyakran alkalmazott módszer például a piacszegmentálás során (amikor a fogyasztókat különböző csoportokba sorolják), piacszerkezet-elemzésnél, új termék lehetőségeinek feltárásánál, tesztpiacok kiválasztásánál. A klaszterelemzés kiválóan használható szociális hálózatok elemzésénél, amikor emberek nagy csoportját szeretnénk kisebb közösségekbe sorolni.

Informatika[szerkesztés | forrásszöveg szerkesztése]

A képfeldolgozásban a klaszterelemzés igénybevételével azonosíthatóak az élek vagy a tárgyak a képeken. A klaszterezés segítségével a weboldalak, webes keresési eredmények csoportokba rendezésénél relevánsabb szempontokat alkothatunk (szemben például a hagyományos keresőprogramokkal), vagy például internetes boltok termékeit is csoportosíthatjuk.

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297
  • Prinzie, A & Van den Poel, D. (2006). Incorporating sequential information into traditional classification models by using an element/position-sensitive SAM. Decision Support Systems 42 (2): 508-526.
  • Sajtos, L. & Mitev, A. (2007). SPSS kutatási és adatelemzési kézikönyv. Aliena Kiadó, Budapest.
  • Székelyi, M. & Barna, I. (2002). Túlélőkészlet az SPSS-hez. Többváltozós elemzési technikákról társadalomkutatók számára. Typotex Kiadó, Budapest.

Források[szerkesztés | forrásszöveg szerkesztése]