Odeslat svou dobrou práci do znalostní báze je jednoduché. Použijte níže uvedený formulář
Studenti, postgraduální studenti, mladí vědci, kteří využívají znalostní základnu ve svém studiu a práci, vám budou velmi vděční.
Úvod
1.Historie "shlukové analýzy"
2. Terminologie
2.1 Předmět a funkce
2.2 Vzdálenost mezi objekty (metrické)
2.3Hustota a lokalita shluků
2.4 Vzdálenost mezi shluky
3. Metody seskupování
3.1Vlastnosti hierarchických aglomerativních metod
3.2 Vlastnosti metod iterativního shlukování
4. Shlukování funkcí
5. Stabilita a kvalita shlukování
Bibliografie
ÚVOD
"Shluková analýza je soubor matematických metod navržených tak, aby vytvořily relativně "vzdálené" od sebe navzájem skupiny "blízkých" objektů podle informací o vzdálenostech nebo souvislostech (mírách blízkosti) mezi nimi. Významově je podobný termínům: automatický klasifikace, taxonomie, rozpoznávání vzorů bez učitele." Tato definice shlukové analýzy je uvedena v posledním vydání Statistického slovníku. Ve skutečnosti je „shluková analýza“ zobecněný název pro poměrně velkou sadu algoritmů používaných k vytvoření klasifikace. Řada publikací také používá taková synonyma pro analýzu shluků, jako je klasifikace a dělení. Shluková analýza je ve vědě široce používána jako prostředek typologické analýzy. V jakékoli vědecké činnosti je klasifikace jednou ze základních složek, bez které nelze budovat a testovat vědecké hypotézy a teorie. Ve své práci proto považuji za nutné zabývat se problematikou shlukové analýzy (základ shlukové analýzy), zamyslet se nad její terminologií a uvést několik příkladů použití této metody se zpracováním dat jako hlavním cílem.
1. HISTORIE "KLUSTEROVÉ ANALÝZY"
Analýza domácích i zahraničních publikací ukazuje, že shluková analýza se používá v celé řadě vědeckých oblastí: chemie, biologie, lékařství, archeologie, historie, geografie, ekonomie, filologie atd. Kniha VV Nalimova "Pravděpodobnostní model jazyka" popisuje použití shlukové analýzy při studiu 70 analytických vzorků. Většina literatury o shlukové analýze se objevila během posledních tří desetiletí, ačkoli první práce, které se zmiňovaly o shlukových metodách, se objevily již poměrně dávno. Polský antropolog K. Chekanowski předložil myšlenku „strukturální klasifikace“, která obsahovala hlavní myšlenku shlukové analýzy - alokaci kompaktních skupin objektů.
V roce 1925 sovětský hydrobiolog P.V. Terentyev vyvinul tzv. „metodu korelačních plejád“, určenou pro seskupování korelovaných znaků. Tato metoda dala podnět k vývoji metod seskupování pomocí grafů. Termín „shluková analýza“ poprvé navrhl Trion. Slovo „cluster“ je z angličtiny přeloženo jako „chomáč, štětec, svazek, skupina“. Z tohoto důvodu se tento typ analýzy původně nazýval „shluková analýza“. Na počátku 50. let se objevily publikace R. Lewise, E. Fixa a J. Hodgese o algoritmech hierarchické shlukové analýzy. Znatelný impuls k rozvoji práce na shlukové analýze dala práce R. Rosenblatta o rozpoznávacím zařízení (perceptronu), která položila základ pro rozvoj teorie „rozpoznávání vzorů bez učitele“.
Impulsem pro rozvoj metod shlukování byla kniha „Principles of Numerical Taxonomy“, vydaná v roce 1963. dva biologové - Robert Sokal a Peter Sneath. Autoři této knihy vycházeli ze skutečnosti, že pro vytvoření efektivních biologických klasifikací by měl shlukovací postup zajistit použití různých indikátorů charakterizujících zkoumané organismy, posoudit míru podobnosti mezi těmito organismy a zajistit umístění podobných organismů. ve stejné skupině. Vytvořené skupiny by v tomto případě měly být dostatečně „lokální“, tzn. podobnost objektů (organismů) v rámci skupin by měla převyšovat podobnost skupin mezi sebou. Následná analýza identifikovaných skupin může podle názoru autorů objasnit, zda tyto skupiny odpovídají různým biologickým druhům. Sokal a Sneath tedy předpokládali, že odhalení struktury rozdělení objektů do skupin pomáhá ustavit proces utváření těchto struktur. A právě odlišnost a podobnost organismů různých shluků (skupin) může sloužit jako základ pro pochopení probíhajícího evolučního procesu a objasnění jeho mechanismu.
Ve stejných letech bylo navrženo mnoho algoritmů takovými autory jako J. McKean, G. Ball a D. Hall používající metody k-means; G. Lance a W. Williams, N. Jardine a další - o hierarchických metodách. Významně přispěli k rozvoji metod shlukové analýzy domácí vědci - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Zejména v 60.-70. Velké oblibě se těšily četné algoritmy vyvinuté novosibirskými matematiky N. G. Zagoruiko, V. N. Elkinou a G. S. Lbovem. Jedná se o tak známé algoritmy jako FOREL, BIGFOR, KRAB, NTTP, DRET, TRF atd. Na základě těchto balíčků byl vytvořen specializovaný softwarový balík OTEX. Neméně zajímavé softwarových produktů PPSA a Klass-Master vytvořili moskevští matematici S.A. Aivazyan, I.S. Enyukov a B.G. Mirkin.
Metody shlukové analýzy jsou do jisté míry dostupné ve většině nejznámějších tuzemských i zahraničních statistických balíčků: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, COPRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S -PLUS atd. Samozřejmě, 10 let po vydání této recenze se toho změnilo docela dost, objevily se nové verze mnoha statistických programů a objevily se úplně nové programy, které využívají jak nové algoritmy, tak výrazně zvýšený výkon. počítačová věda. Většina statistických balíčků však používá algoritmy navržené a vyvinuté v 60.–70.
Podle hrubých odhadů odborníků se počet publikací o shlukové analýze a jejích aplikacích v různých oblastech znalostí každé tři roky zdvojnásobí. Jaké jsou důvody tak bouřlivého zájmu o tento typ analýzy? Objektivně existují tři hlavní důvody tohoto jevu. Jedná se o vznik výkonné výpočetní technologie, bez které není shluková analýza reálných dat prakticky proveditelná. Druhým důvodem je, že moderní věda je ve svých konstrukcích stále více založena na klasifikaci. Navíc se tento proces stále více prohlubuje, protože paralelně s tím dochází ke stále větší specializaci znalostí, což je nemožné bez dostatečně objektivní klasifikace.
Třetí důvod - prohlubování speciálních znalostí nevyhnutelně vede k nárůstu počtu proměnných zohledňovaných při analýze určitých objektů a jevů. V důsledku toho se subjektivní klasifikace, která dříve spoléhala na poměrně malý počet zohledněných znaků, často ukazuje jako nespolehlivá. A objektivní klasifikace se stále rostoucí sadou charakteristik objektů vyžaduje použití složitých shlukovacích algoritmů, které lze implementovat pouze na základě moderních počítačů. Právě tyto důvody daly vzniknout „klastrovému boomu“. Mezi lékaři a biology se však shluková analýza ještě nestala poměrně populární a běžnou výzkumnou metodou.
2 TERMINOLOGIE
2. 1 PŘEDMĚT A ZNAMENÍ
Nejprve si představíme pojmy jako objekt a atribut. Objekt – z latinského objectum – subjekt. Ve vztahu k chemii a biologii budeme objekty chápat specifické předměty výzkumu, které jsou studovány pomocí fyzikálních, chemických a jiných metod. Takovými předměty mohou být například vzorky, rostliny, zvířata atd. Určitý soubor objektů, které má výzkumník k dispozici ke studiu, se nazývá vzorek nebo soubor vzorků. Počet objektů v takové populaci se obvykle nazývá velikost vzorku. Typicky je velikost vzorku označena latinským písmenem "n" nebo "N".
Znak (synonyma - vlastnost, proměnná, charakteristika; anglicky - proměnná - proměnná.) - je specifická vlastnost předmětu. Tyto vlastnosti mohou být vyjádřeny jako číselné nebo nečíselné hodnoty. Například krevní tlak (systolický nebo diastolický) se měří v milimetrech rtuti, hmotnost v kilogramech, výška v centimetrech atd. Takové znaky jsou kvantitativní. Na rozdíl od těchto spojitých numerických charakteristik (škál) může mít řada znaků diskrétní, nespojité hodnoty. Na druhé straně se takové diskrétní prvky obvykle dělí do dvou skupin.
1) První skupinou jsou řadové proměnné, nebo jak se jim také říká ordinální proměnné (škály). Takové znaky se vyznačují vlastností uspořádání těchto hodnot. Patří mezi ně stadia konkrétní nemoci, věkové skupiny, skóre znalostí studentů, 12bodová Richterova stupnice velikosti zemětřesení atd.
2) Druhá skupina diskrétních znaků nemá takové pořadí a nazývá se nominální (od slova "nominální" - vzorek) nebo klasifikační znaky. Příkladem takových příznaků může být stav pacienta – „zdravý“ nebo „nemocný“, pohlaví pacienta, doba pozorování – „před léčbou“ a „po léčbě“ atd. V těchto případech je zvykem říkat, že takové rysy patří do stupnice jmen.
Koncepty objektu a prvku se obvykle nazývají matice „vlastnosti objektu“ nebo „vlastnosti objektu“. Matice bude obdélníková tabulka skládající se z hodnot prvků, které popisují vlastnosti zkoumaného vzorku pozorování. V této souvislosti bude jedno pozorování zaznamenáno jako samostatný řádek skládající se z hodnot použitých funkcí. Samostatný atribut v takové datové matici bude reprezentován sloupcem skládajícím se z hodnot tohoto atributu pro všechny objekty ve vzorku.
2. 2 VZDÁLENOST MEZI PŘEDMĚTY (METRICKÉ)
Pojďme si představit pojem „vzdálenost mezi objekty“. Tento koncept je nedílnou mírou podobnosti objektů navzájem. Vzdálenost mezi objekty v prostoru prvků je taková hodnota d ij, která splňuje následující axiomy:
1. d ij > 0 (nezápornost vzdálenosti)
2. d ij = d ji (symetrie)
3. d ij + d jk > d ik (trojúhelníková nerovnost)
4. Pokud d ij není rovno 0, pak i není rovno j (rozlišitelnost neidentických objektů)
5. Jestliže d ij = 0, pak i = j (nerozlišitelnost identických předmětů)
Je vhodné reprezentovat míru blízkosti (podobnosti) objektů jako reciproční na vzdálenosti mezi objekty. Četné publikace věnované shlukové analýze popisují více než 50 různých způsobů výpočtu vzdálenosti mezi objekty. Kromě termínu „vzdálenost“ se v literatuře často vyskytuje další termín – „metrický“, který implikuje metodu pro výpočet konkrétní vzdálenosti. Nejdostupnější pro vnímání a porozumění v případě kvantitativních znaků je tzv. „euklidovská vzdálenost“ nebo „euklidovská metrika“. Vzorec pro výpočet této vzdálenosti je:
Tento vzorec používá následující zápis:
· d ij - vzdálenost mezi i-tým a j-tým objektem;
· x ik - číselná hodnota k-té proměnné pro i-tý objekt;
· x jk - číselná hodnota k-té proměnné pro j-tý objekt;
· v - počet proměnných, které popisují objekty.
Tedy pro případ v=2, kdy máme pouze dvě kvantitativní znaménka, bude vzdálenost d ij rovna délce přepony pravoúhlého trojúhelníku, který spojuje dva body v pravoúhlém souřadnicovém systému. Tyto dva body budou odpovídat i-tému a j-tému pozorování vzorku. Často se místo obvyklé euklidovské vzdálenosti používá její druhá mocnina d 2 ij. V některých případech se navíc používá „vážená“ euklidovská vzdálenost, při jejímž výpočtu se pro jednotlivé pojmy používají váhové koeficienty. Pro ilustraci konceptu euklidovské metriky použijeme jednoduchý tréninkový příklad. Datová matice uvedená v tabulce níže se skládá z 5 pozorování a dvou proměnných.
stůl 1
Datová matice pěti sledovaných vzorků a dvou proměnných.
Pomocí euklidovské metriky vypočítáme matici meziobjektových vzdáleností, sestávající z hodnot d ij - vzdálenost mezi i-tým a j-tým objektem. V našem případě i a j jsou číslo objektu, pozorování. Protože velikost vzorku je 5, i a j mohou nabývat hodnot od 1 do 5. Je také zřejmé, že počet všech možných párových vzdáleností bude 5*5=25. Pro první objekt to budou skutečně následující vzdálenosti: 1-1; 1-2; 1-3; 1-4; 1-5. Pro objekt 2 bude také 5 možných vzdáleností: 2-1; 2-2; 2-3; 2-4; 2-5 atd. Nicméně číslo různé vzdálenosti bude menší než 25, protože je nutné vzít v úvahu vlastnost nerozlišitelnosti identických objektů - d ij = 0 pro i = j. To znamená, že vzdálenost mezi objektem #1 a stejným objektem #1 bude nulová. Stejné nulové vzdálenosti budou pro všechny ostatní případy i = j. Z vlastnosti symetrie navíc vyplývá, že d ij = d ji pro libovolné i a j. Tito. vzdálenost mezi objekty #1 a #2 je rovna vzdálenosti mezi objekty #2 a #1.
Výraz pro euklidovskou vzdálenost je velmi podobný tzv. zobecněné Minkowského mocninné vzdálenosti, ve které se místo dvou v mocninách používá jiná hodnota. V obecném případě je tato hodnota označena symbolem "p".
Pro p = 2 dostaneme obvyklou euklidovskou vzdálenost. Takže výraz pro zobecněnou Minkowského metriku má tvar:
Volbu konkrétní hodnoty exponentu „p“ provádí výzkumník sám.
Speciálním případem Minkowského vzdálenosti je takzvaná Manhattanská vzdálenost, neboli „vzdálenost městských bloků“, odpovídající p=1:
Manhattanská vzdálenost je tedy součtem modulů rozdílů odpovídajících vlastností objektů. Necháme-li p tíhnout k nekonečnu, dostaneme metriku „dominance“ neboli Sup-metriku:
což může být také reprezentováno jako d ij = max| x ik - x jk |.
Minkowského metrika je ve skutečnosti velká rodina metrik, včetně nejpopulárnějších metrik. Existují však metody pro výpočet vzdálenosti mezi objekty, které se zásadně liší od Minkowského metriky. Nejdůležitější z nich je tzv. Mahalanobisova vzdálenost, která má spíše specifické vlastnosti. Výraz pro tuto metriku:
Tady skrz X i a X j jsou uvedeny sloupcové vektory proměnných hodnot pro i-tý a j-tý objekt. Symbol T ve výrazu (X i - X j ) T označuje tzv. vektorovou transpoziční operaci. Symbol S je uvedena společná vnitroskupinová matice rozptylu a kovariance. Symbol -1 výše S znamená, že potřebujete invertovat matici S . Na rozdíl od Minkowského metriky a euklidovské metriky, Mahalanobisova vzdálenost prostřednictvím matice rozptylu a kovariance S spojené s korelacemi proměnných. Když jsou korelace mezi proměnnými nulové, Mahalanobisova vzdálenost je ekvivalentní druhé mocnině euklidovské vzdálenosti.
V případě použití dichotomických (mající pouze dvě hodnoty) kvalitativních znaků se široce používá Hammingova vzdálenost
rovný počtu neshod v hodnotách odpovídajících vlastností pro uvažované i-té a j-té objekty.
2. 3 HUSTOTA A LOKALITA Shluků
Hlavním cílem shlukové analýzy je najít ve vzorku skupiny navzájem podobných objektů. Předpokládejme, že některou z možných metod jsme takové skupiny – shluky získali. Je třeba poznamenat důležité vlastnosti klastrů. Jednou z těchto vlastností je hustota rozložení bodů, pozorování v rámci shluku. Tato vlastnost nám umožňuje definovat shluk jako shluk bodů ve vícerozměrném prostoru, který je relativně hustý ve srovnání s jinými oblastmi tohoto prostoru, které buď neobsahují body vůbec, nebo obsahují malý počet pozorování. Jinými slovy, jak kompaktní je tento shluk, nebo naopak, jak je řídký. Přes dostatečnou evidenci této vlastnosti neexistuje jednoznačný způsob výpočtu takového ukazatele (hustoty). Nejúspěšnějším ukazatelem charakterizujícím kompaktnost, hustotu „nabalení“ vícerozměrných pozorování v daném shluku, je rozptyl vzdálenosti od středu shluku k jednotlivým bodům shluku. Čím menší je rozptyl této vzdálenosti, čím blíže jsou pozorování ke středu shluku, tím větší je hustota shluku. A naopak, čím větší je rozptyl vzdálenosti, tím je tento shluk řidší a v důsledku toho existují body umístěné jak blízko středu shluku, tak i dosti vzdálené od středu shluku.
Další vlastností shluků je jejich velikost. Hlavním ukazatelem velikosti shluku je jeho „poloměr“. Tato vlastnost nejlépe odráží skutečnou velikost shluku, pokud je uvažovaný shluk kruhový a hypersférický ve vícerozměrném prostoru. Pokud však mají shluky protáhlé tvary, pak pojem poloměr nebo průměr již neodráží skutečnou velikost shluku.
Další důležitou vlastností shluku je jejich lokalizace, oddělitelnost. Charakterizuje míru překrývání a vzájemné odlehlosti shluků od sebe ve vícerozměrném prostoru. Zvažte například rozložení tří shluků v prostoru nových integrovaných prvků na obrázku níže. Osy 1 a 2 byly získány speciální metodou z 12 znaků reflexních vlastností různých forem erytrocytů, studovaných pomocí elektronové mikroskopie.
Obrázek 1
Vidíme, že shluk 1 má minimální velikost, zatímco shluky 2 a 3 mají přibližně stejnou velikost. Zároveň můžeme říci, že minimální hustota, a tedy maximální rozptyl vzdálenosti, je charakteristická pro shluk 3. Shluk 1 je navíc oddělen dostatečně velkými úseky prázdného prostoru jak od shluku 2, tak od shluku 3. Zatímco shluky 2 a 3 se částečně překrývají. Zajímavostí je, že shluk 1 má mnohem větší rozdíl od 2. a 3. shluku podél osy 1 než podél osy 2. Naopak shluky 2 a 3 se od sebe liší přibližně stejně jak podél osy 1, tak podél osy 2. Je zřejmé, že pro takovou vizuální analýzu je nutné mít všechna pozorování vzorku promítnuta na speciální osy, ve kterých budou projekce prvků shluku viditelné jako samostatné shluky.
2. 4 VZDÁLENOST MEZI Shluky
V širším smyslu lze objekty chápat nejen jako původní předměty výzkumu, prezentované v matici „objekt-vlastnost“ jako samostatná čára, nebo jako jednotlivé body ve vícerozměrném příznakovém prostoru, ale také jako samostatné skupiny takových bodů , sjednocené jedním nebo druhým algoritmem do shluku. V tomto případě vyvstává otázka, jak chápat vzdálenost mezi takovými akumulacemi bodů (shluků) a jak ji vypočítat. V tomto případě je rozmanitost možností ještě větší než v případě výpočtu vzdálenosti mezi dvěma pozorováními ve vícerozměrném prostoru. Tento postup je komplikován tím, že na rozdíl od bodů shluky zabírají určité množství vícerozměrného prostoru a skládají se z mnoha bodů. V shlukové analýze se široce používají mezishlukové vzdálenosti, počítané na principu nejbližšího souseda (nejbližší soused), těžiště, nejvzdálenějšího souseda, mediánů. Nejčastěji se používají čtyři metody: jeden odkaz, úplný odkaz, průměrný odkaz a Wardova metoda. V metodě single link bude objekt připojen k již existujícímu clusteru, pokud má alespoň jeden z prvků clusteru stejnou úroveň podobnosti jako objekt, který se připojuje. U metody úplných vazeb je objekt připojen ke shluku pouze v případě, že podobnost mezi kandidátem na zahrnutí a kterýmkoli z prvků shluku není menší než určitý práh. Pro průměrný způsob připojení existuje několik modifikací, které představují určitý kompromis mezi jednoduchým a úplným připojením. Vypočítají průměrnou hodnotu podobnosti kandidáta na zařazení se všemi objekty stávajícího shluku. Připojení se provádí, když zjištěná průměrná hodnota podobnosti dosáhne nebo překročí určitou hranici. Nejčastěji se používá aritmetický průměr podobnosti mezi objekty shluku a kandidátem na zahrnutí do shluku.
Mnoho metod shlukování se od sebe liší tím, že jejich algoritmy v každém kroku počítají různé funkcionály kvality rozdělení. Populární Wardova metoda je konstruována tak, aby optimalizovala minimální rozptyl vzdáleností uvnitř clusteru. V prvním kroku se každý shluk skládá z jednoho objektu, díky čemuž je vnitroshlukový rozptyl vzdáleností roven 0. Touto metodou se spojují ty objekty, které dávají minimální přírůstek rozptylu, v důsledku čehož má tato metoda tendenci vytvářet hypersférické shluky.
Vícenásobné pokusy o klasifikaci metod shlukové analýzy vedou k desítkám nebo dokonce stovkám různých tříd. Takovou pestrost generuje velké množství možných způsobů výpočtu vzdálenosti mezi jednotlivými pozorováními, neméně počet metod výpočtu vzdálenosti mezi jednotlivými shluky v procesu shlukování a různé odhady optimality výsledné struktury shluků.
Nejčastěji používané v populárních statistických balíčcích jsou dvě skupiny algoritmů shlukové analýzy: hierarchické aglomerativní metody a metody iterativního seskupování.
3. METODY SESKUPOVÁNÍ
3. 1 VLASTNOSTI HIERARCHICKÝCH AGLOMERATIVNÍCH METOD
V aglomerativních hierarchických algoritmech, které se častěji používají v reálném biomedicínském výzkumu, jsou zpočátku všechny objekty (pozorování) považovány za samostatné, nezávislé shluky skládající se pouze z jednoho prvku. Bez použití výkonné výpočetní techniky je realizace klastrové analýzy dat velmi problematická.
Výběr metriky provádí výzkumník. Po výpočtu matice vzdálenosti začíná proces aglomerací (z latinského agglomero - přikládám, hromadím), procházející postupně krok za krokem. V prvním kroku tohoto procesu se dvě počáteční pozorování (monoklastry) s nejmenší vzdáleností mezi nimi spojí do jednoho shluku, který se již skládá ze dvou objektů (pozorování). Namísto dřívějších N monoklastrů (shluků skládajících se z jednoho objektu) tedy po prvním kroku vznikne N-1 shluků, z nichž jeden shluk bude obsahovat dva objekty (pozorování) a N-2 shluků se bude stále skládat z pouze jeden objekt. Ve druhém kroku jsou možné různé způsoby kombinování N-2 klastrů. Je to proto, že jeden z těchto shluků již obsahuje dva objekty. Z tohoto důvodu vyvstávají dvě hlavní otázky:
· jak vypočítat souřadnice takového shluku dvou (a dále více než dvou) objektů;
· jak vypočítat vzdálenost k takovým "poly-objektovým" shlukům od "monoklastrů" a mezi "poly-objektovými" shluky.
Tyto otázky v konečném důsledku určují konečnou strukturu výsledných shluků (strukturou shluků se rozumí složení jednotlivých shluků a jejich vzájemná poloha ve vícerozměrném prostoru). Různé kombinace metrik a metod pro výpočet souřadnic a vzájemných vzdáleností shluků dávají vzniknout různým metodám shlukové analýzy. Ve druhém kroku, v závislosti na zvolených metodách výpočtu souřadnic shluku skládajícího se z několika objektů a způsobu výpočtu mezikupových vzdáleností, je možné buď znovu spojit dvě samostatná pozorování do nového shluku, nebo spojit jedno nové pozorování do shluku sestávajícího ze dvou objektů. Pro usnadnění může většina programů aglomeračně-hierarchických metod na konci práce poskytnout dva hlavní grafy pro prohlížení. První graf se nazývá dendrogram (z řeckého dendron - strom), odrážející proces aglomerace, slučování jednotlivých pozorování do jediného výsledného shluku. Uveďme příklad dendrogramu 5 pozorování ve dvou proměnných.
Plán1
Vertikální osa takového grafu je osou mezishlukové vzdálenosti a počty objektů – případů použitých v analýze – jsou vyznačeny podél vodorovné osy. Z tohoto dendrogramu je vidět, že objekty č. 1 a č. 2 jsou nejprve spojeny do jednoho shluku, protože vzdálenost mezi nimi je nejmenší a rovná se 1. Toto sloučení je na grafu zobrazeno vodorovnou čarou spojující vertikální segmenty vycházející z bodů označených jako C_1 a C_2. Všimněme si toho, že samotná vodorovná čára prochází přesně na úrovni mezishlukové vzdálenosti rovné 1. Dále se ve druhém kroku k tomuto shluku, který již obsahuje dva objekty, připojuje objekt č. 3, označený jako C_3. Dalším krokem je sloučení objektů #4 a #5, přičemž vzdálenost mezi nimi je rovna 1,41. A v posledním kroku je shluk objektů 1, 2 a 3 zkombinován se shlukem objektů 4 a 5. Graf ukazuje, že vzdálenost mezi těmito dvěma předposledními shluky (poslední shluk zahrnuje všech 5 objektů) je větší než 5 , ale méně než 6, protože horní vodorovná čára spojující dva předposlední shluky prochází na úrovni přibližně rovné 7 a úroveň spojení objektů 4 a 5 je 1,41.
Níže uvedený dendrogram byl získán analýzou skutečného souboru dat sestávajícího ze 70 zpracovaných chemické vzorky, z nichž každý se vyznačoval 12 rysy.
Graf 2
Z grafu je vidět, že v posledním kroku, kdy se poslední dva shluky spojí, je mezi nimi vzdálenost asi 200 jednotek. Je vidět, že první shluk obsahuje mnohem méně objektů než shluk druhý. Níže je zvětšený výřez dendrogramu, na kterém jsou jasně viditelná čísla pozorování, označená jako C_65, C_58 atd. (zleva doprava): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94 atd.
Graf 3 Zvětšená část grafu č. 2 výše
Je vidět, že objekt 44 je monoklastr, který se v předposledním kroku spojí s pravým shlukem, a pak, v posledním kroku, se všechna pozorování spojí do jednoho shluku.
Dalším grafem, který je v takových postupech vytvořen, je graf mezishlukových vzdáleností v každém kroku sjednocení. Níže je podobný graf pro výše uvedený dendrogram.
Graf 4
V řadě programů je možné zobrazit v tabulkové formě výsledky kombinování objektů v každém kroku shlukování. Ve většině těchto tabulek, aby se předešlo zmatkům, se používá odlišná terminologie pro označení počátečních pozorování - monoklastrů a skutečných shluků sestávajících ze dvou nebo více pozorování. V anglickojazyčných statistických balíčcích jsou počáteční pozorování (řádky matice dat) označeny jako "case" - case. Abychom demonstrovali závislost shlukové struktury na volbě metriky a volbě shlukového sjednocovacího algoritmu, uvádíme níže dendrogram odpovídající algoritmu plného spojení. A zde vidíme, že objekt #44 je sloučen se zbytkem výběru v úplně posledním kroku.
Graf 5
Nyní jej porovnejme s jiným diagramem získaným pomocí metody single link na stejných datech. Na rozdíl od metody úplného spojení je vidět, že tato metoda generuje dlouhé řetězce postupně připojených objektů k sobě. Ve všech třech případech však můžeme říci, že vyčnívají dvě hlavní skupiny.
Graf 6
Věnujme také pozornost, že ve všech třech případech se objekt č. 44 spojuje jako monoklastr, i když v různých krocích procesu shlukování. Výběr takových monoklastrů je dobrým prostředkem k detekci anomálních pozorování, nazývaných odlehlé hodnoty. Smažte tento "podezřelý" objekt č. 44 a znovu proveďte shlukování. Získáme následující dendrogram:
Graf 7
Je vidět, že „řetězový“ efekt je zachován, stejně jako rozdělení do dvou lokálních skupin pozorování.
3. 2 VLASTNOSTI ITERATIVNÍCH METOD KLUSTEROVÁNÍ
Mezi iteračními metodami je nejoblíbenější metoda McKeanova k-means. Na rozdíl od hierarchických metod musí ve většině implementací této metody uživatel sám specifikovat požadovaný počet finálních shluků, který se obvykle označuje jako „k“. Stejně jako u metod hierarchického shlukování si uživatel může vybrat jeden nebo jiný typ metriky. Různé algoritmy metody k-means se také liší způsobem výběru počátečních středů daných shluků. V některých verzích metody může (nebo musí) takové počáteční body určit uživatel sám, a to buď jejich výběrem z reálných pozorování, nebo zadáním souřadnic těchto bodů pro každou z proměnných. V jiných implementacích této metody se výběr daného počtu k počátečních bodů provádí náhodně a tyto počáteční body (zrna shluku) lze následně zpřesňovat v několika stupních. Existují 4 hlavní fáze těchto metod:
· vybrat nebo přiřadit k pozorování, která budou primárními centry shluků;
· v případě potřeby se vytvoří mezilehlé shluky přiřazením každého pozorování k nejbližším specifikovaným středům shluků;
· po přiřazení všech pozorování k jednotlivým shlukům jsou primární středy shluků nahrazeny průměry shluků;
· předchozí iterace se opakuje, dokud se změny souřadnic středů shluků nestanou minimální.
V některých verzích této metody může uživatel nastavit číselnou hodnotu kritéria, která je interpretována jako minimální vzdálenost pro výběr nových středů clusteru. Pozorování nebude považováno za kandidáta na nové centrum shluku, pokud jeho vzdálenost k nahrazenému středu shluku překročí zadané číslo. Tento parametr se v některých programech nazývá "poloměr". Kromě tohoto parametru je také možné nastavit maximální počet iterací nebo dosáhnout určitého, obvykle dosti malého, počtu, se kterým se porovnává změna vzdálenosti pro všechna centra clusteru. Toto nastavení se běžně nazývá „konvergence“, protože odráží konvergenci procesu iterativního shlukování. Níže uvádíme některé výsledky, které byly získány pomocí metody McKean k-means k předchozím údajům. Počet požadovaných shluků byl zpočátku nastaven na 3 a poté na 2. Jejich první část obsahuje výsledky jednofaktorové analýza rozptylu, ve kterém číslo shluku funguje jako seskupovací faktor. V prvním sloupci je seznam 12 proměnných, následují součty čtverců (SS) a stupňů volnosti (df), dále Fisherův F-test a v posledním sloupci dosažená hladina významnosti „p“.
Tabulka 2 McKean k-střední údaje použitelné pro 70 testovacích vzorků.
|
Proměnné |
|||||||
Jak je vidět z této tabulky, nulová hypotéza o rovnosti průměrů ve třech skupinách je zamítnuta. Níže je uveden graf průměrů všech proměnných pro jednotlivé shluky. Stejné shlukové průměry proměnných jsou uvedeny níže ve formě tabulky.
Tabulka 3. Podrobný přehled dat na příkladu tří shluků.
|
Variabilní |
Cluster #1 |
Shluk #2 |
Shluk #3 |
|
Graf 8
Analýza průměrných hodnot proměnných pro každý shluk nám umožňuje dospět k závěru, že podle funkce X1 mají shluky 1 a 3 blízké hodnoty, zatímco shluk 2 má průměrnou hodnotu mnohem nižší než v ostatních dvou shlucích. Naopak podle funkce X2 má první shluk nejnižší hodnotu, zatímco 2. a 3. shluk mají vyšší a blízké průměrné hodnoty. Pro vlastnosti X3-X12 jsou střední hodnoty ve shluku 1 výrazně vyšší než ve shlucích 2 a 3. Následující tabulka analýzy ANOVA výsledků shlukování do dvou shluků také ukazuje potřebu zamítnout nulovou hypotézu o rovnosti skupinových průměrů pro téměř všech 12 znaků, s výjimkou proměnné X4, u které se dosažená hladina významnosti ukázala jako více než 5 %.
Tabulka 4. Tabulka disperzní analýzy výsledků shlukování do dvou shluků.
|
Proměnné |
|||||||
Níže je uveden graf a tabulka skupinových průměrů pro případ shlukování do dvou shluků.
Tabulka 5. Tabulka pro případ shlukování do dvou shluků.
|
Proměnné |
Cluster #1 |
Shluk #2 |
|
Graf 9.
V případě, že výzkumník není schopen předem určit nejpravděpodobnější počet shluků, je nucen výpočty opakovat s nastavením jiného počtu, podobně jako výše. A poté, porovnávejte získané výsledky mezi sebou, zastavte se u jedné z nejpřijatelnějších možností shlukování.
4 . SESKUPOVÁNÍ VLASTNOSTÍ
Kromě shlukování jednotlivých pozorování existují také algoritmy shlukování funkcí. Jednou z prvních takových metod je metoda korelačních plejád Terentiev P.V. Primitivní obrázky takových plejád lze často nalézt v biomedicínských publikacích ve formě kruhu posetého šipkami spojujícími znaky, pro které autoři našli korelaci. Řada programů pro shlukování objektů a funkcí má samostatné procedury. Například v balíčku SAS pro shlukování funkcí je použita procedura VARCLUS (z VARiable - proměnná a CLUSter - cluster), zatímco shluková analýza pozorování je prováděna jinými procedurami - FASTCLUS a CLUSTER. Konstrukce dendrogramu se v obou případech provádí pomocí TREE (stromové) procedury.
V jiných statistických balíčcích se výběr prvků pro shlukování - objektů nebo prvků - provádí ve stejném modulu. Jako metrika pro shlukování prvků se často používají výrazy, které zahrnují hodnotu určitých koeficientů odrážejících sílu vztahu pro pár prvků. V tomto případě je velmi vhodné, aby znaménka se silou spojení rovnou jedné (funkční závislost) vzala vzdálenost mezi znaménky rovnou nule. S funkčním spojením může hodnota jednoho prvku přesně vypočítat hodnotu jiného prvku. S poklesem síly vztahu mezi znameními se odpovídajícím způsobem zvětšuje vzdálenost. Níže je graf ukazující dendrogram kombinace 12 prvků, které byly použity výše při shlukování 70 analytických vzorků.
Graf 10. Dendrogramshlukování 12 funkcí.
Jak je vidět z tohoto dendrogramu, máme co do činění se dvěma lokálními seskupeními znaků: X1-X10 a X11-X12 Skupina znaků X1-X10 se vyznačuje poměrně malou hodnotou mezishlukových vzdáleností, nepřesahující přibližně 100 jednotek. Zde také vidíme některé vnitřní spárované podskupiny: X1 a X2, X3 a X4, X6 a X7. Vzdálenost mezi rysy těchto párů, která je velmi blízká nule, ukazuje na jejich silný párový vztah. Zatímco u dvojice X11 a X12 je hodnota mezishlukové vzdálenosti mnohem větší a činí asi 300 jednotek. Konečně, velmi velká vzdálenost mezi levým (X1-X10) a pravým (X11-X12) shluky, rovnající se asi 1150 jednotkám, naznačuje, že vztah mezi těmito dvěma skupinami prvků je zcela minimální.
5. STABILITA A KVALITA KLUSTERŮ
Je zřejmé, že by bylo absurdní klást si otázku, jak absolutní je ta či ona klasifikace získaná pomocí metod shlukové analýzy. Při změně metody shlukování se stabilita projeví tím, že na dendrogramech jsou celkem jasně patrné dva shluky.
Jako jeden z možných způsobů kontroly stability výsledků shlukové analýzy lze použít metodu porovnávání výsledků získaných pro různé shlukovací algoritmy. Dalšími způsoby jsou tzv. bootstrap metoda navržená B. Efronem v roce 1977, metody „jackknife“ a „sliding control“. Nejjednodušším prostředkem kontroly stability shlukového řešení může být náhodné rozdělení počátečního vzorku na dvě přibližně stejné části, shlukování obou částí a následné porovnání výsledků. Časově náročnější způsob zahrnuje postupné vyloučení prvního objektu na začátku a shlukování zbývajících (N - 1) objektů. Dále postupné provádění tohoto postupu s výjimkou druhého, třetího atd. objektů, je analyzována struktura všech N získaných shluků. Další algoritmus pro kontrolu stability zahrnuje vícenásobnou reprodukci, duplikaci původního vzorku N objektů, pak spojení všech duplikovaných vzorků do jednoho velkého vzorku (pseudoobecná populace) a náhodné extrahování nového vzorku N objektů z něj. Poté je tento vzorek shlukován, poté je odebrán nový náhodný vzorek a znovu se provádí shlukování atd. Je to také poměrně náročné na práci.
Neméně problémů není ani při posuzování kvality shlukování. Je známo poměrně dost algoritmů pro optimalizaci clusterových řešení. V 50. letech se objevily první práce, které obsahovaly formulace kritéria pro minimalizaci intraklastrového rozptylu a algoritmus (typu k-means) pro nalezení optimálního řešení. V roce 1963 Článek J. Warda také představil podobný optimalizační hierarchický algoritmus. Neexistuje žádné univerzální kritérium pro optimalizaci clusterového řešení. To vše ztěžuje výzkumníkovi výběr optimálního řešení. V takové situaci tím nejlepším možným způsobem tvrdit, že nalezené shlukové řešení je v této fázi studie optimální, je pouze konzistence tohoto řešení se závěry získanými pomocí jiných metod vícerozměrné statistiky.
Ve prospěch závěru o optimálnosti shlukování svědčí i pozitivní výsledky ověření prediktivních momentů získaného řešení již na jiných objektech studia. Při použití hierarchických metod shlukové analýzy lze doporučit porovnání několika grafů mezi sebou přírůstková změna mezishluková vzdálenost. V tomto případě by měla být dána přednost možnosti, pro kterou je pozorována plochá čára takového přírůstku od prvního kroku po několik předposledních kroků s ostrým vertikálním vzestupem v tomto grafu v posledních 1-2 krocích shlukování.
ZÁVĚRY
Ve své práci jsem se snažil ukázat nejen složitost tohoto typu analýzy, ale také optimální možnosti zpracování dat, protože často pro přesnost výsledků musíte použít desítky až stovky vzorků. Tenhle typ analýza pomáhá klasifikovat a zpracovávat výsledky. Za nedůležitou považuji také přijatelnost počítačových technologií v této analýze, která umožňuje zkrátit proces zpracování výsledků a umožňuje tak věnovat větší pozornost správnosti odběru vzorků pro analýzu.
Při použití shlukové analýzy existují takové jemnosti a detaily, které se objevují v jednotlivých konkrétních případech a nejsou okamžitě viditelné. Například role škály znaků může být minimální a v některých případech může být dominantní. V takových případech je nutné použít variabilní transformace. To je zvláště účinné při použití metod, které vytvářejí nelineární transformace prvků, které obecně zvyšují celkovou úroveň korelací mezi prvky.
Ještě větší specifičnost je v použití shlukové analýzy ve vztahu k objektům, které jsou popsány pouze kvalitativními znaky. V tomto případě jsou metody předběžné digitalizace kvalitativních prvků a shluková analýza s novými prvky poměrně úspěšné. Ve své práci jsem ukázal, že shluková analýza poskytuje mnoho nových a originálních informací jak v případě její aplikace v dostatečně prostudovaných systémech, tak i při studiu systémů s neznámou strukturou.
Je třeba také poznamenat, že shluková analýza se stala nepostradatelnou v evolučním výzkumu, což umožňuje konstrukci fylogenetických stromů ukazujících evoluční cesty. Tyto metody jsou široce používány v programech vědecký výzkum ve fyzikální a analytické chemii.
BIBLIOGRAFIE
1) Aivazyan S. A., Enyukov I. S., Meshalkin L. D. O struktuře a obsahu softwarového balíčku pro aplikovanou statistickou analýzu//Algoritmické a software aplikovaná statistická analýza.--M., 1980.
2) Ayvazyan S.A., Bezhaeva Z.I., Staroverov O.V. Klasifikace vícerozměrných pozorování.--M.: Statistics, 1974.
3) Becker V. A., Lukatskaya M. L. O analýze struktury matice vazebných koeficientů//Problémy ekonomického a statistického modelování a prognózování v průmyslu.-- Novosibirsk, 1970.
4) Braverman E. M., Muchnik I. B. Strukturální metody zpracování dat.--M.: Nauka, 1983.
5) Voronin Yu. A. Klasifikační teorie a její aplikace.--Novosibirsk: Nauka, 1987.
6) Good I. J. Botryology of botryology//Klasifikace a cluster.--M.: Mir, 1980.
7) Dubrovsky S. A. Aplikovaná vícerozměrná statistická analýza.--M.: Finance and statistics, 1982.
8) Duran N., Odell P. Cluster analysis.--M.: Statistics, 1977.
9) Eliseeva I.I., Rukavishnikov V.S. Seskupení, korelace, rozpoznávání vzorů.--M.: Statistics, 1977.
10) Zagoruiko N. G. Rozpoznávací metody a jejich aplikace.--M .: Sovětský rozhlas, 1972.
11) Zade L. A. Fuzzy množiny a jejich aplikace při rozpoznávání vzorů a shlukové analýze//Klasifikace a shlukování.--M.: Mir, 1980.
12) Kildishev G.S., Abolentsev Yu.I. Multidimenzionální seskupení.--M.: Statistics, 1978.
13) Raiskaya II, Gostilin NI, Frenkel AA O jednom způsobu kontroly platnosti dělení ve shlukové analýze.//Uplatnění vícerozměrné statistické analýzy v ekonomii a hodnocení kvality produktů.--Ch. P. Tartu, 1977.
14) Shurygin A. M. Distribuce mezibodových vzdáleností a rozdílů // Software a podpora algoritmů pro aplikovanou vícerozměrnou statistickou analýzu. -- M., 1983.
15) Eeremaa R. Obecná teorie navrhování klastrových systémů a algoritmů pro nalezení jejich numerických reprezentací: Sborník Výpočetního centra TSU.--Tartu, 1978.
16) Yastremsky B.S. Selected Works.--M.: Statistics, 1964.
Podobné dokumenty
Cíle segmentace trhu v marketingové aktivity. Podstata shlukové analýzy, hlavní fáze její implementace. Vyberte způsob měření vzdálenosti nebo míry podobnosti. Hierarchické, nehierarchické metody shlukování. Posouzení spolehlivosti a spolehlivosti.
zpráva, přidáno 02.11.2009
Hlavní charakteristiky finanční situaci podniky. Krize v podniku, její příčiny, druhy a důsledky. Moderní metody a nástroje klastrové analýzy, vlastnosti jejich použití pro finanční a ekonomické hodnocení podniku.
práce, přidáno 10.09.2013
Proveďte shlukovou analýzu podniků pomocí Statgraphics Plus. Konstrukce lineární regresní rovnice. Výpočet koeficientů pružnosti pomocí regresních modelů. Posouzení statistické významnosti rovnice a koeficientu determinace.
úkol, přidáno 16.03.2014
Konstrukce typologických regresí pro jednotlivé skupiny pozorování. Prostorová data a časové informace. Rozsah použití shlukové analýzy. Pojem homogenity objektů, vlastnosti matice vzdáleností. Provádění typologické regrese.
prezentace, přidáno 26.10.2013
Tvorba kombinovaných modelů a metod as moderním způsobem prognózování. Model založený na ARIMA pro popis stacionárních a nestacionárních časových řad při řešení problémů shlukování. Autoregresní AR modely a aplikace korelogramů.
prezentace, přidáno 01.05.2015
Charakteristika různých typů metrik. Metoda nejbližšího souseda a její zobecnění. Algoritmus nejbližšího souseda. Metoda Parzenova okna. Zobecněný metrický klasifikátor. Problém výběru metriky. Manhattan a euklidovská vzdálenost. kosinusová míra.
semestrální práce, přidáno 03.08.2015
Charakteristika stavebního průmyslu Krasnodarského území. Prognóza vývoje bytové výstavby. Moderní metody a nástroje shlukové analýzy. Vícerozměrné statistické metody pro diagnostiku ekonomického stavu podniku.
práce, přidáno 20.07.2015
Charakteristika hypotečních úvěrů na příkladu Brjanské oblasti. Přehled matematických rozhodovacích metod: expertní hodnocení, sekvenční a párová porovnávání, hierarchická analýza. Vývoj vyhledávacího programu pro optimální hypoteční úvěr.
semestrální práce, přidáno 29.11.2012
Oblasti aplikace systémové analýzy, její místo, role, cíle a funkce v moderní věda. Pojem a obsah metod systémové analýzy, její neformální metody. Vlastnosti heuristických a expertních výzkumných metod a vlastnosti jejich aplikace.
semestrální práce, přidáno 20.05.2013
Vývoj a výzkum ekonometrických metod s přihlédnutím ke specifikům ekonomických dat a v souladu s potřebami ekonomika a praktik. Aplikace ekonometrických metod a modelů pro statistickou analýzu ekonomických dat.
Univerzita: VZFEI
Rok a město: Moskva 2008
1. Úvod. Koncepce metody shlukové analýzy.
2. Popis metodiky aplikace shlukové analýzy. Kontrolní příklad řešení problémů.
4. Seznam použité literatury
- Úvod. Koncepce metody shlukové analýzy.
Shluková analýza je soubor metod, které umožňují klasifikovat vícerozměrná pozorování, z nichž každá je popsána sadou vlastností (parametrů) X1, X2, ..., Xk.
Účelem shlukové analýzy je vytvoření skupin navzájem podobných objektů, které se běžně nazývají shluky (třída, taxon, koncentrace).
Shluková analýza je jednou z oblastí statistického výzkumu. Zvláště důležité místo zaujímá v těch vědních oborech, které jsou spojeny se studiem hromadných jevů a procesů. Potřeba vyvinout metody shlukové analýzy a jejich použití je diktována skutečností, že pomáhají budovat vědecky podložené klasifikace, identifikovat interní komunikace mezi jednotkami sledované populace. Kromě toho lze ke kompresi informací použít metody shlukové analýzy, což je důležitý faktor vzhledem k neustálému nárůstu a složitosti toků statistických dat.
Metody shlukové analýzy umožňují řešit následující problémy:
Provádění klasifikace objektů s přihlédnutím k vlastnostem, které odrážejí podstatu, povahu objektů. Řešení takového problému zpravidla vede k prohloubení znalostí o souhrnu klasifikovaných objektů;
Kontrola provedených předpokladů o přítomnosti nějaké struktury ve studovaném souboru objektů, tzn. hledání existující struktury;
Konstrukce nových klasifikací pro špatně prozkoumané jevy, kdy je potřeba zjistit přítomnost souvislostí v populaci a pokusit se do ní vnést strukturu (1. s. 85-86).
2. Popis metodiky aplikace shlukové analýzy. Kontrolní příklad řešení problémů.
Shluková analýza umožňuje vytvořit členění do homogenních skupin (shluků) z n objektů charakterizovaných k rysy. Homogenita objektů je určena vzdáleností p(xi xj), kde xi = (xi1, …., xik) a xj= (xj1,…,xjk) jsou vektory složené z hodnot k atributů i -tý a j-tý předmět.
U objektů charakterizovaných číselnými znaky je vzdálenost určena následujícím vzorcem:
p(xi, xj) = √ ∑(x1m-xjm) 2 (1)*
Objekty jsou považovány za homogenní, pokud p(xi xj)< p предельного.
Grafické znázornění sjednocení lze získat pomocí shlukového sjednocovacího stromu - dendrogramu. (2. Kapitola 39).
Testovací případ (příklad 92).
|
Objem prodeje |
|||||
Klasifikujme tyto objekty pomocí principu „blízkého souseda“. Najděte vzdálenosti mezi objekty pomocí vzorce (1)* . Doplňme tabulku.
Vysvětlíme si, jak se tabulka zaplňuje.
Na průsečíku řádku i a sloupce j je uvedena vzdálenost p(xi xj) (výsledek se zaokrouhluje na dvě desetinná místa nahoru).
Například na průsečíku řádku 1 a sloupce 3 je uvedena vzdálenost p(x1, x3) = √(1-6) 2 +(9-8) 2 ≈ 5,10 a na průsečíku řádku 3 a sloupce 5, vzdálenost p(x3, x5) = √ (6-12) 2 + (8-7) 2 ≈ 6,08. Protože p(xi, xj) = p(xj,xi), není třeba vyplňovat spodní část tabulky.
Aplikujme princip „blízkého souseda“. V tabulce najdeme nejmenší ze vzdáleností (pokud jich je více, vybereme kteroukoli z nich). Toto je p 1,2 ≈ p 4,5 \u003d 2,24. Nechť p min = p 4,5 = 2,24. Potom můžeme spojit objekty 4 a 5 do jedné skupiny, to znamená, že spojený sloupec 4 a 5 bude obsahovat nejmenší z odpovídajících čísel sloupců 4 a 5 původní tabulky vzdáleností. Totéž uděláme s řádky 4 a 5. Získáme novou tabulku.
Ve výsledné tabulce najdeme nejmenší ze vzdáleností (pokud jich je více, pak zvolíme kteroukoli z nich): р min = р 1,2 = 2,24. Potom můžeme spojit objekty 1,2,3 do jedné skupiny, to znamená, že spojený sloupec 1,2,3 bude obsahovat nejmenší z odpovídajících čísel sloupců 1 a 2 a 3 předchozí tabulky vzdáleností. Totéž uděláme s řádky 1 a 2 a 3. Získáme novou tabulku.
Máme dva shluky: (1,2,3) a (4,5).
3. Řešení úloh pro kontrolní práci.
Problém 85.
Podmínky: Pět výrobních závodů se vyznačuje dvěma znaky: objemem prodeje a průměrnými ročními náklady na dlouhodobý majetek.
|
Objem prodeje |
|||||
|
Průměrné roční náklady stálý výrobní majetek |
Řešení: Najděte vzdálenosti mezi objekty pomocí vzorce (1)* (zaokrouhlíme na dvě desetinná místa):
p 1,1 \u003d √ (2-2) 2 + (2-2) 2 \u003d 0
p 1,2 \u003d √ (2-5) 2 + (7-9) 2 ≈ 3,61
p 1,3 \u003d √ (2-7) 2 + (7-10) 2 ≈ 5,83
p 2,2 \u003d √ (5-5) 2 + (9-9) 2 \u003d 0
p 2,3 \u003d √ (5-7) 2 + (9-10) 2 ≈ 2,24
p 3,4 \u003d √ (7-12) 2 + (10-8) 2 ≈5,39
p 3,5 \u003d √ (7-13) 2 + (10-5) 2 ≈ 7,81
p 4,5 \u003d √ (12-13) 2 + (8-5) 2 ≈ 3,16
Na základě výsledků výpočtů vyplníme tabulku:
Aplikujme princip nejbližšího souseda. Za tímto účelem najdeme v tabulce nejmenší ze vzdáleností (pokud jich je několik, vyberte kteroukoli z nich). Toto je p 2,3=2,24. Nechť p min = p 2,3 = 2,24, pak můžeme kombinovat objekty sloupců "2" a "3" a také kombinovat řady objektů "2" a "3". V nové tabulce zadáme nejmenší hodnoty z původní tabulky do kombinovaných skupin.
V nové tabulce najdeme nejmenší ze vzdáleností (pokud jich je více, vybereme kteroukoli z nich). Toto je p 4,5=3,16. Nechť p min = p 4,5 = 3,16, pak můžeme kombinovat objekty sloupců "4" a "5" a také kombinovat řady objektů "4" a "5". V nové tabulce zadáme nejmenší hodnoty z původní tabulky do kombinovaných skupin.
V nové tabulce najdeme nejmenší ze vzdáleností (pokud jich je více, vybereme kteroukoli z nich). Jsou to p 1, 2 a 3 = 3,61. Nechť p min = p 1, 2 a 3 = 3,61, pak můžeme sloučit sloupcové objekty "1" a "2 a 3" a také sloučit řádky. V nové tabulce zadáme nejmenší hodnoty z původní tabulky do kombinovaných skupin.
Získáme dva shluky: (1,2,3) a (4,5).
Dendrogram ukazuje pořadí výběru prvků a odpovídající minimální vzdálenosti pmin.
Odpovědět: Výsledkem shlukové analýzy podle principu „nejbližšího souseda“ jsou 2 shluky navzájem podobných objektů: (1,2,3) a (4,5).
Problém 211.
Podmínky: Pět výrobních zařízení se vyznačuje dvěma znaky: objemem prodeje a průměrnou roční hodnotou dlouhodobého majetku.
|
Objem prodeje |
|||||
|
Průměrné roční náklady na stálá výrobní aktiva |
Klasifikujte tyto objekty pomocí principu nejbližšího souseda.
Řešení: Pro vyřešení problému uvádíme data v původní tabulce. Pojďme určit vzdálenosti mezi objekty. Objekty budeme klasifikovat podle principu „nejbližší soused“. Výsledky jsou prezentovány ve formě dendrogramu.
|
Objem prodeje |
|||||
|
Průměrné roční náklady na stálá výrobní aktiva |
Pomocí vzorce (1)* zjistíme vzdálenosti mezi objekty:
p 1,1 = 0, p 1,2 = 6, p 1,3 = 8,60, p 1,4 = 6,32, p 1,5 = 6,71, p 2,2 = 0, p 2,3 = 7,07, p 2,4 = 2, p 2,5 = 3,32 0, p3,4 = 5,10, p3,5 = 4,12, p4,4=0, p4,5=1, p5,5=0.
Výsledky jsou uvedeny v tabulce:
Nejmenší hodnota vzdáleností v tabulce je p 4,5=1. Nechť p min = p 4,5 = 1, pak můžeme kombinovat objekty sloupců "4" a "5" a také kombinovat řady objektů "4" a "5". V nové tabulce zadáme nejmenší hodnoty z původní tabulky do kombinovaných skupin.
Nejmenší hodnota vzdáleností v nové tabulce je p 2, 4 a 5=2. Nechť p min = p 2, 4 a 5=2, pak můžeme kombinovat objekty sloupců "4 a 5" a "3" a také kombinovat řady objektů "4 a 5" a "3". V nové tabulce zadáme nejmenší hodnoty z tabulky do kombinovaných skupin.
Nejmenší hodnota vzdáleností v nové tabulce je p 3,4,5=2. Nechť p min = p 3,4,5=2, pak můžeme kombinovat objekty sloupců "3,4,5" a "2" a také kombinovat řady objektů "3,4,5" a " 2". V nové tabulce zadáme nejmenší hodnoty z tabulky do kombinovaných skupin.
| nebo se přihlaste na stránku. |
Viz CLUSTEROVÁ ANALÝZA. antinacistické. Encyklopedie sociologie, 2009 ... Encyklopedie sociologie
shluková analýza- jedná se o soubor metod, které umožňují klasifikovat vícerozměrná pozorování, z nichž každé je popsáno určitou sadou proměnných. Účelem shlukové analýzy je vytvoření skupin navzájem podobných objektů, které se běžně nazývají ... ... Sociologický slovník Socium
shluková analýza- matematický postup pro vícerozměrnou analýzu, který umožňuje na základě souboru ukazatelů charakterizujících řadu objektů (například předmětů) je seskupit do tříd (shluků) tak, aby objektů zahrnutých v jedné třídě bylo více . ... ... Velká psychologická encyklopedie
Shluková analýza- matematický postup, který umožňuje na základě podobnosti kvantitativních hodnot několika znaků charakteristických pro každý objekt (například subjekt) libovolné množiny seskupit tyto objekty do určitých tříd nebo shluků. ... .. Psychologický slovník
shluková analýza- - [L.G. Sumenko. Anglický ruský slovník informačních technologií. M.: GP TsNIIS, 2003.] Témata Informační technologie obecně EN shluková analýza … Technická příručka překladatele
shluková analýza- * shluková analýza * shluková analýza neboli shlukování dat je vícerozměrný statistický postup, který shromažďuje data obsahující informace o výběru objektů a poté uspořádává objekty do relativně homogenních skupin shluků (Q ... ... Genetika. encyklopedický slovník
shluková analýza- Je žádoucí zlepšit tento článek v matematice?: Vkládání poznámek pod čarou, přesnější označení zdrojů. Opravte článek podle stylistických pravidel Wikipedie. Recycle ofo ... Wikipedie
CLUSTEROVÁ ANALÝZA- - matematický postup pro vícerozměrnou analýzu, který umožňuje na základě souboru ukazatelů charakterizujících řadu objektů (například předmětů) je seskupit do tříd (shluků), takže objekty zahrnuté v jedné třídě jsou více ... ... Encyklopedický slovník psychologie a pedagogiky
CLUSTEROVÁ ANALÝZA - Běžné jméno pro různé matematické metody pro určování hluboké struktury ve složitých datech. Shluková analýza je v mnoha ohledech podobná faktorové analýze. Oba zahrnují hledání unitárních prvků (faktorů nebo shluků), které... ... Výkladový slovník psychologie
CLUSTEROVÁ ANALÝZA- (shluková analýza) technika používaná k identifikaci skupin objektů nebo lidí, které mohou vykazovat relativní rozdíly v souboru dat. Poté jsou studovány charakteristiky takových lidí v každé skupině. V průzkumu trhu, ... ... Velký výkladový sociologický slovník
CLUSTEROVÁ ANALÝZA- (CLUSTER ANALYSIS) Skupina statistických technik používaných k určení vnitřní struktury dat při analýze výzkumných informací týkajících se více proměnných. Účelem shlukové analýzy je identifikovat skupiny objektů ... ... sociologický slovník
Tato kniha je věnována právě jednomu z nejslibnějších přístupů k analýze vícerozměrných procesů a jevů v tomto smyslu – shlukové analýze.
Shluková analýza je způsob seskupování vícerozměrných objektů, založený na prezentaci výsledků jednotlivých pozorování podle bodů vhodného geometrického prostoru s následným výběrem skupin jako "shluků" těchto bodů. Vlastně „shluk“ (shluk) v anglický jazyk a znamená „sraženina“, „hrozen (hrozen)“, „shluk (hvězd)“ atd. Tento výraz neobvykle dobře zapadá do vědecké terminologie, protože jeho první slabika odpovídá tradičnímu výrazu „třída“ a druhá, jak to bylo, naznačuje jeho umělý původ. Nepochybujeme o tom, že terminologie shlukové analýzy nahradí všechny konstrukty dříve používané pro tento účel (neřízené rozpoznávání vzorů, stratifikace, taxonomie, automatická klasifikace atd.). Potenciální možnosti shlukové analýzy jsou zřejmé pro řešení řekněme problémů identifikace skupin podniků působících v podobných podmínkách nebo s podobnými výsledky, homogenních skupin obyvatelstva v různých aspektech života či životního stylu obecně atd.
Jako vědecký směr se shluková analýza deklarovala v polovině 60. let a od té doby se rychle rozvíjí a je jedním z nejintenzivnějších odvětví statistické vědy. Stačí říci, že pouze počet dosud publikovaných monografií o shlukové analýze v různých zemích se měří na stovky (zatímco řekněme podle takové „zasloužené“ metody vícerozměrné statistické analýzy, jako je např. faktorová analýza, je stěží možné napočítat několik desítek knih). A to je celkem pochopitelné. Vždyť se vlastně bavíme o modelování operace seskupení, jedné z nejdůležitějších nejen ve statistice, ale obecně – jak v poznávání, tak v rozhodování.
U nás vyšla řada monografií věnovaných studiu specifických socioekonomických problémů pomocí shlukové analýzy (1), metodice využití shlukové analýzy v socioekonomickém výzkumu (2), metodice shlukové analýzy jako takové ( 3) (Základy statistické analýzy)
Navrhovaná kniha I. D. Mandela je jakoby kolmá k této klasifikaci: její obsah je spojen s každou z těchto tří oblastí.
Účelem knihy je shrnout stav techniky shlukovou analýzu, analyzovat možnosti jejího využití a úkoly dalšího rozvoje. Tato myšlenka sama o sobě nemůže vzbudit respekt: nezaujatá analýza a zobecnění vyžadují hodně práce, erudice, odvahy a jsou vědeckou komunitou hodnoceny mnohem níže než propagace a vývoj vlastních návrhů. (Kniha však obsahuje také původní autorčiny vývojové trendy související s „intenzionální“ analýzou a dualitou klasifikací.)
S realizací tohoto cíle jsou spojeny jak přednosti knihy, tak její nedostatky. Mezi výhody by mělo patřit:
· metodologické studium pojmů homogenita, seskupování a klasifikace s přihlédnutím k mnohorozměrnosti jevů a procesů;
· systematický přehled přístupů a metod shlukové analýzy (včetně až 150 specifických algoritmů);
· prezentace technologie a výsledků experimentálního srovnání postupů shlukové analýzy; Tato kniha je věnována právě jednomu z nejslibnějších přístupů k analýze vícerozměrných procesů a jevů v tomto smyslu – shlukové analýze.
Shluková analýza je způsob seskupování vícerozměrných objektů, založený na prezentaci výsledků jednotlivých pozorování podle bodů vhodného geometrického prostoru s následným výběrem skupin jako "shluků" těchto bodů. Ve skutečnosti „cluster“ (shluk) v angličtině znamená „sraženina“, „hrozen (hrozen)“, „shluk (hvězd)“ atd. Tento termín neobvykle dobře zapadá do vědecké terminologie, protože jeho první slabika odpovídá tradiční termín „třída“ a druhý, jak to bylo, označuje jeho umělý původ. Nepochybujeme o tom, že terminologie shlukové analýzy nahradí všechny konstrukty dříve používané pro tento účel (neřízené rozpoznávání vzorů, stratifikace, taxonomie, automatická klasifikace atd.). Potenciální možnosti shlukové analýzy jsou zřejmé pro řešení řekněme problémů identifikace skupin podniků působících v podobných podmínkách nebo s podobnými výsledky, homogenních skupin obyvatelstva v různých aspektech života či životního stylu obecně atd.
Jako vědecký směr se shluková analýza deklarovala v polovině 60. let a od té doby se rychle rozvíjí a je jedním z nejintenzivnějších odvětví statistické vědy. Stačí říci, že pouze řada monografií o shlukové analýze, voj obecná schémata použití metod shlukové analýzy implementovaných v poměrně názorných tabulkách; doporučující charakter prezentace.
Tyto přednosti určují samostatné místo knihy I. D. Mandela mezi ostatními publikacemi.
Nedostatkem knihy je nejednoznačnost některých doporučení a chybějící systematická analýza problematiky využití metod shlukové analýzy v předmětových socioekonomických aplikacích. Je pravda, že toto je způsobeno nedostatečným využíváním shlukové analýzy v této oblasti.
Kniha poskytuje odrazový můstek, jehož použití usnadňuje postup v nejtěžší problematice jakékoli teorie – praktickém využití nástrojů, které poskytuje.
B. G. Mirkin
Témata výzkumu sahají od analýzy morfologie mumifikovaných hlodavců na Nové Guineji po studium výsledků hlasování amerických senátorů, od analýzy behaviorálních funkcí zmrazených švábů při jejich rozmrazení až po studium geografického rozšíření. některých druhů lišejníků v Saskatchewanu.
Tato exploze publikací měla obrovský dopad na vývoj a aplikaci shlukové analýzy. Ale bohužel existují i negativní stránky. Rychlý nárůst publikací o shlukové analýze vedl k vytvoření seskupení uživatelů a v důsledku toho k vytvoření žargonu používaného pouze skupinami, které je vytvořily (Blashfield a Aldenderfer, 1978; Blashfield, 1980).
O tvorbě žargonu specialisty v oboru společenské vědy o tom svědčí například různorodá terminologie vztahující se k Wardově metodě. "Wardova metoda" se v literatuře nazývá jinak. Jsou známy alespoň čtyři další její názvy: „metoda minimálního rozptylu“, „metoda součtu čtvercových chyb“, „minimalizace hierarchického seskupení“ a „HGROUP“. První dva názvy jednoduše odkazují na kritérium, jehož optimum je určeno Wardovou metodou, zatímco třetí se vztahuje k součtu čtvercových chyb, což je monotónní stopová transformace matice W, vnitroskupinové kovarianční matice. Konečně, široce používaný název "HGROUP" je název populární počítačový program, která implementuje Wardovu metodu (Veldman, 1967).
Tvoření žargonu brání rozvoji mezioborových vazeb, brzdí efektivní srovnání metodologie a výsledky aplikace shlukové analýzy v různých oblastech vědy, vede ke zbytečnému úsilí (znovuvynalézání stejných algoritmů) a nakonec nedává novým uživatelům hluboké pochopení metod, které si zvolili (Blashfield a aldenderfer, 1978 ). Například jedna společenskovědní studie (Rogers a Linden, 1973) porovnávala tři různé metody shlukování pomocí stejných dat. Tyto metody nazvali takto: „hierarchické seskupení“, „hierarchické shlukování neboli HCG“ a „shluková analýza“. A žádný z těchto názvů nebyl známý metodám shlukování. Začínající uživatel programů pro analýzu shluků bude zmaten všemi existujícími názvy a nebude je moci přiřadit k jiným popisům metod shlukování. Zkušení uživatelé se při porovnávání svých výzkumů s podobnou prací ocitnou ve složité pozici. Možná zacházíme do extrémů, ale žargon je vážný problém.
V posledních letech se vývoj shlukové analýzy poněkud zpomalil, soudě podle počtu publikací a počtu oborů, kde je tato metoda aplikována. Dá se říci, že v současnosti psychologie, sociologie, biologie, statistika a další technické obory vstoupit do fáze konsolidace ve vztahu ke shlukové analýze.
Počet článků vychvalujících přednosti shlukové analýzy postupně klesá. Zároveň přibývá prací, ve kterých je na kontrolních datech porovnávána použitelnost různých metod shlukování. V literatuře je věnována větší pozornost aplikacím. Mnoho studií je zaměřeno na vývoj praktických opatření pro testování platnosti výsledků získaných pomocí shlukové analýzy. To vše svědčí o seriózních pokusech o vytvoření rozumné statistické teorie shlukových metod.
