Metoda k-means

Metoda k - means este cea mai populară metodă de grupare . A fost inventat în anii 1950 de matematicianul Hugo Steinhaus [1] și aproape simultan de Stuart Lloyd [2] . A câștigat o popularitate deosebită după munca lui McQueen [3] .

Acțiunea algoritmului este de așa natură încât urmărește să minimizeze abaterea pătrată totală a punctelor clusterului de la centrele acestor clustere:

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

unde este numărul de clustere, sunt clusterele rezultate , și sunt centrele de masă ale tuturor vectorilor din cluster . $k$ $Si}$ $i=1,2,\dots ,k$ $\mu _{i}$ $X$ $Si}$

Prin analogie cu metoda componentelor principale , centrele clusterelor sunt numite și puncte principale , iar metoda în sine este numită metoda punctelor principale [4] și este inclusă în teoria generală a obiectelor principale care oferă cea mai bună aproximare a datelor. [5] .

Algoritm

Algoritmul este o versiune a algoritmului EM , folosit și pentru a separa un amestec de gaussieni . Împarte setul de elemente ale spațiului vectorial într-un număr precunoscut de clustere k .

Ideea principală este că la fiecare iterație centrul de masă este recalculat pentru fiecare cluster obținut la pasul anterior, apoi vectorii sunt împărțiți din nou în clustere în funcție de care dintre noile centre s-a dovedit a fi mai aproape conform metricii alese.

Algoritmul se termină atunci când nu există nicio modificare a distanței intracluster la o anumită iterație. Acest lucru se întâmplă într-un număr finit de iterații, deoarece numărul de partiții posibile ale unei mulțimi finite este finit și la fiecare pas abaterea pătrată totală V scade, astfel încât bucla este imposibilă.

După cum arată David Arthur și Sergey Vasilvitsky, pe unele clase de mulțimi , complexitatea algoritmului în ceea ce privește timpul necesar pentru convergență este [6] . $2^{\Omega ({\sqrt {n)))}$

Demonstrarea algoritmului

Acțiunea algoritmului în cazul bidimensional. Punctele de plecare sunt alese aleatoriu.

Probleme cu k-means

Nu este garantată realizarea minimului global al abaterii standard totale V , ci doar una dintre minimele locale.
Rezultatul depinde de alegerea centrelor cluster inițiali; alegerea lor optimă este necunoscută.
Numărul de clustere trebuie cunoscut în prealabil.

Extensii și variații

Implementarea rețelei neuronale a K-means este cunoscută și utilizată pe scară largă - o rețea de cuantizare vectorială a semnalelor (una dintre versiunile rețelelor neuronale ale lui Kohonen ).

Există o extensie k-means++ , care vizează alegerea optimă a valorilor inițiale ale centrelor de cluster.

Aplicații pentru învățare profundă și viziune automată

În algoritmii de învățare profundă , metoda k-means este uneori folosită nu pentru scopul propus (clasificare prin clustering), ci pentru a crea așa-numitele filtre (nuclee de convoluție, dicționare). De exemplu, pentru recunoașterea imaginii, algoritmul k-means este alimentat cu bucăți aleatorii mici de imagini ale eșantionului de antrenament, să zicem, cu dimensiunea de 16x16, ca un vector liniar, fiecare element al căruia codifică luminozitatea punctului său. Numărul de clustere k este setat mare, de exemplu, 256. Metoda k-means antrenată, în anumite condiții, produce centrii cluster (centroizi), care sunt baze convenabile în care poate fi descompusă orice imagine de intrare. Astfel de centroizi „antrenați” sunt utilizați în continuare ca filtre, de exemplu, pentru o rețea neuronală convoluțională ca nuclee de convoluție sau alte sisteme similare de viziune artificială [8] . Astfel, învățarea nesupravegheată se realizează folosind metoda k-means.

Link -uri

↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Taur. Acad. Polon. Sc., C1. III vol IV: 801-804.
↑ Lloyd S. (1957). Cuantificarea celor mai mici pătrate în PCM. Lucrarea Bell Telephone Laboratories.
↑ MacQueen J. (1967). Câteva metode de clasificare și analiză a observațiilor multivariate. În Proc. Al 5-lea simptom Berkeley. la Matematică. Statistică și probabilitate, paginile 281-297.
↑ Flury B. (1990). punctele principale. Biometrika, 77, 33-41.
↑ Gorban AN, Zinovyev AY (2009). Principalele grafice și varietăți , cap. 2 în: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, PA, SUA, pp. 28-59.
↑ David Arthur și Serghei Vassilvitskii (2006). „Cât de lentă este metoda k-means?” (PDF) . Proceedings of the 2006 Symposium on Computational Geometry (SoCG) . Arhivat (PDF) din original pe 2009-01-24 . Consultat 2008-04-20 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ EM Mirkes, K-means and K-medoids applet Arhivat 29 mai 2013 la Wayback Machine . Universitatea din Leicester, 2011.
↑ Adam Coates și Andrew Y. Ng. Learning Feature Representations with K-means Arhivat 21 iunie 2015 la Wayback Machine , Universitatea Stanford, 2012

Demonstrație și vizualizare

J. Tu, R. Gonzalez „Principles of Pattern Recognition”, Editura Mir, Moscova 1978, pp. 109-112 (descrierea algoritmului cu un exemplu numeric).
K-means și K-medoids ( un applet care demonstrează funcționarea algoritmului și vă permite să explorați și să comparați două metode), E. Mirkes și University of Leicester
Un applet interactiv care demonstrează cum funcționează algoritmul

Î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