Hierarchické shlukování - Hierarchical clustering

v dolování dat a statistika, hierarchické shlukování (také zvaný hierarchická shluková analýza nebo HCA) je metoda shluková analýza který se snaží vybudovat hierarchie shluků. Strategie pro hierarchické shlukování se obecně dělí na dva typy:^[1]

• Aglomerativní: Toto je „zdola nahoru "přístup: každé pozorování začíná ve svém vlastním klastru a páry klastrů jsou sloučeny, když se jeden posune v hierarchii nahoru."
• Rozporuplné: Toto je „vzhůru nohama "přístup: všechna pozorování začínají v jednom klastru a rozdělení se provádí rekurzivně, když se člověk pohybuje dolů v hierarchii.

Obecně platí, že sloučení a rozdělení jsou určeny v a chamtivý způsob. Výsledky hierarchického shlukování^[2] jsou obvykle uvedeny v a dendrogram.

Standardní algoritmus pro hierarchické aglomerativní shlukování (HAC) má časová složitost z ${ displaystyle { mathcal {O}} (n ^ {3})}$ a vyžaduje ${ displaystyle Omega (n ^ {2})}$ paměť, což je příliš pomalé i pro střední datové sady. Pro některé speciální případy jsou však optimální účinné aglomerativní metody (složité ${ displaystyle { mathcal {O}} (n ^ {2})}$) jsou známy: SLINK^[3] pro jednoduchá vazba a CLINK^[4] pro shlukování úplného propojení. S halda, lze dobu běhu obecného případu zkrátit na ${ displaystyle { mathcal {O}} (n ^ {2} log n)}$, vylepšení výše zmíněné vazby ${ displaystyle { mathcal {O}} (n ^ {3})}$za cenu dalšího zvyšování požadavků na paměť. V mnoha případech jsou režijní náklady paměti tohoto přístupu příliš velké, aby byly prakticky použitelné.

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

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

Klastrová odlišnost

Aby bylo možné rozhodnout, které klastry by měly být kombinovány (pro aglomeraci) nebo kde by měl být klastr rozdělen (pro rozdělování), je nutná míra odlišnosti mezi soubory pozorování. Ve většině metod hierarchického shlukování je toho dosaženo použitím vhodného metrický (míra vzdálenost mezi dvojicemi pozorování) a kritérium vazby, které specifikuje odlišnost množin jako funkci párových vzdáleností pozorování v množinách.

Metrický

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

Některé běžně používané metriky pro hierarchické shlukování jsou:^[5]

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} = součet _ {i} (a_ {i} -b_ {i}) ^ {2}}$
Vzdálenost na Manhattanu	${ displaystyle | a-b | _ {1} = součet _ {i} | a_ {i} -b_ {i} |}$
Maximální 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

U textových nebo jiných nečíselných dat jsou to metriky, jako je Hammingova vzdálenost nebo Levenshteinova vzdálenost jsou často používány.

Přehled shlukové analýzy ve výzkumu psychologie zdraví zjistil, že nejběžnějším měřítkem vzdálenosti v publikovaných studiích v této oblasti výzkumu je euklidovská vzdálenost nebo čtvercová euklidovská vzdálenost.^{[Citace je zapotřebí ]}

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 sadami pozorování A a B jsou:^[6][7]

Jména	Vzorec
Maximum nebo shlukování úplného propojení	${ displaystyle max , {, d (a, b): a v A, , b v B , }.}$
Minimální nebo shlukování s jedním spojením	${ displaystyle min , {, d (a, b): a v A, , b v B , }.}$
Nevážený průměr shlukování vazeb (nebo UPGMA )	${ displaystyle { frac {1} {| A | cdot | B |}} sum _ {a v A} sum _ {b v 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}}.}$
Shlukování vazeb těžiště nebo UPGMC	${ displaystyle | c_ {s} -c_ {t} |}$ kde ${ displaystyle c_ {s}}$ a ${ displaystyle c_ {t}}$ jsou centroidy klastrů s a t, resp.
Minimální shlukování energie	${ displaystyle { frac {2} {nm}} součet _ {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 odchylek uvnitř clusteru.
• Zvýšení rozptylu pro slučovaný klastr (Wardovo kritérium ).^[8]
• Pravděpodobnost, že se klastry kandidátů objeví ze stejné distribuční funkce (V-vazba).
• Produkt součinu stupně a stupně na grafu k-nejbližšího souseda (vazba stupně grafu).^[9]
• Přírůstek nějakého deskriptoru klastru (tj. Množství definované pro měření kvality klastru) po sloučení dvou klastrů.^[10][11][12]

Diskuse

Hierarchické shlukování má zřetelnou výhodu v tom, že lze použít jakoukoli platnou míru vzdálenosti. Samotná pozorování ve skutečnosti nejsou nutná: používá se pouze matice vzdáleností.

Příklad shlukování aglomerací

Nezpracovaná data

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

Hierarchické shlukování dendrogram bude jako takový:

Tradiční zastoupení

Řezáním stromu v dané výšce získáte rozdělení shluků s vybranou přesností. V tomto příkladu řezání za druhou řadou (shora) dendrogram získá klastry {a} {b c} {d e} {f}. Řezáním po třetím řádku se získá shluky {a} {b c} {d e f}, což je hrubší shlukování, s menším počtem, ale většími shluky.

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čení, které prvky se mají v clusteru sloučit. Obvykle chceme vzít dva nejbližší prvky podle zvolené vzdálenosti.

Volitelně lze také sestrojit a matice vzdálenosti v této fázi, kdy číslo v i-házet j-tý sloupec je vzdálenost mezi i-th a j-té prvky. Poté, jak postupuje shlukování, jsou řádky a sloupce sloučeny, protože jsou seskupeny a aktualizovány vzdálenosti. Toto je běžný způsob implementace tohoto typu klastrování a má výhodu ukládání mezipaměti vzdáleností mezi klastry. Jednoduchý aglomerativní shlukovací algoritmus je popsán v shlukování s jedním spojením strana; 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 chcete je dále sloučit. K tomu musíme vzít vzdálenost mezi {a} a {b c}, a proto definovat vzdálenost mezi dvěma klastry. Obvykle vzdálenost mezi dvěma klastry ${ displaystyle { mathcal {A}}}$ a ${ displaystyle { mathcal {B}}}$ je jedním z následujících:

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

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

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

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

• Průměrná vzdálenost mezi prvky každého klastru (nazývaná také průměrná shluková vazba, použitá 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 odchylek uvnitř clusteru.
• Zvýšení rozptylu pro slučovaný klastr (Wardova metoda^[8])
• Pravděpodobnost, že se klastry kandidátů objeví 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, který je schopen 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.^[13]

Vždy je možné se rozhodnout zastavit shlukování, když existuje dostatečně malý počet shluků (kritérium počtu). Některá propojení mohou také zaručit, že ke aglomeraci dochází ve větší vzdálenosti mezi klastry než předchozí aglomerace, a pak je možné zastavit shlukování, když jsou klastry příliš daleko od sebe, aby je bylo možné sloučit (kritérium vzdálenosti). To však neplatí například pro těžiště, kde dochází k tzv. Obrácení^[14] (inverze, odchylky od ultrametricity).

Rozporuplné shlukování

Základní princip dělícího shlukování byl publikován jako algoritmus DIANA (DIvisive ANAlysis Clustering).^[15] Zpočátku jsou všechna data ve stejném clusteru a největší cluster je rozdělen, dokud není každý objekt samostatný.Because there exist ${ displaystyle O (2 ^ {n})}$ způsoby rozdělení každého shluku, heuristika je nutná. DIANA vybere objekt s maximální průměrnou odlišností a poté přesune všechny objekty do tohoto klastru, které jsou více podobné novému klastru než zbytku.

Software

Open source implementace

Hierarchické shlukování dendrogram z Datová sada Iris (použitím R ). Zdroj

Hierarchické shlukování a interaktivní vizualizace dendrogramu ve Windows Orange data mining suite.

• 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 zahrnuje několik hierarchických klastrových algoritmů, různé strategie propojení a také zahrnuje efektivní SLINK,^[3] CINKAT^[4] a Anderbergovy algoritmy, flexibilní extrakce clusteru z dendrogramů a různých dalších shluková analýza algoritmy.
• Oktáva, GNU analogicky k MATLAB implementuje hierarchické shlukování do funkce "propojení".
• oranžový, softwarová sada pro dolování dat, zahrnuje hierarchické shlukování s interaktivní vizualizací dendrogramu.
• R má mnoho balíčků, které poskytují funkce pro hierarchické shlukování.
• SciPy implementuje hierarchické shlukování v Pythonu, včetně efektivního algoritmu SLINK.
• scikit-učit se také implementuje hierarchické shlukování v Pythonu.
• Weka zahrnuje hierarchickou klastrovou analýzu.

Komerční implementace

• MATLAB zahrnuje hierarchickou klastrovou analýzu.
• SAS zahrnuje hierarchickou klastrovou analýzu v PROC CLUSTER.
• Mathematica zahrnuje balíček hierarchických klastrů.
• 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 zahrnuje hierarchický clusterový algoritmus nejbližšího souseda s grafickým výstupem pro Geografický informační systém.

Viz také

Reference

Další čtení

• Kaufman, L .; Rousseeuw, P.J. (1990). Hledání skupin v datech: Úvod do klastrové analýzy (1. vyd.). New York: John Wiley. ISBN  0-471-87876-6.
• Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). „14.3.12 Hierarchické shlukování“. Prvky statistického učení (2. vyd.). New York: Springer. str. 520–528. ISBN  978-0-387-84857-0. Archivovány od originál (PDF) dne 10. 11. 2009. Citováno 2009-10-20.