Klaszteranalízis

A klaszteranalízis egy többdimenziós statisztikai eljárás,  amely egy objektummintáról információkat tartalmazó adatokat gyűjt, majd az objektumokat viszonylag homogén csoportokba rendezi [1] [2] [3] [4] . A klaszterezési probléma a statisztikai feldolgozásra, valamint a nem felügyelt tanulási problémák széles csoportjára vonatkozik .

A legtöbb kutató (lásd például [5] ) hajlamos azt hinni, hogy a "klaszteranalízis" ( angolul  cluster - bunch, clot, bundle) kifejezést először R. Tryon  pszichológus javasolta [6] . Ezt követően számos olyan kifejezés merült fel, amelyeket jelenleg a "klaszteranalízis" kifejezés szinonimájaként tartanak számon: automatikus osztályozás, botriológia.

A klaszteranalízis alkalmazási köre igen széles: használják a régészetben , az orvostudományban , a pszichológiában , a kémiában , a biológiában , a közigazgatásban , a filológiában , az antropológiában , a marketingben , a szociológiában , a geológiában és más tudományágakban. Az alkalmazás egyetemessége azonban számos inkompatibilis kifejezés, módszer és megközelítés megjelenéséhez vezetett, amelyek megnehezítik a klaszteranalízis egyértelmű használatát és következetes értelmezését.

Feladatok és feltételek

A klaszterelemzés a következő fő feladatokat látja el:

• Tipológia vagy osztályozás kidolgozása.
• Hasznos fogalmi sémák feltárása az objektumok csoportosításához.
• Hipotézisek generálása adatfeltárás alapján.
• Hipotézisvizsgálat vagy kutatás annak megállapítására, hogy az így vagy úgy azonosított típusok (csoportok) valóban jelen vannak-e a rendelkezésre álló adatokban.

A vizsgálat tárgyától függetlenül a klaszteranalízis használata a következő lépéseket tartalmazza:

• Mintavétel a klaszterezéshez. Nyilvánvaló, hogy csak mennyiségi adatokat érdemes klaszterezni.
• Egy olyan változóhalmaz definíciója, amely alapján a mintában lévő objektumok kiértékelődnek, azaz egy jellemzőtér.
• Az objektumok közötti hasonlóság (vagy különbség) egyik vagy másik mértékének értékeinek kiszámítása.
• A klaszterelemzési módszer alkalmazása hasonló objektumok csoportjainak létrehozására.
• A klasztermegoldás eredményeinek validálása.

Az adatokkal szemben támasztott két alapvető követelmény leírása található - az egységesség és a teljesség. A homogenitás megköveteli, hogy minden klaszterezett entitás azonos jellegű legyen, és hasonló jellemzőkkel írják le [7] . Ha a klaszteranalízist faktoranalízis előzi meg , akkor a mintát nem kell „javítani” - a megadott követelményeket maga a faktormodellezési eljárás hajtja végre (van még egy előnye - a z-standardizálás a mintára nézve negatív következmények nélkül; ha közvetlenül klaszteranalízisre történik, ez a csoportok elkülönítésének egyértelműségének csökkenéséhez vezethet). Ellenkező esetben a mintát módosítani kell.

Klaszterezési problémák tipológiája

Bemeneti adattípusok

• Tárgyak tájékoztató jellegű leírása. Minden objektumot jellemzőinek halmaza ír le, amelyeket jellemzőknek nevezünk . A jellemzők lehetnek numerikusak vagy nem numerikusak.
• Az objektumok közötti távolságmátrix . Minden objektumot a metrikus tér többi objektumától mért távolságok írnak le .
• Az objektumok közötti hasonlósági mátrix [8] . Figyelembe kell venni az objektumnak a minta más objektumaihoz való hasonlóságának mértékét a metrikus térben. A hasonlóság itt kiegészíti az objektumok közötti távolságot (különbséget) 1-gyel.

A modern tudományban számos algoritmust használnak a bemeneti adatok feldolgozására. Az objektumok jellemzők alapján történő összehasonlításával végzett elemzést (a biológia tudományokban legelterjedtebb) Q -típusú elemzésnek, a tárgyakon alapuló jellemzők összehasonlítása esetén pedig R - típusú elemzésnek nevezzük. Vannak kísérletek hibrid típusú elemzések alkalmazására (például RQ -analízis ), de ez a módszertan még nincs megfelelően kidolgozva.

A klaszterezés céljai

• Adatok megértése a klaszterstruktúra azonosításával. A minta hasonló objektumok csoportjaira bontása lehetővé teszi a további adatfeldolgozás és döntéshozatal egyszerűsítését azáltal, hogy minden klaszterre saját elemzési módszert alkalmaz (az „ oszd meg és uralkodj ” stratégia).
• Adattömörítés . Ha a kezdeti minta túlságosan nagy, akkor csökkenthető, így minden klaszterből az egyik legtipikusabb képviselő marad.
• Újdonság észlelése _ _ _  A rendszer olyan atipikus objektumokat választ ki, amelyek nem csatolhatók egyik fürthöz sem.

Az első esetben a klaszterek számát próbálják csökkenteni. A második esetben fontosabb az egyes klasztereken belüli objektumok nagyfokú hasonlóságának biztosítása, és bármennyi klaszter lehet. A harmadik esetben azok az egyedi objektumok, amelyek egyik klaszterbe sem illeszkednek, a legnagyobb érdeklődésre tarthatnak számot.

Mindezekben az esetekben hierarchikus klaszterezés alkalmazható , amikor a nagy klasztereket kisebbekre bontják, amelyek viszont még kisebbre oszlanak, stb. Az ilyen feladatokat taxonómiai feladatoknak nevezzük . A taxonómia eredménye egy faszerű hierarchikus struktúra. Ezen túlmenően minden objektumot az összes olyan klaszter felsorolása jellemez, amelyekhez tartozik, általában a nagytól a kicsiig.

Klaszterezési módszerek

A klaszterezési módszereknek nincs általánosan elfogadott osztályozása, de számos megközelítési csoport megkülönböztethető (egyes módszerek egyszerre több csoporthoz is hozzárendelhetők, ezért javasolt ezt a tipizálást a klaszterezés valós osztályozásának közelítésének tekinteni. módszerek) [9] :

1. Valószínűségi megközelítés . Feltételezzük, hogy minden vizsgált objektum a k osztály valamelyikébe tartozik. Egyes szerzők (például A. I. Orlov) úgy vélik, hogy ez a csoport egyáltalán nem tartozik a klaszterezéshez, és „diszkrimináció” néven ellenzik azt, vagyis az objektumok valamelyik ismert csoporthoz való hozzárendelését (képzési minták).
   • K- jelenti
   • K-medián
   • EM algoritmus
   • FOREL család algoritmusai
   • Diszkriminancia elemzés
2. Mesterséges intelligencia rendszerekre épülő megközelítések: nagyon feltételes csoport, hiszen rengeteg módszer létezik és módszertanilag is nagyon eltérőek.
   • C- közép fuzzy klaszterezési módszer ( C-means )
   • Kohonen neurális hálózata
   • genetikai algoritmus
3. logikus megközelítés. A dendrogram felépítése döntési fa segítségével történik.
4. Gráfelméleti megközelítés.
   • Grafikon klaszterező algoritmusok
5. Hierarchikus megközelítés. Beágyazott csoportok (különböző sorrendű klaszterek) jelenlétét feltételezzük. Az algoritmusokat pedig agglomeratív (egyesítő) és osztó (elválasztó) részekre osztják. A jellemzők száma szerint néha megkülönböztetnek monotetikus és politetikus osztályozási módszereket.
   • Hierarchikus felosztási klaszterezés vagy taxonómia. A klaszterezési problémákat a kvantitatív taxonómia kezeli .
6. Egyéb módszerek. Nem szerepel az előző csoportokban.
   • Statisztikai klaszterezési algoritmusok
   • Klaszterek együttese
   • A KRAB család algoritmusai
   • Szitálási módszeren alapuló algoritmus
   • DBSCAN stb.

A 4. és 5. megközelítést néha a strukturális vagy geometriai megközelítés elnevezéssel kombinálják, amely a közelség formalizáltabb fogalmával rendelkezik [10] . A felsorolt ​​módszerek közötti jelentős különbségek ellenére mindegyik az eredeti „ tömörségi hipotézisre ” támaszkodik : az objektumtérben minden közeli objektumnak ugyanabba a klaszterbe kell tartoznia, illetve minden objektumnak különböző klaszterben kell lennie.

A klaszterezési probléma formális megfogalmazása

Legyen  objektumok  halmaza, klaszterek számainak (neveinek, címkéinek) halmaza. Az objektumok közötti távolságfüggvény adott . Az objektumok véges tanítókészlete létezik . A mintát nem átfedő részhalmazokra, úgynevezett klaszterekre kell felosztani , hogy minden klaszter olyan objektumokból álljon, amelyek metrikusan közel állnak egymáshoz , és a különböző klaszterek objektumai jelentősen eltérnek egymástól. Ebben az esetben minden objektumhoz hozzá van rendelve egy fürtszám .

A fürtözési algoritmus  egy olyan függvény , amely bármely objektumot fürtszámhoz rendel . A halmaz bizonyos esetekben előre ismert, de gyakrabban a klaszterek optimális számának meghatározása a feladat, a klaszterezés minőségének egyik vagy másik kritériuma szempontjából .

A klaszterezés (felügyelt tanulás ) abban különbözik az osztályozástól ( felügyelt tanulás ), hogy az eredeti objektumok címkéi kezdetben nincsenek beállítva, sőt maga a halmaz ismeretlen is lehet .

A klaszterezési probléma megoldása alapvetően nem egyértelmű, ennek több oka is van (több szerző szerint):

• nincs egyedülállóan legjobb kritérium a klaszterezés minőségére. Számos heurisztikus kritérium ismert, valamint számos olyan algoritmus, amelyek nem rendelkeznek egyértelműen meghatározott kritériummal, de meglehetősen ésszerű klaszterezést hajtanak végre „konstrukció alapján”. Mindegyik különböző eredményt adhat. Ezért a klaszterezés minőségének meghatározásához a témakör szakértője szükséges, aki felmérheti a klaszterek kiválasztásának értelmét.
• a klaszterek száma általában előre nem ismert, és valamilyen szubjektív kritérium alapján van beállítva. Ez csak a diszkriminációs módszerekre igaz, mivel a klaszterezési módszerekben a klaszterek kiválasztása formalizált közelítési mérőszámokon alapuló megközelítéssel történik.
• a klaszterezés eredménye jelentősen függ a mérőszámtól, amelynek megválasztása általában szintén szubjektív, és szakértő határozza meg. De számos ajánlás létezik a közelítési intézkedések kiválasztására különböző feladatokhoz.

Alkalmazás

A biológiában

A biológiában a klaszterezés számos területen alkalmazható. Például a bioinformatikában kölcsönható gének összetett hálózatainak elemzésére használják, amelyek néha több száz vagy akár több ezer elemből állnak. A klaszteranalízis lehetővé teszi a vizsgált rendszer alhálózatainak, szűk keresztmetszeteinek, hubjainak és egyéb rejtett tulajdonságainak azonosítását, ami végső soron lehetővé teszi az egyes gének hozzájárulásának a vizsgálatát a vizsgált jelenség kialakulásához.

Az ökológia területén széles körben használják térben homogén élőlénycsoportok, közösségek stb. azonosítására. Ritkábban alkalmaznak klaszterelemzési módszereket a közösségek időbeli vizsgálatára. A közösségek szerkezetének heterogenitása a klaszterelemzés nem triviális módszereinek megjelenéséhez vezet (például a Czekanowski-módszer ).

Történelmileg a hasonlóság mértékét gyakrabban használták a biológiában a közelség mértékeként , nem pedig a különbség (távolság) mértékeként.

A szociológiában

A szociológiai kutatások eredményeinek elemzésekor ajánlatos az elemzést egy hierarchikus agglomeratív család módszereivel, nevezetesen a Ward-módszerrel végezni, amelyben a klasztereken belüli minimális diszperziót optimalizálják, ennek eredményeként megközelítőleg azonos méretű klaszterek jönnek létre. jönnek létre. A szociológiai adatok elemzésére Ward módszere a legsikeresebb. A különbség mértékeként a kvadratikus euklideszi távolság jobb, ami hozzájárul a klaszterek kontrasztjának növekedéséhez. A hierarchikus klaszteranalízis fő eredménye egy dendrogram vagy "jégcsapdiagram". Értelmezése során a kutatók a faktoranalízis eredményeinek értelmezéséhez hasonló problémával szembesülnek - a klaszterek azonosításának egyértelmű kritériumainak hiányával. Főként két módszer alkalmazása javasolt - a dendrogram vizuális elemzése és a különböző módszerekkel végzett klaszterezés eredményeinek összehasonlítása.

A dendrogram vizuális elemzése magában foglalja a fa "kivágását" a mintaelemek hasonlóságának optimális szintjén. A „szőlőágat” (M. S. Oldenderfer és R. K. Blashfield [11] terminológiája ) a Rescaled Distance Cluster Combine skála 5-ös pontjánál „le kell vágni”, így 80%-os hasonlósági szint érhető el. Ha a klaszterek kiválasztása ezzel a címkével nehézkes (több kis fürt egyesül egy nagyba rajta), akkor választhat másik címkét. Ezt a technikát Oldenderfer és Blashfield javasolta.

Most felmerül az elfogadott klasztermegoldás stabilitásának kérdése. Valójában a klaszterezés stabilitásának ellenőrzése a megbízhatóságának ellenőrzésén múlik. Itt van egy ökölszabály – a stabil tipológia megmarad, ha a klaszterezési módszerek megváltoznak. A hierarchikus klaszteranalízis eredményei iteratív k-közép klaszteranalízissel ellenőrizhetők. Ha a válaszadói csoportok összehasonlított besorolásaiban az egyezések aránya meghaladja a 70%-ot (az egybeesések több mint 2/3-a), akkor klaszterdöntés születik.

Lehetetlen ellenőrizni a megoldás megfelelőségét más típusú elemzés igénybevétele nélkül. Legalábbis elméletileg ez a probléma nem oldódott meg. Oldenderfer és Blashfield klasszikus klaszterelemzése öt további robusztussági vizsgálati módszert dolgoz ki, és végül elutasít:

1. kofenetikus korreláció  - nem ajánlott és korlátozott a felhasználása;
2. szignifikancia tesztek (varianciaanalízis) - mindig szignifikáns eredményt adnak;
3. az ismételt (véletlenszerű) minták technikája, amely azonban nem bizonyítja a döntés érvényességét;
4. a külső jellemzőkre vonatkozó szignifikanciavizsgálatok csak ismételt mérésekre alkalmasak;
5. A Monte Carlo módszerek nagyon összetettek, és csak tapasztalt matematikusok számára hozzáférhetők .

Az informatikában

• Keresési eredmények klaszterezése  – a találatok „intelligens” csoportosítására szolgál fájlok , webhelyek , egyéb objektumok keresésekor , lehetővé téve a felhasználó számára, hogy gyorsan navigáljon, válasszon ki egy ismert relevánsabb részhalmazt, és kizárjon egy ismert, kevésbé releváns részhalmazt – ami növelheti a használhatóságot . az interfész összehasonlítása az egyszerű relevancia lista formájában megjelenő kimenettel .
  • A Clusty a Vivísimo  klaszterező keresőmotorja .
  • A Nigma  egy orosz keresőmotor automatikus találatcsoportosítással
  • Quintura  - vizuális klaszterezés kulcsszófelhő formájában
• Képszegmentálás ( angol.  képszegmentálás ) – a klaszterezés használható a digitális kép felosztására külön területekre a határok észlelése ( angol.  élérzékelés ) vagy tárgyfelismerés érdekében .
• Az adatbányászat –  a klaszterezés az adatbányászatban akkor válik értékessé, ha az adatelemzés egyik szakaszaként működik, és egy teljes analitikai megoldást épít fel .  Az elemzőnek gyakran könnyebb azonosítani a hasonló objektumok csoportjait, tanulmányozni a jellemzőit, és minden csoporthoz külön modellt építeni, mint egy általános modellt létrehozni az összes adathoz. Ezt a technikát folyamatosan alkalmazzák a marketingben, kiemelve vásárlói csoportokat, vásárlókat, árukat, és mindegyikre külön stratégiát dolgoznak ki.

Lásd még

• Dokumentumcsoportosítás
• Dokumentum minősítés
• Neurális hálózatok
• Kohonen önszerveződő térképe
• A pénzügyi piacok klaszterelemzése archiválva 2017. február 21-én a Wayback Machine -nél

Jegyzetek

1. ↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Alkalmazott statisztika: Osztályozás és méretcsökkentés. - M .: Pénzügy és statisztika, 1989. - 607 p.
2. ↑ Mandel I. D. Klaszterelemzés. — M.: Pénzügy és statisztika, 1988. — 176 p.
3. ↑ Khaidukov D.S. A klaszteranalízis alkalmazása a közigazgatásban // Matematika filozófiája: Aktuális problémák. — M.: MAKS Press, 2009. — 287 p.
4. ↑ Osztályozás és klaszter. Szerk. J. Wen Raizina. M.: Mir, 1980. 390 p.
5. ↑ Mandel I. D. Klaszterelemzés. - M .: Pénzügy és statisztika, 1988. - 10. o.
6. ↑ Tryon RC klaszterelemzés. - London: Ann Arbor Edwards Bros, 1939. - 139 p.
7. ↑ Zhambyu M. Hierarchikus klaszterelemzés és megfeleltetések. — M.: Pénzügy és statisztika, 1988. — 345 p.
8. ↑ Duran B., Odell P. Klaszteranalízis. — M.: Statisztika, 1977. — 128 p.
9. ↑ Berikov V. S., Lbov G. S. A klaszterelemzés modern trendjei Archív példány 2013. augusztus 10-én a Wayback Machine -nél // Össz-oroszországi versenyképes válogatás áttekintő és elemző cikkekből az „Információs és telekommunikációs rendszerek” kiemelt irányban, 2008. - 26 p. .
10. ↑ Vjatcsenin D. A. Az automatikus osztályozás homályos módszerei. - Minszk: Technoprint, 2004. - 219 p.
11. ↑ Oldenderfer M.S., Blashfield R.K. Klaszterelemzés / Faktor-, diszkriminancia- és klaszteranalízis: per. angolról; Alatt. szerk. I. S. Enyukova. — M.: Pénzügy és statisztika, 1989—215 p.

Linkek

• A www.MachineLearning.ru  egy professzionális wiki-forrás, amely a gépi tanulással és az adatbányászattal foglalkozik

• COMPACT – Összehasonlító csomag a klaszterezés értékeléséhez , archiválva 2007. február 26-án a Wayback Machine -nél . Egy ingyenes Matlab csomag, 2006.
• P. Berkhin, Felmérés a fürtözési adatbányászati ​​technikákról , archiválva : 2007. január 17., a Wayback Machine , Accrue Software, 2002.
• Jain, Murty és Flynn: Data Clustering: A Review Archiválva : 2007. február 3., a Wayback Machine , ACM Comp. Surv., 1999.
• a hierarchikus, a k-középek és a fuzzy c-means egy másik bemutatásához lásd a klaszterezés bevezetőjét. Archivált 2007. január 29. a Wayback Machine -nél . Magyarázatot is tartalmaz a Gauss -féle keveredésről .
• David Dowe, Mixture Modeling page Archivált : 2007. április 5. a Wayback Machine -nél  – egyéb klaszterezési és keverékmodell-hivatkozások.
• oktatóanyag a klaszterezésről [1]  (lefelé mutató link 2013. 05. 13. óta [3454 nap] - előzmények )
• Az on-line tankönyv: Információelmélet, következtetés és tanulási algoritmusok archiválva 2015. február 6-án a Wayback Machine -nél , David JC MacKay , a k-közép klaszterezésről, a lágy k-közép klaszterezésről, valamint a levezetésekről, beleértve az EM algoritmust és a variációt is tartalmaz. az EM algoritmus nézete.
• A nem-paraméteres klaszterezés és a számítógépes látás áttekintése
• „Az önszerveződő gén” oktatóanyag, amely a klaszterezést versengő tanuláson és önszerveződő térképeken keresztül magyarázza.
• kernlab  (2013. 05. 13. óta lefelé irányuló kapcsolat [3454 nap] - előzmények )  – R csomag kernel alapú gépi tanuláshoz (a spektrális fürtözés megvalósítását tartalmazza)
• Oktatóanyag archiválva 2007. december 29-én a Wayback Machine -nél  - Oktatóanyag a fürtözési algoritmusok (k-középek, fuzzy-c-means, hierarchikus, Gauss-féle keverék) bemutatásával + néhány interaktív demó (java kisalkalmazások)
• Adatbányászati ​​szoftver archiválva 2017. június 24-én a Wayback Machine -nél  – Az adatbányászati ​​szoftverek gyakran használnak klaszterezési technikákat.
•  Java Competive Learning Application (2013. 05. 13. óta lefelé irányuló kapcsolat [3454 nap] - előzmények ) Felügyelet nélküli neurális hálózatok csomagja fürtözéshez. Java nyelven írva. Teljes forráskóddal.
• Machine Learning Software archiválva 2018. április 3-án a Wayback Machine -nél  – Sok fürtözési szoftvert is tartalmaz.
• Fuzzy klaszterezési algoritmusok és alkalmazásuk az orvosi képelemzéshez PhD értekezés, 2001, AI Shihab. Archivált : 2007. szeptember 27. a Wayback Machine -nél
• Cluster Computing and MapReduce 4. előadás archiválva 2019. január 14-én a Wayback Machine -nél
• PyClustering Library archiválva 2018. június 11-én a Wayback Machine -nél  - A Python könyvtár fürtözési algoritmusokat tartalmaz (a C++ forráskód is használható - a könyvtár CCORE része) és neurális és oszcillációs hálózatok gyűjteményét példákkal és bemutatókkal.

Szótárak és enciklopédiák	nagy kínai nagy kínai nagy kínai nagy kínai Nagy orosz Britannica (online)
Bibliográfiai katalógusokban	BNF : 12124521b J9U : 987007283912705171 LCCN : sh85027250 NKC : ph161652