Gruparea ierarhică

Clustering ierarhic (de asemenea, algoritmi de clustering grafic și analiza cluster ierarhică ) este un set de algoritmi de ordonare a datelor care vizează crearea unei ierarhii ( arborele ) de clustere imbricate. Există două clase de metode de grupare ierarhică:

Metode aglomerative ( ing. aglomerative ): noi clustere sunt create prin combinarea clusterelor mai mici și astfel se creează un copac de la frunze la trunchi;
Metode divizionare sau divizionare ( ing. divizionare ): noi grupuri sunt create prin împărțirea clusterelor mai mari în altele mai mici și, astfel, se creează un copac de la trunchi până la frunze.

Algoritmii de grupare ierarhică presupun că setul de obiecte analizat este caracterizat de un anumit grad de conectivitate. În funcție de numărul de caracteristici, uneori se disting metodele monotetice și politetice de clasificare. La fel ca majoritatea modalităților vizuale de reprezentare a dependențelor, graficele își pierd rapid vizibilitatea pe măsură ce crește numărul de clustere. Există o serie de programe specializate pentru construirea de grafice .

Dendrograma

O dendrogramă este de obicei înțeleasă ca un arbore construit dintr-o matrice de măsuri de proximitate. Dendrograma vă permite să descrieți relația dintre obiecte dintr-un anumit set [1] . Crearea unei dendrograme necesită o matrice de similaritate (sau diferență ) care determină nivelul de similaritate între perechile de clustere. Metodele aglomerative sunt mai frecvent utilizate.

Pentru a construi o matrice de similaritate (diferență), este necesar să se stabilească o măsură de distanță între două clustere. Cele mai utilizate metode pentru determinarea distanței ( strategii de sortare în limba engleză ) [2] :

Metoda de legătură unică este cunoscută și sub denumirea de „metoda celui mai apropiat vecin” . Se presupune că distanța dintre două grupuri este egală cu distanța minimă dintre două elemente din grupuri diferite: , unde este distanța dintre elemente și aparținând clusterelor și $\min \,\{\,d(a,b):a\in A,\,b\in B\,\)$ $d(a,b)$ $A$ $b$ $A$ $B$
Metoda de legare completă estecunoscută și sub denumirea de metoda vecinului îndepărtat . Distanţa dintre două clustere se presupune a fi egală cu distanţa maximă dintre două elemente din clustere diferite:; $\max \,\{\,d(a,b):a\in A,\,b\in B\,\)$
Metoda perechilor -grup folosind media aritmetică :
- Neponderat ( în engleză UPGMA ). Se presupune că distanța dintre două clustere este egală cu distanța medie dintre elementele acestor clustere: , unde este distanța dintre elemente și aparținând clusterelor și , și și sunt cardinalitățile clusterelor. ${1 \over {|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b)$ $d(a,b)$ $A$ $b$ $A$ $B$ $|A|$ $|B|$
- Ponderat ( în engleză WPGMA ).
Metoda centroid ( metoda engleză a grupului de perechi folosind media centroid ):
- Neponderat ( în engleză UPGMC ). Se presupune că distanța dintre clustere este egală cu distanța dintre centroizii lor (centrele de masă) [3] : , unde și sunt centroizii și . $\|c_{A}-c_{B}\|$ $c_{A}$ $c_{B}$ $A$ $B$
- Ponderat ( în engleză WPGMC ).
metoda lui Ward . _ Spre deosebire de alte metode de analiză a clusterelor, metodele de analiză a dispersiei sunt folosite aici pentru a estima distanțele dintre clustere. Ca distanță dintre clustere, luăm creșterea sumei pătratelor distanțelor obiectelor până la centrul clusterului, obținută ca urmare a unirii lor [4] : . La fiecare pas al algoritmului, două clustere sunt combinate care conduc la creșterea minimă a varianței. Această metodă este utilizată pentru probleme cu clustere strâns distanțate. ${\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))$

Pentru primele trei metode, există o formulă generală propusă de A. N. Kolmogorov pentru măsurile de similaritate [5] :

K_{\eta }([i,j],k)=\left[{\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}}

unde este un grup de două obiecte (clustere) și ; — obiectul (clusterul) cu care se caută asemănarea grupului specificat; este numărul de elemente din cluster ; este numărul de elemente din cluster . Pentru distanțe există o formulă similară Lance-Williams [6] . $[i,j]$ $i$ $j$ $k$ $n_{i}$ $i$ $n_{j}$ $j$

Pleiadele corelative

Folosit pe scară largă în geobotanica și florărie . Ele sunt adesea numite pleiade de corelație [7] [8] [9] [10] .

Un caz deosebit este metoda cunoscută sub numele de metoda de construire a arborilor optimi (dendrite) , care a fost propusă de matematicianul școlii din Lviv Hugo Steinhaus [11] , ulterior metoda a fost dezvoltată de matematicienii școlii taxonomice din Wroclaw [12] . De asemenea, dendritele nu ar trebui să formeze cicluri. Puteți utiliza parțial arcuri direcționate de grafice utilizând măsuri suplimentare de includere (măsuri de similaritate asimetrică).

Diagrama lui Czekanowski

Metoda „diagonalizării” matricei diferențelor și reprezentării grafice a clusterelor de-a lungul diagonalei principale a matricei diferențelor (diagrama lui Czekanowski) a fost propusă pentru prima dată de Jan Czekanowski în 1909 [13] . Iată o descriere a metodologiei:

Esența acestei metode constă în faptul că întreaga amplitudine a valorilor de similaritate obținute este împărțită într-un număr de clase, iar apoi în matricea valorilor de similaritate aceste valori sunt înlocuite cu umbrire diferită pentru fiecare clasă și, de obicei, umbrirea mai întunecată este folosită pentru clasele de similaritate mai înalte. Apoi, schimbând ordinea descrierilor în tabel, se asigură că urmează mai multe descrieri similare [14]

Să dăm un exemplu ipotetic de obținere a diagramei de mai sus. Baza metodei este construirea unei matrice de închidere tranzitivă [15] .

Pentru a construi o matrice de închidere tranzitivă, să luăm o matrice de similaritate simplă și să o înmulțim singur:

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

unde este elementul de la intersecția rândului -lea și coloanei -lea din noua (a doua) matrice obținută după prima iterație; este numărul total de rânduri (coloane) din matricea de similaritate. Această procedură trebuie continuată până când matricea devine idempotentă (adică auto-similară): , unde n este numărul de iterații. $K(i,j)$ $i$ $j$ $q$ $K^{{(n)}}(i,j)=K^{{(n-1)}}(i,j)$

Apoi, transformăm matricea în așa fel încât valorile numerice apropiate să fie în apropiere. Dacă fiecărei valori numerice i se atribuie o culoare sau o nuanță de culoare (ca și în cazul nostru), atunci obținem diagrama clasică Czekanowski. În mod tradițional, o culoare mai închisă corespunde unei asemănări mai mari, iar o culoare mai deschisă corespunde uneia mai mici. În aceasta, este similar cu harta termică pentru matricea distanțelor .

Vezi și

Surse și note

↑ Zhambyu M. Analiza clusterului ierarhic și corespondențe. — M.: Finanţe şi statistică, 1988. — 345 p.
↑ Clasificare și cluster. Ed. J. Wen Raizina. M.: Mir, 1980. 390 p.
↑ Sneath PHA, Sokal RR Taxonomie numerică: principiile și practicile clasificării numerice. - San-Francisco: Freeman, 1973. - 573 p.
↑ Ward JH Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. - 236 p.
↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Statistica aplicată: Clasificare și reducere a dimensionalității. - M .: Finanţe şi statistică, 1989. - 607 p.
↑ Lance GN, Willams WT O teorie generală a strategiilor de sortare prin clasificare. 1. Sisteme ierarhice // Comp. J. 1967. Nr. 9. P. 373-380.
↑ von Terentjev PV Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. Nr. 23(1-2). P. 23-51.
↑ Terentiev P.V. Metoda de corelare a pleiadelor // Vestn. LGU. Nr. 9. 1959. S. 35-43.
↑ Terentiev P. V. Dezvoltarea ulterioară a metodei de corelare a pleiadelor // Aplicarea metodelor matematice în biologie. T. 1. L.: 1960. S. 42-58.
↑ Vyhandu L.K. Despre studiul sistemelor biologice cu atribute multiple // Aplicarea metodelor matematice în biologie. L.: problema. 3. 1964. S. 19-22.
↑ Steinhaus G. Caleidoscop matematic. — M.: Nauka, 1981. — 160 p.
↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropopol. 1951. T. 17. S. 193-211.
↑ Czekanowski J. Zur diferential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
↑ Vasilevich V. I. Metode statistice în geobotanica. - L .: Nauka, 1969. - 232 p.
↑ Tamura S., Hiquchi S., Tanaka K. Pattern classification based on fuzzy relation // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, nr.1, pp. 61-67.

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG