Hierarchické shlukování

Hierarchické shlukování (také grafové shlukovací algoritmy a hierarchická shluková analýza ) je sada algoritmů řazení dat zaměřená na vytvoření hierarchie ( stromu ) vnořených shluků. Existují dvě třídy metod hierarchického shlukování:

Aglomerativní metody ( angl. aglomerative ): nové shluky vznikají spojením menších shluků a vzniká tak strom od listů po kmen;
Dělící nebo divizní metody ( angl. divisive ): nové shluky vznikají dělením větších shluků na menší a tím vzniká strom od kmene až po listy.

Hierarchické shlukovací algoritmy předpokládají, že analyzovaná množina objektů se vyznačuje určitým stupněm konektivity. Podle počtu znaků se někdy rozlišují monotetické a polytetické způsoby klasifikace. Stejně jako většina vizuálních způsobů znázornění závislostí grafy rychle ztrácejí viditelnost s rostoucím počtem shluků. Pro konstrukci grafů existuje řada specializovaných programů .

Dendrogram

Dendrogram je obvykle chápán jako strom vytvořený z matice měření blízkosti. Dendrogram umožňuje znázornit vztah mezi objekty z dané množiny [1] . Vytvoření dendrogramu vyžaduje matici podobnosti (nebo rozdílu ) , která určuje úroveň podobnosti mezi páry shluků. Častěji se používají aglomerativní metody.

Pro sestavení matice podobnosti (rozdílu) je nutné nastavit míru vzdálenosti mezi dvěma shluky. Nejčastěji používané metody určování vzdálenosti ( anglicky sorting strategy ) [2] :

Metoda jediného propojení je také známá jako „metoda nejbližšího souseda“ . Předpokládá se, že vzdálenost mezi dvěma shluky je rovna minimální vzdálenosti mezi dvěma prvky z různých shluků: , kde je vzdálenost mezi prvky a patřícími do shluků a ${\displaystyle \min \,\{\,d(a,b):a\v A,\,b\v B\,\))$ $d(a,b)$ $A$ $b$ $A$ $B$
Metoda úplného propojení jetaké známá jako metoda vzdáleného souseda . Předpokládá se, že vzdálenost mezi dvěma shluky je rovna maximální vzdálenosti mezi dvěma prvky z různých shluků:; ${\displaystyle \max \,\{\,d(a,b):a\v A,\,b\v B\,\))$
Metoda párových skupin pomocí aritmetického průměru :
- Nevážený ( anglicky UPGMA ). Předpokládá se, že vzdálenost mezi dvěma shluky je rovna průměrné vzdálenosti mezi prvky těchto shluků: , kde je vzdálenost mezi prvky a patřícími do shluků a , a jsou mohutnosti shluků. ${1 \over {|A|\cdot |B|}}\součet _{a\in A}\součet _{b\in B}d(a,b)$ $d(a,b)$ $A$ $b$ $A$ $B$ $|A|$ $|B|$
- Vážené ( anglicky WPGMA ).
Metoda těžiště ( anglická metoda párových skupin s použitím průměru těžiště ):
- Nevážený ( anglicky UPGMC ). Předpokládá se, že vzdálenost mezi shluky je rovna vzdálenosti jejich těžišť (těžišť) [3] : , kde a jsou těžiště a . $\|c_{A}-c_{B}\|$ $c_{A}$ $c_{B}$ $A$ $B$
- Vážené ( anglicky WPGMC ).
Wardova metoda . _ _ Na rozdíl od jiných metod shlukové analýzy se zde k odhadu vzdáleností mezi shluky používají metody disperzní analýzy. Jako vzdálenost mezi shluky bereme nárůst součtu čtverců vzdáleností objektů od středu shluku, získaný jako výsledek jejich sjednocení [4] : . V každém kroku algoritmu se kombinují dva shluky, které vedou k minimálnímu zvýšení rozptylu. Tato metoda se používá pro problémy s těsně rozmístěnými shluky. ${\displaystyle \Delta =\sum _{i}{(x_{i}-{\bar {x)))^{2}}-\součet _{x_{i}\in A}(x_{i} -{\bar {a)))^{2}-\součet _{x_{i}\in B}(x_{i}-{\bar {b)))^{2))$

Pro první tři metody existuje obecný vzorec navržený A. N. Kolmogorovem pro míry podobnosti [5] :

K_{\eta }([i,j],k)=\left[{\frac {(n_{i}K(i,k)^{\eta }+(n_{j}K(j,k) ^{\eta })}{n_{i}+n_{j}}}\right]^{{\frac {1}{\eta }}},-{\mathcal {1}}\leqslant \eta \ leqslant + {\mathcal {1}}

kde je skupina dvou objektů (shluků) a ; — objekt (shluk), se kterým se hledá podobnost specifikované skupiny; je počet prvků ve shluku ; je počet prvků ve shluku . Pro vzdálenosti existuje podobný Lance-Williamsův vzorec [6] . $[i,j]$ $i$ $j$ $k$ $n_{i}$ $i$ $n_{j}$ $j$

Korelativní Plejády

Široce používán v geobotanice a květinářství . Často se jim říká korelační plejády [7] [8] [9] [10] .

Speciálním případem je metoda známá jako metoda konstrukce optimálních stromů (dendritů) , kterou navrhl matematik lvovské školy Hugo Steinhaus [11] , později metodu vyvinuli matematici vratislavské taxonomické školy [12] . Dendrity by také neměly tvořit cykly. Částečně můžete použít orientované oblouky grafů pomocí dalších inkluzních opatření (asymetrické míry podobnosti).

Czekanowskiho diagram

Metodu „diagonalizace“ diferenční matice a grafické znázornění shluků podél hlavní diagonály diferenční matice (Czekanowskiho diagram) poprvé navrhl Jan Czekanowski v roce 1909 [13] . Zde je popis metodiky:

Podstata této metody spočívá ve skutečnosti, že celá amplituda získaných hodnot podobnosti je rozdělena do několika tříd a poté jsou v matici hodnot podobnosti tyto hodnoty nahrazeny stínováním, které je odlišné pro každá třída a pro vyšší třídy podobnosti se obvykle používá tmavší stínování. Poté změnou pořadí popisů v tabulce zajistí, že bude následovat více podobných popisů [14]

Uveďme hypotetický příklad získání výše uvedeného diagramu. Základem metody je konstrukce tranzitivní uzavírací matice [15] .

Chcete-li vytvořit tranzitivní uzavírací matici, vezměme jednoduchou matici podobnosti a vynásobte ji samotnou:

K^{{(2)}}(i,j)=max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q ,j)))

kde je prvek na průsečíku -tého řádku a -tého sloupce v nové (druhé) matici získané po první iteraci; je celkový počet řádků (sloupců) matice podobnosti. Tento postup musí pokračovat, dokud se matice nestane idempotentní (tj. sobě podobná): , kde n je počet iterací. $K(i,j)$ $i$ $j$ $q$ $K^{{(n)}}(i,j)=K^{{(n-1)}}(i,j)$

Dále transformujeme matici tak, aby blízké číselné hodnoty byly blízko. Pokud je každé číselné hodnotě přiřazena barva nebo odstín barvy (jako v našem případě), pak dostaneme klasický Czekanowski diagram. Tradičně tmavší barva odpovídá větší podobnosti a světlejší barva odpovídá menší. V tomto je podobná teplotní mapě pro matici vzdálenosti .

Viz také

Zdroje a poznámky

↑ Zhambyu M. Hierarchická shluková analýza a korespondence. — M.: Finance a statistika, 1988. — 345 s.
↑ Klasifikace a shluk. Ed. J. Wen Raizina. M.: Mir, 1980. 390 s.
↑ Sneath PHA, Sokal RR Numerická taxonomie: Principy a postupy numerické klasifikace. - San-Francisco: Freeman, 1973. - 573 s.
↑ Ward JH Hierarchické seskupení k optimalizaci objektivní funkce // J. of the American Statistical Association, 1963. - 236 s.
↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Aplikovaná statistika: Klasifikace a redukce rozměrů. - M .: Finance a statistika, 1989. - 607 s.
↑ Lance GN, Willams WT Obecná teorie klasifikačních třídicích strategií. 1. Hierarchické systémy // Porov. J. 1967. č. 9. str. 373-380.
↑ von Terentjev PV Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. č. 23(1-2). S. 23-51.
↑ Terentiev P. V. Metoda korelačních plejád // Vestn. LGU. č. 9. 1959. S. 35-43.
↑ Terentiev P. V. Další vývoj metody korelačních plejád // Aplikace matematických metod v biologii. T. 1. L.: 1960. S. 42-58.
↑ Vyhandu L.K. O studiu víceatributových biologických systémů // Aplikace matematických metod v biologii. L.: vydání. 3. 1964. S. 19-22.
↑ Steinhaus G. Matematický kaleidoskop. — M.: Nauka, 1981. — 160 s.
↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropopol. 1951. T. 17. S. 193-211.
↑ Czekanowski J. Zur diferenciál Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
↑ Vasilevič V.I. Statistické metody v geobotanice. - L .: Nauka, 1969. - 232 s.
↑ Tamura S., Hiquchi S., Tanaka K. Klasifikace vzorů na základě fuzzy vztahu // IEEE transakce o systémech, člověku a kybernetice, 1971, SMC 1, č. 1, s. 61-67.

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-síť Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG