Hierarkisk klyngedannelse

Hierarkisk klyngedannelse (også grafklyngealgoritmer og hierarkisk klyngeanalyse ) er et sæt af databestillingsalgoritmer, der har til formål at skabe et hierarki ( træ ) af indlejrede klynger. Der er to klasser af hierarkiske klyngemetoder:

Agglomerative metoder ( eng. agglomerative ): nye klynger skabes ved at kombinere mindre klynger og dermed skabes et træ fra blade til stamme;
Delings- eller divisionsmetoder ( eng. divisive ): nye klynger skabes ved at opdele større klynger i mindre, og derved skabes et træ fra stammen til bladene .

Hierarkiske klyngealgoritmer antager, at det analyserede sæt af objekter er karakteriseret ved en vis grad af forbindelse. I henhold til antallet af funktioner skelnes der nogle gange mellem monotetiske og polytetiske klassificeringsmetoder. Som de fleste visuelle måder at repræsentere afhængigheder på, mister grafer hurtigt synlighed, efterhånden som antallet af klynger stiger. Der findes en række specialiserede programmer til at konstruere grafer .

Dendrogram

Et dendrogram forstås normalt som et træ konstrueret ud fra en matrix af nærhedsforanstaltninger. Dendrogrammet giver dig mulighed for at skildre forholdet mellem objekter fra et givet sæt [1] . Oprettelse af et dendrogram kræver en ligheds (eller forskel ) matrix , der bestemmer niveauet af lighed mellem par af klynger. Agglomerative metoder er mere almindeligt anvendte.

For at opbygge en ligheds (forskel) matrix er det nødvendigt at indstille et afstandsmål mellem to klynger. De mest almindeligt anvendte metoder til at bestemme afstanden ( engelske sorteringsstrategier ) [2] :

Enkeltkoblingsmetoden er også kendt som "nærmeste nabo-metoden " . Afstanden mellem to klynger antages at være lig med minimumsafstanden mellem to elementer fra forskellige klynger: , hvor er afstanden mellem elementer og tilhørsforhold til klynger og ${\displaystyle \min \,\{\,d(a,b):a\i A,\,b\i B\,\))$ $d(a,b)$ $-en$ $b$ $EN$ $B$
Den komplette koblingsmetode erogså kendt som fjern nabometoden . Afstanden mellem to klynger antages at være lig med den maksimale afstand mellem to elementer fra forskellige klynger:; ${\displaystyle \max \,\{\,d(a,b):a\i A,\,b\i B\,\))$
Par -gruppe metode ved hjælp af aritmetisk middelværdi :
- Uvægtet ( engelsk UPGMA ). Afstanden mellem to klynger antages at være lig med den gennemsnitlige afstand mellem elementerne i disse klynger: , hvor er afstanden mellem elementerne og tilhørende til klyngerne og , og og er klyngernes kardinaliteter . ${1 \over {|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b)$ $d(a,b)$ $-en$ $b$ $EN$ $B$ $|A|$ $|B|$
- Vægtet ( engelsk WPGMA ).
Centroid-metode ( engelsk pargruppemetode, der bruger tyngdepunktsgennemsnittet ):
- Uvægtet ( engelsk UPGMC ). Afstanden mellem klynger antages at være lig med afstanden mellem deres tyngdepunkter (massecentre) [3] : , hvor og er tyngdepunkter og . $\|c_{A}-c_{B}\|$ $c_{A}$ $c_{B}$ $EN$ $B$
- Vægtet ( engelsk WPGMC ).
Wards metode . _ _ I modsætning til andre metoder til klyngeanalyse bruges metoderne til spredningsanalyse her til at estimere afstandene mellem klynger. Som afstanden mellem klynger tager vi stigningen i summen af kvadratiske afstande af objekter til midten af klyngen, opnået som et resultat af deres forening [4] : . Ved hvert trin i algoritmen kombineres to klynger, der fører til den minimale stigning i variansen. Denne metode bruges til problemer med tæt anbragte klynger. ${\displaystyle \Delta =\sum _{i}{(x_{i}-{\bar {x)))^{2}}-\sum _{x_{i}\in A}(x_{i} -{\bar {a)))^{2}-\sum _{x_{i}\in B}(x_{i}-{\bar {b)))^{2))$

For de første tre metoder er der en generel formel foreslået af A. N. Kolmogorov for lighedsmål [5] :

K_{\eta }([i,j],k)=\venstre[{\frac {(n_{i}K(i,k)^{\eta }+(n_{j}K(j,k) ^{\eta })}{n_{i}+n_{j}}}\right]^{{\frac {1}{\eta }}},-{\mathcal {1}}\leqslant \eta \ leqslant +{\mathcal {1}}

hvor er en gruppe af to objekter (klynger) og ; — det objekt (cluster), med hvilket ligheden mellem den specificerede gruppe søges; er antallet af elementer i klyngen ; er antallet af elementer i klyngen . For afstande er der en lignende Lance-Williams formel [6] . $[i,j]$ $jeg$ $j$ $k$ $n_{i}$ $jeg$ $n_{j}$ $j$

Korrelative Plejader

Udbredt i geobotanik og blomsterbrug . De kaldes ofte korrelationsplejader [7] [8] [9] [10] .

Et særligt tilfælde er metoden kendt som metoden til at konstruere optimale træer (dendritter) , som blev foreslået af matematikeren fra Lviv-skolen Hugo Steinhaus [11] , senere blev metoden udviklet af matematikere fra Wroclaws taksonomiske skole [12] . Dendritter bør heller ikke danne cyklusser. Du kan delvist bruge rettede buer af grafer ved at bruge yderligere inklusionsmål (asymmetriske lighedsmål).

Czekanowskis diagram

Metoden til "diagonalisering" af differensmatricen og den grafiske repræsentation af klynger langs differensmatricens hoveddiagonal (Czekanowskis diagram) blev først foreslået af Jan Czekanowski i 1909 [13] . Her er en beskrivelse af metoden:

Essensen af denne metode ligger i det faktum, at hele amplituden af de opnåede lighedsværdier er opdelt i et antal klasser, og derefter i matrixen af lighedsværdier erstattes disse værdier af skygger, der er forskellige for hver klasse, og normalt bruges mørkere skygger til højere lighedsklasser. Derefter, ved at ændre rækkefølgen af beskrivelser i tabellen, sikrer de, at flere lignende beskrivelser er næste [14]

Lad os give et hypotetisk eksempel på at opnå ovenstående diagram. Grundlaget for metoden er konstruktionen af en transitiv lukkematrix [15] .

For at bygge en transitiv lukningsmatrix, lad os tage en simpel lighedsmatrix og gange den med sig selv:

K^{{(2)}}(i,j)=max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q) ,j)))

hvor er elementet i skæringspunktet mellem -th række og -th kolonne i den nye (anden) matrix opnået efter den første iteration; er det samlede antal rækker (kolonner) i lighedsmatrixen. Denne procedure skal fortsættes, indtil matrixen bliver idempotent (det vil sige selv-lignende): , hvor n er antallet af iterationer. $K(i,j)$ $jeg$ $j$ $q$ $K^{{(n)}}(i,j)=K^{{(n-1)}}(i,j)$

Dernæst transformerer vi matricen på en sådan måde, at tætte numeriske værdier er i nærheden. Hvis hver numerisk værdi er tildelt en farve eller farvenuance (som i vores tilfælde), får vi det klassiske Czekanowski-diagram. Traditionelt svarer en mørkere farve til en større lighed, og en lysere farve svarer til en mindre. I denne ligner det varmekortet for afstandsmatrixen .

Se også

Kilder og noter

↑ Zhambyu M. Hierarkisk klyngeanalyse og korrespondancer. — M.: Finans og statistik, 1988. — 345 s.
↑ Klassifikation og klynge. Ed. J. Wen Raizina. M.: Mir, 1980. 390 s.
↑ Sneath PHA, Sokal RR Numerisk taksonomi: Principperne og praksisserne for numerisk klassifikation. - San-Francisco: Freeman, 1973. - 573 s.
↑ Ward JH Hierarkisk gruppering for at optimere en objektiv funktion // J. fra American Statistical Association, 1963. - 236 s.
↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Anvendt statistik: Klassifikation og dimensionsreduktion. - M .: Finans og statistik, 1989. - 607 s.
↑ Lance GN, Willams WT En generel teori om klassifikationssorteringsstrategier. 1. Hierarkiske systemer // Comp. J. 1967. nr. 9. P. 373-380.
↑ af Terentjev PV Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amfibier, Salientia) // Biometrika. 1931. nr. 23(1-2). S. 23-51.
↑ Terentiev P.V. Metode til korrelation pleiades // Vestn. LGU. nr. 9. 1959. S. 35-43.
↑ Terentiev P. V. Videreudvikling af metoden til korrelationspleiader // Anvendelse af matematiske metoder i biologi. T. 1. L.: 1960. S. 42-58.
↑ Vyhandu L.K. Om studiet af biologiske systemer med flere attributter // Anvendelse af matematiske metoder i biologi. L.: spørgsmål. 3. 1964. S. 19-22.
↑ Steinhaus G. Matematisk kalejdoskop. — M.: Nauka, 1981. — 160 s.
↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropopol. 1951. T. 17. S. 193-211.
↑ Czekanowski J. Zur differential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
↑ Vasilevich V.I. Statistiske metoder i geobotanik. - L .: Nauka, 1969. - 232 s.
↑ Tamura S., Hiquchi S., Tanaka K. Mønsterklassificering baseret på fuzzy relation // IEEE-transaktion på systemer, menneske og kybernetik, 1971, SMC 1, nr. 1, s. 61-67.

Machine learning og data mining
Opgaver	Klassificeringsproblem 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