Hierarchikus klaszterezés

A hierarchikus klaszterezés (a gráfklaszterezési algoritmusok és a hierarchikus klaszteranalízis is) olyan adatrendezési algoritmusok halmaza, amelyek célja a beágyazott klaszterek hierarchiájának ( fa ) létrehozása. A hierarchikus klaszterezési módszereknek két osztálya van:

Agglomerációs módszerek ( eng. agglomerative ): kisebb klaszterek kombinálásával új klaszterek jönnek létre, és így fa jön létre a levelektől a törzsig;
Divíziós vagy felosztási módszerek ( eng. divisive ): a nagyobb klaszterek kisebbekre osztásával új klaszterek jönnek létre, és így fa jön létre a törzstől a levelekig.

A hierarchikus klaszterező algoritmusok feltételezik, hogy az elemzett objektumok halmazát bizonyos fokú összekapcsolhatóság jellemzi. A jellemzők száma szerint néha megkülönböztetnek monotetikus és politetikus osztályozási módszereket. A függőségek megjelenítésének legtöbb vizuális módjához hasonlóan a grafikonok is gyorsan elveszítik láthatóságukat a klaszterek számának növekedésével. Számos speciális program létezik grafikonok készítésére .

Dendrogram

A dendrogramon általában egy közelségi mértékek mátrixából összeállított fát értünk. A dendrogram lehetővé teszi egy adott halmaz objektumai közötti kapcsolat ábrázolását [1] . A dendrogram létrehozásához hasonlósági (vagy különbségi ) mátrixra van szükség , amely meghatározza a klaszterpárok közötti hasonlóság szintjét. Az agglomerációs módszereket gyakrabban alkalmazzák.

Hasonlósági (különbség) mátrix felépítéséhez be kell állítani egy távolságmértéket két klaszter között. A távolság meghatározására leggyakrabban használt módszerek ( angol rendezési stratégiák ) [2] :

Az egykapcsolatos módszert "legközelebbi szomszéd módszernek " is nevezik . Feltételezzük, hogy két klaszter távolsága egyenlő a különböző klaszterekből származó két elem közötti minimális távolsággal: , ahol az elemek és a klaszterekhez való tartozás távolsága és ${\displaystyle \min \,\{\,d(a,b):a\in A,\,b\in B\,\))$ $d(a,b)$ $a$ $b$ $A$ $B$
A teljes összekapcsolási módszert távoli szomszéd módszernekis nevezik . Feltételezzük, hogy két klaszter közötti távolság egyenlő a különböző klaszterekből származó két elem közötti maximális távolsággal:; ${\displaystyle \max \,\{\,d(a,b):a\in A,\,b\in B\,\))$
Pair -group módszer számtani átlaggal :
- Súlyozatlan ( angol UPGMA ). Feltételezzük, hogy két klaszter távolsága megegyezik ezen klaszterek elemei közötti átlagos távolsággal: , ahol az elemek és a klaszterekhez tartozó elemek közötti távolság és , és és a klaszterek kardinalitásai . ${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|$
- Súlyozott ( angol WPGMA ).
Centroid módszer ( angol pair-group módszer a centroid átlagával ):
- Súlyozatlan ( angol UPGMC ). Feltételezzük, hogy a klaszterek közötti távolság egyenlő a súlypontjaik (tömegközéppontjaik) közötti távolsággal [3] : , ahol és a súlypontok és . $\|c_{A}-c_{B}\|$ $c_{A}$ $c_{B}$ $A$ $B$
- Súlyozott ( angol WPGMC ).
Ward módszere . _ _ Más klaszterelemzési módszerekkel ellentétben itt a diszperzióanalízis módszereit használjuk a klaszterek közötti távolságok becslésére. A klaszterek közötti távolságként az objektumok a klaszter középpontja közötti távolságok négyzetes összegének növekedését vesszük, amelyet egyesülésük eredményeként kapunk [4] : . Az algoritmus minden lépésében két klaszter kombinálódik, amelyek a variancia minimális növekedéséhez vezetnek. Ezt a módszert szorosan elhelyezkedő klaszterekkel kapcsolatos problémák esetén használják. ${\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))$

Az első három módszerhez létezik egy általános képlet, amelyet A. N. Kolmogorov javasolt a hasonlósági mérésekre [5] :

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

ahol két objektum (klaszter) csoportja és ; — az objektum (klaszter), amellyel a meghatározott csoport hasonlóságát keresik; a klaszter elemeinek száma ; a klaszter elemeinek száma . A távolságokra van egy hasonló Lance-Williams képlet [6] . $[i,j]$ $én$ $j$ $k$ $n_{i}$ $én$ $n_{j}$ $j$

Korrelatív Plejádok

Széles körben használják a geobotanikában és a virágkertészetben . Gyakran korrelációs plejádoknak nevezik őket [7] [8] [9] [10] .

Speciális eset az optimális fák (dendritek) szerkesztési módszereként ismert módszer , amelyet a lvivi iskola matematikusa, Hugo Steinhaus [11] javasolt , majd a módszert a wroclawi taxonómiai iskola matematikusai dolgozták ki [12] . A dendritek szintén nem alkothatnak ciklusokat. A grafikonok irányított íveit részben használhatja további befogadási mértékek (aszimmetrikus hasonlósági mértékek) használatával.

Czekanowski diagramja

A különbségi mátrix "diagonalizálásának" módszerét és a klaszterek grafikus ábrázolását a különbségmátrix főátlója mentén (Czekanowski diagramja) Jan Czekanowski javasolta először 1909-ben [13] . Itt található a módszertan leírása:

Ennek a módszernek a lényege abban rejlik, hogy a kapott hasonlósági értékek teljes amplitúdóját több osztályra osztjuk, majd a hasonlósági értékek mátrixában ezeket az értékeket olyan árnyékolással helyettesítjük, amely eltérő minden osztályt, és általában sötétebb árnyékolást használnak a magasabb hasonlósági osztályokhoz. Ezután a táblázatban a leírások sorrendjének megváltoztatásával biztosítják, hogy további hasonló leírások következzenek [14]

Adjunk egy hipotetikus példát a fenti diagram megszerzésére. A módszer alapja egy tranzitív zárómátrix felépítése [15] .

Egy tranzitív lezárási mátrix felépítéséhez vegyünk egy egyszerű hasonlósági mátrixot, és szorozzuk meg önmagával:

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

ahol az első iteráció után kapott új (második) mátrixban a -edik sor és -edik oszlop metszéspontjában lévő elem ; a hasonlósági mátrix sorainak (oszlopainak) teljes száma. Ezt az eljárást addig kell folytatni, amíg a mátrix idempotenssé (vagyis önhasonlóvá) nem válik: , ahol n az iterációk száma. $K(i,j)$ $én$ $j$ $q$ $K^{{(n)}}(i,j)=K^{{(n-1)}}(i,j)$

Ezután a mátrixot úgy alakítjuk át, hogy közeli számértékek legyenek a közelben. Ha minden számértékhez hozzárendelünk egy színt vagy színárnyalatot (mint esetünkben), akkor a klasszikus Czekanowski diagramot kapjuk. Hagyományosan a sötétebb szín nagyobb hasonlóságot, a világosabb szín pedig egy kisebb hasonlóságot jelent. Ebben hasonló a távolságmátrix hőtérképéhez .

Lásd még

Források és jegyzetek

↑ Zhambyu M. Hierarchikus klaszterelemzés és megfeleltetések. — M.: Pénzügy és statisztika, 1988. — 345 p.
↑ Osztályozás és klaszter. Szerk. J. Wen Raizina. M.: Mir, 1980. 390 p.
↑ Sneath PHA, Sokal RR Numerikus taxonómia: A numerikus osztályozás alapelvei és gyakorlata. - San-Francisco: Freeman, 1973. - 573 p.
↑ Ward JH Hierarchikus csoportosítás egy célfüggvény optimalizálására // J. of the American Statistical Association, 1963. - 236 p.
↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Alkalmazott statisztika: Osztályozás és méretcsökkentés. - M .: Pénzügy és statisztika, 1989. - 607 p.
↑ Lance GN, Willams WT Az osztályozási rendezési stratégiák általános elmélete. 1. Hierarchikus rendszerek // Összeg. J. 1967. No. 9. P. 373-380.
↑ von Terentjev PV Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. 23. szám (1-2). P. 23-51.
↑ Terentiev P.V. Korrelációs plejádok módszere // Vestn. LGU. 9. szám 1959. S. 35-43.
↑ Terentiev P. V. A korrelációs plejádok módszerének továbbfejlesztése // Matematikai módszerek alkalmazása a biológiában. T. 1. L.: 1960. S. 42-58.
↑ Vyhandu L.K. A többattribútumú biológiai rendszerek vizsgálatáról // Matematikai módszerek alkalmazása a biológiában. L.: kérdés. 3. 1964. S. 19-22.
↑ Steinhaus G. Matematikai kaleidoszkóp. — 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 differenciál Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
↑ Vasziljevics V. I. Statisztikai módszerek a geobotanikában. - L .: Nauka, 1969. - 232 p.
↑ Tamura S., Hiquchi S., Tanaka K. Mintaosztályozás fuzzy reláción alapul // IEEE tranzakció a rendszereken, az emberen és a kibernetikán, 1971, SMC 1, 1. sz., 61-67.

Gépi tanulás és adatbányászat
Feladatok	Osztályozási feladat Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellegyüttesek Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-háló Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG