BIRKE

Balanceret iterativ reduktion og clustering ved hjælp af hierarkier ( BIRCH ) er en uovervåget data mining- algoritme , der bruges til at udføre hierarkisk clustering på store datasæt [1] . Fordelen ved BIRCH er metodens evne til dynamisk at klynge efterhånden som multidimensionelle metriske datapunkter ankommer, i et forsøg på at få den bedste kvalitetsklynger for det tilgængelige sæt af ressourcer (hukommelse og tidsramme ). I de fleste tilfælde kræver BIRCH-algoritmen én gang gennem databasen .

BIRCH-udviklerne hævdede, at det var "den første klyngealgoritme, der tilbyder effektiv håndtering af 'støj' (datapunkter, der ikke er en del af skemaet) i databaser" [1] og slog DBSCAN på to måneder. Algoritmen modtog SIGMOD- prisen i 2006 efter 10 års test [2] .

Problem med tidligere metoder

Tidligere klyngealgoritmer fungerede mindre effektivt på store databaser og opførte sig utilstrækkeligt, når dataene var for store til at passe i RAM . Som et resultat var der mange omkostninger at opnå klyngedannelse af høj kvalitet, samtidig med at omkostningerne ved ekstra I/O blev minimeret. Desuden så de fleste BIRCH-forgængere på alle datapunkter (eller alle aktuelt udvalgte klynger) ens for hver 'klyngebeslutning' og foretog ikke heuristisk vægtning baseret på afstandene mellem disse datapunkter.

Fordele ved BIRCH

Hver klyngeløsning er lokal og udføres uden at se på alle datapunkter og aktuelt eksisterende klynger. Metoden fungerer på observationer, hvis datarum normalt ikke er ensartet udfyldt, og ikke alle datapunkter er lige vigtige. Metoden gør det muligt at bruge al tilgængelig hukommelse til at opnå de mest nøjagtige mulige underklynger og samtidig minimere I/O-omkostningerne. Metoden er inkrementel og kræver ikke det fulde datasæt på én gang.

Algoritme

BIRCH-algoritmen tager som input et sæt af N datapunkter, repræsenteret som reelle vektorer , og det ønskede antal klynger, K . Algoritmen er opdelt i fire faser, hvoraf den anden er valgfri.

Den første fase bygger et CF-træ af datapunkter, en meget afbalanceret træstruktur defineret som følger:

Givet et sæt af N d-dimensionelle datapunkter, er klyngefunktionen af sættet defineret som en tripel , hvor er en lineær sum og er summen af kvadraterne af datapunkterne. $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}$
Klyngefunktioner er organiseret i et CF-træ , et meget afbalanceret træ med to parametre: forgreningsfaktor og tærskelværdi . Hver ikke-bladsknude består af højst indgange af formen , hvor er en pointer til dens th child , og er et klyngeflag, der repræsenterer den tilknyttede underklynge. Arket indeholder højst input, hver af formularen . Den har også to pointere, prev og next, som bruges til at sammenkæde alle arkene. Træets størrelse afhænger af parameteren T. Node A er påkrævet for at passe på en side med størrelse P. B og L bestemmes af værdien af P. Således kan P ændres til tune performance . Dette er en meget kompakt repræsentation af datasættet, fordi hvert ark ikke er et enkelt datapunkt, men en underklynge. $B$ $T$ $B$ $[CF_{i},child_{i}]$ ${\displaystyle child_{i))$ $jeg$ $CF_{i}$ $L$ $[CF_{i}]$

I det andet trin gennemgår algoritmen alle bladene i det indledende CF-træ for at bygge et mindre CF-træ ved at fjerne frafald og gruppere overløbne underklasser i større underklasser. Dette trin er markeret som valgfrit i BIRCH-kildevisningen.

Det tredje trin bruger den eksisterende algoritme til at gruppere alle ark. Her anvendes den agglomerative hierarkiske klyngealgoritme direkte på subklyngerne repræsenteret af deres CF-vektorer. Det giver også fleksibiliteten til at give brugeren mulighed for at angive enten det ønskede antal klynger eller den ønskede tærskelværdi for klyngediameter. Efter dette trin får vi et sæt klynger, der indeholder de vigtigste distributionsmønstre i dataene. Der kan dog være små lokale unøjagtigheder, som kan håndteres af det valgfrie trin 4. I trin 4 bruges tyngdepunkterne for klyngerne opnået i trin 3 som frø og omfordelingspunkter for datapunkter for at opnå et nyt sæt klynger . Trin 4 giver også mulighed for at kassere outliers. Det vil sige, at et punkt, der er for langt fra den nærmeste kerne, kan betragtes som en outlier.

Beregning af tegn på klynger

Hvis kun er givet , kan de samme målinger opnås uden at kende de sande værdier. $CF=[N,{\overrightarrow {LS}},{\overrightarrow {SS}}]$

Centroid: ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow { LS}}{N}}}$

Radius : $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}}}$

Gennemsnitlig afstand mellem klynger og : $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}}}}$

I multifaktorielle tilfælde kan kvadratroden erstattes af en passende norm.

Noter

↑ 1 2 Zhang, Ramakrishnan, Livny, 1996 , s. 103-114.
↑ 2006 SIGMOD Test of Time Award (link utilgængeligt) . Arkiveret fra originalen den 23. maj 2010. (ubestemt)

Litteratur

Zhang T., Ramakrishnan R., Livny M. BIRCH: en effektiv dataklyngemetode til meget store databaser // Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96. - 1996. - doi : 10.1145/233269.233324 .

Machine learning og data mining
Opgaver	Klassifikationsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-Net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG