K-keinomenetelmä

K - means - menetelmä on suosituin klusterointimenetelmä . Sen keksi 1950-luvulla matemaatikko Hugo Steinhaus [1] ja lähes samanaikaisesti Stuart Lloyd [2] . Hän saavutti erityisen suosion McQueenin [3] työn jälkeen .

Algoritmin toiminta on sellainen, että se pyrkii minimoimaan klusteripisteiden kokonaisneliöpoikkeaman näiden klustereiden keskuksista:

V=\sum _{i=1}^{k}\sum _{x\in S_{i}}(x-\mu _{i})^{2}

missä on klusterien lukumäärä, ovat tuloksena olevat klusterit, ja ovat kaikkien klusterin vektorien massakeskuksia . $k$ $Si}$ $i=1,2,\pisteet ,k$ $\mu _{i}$ $x$ $Si}$

Analogisesti pääkomponenttien menetelmän kanssa klustereiden keskipisteitä kutsutaan myös pääpisteiksi , ja itse menetelmää kutsutaan pääpisteiden menetelmäksi [4] ja se sisältyy yleiseen pääobjektien teoriaan , jotka tarjoavat parhaan likimääräisen datan. [5] .

Algoritmi

Algoritmi on versio EM-algoritmista , jota käytetään myös Gaussin sekoituksen erottamiseen . Se jakaa vektoriavaruuden elementtijoukon ennalta tunnetuiksi ryhmiksi k .

Pääajatuksena on, että jokaisessa iteraatiossa massakeskipiste lasketaan uudelleen jokaiselle edellisessä vaiheessa saadulle klusterille, jonka jälkeen vektorit jaetaan jälleen klustereihin sen mukaan, kumpi uusista keskuksista osoittautui valitun metriikan mukaan lähempänä.

Algoritmi päättyy, kun klusterin sisäinen etäisyys ei muutu jossain iteraatiossa. Tämä tapahtuu äärellisessä määrässä iteraatioita, koska äärellisen joukon mahdollisten osioiden määrä on äärellinen ja jokaisessa vaiheessa neliöpoikkeama V pienenee, joten silmukan muodostaminen on mahdotonta.

Kuten David Arthur ja Sergey Vasilvitsky ovat osoittaneet, joissakin joukkoluokissa algoritmin monimutkaisuus konvergenssin vaatiman ajan suhteen on [6] . $2^{\Omega ({\sqrt {n)))}$

Algoritmin esittely

Algoritmin toiminta kaksiulotteisessa tapauksessa. Lähtökohdat valitaan sattumanvaraisesti.

Ongelmia k-meansin kanssa

Kokonaiskeskihajonnan V globaalin minimin saavuttamista ei taata , vaan vain yksi paikallisista minimiistä.
Tulos riippuu alkuperäisten klusterikeskusten valinnasta, niiden optimaalinen valinta ei ole tiedossa.
Klusterien lukumäärä on tiedettävä etukäteen.

Laajennukset ja muunnelmat

K-meansin neuroverkkototeutus on laajalti tunnettu ja käytetty - signaalien vektorikvantisointiverkko (yksi Kohosen hermoverkkojen versioista ).

Siellä on laajennus k-means++ , jolla pyritään optimaaliseen klusterikeskusten alkuarvojen valintaan.

Sovellukset syväoppimiseen ja konenäköön

Syväoppimisalgoritmeissa k- means -menetelmää ei toisinaan käytetä aiottuun tarkoitukseen (luokittelu klusteroinnin avulla), vaan ns. suodattimien (konvoluutioytimet, sanakirjat) luomiseen. Esimerkiksi kuvantunnistusta varten k-means-algoritmiin syötetään pieniä satunnaisia harjoitusnäytekuvia, esimerkiksi kooltaan 16x16, lineaarisena vektorina, jonka jokainen elementti koodaa pisteensä kirkkauden. Klusterien lukumääräksi asetetaan suuri, esimerkiksi 256. Harjoiteltu k-means-menetelmä tuottaa tietyissä olosuhteissa klusterikeskuksia (keskipisteitä), jotka ovat käteviä tukikohtia, joihin mikä tahansa syötekuva voidaan hajottaa. Tällaisia "koulutettuja" sentroideja käytetään edelleen suodattimina esimerkiksi konvoluutiohermoverkossa konvoluutioytiminä tai muina vastaavina konenäköjärjestelminä [8] . Näin ollen ohjaamaton oppiminen tapahtuu k-means-menetelmällä.

Linkit

↑ Steinhaus H. (1956). Sur la Division des Corps materiels en partys. Sonni. Acad. Polon. Sc., C1. III osa IV: 801-804.
↑ Lloyd S. (1957). Pienimmän neliön kvantisointi PCM:issä. Bell Telephone Laboratories -paperi.
↑ MacQueen J. (1967). Joitakin menetelmiä monimuuttujahavaintojen luokitteluun ja analysointiin. Julkaisussa Proc. 5. Berkeley Symp. matematiikassa. Tilastot ja todennäköisyys, sivut 281-297.
↑ Flury B. (1990). pääkohdat. Biometrika, 77, 33-41.
↑ Gorban AN, Zinovjev AY (2009). Pääkuvaajat ja jakoputket , Ch. 2 julkaisussa: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Emilio Soria Olivas et al. (toim.), IGI Global, Hershey, PA, USA, s. 28-59.
↑ David Arthur & Sergei Vassilvitskii (2006). "Kuinka hidas on k-means -menetelmä?" (PDF) . Proceedings of the 2006 Symposium on Computational Geometry (SoCG) . Arkistoitu (PDF) alkuperäisestä 2009-01-24 . Haettu 20.04.2008 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ EM Mirkes, K-means ja K-medoids -sovelma Arkistoitu 29. toukokuuta 2013 Wayback Machinessa . Leicesterin yliopisto, 2011.
↑ Adam Coates ja Andrew Y. Ng. Learning Feature Representations with K-means Arkistoitu 21. kesäkuuta 2015, Wayback Machine , Stanford University, 2012

Esittely ja visualisointi

J. Tu, R. Gonzalez "Principles of Pattern Recognition", Mir Publishing House, Moskova 1978, s. 109-112 (algoritmin kuvaus numeerisella esimerkillä).
K-means ja K-medoids ( sovelma , joka esittelee algoritmin toiminnan ja mahdollistaa kahden menetelmän tutkimisen ja vertailun), E. Mirkes ja University of Leicester
Interaktiivinen sovelma, joka näyttää, miten algoritmi toimii

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