Poskytuje aktuálny a dôležitý úvod do fuzzy zhlukovej analýzy, jej metód a použitia. Systematicky popisuje rôzne techniky fuzzy zhlukovania, aby si čitateľ mohol vybrať metódu najvhodnejšiu na riešenie jeho problému. Existuje dobrý a veľmi komplexný prehľad literatúry o predmete, rozpoznávaní obrázkov, klasifikácii pokrytia, analýze údajov a odvodení pravidiel. Príklady sú dostatočne ilustratívne a poskytujú. výsledky boli testované.
Toto je najpodrobnejšia kniha o fuzzy zhlukovaní, a preto sa odporúča počítačovým vedcom, matematikom, inžinierom - každému, kto sa zaoberá analýzou údajov a spracovaním obrazu. Bude to užitočné aj pre študentov, ktorí pracujú v oblasti počítačových vied.
Práca je venovaná jednej z metód teórie rozpoznávania vzorov — zhlukovej analýze.
Stručnou formou sú prezentované hlavné myšlienky zhlukovej analýzy a sú uvedené niektoré oblasti jej aplikácie v banskom výskume. Popísané metódy klastrovania je možné použiť v reálnych problémoch. V algoritmoch je výpočtová časť uvažovaná dostatočne podrobne.
Napriek tomu, že klastrová analýza je efektívnym a pohodlným klasifikačným nástrojom a je tiež veľmi bežná v praktickom výskume, existuje len veľmi málo publikácií na túto tému v ruštine a tie existujúce sú neinformatívne. Táto brožúra zdôrazňuje niektoré zo základných problémov klastrovej analýzy.
Pre výskumníkov, dizertátorov a odborníkov pracujúcich v oblasti viacrozmernej štatistickej analýzy.
značky,Témou knihy je prehľad stavu teórie a praxe aplikácie "zhlukovej analýzy". Táto metóda má všetky výhody kombinovanej metódy zoskupovania a nie je zbavená svojej hlavnej nevýhody - materiálovej disperzie, ktorá otvára široké možnosti použitia danej metódy v štatistickej analýze, pri klasifikácii objektov, v štúdiu. vzťahov, vzorová typizácia a pod. Kniha sa vyznačuje úplnosťou, prístupnosťou a spolu so stručnosťou prezentácie. Kniha je určená štatistikom, ekonómom, ale aj sociológom, demografom, biológom a ďalším odborníkom. Reprodukované v pôvodnom autorskom pravopise vydania z roku 1977 (vydavateľstvo Statistica).
značky,Témy výskumu siahajú od analýzy morfológie mumifikovaných hlodavcov na Novej Guinei po štúdium výsledkov hlasovania amerických senátorov, od analýzy behaviorálnych funkcií mrazených švábov po rozmrazení až po štúdium geografického rozšírenia. niektorých druhov lišajníkov v Saskatchewane.
Táto explózia publikácií mala obrovský vplyv na vývoj a aplikáciu klastrovej analýzy. Ale, bohužiaľ, existujú aj negatívne stránky. Rýchly rast publikácií o zhlukovej analýze viedol k vytvoreniu zoskupení používateľov a v dôsledku toho k vytvoreniu žargónu používaného iba zoskupeniami, ktoré ho vytvorili (Blashfield a Aldenderfer, 1978; Blashfield, 1980).
O formovaní žargónu sociálnymi vedcami svedčí napríklad rôznorodá terminológia súvisiaca s Wardovou metódou. „Wardova metóda“ sa v literatúre nazýva inak. Známe sú aspoň štyri ďalšie jej názvy: „metóda minimálneho rozptylu“, „metóda súčtu štvorcových chýb“, „minimalizácia hierarchického zoskupenia“ a „HGROUP“. Prvé dva názvy jednoducho odkazujú na kritérium, ktorého optimum je určené Wardovou metódou, zatiaľ čo tretí súvisí so súčtom štvorcových chýb, čo je monotónna stopová transformácia matice W, vnútroskupinovej kovariančnej matice. Napokon, bežne používaný názov „HGROUP“ je názov populárneho počítačového programu, ktorý implementuje Wardovu metódu (Veldman, 1967).
Vytváranie žargónu bráni rozvoju interdisciplinárnych prepojení, bráni efektívnemu porovnávaniu metodológie a výsledkov aplikácie zhlukovej analýzy v rôznych oblastiach vedy, vedie k zbytočnému úsiliu (znovuvynájdenie rovnakých algoritmov) a napokon neprináša nové používateľom hlboké pochopenie metód, ktoré si zvolili (Blashfield a aldenderfer, 1978). Napríklad jedna spoločenskovedná štúdia (Rogers a Linden, 1973) porovnávala tri rôzne metódy zhlukovania s použitím rovnakých údajov. Tieto metódy nazvali takto: „hierarchické zoskupovanie“, „hierarchické zoskupovanie alebo HCG“ a „zhluková analýza“. A žiadny z týchto názvov nebol známy metódam klastrovania. Začínajúci používateľ programov klastrovej analýzy bude zmätený všetkými existujúcimi názvami a nebude ich môcť priradiť k iným popisom metód klastrovania. Skúsení používatelia sa ocitnú v ťažkej pozícii pri porovnávaní svojho výskumu s podobnou prácou. Možno zachádzame do extrémov, ale žargón je vážny problém.
V posledných rokoch sa vývoj zhlukovej analýzy trochu spomalil, súdiac podľa počtu publikácií a počtu odborov, kde sa táto metóda uplatňuje. Dá sa povedať, že v súčasnosti psychológia, sociológia, biológia, štatistika a niektoré technické disciplíny vstupujú do fázy konsolidácie vo vzťahu ku zhlukovej analýze.
Počet článkov vychvaľujúcich prednosti zhlukovej analýzy postupne klesá. Zároveň pribúdajú práce, v ktorých sa porovnáva použiteľnosť rôznych metód zhlukovania na kontrolných dátach. V literatúre sa viac pozornosti venuje aplikáciám. Mnohé štúdie sú zamerané na vývoj praktických opatrení na testovanie platnosti výsledkov získaných pomocou klastrovej analýzy. To všetko svedčí o serióznych pokusoch o vytvorenie rozumnej štatistickej teórie zhlukových metód.
Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár
Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, vám budú veľmi vďační.
Úvod
1. História "zhlukovej analýzy"
2.Terminológia
2.1 Predmet a podpis
2.2 Vzdialenosť medzi objektmi (metrická)
2.3Hustota a lokalita zhlukov
2.4 Vzdialenosť medzi klastrami
3. Metódy zoskupovania
3.1 Vlastnosti hierarchických aglomeračných metód
3.2 Vlastnosti metód iteratívneho zhlukovania
4. Klastrovanie funkcií
5. Stabilita a kvalita klastrovania
Bibliografia
ÚVOD
"Zhluková analýza je súbor matematických metód navrhnutých tak, aby vytvárali relatívne "vzdialené" od seba skupiny "blízkých" objektov podľa informácií o vzdialenostiach alebo spojeniach (mierach blízkosti) medzi nimi. Významovo je podobná pojmom: automatický klasifikácia, taxonómia, rozpoznávanie vzorov bez učiteľa.“ Táto definícia zhlukovej analýzy je uvedená v najnovšom vydaní Štatistického slovníka. V skutočnosti je „zhluková analýza“ zovšeobecnený názov pre pomerne veľkú skupinu algoritmov používaných na vytvorenie klasifikácie. Množstvo publikácií používa aj také synonymá pre analýzu zhlukov, ako je klasifikácia a rozdelenie. Zhluková analýza je vo vede široko používaná ako prostriedok typologickej analýzy. V akejkoľvek vedeckej činnosti je klasifikácia jednou zo základných zložiek, bez ktorej nie je možné budovať a testovať vedecké hypotézy a teórie. Preto vo svojej práci považujem za potrebné zamyslieť sa nad problematikou zhlukovej analýzy (základ zhlukovej analýzy), zamyslieť sa nad jej terminológiou a uviesť niekoľko príkladov použitia tejto metódy so spracovaním údajov ako hlavným cieľom.
1. HISTÓRIA "Zhlukovej analýzy"
Analýza domácich a zahraničných publikácií ukazuje, že zhluková analýza sa používa v širokej škále vedných oblastí: chémia, biológia, medicína, archeológia, história, geografia, ekonómia, filológia atď. Kniha VV Nalimova „Pravdepodobnostný model jazyka“ popisuje využitie zhlukovej analýzy pri štúdiu 70 analytických vzoriek. Väčšina literatúry o klastrovej analýze sa objavila počas posledných troch desaťročí, hoci prvé práce, ktoré spomínali klastrové metódy, sa objavili už dávno. Poľský antropológ K. Chekanowski predložil myšlienku „štrukturálnej klasifikácie“, ktorá obsahovala hlavnú myšlienku zhlukovej analýzy - rozdelenie kompaktných skupín objektov.
V roku 1925 sovietsky hydrobiológ P.V. Terentyev vyvinul takzvanú „metódu korelačných plejád“, určenú na zoskupovanie korelovaných znakov. Táto metóda dala podnet na vývoj metód zoskupovania pomocou grafov. Termín „zhluková analýza“ prvýkrát navrhol Trion. Slovo "cluster" je preložené z angličtiny ako "parta, kefa, partia, skupina". Z tohto dôvodu sa tento typ analýzy pôvodne nazýval „zhluková analýza“. Začiatkom 50. rokov sa objavili publikácie R. Lewisa, E. Fixa a J. Hodgesa o algoritmoch hierarchickej klastrovej analýzy. Výrazný impulz k rozvoju práce na zhlukovej analýze dala práca R. Rosenblatta o rozpoznávacom zariadení (perceptróne), ktorá položila základ pre rozvoj teórie „rozpoznania vzorov bez učiteľa“.
Impulzom pre rozvoj metód zhlukovania bola kniha „Principles of Numerical Taxonomy“, vydaná v roku 1963. dvaja biológovia - Robert Sokal a Peter Sneath. Autori tejto knihy vychádzali zo skutočnosti, že na vytvorenie efektívnych biologických klasifikácií by postup zhlukovania mal zabezpečiť použitie rôznych ukazovateľov charakterizujúcich skúmané organizmy, posúdiť mieru podobnosti medzi týmito organizmami a zabezpečiť umiestnenie podobných organizmov. v rovnakej skupine. V tomto prípade by mali byť vytvorené skupiny dostatočne „lokálne“, t.j. podobnosť predmetov (organizmov) v rámci skupín by mala prevyšovať podobnosť skupín medzi sebou. Následná analýza identifikovaných skupín môže podľa autorov objasniť, či tieto skupiny zodpovedajú rôznym biologickým druhom. Sokal a Sneath teda predpokladali, že odhalenie štruktúry rozloženia objektov do skupín pomáha nastoliť proces formovania týchto štruktúr. A práve odlišnosť a podobnosť organizmov rôznych zhlukov (skupín) môže slúžiť ako základ pre pochopenie prebiehajúceho evolučného procesu a objasnenie jeho mechanizmu.
V tých istých rokoch navrhli mnoho algoritmov takí autori ako J. McKean, G. Ball a D. Hall využívajúce metódy k-means; G. Lance a W. Williams, N. Jardine a ďalší - o hierarchických metódach. K vývoju metód klastrovej analýzy významne prispeli domáci vedci - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Najmä v 60-70 rokoch. Početné algoritmy vyvinuté novosibirskými matematikmi N. G. Zagoruikom, V. N. Elkinom a G. S. Lbovom sa tešili veľkej obľube. Sú to také známe algoritmy ako FOREL, BIGFOR, KRAB, NTTP, DRET, TRF atď. Na základe týchto balíkov bol vytvorený špecializovaný softvérový balík OTEX. Nemenej zaujímavé softvérové produkty PPSA a Class-Master vytvorili moskovskí matematici S.A. Aivazyan, I.S. Enyukov a B.G. Mirkin.
Metódy zhlukovej analýzy sú do určitej miery dostupné vo väčšine najznámejších domácich a zahraničných štatistických balíkov: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, COPRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S -PLUS atď. Samozrejme, 10 rokov po zverejnení tejto recenzie sa toho zmenilo pomerne veľa, objavili sa nové verzie mnohých štatistických programov a objavili sa úplne nové programy, ktoré využívajú nové algoritmy a výrazne zvýšili výpočtový výkon. Väčšina štatistických balíkov však používa algoritmy navrhnuté a vyvinuté v 60-70 rokoch.
Podľa hrubých odhadov odborníkov sa počet publikácií o zhlukovej analýze a jej aplikáciách v rôznych oblastiach poznania každé tri roky zdvojnásobí. Aké sú dôvody takého búrlivého záujmu o tento typ analýzy? Objektívne existujú tri hlavné dôvody tohto javu. Ide o vznik výkonnej výpočtovej technológie, bez ktorej nie je prakticky možná klastrová analýza reálnych údajov. Druhým dôvodom je, že moderná veda je vo svojich konštrukciách stále viac založená na klasifikácii. Navyše sa tento proces stále viac prehlbuje, keďže paralelne s tým dochádza k narastajúcej špecializácii vedomostí, čo je nemožné bez dostatočne objektívnej klasifikácie.
Tretí dôvod - prehlbovanie špeciálnych vedomostí nevyhnutne vedie k zvýšeniu počtu premenných, ktoré sa berú do úvahy pri analýze určitých objektov a javov. V dôsledku toho sa subjektívna klasifikácia, ktorá sa predtým spoliehala na pomerne malý počet zohľadňovaných znakov, často ukazuje ako nespoľahlivá. A objektívna klasifikácia so stále rastúcim súborom charakteristík objektov si vyžaduje použitie zložitých zhlukových algoritmov, ktoré možno implementovať iba na základe moderných počítačov. Práve z týchto dôvodov vznikol „klastrový boom“. Medzi lekármi a biológmi sa však zhluková analýza ešte nestala pomerne populárnou a bežnou výskumnou metódou.
2 TERMINOLÓGIA
2. 1 PREDMET A ZNAK
Najprv predstavme také pojmy ako objekt a znak. Objekt – z latinského objectum – subjekt. Objektmi budeme vo vzťahu k chémii a biológii rozumieť špecifické predmety výskumu, ktoré sa študujú pomocou fyzikálnych, chemických a iných metód. Takýmito predmetmi môžu byť napríklad vzorky, rastliny, zvieratá atď. Určitý súbor objektov, ktoré má výskumník k dispozícii na štúdium, sa nazýva vzorka alebo súbor vzoriek. Počet objektov v takejto populácii sa zvyčajne nazýva veľkosť vzorky. Veľkosť vzorky sa zvyčajne označuje latinským písmenom "n" alebo "N".
Znak (synonymá - vlastnosť, premenná, charakteristika; angl. - premenná - premenná.) - je špecifická vlastnosť objektu. Tieto vlastnosti môžu byť vyjadrené ako číselné alebo nečíselné hodnoty. Napríklad krvný tlak (systolický alebo diastolický) sa meria v milimetroch ortuťového stĺpca, hmotnosť v kilogramoch, výška v centimetroch atď. Takéto znaky sú kvantitatívne. Na rozdiel od týchto spojitých numerických charakteristík (stupníc) môže mať množstvo znakov diskrétne, nespojité hodnoty. Na druhej strane sú takéto diskrétne znaky zvyčajne rozdelené do dvoch skupín.
1) Prvou skupinou sú poradové premenné, alebo ako sa tiež nazývajú poradové premenné (škály). Takéto znaky sa vyznačujú vlastnosťou usporiadania týchto hodnôt. Patria sem štádiá konkrétnej choroby, vekové skupiny, skóre vedomostí študentov, 12-bodová Richterova stupnica magnitúdy zemetrasenia atď.
2) Druhá skupina diskrétnych znakov takéto poradie nemá a nazýva sa nominálnymi (od slova „nominálny“ – vzorka) alebo klasifikačnými znakmi. Príkladom takýchto znakov môže byť stav pacienta – „zdravý“ alebo „chorý“, pohlavie pacienta, obdobie pozorovania – „pred liečbou“ a „po liečbe“ atď. V týchto prípadoch je zvykom povedať, že takéto znaky patria do stupnice mien.
Koncepty objektu a funkcie sa zvyčajne nazývajú matica „vlastnosti objektu“ alebo „vlastnosti objektu“. Matica bude obdĺžniková tabuľka pozostávajúca z hodnôt funkcií, ktoré opisujú vlastnosti skúmanej vzorky pozorovaní. V tejto súvislosti sa jedno pozorovanie zaznamená ako samostatný riadok pozostávajúci z hodnôt použitých funkcií. Samostatný atribút v takejto matici údajov bude reprezentovaný stĺpcom pozostávajúcim z hodnôt tohto atribútu pre všetky objekty vo vzorke.
2. 2 VZDIALENOSŤ MEDZI PREDMETMI (METRICKÁ)
Predstavme si pojem „vzdialenosť medzi objektmi“. Tento koncept je integrálnou mierou podobnosti objektov navzájom. Vzdialenosť medzi objektmi v priestore prvkov je taká hodnota d ij, ktorá spĺňa nasledujúce axiómy:
1. d ij > 0 (nezápornosť vzdialenosti)
2. d ij = d ji (symetria)
3. d ij + d jk > d ik (trojuholníková nerovnosť)
4. Ak sa d ij nerovná 0, potom i sa nerovná j (rozlíšiteľnosť neidentických predmetov)
5. Ak d ij = 0, potom i = j (nerozoznateľnosť identických predmetov)
Je vhodné reprezentovať mieru blízkosti (podobnosť) objektov ako prevrátenú hodnotu vzdialenosti medzi objektmi. Početné publikácie venované zhlukovej analýze opisujú viac ako 50 rôznych spôsobov výpočtu vzdialenosti medzi objektmi. Okrem pojmu „vzdialenosť“ sa v literatúre často vyskytuje aj ďalší pojem – „metrika“, ktorý zahŕňa metódu výpočtu konkrétnej vzdialenosti. Najdostupnejšia pre vnímanie a pochopenie v prípade kvantitatívnych znakov je takzvaná „euklidovská vzdialenosť“ alebo „euklidovská metrika“. Vzorec na výpočet tejto vzdialenosti je:
Tento vzorec používa nasledujúci zápis:
· d ij - vzdialenosť medzi i-tým a j-tým objektom;
· x ik - číselná hodnota k-tej premennej pre i-tý objekt;
· x jk - číselná hodnota k-tej premennej pre j-tý objekt;
· v - počet premenných, ktoré popisujú objekty.
Teda pre prípad v=2, keď máme len dve kvantitatívne znamienka, bude vzdialenosť d ij rovná dĺžke prepony pravouhlého trojuholníka, ktorý spája dva body v pravouhlom súradnicovom systéme. Tieto dva body budú zodpovedať i-tým a j-tým pozorovaniam vzorky. Často sa namiesto obvyklej euklidovskej vzdialenosti používa jej druhá mocnina d 2 ij. Okrem toho sa v niektorých prípadoch používa „vážená“ euklidovská vzdialenosť, pri výpočte ktorej sa používajú váhové koeficienty pre jednotlivé pojmy. Na ilustráciu konceptu euklidovskej metriky použijeme jednoduchý tréningový príklad. Dátová matica uvedená v tabuľke nižšie pozostáva z 5 pozorovaní a dvoch premenných.
stôl 1
Dátová matica piatich pozorovaných vzoriek a dvoch premenných.
Pomocou euklidovskej metriky vypočítame maticu medziobjektových vzdialeností, pozostávajúcu z hodnôt d ij - vzdialenosť medzi i-tým a j-tým objektom. V našom prípade i a j sú číslo objektu, pozorovania. Keďže veľkosť vzorky je 5, i a j môžu nadobúdať hodnoty od 1 do 5. Je tiež zrejmé, že počet všetkých možných párových vzdialeností bude 5*5=25. V skutočnosti to budú pre prvý objekt tieto vzdialenosti: 1-1; 1-2; 1-3; 1-4; 1-5. Pre objekt 2 bude tiež 5 možných vzdialeností: 2-1; 2-2; 2-3; 2-4; 2-5 atď. Počet rôznych vzdialeností však bude menší ako 25, keďže je potrebné vziať do úvahy vlastnosť nerozoznateľnosti rovnakých predmetov - d ij = 0 pre i = j. To znamená, že vzdialenosť medzi objektom #1 a rovnakým objektom #1 bude nulová. Rovnaké nulové vzdialenosti budú pre všetky ostatné prípady i = j. Okrem toho z vlastnosti symetrie vyplýva, že d ij = d ji pre ľubovoľné i a j. Tie. vzdialenosť medzi objektmi #1 a #2 sa rovná vzdialenosti medzi objektmi #2 a #1.
Výraz pre euklidovskú vzdialenosť je veľmi podobný takzvanej zovšeobecnenej Minkowského mocninnej vzdialenosti, v ktorej sa namiesto dvoch v mocninách používa iná hodnota. Vo všeobecnom prípade je táto hodnota označená symbolom "p".
Pre p = 2 dostaneme obvyklú euklidovskú vzdialenosť. Takže výraz pre zovšeobecnenú Minkowského metriku má tvar:
Voľbu konkrétnej hodnoty exponentu „p“ robí výskumník sám.
Špeciálnym prípadom Minkowského vzdialenosti je takzvaná Manhattanská vzdialenosť alebo „vzdialenosť medzi mestskými blokmi“, ktorá zodpovedá p=1:
Vzdialenosť Manhattanu je teda súčtom modulov rozdielov zodpovedajúcich vlastností objektov. Ak necháme p smerovať k nekonečnu, dostaneme metriku „dominancie“ alebo Sup-metriku:
čo možno tiež znázorniť ako d ij = max| x ik - x jk |.
Minkowského metrika je v skutočnosti veľká rodina metrík vrátane najpopulárnejších metrík. Existujú však metódy na výpočet vzdialenosti medzi objektmi, ktoré sa zásadne líšia od Minkowského metrík. Najdôležitejšia z nich je takzvaná Mahalanobisova vzdialenosť, ktorá má skôr špecifické vlastnosti. Výraz pre túto metriku:
Tu cez X i A X j sú uvedené stĺpcové vektory premenných hodnôt pre i-tý a j-tý objekt. Symbol T vo výraze (X i - X j ) T označuje takzvanú vektorovú transpozičnú operáciu. Symbol S je uvedená spoločná vnútroskupinová matica rozptylu a kovariancie. Symbol -1 vyššie S znamená, že musíte prevrátiť maticu S . Na rozdiel od Minkowského metriky a euklidovskej metriky, Mahalanobisova vzdialenosť cez maticu rozptylu a kovariancie S spojené s koreláciami premenných. Keď sú korelácie medzi premennými nulové, Mahalanobisova vzdialenosť je ekvivalentná druhej mocnine euklidovskej vzdialenosti.
V prípade použitia dichotomických (s iba dvoma hodnotami) kvalitatívnych znakov sa široko používa Hammingova vzdialenosť
rovná počtu nezhôd v hodnotách zodpovedajúcich vlastností pre uvažované i-té a j-té objekty.
2. 3 HUSTOTA A LOKALITA Zhlukov
Hlavným cieľom zhlukovej analýzy je nájsť vo vzorke skupiny navzájom podobných objektov. Predpokladajme, že niektorou z možných metód sme získali takéto skupiny – zhluky. Treba poznamenať dôležité vlastnosti klastrov. Jednou z týchto vlastností je hustota rozloženia bodov, pozorovaní v rámci zhluku. Táto vlastnosť nám umožňuje definovať zhluk ako zhluk bodov vo viacrozmernom priestore, ktorý je relatívne hustý v porovnaní s inými oblasťami tohto priestoru, ktoré buď neobsahujú body vôbec, alebo obsahujú malý počet pozorovaní. Inými slovami, aký kompaktný je tento zhluk, alebo naopak, aký je riedky. Napriek dostatočnej evidencii tejto vlastnosti neexistuje jednoznačný spôsob výpočtu takéhoto ukazovateľa (hustoty). Najúspešnejším ukazovateľom charakterizujúcim kompaktnosť, hustotu „nabaľovania“ viacrozmerných pozorovaní v danom zhluku, je rozptyl vzdialenosti od stredu zhluku k jednotlivým bodom zhluku. Čím menší je rozptyl tejto vzdialenosti, čím bližšie sú pozorovania k stredu zhluku, tým väčšia je hustota zhluku. A naopak, čím väčší je rozptyl vzdialenosti, tým je tento zhluk riedky, a preto sú body umiestnené tak blízko stredu zhluku, ako aj dosť vzdialené od stredu zhluku.
Ďalšou vlastnosťou klastrov je ich veľkosť. Hlavným ukazovateľom veľkosti klastra je jeho „polomer“. Táto vlastnosť najviac odráža skutočnú veľkosť zhluku, ak je uvažovaný zhluk okrúhly a je hypersférou vo viacrozmernom priestore. Ak však majú zhluky predĺžené tvary, potom pojem polomer alebo priemer už neodráža skutočnú veľkosť zhluku.
Ďalšou dôležitou vlastnosťou klastra je ich lokalizácia, oddeliteľnosť. Charakterizuje mieru prekrývania a vzájomnej odľahlosti zhlukov od seba vo viacrozmernom priestore. Zvážte napríklad rozloženie troch klastrov v priestore nových integrovaných prvkov na obrázku nižšie. Osi 1 a 2 boli získané špeciálnou metódou z 12 znakov reflexných vlastností rôznych foriem erytrocytov, študovaných pomocou elektrónovej mikroskopie.
Obrázok 1
Vidíme, že klaster 1 má minimálnu veľkosť, zatiaľ čo klastre 2 a 3 majú približne rovnakú veľkosť. Zároveň môžeme povedať, že minimálna hustota, a teda maximálny rozptyl vzdialenosti je charakteristická pre zhluk 3. Okrem toho je zhluk 1 oddelený dostatočne veľkými časťami prázdneho priestoru od zhluku 2 aj klastra 3. 2 a 3 sa čiastočne prekrývajú. Zaujímavosťou je, že zhluk 1 má oveľa väčší rozdiel od 2. a 3. zhluku pozdĺž osi 1 ako pozdĺž osi 2. Naopak, zhluky 2 a 3 sa od seba líšia približne rovnako ako pozdĺž osi 1, tak aj pozdĺž osi 2. Je zrejmé, že pre takúto vizuálnu analýzu je potrebné mať všetky pozorovania vzorky premietnuté na špeciálne osi, v ktorých budú viditeľné projekcie prvkov zhlukov ako samostatné zhluky.
2. 4 VZDIALENOSŤ MEDZI Zhlukmi
V širšom zmysle možno objekty chápať nielen ako pôvodné predmety skúmania, prezentované v matici „objektovo-vlastnosti“ ako samostatnú líniu, alebo ako jednotlivé body vo viacrozmernom priestore znakov, ale aj ako samostatné skupiny takýchto bodov. , zjednotené jedným alebo druhým algoritmom do klastra. V tomto prípade vyvstáva otázka, ako pochopiť vzdialenosť medzi takýmito akumuláciami bodov (zhlukov) a ako ju vypočítať. V tomto prípade je rozmanitosť možností ešte väčšia ako v prípade výpočtu vzdialenosti medzi dvoma pozorovaniami vo viacrozmernom priestore. Tento postup je komplikovaný tým, že na rozdiel od bodov zhluky zaberajú určité množstvo viacrozmerného priestoru a skladajú sa z mnohých bodov. V zhlukovej analýze sa široko používajú medzizhlukové vzdialenosti, vypočítané na princípe najbližšieho suseda (najbližší sused), ťažiska, najvzdialenejšieho suseda (najvzdialenejší sused), mediánov. Najrozšírenejšie sú štyri metódy: jednoduchá väzba, plná väzba, priemerná väzba a Wardova metóda. Pri metóde jedného prepojenia bude objekt pripojený k už existujúcemu klastra, ak má aspoň jeden z prvkov klastra rovnakú úroveň podobnosti ako spájaný objekt. Pri metóde úplných väzieb je objekt pripojený ku klastru iba vtedy, ak podobnosť medzi kandidátom na zaradenie a ktorýmkoľvek prvkom klastra nie je menšia ako určitá prahová hodnota. Pre priemerný spôsob pripojenia existuje niekoľko úprav, ktoré predstavujú určitý kompromis medzi jednoduchým a úplným pripojením. Vypočítajú priemernú hodnotu podobnosti kandidáta na zaradenie so všetkými objektmi existujúceho zhluku. Pripojenie sa vykoná, keď zistená priemerná hodnota podobnosti dosiahne alebo prekročí určitú hranicu. Najčastejšie sa používa aritmetický priemer podobnosti medzi objektmi klastra a kandidátom na zaradenie do klastra.
Mnohé z klastrovacích metód sa navzájom líšia tým, že ich algoritmy v každom kroku počítajú rôzne funkcionality kvality rozdelenia. Populárna Wardova metóda je konštruovaná tak, aby optimalizovala minimálny rozptyl vnútroklastrových vzdialeností. V prvom kroku sa každý zhluk skladá z jedného objektu, vďaka čomu sa vnútroklastrový rozptyl vzdialeností rovná 0. Touto metódou sa kombinujú tie objekty, ktoré poskytujú minimálny prírastok rozptylu, v dôsledku čoho má táto metóda tendenciu vytvárať hypersférické zhluky.
Viacnásobné pokusy o klasifikáciu metód klastrovej analýzy vedú k desiatkam alebo dokonca stovkám rôznych tried. Takúto pestrosť generuje veľké množstvo možných spôsobov výpočtu vzdialenosti medzi jednotlivými pozorovaniami, nemenej počet metód na výpočet vzdialenosti medzi jednotlivými zhlukmi v procese zhlukovania a rôzne odhady optimality výslednej štruktúry zhlukov.
Najpoužívanejšie v populárnych štatistických balíkoch sú dve skupiny algoritmov klastrovej analýzy: hierarchické aglomeratívne metódy a metódy iteratívneho zoskupovania.
3. METÓDY ZOSKUPOVANIA
3. 1 ZNAKY HIERARCHICKÝCH AGLOMERATÍVNYCH METÓD
V aglomeratívnych hierarchických algoritmoch, ktoré sa častejšie používajú v reálnom biomedicínskom výskume, sa spočiatku všetky objekty (pozorovania) považujú za samostatné, nezávislé zhluky pozostávajúce iba z jedného prvku. Bez použitia výkonnej výpočtovej techniky je implementácia klastrovej analýzy dát veľmi problematická.
Výber metriky vykonáva výskumník. Po výpočte matice vzdialenosti sa začne proces aglomerácií (z latinského agglomero - prikladám, hromadím), prechádzajúci postupne krok za krokom. V prvom kroku tohto procesu sa dve počiatočné pozorovania (monoklastre) s najmenšou vzdialenosťou medzi nimi spoja do jedného zhluku, ktorý už pozostáva z dvoch objektov (pozorovaní). Namiesto bývalých N monoklastrov (zhlukov pozostávajúcich z jedného objektu) teda po prvom kroku vznikne N-1 zhlukov, z ktorých jeden zhluk bude obsahovať dva objekty (pozorovania) a N-2 zhlukov bude stále pozostávať z len jeden objekt. V druhom kroku sú možné rôzne spôsoby kombinovania N-2 klastrov. Je to preto, že jeden z týchto zhlukov už obsahuje dva objekty. Z tohto dôvodu vyvstávajú dve hlavné otázky:
· ako vypočítať súradnice takéhoto zhluku dvoch (a ďalej viac ako dvoch) objektov;
· ako vypočítať vzdialenosť k takýmto „poly-objektovým“ zhlukom od „monoklastrov“ a medzi „poly-objektovými“ zhlukami.
V konečnom dôsledku tieto otázky určujú konečnú štruktúru výsledných zhlukov (štruktúrou zhlukov sa rozumie zloženie jednotlivých zhlukov a ich vzájomná poloha vo viacrozmernom priestore). Rôzne kombinácie metrík a metód na výpočet súradníc a vzájomných vzdialeností zhlukov vedú k rôznorodosti metód zhlukovej analýzy. V druhom kroku, v závislosti od zvolených metód na výpočet súradníc zhluku pozostávajúceho z niekoľkých objektov a spôsobu výpočtu medziklastrových vzdialeností, je možné buď znovu spojiť dve samostatné pozorovania do nového zhluku, alebo spojiť jedno nové pozorovanie do zhluku pozostávajúceho z dvoch objektov. Pre pohodlie väčšina programov aglomeratívno-hierarchických metód na konci práce môže poskytnúť dva hlavné grafy na prezeranie. Prvý graf sa nazýva dendrogram (z gréckeho dendron - strom), odrážajúci proces aglomerácie, spájanie jednotlivých pozorovaní do jedného výsledného zhluku. Uveďme príklad dendrogramu 5 pozorovaní v dvoch premenných.
Rozvrh1
Vertikálna os takéhoto grafu je osou medziklastrovej vzdialenosti a počty objektov – prípady použité v analýze – sú vyznačené pozdĺž horizontálnej osi. Z tohto dendrogramu je vidieť, že objekty č. 1 a č. 2 sa najskôr spoja do jedného zhluku, pretože vzdialenosť medzi nimi je najmenšia a rovná sa 1. Toto zlúčenie je na grafe znázornené vodorovnou čiarou spájajúcou vertikálne segmenty. vychádzajúci z bodov označených ako C_1 a C_2. Všimnime si, že samotná vodorovná čiara prechádza presne na úrovni medziklastrovej vzdialenosti rovnajúcej sa 1. Ďalej sa v druhom kroku k tomuto zhluku, ktorý už obsahuje dva objekty, pripája objekt č. 3, označený ako C_3. Ďalším krokom je zlúčenie objektov #4 a #5, pričom vzdialenosť medzi nimi sa rovná 1,41. A v poslednom kroku sa zhluk objektov 1, 2 a 3 spojí so zhlukom objektov 4 a 5. Graf ukazuje, že vzdialenosť medzi týmito dvoma predposlednými zhlukmi (posledný zhluk zahŕňa všetkých 5 objektov) je väčšia ako 5 , ale menej ako 6, pretože horná vodorovná čiara spájajúca dva predposledné zhluky prechádza na úrovni približne rovnej 7 a úroveň spojenia objektov 4 a 5 je 1,41.
Nižšie uvedený dendrogram bol získaný analýzou skutočného súboru údajov pozostávajúceho zo 70 spracovaných chemických vzoriek, z ktorých každá bola charakterizovaná 12 znakmi.
Graf 2
Z grafu je vidieť, že v poslednom kroku, keď sa posledné dva zhluky spoja, je vzdialenosť medzi nimi asi 200 jednotiek. Je vidieť, že prvý zhluk obsahuje oveľa menej objektov ako druhý zhluk Nižšie je zväčšená časť dendrogramu, na ktorej sú jasne viditeľné pozorovacie čísla, označené ako C_65, C_58 atď. (zľava doprava): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94 atď.
Graf 3 Zväčšená časť grafu č. 2 vyššie
Je možné vidieť, že objekt 44 je monoklaster, ktorý sa v predposlednom kroku spája s pravým zhlukom a potom, v poslednom kroku, sa všetky pozorovania spoja do jedného zhluku.
Ďalší graf, ktorý je vytvorený v takýchto postupoch, je graf medziklastrových vzdialeností v každom kroku spojenia. Nižšie je podobný graf pre vyššie uvedený dendrogram.
graf 4
V mnohých programoch je možné zobraziť v tabuľkovej forme výsledky kombinovania objektov v každom kroku zhlukovania. Aby sa predišlo nejasnostiam, vo väčšine týchto tabuliek sa používa odlišná terminológia na označenie počiatočných pozorovaní - monoklastrov a skutočných zhlukov pozostávajúcich z dvoch alebo viacerých pozorovaní. V štatistických balíkoch v anglickom jazyku sú počiatočné pozorovania (riadky matice údajov) označené ako „case“ – case. Aby sme demonštrovali závislosť štruktúry klastra na výbere metriky a voľbe algoritmu zjednotenia klastrov, nižšie uvádzame dendrogram zodpovedajúci algoritmu úplného pripojenia. A tu vidíme, že objekt #44 sa zlúči so zvyškom výberu v úplne poslednom kroku.
Graf 5
Teraz ho porovnajme s iným grafom získaným použitím metódy jedného prepojenia na rovnakých údajoch. Na rozdiel od metódy úplného spojenia je možné vidieť, že táto metóda generuje dlhé reťazce sekvenčne pripojených objektov k sebe. Vo všetkých troch prípadoch však môžeme povedať, že vyčnievajú dve hlavné skupiny.
Graf 6
Venujme pozornosť aj tomu, že vo všetkých troch prípadoch sa objekt č. 44 spája ako monoklaster, aj keď v rôznych krokoch procesu zhlukovania. Výber takýchto monoklastrov je dobrým prostriedkom na zisťovanie anomálnych pozorovaní, nazývaných odľahlé hodnoty. Vymažme tento "podozrivý" objekt č. 44 a znova vykonajte zhlukovanie. Získame nasledujúci dendrogram:
Graf 7
Je vidieť, že „reťazový“ efekt je zachovaný, rovnako ako rozdelenie do dvoch lokálnych skupín pozorovaní.
3. 2 ZNAKY ITERATÍVNYCH METÓD KLUSTEROVANIA
Spomedzi iteračných metód je najpopulárnejšou metódou McKeanova metóda k-means. Na rozdiel od hierarchických metód musí vo väčšine implementácií tejto metódy používateľ sám špecifikovať požadovaný počet finálnych zhlukov, ktorý sa zvyčajne označuje ako „k“. Rovnako ako v hierarchických metódach klastrovania si používateľ môže vybrať jeden alebo iný typ metriky. Rôzne algoritmy metódy k-means sa líšia aj spôsobom výberu počiatočných stredov daných zhlukov. V niektorých verziách metódy môže (alebo musí) používateľ sám určiť takéto počiatočné body, a to buď ich výberom z reálnych pozorovaní, alebo zadaním súradníc týchto bodov pre každú z premenných. V iných implementáciách tejto metódy sa výber daného počtu k počiatočných bodov uskutočňuje náhodne a tieto počiatočné body (zrná klastra) možno následne spresniť v niekoľkých fázach. Existujú 4 hlavné fázy takýchto metód:
· vybrať alebo priradiť k pozorovaniam, ktoré budú primárnymi centrami zhlukov;
· ak je to potrebné, prechodné zhluky sa vytvoria priradením každého pozorovania k najbližším špecifikovaným stredom zhlukov;
· po priradení všetkých pozorovaní k jednotlivým zhlukom sú primárne centrá zhlukov nahradené priemermi zhlukov;
· predchádzajúca iterácia sa opakuje, kým sa zmeny v súradniciach stredov klastrov nestanú minimálnymi.
V niektorých verziách tejto metódy môže používateľ nastaviť číselnú hodnotu kritéria, ktorá sa interpretuje ako minimálna vzdialenosť pre výber nových stredov klastra. Pozorovanie sa nebude považovať za kandidáta na nové centrum klastra, ak jeho vzdialenosť od nahradeného centra klastra presiahne špecifikovaný počet. Tento parameter sa v niektorých programoch nazýva "polomer". Okrem tohto parametra je možné nastaviť aj maximálny počet iterácií alebo dosiahnuť určitý, zvyčajne dosť malý počet, s ktorým sa porovnáva zmena vzdialenosti pre všetky centrá klastra. Toto nastavenie sa bežne označuje ako „konvergencia“, pretože odráža konvergenciu procesu iteratívneho klastrovania. Nižšie uvádzame niektoré z výsledkov, ktoré boli získané pomocou metódy McKean k-means k predchádzajúcim údajom. Počet požadovaných zhlukov bol spočiatku nastavený na 3 a potom na 2. Ich prvá časť obsahuje výsledky jednosmernej analýzy rozptylu, v ktorej počet zhlukov funguje ako zoskupovací faktor. V prvom stĺpci je zoznam 12 premenných, nasledujú súčty štvorcov (SS) a stupňov voľnosti (df), potom Fisherov F-test a v poslednom stĺpci dosiahnutá hladina významnosti „p“.
Tabuľka 2 McKean k-priemerné údaje použiteľné pre 70 testovacích vzoriek.
|
Premenné |
|||||||
Ako je možné vidieť z tejto tabuľky, nulová hypotéza o rovnosti priemerov v troch skupinách sa zamieta. Nižšie je uvedený graf priemerov všetkých premenných pre jednotlivé zhluky. Rovnaké zhlukové priemery premenných sú uvedené nižšie vo forme tabuľky.
Tabuľka 3. Podrobný prehľad údajov na príklade troch klastrov.
|
Variabilné |
Skupina #1 |
Skupina #2 |
Skupina č. 3 |
|
Graf 8
Analýza priemerných hodnôt premenných pre každý klaster nám umožňuje dospieť k záveru, že podľa funkcie X1 majú klastre 1 a 3 blízke hodnoty, zatiaľ čo klaster 2 má priemernú hodnotu oveľa nižšiu ako v ostatných dvoch klastroch. Naopak, podľa funkcie X2 má prvý klaster najnižšiu hodnotu, zatiaľ čo 2. a 3. klaster majú vyššie a blízke priemerné hodnoty. Pre znaky X3-X12 sú priemerné hodnoty v klastri 1 výrazne vyššie ako v klastroch 2 a 3. Nasledujúca tabuľka analýzy ANOVA výsledkov zhlukovania do dvoch zhlukov tiež ukazuje potrebu zamietnuť nulovú hypotézu o rovnosti skupinových priemerov pre takmer všetkých 12 znakov, s výnimkou premennej X4, pre ktorú bola dosiahnutá hladina významnosti vyššia ako 5 %.
Tabuľka 4. Tabuľka disperznej analýzy výsledkov zhlukovania do dvoch zhlukov.
|
Premenné |
|||||||
Nižšie je uvedený graf a tabuľka skupinových priemerov pre prípad zhlukovania do dvoch zhlukov.
Tabuľka 5. Tabuľka pre prípad zhlukovania do dvoch zhlukov.
|
Premenné |
Skupina #1 |
Skupina #2 |
|
Graf 9.
V prípade, že výskumník nie je schopný vopred určiť najpravdepodobnejší počet zhlukov, je nútený zopakovať výpočty s nastavením iného počtu, podobne ako vyššie. A potom, porovnávajúc získané výsledky medzi sebou, zastavte sa pri jednej z najprijateľnejších možností zoskupovania.
4 . ZHRNUTIE VLASTNOSTÍ
Okrem zoskupovania jednotlivých pozorovaní existujú aj algoritmy na zoskupovanie funkcií. Jednou z prvých takýchto metód je metóda korelačných plejád Terentiev P.V. Primitívne obrázky takýchto plejád možno často nájsť v biomedicínskych publikáciách vo forme kruhu posiateho šípkami spájajúcimi znaky, pre ktoré autori našli koreláciu. Množstvo programov na zoskupovanie objektov a funkcií má samostatné procedúry. Napríklad v balíku SAS pre klastrovanie prvkov sa používa procedúra VARCLUS (z VARiable - premenná a CLUSter - klaster), zatiaľ čo zhluková analýza pozorovaní sa vykonáva inými procedúrami - FASTCLUS a CLUSTER. Konštrukcia dendrogramu sa v oboch prípadoch realizuje pomocou TREE (stromového) postupu.
V iných štatistických balíkoch sa výber prvkov na zhlukovanie – objektov alebo prvkov – vykonáva v rovnakom module. Ako metrika pre zhlukovanie prvkov sa často používajú výrazy, ktoré zahŕňajú hodnotu určitých koeficientov odrážajúcich silu vzťahu pre pár vlastností. V tomto prípade je veľmi vhodné, aby znaky so silou spojenia rovnajúcou sa jednej (funkčná závislosť) mali vzdialenosť medzi znakmi rovnú nule. Skutočne, s funkčným spojením môže hodnota jedného prvku presne vypočítať hodnotu iného prvku. So znižovaním sily vzťahu medzi znakmi sa primerane zväčšuje aj vzdialenosť. Nižšie je uvedený graf zobrazujúci dendrogram kombinácie 12 prvkov, ktoré boli použité vyššie pri zoskupovaní 70 analytických vzoriek.
Graf 10. Dendrogramzhlukovanie 12 funkcií.
Ako vidno z tohto dendrogramu, máme čo do činenia s dvoma lokálnymi zoskupeniami znakov: X1-X10 a X11-X12 Skupina znakov X1-X10 sa vyznačuje pomerne malou hodnotou medziklastrových vzdialeností, nepresahujúcou približne 100 jednotiek. Tu tiež vidíme niekoľko vnútorných párových podskupín: X1 a X2, X3 a X4, X6 a X7. Vzdialenosť medzi znakmi týchto párov, ktorá je veľmi blízka nule, naznačuje ich silný párový vzťah. Zatiaľ čo pre pár X11 a X12 je hodnota medziklastrovej vzdialenosti oveľa väčšia a je asi 300 jednotiek. Napokon, veľmi veľká vzdialenosť medzi ľavým (X1-X10) a pravým (X11-X12) zhlukom, ktorá sa rovná približne 1150 jednotkám, naznačuje, že vzťah medzi týmito dvoma skupinami prvkov je celkom minimálny.
5. STABILITA A KVALITA KLUSTEROV
Je zrejmé, že by bolo absurdné klásť si otázku, aká absolútna je tá či oná klasifikácia získaná pomocou metód zhlukovej analýzy. Pri zmene metódy zhlukovania sa stabilita prejaví tak, že na dendrogramoch sú celkom jasne viditeľné dva zhluky.
Ako jeden z možných spôsobov kontroly stability výsledkov zhlukovej analýzy možno použiť metódu porovnávania výsledkov získaných pre rôzne zhlukovacie algoritmy. Ďalšími spôsobmi sú takzvaná bootstrap metóda navrhnutá B. Efronom v roku 1977, metódy „jackknife“ a „sliding control“. Najjednoduchším prostriedkom na kontrolu stability klastrového riešenia môže byť náhodné rozdelenie počiatočnej vzorky na dve približne rovnaké časti, zoskupenie oboch častí a následné porovnanie výsledkov. Časovo náročnejší spôsob zahŕňa postupné vylúčenie prvého objektu na začiatku a zoskupenie zostávajúcich (N - 1) objektov. Ďalej, postupné vykonávanie tohto postupu s výnimkou druhého, tretieho atď. objektov, je analyzovaná štruktúra všetkých N získaných zhlukov. Ďalší algoritmus na kontrolu stability zahŕňa viacnásobnú reprodukciu, duplikáciu pôvodnej vzorky N objektov, potom spojenie všetkých duplikovaných vzoriek do jednej veľkej vzorky (pseudovšeobecná populácia) a náhodnú extrakciu novej vzorky N objektov z nej. Potom sa uskutoční zhlukovanie tejto vzorky, potom sa extrahuje nová náhodná vzorka a znova sa uskutoční zhlukovanie atď. Je to tiež dosť náročné na prácu.
Nie sú menšie problémy pri posudzovaní kvality klastrovania. Je známych pomerne veľa algoritmov na optimalizáciu klastrových riešení. Prvé práce, ktoré obsahovali formulácie kritéria pre minimalizáciu vnútroklastrového rozptylu a algoritmus (typu k-means) na nájdenie optimálneho riešenia, sa objavili v 50. rokoch. V roku 1963 Článok J. Warda tiež predstavil podobný optimalizačný hierarchický algoritmus. Neexistuje žiadne univerzálne kritérium pre optimalizáciu klastrového riešenia. To všetko sťažuje výskumníkovi výber optimálneho riešenia. V takejto situácii je najlepším spôsobom, ako potvrdiť, že nájdené klastrové riešenie je v tejto fáze štúdie optimálne, iba konzistentnosť tohto riešenia so závermi získanými pomocou iných metód viacrozmernej štatistiky.
V prospech záveru o optimálnosti zhlukovania hovoria aj pozitívne výsledky kontroly prediktívnych momentov získaného riešenia už na iných objektoch štúdia. Pri použití hierarchických metód zhlukovej analýzy môžeme odporučiť porovnanie niekoľkých grafov postupných zmien medzizhlukovej vzdialenosti medzi sebou. V tomto prípade by sa mala uprednostniť možnosť, pri ktorej sa pozoruje plochá čiara takéhoto prírastku od prvého kroku po niekoľko predposledných krokov s prudkým vertikálnym vzostupom v tomto grafe pri posledných 1-2 krokoch zoskupovania.
ZÁVERY
Vo svojej práci som sa snažil poukázať nielen na zložitosť tohto typu analýzy, ale aj na optimálne možnosti spracovania dát, pretože často na presnosť výsledkov musíte použiť desiatky až stovky vzoriek. Tento typ analýzy pomáha klasifikovať a spracovávať výsledky. Za nepodstatnú považujem aj prijateľnosť výpočtovej techniky pri tejto analýze, ktorá umožňuje skrátiť proces spracovania výsledkov časovo menej náročným a umožňuje tak venovať väčšiu pozornosť správnosti odberu vzoriek na analýzu.
Pri použití zhlukovej analýzy existujú také jemnosti a detaily, ktoré sa objavujú v jednotlivých konkrétnych prípadoch a nie sú okamžite viditeľné. Napríklad úloha škály funkcií môže byť minimálna a v niektorých prípadoch môže byť dominantná. V takýchto prípadoch je potrebné použiť premenné transformácie. Toto je obzvlášť účinné pri použití metód, ktoré produkujú nelineárne transformácie prvkov, ktoré vo všeobecnosti zvyšujú celkovú úroveň korelácií medzi prvkami.
Ešte väčšia špecifickosť je v použití zhlukovej analýzy vo vzťahu k objektom, ktoré sú opísané iba kvalitatívnymi znakmi. V tomto prípade sú metódy predbežnej digitalizácie kvalitatívnych prvkov a zhluková analýza s novými vlastnosťami celkom úspešné. Vo svojej práci som ukázal, že zhluková analýza poskytuje množstvo nových a originálnych informácií ako v prípade jej aplikácie v dostatočne preštudovaných systémoch, tak aj pri štúdiu systémov s neznámou štruktúrou.
Treba tiež poznamenať, že klastrová analýza sa stala nevyhnutnou v evolučnom výskume, čo umožňuje konštrukciu fylogenetických stromov ukazujúcich evolučné cesty. Tieto metódy sú tiež široko používané vo vedeckých výskumných programoch vo fyzikálnej a analytickej chémii.
BIBLIOGRAFIA
1) Aivazyan S. A., Enyukov I. S., Meshalkin L. D. O štruktúre a obsahu softvérového balíka pre aplikovanú štatistickú analýzu//Algoritmus a softvér pre aplikovanú štatistickú analýzu. -- M., 1980.
2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Klasifikácia viacrozmerných pozorovaní. -- M.: Štatistika, 1974.
3) Becker V. A., Lukatskaya M. L. O analýze štruktúry matice väzbových koeficientov//Problémy ekonomického a štatistického modelovania a prognózovania v priemysle.-- Novosibirsk, 1970.
4) Braverman E. M., Muchnik I. B. Štrukturálne metódy spracovania údajov.--M.: Nauka, 1983.
5) Voronin Yu. A. Klasifikačná teória a jej aplikácie.--Novosibirsk: Nauka, 1987.
6) Good I. J. Botryology of botryology//Klasifikácia a klaster.--M.: Mir, 1980.
7) Dubrovsky S. A. Aplikovaná viacrozmerná štatistická analýza.--M.: Finance and statistics, 1982.
8) Duran N., Odell P. Cluster analysis.--M.: Statistics, 1977.
9) Eliseeva I.I., Rukavishnikov V.S. Zoskupenie, korelácia, rozpoznávanie vzorov.--M.: Štatistika, 1977.
10) Zagoruiko N. G. Metódy rozpoznávania a ich aplikácia.--M .: Sovietsky rozhlas, 1972.
11) Zade L. A. Fuzzy množiny a ich aplikácia pri rozpoznávaní vzorov a zhlukovej analýze//Klasifikácia a zhlukovanie.--M.: Mir, 1980.
12) Kildishev G.S., Abolentsev Yu.I. Multidimenzionálne zoskupenia.--M.: Štatistika, 1978.
13) Raiskaya II, Gostilin NI, Frenkel' AA O jednom spôsobe kontroly platnosti delenia v zhlukovej analýze.//Aplikácia viacrozmernej štatistickej analýzy v ekonómii a hodnotení kvality produktov.--Ch. P. Tartu, 1977.
14) Shurygin A. M. Distribúcia medzibodových vzdialeností a rozdielov // Softvérová a algoritmická podpora pre aplikovanú viacrozmernú štatistickú analýzu. -- M., 1983.
15) Eeremaa R. Všeobecná teória navrhovania klastrových systémov a algoritmov na hľadanie ich numerických reprezentácií: Zborník výpočtového centra TSU.--Tartu, 1978.
16) Yastremsky B.S. Selected Works.--M.: Statistics, 1964.
Podobné dokumenty
Ciele segmentácie trhu v marketingových aktivitách. Podstata klastrovej analýzy, hlavné fázy jej implementácie. Vyberte spôsob merania vzdialenosti alebo miery podobnosti. Hierarchické, nehierarchické metódy zhlukovania. Posudzovanie spoľahlivosti a spoľahlivosti.
správa, pridaná 02.11.2009
Hlavné ukazovatele finančnej situácie podniku. Kríza v podniku, jej príčiny, typy a dôsledky. Moderné metódy a nástroje zhlukovej analýzy, vlastnosti ich využitia pre finančné a ekonomické hodnotenie podniku.
práca, pridané 10.09.2013
Vykonajte zhlukovú analýzu podnikov pomocou programu Statgraphics Plus. Konštrukcia lineárnej regresnej rovnice. Výpočet koeficientov elasticity pomocou regresných modelov. Posúdenie štatistickej významnosti rovnice a koeficientu determinácie.
úloha, pridané 16.03.2014
Konštrukcia typologických regresií pre jednotlivé skupiny pozorovaní. Priestorové údaje a časové informácie. Rozsah použitia klastrovej analýzy. Pojem homogenity objektov, vlastnosti matice vzdialeností. Vykonávanie typologickej regresie.
prezentácia, pridané 26.10.2013
Tvorba kombinovaných modelov a metód ako moderný spôsob prognózovania. Model založený na ARIMA na popis stacionárnych a nestacionárnych časových radov pri riešení klastrovacích problémov. Autoregresívne AR modely a aplikácia korelogramov.
prezentácia, pridané 01.05.2015
Charakteristika rôznych typov metrík. Metóda najbližšieho suseda a jej zovšeobecnenia. Algoritmus najbližšieho suseda. Metóda Parzenového okna. Zovšeobecnený metrický klasifikátor. Problém výberu metriky. Manhattan a euklidovská vzdialenosť. kosínusová miera.
semestrálna práca, pridaná 03.08.2015
Charakteristika stavebného priemyslu na území Krasnodar. Prognóza vývoja bytovej výstavby. Moderné metódy a nástroje zhlukovej analýzy. Viacrozmerné štatistické metódy na diagnostikovanie ekonomického stavu podniku.
práca, pridané 20.07.2015
Charakteristika hypotekárnych úverov na príklade regiónu Brjansk. Prehľad matematických metód rozhodovania: expertné hodnotenia, sekvenčné a párové porovnávanie, hierarchická analýza. Vývoj vyhľadávacieho programu optimálneho hypotekárneho úveru.
ročníková práca, pridaná 29.11.2012
Oblasti aplikácie systémovej analýzy, jej miesto, úloha, ciele a funkcie v modernej vede. Pojem a obsah metód systémovej analýzy, jej neformálne metódy. Vlastnosti heuristických a expertných výskumných metód a vlastnosti ich aplikácie.
ročníková práca, pridaná 20.05.2013
Vývoj a výskum ekonometrických metód s prihliadnutím na špecifiká ekonomických údajov a v súlade s potrebami ekonomickej vedy a praxe. Aplikácia ekonometrických metód a modelov pre štatistickú analýzu ekonomických údajov.
Termín „zhluková analýza“ prvýkrát použil americký psychológ Robert Trion v práci s rovnakým názvom v roku 1930. Napriek tomu pojmy „zhluk“ a „zhluková analýza“ vnímajú rodení hovoriaci ako nové, čo si všimol Alexander Khrolenko, ktorý vykonal korpusovú analýzu používania lexémy „zhluk“: „väčšina autorov používajúcich tento výraz platí pozornosť jeho novosti“ (Khrolenko , 2016, s. 106)
Klastrová analýza zahŕňa mnoho rôznych klasifikačných algoritmov, ktorých účelom je organizovať informácie do zhlukov. Je dôležité si uvedomiť, že klastrová analýza nie je sama o sebe určitým algoritmom, ale existuje úloha, ktorú treba vyriešiť. Mark Ereshefsky vo svojej práci „The Scarcity of the Linear Hierarchy“ poznamenáva, že zhluková analýza je jedným z troch typov klasifikácie objektov na svete, spolu s esencializmom a historickou klasifikáciou.
V lingvistike zhlukový princíp opisu zahŕňa okrem analýzy jednotiek zahrnutých v tomto zhluku aj analýzu vzťahov v nich. Môžu to byť spojenia rôznych úrovní: od logických (napríklad paradigmatických a syntagmatických) až po slovotvorné a fonetické spojenia.
F. Brown identifikuje nasledujúce kroky zhlukovej analýzy (Brown):
- 1. Výber miery a vytvorenie potrebných meraní, kritérií alebo entít, ktoré sa majú klasifikovať
- 2. Nastavenie miery podobnosti
- 3. Formulácia pravidiel na určenie poradia tvorby zhlukov
- 4. Aplikovanie pravidiel na vytváranie klastrov
Treba poznamenať, že tretí bod vyvoláva otázky, pretože charakteristickým znakom zhlukovania ako klasifikačnej metódy je absencia špecifikovaných tried. Klastrovanie dokumentov je úlohou získavania informácií. Na rozdiel od textovej kategorizácie nezahŕňa preddefinované kategórie ani tréningové sady. Zhluky a vzťahy medzi nimi sa „automaticky extrahujú z dokumentov a dokumenty sa k týmto zhlukom postupne pripájajú“ (Golub, s. 52-53) Mark Ereshefsky predstavuje zhlukovú analýzu ako klasifikačnú metódu. Verí, že "všetky formy zhlukovej analýzy sú založené na dvoch predpokladoch: členovia taxonomickej skupiny musia zdieľať zhluk znakov a tieto znaky sa nemôžu objaviť u všetkých alebo len u jedného člena tejto skupiny." (Ereshefsky, s. 15)
Vo svojej práci „Zhlukový prístup v lingvistickej analýze“ (Nurgalieva, 2013) N.Kh. Nurgalieva identifikuje štyri hlavné úlohy klastrovej analýzy:
- 1. Vypracovanie typológie alebo klasifikácie
- 2. Skúmanie užitočných koncepčných schém na zoskupovanie objektov
- 3. Prezentácia hypotéz na základe skúmaných údajov
- 4. Testovanie hypotéz alebo štúdií s cieľom určiť, či typy (skupiny) identifikované tak či onak sú skutočne prítomné v dostupných údajoch
Všetky metódy zhlukovej analýzy možno rozdeliť na „tvrdú“, prehľadnú zhlukovú analýzu, keď každý objekt buď patrí do zhluku alebo nie, a „mäkkú“, fuzzy zhlukovú analýzu, keď každý objekt patrí do nejakej skupiny s určitým stupňom pravdepodobnosti. .
Metódy klastrovej analýzy sa tiež delia na hierarchické a nehierarchické. Hierarchické metódy znamenajú na rozdiel od nehierarchických metód prítomnosť vnorených skupín. Nurgaliyeva poznamenáva, že hierarchická metóda „sa zdá byť najvhodnejšia na riešenie lingvistických problémov“ (Nurgaliyeva, s. 1), pretože umožňuje vidieť a analyzovať štruktúru skúmaného javu.
KLUSTEROVÁ ANALÝZA V PROBLEMATIKE SOCIÁLNO-EKONOMICKÉHO PROGNÓZOVANIA
Úvod do klastrovej analýzy.
Pri analýze a predpovedaní sociálno-ekonomických javov sa výskumník často stretáva s mnohorozmernosťou ich opisu. Stáva sa to pri riešení problému segmentácie trhu, budovaní typológie krajín podľa dostatočne veľkého počtu ukazovateľov, predpovedaní trhovej situácie pre jednotlivé tovary, skúmaní a predpovedaní hospodárskej depresie a mnohých ďalších problémov.
Metódy viacrozmernej analýzy sú najúčinnejším kvantitatívnym nástrojom na štúdium sociálno-ekonomických procesov opísaných veľkým množstvom charakteristík. Patrí medzi ne zhluková analýza, taxonómia, rozpoznávanie vzorov a faktorová analýza.
Zhluková analýza najzreteľnejšie odráža vlastnosti viacrozmernej analýzy pri klasifikácii, faktorovej analýze - pri štúdiu komunikácie.
Niekedy sa prístup zhlukovej analýzy v literatúre označuje ako numerická taxonómia, numerická klasifikácia, samoučenie sa atď.
Zhluková analýza našla svoje prvé uplatnenie v sociológii. Názov klastrová analýza pochádza z anglického slova cluster – hromada, hromadenie. Prvýkrát v roku 1939 definoval predmet zhlukovej analýzy a jej popis vypracoval výskumník Trion. Hlavným účelom zhlukovej analýzy je rozdeliť súbor skúmaných objektov a prvkov do skupín alebo zhlukov, ktoré sú v príslušnom zmysle homogénne. To znamená, že sa rieši problém klasifikácie údajov a identifikácie zodpovedajúcej štruktúry v nich. Metódy zhlukovej analýzy je možné použiť v rôznych prípadoch, dokonca aj v prípadoch, keď hovoríme o jednoduchom zoskupení, v ktorom všetko závisí od vytvorenia skupín podľa kvantitatívnej podobnosti.
Veľkou výhodou klastrovej analýzy je, že vám umožňuje rozdeliť objekty nie podľa jedného parametra, ale podľa celého súboru funkcií. Okrem toho zhluková analýza, na rozdiel od väčšiny matematických a štatistických metód, neukladá žiadne obmedzenia na typ posudzovaných objektov a umožňuje nám zvážiť súbor počiatočných údajov takmer ľubovoľnej povahy. Má to veľký význam napríklad pre konjunktúrne prognózovanie, keď majú ukazovatele rôzne formy, ktoré sťažujú používanie tradičných ekonometrických prístupov.
Klastrová analýza umožňuje zvažovať pomerne veľké množstvo informácií a drasticky redukovať, komprimovať veľké množstvo sociálno-ekonomických informácií, urobiť ich kompaktnými a vizuálnymi.
Zhluková analýza má veľký význam vo vzťahu k súborom časových radov charakterizujúcich ekonomický vývoj (napríklad všeobecné ekonomické a komoditné podmienky). Tu je možné vyčleniť obdobia, kedy boli hodnoty zodpovedajúcich ukazovateľov pomerne blízko, ako aj určiť skupiny časových radov, ktorých dynamika je najpodobnejšia.
Klastrovú analýzu možno použiť cyklicky. V tomto prípade sa štúdia vykonáva, kým sa nedosiahnu požadované výsledky. Každý cyklus tu zároveň môže poskytnúť informácie, ktoré môžu výrazne zmeniť smer a prístupy ďalšej aplikácie zhlukovej analýzy. Tento proces môže byť reprezentovaný ako systém spätnej väzby.
V problémoch sociálno-ekonomického prognózovania je veľmi sľubné kombinovať zhlukovú analýzu s inými kvantitatívnymi metódami (napríklad s regresnou analýzou).
Ako každá iná metóda, klastrová analýza má určité nevýhody a obmedzenia: Najmä zloženie a počet zhlukov závisí od zvolených deliacich kritérií. Pri redukcii počiatočného dátového poľa do kompaktnejšej podoby môže dochádzať k určitým deformáciám a môže dôjsť aj k strate jednotlivých vlastností jednotlivých objektov v dôsledku ich nahradenia charakteristikami zovšeobecnených hodnôt parametrov klastra. Pri klasifikácii objektov sa veľmi často ignoruje možnosť absencie akýchkoľvek klastrových hodnôt v uvažovanej množine.
Pri klastrovej analýze sa uvažuje, že:
a) zvolené charakteristiky v zásade umožňujú požadované zhlukovanie;
b) jednotky merania (mierka) sú zvolené správne.
Veľkú úlohu zohráva výber mierky. Údaje sa zvyčajne normalizujú odčítaním priemeru a delením štandardnou odchýlkou tak, aby sa rozptyl rovnal jednej.
Problém klastrovej analýzy.
Úlohou zhlukovej analýzy je rozdeliť množinu objektov G na m (m je celé číslo) zhluky (podmnožiny) Q1, Q2, ..., Qm na základe údajov obsiahnutých v množine X tak, aby každý objekt Gj patrí do jednej a len jednej podmnožiny oddielov a že objekty patriace do rovnakého klastra sú podobné, zatiaľ čo objekty patriace do rôznych klastrov sú heterogénne.
Napríklad nech G zahŕňa n krajín, z ktorých každá je charakterizovaná HNP na obyvateľa (F1), počtom M áut na 1 000 ľudí (F2), spotrebou elektriny na obyvateľa (F3), spotrebou ocele na obyvateľa (F4), atď. Potom X1 (vektor merania) je súbor špecifikovaných charakteristík pre prvú krajinu, X2 pre druhú, X3 pre tretiu atď. Výzvou je rozdeliť krajiny podľa úrovne rozvoja.
Riešením problému klastrovej analýzy sú partície, ktoré spĺňajú určité kritérium optimálnosti. Týmto kritériom môže byť nejaká funkcionalita, ktorá vyjadruje úrovne vhodnosti rôznych oddielov a zoskupení, čo sa nazýva účelová funkcia. Napríklad vnútroskupinový súčet štvorcových odchýlok možno považovať za cieľovú funkciu:
kde xj - predstavuje merania j-tého objektu.
Na vyriešenie problému zhlukovej analýzy je potrebné definovať pojem podobnosti a heterogenity.
Je jasné, že i-ty a j-tý objekt by spadol do toho istého zhluku, keď by vzdialenosť (vzdialenosť) medzi bodmi Xi a Xj bola dostatočne malá, a spadli by do rôznych zhlukov, keď by táto vzdialenosť bola dostatočne veľká. Dostať sa do jedného alebo rôznych zhlukov objektov je teda určené konceptom vzdialenosti medzi Xi a Xj od Ep, kde Ep je p-rozmerný euklidovský priestor. Nezáporná funkcia d(Xi, Xj) sa nazýva funkcia vzdialenosti (metrická), ak:
a) d(Xi, Xj) ³ 0, pre všetky Xi a Xj z Ep
b) d(Xi, Xj) = 0 práve vtedy, ak Xi = Xj
c) d(Xi, Xj) = d(Xj, Xi)
d) d(Xi, Xj) £ d(Xi, Xk) + d(Xk, Xj), kde Xj; Xi a Xk sú akékoľvek tri vektory z Ep.
Hodnota d(Xi, Xj) pre Xi a Xj sa nazýva vzdialenosť medzi Xi a Xj a je ekvivalentná vzdialenosti medzi Gi a Gj podľa zvolených charakteristík (F1, F2, F3, ..., Fр).
Najčastejšie používané funkcie vzdialenosti sú:
1. Euklidovská vzdialenosť d2(Хi , Хj) = 
2. l1 - norma d1(Хi , Хj) =
3. Supremum - norma d¥ (Хi , Хj) = súp
k = 1, 2, ..., s
4. lp - norma dр(Хi , Хj) = 
Najpopulárnejšia je euklidovská metrika. Metrika l1 sa vypočíta najjednoduchšie. Najvyššia norma sa ľahko vypočíta a zahŕňa postup objednávania, zatiaľ čo norma lp pokrýva funkcie vzdialenosti 1, 2, 3,.
Nech je n meraní X1, X2,..., Xn reprezentovaných ako dátová matica p ´n:
Potom môže byť vzdialenosť medzi pármi vektorov d(Хi, Хj) reprezentovaná ako symetrická matica vzdialenosti:
Koncept opačný k vzdialenosti je koncept podobnosti medzi objektmi Gi. a Gj. Nezáporná reálna funkcia S(Хi ; Хj) = Sij sa nazýva miera podobnosti, ak:
1) 0 £ S(Xi, Xj)<1 для Хi¹ Хj
2) S(Хi, Хi) = 1
3) S(Xi, Xj) = S(Xj, Xi)
Páry hodnôt miery podobnosti možno kombinovať do matice podobnosti:
Hodnota Sij sa nazýva koeficient podobnosti.
1.3. Metódy zhlukovej analýzy.
V súčasnosti existuje veľa metód klastrovej analýzy. Zastavme sa pri niektorých z nich (metódy uvedené nižšie sa zvyčajne nazývajú metódy minimálneho rozptylu).
Nech X je pozorovacia matica: X = (X1, X2,..., Xu) a druhá mocnina euklidovskej vzdialenosti medzi Xi a Xj je určená vzorcom:
1) Metóda úplných spojení.
Podstata tejto metódy spočíva v tom, že dva objekty patriace do rovnakej skupiny (zhluku) majú koeficient podobnosti, ktorý je menší ako nejaká prahová hodnota S. Z hľadiska euklidovskej vzdialenosti d to znamená, že vzdialenosť medzi dvoma bodmi (objektmi) klaster by nemal prekročiť určitú prahovú hodnotu h. h teda určuje maximálny povolený priemer podmnožiny tvoriacej zhluk.
2) Metóda maximálnej lokálnej vzdialenosti.
Každý objekt sa považuje za jednobodový zhluk. Objekty sa zoskupujú podľa nasledujúceho pravidla: dva zhluky sa kombinujú, ak je maximálna vzdialenosť medzi bodmi jedného zhluku a bodmi druhého minimálna. Postup pozostáva z n - 1 krokov a výsledkom sú oddiely, ktoré zodpovedajú všetkým možným oddielom v predchádzajúcej metóde pre akékoľvek prahové hodnoty.
3) Slovná metóda.
V tejto metóde sa ako účelová funkcia používa vnútroskupinový súčet štvorcových odchýlok, čo nie je nič iné ako súčet štvorcových vzdialeností medzi každým bodom (objektom) a priemerom pre zhluk obsahujúci tento objekt. V každom kroku sa kombinujú dva zhluky, ktoré vedú k minimálnemu zvýšeniu účelovej funkcie, t.j. vnútroskupinový súčet štvorcov. Táto metóda je zameraná na kombinovanie tesne umiestnených zhlukov.
4) Centroidová metóda.
Vzdialenosť medzi dvoma zhlukami je definovaná ako euklidovská vzdialenosť medzi stredmi (priemermi) týchto zhlukov:
d2 ij = (`X – `Y)Т(`X – `Y) Klastrovanie postupuje krok za krokom v každom z n–1 krokov kombinuje dva zhluky G a p s minimálnou hodnotou d2ij Ak je n1 oveľa väčšie ako n2, potom stredy spojenia dvoch zhlukov sú blízko seba a charakteristiky druhého zhluku sa pri kombinácii zhlukov prakticky ignorujú. Niekedy sa táto metóda niekedy nazýva aj metóda vážených skupín.
1.4 Algoritmus sekvenčného klastrovania.
Uvažujme Ι = (Ι1, Ι2, … Ιn) ako množinu zhlukov (Ι1), (Ι2),…(Ιn). Vyberme si dve z nich, napríklad Ι i a Ι j, ktoré sú v istom zmysle bližšie k sebe a spojme ich do jedného zhluku. Nový súbor klastrov, ktorý už pozostáva z n-1 klastrov, bude:
(Ι1), (Ι2)…, (Ι i, Ι j), …, (Ιn).
Opakovaním procesu získame po sebe nasledujúce súbory zhlukov pozostávajúce z (n-2), (n-3), (n-4) atď. klastre. Na konci postupu môžete získať zhluk pozostávajúci z n objektov a zhodujúci sa s počiatočnou množinou Ι = (Ι1, Ι2, … Ιn).
Ako mieru vzdialenosti berieme druhú mocninu euklidovskej metriky di j2. a vypočítajte maticu D = (di j2), kde di j2 je druhá mocnina vzdialenosti medzi
| 1 | Ja 2 | Ja 3 | …. | n | |
| 1 | 0 | d122 | d132 | …. | d1n2 |
| Ja 2 | 0 | d232 | …. | d2n2 | |
| Ja 3 | 0 | …. | d3n2 | ||
| …. | …. | …. | |||
| n | 0 |
Nech je vzdialenosť medzi Ι i a Ι j minimálna:
di j2 = min (di j2, i 1 j). Pomocou Ι i a Ι j vytvoríme nový zhluk
(I, I). Zostrojte novú ((n-1), (n-1)) maticu vzdialeností
| (ja, ja j) | 1 | Ja 2 | Ja 3 | …. | n | |
| (ja; ja j) | 0 | di j21 | di j22 | di j23 | …. | di j2n |
| 1 | 0 | d122 | d13 | …. | d12n | |
| Ja 2 | 0 | di j21 | …. | d2n | ||
| Ja 3 | 0 | …. | d3n | |||
| n | 0 |
(n-2) riadkov pre poslednú maticu sa vyberie z predchádzajúcej matice a prvý riadok sa prepočíta. Výpočty možno zredukovať na minimum, ak možno vyjadriť di j2k,k = 1, 2,…, n; (k ¹ i ¹ j) cez prvky pôvodnej matice.
Spočiatku sa vzdialenosť určovala iba medzi jednoprvkovými zhlukmi, ale je potrebné určiť aj vzdialenosti medzi zhlukami obsahujúcimi viac ako jeden prvok. Dá sa to urobiť rôznymi spôsobmi av závislosti od zvolenej metódy získame algoritmy klastrovej analýzy s rôznymi vlastnosťami. Napríklad je možné nastaviť vzdialenosť medzi klastrami i + j a niektorým iným klastrom k rovnú aritmetickému priemeru vzdialeností medzi klastrami i a k a klastrami j a k:
di+j,k = ½ (di k + dj k).
Ale je možné definovať aj di+j,k ako minimum z týchto dvoch vzdialeností:
di+j,k = min(di k + dj k).
Je teda opísaný prvý krok operácie aglomeratívneho hierarchického algoritmu. Ďalšie kroky sú rovnaké.
Pomerne širokú triedu algoritmov možno získať, ak sa na prepočet vzdialeností použije nasledujúci všeobecný vzorec:
di+j,k = A(w) min(dik djk) + B(w) max(dik djk), kde
A(w) = ak dik £ djk
A(w) = ak dik > djk
B(w) = ak dik £ djk
B(w) = ak dik > djk
kde ni a nj sú počet prvkov v zhlukoch i a j a w je voľný parameter, ktorého výber určuje konkrétny algoritmus. Napríklad s w = 1 dostaneme takzvaný algoritmus „priemerného spojenia“, pre ktorý má vzorec na prepočet vzdialeností tvar:
di+j,k = 
V tomto prípade sa vzdialenosť medzi dvoma klastrami v každom kroku algoritmu rovná aritmetickému priemeru vzdialeností medzi všetkými pármi prvkov tak, že jeden prvok z páru patrí do jedného klastra a druhý do iného.
Vizuálny význam parametra w bude jasný, ak dáme w®¥. Vzorec na prevod vzdialenosti má tvar:
di+j,k = min(di,k djk)
Pôjde o takzvaný algoritmus „najbližší sused“, ktorý vám umožňuje vybrať zhluky ľubovoľne zložitého tvaru za predpokladu, že rôzne časti takýchto zhlukov sú spojené reťazami prvkov blízko seba. V tomto prípade sa vzdialenosť medzi dvoma klastrami v každom kroku algoritmu rovná vzdialenosti medzi dvoma najbližšími prvkami patriacimi do týchto dvoch klastrov.
Pomerne často sa predpokladá, že počiatočné vzdialenosti (rozdiely) medzi zoskupenými prvkami sú dané. V niektorých prípadoch je to pravda. Špecifikované sú však iba objekty a ich charakteristiky a na základe týchto údajov je zostavená matica vzdialenosti. V závislosti od toho, či sa počítajú vzdialenosti medzi objektmi alebo medzi charakteristikami objektov, sa používajú rôzne metódy.
V prípade zhlukovej analýzy objektov je najbežnejšou mierou rozdielu buď druhá mocnina euklidovskej vzdialenosti
(kde xih, xjh sú hodnoty h-tého atribútu pre i-tý a j-tý objekt a m je počet charakteristík), alebo samotná euklidovská vzdialenosť. Ak sú vlastnostiam priradené rôzne váhy, potom sa tieto váhy môžu brať do úvahy pri výpočte vzdialenosti
Niekedy sa vzdialenosť používa ako miera rozdielu vypočítaná podľa vzorca:
ktoré sa nazývajú: vzdialenosť „Hamming“, „Manhattan“ alebo „mestský blok“.
Prirodzeným meradlom podobnosti charakteristík objektov v mnohých problémoch je korelačný koeficient medzi nimi
kde mi ,mj ,di ,dj sú stredná a odmocnina odchýlky pre charakteristiky i a j, v tomto poradí. Hodnota 1 - r môže slúžiť ako miera rozdielu medzi charakteristikami. V niektorých úlohách je znamienko korelačného koeficientu nevýznamné a závisí len od voľby mernej jednotky. V tomto prípade sa ô1 - ri j ô používa ako miera rozdielu medzi charakteristikami
1.5 Počet klastrov.
Veľmi dôležitou otázkou je problém výberu potrebného počtu klastrov. Niekedy je možné a priori zvoliť m počet zhlukov. Vo všeobecnom prípade sa však toto číslo určuje v procese rozdelenia súboru do zhlukov.
Štúdie vykonali Fortier a Solomon a zistilo sa, že na dosiahnutie pravdepodobnosti, že sa nájde najlepší oddiel, je potrebné vziať počet zhlukov. Optimálny počet oddielov je teda funkciou daného zlomku b najlepších alebo v istom zmysle realizovateľných oddielov v množine všetkých možných oddielov. Celkový rozptyl bude tým väčší, čím vyšší bude podiel b prípustných priečok. Fortier a Solomon vyvinuli tabuľku, z ktorej je možné zistiť počet potrebných partícií. S(a,b) v závislosti od a a b (kde a je pravdepodobnosť, že sa nájde najlepší oddiel, b je podiel najlepších oddielov na celkovom počte oddielov) Navyše, ako miera heterogenity, nie rozptylu používa sa však opatrenie o členstve, ktoré zaviedli Holzenger a Harman. Tabuľka hodnôt S(a,b) je uvedená nižšie.
Tabuľka hodnôt S(a,b).
| b\a | 0.20 | 0.10 | 0.05 | 0.01 | 0.001 | 0.0001 |
| 0.20 | 8 | 11 | 14 | 21 | 31 | 42 |
| 0.10 | 16 | 22 | 29 | 44 | 66 | 88 |
| 0.05 | 32 | 45 | 59 | 90 | 135 | 180 |
| 0.01 | 161 | 230 | 299 | 459 | 689 | 918 |
| 0.001 | 1626 | 2326 | 3026 | 4652 | 6977 | 9303 |
| 0.0001 | 17475 | 25000 | 32526 | 55000 | 75000 | 100000 |
Pomerne často je kritériom pre kombinovanie (počet zhlukov) zmena zodpovedajúcej funkcie. Napríklad súčty štvorcových odchýlok: 
Proces zoskupovania by tu mal zodpovedať konzistentnému minimálnemu zvýšeniu hodnoty kritéria E. Prítomnosť prudkého skoku v hodnote E možno interpretovať ako charakteristiku počtu zhlukov, ktoré objektívne existujú v skúmanej populácii.
Takže druhý spôsob, ako určiť najlepší počet zhlukov, je identifikovať skoky určené fázovým prechodom zo silne viazaného do slabo viazaného stavu objektov.
1.6 Dendogramy.
Najznámejšia metóda reprezentácie matice vzdialenosti alebo podobnosti je založená na myšlienke dendogramu alebo stromového diagramu. Dendogram možno definovať ako grafickú reprezentáciu výsledkov sekvenčného zhlukovacieho procesu, ktorý sa vykonáva pomocou matice vzdialeností. Pomocou dendogramu je možné graficky alebo geometricky znázorniť postup zhlukovania za predpokladu, že tento postup pracuje len s prvkami matice vzdialenosti alebo podobnosti.
Existuje mnoho spôsobov, ako vytvoriť dendrogramy. V dendrograme sú objekty umiestnené vertikálne vľavo, výsledky zhlukovania sú vpravo. Hodnoty vzdialenosti alebo podobnosti zodpovedajúce štruktúre nových zhlukov sú zobrazené pozdĺž vodorovnej priamky cez dendrogramy.
Obrázok 1 ukazuje jeden príklad dendogramu. Obrázok 1 zodpovedá prípadu šiestich objektov (n=6) ak charakteristikám (vlastnostiam). Objekty A a C sú najbližšie, a preto sú spojené do jedného zhluku na úrovni blízkosti rovnajúcej sa 0,9. Objekty D a E sú kombinované na úrovni 0,8. Teraz máme 4 klastre:
Typ dendogramu závisí od výberu miery podobnosti alebo vzdialenosti medzi objektom a zhlukom a od metódy zhlukovania. Najdôležitejším bodom je výber miery podobnosti alebo miery vzdialenosti medzi objektom a zhlukom.
Počet algoritmov klastrovej analýzy je príliš veľký. Všetky sa dajú rozdeliť na hierarchické a nehierarchické.
Hierarchické algoritmy sú spojené s konštrukciou dendogramov a delia sa na:
a) aglomeratívne, vyznačujúce sa konzistentnou kombináciou počiatočných prvkov a zodpovedajúcim poklesom počtu zhlukov;
b) deliteľné (deliteľné), v ktorých sa zvyšuje počet zhlukov, počnúc jedným, v dôsledku čoho sa vytvára postupnosť štiepiacich sa skupín.
Algoritmy klastrovej analýzy majú dnes dobrú softvérovú implementáciu, ktorá umožňuje riešiť problémy najvyššej dimenzie.
1.7 Údaje
Klastrovú analýzu možno použiť na intervalové údaje, frekvencie, binárne údaje. Je dôležité, aby sa premenné menili na porovnateľných mierkach.
Heterogenita meracích jednotiek a následná nemožnosť primeraného vyjadrenia hodnôt rôznych ukazovateľov v rovnakej mierke vedie k tomu, že vzdialenosť medzi bodmi, odrážajúca polohu objektov v priestore ich vlastností, sa ukazuje závisieť od ľubovoľne zvolenej mierky. Aby sa eliminovala heterogenita merania počiatočných údajov, všetky ich hodnoty sú predbežne normalizované, t.j. sú vyjadrené pomerom týchto hodnôt k určitej hodnote, ktorá odráža určité vlastnosti tohto ukazovateľa. Normalizácia počiatočných údajov pre klastrovú analýzu sa niekedy vykonáva vydelením počiatočných hodnôt štandardnou odchýlkou zodpovedajúcich ukazovateľov. Ďalším spôsobom je výpočet takzvaného štandardizovaného príspevku. Nazýva sa aj Z-príspevok.
Z-príspevok ukazuje, koľko štandardných odchýlok oddeľuje dané pozorovanie od priemeru:
Kde xi je hodnota tohto pozorovania, je priemer, S je štandardná odchýlka.
Priemer pre Z-príspevky je nula a štandardná odchýlka je 1.
Štandardizácia umožňuje porovnanie pozorovaní z rôznych distribúcií. Ak je rozdelenie premennej normálne (alebo blízke normálu) a priemer a rozptyl sú známe alebo odhadnuté z veľkých vzoriek, potom Z-príspevok pozorovania poskytuje konkrétnejšie informácie o jeho umiestnení.
Všimnite si, že normalizačné metódy znamenajú uznanie všetkých znakov ako ekvivalentných z hľadiska objasnenia podobnosti uvažovaných objektov. Už bolo poznamenané, že vo vzťahu k ekonomike sa uznanie rovnocennosti rôznych ukazovateľov nezdá vždy opodstatnené. Bolo by žiaduce, spolu s normalizáciou, dať každému z indikátorov váhu, ktorá odráža jeho význam pri zisťovaní podobností a rozdielov medzi objektmi.
V tejto situácii sa treba uchýliť k metóde určovania váh jednotlivých ukazovateľov – prieskumu odborníkov. Napríklad pri riešení problému klasifikácie krajín podľa úrovne ekonomického rozvoja sme vychádzali z výsledkov prieskumu 40 popredných moskovských odborníkov na problémy vyspelých krajín na desaťbodovej škále:
zovšeobecnené ukazovatele sociálno-ekonomického rozvoja - 9 bodov;
ukazovatele odvetvového rozloženia zamestnaného obyvateľstva - 7 bodov;
ukazovatele prevalencie prenajatej práce - 6 bodov;
ukazovatele charakterizujúce ľudský prvok výrobných síl - 6 bodov;
ukazovatele vývoja materiálnych výrobných síl - 8 bodov;
ukazovateľ verejných výdavkov - 4 body;
"vojensko-ekonomické" ukazovatele - 3 body;
sociodemografické ukazovatele - 4 body.
Odhady odborníkov boli relatívne stabilné.
Odborné hodnotenia poskytujú dobre známy základ na určenie dôležitosti ukazovateľov zaradených do určitej skupiny ukazovateľov. Násobenie normalizovaných hodnôt ukazovateľov koeficientom zodpovedajúcim priemernému hodnotiacemu skóre umožňuje vypočítať vzdialenosti medzi bodmi, ktoré odrážajú polohu krajín vo viacrozmernom priestore, berúc do úvahy nerovnakú váhu ich vlastností.
Pomerne často sa pri riešení takýchto problémov nepoužíva jeden, ale dva výpočty: prvý, v ktorom sa všetky znaky považujú za ekvivalentné, druhý, kde sa im priraďujú rôzne váhy v súlade s priemernými hodnotami odborných odhadov.
1.8. Aplikácia zhlukovej analýzy.
Pozrime sa na niektoré aplikácie klastrovej analýzy.
Rozdelenie krajín do skupín podľa úrovne rozvoja.
Študovalo sa 65 krajín podľa 31 ukazovateľov (národný dôchodok na obyvateľa, podiel obyvateľstva zamestnaného v priemysle v %, úspory na obyvateľa, podiel obyvateľstva zamestnaného v poľnohospodárstve v %, priemerná dĺžka života, počet áut na 1 tisíc obyvateľov, počet ozbrojených síl na 1 milión obyvateľov, podiel HDP v priemysle v %, podiel HDP v poľnohospodárstve v %, atď.)
Každá z krajín vystupuje v tejto úvahe ako objekt charakterizovaný určitými hodnotami 31 ukazovateľov. V súlade s tým môžu byť reprezentované ako body v 31-rozmernom priestore. Takýto priestor sa zvyčajne nazýva priestor vlastníctva skúmaných objektov. Porovnanie vzdialenosti medzi týmito bodmi bude odrážať stupeň blízkosti uvažovaných krajín, ich vzájomnú podobnosť. Socioekonomický význam tohto chápania podobnosti znamená, že krajiny sa považujú za čím viac podobné, tým menšie sú rozdiely medzi rovnakými ukazovateľmi, ktorými sú opísané.
Prvým krokom takejto analýzy je identifikácia dvojice národných ekonomík zahrnutých do matice podobnosti, pričom vzdialenosť medzi nimi je najmenšia. Pôjde zrejme o najpodobnejšie, podobné ekonomiky. V nasledujúcej úvahe sú obe tieto krajiny považované za jednu skupinu, jeden klaster. V súlade s tým je pôvodná matica transformovaná tak, že jej prvkami sú vzdialenosti medzi všetkými možnými pármi nie 65, ale 64 objektov - 63 ekonomík a novo transformovaný klaster - podmienené spojenie dvoch najpodobnejších krajín. Riadky a stĺpce zodpovedajúce vzdialenostiam od dvojice krajín zahrnutých v únii k všetkým ostatným sa z pôvodnej matice podobnosti vypustia, ale pridajú sa riadky a stĺpce obsahujúce vzdialenosť medzi zhlukom získaným úniou a ostatnými krajinami.
Predpokladá sa, že vzdialenosť medzi novo získaným klastrom a krajinami sa rovná priemeru vzdialeností medzi posledne menovaným a dvoma krajinami, ktoré tvoria nový klaster. Inými slovami, kombinovaná skupina krajín sa považuje za celok s charakteristikami, ktoré sa zhruba rovnajú priemeru charakteristík krajín, ktoré ju tvoria.
Druhým krokom analýzy je uvažovanie takto transformovanej matice so 64 riadkami a stĺpcami. Opäť sa identifikuje dvojica ekonomík, pričom vzdialenosť medzi nimi je najmenej dôležitá a tie sa, rovnako ako v prvom prípade, spájajú. V tomto prípade môže byť najmenšia vzdialenosť medzi dvojicou krajín, ako aj medzi ľubovoľnou krajinou a úniou krajín získanou v predchádzajúcej fáze.
Ďalšie postupy sú podobné tým, ktoré sú opísané vyššie: v každej fáze sa matica transformuje tak, že z nej sú vylúčené dva stĺpce a dva riadky obsahujúce vzdialenosť k objektom (páry krajín alebo združení - zhlukov), ktoré sa spojili v predchádzajúcej fáze. ; vylúčené riadky a stĺpce sú nahradené stĺpcom a riadkom obsahujúcim vzdialenosti od nových pripojení k ostatným prvkom; ďalej sa v upravenej matici odhalí dvojica najbližších objektov. Analýza pokračuje až do úplného vyčerpania matice (t. j. kým sa všetky krajiny nespoja). Zovšeobecnené výsledky maticovej analýzy možno znázorniť vo forme stromu podobnosti (dendogramu), podobného tomu, ktorý je opísaný vyššie, len s tým rozdielom, že strom podobnosti, ktorý odráža relatívnu blízkosť všetkých 65 krajín, o ktorých uvažujeme, je oveľa komplikovanejšie ako schéma, v ktorej sa objavuje len päť národných ekonomík. Tento strom obsahuje 65 úrovní podľa počtu zhodných objektov. Prvá (nižšia) úroveň obsahuje body zodpovedajúce každej krajine zvlášť. Prepojenie týchto dvoch bodov na druhej úrovni ukazuje dvojicu krajín, ktoré sú si z hľadiska všeobecného typu národných ekonomík najbližšie. Na tretej úrovni je zaznamenaný ďalší najpodobnejší pomer párov krajín (ako už bolo spomenuté, v tomto pomere môže byť buď nový pár krajín, alebo nová krajina a už identifikovaný pár podobných krajín). A tak ďalej až po poslednú úroveň, na ktorej všetky skúmané krajiny vystupujú ako jeden súbor.
Výsledkom aplikácie klastrovej analýzy bolo získaných päť skupín krajín:
afro-ázijská skupina;
latinsko-ázijská skupina;
latinsko-stredomorská skupina;
skupina vyspelých kapitalistických krajín (bez USA)
Zavedenie nových ukazovateľov nad rámec tu používaných 31 ukazovateľov alebo ich nahradenie inými prirodzene vedie k zmene výsledkov klasifikácie krajín.
2. Rozdelenie krajín podľa kritéria blízkosti kultúry.
Ako viete, marketing by mal zohľadňovať kultúru krajín (zvyky, tradície atď.).
Klastrovaním sa získali tieto skupiny krajín:
arabčina;
Stredný východ;
škandinávsky;
nemecky hovoriaci;
Anglicky hovoriacej;
románsky európsky;
Latinský Američan;
Ďaleký východ.
3. Vypracovanie prognózy trhu so zinkom.
Zhluková analýza zohráva dôležitú úlohu v štádiu redukcie ekonomického a matematického modelu konjunktúry komodít, prispieva k uľahčeniu a zjednodušeniu výpočtových postupov, zabezpečuje väčšiu kompaktnosť získaných výsledkov pri zachovaní požadovanej presnosti. Použitie zhlukovej analýzy umožňuje rozdeliť celý počiatočný súbor trhových ukazovateľov do skupín (zhlukov) podľa relevantných kritérií, čím sa uľahčuje výber najreprezentatívnejších ukazovateľov.
Klastrová analýza sa široko používa na modelovanie trhových podmienok. V praxi je väčšina prognostických úloh založená na použití klastrovej analýzy.
Napríklad úloha vypracovať prognózu trhu so zinkom.
Spočiatku bolo vybraných 30 kľúčových ukazovateľov globálneho trhu so zinkom:
X1 - čas
Výrobné čísla:
X2 - vo svete
X4 - Európa
X5 - Kanada
X6 - Japonsko
X7 - Austrália
Ukazovatele spotreby:
X8 - vo svete
X10 - Európa
X11 - Kanada
X12 - Japonsko
X13 - Austrália
Zásoby výrobcov zinku:
X14 - vo svete
X16 - Európa
X17 - ostatné krajiny
Spotrebiteľské zásoby zinku:
X18 - v USA
X19 - v Anglicku
X10 - v Japonsku
Dovoz zinkových rúd a koncentrátov (tis. ton)
X21 - v USA
X22 - v Japonsku
X23 - v Nemecku
Vývoz zinkových rúd a koncentrátov (tisíc ton)
X24 - z Kanady
X25 - z Austrálie
Dovoz zinku (tisíc ton)
X26 - v USA
X27 - do Anglicka
X28 - v Nemecku
Vývoz zinku (tisíc ton)
X29 - z Kanady
X30 - z Austrálie
Na určenie špecifických závislostí bol použitý aparát korelačnej a regresnej analýzy. Vzťahy boli analyzované na základe matice párových korelačných koeficientov. Tu bola prijatá hypotéza normálneho rozdelenia analyzovaných ukazovateľov konjunktúry. Je zrejmé, že rij nie sú jediným možným ukazovateľom vzťahu použitých ukazovateľov. Potreba použiť klastrovú analýzu v tomto probléme je spôsobená tým, že množstvo ukazovateľov ovplyvňujúcich cenu zinku je veľmi veľké. Je potrebné ich znížiť z niekoľkých nasledujúcich dôvodov:
a) nedostatok úplných štatistických údajov pre všetky premenné;
b) prudká komplikácia výpočtových postupov, keď sa do modelu zavedie veľké množstvo premenných;
c) optimálne využitie metód regresnej analýzy vyžaduje prekročenie počtu pozorovaných hodnôt nad počtom premenných najmenej 6-8 krát;
d) túžba použiť v modeli štatisticky nezávislé premenné atď.
Je veľmi ťažké vykonať takúto analýzu priamo na relatívne objemnej matici korelačných koeficientov. Pomocou klastrovej analýzy možno celý súbor trhových premenných rozdeliť do skupín tak, že prvky každého klastra navzájom silne korelujú a zástupcovia rôznych skupín sa vyznačujú slabou koreláciou.
Na vyriešenie tohto problému bol použitý jeden z algoritmov aglomeratívnej hierarchickej klastrovej analýzy. V každom kroku sa počet zhlukov zníži o jeden v dôsledku optimálneho, v určitom zmysle, spojenia dvoch skupín. Kritériom spojenia je zmena príslušnej funkcie. V závislosti od toho sa použili hodnoty súčtu štvorcových odchýlok vypočítaných podľa nasledujúcich vzorcov:
(j = 1, 2, …, m),
kde j je číslo zhluku, n je počet prvkov v zhluku.
rij - párový korelačný koeficient.
Proces zoskupovania teda musí zodpovedať postupnému minimálnemu zvýšeniu hodnoty kritéria E.
V prvej fáze je počiatočné dátové pole prezentované ako súbor pozostávajúci zo zhlukov, z ktorých každý obsahuje jeden prvok. Proces zoskupovania začína spojením takejto dvojice zhlukov, čo vedie k minimálnemu zvýšeniu súčtu štvorcových odchýlok. To si vyžaduje odhad súčtu štvorcových odchýlok pre každý z možných zväzkov klastrov. V ďalšej fáze sa už pre klastre zvažujú hodnoty súčtov štvorcových odchýlok atď. Tento proces sa v určitom kroku zastaví. Aby ste to dosiahli, musíte sledovať hodnotu súčtu štvorcových odchýlok. Vzhľadom na postupnosť rastúcich hodnôt je možné zachytiť skok (jeden alebo viacero) v jej dynamike, ktorý možno interpretovať ako charakteristiku počtu skupín „objektívne“ existujúcich v skúmanej populácii. Vo vyššie uvedenom príklade sa skoky uskutočnili, keď bol počet zhlukov 7 a 5. Ďalej by sa počet skupín nemal znižovať, pretože to vedie k zníženiu kvality modelu. Po získaní klastrov sa vyberú premenné, ktoré sú z ekonomického hľadiska najdôležitejšie a najviac súvisia s vybraným trhovým kritériom – v tomto prípade kotácie zinku na London Metal Exchange. Tento prístup vám umožňuje uložiť významnú časť informácií obsiahnutých v pôvodnom súbore počiatočných indikátorov konjunktúry.
