Metódy zhlukovej analýzy. hierarchické metódy. Zhluková analýza je algoritmus na štúdium údajov rozdelených do skupín podľa podobných charakteristík.

pozdravujem!

Vo svojej diplomovej práci som vykonal prehľad a komparatívnu analýzu algoritmov zhlukovania údajov. Myslel som si, že už zozbieraný a vypracovaný materiál môže byť pre niekoho zaujímavý a užitočný.
O tom, čo je zhlukovanie, povedal v článku. Čiastočne zopakujem slová Alexandra, čiastočne doplním. Aj na konci tohto článku si môžu záujemcovia prečítať materiály na odkazoch v zozname literatúry.

Suchý „diplomový“ štýl prezentácie som sa snažil preniesť aj do novinárskejšieho.

Koncept klastrovania

Klastrovanie (alebo klastrová analýza) je úlohou rozdeliť množinu objektov do skupín nazývaných klastre. V každej skupine by mali byť „podobné“ objekty a objekty rôznych skupín by sa mali čo najviac líšiť. Hlavný rozdiel medzi zoskupovaním a klasifikáciou je v tom, že zoznam skupín nie je jasne definovaný a určuje sa v priebehu algoritmu.

Aplikácia klastrovej analýzy v všeobecný pohľad sa scvrkáva na nasledujúce kroky:

Výber vzorky objektov na zhlukovanie.
Definícia množiny premenných, podľa ktorých budú objekty vo vzorke hodnotené. Ak je to potrebné, normalizujte hodnoty premenných.
Výpočet hodnôt merania podobnosti medzi objektmi.
Aplikácia metódy zhlukovej analýzy na vytváranie skupín podobných objektov (zhlukov).
Prezentácia výsledkov analýzy.

Po prijatí a analýze výsledkov je možné upraviť zvolenú metriku a metódu zoskupovania, kým sa nedosiahne optimálny výsledok.

Miery vzdialenosti

Ako teda určiť „podobnosť“ objektov? Najprv musíte vytvoriť vektor charakteristík pre každý objekt - spravidla je to súbor číselných hodnôt, napríklad výška a hmotnosť osoby. Existujú však aj algoritmy, ktoré pracujú s kvalitatívnymi (tzv. kategorickými) charakteristikami.

Keď sme určili vektor prvku, môžeme ho normalizovať tak, aby všetky komponenty pri výpočte „vzdialenosti“ prispievali rovnako. Počas procesu normalizácie sa všetky hodnoty znížia na určitý rozsah, napríklad [-1, -1] alebo .

Nakoniec sa pre každú dvojicu predmetov meria „vzdialenosť“ medzi nimi – miera podobnosti. Existuje veľa metrík, tu sú len tie hlavné:

Výber metriky je výlučne na výskumníkovi, pretože výsledky zhlukovania sa môžu výrazne líšiť pri použití rôznych mier.

Klasifikácia algoritmov

Pre seba som identifikoval dve hlavné klasifikácie klastrovacích algoritmov.

Hierarchický a plochý.
Hierarchické algoritmy (tiež nazývané taxonomické algoritmy) nestavajú jedno rozdelenie vzorky do nesúvislých zhlukov, ale systém vnorených oddielov. To. na výstupe dostaneme strom klastrov, ktorého koreňom je celá vzorka a listy sú najmenšie zhluky.
Ploché algoritmy vytvárajú jednu oblasť objektov do zhlukov.
Jasné a nejasné.
Jasné (alebo neprekrývajúce sa) algoritmy priraďujú každému vzorovému objektu číslo zhluku, t.j. každý objekt patrí len do jedného klastra. Fuzzy (alebo pretínajúce sa) algoritmy priraďujú každému objektu množinu skutočných hodnôt, ktoré ukazujú stupeň vzťahu objektu ku klastrom. Tie. každý objekt s určitou pravdepodobnosťou patrí do každého zhluku.

Zlučovanie klastrov

V prípade použitia hierarchických algoritmov vyvstáva otázka, ako zhluky navzájom kombinovať, ako vypočítať „vzdialenosti“ medzi nimi. Existuje niekoľko metrík:

Jedno spojenie (najbližšie susedské vzdialenosti)
V tejto metóde je vzdialenosť medzi dvoma zhlukami určená vzdialenosťou medzi dvoma najbližšími objektmi (najbližšími susedmi) v rôznych zhlukoch. Výsledné zhluky majú tendenciu sa spájať.
Celý odkaz (vzdialenosť od najvzdialenejších susedov)
V tejto metóde sú vzdialenosti medzi zhlukami určené najväčšou vzdialenosťou medzi akýmikoľvek dvoma objektmi v rôznych zhlukoch (t. j. najvzdialenejšími susedmi). Táto metóda zvyčajne funguje veľmi dobre, keď objekty pochádzajú zo samostatných skupín. Ak sú zhluky pretiahnuté alebo ich prirodzený typ je „reťazový“, potom je táto metóda nevhodná.
Nevážený párový priemer
V tejto metóde sa vzdialenosť medzi dvoma rôznymi zhlukami vypočíta ako priemerná vzdialenosť medzi všetkými pármi objektov v nich. Metóda je efektívna, keď objekty tvoria rôzne skupiny, ale rovnako dobre funguje aj v prípadoch rozšírených ("reťazových") zhlukov.
Vážený párový priemer
Metóda je identická s metódou neváženého párového priemeru s tým rozdielom, že ako váhový faktor sa pri výpočtoch používa veľkosť príslušných zhlukov (tj počet objektov, ktoré obsahujú). Preto by sa táto metóda mala použiť, keď sa očakávajú nerovnaké veľkosti klastrov.
Metóda neváženého ťažiska
V tejto metóde je vzdialenosť medzi dvoma klastrami definovaná ako vzdialenosť medzi ich ťažiskami.
Metóda váženého ťažiska (medián)
Táto metóda je identická s predchádzajúcou, s výnimkou toho, že výpočty používajú váhy na zohľadnenie rozdielov medzi veľkosťami klastrov. Preto, ak existujú alebo existuje podozrenie na významné rozdiely vo veľkostiach klastrov, táto metóda je vhodnejšia ako predchádzajúca.

Prehľad algoritmov

Hierarchické zhlukovacie algoritmy

Existujú dva hlavné typy algoritmov hierarchického zhlukovania: vzostupný a zostupný algoritmus. Algoritmy zhora nadol fungujú na princípe zhora nadol: na začiatku sú všetky objekty umiestnené v jednom zhluku, ktorý sa potom delí na menšie a menšie zhluky. Bežnejšie sú algoritmy zdola nahor, ktoré najprv umiestnia každý prvok do samostatného klastra a potom zhluky zlúčia do väčších a väčších zhlukov, až kým všetky vzorkované prvky nebudú obsiahnuté v rovnakom klastri. Takto je skonštruovaný systém vnorených oddielov. Výsledky takýchto algoritmov sú zvyčajne prezentované vo forme stromu - dendrogramu. Klasickým príkladom takéhoto stromu je klasifikácia zvierat a rastlín.

Na výpočet vzdialeností medzi zhlukmi každý používa najčastejšie dve vzdialenosti: jednoduché spojenie alebo úplné spojenie (pozri prehľad mier vzdialeností medzi zhlukami).

Nevýhodou hierarchických algoritmov je systém úplných partícií, ktorý môže byť v kontexte riešeného problému nadbytočný.

Algoritmy kvadratických chýb

Problém zhlukovania možno považovať za konštrukciu optimálneho rozdelenia objektov do skupín. V tomto prípade možno optimálnosť definovať ako požiadavku na minimalizáciu chyby rozdelenia koreňovej strednej hodnoty:

Kde cj- "ťažisko" zhluku j(bod s priemernými hodnotami charakteristík pre daný klaster).

Algoritmy kvadratických chýb sú typu plochých algoritmov. Najbežnejším algoritmom v tejto kategórii je metóda k-means. Tento algoritmus vytvára daný počet zhlukov umiestnených čo najďalej od seba. Práca algoritmu je rozdelená do niekoľkých etáp:

Vyberte si náhodne k body, ktoré sú počiatočnými „ťažiskami“ zhlukov.
Priraďte každý objekt do zhluku s najbližším „stredom hmoty“.
Prepočítajte „ťažiská“ zhlukov podľa ich aktuálneho zloženia.
Ak nie je splnené kritérium na zastavenie algoritmu, vráťte sa na krok 2.

Ako kritérium na zastavenie činnosti algoritmu sa zvyčajne volí minimálna zmena strednej štvorcovej chyby. Algoritmus je tiež možné zastaviť, ak v kroku 2 neboli žiadne objekty, ktoré sa presúvali z klastra do klastra.

Nevýhody tohto algoritmu zahŕňajú potrebu špecifikovať počet klastrov na rozdelenie.

Fuzzy Algoritmy

Najpopulárnejším fuzzy zhlukovým algoritmom je algoritmus c-means. Ide o modifikáciu metódy k-means. Kroky algoritmu:

Tento algoritmus nemusí byť vhodný, ak nie je vopred známy počet zhlukov, alebo ak je potrebné jedinečne priradiť každý objekt jednému zhluku.

Algoritmy založené na teórii grafov

Podstatou takýchto algoritmov je, že výber objektov je reprezentovaný ako graf G=(V, E), ktorej vrcholy zodpovedajú objektom a ktorých hrany majú váhu rovnajúcu sa „vzdialenosti“ medzi objektmi. Výhodou algoritmov zhlukovania grafov je viditeľnosť, relatívna jednoduchosť implementácie a možnosť rôznych vylepšení na základe geometrických úvah. Hlavnými algoritmami sú algoritmus na extrakciu spojených komponentov, algoritmus na zostavenie minimálneho spanningového (spanning) stromu a algoritmus na vrstvené zhlukovanie.

Algoritmus na extrakciu pripojených komponentov

V algoritme na extrakciu pripojených komponentov je nastavený vstupný parameter R a v grafe všetky hrany, pre ktoré sú "vzdialenosti" väčšie ako R. Zostanú spojené len najbližšie dvojice objektov. Účelom algoritmu je nájsť takúto hodnotu R, ktorá leží v rozmedzí všetkých „vzdialeností“, pri ktorých sa graf „rozpadne“ na niekoľko spojených komponentov. Výslednými komponentmi sú klastre.

Ak chcete vybrať parameter R zvyčajne sa zostrojí histogram distribúcií párových vzdialeností. V úlohách s dobre definovanou klastrovou dátovou štruktúrou bude mať histogram dva vrcholy – jeden zodpovedá vzdialenostiam v rámci klastra, druhý zodpovedá vzdialenostiam medzi klastrami. Parameter R je vybraný zo zóny minima medzi týmito vrcholmi. Zároveň je pomerne ťažké kontrolovať počet zhlukov pomocou prahu vzdialenosti.

Minimálny algoritmus Spanning Tree

Algoritmus minimálneho kostrového stromu najprv vytvorí minimálny kostrový strom na grafe a potom postupne odstráni hrany s najvyššou váhou. Obrázok ukazuje minimálnu kostru získanú pre deväť prvkov.

Odstránením odkazu označeného CD s dĺžkou 6 jednotiek (okraj s maximálnou vzdialenosťou) získame dva zhluky: (A, B, C) a (D, E, F, G, H, I). Druhý zhluk možno ďalej rozdeliť na ďalšie dva zhluky odstránením okraja EF, ktorý má dĺžku 4,5 jednotky.

Vrstvené klastrovanie

Algoritmus zhlukovania vrstvy po vrstve je založený na výbere spojených komponentov grafu na určitej úrovni vzdialeností medzi objektmi (vrcholmi). Úroveň vzdialenosti je nastavená prahom vzdialenosti c. Napríklad, ak vzdialenosť medzi objektmi

, potom .

Algoritmus vrstveného klastrovania generuje postupnosť podgrafov grafu G, ktoré odrážajú hierarchické vzťahy medzi klastrami:

Kde Gt = (V, Et)- graf hladiny s t,
,
s t– t-tý prah vzdialenosti,
m je počet úrovní hierarchie,
G 0 = (V, o), o je prázdna množina hrán grafu získaná pomocou t0 = 1,
Gm = G, teda graf objektov bez obmedzenia vzdialenosti (dĺžky hrán grafu), od r tm = 1.

Zmenou prahov vzdialenosti ( s 0 , …, s m), kde 0 = od 0 < od 1 < …< s m= 1, je možné kontrolovať hĺbku hierarchie výsledných zhlukov. Algoritmus klastrovania vrstva po vrstve je teda schopný vytvoriť plochý dátový oddiel aj hierarchický oddiel.

Porovnanie algoritmov

Výpočtová zložitosť algoritmov

Porovnávacia tabuľka algoritmov

Algoritmus klastrovania	Forma zhlukov	Vstupné Data	výsledky
Hierarchický	zadarmo	Počet zhlukov alebo prah vzdialenosti na skrátenie hierarchie	Binárny strom zhlukov
k-znamená	hypersféra	Počet zhlukov	Klastrové centrá
c-znamená	hypersféra	Počet zhlukov, stupeň neostrosti	Klastrové centrá, matica členstva
Výber pripojených komponentov	zadarmo	Prah vzdialenosti R
Minimálny kostra	zadarmo	Počet zhlukov alebo prah vzdialenosti na odstránenie hrán	Stromová štruktúra zhlukov
Vrstvené klastrovanie	zadarmo	Postupnosť prahov vzdialenosti	Stromová štruktúra zhlukov s rôznymi úrovňami hierarchie

Trochu o aplikácii

Vo svojej práci som potreboval vybrať samostatné oblasti z hierarchických štruktúr (stromov). Tie. v podstate bolo potrebné rozrezať pôvodný strom na niekoľko menších stromov. Keďže riadený strom je špeciálnym prípadom grafu, algoritmy založené na teórii grafov sú prirodzene vhodné.

Na rozdiel od plne spojeného grafu nie sú všetky vrcholy v orientovanom strome spojené hranami a celkový počet hrán je n–1, kde n je počet vrcholov. Tie. vo vzťahu k uzlom stromu sa zjednoduší práca algoritmu na extrakciu spojených komponentov, pretože odstránením ľubovoľného počtu hrán sa strom „rozdelí“ na spojené komponenty (samostatné stromy). Minimálny algoritmus spanning tree sa v tomto prípade bude zhodovať s algoritmom na extrakciu pripojených komponentov - odstránením najdlhších hrán sa pôvodný strom rozdelí na niekoľko stromov. V tomto prípade je zrejmé, že fáza budovania najmenšieho kostry sa preskočí.

V prípade použitia iných algoritmov by museli samostatne brať do úvahy prítomnosť vzťahov medzi objektmi, čo algoritmus komplikuje.

Samostatne chcem povedať, že na dosiahnutie najlepšieho výsledku je potrebné experimentovať s výberom mier vzdialenosti a niekedy dokonca zmeniť algoritmus. Neexistuje jediné riešenie.

zhluková analýza

Väčšina výskumníkov sa prikláňa k názoru, že po prvýkrát sa používa termín „zhluková analýza“ (angl. zhluk- trs, zrazenina, trs) navrhol matematik R. Trion. Následne vzniklo množstvo pojmov, ktoré sa dnes považujú za synonymá s pojmom „zhluková analýza“: automatická klasifikácia; botryológia.

Klastrová analýza je viacrozmerný štatistický postup, ktorý zhromažďuje údaje obsahujúce informácie o vzorke objektov a potom objekty usporiada do relatívne homogénnych skupín (zhlukov) (Q-zhlukovanie alebo Q-technika, vlastná zhluková analýza). Zhluk – skupina prvkov charakterizovaná spoločnou vlastnosťou, hlavným cieľom zhlukovej analýzy je nájsť vo vzorke skupiny podobných objektov. Rozsah aplikácií zhlukovej analýzy je veľmi široký: využíva sa v archeológii, medicíne, psychológii, chémii, biológii, verejnej správe, filológii, antropológii, marketingu, sociológii a ďalších disciplínach. Univerzálnosť aplikácie však viedla k vzniku veľkého množstva nekompatibilných termínov, metód a prístupov, ktoré sťažujú jednoznačné používanie a dôslednú interpretáciu zhlukovej analýzy. Orlov A. I. navrhuje rozlišovať takto:

Úlohy a podmienky

Klastrová analýza vykonáva nasledovné hlavné ciele:

Vypracovanie typológie alebo klasifikácie.
Skúmanie užitočných koncepčných schém na zoskupovanie objektov.
Generovanie hypotéz na základe prieskumu údajov.
Testovanie hypotéz alebo výskum s cieľom zistiť, či typy (skupiny) identifikované tak či onak sú skutočne prítomné v dostupných údajoch.

Bez ohľadu na predmet štúdia, použitie klastrovej analýzy zahŕňa Ďalšie kroky:

Odber vzoriek na klastrovanie. Rozumie sa, že má zmysel zoskupovať iba kvantitatívne údaje.
Definícia množiny premenných, podľa ktorých budú hodnotené objekty vo vzorke, teda priestor znakov.
Výpočet hodnôt jednej alebo druhej miery podobnosti (alebo rozdielu) medzi objektmi.
Aplikácia metódy zhlukovej analýzy na vytváranie skupín podobných objektov.
Validácia výsledkov klastrového riešenia.

Klastrová analýza uvádza nasledovné požiadavky na údaje:

ukazovatele by nemali navzájom korelovať;
ukazovatele by nemali byť v rozpore s teóriou meraní;
rozloženie ukazovateľov by malo byť blízke normálu;
ukazovatele musia spĺňať požiadavku „stability“, čo znamená absenciu vplyvu na ich hodnoty náhodnými faktormi;
vzorka by mala byť homogénna, nemala by obsahovať „odľahlé hodnoty“.

Môžete nájsť popis dvoch základných požiadaviek na údaje – jednotnosť a úplnosť:

Homogenita vyžaduje, aby všetky entity zobrazené v tabuľke mali rovnakú povahu. Požiadavkou na úplnosť je, že zostavy ja a J predložil úplný popis prejavov posudzovaného javu. Ak vezmeme do úvahy tabuľku, v ktorej ja je zbierka a J- súbor premenných popisujúcich túto populáciu, potom by to mala byť reprezentatívna vzorka zo skúmanej populácie a systém charakteristík J by mali poskytnúť uspokojivé vektorové zastúpenie jednotlivcov i z pohľadu výskumníka.

Ak klastrovej analýze predchádza faktorová analýza, potom nie je potrebné vzorku „opravovať“ – uvedené požiadavky vykoná automaticky samotná procedúra modelovania faktorov (je tu ďalšia výhoda – z-štandardizácia bez negatívnych dôsledkov na vzorku; ak vykonáva sa priamo pre zhlukovú analýzu, môže to viesť k zníženiu prehľadnosti oddeľovania skupín). V opačnom prípade je potrebné vzorku upraviť.

Typológia klastrovacích problémov

Typy vstupu

AT moderná veda Na spracovanie vstupných údajov sa používa niekoľko algoritmov. Analýza porovnávaním objektov na základe znakov (najbežnejšie v biologických vedách) sa nazýva Q- typ analýzy a v prípade porovnávania vlastností na základe objektov - R- druh analýzy. Existujú pokusy použiť hybridné typy analýz (napr. RQ analýza), ale táto metodika ešte nebola riadne vyvinutá.

Ciele klastrovania

Pochopenie údajov identifikáciou štruktúry klastra. Rozdelenie vzorky do skupín podobných objektov umožňuje zjednodušiť ďalšie spracovanie údajov a rozhodovanie aplikáciou vlastnej metódy analýzy na každý zhluk (stratégia „rozdeľ a panuj“).
Kompresia údajov. Ak je počiatočná vzorka príliš veľká, môže sa zredukovať, pričom zostane jeden z najtypickejších predstaviteľov z každého klastra.
detekcia novosti. detekcia novosti). Vyberajú sa atypické objekty, ktoré nie je možné pripojiť k žiadnemu z klastrov.

V prvom prípade sa snažia počet zhlukov zmenšiť. V druhom prípade je dôležitejšie zabezpečiť vysoký stupeň podobnosti objektov v rámci každého klastra a môže existovať ľubovoľný počet zhlukov. V treťom prípade je najväčší záujem o jednotlivé objekty, ktoré nezapadajú do žiadneho zo zhlukov.

Vo všetkých týchto prípadoch je možné použiť hierarchické zhlukovanie, keď sa veľké zhluky rozdelia na menšie, ktoré sa zase rozdelia na ešte menšie atď. Takéto úlohy sa nazývajú úlohy taxonómie. Výsledkom taxonómie je stromová hierarchická štruktúra. Okrem toho je každý objekt charakterizovaný vymenovaním všetkých zhlukov, do ktorých patrí, zvyčajne od veľkých po malé.

Metódy klastrovania

Neexistuje všeobecne akceptovaná klasifikácia metód zhlukovania, ale možno zaznamenať solídny pokus V. S. Berikova a G. S. Lbova. Ak zovšeobecníme rôzne klasifikácie metód zhlukovania, môžeme rozlíšiť niekoľko skupín (niektoré metódy možno priradiť viacerým skupinám naraz, a preto sa navrhuje považovať túto typizáciu za určitú aproximáciu k skutočnej klasifikácii metód zhlukovania):

Pravdepodobnostný prístup. Predpokladá sa, že každý uvažovaný objekt patrí do jednej z k tried. Niektorí autori (napríklad A. I. Orlov) tomu veria túto skupinu sa vôbec netýka zhlukovania a oponuje mu pod názvom „diskriminácia“, teda výber priraďovania objektov do jednej zo známych skupín (tréningové vzorky).
Prístupy založené na systémoch umelej inteligencie. Veľmi podmienená skupina, pretože existuje veľa metód AI a metodicky sú veľmi odlišné.
logický prístup. Konštrukcia dendrogramu sa vykonáva pomocou rozhodovacieho stromu.
Grafo-teoretický prístup.
- Algoritmy zhlukovania grafov
Hierarchický prístup. Predpokladá sa prítomnosť vnorených skupín (zhlukov rôznych rádov). Algoritmy sa zase delia na aglomeratívne (zjednocujúce) a deliace (oddeľujúce). Podľa počtu znakov sa niekedy rozlišujú monotetické a polytetické spôsoby klasifikácie.
- Hierarchické deliace zhlukovanie alebo taxonómia. Problémy zhlukovania sa berú do úvahy v kvantitatívnej taxonómii.
Iné metódy. Nezahrnuté v predchádzajúcich skupinách.
- Štatistické klastrovacie algoritmy
- Súbor klastrov
- Algoritmy rodiny KRAB
- Algoritmus založený na metóde preosievania
- DBSCAN atď.

Prístupy 4 a 5 sa niekedy kombinujú pod názvom štrukturálny alebo geometrický prístup, ktorý má viac formalizovaný koncept blízkosti. Napriek výrazným rozdielom medzi uvedenými metódami sa všetky spoliehajú na pôvodný „ hypotéza kompaktnosti»: v objektovom priestore musia všetky blízke objekty patriť do rovnakého zhluku a všetky rôzne objekty musia byť v rôznych zhlukoch.

Formálne vyhlásenie o probléme klastrovania

Nech je množina objektov, je množina čísel (názvov, označení) zhlukov. Funkcia vzdialenosti medzi objektmi je daná. Existuje konečná trénovacia množina objektov. Je potrebné vzorku rozdeliť na neprekrývajúce sa podmnožiny, tzv klastre, takže každý zhluk pozostáva z objektov blízkych metrike a objekty rôznych zhlukov sa výrazne líšia. V tomto prípade je každému objektu priradené číslo klastra.

Algoritmus klastrovania je funkcia, ktorá spája akýkoľvek objekt s číslom klastra. Súbor je v niektorých prípadoch známy vopred, ale častejšie je úlohou určiť optimálny počet zhlukov z hľadiska jedného alebo druhého. kritériá kvality zhlukovanie.

Klastrovanie (učenie bez dozoru) sa líši od klasifikácie (učenie pod dohľadom) v tom, že označenia pôvodných objektov nie sú pôvodne nastavené a samotný súbor môže byť dokonca neznámy.

Riešenie problému zhlukovania je zásadne nejednoznačné a existuje na to niekoľko dôvodov (podľa viacerých autorov):

neexistuje jednoznačne najlepšie kritérium kvalita zhlukovania. Je známych množstvo heuristických kritérií, ako aj množstvo algoritmov, ktoré nemajú jasne definované kritérium, ale vykonávajú pomerne rozumné zhlukovanie „podľa konštrukcie“. Všetky môžu poskytnúť rôzne výsledky. Na určenie kvality klastrovania je preto potrebný odborník v predmetnej oblasti, ktorý by vedel posúdiť zmysluplnosť výberu klastrov.
počet zhlukov je zvyčajne vopred neznámy a je stanovený podľa nejakého subjektívneho kritéria. Platí to len pre diskriminačné metódy, pretože pri metódach klastrovania sa zhluky vyberajú pomocou formalizovaného prístupu založeného na opatreniach blízkosti.
výsledok zhlukovania výrazne závisí od metriky, ktorej výber je spravidla tiež subjektívny a určuje ju odborník. Je však potrebné poznamenať, že existuje niekoľko odporúčaní na výber opatrení na blízkosť pre rôzne úlohy.

Aplikácia

V biológii

V biológii má zhlukovanie mnoho aplikácií v širokej škále oblastí. Napríklad v bioinformatike sa používa na analýzu zložitých sietí interagujúcich génov, ktoré niekedy pozostávajú zo stoviek alebo dokonca tisícov prvkov. Klastrová analýza vám umožňuje identifikovať podsiete, úzke miesta, uzly a ďalšie skryté vlastnosti skúmaného systému, čo vám v konečnom dôsledku umožňuje zistiť podiel každého génu na vzniku skúmaného javu.

V oblasti ekológie sa široko používa na identifikáciu priestorovo homogénnych skupín organizmov, spoločenstiev atď. Menej často sa na štúdium spoločenstiev v priebehu času používajú metódy klastrovej analýzy. Heterogenita štruktúry spoločenstiev vedie k vzniku netriviálnych metód zhlukovej analýzy (napríklad Czekanowského metóda).

Vo všeobecnosti stojí za zmienku, že historicky sa miery podobnosti v biológii častejšie používajú ako miery blízkosti, než miery rozdielu (vzdialenosti).

V sociológii

Pri analýze výsledkov sociologického výskumu sa odporúča vykonať analýzu pomocou metód hierarchickej aglomeratívnej rodiny, konkrétne Wardovej metódy, pri ktorej sa v rámci zhlukov optimalizuje minimálny rozptyl, výsledkom čoho sú zhluky približne rovnakej veľkosti. sú vytvorené. Wardova metóda je najúspešnejšia pri analýze sociologických údajov. Ako miera rozdielu je lepšia kvadratická euklidovská vzdialenosť, čo prispieva k zvýšeniu kontrastu zhlukov. Hlavným výsledkom hierarchickej zhlukovej analýzy je dendrogram alebo „srazový diagram“. Pri jej interpretácii sa výskumníci stretávajú s problémom rovnakého druhu, ako je interpretácia výsledkov faktorovej analýzy – nedostatok jednoznačných kritérií na identifikáciu zhlukov. Ako hlavné sa odporúča použiť dve metódy - vizuálnu analýzu dendrogramu a porovnanie výsledkov zhlukovania vykonaných rôznymi metódami.

Vizuálna analýza dendrogramu zahŕňa „rezanie“ stromu na optimálnu úroveň podobnosti prvkov vzorky. „Vetva viniča“ (terminológia Oldenderfer M.S. a Blashfield R.K.) by mala byť „odrezaná“ okolo 5 na stupnici Rescaled Distance Cluster Combine, čím sa dosiahne 80% úroveň podobnosti. Ak je výber zhlukov podľa tohto označenia zložitý (niekoľko malých zhlukov sa na ňom zlúči do jedného veľkého), môžete si vybrať iné označenie. Túto techniku navrhli Oldenderfer a Blashfield.

Teraz vyvstáva otázka stability prijatého klastrového riešenia. V skutočnosti kontrola stability klastrovania spočíva v kontrole jeho spoľahlivosti. Platí tu základné pravidlo – pri zmene metód zhlukovania sa zachováva stabilná typológia. Výsledky hierarchickej zhlukovej analýzy je možné overiť iteračnou zhlukovou analýzou k-means. Ak majú porovnávané klasifikácie skupín respondentov podiel zhody viac ako 70 % (viac ako 2/3 zhody), tak sa rozhoduje o klastri.

Bez použitia iného typu analýzy nie je možné skontrolovať adekvátnosť riešenia. Aspoň teoreticky tento problém nie je vyriešený. Klastrová analýza Oldenderfera a Blashfielda rozpracúva a nakoniec odmieta päť dodatočných metód testovania robustnosti:

V informatike

Klastrovanie výsledkov vyhľadávania – používa sa na „inteligentné“ zoskupovanie výsledkov pri vyhľadávaní súborov, webových stránok, iných objektov, čo umožňuje používateľovi rýchlu navigáciu, výber podmnožiny, ktorá je zjavne relevantnejšia a vylučuje známu menej relevantnú – čo môže zvýšiť použiteľnosť rozhrania v porovnaní s výstupom vo forme jednoduchého zoradeného podľa zoznamu relevantnosti.
- Clusty – vyhľadávací nástroj Vivísimo na zoskupovanie
- Nigma - ruský vyhľadávač s automatickým zoskupovaním výsledkov
- Quintura - vizuálne zhlukovanie vo forme oblaku kľúčových slov
Segmentácia obrazu segmentácia obrazu) - Klastrovanie možno použiť na rozdelenie digitálneho obrazu na odlišné oblasti za účelom detekcie hrán. detekcia hrán) alebo rozpoznávanie objektov.
Dolovanie dát data mining)- Klastrovanie v dolovaní údajov sa stáva cenným, keď funguje ako jedna z fáz analýzy údajov a vytvára kompletné analytické riešenie. Pre analytika je často jednoduchšie identifikovať skupiny podobných objektov, študovať ich vlastnosti a vytvoriť samostatný model pre každú skupinu, než vytvoriť jeden všeobecný model pre všetky údaje. Táto technika sa neustále používa v marketingu, zvýrazňuje skupiny zákazníkov, kupujúcich, tovar a rozvíja samostatnú stratégiu pre každého z nich.

pozri tiež

Poznámky

Odkazy

V ruštine

www.MachineLearning.ru - profesionálny wiki zdroj venovaný strojovému učeniu a dolovaniu údajov

V angličtine

COMPACT - Porovnávací balík pre hodnotenie klastrov. Bezplatný balík Matlab, 2006.
P. Berkhin, Prehľad techník ťažby dát z klastrov, Accrue Software, 2002.
Jain, Murty a Flynn: Klastrovanie údajov: Prehľad, ACM Comp. Surv., 1999.
pre ďalšiu prezentáciu hierarchických, k-means a fuzzy c-means pozri tento úvod do klastrovania . Má tiež vysvetlenie o zmesi Gaussovcov.
David dowe, Stránka Mixture Modeling- iné prepojenia modelov klastrovania a zmesí.
návod na klastrovanie
Online učebnica: Teória informácií, vyvodzovanie a algoritmy učenia sa od Davida J.C. MacKay obsahuje kapitoly o zhlukovaní k-means, soft k-means clustering a odvodeniach vrátane E-M algoritmu a variačný pohľad na E-M algoritmus.
"Samoorganizovaný gén", návod vysvetľujúci zhlukovanie prostredníctvom konkurenčného učenia a samoorganizujúcich sa máp.
kernlab - balík R pre strojové učenie založené na jadre (zahŕňa implementáciu spektrálneho klastrovania)
Výukový program - Výukový program so zavedením klastrových algoritmov (k-means, fuzzy-c-means, hierarchický, zmes gaussiánov) + niekoľko interaktívnych ukážok (java applety)
Softvér na dolovanie údajov – Softvér na dolovanie údajov často využíva techniky klastrovania.
Java Competitve Learning Application Sada neurónových sietí bez dozoru pre klastrovanie. Napísané v jazyku Java. Kompletné so všetkými zdrojovými kódmi.
Softvér strojového učenia – obsahuje aj veľa klastrovacieho softvéru.

V najrozmanitejších oblastiach činnosti sa často musíme zaoberať veľkým množstvom akýchkoľvek položiek, v súvislosti s ktorými musíme konať.

A celý tento objem si ani nedokážeme uvedomiť, nieto ešte pochopiť.

Aká je cesta von? No, samozrejme, „všetko položte na police“. V tomto prípade ľudová múdrosť získava presne definovanú vedeckú formuláciu.

Zhluková analýza je štúdium objektov ich kombinovaním do homogénnych skupín s podobnými vlastnosťami. Jeho metódy sú použiteľné doslova vo všetkých oblastiach: od medicíny po obchodovanie na Forexe, od poistenia áut až po archeológiu. A pre marketérov a personalistov je jednoducho nenahraditeľný.

Viac o tom v článku.

Čo je klaster

Klastrová analýza je navrhnutá tak, aby rozdelila množinu objektov do homogénnych skupín (klastrov alebo tried). Toto je úloha viacrozmernej klasifikácie údajov.

Existuje asi 100 rôznych klastrovacích algoritmov, avšak najčastejšie používané sú:

hierarchická zhluková analýza,
k-znamená zhlukovanie.

Kde sa používa klastrová analýza:

V marketingu ide o segmentáciu konkurentov a spotrebiteľov.
Vo vedení:
1. rozdelenie personálu do skupín s rôznou úrovňou motivácie,
2. klasifikácia dodávateľov,
3. identifikáciu podobných výrobných situácií, v ktorých dochádza k manželstvu.
V medicíne klasifikácia symptómov, pacientov, liekov.
V sociológii rozdelenie respondentov do homogénnych skupín.

V skutočnosti sa klastrová analýza osvedčila vo všetkých sférach ľudského života. Krása tejto metódy je v tom, že funguje aj vtedy, keď je málo údajov a nie sú splnené požiadavky na normálne rozdelenia. náhodné premenné a ďalšie požiadavky klasických metód štatistickej analýzy.

Vysvetlime podstatu klastrovej analýzy bez toho, aby sme sa uchýlili k striktnej terminológii.

Povedzme, že ste vykonali prieskum medzi zamestnancami a chcete zistiť, ako môžete najefektívnejšie riadiť svojich zamestnancov. To znamená, že chcete rozdeliť zamestnancov do skupín a pre každú z nich vybrať najefektívnejšie ovládacie páky. Zároveň by mali byť zrejmé rozdiely medzi skupinami a v rámci skupiny by si mali byť respondenti čo najviac podobní.

Na vyriešenie problému sa navrhuje použiť hierarchickú zhlukovú analýzu. V dôsledku toho dostaneme strom, pri pohľade na ktorý sa musíme rozhodnúť, do koľkých tried (zhlukov) chceme zamestnancov rozdeliť. Predpokladajme, že sa rozhodneme rozdeliť zamestnancov do troch skupín a potom na štúdium respondentov, ktorí spadali do každého zhluku, dostaneme tablet s nasledujúcim obsahom:

Vysvetlíme si, ako vzniká vyššie uvedená tabuľka. Prvý stĺpec obsahuje číslo klastra - skupiny, ktorej údaje sa odrážajú v riadku. Napríklad prvý zhluk je z 80 % mužský. 90 % z prvého klastra patrí do vekovej skupiny od 30 do 50 rokov a 12 % opýtaných sa domnieva, že benefity sú veľmi dôležité. A tak ďalej.

Pokúsme sa urobiť portréty respondentov každého klastra:

Prvou skupinou sú najmä muži v zrelom veku, zastávajúci vedúce pozície. Sociálny balíček (MED, LGOTI, TIME-free time) ich nezaujíma. Radšej dostávajú dobrý plat, ako pomoc od zamestnávateľa.
Skupina dva, naopak, preferuje sociálny balíček. Pozostáva najmä z „starých“ ľudí obsadzujúcich nízke pozície. Plat je pre nich určite dôležitý, ale sú tu aj iné priority.
Tretia skupina je najviac „mladá“. Na rozdiel od predchádzajúcich dvoch je zjavný záujem o vzdelávanie a možnosti profesionálneho rastu. Táto kategória zamestnancov má dobrú šancu čoskoro doplniť prvú skupinu.

Pri plánovaní kampane na zavedenie efektívnych metód personálneho manažmentu je teda zrejmé, že v našej situácii je možné zvýšiť sociálny balíček pre druhú skupinu napríklad na úkor miezd. Ak hovoríme o tom, ktorí špecialisti by mali byť poslaní na školenie, potom určite odporúčame venovať pozornosť tretej skupine.

Zdroj: "nickart.spb.ru"

Klastrová analýza je kľúčom k pochopeniu trhu

Klaster je cena aktíva v určitom časovom období, počas ktorého sa uskutočnili transakcie. Výsledný objem nákupu a predaja je označený číslom v rámci klastra. Pruh akéhokoľvek TF obsahuje spravidla niekoľko zhlukov. To vám umožní detailne vidieť objemy nákupov, predajov a ich zostatok v každom jednotlivom pruhu, pre každú cenovú hladinu.

Vytvorenie zhlukového grafu

Zmena ceny jedného aktíva so sebou nevyhnutne prináša reťazec cenových pohybov aj na iných nástrojoch. Vo väčšine prípadov k pochopeniu trendového pohybu dochádza už v momente, keď sa rýchlo rozvíja a vstup na trh pozdĺž trendu je spojený s pádom do korekčnej vlny.

Pre úspešné obchody je potrebné porozumieť aktuálnej situácii a vedieť predvídať budúce pohyby cien. Dá sa to naučiť analýzou klastrového grafu. Pomocou klastrovej analýzy môžete vidieť aktivitu účastníkov trhu aj v tej najmenšej cenovej lište.

Toto je najpresnejšia a najpodrobnejšia analýza, pretože ukazuje bodové rozdelenie objemov transakcií pre každú cenovú hladinu aktív. Trh neustále čelí záujmom predávajúcich a kupujúcich. A každý najmenší cenový pohyb (tick) je posunom ku kompromisu – cenovej hladine – ktorá v tento moment vyhovuje obom stranám.

Trh je ale dynamický, počet predávajúcich a kupujúcich sa neustále mení. Ak v určitom okamihu na trhu dominovali predajcovia, v ďalšom okamihu s najväčšou pravdepodobnosťou budú kupujúci. Počet uskutočnených transakcií v susedných cenových hladinách tiež nie je rovnaký.

A predsa sa najprv situácia na trhu premietne do celkového objemu transakcií a až potom do ceny. Ak vidíte akcie dominantných účastníkov trhu (predávajúcich alebo kupujúcich), môžete predpovedať samotný pohyb ceny.

Ak chcete úspešne použiť klastrovú analýzu, musíte najprv pochopiť, čo je klaster a delta:

Klaster je cenový pohyb, ktorý je rozdelený na úrovne, na ktorých sa uskutočnili transakcie so známymi objemami.
Delta ukazuje rozdiel medzi nákupom a predajom v každom klastri.

zhlukový graf

Každý klaster alebo skupina delt vám umožňuje zistiť, či v danom čase na trhu dominujú kupujúci alebo predávajúci. Celkovú deltu stačí vypočítať súčtom predajov a nákupov. Ak je delta záporná, potom je trh prepredaný, existujú nadbytočné predajné transakcie. Keď je delta pozitívna, na trhu jednoznačne dominujú kupujúci.

Samotná delta môže nadobudnúť normálnu alebo kritickú hodnotu. Hodnota delta objemu presahujúca normálnu hodnotu v klastri je zvýraznená červenou farbou. Ak je delta mierna, potom to charakterizuje plochý stav na trhu. O normálna hodnota delta na trhu, existuje trendový pohyb, ale kritická hodnota je vždy predzvesťou zvrátenia ceny.

Forexové obchodovanie s CA

Ak chcete získať maximálny zisk, musíte byť schopní určiť prechod delty z miernej úrovne na normálnu. V tomto prípade si skutočne môžete všimnúť úplný začiatok prechodu z plochého na trendový pohyb a byť schopný získať čo najväčší zisk.

Klastrový graf je viac vizuálny, umožňuje vám vidieť významné úrovne akumulácie a distribúcie objemov, budovať úrovne podpory a odporu.

To umožňuje obchodníkovi nájsť presný vstup do obchodu. Pomocou delty je možné posúdiť prevahu predajov alebo nákupov na trhu. Klastrová analýza vám umožňuje sledovať transakcie a sledovať ich objemy v rámci ľubovoľného TF. Toto je obzvlášť dôležité, keď sa blížite k významným úrovniam podpory alebo odporu. Klastrové úsudky sú kľúčom k pochopeniu trhu.

Zdroj: "orderflowtrading.ru"

Oblasti a vlastnosti aplikácie zhlukovej analýzy

Pojem klastrová analýza (prvýkrát zavedený Tryonom, 1939) v skutočnosti zahŕňa súbor rôznych klasifikačných algoritmov. Všeobecná otázka, na ktoré sa pýtajú výskumníci v mnohých oblastiach, je, ako usporiadať pozorované údaje do vizuálnych štruktúr, t.j. rozšíriť taxonómie.

Cieľom biológov je napríklad vlámať zvieratá rôzne druhy zmysluplne popísať rozdiely medzi nimi. Podľa moderného systému akceptovaného v biológii patrí človek medzi primáty, cicavce, amnioty, stavovce a zvieratá.

Všimnite si, že v tejto klasifikácii platí, že čím vyššia je úroveň agregácie, tým menšia je podobnosť medzi členmi v zodpovedajúcej triede. Človek má viac podobností s inými primátmi (t. j. ľudoopmi) ako so „vzdialenými“ členmi čeľade cicavcov (t. j. psami) atď.

Všimnite si, že predchádzajúca diskusia sa týka klastrovacích algoritmov, ale nespomína nič o testovaní štatistickej významnosti. Klastrová analýza v skutočnosti nie je ani tak bežnou štatistickou metódou, ako skôr „množinou“ rôznych algoritmov na „distribúciu objektov do zhlukov“.

Existuje názor, že na rozdiel od mnohých iných štatistických postupov sa metódy zhlukovej analýzy používajú vo väčšine prípadov, keď nemáte žiadne apriórne hypotézy o triedach, ale stále ste v popisnej fáze výskumu. Malo by sa chápať, že klastrová analýza určuje „najzmysluplnejšie rozhodnutie“.

Testovanie štatistickej významnosti tu preto nie je v skutočnosti použiteľné, dokonca ani v prípadoch, keď sú známe hladiny p (ako napríklad v metóde K-means).

Technika klastrovania sa používa v širokej škále oblastí. Hartigan (1975) poskytol vynikajúci prehľad mnohých publikovaných štúdií obsahujúcich výsledky získané metódami zhlukovej analýzy. Napríklad v oblasti medicíny vedie zoskupovanie chorôb, liečenie chorôb alebo symptómov chorôb k široko používaným taxonómiám.

V oblasti psychiatrie správna diagnóza zhluky symptómov, ako je paranoja, schizofrénia atď., sú rozhodujúce pre úspešnú liečbu. V archeológii sa výskumníci pomocou zhlukovej analýzy snažia stanoviť taxonómie kamenných nástrojov, pohrebných predmetov atď.

Sú známe rozšírené aplikácie klastrovej analýzy marketingový výskum. Vo všeobecnosti vždy, keď je potrebné zatriediť „hory“ informácií do skupín vhodných na ďalšie spracovanie, zhluková analýza sa ukazuje ako veľmi užitočná a efektívna.

Zhlukovanie stromov

Účelom asociačného algoritmu (zhlukovanie stromov) je spojiť objekty (napríklad zvieratá) do dostatočne veľkých zhlukov pomocou určitej miery podobnosti alebo vzdialenosti medzi objektmi. Typickým výsledkom takéhoto zhlukovania je hierarchický strom.

Zvážte horizontálny stromový diagram. Diagram začína každým objektom v triede (na ľavej strane diagramu). Teraz si predstavte, že postupne (veľmi malými krokmi) „oslabujete“ svoje kritérium pre to, aké predmety sú jedinečné a ktoré nie. Inými slovami, znížite prah súvisiaci s rozhodnutím spojiť dva alebo viac objektov do jedného klastra.

Výsledkom je, že spájate stále viac objektov a agregujete (spájate) stále viac a viac zhlukov čoraz odlišných prvkov. Nakoniec sa v poslednom kroku všetky objekty zlúčia.

V týchto grafoch predstavujú horizontálne osi združovaciu vzdialenosť (vo vertikálnych dendrogramoch zvislé osi predstavujú združovaciu vzdialenosť). Takže pre každý uzol v grafe (kde sa vytvorí nový zhluk) môžete vidieť veľkosť vzdialenosti, na ktorú sú zodpovedajúce prvky spojené do nového samostatného zhluku.

Keď majú údaje jasnú „štruktúru“ v zmysle zhlukov objektov, ktoré sú si navzájom podobné, potom sa táto štruktúra pravdepodobne prejaví v hierarchickom strome rôznymi vetvami. Výsledkom úspešnej analýzy metódou join je možnosť detegovať zhluky (vetvy) a interpretovať ich.

Miery vzdialenosti

Metóda zjednotenia alebo stromového zhlukovania sa používa pri vytváraní zhlukov rozdielov alebo vzdialenosti medzi objektmi. Tieto vzdialenosti môžu byť definované v jednorozmernom alebo viacrozmernom priestore. Napríklad, ak musíte v kaviarni zoskupiť druhy jedál, môžete vziať do úvahy počet kalórií v nich obsiahnutých, cenu, subjektívne hodnotenie chuti atď.

Najpriamejším spôsobom výpočtu vzdialenosti medzi objektmi vo viacrozmernom priestore je výpočet euklidovských vzdialeností. Ak máte dvoj- alebo trojrozmerný priestor, potom je táto miera skutočnou geometrickou vzdialenosťou medzi objektmi v priestore (ako keby boli vzdialenosti medzi objektmi merané páskou).

Algoritmus združovania sa však „nestará“ o to, či „poskytnuté“ vzdialenosti sú skutočné alebo nejaké iné odvodené miery vzdialenosti, čo je pre výskumníka zmysluplnejšie; a úlohou výskumníkov je nájsť správna metóda pre špecifické aplikácie.

Euklidovská vzdialenosť.

Zdá sa, že toto je najviac všeobecný typ vzdialenostiach. Je to jednoducho geometrická vzdialenosť vo viacrozmernom priestore a vypočíta sa takto:

Všimnite si, že euklidovská vzdialenosť (a jej štvorec) sa vypočítava z pôvodných údajov, nie zo štandardizovaných údajov. Toto je obvyklý spôsob výpočtu, ktorý má určité výhody (napríklad vzdialenosť medzi dvoma objektmi sa nemení, keď sa do analýzy zavedie nový objekt, čo sa môže ukázať ako odľahlá hodnota).

Vzdialenosti však môžu byť značne ovplyvnené rozdielmi medzi osami, z ktorých sa vzdialenosti počítajú.

Napríklad, ak je jedna z osí meraná v centimetroch a potom ju prevediete na milimetre (vynásobením hodnôt 10), potom bude konečná euklidovská vzdialenosť (alebo druhá mocnina euklidovskej vzdialenosti) vypočítaná zo súradníc sa dramaticky menia a v dôsledku toho sa výsledky zhlukovej analýzy môžu veľmi líšiť od predchádzajúcich.

Štvorec euklidovskej vzdialenosti.

Niekedy možno budete chcieť umocniť štandardnú euklidovskú vzdialenosť, aby ste dali väčšiu váhu vzdialenejším objektom. Táto vzdialenosť sa vypočíta takto:

Vzdialenosť medzi mestskými blokmi (Manhattan).

Táto vzdialenosť je jednoducho priemerom rozdielov medzi súradnicami. Vo väčšine prípadov táto miera vzdialenosti vedie k rovnakým výsledkom ako pre obvyklú Euklidovu vzdialenosť.

Všimnite si však, že pre toto opatrenie sa vplyv jednotlivých veľkých rozdielov (odľahlých hodnôt) znižuje (pretože nie sú na druhú mocninu). Vzdialenosť Manhattan sa vypočíta podľa vzorca:

Čebyševova vzdialenosť.

Táto vzdialenosť môže byť užitočná, keď chceme definovať dva objekty ako "odlišné", ak sa líšia v ktorejkoľvek jednej súradnici (akejkoľvek jednej dimenzii). Čebyševova vzdialenosť sa vypočíta podľa vzorca:

Výkonová vzdialenosť.
Niekedy je žiaduce postupne zvyšovať alebo znižovať hmotnosť týkajúcu sa rozmeru, pre ktorý sú zodpovedajúce predmety veľmi odlišné. To sa dá dosiahnuť pomocou mocninovej vzdialenosti. Výkonová vzdialenosť sa vypočíta podľa vzorca:

kde r a p sú užívateľom definované parametre.

Niekoľko príkladov výpočtov môže ukázať, ako toto opatrenie „funguje“:
- Parameter p je zodpovedný za postupné váženie rozdielov nad jednotlivými súradnicami.
- Parameter r je zodpovedný za progresívne váženie veľkých vzdialeností medzi objektmi.
- Ak sa oba parametre - r a p, rovnajú dvom, potom sa táto vzdialenosť zhoduje s euklidovskou vzdialenosťou.
Percento nesúhlasu.

Toto opatrenie sa používa, keď sú údaje kategorické. Táto vzdialenosť sa vypočíta podľa vzorca:

Asociačné alebo asociačné pravidlá

V prvom kroku, keď je každý objekt samostatným zhlukom, sú vzdialenosti medzi týmito objektmi určené vybranou mierou. Keď je však niekoľko objektov spojených dohromady, vyvstáva otázka, ako by sa mali určiť vzdialenosti medzi zhlukami?

Inými slovami, potrebujete pravidlo spojenia alebo prepojenia pre dva klastre. Sú tu rôzne možnosti: napríklad môžete spojiť dva zhluky, keď sú v dvoch zhlukoch ľubovoľné dva objekty bližší priateľ navzájom, než je zodpovedajúca komunikačná vzdialenosť.

Inými slovami, na určenie vzdialenosti medzi klastrami používate „pravidlo najbližšieho suseda“; táto metóda sa nazýva metóda jedného prepojenia. Toto pravidlo vytvára „vláknité“ zhluky, t.j. klastre „spojené“ iba jednotlivými prvkami, ktoré sú náhodou bližšie k sebe ako ostatné.

Prípadne môžete použiť susedov v zhlukoch, ktoré sú od seba najďalej zo všetkých ostatných párov funkcií. Táto metóda sa nazýva metóda úplného prepojenia. Existuje aj mnoho ďalších metód spájania klastrov, podobných tým, o ktorých sa diskutovalo.

Jednoduché pripojenie (metóda najbližšieho suseda).

Ako je opísané vyššie, v tejto metóde je vzdialenosť medzi dvoma zhlukami určená vzdialenosťou medzi dvoma najbližšími objektmi (najbližšími susedmi) v rôznych zhlukoch.

Toto pravidlo musí v istom zmysle spájať objekty, aby vytvorili zhluky, a výsledné zhluky majú tendenciu byť reprezentované dlhými „reťazcami“.

Plné pripojenie (metóda najvzdialenejších susedov).

V tejto metóde sú vzdialenosti medzi zhlukami definované ako najväčšia vzdialenosť medzi akýmikoľvek dvoma objektmi v rôznych zhlukoch (t. j. „najvzdialenejší susedia“).

Táto metóda zvyčajne funguje veľmi dobre, keď predmety skutočne pochádzajú z naozaj rôznych „hájov“.

Ak sú zhluky nejakým spôsobom pretiahnuté alebo ich prirodzený typ je „reťazový“, potom je táto metóda nevhodná.

Nevážený párový priemer.

V tejto metóde sa vzdialenosť medzi dvoma rôznymi zhlukami vypočíta ako priemerná vzdialenosť medzi všetkými pármi objektov v nich. Metóda je účinná, keď objekty skutočne tvoria rôzne „háje“, ale rovnako dobre funguje aj v prípadoch rozšírených (typu „reťazca“) zhlukov.

Všimnite si, že vo svojej knihe Sneath a Sokal (1973) zaviedli skratku UPGMA na označenie tejto metódy ako metódy nevážených párových skupín s použitím aritmetických priemerov.

Vážený párový priemer.

Metóda je identická s metódou neváženého párového priemeru s tým rozdielom, že ako váhový faktor sa pri výpočtoch používa veľkosť príslušných zhlukov (tj počet objektov, ktoré obsahujú). Preto by sa navrhovaná metóda mala použiť, keď sa predpokladajú nerovnaké veľkosti zhlukov.

Sneath a Sokal (1973) zavádzajú skratku WPGMA na označenie tejto metódy ako metódy vážených párových skupín s použitím aritmetických priemerov.

Metóda neváženého ťažiska.

V tejto metóde je vzdialenosť medzi dvoma klastrami definovaná ako vzdialenosť medzi ich ťažiskami.

Sneath a Sokal (1973) používajú skratku UPGMC na označenie tejto metódy ako metódy neváženej párovej skupiny s použitím priemeru ťažiska.

Metóda váženého ťažiska (medián).

Táto metóda je identická s predchádzajúcou, s tým rozdielom, že pri výpočtoch sa používajú váhy, ktoré zohľadňujú rozdiel medzi veľkosťami zhlukov (t. j. počtom objektov v nich).

Preto, ak existujú (alebo existuje podozrenie) na významné rozdiely vo veľkostiach klastrov, táto metóda je vhodnejšia ako predchádzajúca.

Sneath a Sokal (1973) použili skratku WPGMC, aby ju označili ako metódu vážených párových skupín s použitím ťažiskového priemeru.

Wardova metóda.

Táto metóda sa líši od všetkých ostatných metód, pretože používa metódy ANOVA na odhad vzdialeností medzi klastrami. Metóda minimalizuje súčet štvorcov (SS) pre akékoľvek dva (hypotetické) zhluky, ktoré môžu byť vytvorené v každom kroku.

Podrobnosti možno nájsť vo Wardovi (1963). Vo všeobecnosti sa metóda javí ako veľmi efektívna, ale má tendenciu vytvárať malé zhluky.

obojsmerná únia

Skôr sa o tejto metóde hovorilo v súvislosti s „objektmi“, ktoré by mali byť zoskupené. Vo všetkých ostatných typoch analýzy je otázka, ktorá je pre výskumníka zaujímavá, zvyčajne vyjadrená z hľadiska pozorovaní alebo premenných. Ukazuje sa, že zhlukovanie, či už pozorovaní alebo premenných, môže viesť k celkom zaujímavým výsledkom.

Predstavte si napríklad, že lekársky výskumník zbiera údaje o rôzne vlastnosti(premenné) stavy pacientov (pozorovania) trpiacich srdcovým ochorením. Výskumník môže chcieť zoskupiť pozorovania (pacientov), aby identifikoval zoskupenia pacientov s podobnými symptómami.

Zároveň si výskumník môže želať zoskupiť premenné, aby identifikoval zhluky premenných, ktoré sú spojené s podobným fyzickým stavom. Po tejto diskusii o tom, či zhlukovať pozorovania alebo premenné, by sme si mohli položiť otázku, prečo nezhlukovať oboma smermi?

Modul Cluster Analysis obsahuje efektívny obojsmerný postup spojenia, ktorý to umožňuje. Obojsmerné združovanie sa však používa (pomerne zriedkavo) za okolností, keď sa očakáva, že pozorovania aj premenné prispejú súčasne k objaveniu zmysluplných zhlukov.

Ak sa teda vrátime k predchádzajúcemu príkladu, môžeme predpokladať, že lekársky výskumník potrebuje identifikovať skupiny pacientov, ktoré sú podobné vo vzťahu k určitým skupinám charakteristík fyzického stavu.

Ťažkosti pri interpretácii získaných výsledkov vyplývajú zo skutočnosti, že podobnosti medzi rôznymi klastrami môžu pochádzať (alebo byť príčinou) určitého rozdielu v podskupinách premenných. Preto sú výsledné zhluky vo svojej podstate heterogénne.

Možno sa to na prvý pohľad zdá trochu zahmlené; v porovnaní s inými opísanými metódami klastrovej analýzy je obojsmerné združovanie pravdepodobne najmenej bežne používanou metódou. Niektorí výskumníci sa však domnievajú, že ponúka silný nástroj na prieskumnú analýzu údajov (viac informácií nájdete v Hartiganovom opise tejto metódy (Hartigan, 1975)).

K znamená metóda

Táto metóda klastrovania sa výrazne líši od aglomeračných metód, ako je Union (stromové zhlukovanie) a Two-Way Union. Predpokladajme, že už máte hypotézy o počte zhlukov (podľa pozorovania alebo premennej).

Systému môžete prikázať, aby vytvoril presne tri zhluky tak, aby boli čo najrôznejšie. Toto je presne ten typ problému, ktorý rieši algoritmus K-Means. Vo všeobecnosti metóda K-means vytvára presne K odlišných zhlukov vzdialených od seba čo najďalej.

V príklade fyzického stavu môže mať lekársky výskumník „tušenie“ zo svojej klinickej skúsenosti, že jeho pacienti vo všeobecnosti spadajú do troch rôznych kategórií. Ďalej by mohol chcieť vedieť, či je možné jeho intuíciu numericky overiť, t.j. klastrová analýza K znamená skutočne tri zhluky pacientov, ako sa očakávalo?

Ak áno, potom prostriedky rôznych meraní fyzikálnych parametrov pre každý klaster by poskytli kvantitatívny spôsob reprezentácie hypotéz výskumníka (napr. pacienti v klastri 1 majú vysoký parameter 1, nižší parameter 2 atď.).

Z výpočtového hľadiska si túto metódu môžete predstaviť ako analýzu rozptylu „spätne“.

Program začína s K náhodne vybranými klastrami a potom mení príslušnosť objektov k nim, aby:

minimalizovať variabilitu v rámci klastrov,
maximalizovať variabilitu medzi klastrami.

Táto metóda je podobná reverznej analýze rozptylu (ANOVA) v tom, že test významnosti v ANOVA porovnáva variabilitu medzi skupinami oproti variabilite v rámci skupiny pri testovaní hypotézy, že priemery skupín sa navzájom líšia.

Pri zhlukovaní K-means program presúva objekty (t. j. pozorovania) z jednej skupiny (klastra) do druhej, aby pri vykonávaní analýzy rozptylu (ANOVA) získal najvýznamnejší výsledok. Po získaní výsledkov klastrovej analýzy K-priemerov sa zvyčajne dajú vypočítať priemery pre každý klaster pre každú dimenziu, aby sa posúdilo, ako sa klastre navzájom líšia.

V ideálnom prípade by ste mali získať veľmi odlišné prostriedky pre väčšinu, ak nie všetky, meraní použitých v analýze. Hodnoty F-štatistiky získané pre každú dimenziu sú ďalším indikátorom toho, ako dobre príslušná dimenzia rozlišuje medzi klastrami.

Zdroj: "biometria.tomsk.ru"

Klasifikácia objektov podľa ich vlastností

Zhluková analýza (zhluková analýza) - súbor viacrozmerných štatistických metód na klasifikáciu objektov podľa ich charakteristík, rozdelenie súboru objektov do homogénnych skupín, ktoré sú si blízke z hľadiska kritérií definovania, výber objektov určitej skupiny.

Klaster je skupina objektov identifikovaných ako výsledok zhlukovej analýzy na základe danej miery podobnosti alebo rozdielu medzi objektmi. Objektom sú konkrétne predmety štúdia, ktoré je potrebné klasifikovať. Objekty v klasifikácii sú spravidla pozorovania. Napríklad spotrebitelia produktov, krajín alebo regiónov, produktov atď.

Aj keď je možné vykonať zhlukovú analýzu podľa premenných. Klasifikácia objektov vo viacrozmernej zhlukovej analýze prebieha podľa viacerých kritérií súčasne, pričom môže ísť o kvantitatívne aj kategorické premenné v závislosti od metódy zhlukovej analýzy. Hlavným cieľom zhlukovej analýzy je teda nájsť vo vzorke skupiny podobných objektov.

Súbor viacrozmerných štatistických metód zhlukovej analýzy možno rozdeliť na hierarchické metódy (aglomeratívne a deliace) a nehierarchické (metóda k-means, dvojstupňová zhluková analýza).

Neexistuje však všeobecne akceptovaná klasifikácia metód a metódy klastrovej analýzy niekedy zahŕňajú aj metódy na vytváranie rozhodovacích stromov, neurálne siete, diskriminačná analýza, logistická regresia.

Rozsah klastrovej analýzy je vzhľadom na jej všestrannosť veľmi široký. Zhluková analýza sa používa v ekonómii, marketingu, archeológii, medicíne, psychológii, chémii, biológii, verejnej správe, filológii, antropológii, sociológii a ďalších oblastiach.

Tu je niekoľko príkladov použitia klastrovej analýzy:

medicína - klasifikácia chorôb, ich symptómy, spôsoby liečby, klasifikácia skupín pacientov;
marketing - úlohy optimalizácie produktového radu spoločnosti, segmentácia trhu podľa skupín tovarov alebo spotrebiteľov, identifikácia potenciálneho spotrebiteľa;
sociológia - rozdelenie respondentov do homogénnych skupín;
psychiatria – správna diagnostika symptómových skupín je rozhodujúca pre úspešnú terapiu;
biológia - klasifikácia organizmov podľa skupín;
ekonomika - klasifikácia subjektov Ruskej federácie podľa investičnej atraktivity.

Zdroj: "statmethods.ru"

Všeobecné informácie o klastrovej analýze

Klastrová analýza zahŕňa súbor rôznych klasifikačných algoritmov. Častou otázkou, ktorú si výskumníci v mnohých oblastiach kladú, je, ako usporiadať pozorované údaje do vizuálnych štruktúr.

Cieľom biológov je napríklad rozdeliť zvieratá na rôzne druhy, aby zmysluplne popísali rozdiely medzi nimi.

Úlohou zhlukovej analýzy je rozdeliť počiatočnú množinu objektov do skupín podobných, blízkych objektov. Tieto skupiny sa nazývajú klastre.

Inými slovami, zhluková analýza je jedným zo spôsobov klasifikácie objektov podľa ich charakteristík. Je žiaduce, aby výsledky klasifikácie mali zmysluplnú interpretáciu.

Výsledky získané metódami zhlukovej analýzy sa používajú v rôznych oblastiach:

V marketingu je to segmentácia konkurentov a spotrebiteľov.
V psychiatrii je pre úspešnú terapiu rozhodujúca správna diagnostika symptómov ako paranoja, schizofrénia atď.
V manažmente je dôležitá klasifikácia dodávateľov, identifikácia podobných výrobných situácií, v ktorých dochádza k manželstvu.
V sociológii rozdelenie respondentov do homogénnych skupín.
Pri portfóliovom investovaní je dôležité zoskupovať cenné papiere podľa ich podobnosti v trende výnosu s cieľom zostaviť na základe získaných informácií o akciovom trhu optimálne investičné portfólio, ktoré umožňuje maximalizovať návratnosť investícií pri danom stupni rizika. .

V skutočnosti sa klastrová analýza osvedčila vo všetkých sférach ľudského života. Vo všeobecnosti vždy, keď je potrebné klasifikovať veľké množstvo informácií tohto druhu a prezentovať ich vo forme vhodnej na ďalšie spracovanie, zhluková analýza sa ukazuje ako veľmi užitočná a efektívna.

Klastrová analýza umožňuje zvážiť pomerne veľké množstvo informácií a značne komprimovať veľké polia sociálno-ekonomických informácií, vďaka čomu sú kompaktné a vizuálne.

Zhluková analýza má veľký význam vo vzťahu k súborom charakterizujúcich časové rady ekonomický vývoj(napríklad všeobecná ekonomická a komoditná konjunktúra).

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

Výhody a nevýhody

Zhluková analýza umožňuje objektívnu klasifikáciu akýchkoľvek objektov, ktoré sa vyznačujú množstvom znakov. Z toho vyplýva množstvo výhod:

Výsledné zhluky môžu byť interpretované, to znamená, že opisujú, aké skupiny skutočne existujú.
Jednotlivé zhluky môžu byť vyradené. To je užitočné v prípadoch, keď sa v súbore údajov vyskytli určité chyby, v dôsledku ktorých sa hodnoty ukazovateľov pre jednotlivé objekty výrazne líšia. Pri aplikácii zhlukovej analýzy takéto objekty spadajú do samostatného zhluku.
Pre ďalšiu analýzu je možné vybrať len tie zhluky, ktoré majú charakteristiky záujmu.

Ako každá iná metóda, aj klastrová analýza má určité nevýhody a obmedzenia. Konkrétne:

zloženie a počet klastrov závisí od zvolených kritérií rozdelenia,
pri zmenšení pôvodného dátového poľa na kompaktnejšiu formu môže dôjsť k určitým deformáciám,
jednotlivé vlastnosti jednotlivých objektov sa môžu stratiť v dôsledku ich nahradenia charakteristikami zovšeobecnených hodnôt parametrov klastra.

Metódy

V súčasnosti je známych viac ako sto rôznych zhlukových algoritmov. Ich rôznorodosť je vysvetlená nielen rôznymi výpočtovými metódami, ale aj rôznymi konceptmi, ktoré sú základom klastrovania. Odporúčania pre výber jednej alebo druhej metódy klastrovania je možné poskytnúť len všeobecne a hlavným kritériom výberu je praktická užitočnosť výsledku.

Balík Statistica implementuje nasledujúce metódy klastrovania:

Hierarchické algoritmy - stromové zhlukovanie. Hierarchické algoritmy sú založené na myšlienke sekvenčného zoskupovania. V počiatočnom kroku sa každý objekt považuje za samostatný zhluk. V ďalšom kroku sa niektoré z klastrov, ktoré sú najbližšie k sebe, spoja do samostatného klastra.
Metóda K-means. Táto metóda je najčastejšie používaná. Patrí do skupiny takzvaných referenčných metód zhlukovej analýzy. Počet klastrov K nastavuje užívateľ.
Obojstranná asociácia. Pri použití tejto metódy sa zhlukovanie vykonáva súčasne podľa premenných (stĺpcov) aj výsledkov pozorovania (riadkov).

Procedúra obojsmerného spojenia sa vykonáva vtedy, keď možno očakávať, že simultánne zoskupovanie premenných a pozorovaní poskytne zmysluplné výsledky.

Výsledky postupu sú deskriptívna štatistika podľa premenných a prípadov, ako aj dvojrozmerný farebný graf, na ktorom sú hodnoty údajov farebne odlíšené. Rozložením farieb môžete získať predstavu o homogénnych skupinách.

Normalizácia premenných

Rozdelenie počiatočnej množiny objektov do zhlukov je spojené s výpočtom vzdialeností medzi objektmi a výberom objektov, pričom vzdialenosť medzi nimi je najmenšia zo všetkých možných. Najčastejšie používaná je nám všetkým známa euklidovská (geometrická) vzdialenosť. Táto metrika zodpovedá intuitívnym predstavám o blízkosti objektov v priestore (akoby sa vzdialenosti medzi objektmi merali pomocou páskového meradla).

Ale pre danú metriku môže byť vzdialenosť medzi objektmi silne ovplyvnená zmenami mierok (jednotiek merania). Ak sa napríklad jeden z prvkov meria v milimetroch a potom sa jeho hodnota prevedie na centimetre, euklidovská vzdialenosť medzi objektmi sa dramaticky zmení. To povedie k tomu, že výsledky zhlukovej analýzy sa môžu výrazne líšiť od predchádzajúcich.

Ak sa premenné merajú v rôznych meracích jednotkách, potom je potrebná ich predbežná normalizácia, teda transformácia počiatočných údajov, ktorá ich prevedie na bezrozmerné veličiny.

Normalizácia silne deformuje geometriu pôvodného priestoru, čo môže zmeniť výsledky zhlukovania. V balíku Statistica je každá premenná x normalizovaná podľa vzorca:

Ak to chcete urobiť, kliknite pravým tlačidlom myši na názov premennej a z ponuky, ktorá sa otvorí, vyberte postupnosť príkazov: Vyplniť/ Štandardizovať blok/ Štandardizovať stĺpce. Hodnoty normalizovanej premennej sa budú rovnať nule a odchýlky sa budú rovnať jednej.

Metóda K-means v programe Statistica

Metóda K-means rozdeľuje množinu objektov na daný počet K rôznych zhlukov umiestnených v najväčšej možnej vzdialenosti od seba. Po získaní výsledkov klastrovej analýzy K-priemerov sa zvyčajne dajú vypočítať priemery pre každý klaster pre každú dimenziu, aby sa posúdilo, ako sa klastre navzájom líšia.

V ideálnom prípade by ste mali získať veľmi odlišné prostriedky pre väčšinu meraní používaných v analýze. Hodnoty F-štatistiky získané pre každú dimenziu sú ďalším indikátorom toho, ako dobre príslušná dimenzia rozlišuje medzi klastrami.

Ako príklad uveďme výsledky prieskumu medzi 17 zamestnancami podniku o spokojnosti s ukazovateľmi kvality kariéry. Tabuľka obsahuje odpovede na otázky dotazníka na desaťbodovej škále (1 je minimálne skóre, 10 je maximum).

Názvy premenných zodpovedajú odpovediam na nasledujúce otázky:

SLT - kombinácia osobných cieľov a cieľov organizácie;
OSO - zmysel pre spravodlivosť v mzdách;
TBD - územná blízkosť domu;
PEW - pocit ekonomického blahobytu;
ČR - kariérny rast;
ZhSR - túžba zmeniť zamestnanie;
OSB dosky sú pocitom sociálnej pohody.

Pomocou týchto údajov je potrebné rozdeliť zamestnancov do skupín a pre každú z nich vybrať najefektívnejšie ovládacie páky. Zároveň by mali byť zrejmé rozdiely medzi skupinami a v rámci skupiny by si mali byť respondenti čo najviac podobní.

K dnešnému dňu väčšina sociologických prieskumov dáva iba percento hlasov: zvažuje sa hlavný počet kladných odpovedí alebo percento nespokojných, ale táto otázka sa systematicky nezohľadňuje. Prieskum najčastejšie neukazuje trendy v situácii.

Postupy klastrovej analýzy možno použiť na identifikáciu niektorých skutočne existujúcich vzťahov prvkov na základe údajov z prieskumu a na tomto základe vytvoriť ich typológiu. Prítomnosť akýchkoľvek apriórnych hypotéz sociológa počas prevádzky postupov klastrovej analýzy nie je nevyhnutná podmienka.

V programe Statistica sa klastrová analýza vykonáva nasledovne.

Vytvorte dátový súbor.
Vyberte modul Štatistika/Multivariable Exploratory Techniques/Cluster Analysis. Kliknite na tlačidlo OK, v dôsledku čoho sa zobrazí dialógové okno:
V zobrazenom okne vyberte metódu zoskupovania K-means a kliknite na tlačidlo OK.
V zobrazenom dialógovom okne musíte nastaviť nasledujúce nastavenia:
- Vyberte premenné pomocou tlačidla Premenné.
- Vyberte objekty zhlukovania: môžu to byť premenné - stĺpce (stĺpce premenných) alebo pozorovania - riadky (prípady (riadky)). Najprv zhlukujme riadky (Cases(rows)).
- Vyberte počet klastrov.
  Túto voľbu robí užívateľ na základe vlastných predpokladov o počte skupín podobných objektov.
  Pri výbere počtu klastrov sa riaďte nasledujúcimi informáciami:
  1. Počet zhlukov by podľa možnosti nemal byť príliš veľký.
  2. Vzdialenosť, v ktorej boli objekty daného zhluku spojené, by mala byť, ak je to možné, oveľa menšia ako vzdialenosť, v ktorej sa k tomuto zhluku pripája niečo iné.
  Pri výbere počtu zhlukov sa najčastejšie vyskytuje niekoľko správnych riešení súčasne. Zaujíma nás napríklad, ako odpovede na otázky dotazníka korelujú s radovými zamestnancami a vedením podniku. Preto zvolíme K=2. Pre ďalšiu segmentáciu môžete zvýšiť počet klastrov.
- Ďalej je potrebné vybrať počiatočné rozdelenie objektov do zhlukov (Initial cluster centers). Balík Statistica ponúka:
  1. vyberte pozorovania s maximálnou vzdialenosťou medzi stredmi zhlukov;
  2. triediť vzdialenosti a vyberať pozorovania v pravidelných intervaloch (predvolené nastavenie);
  3. vezmite prvé pozorovacie centrá a pripevnite na ne zvyšok predmetov.
  Pre naše účely je vhodná prvá možnosť.

Mnoho klastrovacích algoritmov často „vnucuje“ štruktúru, ktorá nie je vlastná údajom a dezorientuje výskumníka. Preto je mimoriadne potrebné použiť niekoľko algoritmov klastrovej analýzy a vyvodiť závery na základe všeobecného hodnotenia výsledkov algoritmov.

Výsledky analýzy je možné zobraziť v dialógovom okne, ktoré sa zobrazí:

Ak vyberiete kartu Graf priemerov, vykreslí sa graf súradníc stredov klastrov:

Každá prerušovaná čiara na tomto grafe zodpovedá jednému zo zhlukov:

Každé delenie horizontálnej osi grafu zodpovedá jednej z premenných zahrnutých do analýzy.
Vertikálna os zodpovedá priemerným hodnotám premenných pre objekty zahrnuté v každom z klastrov.

Možno poznamenať, že takmer vo všetkých otázkach existujú značné rozdiely v postoji týchto dvoch skupín ľudí k služobnej kariére. Len v jednom čísle je úplná jednomyseľnosť – v zmysle sociálneho blahobytu (OSB), respektíve jeho nedostatku (2,5 bodu z 10).

Dá sa predpokladať, že:

klaster 1 zobrazuje pracovníkov,
klaster 2 - vedenie:
- Manažéri sú viac spokojní s kariérnym rozvojom (CR), kombináciou osobných cieľov a organizačných cieľov (SOL).
- Majú vyšší pocit ekonomického blahobytu (SEW) a zmysel pre rovnosť odmeňovania (SWA).
- Sú menej znepokojení blízkosťou domova ako pracovníci, pravdepodobne kvôli menším problémom s dopravou.
- Manažéri tiež menej túžia po zmene zamestnania (JSR).

Napriek tomu, že pracovníci sú rozdelení do dvoch kategórií, na väčšinu otázok dávajú relatívne rovnaké odpovede. Inými slovami, ak niečo nevyhovuje všeobecnej skupine zamestnancov, nevyhovuje to ani vrcholovému manažmentu a naopak.

Harmonizácia grafov nám umožňuje dospieť k záveru, že blaho jednej skupiny sa odráža v pohode druhej.

Zhluk 1 nie je spokojný s územnou blízkosťou domu. Táto skupina je hlavnou časťou pracovníkov, ktorí do podniku prichádzajú najmä z rôznych častí mesta. Preto je možné ponúknuť vrcholovému manažmentu, aby pridelil časť zisku na výstavbu bytov pre zamestnancov podniku.

Existujú výrazné rozdiely v postoji dvoch skupín ľudí k služobnej kariére:

Tí zamestnanci, ktorí sú spokojní s kariérnym rastom, ktorí majú vysokú zhodu osobných cieľov a cieľov organizácie, nemajú chuť meniť zamestnanie a pociťujú spokojnosť s výsledkami svojej práce.
Naopak, zamestnanci, ktorí chcú zmeniť prácu a sú nespokojní s výsledkami svojej práce, nie sú spokojní s uvedenými ukazovateľmi.

Vyšší manažment by mal venovať osobitnú pozornosť súčasnej situácii.

Výsledky analýzy rozptylu pre každý atribút sa zobrazia po stlačení tlačidla Analýza rozptylu:

Výkon:

súčty štvorcov odchýlky objektu od stredov klastra (SS Within),
súčty štvorcových odchýlok medzi stredmi klastrov (SS Between),
F-štatistické hodnoty,
hladiny významnosti p.

V našom príklade sú hladiny významnosti pre dve premenné pomerne veľké, čo sa vysvetľuje malým počtom pozorovaní. V plnej verzii štúdie, ktorú možno nájsť v príspevku, sú hypotézy o rovnosti priemerov pre centrá klastrov zamietnuté na hladinách významnosti menších ako 0,01.

Tlačidlo Uložiť klasifikácie a vzdialenosti zobrazuje počet objektov zahrnutých v každom klastri a vzdialenosti objektov od stredu každého klastra.

Zloženie každého zhluku a vzdialenosť objektov od stredu

Tabuľka zobrazuje čísla prípadov (CASE_NO), ktoré tvoria klastre s číslami CLUSTER, a vzdialenosti od stredu každého klastra (DISTANCE).

Informácie o objektoch patriacich do klastrov možno zapísať do súboru a použiť pri ďalšej analýze. V tomto príklade porovnanie výsledkov získaných s dotazníkmi ukázalo, že klaster 1 pozostáva hlavne z radových pracovníkov a klaster 2 - z manažérov.

Možno teda poznamenať, že pri spracovaní výsledkov prieskumu sa zhluková analýza ukázala ako výkonná metóda, ktorá umožňuje vyvodiť závery, ku ktorým nemožno dospieť zostavením histogramu priemerov alebo výpočtom percenta tých, ktorí sú spokojní s rôznymi ukazovateľmi kvalitu pracovného života.

Stromové zhlukovanie je príkladom hierarchického algoritmu, ktorého princípom je postupne zhlukovať do zhluku najskôr najbližšie a potom stále vzdialenejšie prvky od seba. Väčšina týchto algoritmov vychádza z matice podobnosti (vzdialeností) a každý jednotlivý prvok sa najskôr považuje za samostatný zhluk.

Po načítaní modulu analýzy klastrov a výbere položky Joining (klastrovanie stromov) môžete zmeniť nasledujúce parametre v okne zadávania parametrov klastrovania:

Počiatočné údaje (vstup). Môžu byť vo forme matice študovaných údajov (Raw data) a vo forme matice vzdialeností (Distance matrix).
Zhlukovanie (Cluster) pozorovaní (Cases (raw)) alebo premenných (Variable (stĺpce)), ktoré popisujú stav objektu.
Miery vzdialenosti. Tu si môžete vybrať z nasledujúcich opatrení:
- euklidovské vzdialenosti,
- Štvorcové euklidovské vzdialenosti,
- vzdialenosť mestských blokov (vzdialenosť Manhattan, vzdialenosť mestských blokov (Manhattan), metrika vzdialenosti Čebyčev,
- výkonová vzdialenosť (Power...;),
- Percento nesúhlasu.
Metóda klastrovania (pravidlo amalgamácie (prepojenia).
K dispozícii sú nasledujúce možnosti:
- jediný odkaz (metóda najbližšieho suseda) (Single Linkage),
- úplný odkaz (metóda najvzdialenejších susedov) (Complete Linkage),
- nevážený priemer párovej skupiny,
- vážený priemer párovej skupiny,
- metóda neváženého ťažiska (nevážené ťažisko párovej skupiny),
- metóda váženého ťažiska (medián) (ťažisko skupiny vážených párov (medián)),
- Wardova metóda.

V dôsledku zhlukovania sa vytvára horizontálny alebo vertikálny dendrogram - graf, na ktorom sa pri postupnom kombinovaní určujú vzdialenosti medzi objektmi a zhlukami.

Stromová štruktúra grafu umožňuje definovať zhluky v závislosti od zvoleného prahu – danej vzdialenosti medzi zhlukmi.

Okrem toho sa zobrazí matica vzdialeností medzi pôvodnými objektmi (Distance matrix); priemer a štandardné odchýlky pre každý zdrojový objekt (Distiptive statistics). Pre uvažovaný príklad vykonáme zhlukovú analýzu premenných s predvolenými nastaveniami. Výsledný dendrogram je znázornený na obrázku:

Zvislá os dendrogramu znázorňuje vzdialenosti medzi objektmi a medzi objektmi a zhlukami. Takže vzdialenosť medzi premennými SEB a OSD sa rovná piatim. Tieto premenné sú v prvom kroku spojené do jedného klastra.

Horizontálne segmenty dendrogramu sú nakreslené na úrovniach zodpovedajúcich prahovým vzdialenostiam vybraným pre daný krok zhlukovania.

Z grafu je vidieť, že otázka „chuť zmeniť zamestnanie“ (JSR) tvorí samostatný zhluk. Vo všeobecnosti platí, že túžba vysypať sa kdekoľvek navštevuje každého rovnako. Ďalej, samostatným klastrom je otázka územnej blízkosti domova (LHB).

Z hľadiska dôležitosti je na druhom mieste, čo potvrdzuje záver o potrebe bytovej výstavby, urobený podľa výsledkov štúdie metódou K-means.

Pocity ekonomického blahobytu (PEW) a mzdovej rovnosti (PWF) sa spájajú – to je blok ekonomických otázok. Kariéra(CR) a kombinácia osobných cieľov a organizačných cieľov (SOLs).

Iné metódy zhlukovania, ako aj výber iných typov vzdialeností nevedú k výraznej zmene dendrogramu.

výsledky

Zhluková analýza je výkonný nástroj na prieskumnú analýzu údajov a štatistický výskum v akejkoľvek oblasti.
Program Statistica implementuje hierarchické aj štrukturálne metódy zhlukovej analýzy. Výhody tohto štatistického balíka spočívajú v ich grafických schopnostiach. Poskytnuté sú dvojrozmerné a trojrozmerné grafické znázornenia získaných zhlukov v priestore študovaných premenných, ako aj výsledky hierarchického postupu pri zoskupovaní objektov.
Je potrebné aplikovať niekoľko algoritmov klastrovej analýzy a vyvodiť závery na základe všeobecného hodnotenia výsledkov algoritmov.
Klastrovú analýzu možno považovať za úspešnú, ak sa vykonáva rôznymi spôsobmi, výsledky sa porovnávajú a nájdu sa spoločné vzorce a nájdu sa stabilné zhluky bez ohľadu na metódu zhlukovania.
Klastrová analýza vám umožňuje identifikovať problémové situácie a načrtnúť spôsoby ich riešenia. Preto možno túto metódu neparametrickej štatistiky považovať za integrálnu súčasť systémovej analýzy.

Typy vstupu

Orientačný popis predmetov. Každý objekt je opísaný súborom jeho charakteristík, tzv znamenia. Funkcie môžu byť číselné alebo nečíselné.
Matica vzdialenosti medzi objektmi. Každý objekt je opísaný vzdialenosťami od všetkých ostatných objektov v tréningovej sade.

Matica vzdialenosti možno vypočítať z matice opisov vlastností objektov nekonečným množstvom spôsobov, v závislosti od toho, ako zaviesť funkciu vzdialenosti (metriku) medzi opismi prvkov. Euklidovská metrika sa často používa, ale táto voľba je vo väčšine prípadov heuristika a je spôsobená len úvahami o vhodnosti.

Inverzný problém – obnovenie opisov vlastností pomocou matice párových vzdialeností medzi objektmi – vo všeobecnom prípade nemá riešenie a približné riešenie nie je jedinečné a môže mať významnú chybu. Tento problém je riešený metódami viacrozmerného škálovania.

Teda formulácia problému zhlukovania podľa matica vzdialenosti je všeobecnejší. Na druhej strane, v prítomnosti popisov funkcií je často možné postaviť viac efektívne metódy zhlukovanie.

Ciele klastrovania

Pochopenie údajov identifikáciou štruktúry klastra. Rozdelenie vzorky do skupín podobných objektov umožňuje zjednodušiť ďalšie spracovanie údajov a rozhodovanie aplikáciou vlastnej metódy analýzy na každý zhluk (stratégia „rozdeľ a panuj“).
Kompresia údajov. Ak je počiatočná vzorka príliš veľká, môže sa zredukovať, pričom zostane jeden z najtypickejších predstaviteľov z každého klastra.
Detekcia noviniek. Vyberajú sa atypické objekty, ktoré nie je možné pripojiť k žiadnemu z klastrov.

V prvom prípade sa snažia počet zhlukov zmenšiť. V druhom prípade je dôležitejšie zabezpečiť vysoký (alebo pevný) stupeň podobnosti objektov v rámci každého zhluku, pričom zhlukov môže byť ľubovoľný počet. V treťom prípade je najväčší záujem o jednotlivé objekty, ktoré nezapadajú do žiadneho zo zhlukov.

Výsledkom taxonómie je stromová hierarchická štruktúra. Okrem toho je každý objekt charakterizovaný vymenovaním všetkých zhlukov, do ktorých patrí, zvyčajne od veľkých po malé. Vizuálne je taxonómia znázornená ako graf nazývaný dendrogram.

Klasickým príkladom taxonómie založenej na podobnosti je binomická nomenklatúra živých bytostí navrhol Carl Linné v polovici 18. storočia. Podobné systematizácie sú vybudované v mnohých oblastiach poznania s cieľom zefektívniť informácie o vo veľkom počte predmety.

Funkcie vzdialenosti

Metódy klastrovania

Štatistické klastrovacie algoritmy
Hierarchické zhlukovanie alebo taxonómia

Formálne vyhlásenie o probléme klastrovania

Riešenie problému klastrovania je v zásade nejednoznačné a existuje na to niekoľko dôvodov:

Neexistuje žiadne jednoznačne najlepšie kritérium pre kvalitu zoskupovania. Je známych množstvo heuristických kritérií, ako aj množstvo algoritmov, ktoré nemajú jasne definované kritérium, ale vykonávajú pomerne rozumné zhlukovanie „podľa konštrukcie“. Všetky môžu poskytnúť rôzne výsledky.
Počet zhlukov je zvyčajne vopred neznámy a je stanovený podľa nejakého subjektívneho kritéria.
Výsledok zhlukovania výrazne závisí od metriky, ktorej výber je spravidla tiež subjektívny a určuje ju odborník.

Odkazy

Voroncov K.V. Matematické vyučovacie metódy podľa precedensov. Moskovský inštitút fyziky a technológie (2004), VMiK MGU (2007).
Sergej Nikolenko. Prednáška "Algoritmy klastrovania 1" a "Algoritmy klastrovania 2". Kurz "Samoučiace sa systémy".

Literatúra

Aivazyan S.A., Buchstaber V.M., Enyukov I.S., Meshalkin L.D. Aplikovaná štatistika: Klasifikácia a redukcia rozmerov. - M.: Financie a štatistika, 1989.
Zhuravlev Yu. I., Ryazanov V. V., Senko O. V."Uznanie". Matematické metódy. Softvérový systém. Praktické aplikácie. - M.: Fazis, 2006. .
Zagoruiko N. G. Aplikované metódy analýzy dát a znalostí. - Novosibirsk: IM SO RAN, 1999. .
Mandel I. D. zhluková analýza. - M.: Financie a štatistika, 1988. .
Shlesinger M., Glavach V. Desať prednášok o štatistickom a štrukturálnom rozpoznávaní. - Kyjev: Naukova Dumka, 2004. .
Hastie T., Tibshirani R., Friedman J. Prvky štatistického učenia. - Springer, 2001.

Typy vstupu

Orientačný popis predmetov. Každý objekt je opísaný súborom jeho charakteristík, tzv znamenia. Funkcie môžu byť číselné alebo nečíselné.
Matica vzdialenosti medzi objektmi. Každý objekt je opísaný vzdialenosťami od všetkých ostatných objektov v tréningovej sade.

Ciele klastrovania

Pochopenie údajov identifikáciou štruktúry klastra. Rozdelenie vzorky do skupín podobných objektov umožňuje zjednodušiť ďalšie spracovanie údajov a rozhodovanie aplikáciou vlastnej metódy analýzy na každý zhluk (stratégia „rozdeľ a panuj“).
Kompresia údajov. Ak je počiatočná vzorka príliš veľká, môže sa zredukovať, pričom zostane jeden z najtypickejších predstaviteľov z každého klastra.
detekcia novosti. detekcia novosti). Vyberajú sa atypické objekty, ktoré nie je možné pripojiť k žiadnemu z klastrov.

V prvom prípade sa snažia počet zhlukov zmenšiť. V druhom prípade je dôležitejšie zabezpečiť vysoký stupeň podobnosti objektov v rámci každého zhluku, pričom zhlukov môže byť ľubovoľný počet. V treťom prípade je najväčší záujem o jednotlivé objekty, ktoré nezapadajú do žiadneho zo zhlukov.

Vo všetkých týchto prípadoch je možné použiť hierarchické zhlukovanie, keď sa veľké zhluky delia na menšie, ktoré sa zase delia na menšie atď. Takéto úlohy sa nazývajú úlohy taxonómie.

Výsledkom taxonómie je stromová hierarchická štruktúra. Okrem toho je každý objekt charakterizovaný vymenovaním všetkých zhlukov, do ktorých patrí, zvyčajne od veľkých po malé.

Klasickým príkladom taxonómie založenej na podobnosti je binomická nomenklatúra živých bytostí, ktorú navrhol Carl Linné v polovici 18. storočia. Podobné systematizácie sú vybudované v mnohých oblastiach vedomostí s cieľom usporiadať informácie o veľkom počte objektov.

Metódy klastrovania

Formálne vyhlásenie o probléme klastrovania

Literatúra

Aivazyan S.A., Buchstaber V.M., Enyukov I.S., Meshalkin L.D. Aplikovaná štatistika: Klasifikácia a redukcia rozmerov. - M.: Financie a štatistika, 1989.
Zhuravlev Yu. I., Ryazanov V. V., Senko O. V."Uznanie". Matematické metódy. Softvérový systém. Praktické aplikácie. - M.: Fazis, 2006. ISBN 5-7036-0108-8.
Zagoruiko N. G. Aplikované metódy analýzy dát a znalostí. - Novosibirsk: IM SO RAN, 1999. ISBN 5-86134-060-9.
Mandel I. D. zhluková analýza. - M.: Financie a štatistika, 1988. ISBN 5-279-00050-7.
Shlesinger M., Glavach V. Desať prednášok o štatistickom a štrukturálnom rozpoznávaní. - Kyjev: Naukova Dumka, 2004. ISBN 966-00-0341-2.
Hastie T., Tibshirani R., Friedman J. Prvky štatistického učenia. - Springer, 2001. ISBN 0-387-95284-5.
Jain Murty Flynn Klastrovanie údajov: prehľad . // Výpočet ACM. Surv. 31 (3) , 1999

vonkajšie odkazy

V ruštine

www.MachineLearning.ru - profesionálny wiki zdroj venovaný strojovému učeniu a dolovaniu údajov
S. Nikolenko. Prednáška o klastrovacích algoritmoch

V angličtine

COMPACT - Porovnávací balík pre hodnotenie klastrov. Bezplatný balík Matlab, 2006.
P. Berkhin, Prehľad techník ťažby dát z klastrov, Accrue Software, 2002.
Jain, Murty a Flynn: Klastrovanie údajov: Prehľad, ACM Comp. Surv., 1999.
pre ďalšiu prezentáciu hierarchických, k-means a fuzzy c-means pozri tento úvod do klastrovania . Má tiež vysvetlenie o zmesi Gaussovcov.
David dowe, Stránka Mixture Modeling- iné prepojenia modelov klastrovania a zmesí.
návod na klastrovanie
Online učebnica: Teória informácií, vyvodzovanie a algoritmy učenia sa od Davida J.C. MacKay obsahuje kapitoly o zhlukovaní k-means, soft k-means clusteringu a odvodeniach vrátane E-M algoritmu a variačného pohľadu na E-M algoritmus.
"Samoorganizovaný gén" , návod vysvetľujúci zhlukovanie prostredníctvom konkurenčného učenia a samoorganizujúcich sa máp.
kernlab - balík R pre strojové učenie založené na jadre (zahŕňa implementáciu spektrálneho klastrovania)
Výukový program - Výukový program so zavedením klastrových algoritmov (k-means, fuzzy-c-means, hierarchický, zmes gaussiánov) + niekoľko interaktívnych ukážok (java applety)
Softvér na dolovanie údajov – Softvér na dolovanie údajov často využíva techniky klastrovania.
Java Competitve Learning Application Sada neurónových sietí bez dozoru pre klastrovanie. Napísané v jazyku Java. Kompletné so všetkými zdrojovými kódmi.