Hierarchické shlukování - Hierarchical clustering

Část série na
Strojové učení a dolování dat
Problémy Klasifikace Shlukování Regrese Detekce anomálií Čištění dat AutoML Pravidla asociace Posílení učení Strukturovaná predikce Funkce inženýrství Funkce učení Online učení Učení pod dohledem Učení bez dozoru Naučit se řadit Gramatická indukce
Učení pod dohledem ( klasifikace  • regrese ) Rozhodovací stromy Soubory Pytlování Posílení Náhodný les k -NN Lineární regrese Naivní Bayes Umělé neuronové sítě Logistická regrese Perceptron Relevantní vektorový stroj (RVM) Podpora vektorového stroje (SVM)
Shlukování BŘÍZA LÉK Hierarchický k -znamená Očekávání – maximalizace (EM) DBSCAN OPTIKA Střední posun
Redukce rozměrů Faktorová analýza CCA ICA LDA NMF PCA PGD t-SNE
Strukturovaná predikce Grafické modely Bayesova síť Podmíněné náhodné pole Skrytý Markov
Detekce anomálií k -NN Faktor místní odlehlosti
Umělá neurální síť Autoencoder Kognitivní výpočetní technika Hluboké učení DeepDream Vícevrstvý perceptron RNN LSTM GRU ESN Omezený stroj Boltzmann GAN SOM Konvoluční neurální síť U-Net Transformátor Rozšíření neuronové sítě Memtranzistor Elektrochemická RAM (ECRAM)
Posílení učení Q-učení SARSA Časový rozdíl (TD)
Teorie Kompromis předpojatosti a rozptylu Teorie počítačového učení Empirická minimalizace rizik Occam učení Učení PAC Statistické učení VC teorie
Místa strojového učení NeurIPS ICML ML JMLR ArXiv: cs.LG
Související články Glosář umělé inteligence Seznam datových sad pro výzkum strojového učení Nástin strojového učení
proti t E

V dolování dat a statistikách je hierarchické klastrování (také nazývané hierarchická klastrová analýza nebo HCA ) metodou klastrové analýzy, která se snaží vybudovat hierarchii klastrů. Strategie pro hierarchické seskupování obecně spadají do dvou typů:

• Aglomerativní : Jedná se o přístup „ zdola nahoru “: každé pozorování začíná ve svém vlastním klastru a páry klastrů se sloučí, když se člověk posune v hierarchii nahoru.
• Rozdělující : Toto je přístup „ shora dolů “: všechna pozorování začínají v jednom klastru a rozdělení se provádí rekurzivně, jak se člověk posouvá po hierarchii.

Obecně platí, že fúze a rozdělení jsou stanoveny chamtivým způsobem. Výsledky hierarchického shlukování jsou obvykle prezentovány v dendrogramu .

Standardní algoritmus pro hierarchické aglomerativní clustering (HAC) má složitost času na a vyžaduje paměť, která dělá to příliš pomalá pro datové soubory i média. Nicméně, v některých speciálních případech optimální efektivní Aglomerativní metody (složitosti ) jsou známé: Dřez pro jedno-vazbou a CLINK pro kompletní-vazbou shlukování . S hromadou lze dobu běhu obecného případu snížit na , zlepšení na výše uvedené hranici , za cenu dalšího zvýšení požadavků na paměť. V mnoha případech jsou režijní náklady na tento přístup příliš velké na to, aby bylo prakticky použitelné. ${\displaystyle {\mathcal {O}}(n^{3})}$${\displaystyle \Omega (n^{2})}$${\displaystyle {\mathcal {O}}(n^{2})}$${\displaystyle {\mathcal {O}}(n^{2}\log n)}$${\displaystyle {\mathcal {O}}(n^{3})}$

S výjimkou zvláštního případu jednoduchého propojení nelze zaručit nalezení optimálního řešení u žádného z algoritmů (kromě vyčerpávajícího vyhledávání v ). ${\displaystyle {\mathcal {O}}(2^{n})}$

Rozdělující shlukování s vyčerpávajícím hledáním je , ale je běžné používat rychlejší heuristiku k výběru rozdělení, například k -means . ${\displaystyle {\mathcal {O}}(2^{n})}$

Odlišnost klastru

Aby bylo možné rozhodnout, které klastry by měly být kombinovány (pro aglomerační) nebo kde by měly být klastry rozděleny (pro dělící), je zapotřebí určitá míra odlišnosti mezi sadami pozorování. Ve většině metod hierarchického shlukování je toho dosaženo použitím vhodné metriky (míra vzdálenosti mezi dvojicemi pozorování) a kritériem vazby, které specifikuje odlišnost množin jako funkci párových vzdáleností pozorování v sadách.

Metrický

Volba vhodné metriky ovlivní tvar klastrů, protože některé prvky mohou být v rámci jedné metriky k sobě relativně blíže než jiné. Například ve dvou dimenzích je podle metriky vzdálenosti na Manhattanu vzdálenost mezi počátkem (0,0) a (0,5, 0,5) stejná jako vzdálenost mezi počátkem a (0, 1), zatímco pod euklidovskou vzdáleností metrický, ten je přísně větší.

Některé běžně používané metriky pro hierarchické klastrování jsou:

Jména	Vzorec
Euklidovská vzdálenost	${\displaystyle \|a-b\|_{2}={\sqrt {\sum _{i}(a_{i}-b_{i})^{2}}}}$
Čtvercová euklidovská vzdálenost	${\displaystyle \|a-b\|_{2}^{2}=\sum _{i}(a_{i}-b_{i})^{2}}$
Vzdálenost Manhattanu (nebo městského bloku)	${\displaystyle \|a-b\|_{1}=\sum _{i}|a_{i}-b_{i}|}$
Maximální vzdálenost (nebo Chebyshevova vzdálenost)	${\displaystyle \|a-b\|_{\infty }=\max _{i}|a_{i}-b_{i}|}$
Mahalanobisova vzdálenost	${\displaystyle {\sqrt {(a-b)^{\top }S^{-1}(a-b)}}}$kde S je kovarianční matice

Pro textová nebo jiná nečíselná data se často používají metriky jako Hammingova vzdálenost nebo Levenshteinova vzdálenost .

Euklidovské a Manhattanské vzdálenosti jsou speciální případy zobecněné Minkowského vzdálenosti s p = 1 (pro Manhattan) a p = 2 (pro Euclidean).

Existuje několik dalších opatření odlišnosti. Zejména vzdálenosti založené na korelaci - Pearson, Eisen kosinus, Spearman, Kendall korelační vzdálenosti, které jsou široce používány pro analýzu dat genové exprese. Vzdálenost založená na korelaci je definována odečtením korelačního koeficientu od 1. Stručně řečeno, vzdálenosti založené na korelaci nelze použít jako metrické, zatímco druhá odmocnina může být.

Přezkum klastrové analýzy ve výzkumu psychologie zdraví zjistil, že nejběžnějším měřením vzdálenosti v publikovaných studiích v této oblasti výzkumu je euklidovská vzdálenost nebo čtvercová euklidovská vzdálenost.

Kritéria propojení

Kritérium vazby určuje vzdálenost mezi sadami pozorování jako funkci párových vzdáleností mezi pozorováními.

Některá běžně používaná kritéria propojení mezi dvěma soubory pozorování A a B jsou:

Jména	Vzorec
Klastrování s maximálním nebo úplným propojením	${\displaystyle \max \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Klastrování s minimem nebo s jedním spojením	${\displaystyle \min \,\{\,d(a,b):a\in A,\,b\in B\,\}.}$
Nevážené průměrné seskupování vazeb (nebo UPGMA )	${\displaystyle {\frac {1}{|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b).}$
Vážený průměr shlukování vazeb (nebo WPGMA )	${\displaystyle d(i\cup j,k)={\frac {d(i,k)+d(j,k)}{2}}.}$
Klastrování těžiště nebo UPGMC	${\displaystyle \|c_{s}-c_{t}\|}$kde a jsou centroidy klastrů s a t . ${\displaystyle c_{s}}$${\displaystyle c_{t}}$
Minimální shlukování energie	${\displaystyle {\frac {2}{nm}}\sum _{i,j=1}^{n,m}\|a_{i}-b_{j}\|_{2}-{\frac {1}{n^{2}}}\sum _{i,j=1}^{n}\|a_{i}-a_{j}\|_{2}-{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}\|b_{i}-b_{j}\|_{2}}$

kde d je zvolená metrika. Mezi další kritéria propojení patří:

• Součet všech rozptylů uvnitř klastru.
• Zvýšení rozptylu pro slučovaný klastr ( Wardovo kritérium ).
• Pravděpodobnost, že kandidátské klastry vzniknou ze stejné distribuční funkce (V-vazba).
• Součin in-degree a out-degree na k-nejbližším sousedním grafu (vazba grafového stupně).
• Přírůstek nějakého deskriptoru klastru (tj. Veličiny definované pro měření kvality klastru) po sloučení dvou klastrů.

Diskuse

Hierarchické shlukování má jasnou výhodu v tom, že lze použít jakékoli platné měřítko vzdálenosti. Ve skutečnosti nejsou nutná samotná pozorování: používá se pouze matice vzdáleností.

Aglomerativní shlukování příklad

Nezpracovaná data

Předpokládejme například, že tato data mají být seskupena a euklidovská vzdálenost je metrika vzdálenosti .

Dendrogram hierarchického shlukování by byl takový:

Tradiční reprezentace

Řezání stromu v dané výšce poskytne seskupení oddílů se zvolenou přesností. V tomto případě řezání po druhém řádku (shora) dendrogramu poskytne klastry {a} {bc} {de} {f}. Řezáním po třetím řádku získáte shluky {a} {bc} {def}, což je hrubší shlukování, s menším počtem, ale většími klastry.

Tato metoda vytváří hierarchii z jednotlivých prvků postupným slučováním klastrů. V našem příkladu máme šest prvků {a} {b} {c} {d} {e} a {f}. Prvním krokem je určit, které prvky se mají v clusteru sloučit. Obvykle chceme vzít dva nejbližší prvky podle zvolené vzdálenosti.

Volitelně lze v této fázi také sestrojit matici vzdáleností , kde číslo v i -tém řádku j -týho sloupce je vzdálenost mezi i -tými a j -tými prvky. Poté, jak klastrování postupuje, jsou řádky a sloupce sloučeny, protože jsou sloučeny klastry a aktualizovány vzdálenosti. Toto je běžný způsob implementace tohoto typu klastrování a má výhodu v mezipaměti vzdáleností mezi klastry. Jednoduchý algoritmus shlukování aglomerací je popsán na stránce klastrování s jedním spojením ; lze jej snadno přizpůsobit různým typům propojení (viz níže).

Předpokládejme, že jsme spojili dva nejbližší prvky b a c , nyní máme následující klastry { a }, { b , c }, { d }, { e } a { f } a chceme je dále sloučit. K tomu musíme vzít vzdálenost mezi {a} a {bc}, a proto definovat vzdálenost mezi dvěma klastry. Obvykle je vzdálenost mezi dvěma klastry a jedním z následujících: ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$

• Maximální vzdálenost mezi prvky každého klastru (nazývaná také klastrování úplných vazeb ):

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• Minimální vzdálenost mezi prvky každého klastru (nazývaná také klastrování s jedním spojením ):

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• Průměrná vzdálenost mezi prvky každého klastru (také nazývaná průměrná klastrová vazba, používaná např. V UPGMA ):

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}$

• Součet všech rozptylů uvnitř klastru.
• Zvýšení rozptylu pro slučovaný klastr ( Wardova metoda )
• Pravděpodobnost, že kandidátské klastry vzniknou ze stejné distribuční funkce (V-vazba).

V případě svázaných minimálních vzdáleností je náhodně vybrán pár, takže je možné generovat několik strukturálně odlišných dendrogramů. Alternativně mohou být všechny svázané páry spojeny současně, čímž se vytvoří jedinečný dendrogram.

Vždy se můžete rozhodnout zastavit shlukování, pokud existuje dostatečně malý počet klastrů (kritérium počtu). Některé vazby mohou také zaručit, že k aglomeraci dochází ve větší vzdálenosti mezi klastry než předchozí aglomerace, a pak lze shlukování zastavit, když jsou klastry příliš daleko od sebe, aby mohly být sloučeny (kritérium vzdálenosti). To však neplatí např. Pro těžiště vazby, kde může dojít k takzvaným zvratům (inverze, odchylky od ultrametricity).

Rozdělující shlukování

Základní princip dělícího seskupování byl publikován jako algoritmus DIANA (DIvisive ANAlysis Clustering). Zpočátku jsou všechna data ve stejném klastru a největší klastr je rozdělen, dokud není každý objekt oddělený. Protože existují způsoby rozdělení každého klastru, jsou zapotřebí heuristiky. DIANA vybere objekt s maximální průměrnou odlišností a poté přesune do tohoto klastru všechny objekty, které jsou více podobné novému klastru než zbytku. ${\displaystyle O(2^{n})}$

Software

Implementace open source

Hierarchické shlukování dendrogram z Iris datové sady (pomocí R ). Zdroj

Hierarchické klastrování a interaktivní vizualizace dendrogramu v sadě Orange pro dolování dat .

• ALGLIB implementuje několik hierarchických klastrových algoritmů (single-link, Complete-link, Ward) v C ++ a C# s pamětí O (n²) a dobou běhu O (n³).
• ELKI obsahuje více hierarchických shlukovacích algoritmů, různé propojovací strategie a také zahrnuje efektivní algoritmy SLINK, CLINK a Anderberg, flexibilní klastrovou extrakci z dendrogramů a různé další algoritmy klastrové analýzy .
• Octave , analog GNU k MATLABu, implementuje hierarchické shlukování ve funkci „propojení“.
• Orange , softwarová sada pro dolování dat, zahrnuje hierarchické shlukování s interaktivní vizualizací dendrogramu.
• R má mnoho balíčků, které poskytují funkce pro hierarchické klastrování.
• SciPy implementuje hierarchické klastrování v Pythonu, včetně efektivního algoritmu SLINK.
• scikit-learn také implementuje hierarchické klastrování v Pythonu.
• Weka zahrnuje hierarchickou klastrovou analýzu.

Komerční implementace

• MATLAB obsahuje hierarchickou klastrovou analýzu.
• SAS zahrnuje hierarchickou klastrovou analýzu v PROC CLUSTER.
• Mathematica obsahuje balíček hierarchického shlukování.
• NCSS zahrnuje hierarchickou klastrovou analýzu.
• SPSS zahrnuje hierarchickou klastrovou analýzu.
• Qlucore Omics Explorer obsahuje hierarchickou klastrovou analýzu.
• Stata zahrnuje hierarchickou klastrovou analýzu.
• CrimeStat obsahuje algoritmus hierarchického clusteru nejbližšího souseda s grafickým výstupem pro geografický informační systém.

Viz také

Reference

Další čtení

• Kaufman, L .; Rousseeuw, PJ (1990). Hledání skupin v datech: Úvod do klastrové analýzy (1. vydání). New York: John Wiley. ISBN 0-471-87876-6.
• Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2009). „14.3.12 Hierarchické shlukování“ . The Elements of Statistical Learning (2. vyd.). New York: Springer. s. 520–8. ISBN 978-0-387-84857-0. Archivováno z originálu (PDF) dne 2009-11-10 . Citováno 2009-10-20 .