BŘÍZA

Vyvážená iterativní redukce a shlukování pomocí hierarchií ( BIRCH ) je algoritmus dolování dat bez dozoru používaný k provádění hierarchického shlukování na velkých souborech dat [1] . Výhodou BIRCH je schopnost metody dynamicky se shlukovat při příchodu vícerozměrných metrických datových bodů ve snaze získat nejkvalitnější shlukování pro dostupnou sadu zdrojů (paměť a časový rámec ). Ve většině případů vyžaduje algoritmus BIRCH jeden průchod databází .

Vývojáři BIRCH tvrdili, že to byl „první shlukovací algoritmus, který nabízí efektivní zpracování 'šumu' (datové body, které nejsou součástí schématu) v databázích“ [1] porazil DBSCAN za dva měsíce. Algoritmus získal cenu SIGMOD v roce 2006 po 10 letech testování [2] .

Problém s předchozími metodami

Předchozí shlukovací algoritmy fungovaly na velkých databázích méně efektivně a chovaly se neadekvátně, když byla data příliš velká na to, aby se vešla do paměti RAM . Výsledkem bylo mnoho nákladů na získání vysoce kvalitního klastrování při minimalizaci nákladů na extra I/O. Navíc většina předchůdců BIRCH sledovala všechny datové body (nebo všechny aktuálně vybrané shluky) stejně pro každé „rozhodnutí o shlukování“ a neprováděla heuristické vážení založené na vzdálenostech mezi těmito datovými body.

Výhody BŘÍZY

Každé klastrovací řešení je lokální a provádí se bez prohlížení všech datových bodů a aktuálně existujících klastrů. Metoda pracuje na pozorováních, jejichž datový prostor není obvykle rovnoměrně vyplněn a ne každý datový bod je stejně důležitý. Metoda umožňuje využít veškerou dostupnou paměť k získání co nejpřesnějších možných podshluků při minimalizaci I/O nákladů. Metoda je přírůstková a nevyžaduje celou sadu dat najednou.

Algoritmus

Algoritmus BIRCH bere jako vstup sadu N datových bodů reprezentovaných jako reálné vektory a požadovaný počet shluků K. Algoritmus je rozdělen do čtyř fází, z nichž druhá je volitelná.

První fáze vytvoří CF strom datových bodů, vysoce vyváženou stromovou strukturu definovanou takto:

Vzhledem k množině N d-rozměrných datových bodů je shlukovací rys množiny definován jako trojnásobek , kde je lineární součet a je součtem druhých mocnin datových bodů. $CF$ $CF=(N,LS,SS)$ ${\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i))))$ ${\overrightarrow {SS}}=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$
Funkce shlukování jsou organizovány do CF-stromu , vysoce vyváženého stromu se dvěma parametry: faktorem větvení a prahem . Každý nelistový uzel se skládá maximálně z položek formuláře , kde je ukazatel na jeho tého potomka a je příznakem shlukování reprezentujícím přidružený podshluk. List obsahuje maximálně vstupů, každý z formuláře . Má také dva ukazatele, předchozí a další, které se používají k řetězení všech listů. Velikost stromu závisí na parametru T. Uzel A se musí vejít na stránku velikosti P. B a L jsou určeny hodnotou P. P lze tedy změnit pro vyladění výkonu . Jedná se o velmi kompaktní reprezentaci datové sady, protože každý list není jediným datovým bodem, ale dílčím shlukem. $B$ $T$ $B$ $[CF_{i},child_{i}]$ $child_{i}$ $i$ $CF_{i}$ $L$ $[CF_{i}]$

Ve druhém kroku algoritmus prochází všechny listy v počátečním CF stromu, aby vytvořil menší CF strom odstraněním výpadků a seskupením přetečených podtříd do větších podtříd. Tento krok je v zobrazení zdroje BIRCH označen jako volitelný.

Třetí krok používá existující algoritmus ke shlukování všech listů. Zde je aglomerativní hierarchický shlukovací algoritmus aplikován přímo na podshluky reprezentované jejich CF vektory. Poskytuje také flexibilitu umožňující uživateli zadat buď požadovaný počet shluků, nebo požadovaný práh průměru shluku. Po tomto kroku získáme sadu shluků, které obsahují hlavní distribuční vzory v datech. Mohou však existovat malé místní nepřesnosti, které lze vyřešit volitelným krokem 4. V kroku 4 se těžiště shluků získaná v kroku 3 použijí jako počáteční a redistribuční body datových bodů k získání nové sady shluků. . Krok 4 také poskytuje možnost vyřadit odlehlé hodnoty. To znamená, že bod, který je příliš daleko od nejbližšího jádra, lze považovat za odlehlou hodnotu.

Výpočet znaků shluků

Pokud je uvedeno pouze , lze získat stejná měření bez znalosti skutečných hodnot. $CF=[N,{\overrightarrow {LS}},{\overrightarrow {SS}}]$

Těžiště: ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow { LS}}{N}}$

Poloměr : $R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i))}-{\overrightarrow {C)))^{2)){ N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+{\overrightarrow {SS}}-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}$

Průměrná vzdálenost mezi shluky a : $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},{\overrightarrow {SS_{1}}}]$ $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},{\overrightarrow {SS_{2}}}]$ $D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1))\sum _{j=1}^{N_{2))({\overrightarrow { X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\ cdot {\overrightarrow {SS_{2}}}+N_{2}\cdot {\overrightarrow {SS_{1}}}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{ 2}}}}{N_{1}\cdot N_{2}}}}$

V multifaktoriálních případech lze druhou odmocninu nahradit vhodnou normou.

Poznámky

↑ 1 2 Zhang, Ramakrishnan, Livny, 1996 , str. 103–114.
↑ 2006 SIGMOD Test of Time Award (odkaz není k dispozici) . Archivováno z originálu 23. května 2010. (neurčitý)

Literatura

Zhang T., Ramakrishnan R., Livny M. BIRCH: efektivní metoda shlukování dat pro velmi rozsáhlé databáze // Sborník z mezinárodní konference ACM SIGMOD z roku 1996 o správě dat - SIGMOD '96. - 1996. - doi : 10.1145/233269.233324 .

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-Net 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