K-betyder metode

k - means - metoden er den mest populære klyngemetode . Det blev opfundet i 1950'erne af matematikeren Hugo Steinhaus [1] og næsten samtidigt af Stuart Lloyd [2] . Han opnåede særlig popularitet efter McQueens arbejde [3] .

Algoritmens handling er sådan, at den søger at minimere den totale kvadratiske afvigelse af klyngepunkter fra centrene af disse klynger:

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

hvor er antallet af klynger, er de resulterende klynger, og er massecentrene for alle vektorer fra klyngen . $k$ $S_{i}$ $i=1,2,\prikker ,k$ $\mu _{i}$ $x$ $S_{i}$

I analogi med principalkomponenternes metode kaldes klyngernes centre også principalpunkter , og selve metoden kaldes princippernes metode [4] og er inkluderet i den generelle teori om principielle objekter , der giver den bedste tilnærmelse af data [5] .

Algoritme

Algoritmen er en version af EM - algoritmen , der også bruges til at adskille en blanding af gaussere . Den opdeler sættet af elementer i vektorrummet i et forudkendt antal klynger k .

Hovedideen er, at ved hver iteration genberegnes massecentret for hver klynge opnået i det foregående trin, derefter opdeles vektorerne i klynger igen i overensstemmelse med hvilket af de nye centre, der viste sig at være tættere på i henhold til den valgte metrik.

Algoritmen afsluttes, når der ikke er nogen ændring i intracluster-afstanden ved en eller anden iteration. Dette sker i et endeligt antal iterationer, da antallet af mulige partitioner i en endelig mængde er endeligt, og for hvert trin falder den totale kvadratiske afvigelse V , så looping er umulig.

Som vist af David Arthur og Sergey Vasilvitsky, på nogle klasser af sæt , er kompleksiteten af algoritmen med hensyn til den tid, der kræves til konvergens, [6] . $2^{\Omega ({\sqrt {n)))}$

Demonstration af algoritmen

Algoritmens handling i det todimensionelle tilfælde. Udgangspunkter vælges tilfældigt.

Problemer med k-means

Opnåelsen af det globale minimum af den totale standardafvigelse V er ikke garanteret , men kun et af de lokale minima.
Resultatet afhænger af valget af indledende klyngecentre; deres optimale valg er ukendt.
Antallet af klynger skal kendes på forhånd.

Udvidelser og variationer

Den neurale netværksimplementering af K-means er almindeligt kendt og brugt - et netværk af vektorkvantisering af signaler (en af versionerne af Kohonens neurale netværk ).

Der er en udvidelse k-means++ , som er rettet mod det optimale valg af startværdier for klyngecentre.

Ansøgninger til deep learning og machine vision

I deep learning - algoritmer bruges k-means-metoden nogle gange ikke til dets tilsigtede formål (klassificering ved clustering), men til at skabe såkaldte filtre (convolution kerner, ordbøger). For eksempel, til billedgenkendelse, bliver k-middel-algoritmen fodret med små tilfældige stykker af træningsprøvebilleder, f.eks. 16x16 i størrelse, som en lineær vektor, hvor hvert element koder lysstyrken af dets punkt. Antallet af klynger k er sat stort, for eksempel 256. Den trænede k-betyder metode, under visse betingelser, producerer klyngecentre (centroider), som er praktiske baser, hvori ethvert inputbillede kan dekomponeres. Sådanne "trænede" centroider bruges yderligere som filtre, for eksempel for et foldningsneuralt netværk som foldningskerner eller andre lignende maskinsynssystemer [8] . Således udføres uovervåget læring ved hjælp af k-middel metoden.

Demonstration og visualisering

J. Tu, R. Gonzalez "Principles of Pattern Recognition", Mir Publishing House, Moscow 1978, s. 109-112 (beskrivelse af algoritmen med et numerisk eksempel).
K-betyder og K-medoider ( en applet , der demonstrerer algoritmens funktion og giver dig mulighed for at udforske og sammenligne to metoder), E. Mirkes og University of Leicester
En interaktiv applet, der demonstrerer, hvordan algoritmen fungerer

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG