Konsenzuální shlukování - Consensus clustering

Konsenzuální shlukování je metoda agregace (potenciálně konfliktních) výsledků z více algoritmů shlukování. Také zvaný klastrové soubory^[1] nebo agregace klastrování (nebo oddílů), týká se situace, ve které bylo pro konkrétní datový soubor získáno několik různých (vstupních) klastrů a je žádoucí najít jediné (konsensuální) klastrování, které je v některých smysl než stávající shlukování.^[2] Konsenzuální shlukování je tedy problém sladit shlukovací informace o stejné datové sadě pocházející z různých zdrojů nebo z různých běhů stejného algoritmu. Když je obsaženo jako problém s optimalizací, je shoda shlukování známá jako střední oddíl a ukázalo se, že je NP-kompletní,^[3] i když je počet vstupních shluků tři.^[4] Konsenzuální shlukování pro učení bez dozoru je obdobné souborové učení v učení pod dohledem.

Problémy se stávajícími technikami vytváření klastrů

• Současné techniky vytváření klastrů dostatečně neodpovídají všem požadavkům.
• Řešení velkého počtu dimenzí a velkého počtu datových položek může být problematické z důvodu časové složitosti;
• Efektivita metody závisí na definici „vzdálenosti“ (pro seskupování podle vzdálenosti)
• Pokud zjevná míra vzdálenosti neexistuje, musíme ji „definovat“, což není vždy snadné, zejména v multidimenzionálních prostorech.
• Výsledek shlukovacího algoritmu (který může být v mnoha případech sám libovolný) lze interpretovat různými způsoby.

Odůvodnění použití shody shluků

U všech existujících technik vytváření klastrů existují potenciální nedostatky. To může způsobit, že interpretace výsledků bude obtížná, zejména pokud neexistují žádné znalosti o počtu klastrů. Metody klastrování jsou také velmi citlivé na počáteční nastavení klastrování, což může způsobit zesílení nevýznamných dat v nereiterativních metodách. Extrémně důležitým problémem v klastrové analýze je ověření výsledků klastrování, to znamená, jak získat důvěru v důležitost klastrů poskytovaných technikou klastrování (čísla klastrů a přiřazení klastrů). Chybí externí objektivní kritérium (ekvivalent známého označení třídy v analýze pod dohledem) a toto ověřování se stává poněkud nepolapitelným. Interaktivní sestupové metody seskupování, jako například SOM a k-znamená shlukování obejít některé z nedostatků hierarchické shlukování poskytnutím jednoznačně definovaných klastrů a hranic klastrů. Konsenzuální shlukování poskytuje metodu, která představuje shodu napříč několika běhy klastrového algoritmu, k určení počtu klastrů v datech a k posouzení stability objevených klastrů. Metodu lze také použít k vyjádření konsensu o více bězích klastrového algoritmu s náhodným restartem (jako je K-means, Bayesovské shlukování založené na modelu, SOM atd.), Aby se zohlednila jeho citlivost vůči počátečním podmínkám . Může poskytnout data pro vizualizační nástroj ke kontrole čísla klastru, členství a hranic. Chybí jim však intuitivní a vizuální přitažlivost hierarchických klastrových dendrogramů a počet klastrů je třeba zvolit a priori.

Montiho shlukovací algoritmus podle Montiho

Montiho shlukovací algoritmus podle Montiho^[5] je jedním z nejpopulárnějších shlukovacích algoritmů konsensu a používá se k určení počtu klastrů, ${displaystyle K}$. Vzhledem k datové sadě ${displaystyle N}$ celkový počet bodů do klastru, tento algoritmus funguje převzorkováním a seskupením dat pro každý z nich ${displaystyle K}$ a a ${displaystyle NXN}$ vypočítá se konsensuální matice, kde každý prvek představuje zlomek případů, kdy byly dva vzorky seskupeny dohromady. Dokonale stabilní matice by se skládala výhradně z nul a jedniček, představujících všechny dvojice vzorků, které se vždy shlukují dohromady nebo ne dohromady během všech opakovaných vzorkování. Pro odvození optimální lze použít relativní stabilitu konsensuálních matic ${displaystyle K}$.

Přesněji řečeno, vzhledem k sadě bodů ke shluku, ${displaystyle D = {e_ {1}, e_ {2}, ... e_ {N}}}$, nechť ${displaystyle D ^ {1}, D ^ {2}, ..., D ^ {H}}$ být seznam ${displaystyle H}$ pertubované (převzorkované) datové sady původního datového souboru ${displaystyle D}$a nechte ${displaystyle M ^ {h}}$ označit ${displaystyle NXN}$ matice konektivity vyplývající z použití klastrového algoritmu na datovou sadu ${displaystyle D ^ {h}}$. Záznamy z ${displaystyle M ^ {h}}$ jsou definovány takto:

${displaystyle M ^ {h} (i, j) = {egin {cases} 1, & {ext {if}} {ext {body i a j patří do stejného klastru}} 0, & {ext {jinak} } konec {případů}}}$

Nechat ${displaystyle I ^ {h}}$ být ${displaystyle NXN}$ matice identifikátoru, kde ${displaystyle (i, j)}$-tý záznam se rovná 1, pokud jsou body ${displaystyle i}$ a ${displaystyle j}$ jsou ve stejné narušené datové sadě ${displaystyle D ^ {h}}$a 0 jinak. Matice indikátorů se používá ke sledování, které vzorky byly vybrány během každé iterace převzorkování pro krok normalizace. Konsenzuální matice ${displaystyle C}$ je definována jako normalizovaný součet všech matic konektivity všech narušených datových sad a pro každou ${displaystyle K}$.

${displaystyle C (i, j) = left ({frac {extstyle sum _ {h = 1} ^ {H} M ^ {h} (i, j) displaystyle} {sum _ {h = 1} ^ {H} I ^ {h} (i, j)}} v pořádku)}$

To je vstup ${displaystyle (i, j)}$ v konsensuální matici je počet bodů ${displaystyle i}$ a ${displaystyle j}$ byly seskupeny společně děleno celkovým počtem případů, kdy byly vybrány společně. Matice je symetrická a každý prvek je definován v rozsahu ${displaystyle [0,1]}$. Pro každou se vypočítá konsensuální matice ${displaystyle K}$ k testování a stabilita každé matice, to je, jak daleko je matice směrem k matici dokonalé stability (pouze nuly a jedničky) se používá k určení optimální ${displaystyle K}$. Jedním ze způsobů kvantifikace stability systému ${displaystyle K}$th konsenzuální matice zkoumá svou křivku CDF (viz níže).

Potenciál přehnané interpretace Montiho konsensuálního klastrového algoritmu

Měření PAC (podíl nejednoznačného shlukování) vysvětleno. Optimální K je K s nejnižší hodnotou PAC.

Klastrování podle Montiho konsensu může být mocným nástrojem pro identifikaci klastrů, ale je třeba jej používat opatrně, jak ukazuje Şenbabaoğlu et al. ^[6] Ukázalo se, že Montiho konsensuální shlukovací algoritmus je schopen požadovat zjevnou stabilitu náhodného rozdělení nulových datových souborů získaných z unimodální distribuce, a má tedy potenciál vést ke skutečné interpretaci stability klastru ve skutečné studii.^[6][7] Pokud klastry nejsou dobře odděleny, shoda shlukování by mohla vést k závěru o zjevné struktuře, pokud neexistuje, nebo k deklaraci stability klastru, když je subtilní. Identifikace falešně pozitivních klastrů je běžným problémem celého výzkumu klastrů,^[8] a byl vyřešen metodami, jako je SigClust^[8] a statistika GAP.^[9] Tyto metody se však spoléhají na určité předpoklady pro nulový model, které nemusí být vždy vhodné.

Şenbabaoğlu et al ^[6] předvedl původní metriku delta K, aby se rozhodl ${displaystyle K}$ v Montiho algoritmu fungoval špatně a navrhl novou lepší metriku pro měření stability konsenzuálních matic pomocí jejich křivek CDF. V křivce CDF konsensuální matice představuje dolní levá část párů vzorků zřídka seskupených dohromady, pravá horní část představuje ty, které jsou téměř vždy seskupeny dohromady, zatímco střední segment představuje ty, které mají nejednoznačné přiřazení v různých bězích shlukování. Podíl míry nejednoznačného shlukování (PAC) kvantifikuje tento střední segment; a je definován jako zlomek párů vzorků s konsenzuálními indexy spadajícími do intervalu (u₁, u₂) ∈ [0, 1] kde u₁ je hodnota blízká 0 a u₂ je hodnota blízká 1 (například u₁= 0,1 a u₂= 0,9). Nízká hodnota PAC označuje plochý střední segment a nízkou míru nesouhlasných přiřazení napříč permutovanými běhy shlukování. Lze tedy odvodit optimální počet klastrů podle ${displaystyle K}$ hodnota s nejnižším PAC.^[6][7]

Související práce

1. Shlukovací soubor (Strehl a Ghosh): Zvažovali různé formulace problému, z nichž většina tento problém redukovala na problém s rozdělením hyper-grafů. V jedné ze svých formulací uvažovali o stejném grafu jako v problému shlukování korelace. Řešení, které navrhli, je vypočítat to nejlepší k- oddíl grafu, který nezohledňuje pokutu za sloučení dvou uzlů, které jsou daleko od sebe.^{[Citace je zapotřebí ]}

2. Shluková agregace (Fern a Brodley): Aplikovali myšlenku agregace klastrů na sbírku měkké shluky získali náhodnými projekcemi. Použili aglomerativní algoritmus a netrestali za sloučení odlišných uzlů.^{[Citace je zapotřebí ]}

3. Fred a Jain: Navrhli použít algoritmus jednoho propojení ke kombinování více běhů k- znamená algoritmus.^{[Citace je zapotřebí ]}

4. Dana Cristofor a Dan Simovici: Pozorovali souvislost mezi agregací klastrů a shlukováním kategorických dat. Navrhli informační teoretická opatření vzdálenosti a navrhují genetické algoritmy pro nalezení nejlepšího agregačního řešení.^{[Citace je zapotřebí ]}

5. Topchy a kol.: Definovali agregaci klastrování jako problém s odhadem maximální pravděpodobnosti a navrhli EM algoritmus pro nalezení konsensuálního klastrování.^{[Citace je zapotřebí ]}

Shlukování tvrdých souborů

Tento přístup Strehl a Bože zavádí problém kombinování více oddílů sady objektů do jednoho konsolidovaného shlukování bez přístupu k funkcím nebo algoritmům, které určovaly tato rozdělení. Diskutují o třech přístupech k řešení tohoto problému za účelem získání vysoce kvalitních konsenzuálních funkcí. Jejich techniky mají nízké výpočetní náklady, a proto je možné vyhodnotit každou z níže diskutovaných technik a dosáhnout nejlepšího řešení porovnáním výsledků s objektivní funkcí.

Efektivní konsenzuální funkce

1. Algoritmus dělení podobnosti na základě clusterů (CSPA)

V CSPA je podobnost mezi dvěma datovými body definována tak, aby byla přímo úměrná počtu shluků složek souboru, ve kterém jsou seskupeny. Intuice spočívá v tom, že čím více podobných dvou datových bodů je, tím vyšší je šance, že je seskupení složek umístí do stejného klastru. CSPA je nejjednodušší heuristika, ale její výpočetní a úložná složitost je kvadratická n. SC3 je příkladem algoritmu typu CSPA.^[10] Následující dvě metody jsou výpočetně levnější:

2. Algoritmus dělení hyper-grafů (HGPA)

Algoritmus HGPA má velmi odlišný přístup k nalezení shody shlukování než předchozí metoda. Problém seskupení klastrů je formulován jako rozdělení hypergrafu rozdělením minimálního počtu hyperedge. Využívají hMETIS což je systém dělení balíků hypergrafu.

3. Algoritmus Meta-shlukování (MCLA)

Algoritmus meta-cLustering (MCLA) je založen na shlucích klastrů. Nejprve se pokusí vyřešit problém s klastrovou korespondencí a poté pomocí hlasování umístí datové body do finálních konsenzuálních klastrů. Problém korespondence klastrů se řeší seskupením klastrů identifikovaných v jednotlivých klastrech souboru. Shlukování se provádí pomocí METIS a spektrální shlukování.

Měkké shlukování souborů

Punera a Bože rozšířil myšlenku souborů tvrdého shlukování na scénář měkkého shlukování. Každá instance v měkkém souboru je reprezentována zřetězením r distribuce pravděpodobnosti zadního členství získané z algoritmů shlukování složek. Můžeme definovat míru vzdálenosti mezi dvěma instancemi pomocí Kullback – Leibler (KL) divergence, který vypočítá „vzdálenost“ mezi dvěma rozděleními pravděpodobnosti.

1. sCSPA

sCSPA rozšiřuje CSPA výpočtem matice podobnosti. Každý objekt je vizualizován jako bod v dimenzionálním prostoru, přičemž každá dimenze odpovídá pravděpodobnosti jeho příslušnosti ke shluku. Tato technika nejprve transformuje objekty do prostoru popisků a poté interpretuje tečkový produkt mezi vektory představujícími objekty jako jejich podobnost.

2. sMCLA

sMCLA rozšiřuje MCLA přijímáním měkkých shluků jako vstupu. Práce sMCLA lze rozdělit do následujících kroků:

• Vytvořte měkký meta-graf klastrů
• Seskupte klastry do metaklastrů
• Sbalte metaklastry pomocí vážení
• Soutěžte o objekty

3. sHBGF

HBGF představuje soubor jako bipartitní graf s klastry a instancemi jako uzly a hranami mezi instancemi a klastry, do kterých patří.^[11] Tento přístup lze triviálně přizpůsobit tak, aby zvážil měkké soubory, protože algoritmus dělení grafů METIS přijímá váhy na okrajích grafu, který má být rozdělen. V sHBGF má graf n + t vrcholy, kde t je celkový počet podkladových klastrů.

4. Bayesiánské shoda shlukování (BCC)

BCC definuje plně Bayesian model pro měkké konsensuální shlukování, ve kterém se předpokládá, že více shluků zdrojů, definovaných různými vstupními daty nebo různými modely pravděpodobnosti, se volně drží konsensuálního shlukování.^[12] Plná zadní část samostatných shluků a shoda shlukování jsou odvozena současně prostřednictvím Gibbsova vzorkování.

Zdroje

Reference

• Alexander Strehl a J. Ghosh, Klastrové soubory - rámec pro opětovné použití znalostí pro kombinování více oddílů, Journal on Machine Learning Research (JMLR) 2002, 3, 583–617.
• Kunal Punera, Joydeep Ghosh. Soubory měkkých shluků založené na konsensu.
• Aristides Gionis, Heikki Mannila, Panayiotis Tsaparas. Shlukování agregace. 21. mezinárodní konference o datovém inženýrství (ICDE 2005)
• Hongjun Wang, Hanhuai Shan, Arindam Banerjee. Bayesovské klastrové soubory^{[trvalý mrtvý odkaz ]}, Mezinárodní konference SIAM o dolování dat, SDM 09
• Nam Nguyen, bohatý Caruana. Konsenzuální shluky. Sedmá mezinárodní konference IEEE o dolování dat.
• Alexander Topchy, Anil K. Jain, William Punch. Shlukovací soubory: Modely konsensu a slabých oddílů. IEEE International Conference on Data Mining, ICDM 03 & SIAM International Conference on Data Mining, SDM 04