From Wikipedia, the free encyclopedia
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.
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.
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) :
A klaszterezés szintén megkülönböztethető az alapján, hogy mennyire éles a klaszterek közötti választóvonal:
Léteznek ennél még finomabb különbségek:
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.
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 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.
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.
Nézzük például az alábbi adatokat, melyeket csoportosítani szeretnénk:
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}.
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}.
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ó 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.
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):
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.
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 klaszterek számának megválasztása döntési probléma, nincs rá egyetlen elfogadott eljárás. Az egymást követő lépéseknél adódó klaszterek közötti távolság jó irányadó lehet. Akkor célszerű megállni, amikor pl. a távolságérték túllép egy bizonyos értéken, vagyis amikor a soron következő távolság jóval nagyobb az előzőeknél, hirtelen ugrás következik. (Obádovics, (2009) alapján)
A klaszterelemzés eredményeképpen kapott csoportok jóságát, validitását többféleképpen lehet értékelni, de ez gyakran éppoly nehéz feladat, mint a klaszterezés maga. A népszerű megközelítések közé tartozik a “belső” (internal) értékelés, amikoris a klaszterezés összesítve lesz egyetlen kvalitás értékbe, és a “külső” (external) értékelés, amikor a klaszterezés egy már létező, “alapvető igazság” osztályozáshoz van hasonlítva, a “kézi” (manuális) értékelése egy emberi szakértőnek, és az “indirekt” értékelés, amikor a klaszterek a későbbi alkalmazáskor tanúsított hasznosságuk alapján kerülnek értékelésére.
Mind a belső, mind a külső értékelésű mérőeszközöknek számos korlátja van. Előbbi nem mutat arra rá, hogy mennyire hasznos maga klaszterezés, míg utóbbi gyakran nem létező, vagy nem biztos, hogy a létező lehető legjobb címkékhez méri a klaszterezést, ami által az eredmény nem jelenti azt, hogy nem létezik egy másfajta, éppenséggel jobb klaszterezés.
Így a klaszterezés minőségét az emberi, erősen szubjektív értékelés tudja csak megmondani. Ez utóbbi megtartása mellett, a különböző értékelések hasznosak lehetnek a rossz klaszterezések azonosítására.
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.
A klaszteranalízis térbeli és időbeli összehasonlítására szolgálhat heterogén környezetben élő szervezetek közösségeire. Szintén használt növényi rendszertanban mesterséges törzsfejlődés képzésére vagy organizmusok faji, nemzetségi vagy fentebbi szintű, azonos tulajdonságokban osztozó klaszterekbe csoportosítására.
Klaszterezés használható különbözően kifejeződő gének csoportjainak megalkotására.
A genetikus adatok hasonlóságágból klaszterezéssel következtethetünk a populáció struktúrájára.
PET képeknél a klaszteranalízis használható a különböző típusú szövetek megkülönböztetésére háromdimenziós képeknél.
Klaszteranalízis használható az antibiotikus rezisztencia mintázatok elemzésére, vagyis osztályozni az antimikrobális vegyületeket a hatás-mechanizmusuk alapján, illetve osztályozni az antibiotikumokat az antibakteriális hatásuk alapján.
A stilometria a különböző szövegek közötti hasonlóságok és különbségek elemzésére használja. Alkalmas lehet például ismeretlen szerzőjű szövegek szerzőjének azonosítására.
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.
A klaszteranalízis széleskörűen alkalmazott piackutatások során, többváltozós tesztadatokkal dolgozva. A piackutatók általában arra használják a klaszteranalízist, hogy a fogyasztókat piacszegmensekbe osszák, és így jobban megértsék a különböző fogyasztói csoportok közti kapcsolatokat és ez piacszegmentációra, termék pozícionálásra, új termékek kifejlesztésére és teszt piacok kiválasztására felhasználják
A klaszterezés arra is alkalmas, hogy az összes interneten elérhető terméket egyedi termékek csoportjaira bontsa.
Közösségi hálózatok tanulmányozása során a klaszterezés képes lehet közösségek azonosítására nagyobb embercsoportokon belül
A klaszterezés alternatívát jelenthet a hagyományos keresőmotoroknak, mivel képes arra, hogy csoportosítsa a megtalált weboldalakot és fájlokat, és ezáltal relevánsabbá tegye a keresési eredményeket (például csoportosíthatja a találatokat, amikor a keresőszó több különböző dologra is utalhat).
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.
Klaszterelemzéssel azonosíthatók olyan területek, ahol gyakrabban fordulnak elő bizonyos típusú bűnügyek, ezáltal kialakítva úgynevezett forró pontokat, ami lehetővé teszi a bűnmegelőzési erőforrások hatékonyabb allokációját. Az igazságügyi nyelvészet a stilometriai klaszterelemzéssel képes lehet azonosítani egy szöveg szerzőjét.
Képzési célú adatbányászat
A klaszteranalízis használható arra, hogy iskolák vagy tanulók azonos tulajdonságokkal rendelkező csoportjait azonosítsuk.
Közvélemény-kutatási adatokból klaszterelemzéssel kinyerhetők véleményekre, szokásokra, és demográfiára vonatkozó tipológiák, amik hasznosak lehetnek a politikában és marketingben.
A klaszterelemzés hasznos megoldás olyan tudományterületeknél is, mint a robotika, matematikai kémia, klímakutatás, geográfia
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
