Hierarkkinen klusterointi

Hierarkkinen klusterointi (myös graafiklusterointialgoritmit ja hierarkkinen klusterianalyysi ) on joukko tietojen järjestysalgoritmeja, joiden tarkoituksena on luoda sisäkkäisten klustereiden hierarkia ( puu ). Hierarkkisia klusterointimenetelmiä on kaksi luokkaa:

Agglomeratiiviset menetelmät ( eng. agglomerative ): uusia klustereita luodaan yhdistämällä pienempiä klustereita ja näin syntyy puu lehdistä runkoon;
Divisive tai jakomenetelmät ( eng. divisive ): uusia klustereita syntyy jakamalla suurempia klustereita pienempiin ja siten puu syntyy rungosta lehtiin.

Hierarkkiset klusterointialgoritmit olettavat, että analysoidulle objektijoukolle on ominaista tietty liitettävyys. Ominaisuuksien lukumäärän mukaan erotetaan joskus monoteettiset ja polyteettiset luokitusmenetelmät. Kuten useimmat visuaaliset tavat esittää riippuvuuksia, kaaviot menettävät nopeasti näkyvyyden klustereiden määrän kasvaessa. Graafeiden rakentamiseen on olemassa useita erikoisohjelmia .

Dendrogrammi

Dendrogrammi ymmärretään yleensä puuksi , joka on rakennettu läheisyysmittausten matriisista. Dendrogrammin avulla voit kuvata tietyn joukon objektien välistä suhdetta [1] . Dendrogrammin luominen vaatii samankaltaisuus- (tai ero ) matriisin , joka määrittää samankaltaisuuden tason klusteriparien välillä. Agglomeratiivisia menetelmiä käytetään yleisemmin.

Samankaltaisuusmatriisin rakentamiseksi on tarpeen asettaa kahden klusterin välinen etäisyysmitta. Yleisimmin käytetyt menetelmät etäisyyden määrittämiseen ( englanninkieliset lajittelustrategiat ) [2] :

Yksittäinen linkitysmenetelmä tunnetaan myös "lähimmän naapurin menetelmänä" . Kahden klusterin välisen etäisyyden oletetaan olevan yhtä suuri kuin kahden eri klustereista peräisin olevan elementin välinen vähimmäisetäisyys: , missä on elementtien ja klusteriin kuulumisen välinen etäisyys ja ${\näyttötyyli \min \,\{\,d(a,b):a\in A,\,b\in B\,\))$ ${\näyttötyyli d(a,b)}$ $a$ $b$ $A$ $B$
Täydellinen linkitysmenetelmä tunnetaanmyös kaukonaapurimenetelmänä . Kahden klusterin välisen etäisyyden oletetaan olevan yhtä suuri kuin kahden eri klusterin elementin välinen maksimietäisyys:; ${\näyttötyyli \max \,\{\,d(a,b):a\in A,\,b\in B\,\))$
Pariryhmämenetelmä käyttäen aritmeettista keskiarvoa :
- Painottamaton ( englanniksi UPGMA ). Kahden klusterin välisen etäisyyden oletetaan olevan yhtä suuri kuin näiden klustereiden elementtien välinen keskimääräinen etäisyys: , missä on alkioiden ja klusteriin kuuluvien etäisyys ja ja ovat klusterien kardinaalit . ${1 \over {|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b)$ ${\näyttötyyli d(a,b)}$ $a$ $b$ $A$ $B$ $|A|$ $|B|$
- Painotettu ( englanniksi WPGMA ).
Centroid-menetelmä ( englanninkielinen pariryhmämenetelmä, jossa käytetään sentroidikeskiarvoa ):
- Painottamaton ( englanniksi UPGMC ). Klusterien välisen etäisyyden oletetaan olevan yhtä suuri kuin niiden sentroidien (massakeskipisteiden) välinen etäisyys [3] : , jossa ja ovat sentroidit ja . $\|c_{A}-c_{B}\|$ $c_{A}$ $c_{B}$ $A$ $B$
- Painotettu ( englanniksi WPGMC ).
Wardin menetelmä . _ _ Toisin kuin muut klusterianalyysimenetelmät, dispersioanalyysin menetelmiä käytetään tässä arvioimaan klusterien välisiä etäisyyksiä. Klusterien väliseksi etäisyydeksi otetaan objektien klusterin keskipisteen välisten neliöetäisyyksien summan lisäys, joka saadaan niiden liittämisen tuloksena [4] : . Algoritmin jokaisessa vaiheessa yhdistetään kaksi klusteria, jotka johtavat pienimpään varianssin kasvuun. Tätä menetelmää käytetään lähekkäin sijaitsevien klustereiden ongelmiin. ${\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))$

Kolmelle ensimmäiselle menetelmälle on olemassa yleinen kaava, jota A. N. Kolmogorov ehdotti samankaltaisuusmittauksille [5] :

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

jossa on kahden objektin (klustereiden) ryhmä ja ; — objekti (klusteri), jonka kanssa määritellyn ryhmän samankaltaisuutta etsitään; on klusterin elementtien lukumäärä ; on klusterin elementtien lukumäärä . Etäisyyksiä varten on samanlainen Lance-Williams-kaava [6] . $[i,j]$ $i$ $j$ $k$ $n_{i}$ $i$ $n_{j}$ $j$

Korrelatiiviset plejadit

Käytetään laajasti geobotaniikassa ja kukkakaupassa . Niitä kutsutaan usein korrelaatiopleiadeiksi [7] [8] [9] [10] .

Erikoistapaus on menetelmä, joka tunnetaan nimellä optimaalisten puiden (dendriittien) konstruointimenetelmä , jonka ehdotti Lvivin koulukunnan matemaatikko Hugo Steinhaus [11] , myöhemmin menetelmän kehittivät Wroclawin taksonomisen koulukunnan matemaatikot [12] . Dendriitit eivät myöskään saa muodostaa syklejä. Voit käyttää osittain suunnattuja kaavioiden kaaria käyttämällä lisäinkluusiomittoja (epäsymmetrinen samankaltaisuusmitta).

Czekanowskin kaavio

Erotusmatriisin "diagonalisointi" ja klusterien graafinen esittäminen eromatriisin päädiagonaalia pitkin (Czekanowskin diagrammi) ehdotti ensimmäisen kerran Jan Czekanowski vuonna 1909 [13] . Tässä on kuvaus menetelmästä:

Tämän menetelmän ydin on siinä, että saatujen samankaltaisuusarvojen koko amplitudi jaetaan useisiin luokkiin, ja sitten samankaltaisuusarvojen matriisissa nämä arvot korvataan varjostuksella, joka on erilainen jokaisessa luokassa, ja yleensä tummempaa varjostusta käytetään korkeampiin samankaltaisuusluokkiin. Sitten muuttamalla kuvausten järjestystä taulukossa he varmistavat, että seuraavaksi tulee lisää samankaltaisia kuvauksia [14]

Annetaan hypoteettinen esimerkki yllä olevan kaavion saamisesta. Menetelmän perustana on transitiivisen sulkumatriisin rakentaminen [15] .

Transitiivisen sulkumatriisin rakentamiseksi otetaan yksinkertainen samankaltaisuusmatriisi ja kerrotaan se itsellään:

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

missä on -: nnen rivin ja - :nnen sarakkeen leikkauskohdassa oleva elementti uudessa (toisessa) matriisissa, joka on saatu ensimmäisen iteraation jälkeen; on samankaltaisuusmatriisin rivien (sarakkeiden) kokonaismäärä. Tätä menettelyä on jatkettava, kunnes matriisista tulee idempotentti (eli itsensä samankaltainen): , jossa n on iteraatioiden lukumäärä. $K(i,j)$ $i$ $j$ $q$ $K^{{(n)}}(i,j)=K^{{(n-1)}}(i,j)$

Seuraavaksi muunnamme matriisin siten, että lähellä olevat numeeriset arvot ovat lähellä. Jos jokaiselle numeeriselle arvolle on määritetty väri tai värisävy (kuten meidän tapauksessamme), saamme klassisen Czekanowski-kaavion. Perinteisesti tummempi väri vastaa suurempaa samankaltaisuutta ja vaaleampi väri vastaa pienempiä. Tässä se on samanlainen kuin etäisyysmatriisin lämpökartta .

Katso myös

Lähteet ja muistiinpanot

↑ Zhambyu M. Hierarkkinen klusterianalyysi ja vastaavuudet. — M.: Talous ja tilastot, 1988. — 345 s.
↑ Luokittelu ja klusteri. Ed. J. Wen Raizina. M.: Mir, 1980. 390 s.
↑ Sneath PHA, Sokal RR Numeerinen taksonomia: Numeerisen luokituksen periaatteet ja käytännöt. - San-Francisco: Freeman, 1973. - 573 s.
↑ Ward JH Hierarkkinen ryhmittely tavoitefunktion optimoimiseksi // J. of the American Statistical Association, 1963. - 236 s.
↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Sovelletut tilastot: Luokittelu ja ulottuvuuden vähentäminen. - M .: Talous ja tilastot, 1989. - 607 s.
↑ Lance GN, Willams WT Luokittelun lajittelustrategioiden yleinen teoria. 1. Hierarkkiset järjestelmät // Comp. J. 1967. nro 9. s. 373-380.
↑ von Terentjev PV Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. nro 23(1-2). s. 23-51.
↑ Terentiev P.V. Korrelaatioplejadien menetelmä // Vestn. LGU. Nro 9. 1959. S. 35-43.
↑ Terentiev P. V. Korrelaatioplejadien menetelmän jatkokehitys // Matemaattisten menetelmien soveltaminen biologiassa. T. 1. L.: 1960. S. 42-58.
↑ Vyhandu L.K. Monen ominaisuuden biologisten järjestelmien tutkimuksesta // Matemaattisten menetelmien soveltaminen biologiassa. L.: kysymys. 3. 1964. S. 19-22.
↑ Steinhaus G. Matemaattinen kaleidoskooppi. - M.: Nauka, 1981. - 160 s.
↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropopoli. 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. Tilastolliset menetelmät geobotanikassa. - L .: Nauka, 1969. - 232 s.
↑ Tamura S., Hiquchi S., Tanaka K. Sumean suhteeseen perustuva kuvioluokitus // IEEE-tapahtuma järjestelmissä, ihmisessä ja kybernetiikassa, 1971, SMC 1, nro 1, s. 61-67.

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokittelu ongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-verkko Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG