K-significa

Algoritmo di k-mean

Natura	Algoritmo di partizionamento dei dati ( d )

Il partizionamento in k -means (o k -means in inglese) è un metodo di partizionamento dei dati e un problema di ottimizzazione combinatoria . Dati punti e un intero k , il problema è dividere i punti in k gruppi, spesso chiamati cluster , in modo da minimizzare una certa funzione. Consideriamo la distanza di un punto dalla media dei punti del suo ammasso; la funzione da minimizzare è la somma dei quadrati di queste distanze.

Esiste un'euristica classica per questo problema, spesso chiamata metodi k- medie , utilizzata per la maggior parte delle applicazioni. Il problema viene studiato anche come un classico problema di ottimizzazione, ad esempio con algoritmi di approssimazione .

Le k- medie vengono utilizzate in particolare nell'apprendimento senza supervisione in cui le osservazioni sono suddivise in k partizioni. I cluster dinamici sono una generalizzazione del principio per cui ogni partizione è rappresentata da un anello può essere più complessa della media. Un algoritmo di k -means classico è lo stesso dell'algoritmo di quantizzazione Lloyd-Max .

Definizione

Dato un insieme di punti ( x 1 , x 2 ,…, x n ), proviamo a suddividere gli n punti in k insiemi S = { S 1 , S 2 ,…, S k } ( k ≤ n ) minimizzando il distanza tra i punti all'interno di ogni partizione:

{\ underset {\ mathbf {S}} {\ operatorname {arg \, min}}} \ sum _ {i = 1} ^ {k} \ sum _ {\ mathbf {x} _ {j} \ in S_ { i}} \ left \ | \ mathbf {x} _ {j} - {\ boldsymbol {\ mu}} _ {i} \ right \ | ^ {2}

dove μ i è il baricentro dei punti in S i .

Storico

Il termine " k -means" fu usato per la prima volta da James MacQueen nel 1967, sebbene l'idea originale fu proposta da Hugo Steinhaus nel 1957. L' algoritmo classico fu proposto da Stuart Lloyd nel 1957 ai fini della modulazione del codice a impulsi , ma non fu rilasciato al di fuori dei Bell Labs prima del 1982. nel 1965, EW Forgy pubblicò un metodo essenzialmente simile, motivo per cui a volte è chiamato "metodo di Lloyd Forgy". Una versione più efficiente, codificata in Fortran , è stata pubblicata da Hartigan e Wong nel 1975/1979.

Algoritmo classico

Esiste un algoritmo classico per il problema, a volte chiamato metodo k-means , ampiamente utilizzato nella pratica e considerato efficiente sebbene non garantisca né l'ottimalità né il tempo di calcolo polinomiale .

Descrizione

Scegli k punti che rappresentano la posizione media delle partizioni iniziali m 1 (1) ,…, m k (1) (a caso per esempio);
Ripeti finché non c'è convergenza:

- assegnare ogni osservazione alla partizione più vicina (ovvero eseguire una partizione Voronoi secondo i mezzi):

{\ displaystyle S_ {i} ^ {(t)} = \ left \ {\ mathbf {x} _ {j}: {\ big \ |} \ mathbf {x} _ {j} - \ mathbf {m} _ {i} ^ {(t)} {\ big \ |} \ leq {\ big \ |} \ mathbf {x} _ {j} - \ mathbf {m} _ {i ^ {*}} ^ {(t )} {\ big \ |} \ \ forall \ i ^ {*} = 1, \ ldots, k \ right \}}

, - aggiorna la media di ogni cluster:

\ mathbf {m} _ {i} ^ {(t + 1)} = {\ frac {1} {| S_ {i} ^ {(t)} |}} \ sum _ {\ mathbf {x} _ { j} \ in S_ {i} ^ {(t)}} \ mathbf {x} _ {j}

Inizializzazione

L'inizializzazione è un fattore determinante nella qualità dei risultati (minimo locale). Molti lavori trattano questo punto. Esistono due metodi di inizializzazione usuali: il metodo Forgy da un lato e il partizionamento casuale dall'altro. Il metodo di Forgy assegna i k punti delle medie iniziali a k dati di input scelti casualmente. Il partizionamento casuale assegna in modo casuale un cluster a ciascun elemento di dati e quindi procede al (primo) calcolo dei punti medi iniziali.

K-means ++ è un algoritmo di inizializzazione del punto k che propone un'inizializzazione migliorando la probabilità di ottenere la soluzione ottimale (minimo globale). L'intuizione alla base di questo approccio è distribuire i k punti delle medie iniziali. Il punto medio iniziale del primo cluster viene scelto in modo casuale dai dati. Quindi ogni punto medio iniziale viene scelto dai punti rimanenti, con una probabilità proporzionale al quadrato della distanza tra il punto e l'ammasso più vicino.

Analisi

Esiste un numero finito di possibili partizioni con k classi. Inoltre, ogni passaggio dell'algoritmo riduce rigorosamente la funzione di costo, positiva, e rivela una migliore partizione. Ciò consente di affermare che l'algoritmo converge sempre in tempo finito, cioè finisce.

Il partizionamento finale non è sempre ottimale. Inoltre, il tempo di calcolo può essere esponenziale nel numero di punti, anche nel piano. In pratica è possibile imporre un limite al numero di iterazioni o un criterio al miglioramento tra iterazioni.

A k fisso, la complessità liscia è polinomiale per alcune configurazioni, inclusi i punti nello spazio euclideo e il caso della divergenza di Kullback-Leibler . Se k fa parte dell'input, la complessità liscia è ancora polinomiale per il caso euclideo. Questi risultati spiegano in parte l'efficienza dell'algoritmo nella pratica.

Altri aspetti algoritmici

Il problema delle k medie è NP-difficile nel caso generale. Nel caso euclideo esiste un algoritmo di approssimazione polinomiale, di rapporto 9, per ricerca locale .

Applicazioni

Vantaggi e svantaggi per l'apprendimento

Un possibile svantaggio dei k-means per il partizionamento è che i cluster dipendono dall'inizializzazione e dalla distanza scelta .

Il fatto di dover scegliere a priori il parametro k può essere percepito come uno svantaggio o un vantaggio. Nel caso, ad esempio, di calcolare il sacco di parole , ciò consente di fissare esattamente la dimensione del dizionario desiderato. Al contrario, in alcune partizioni dei dati , sarà preferibile fare a meno di tale vincolo.

Quantificazione vettoriale

Riferimenti

JB MacQueen (1967). " Alcuni metodi per la classificazione e l'analisi delle osservazioni multivariate " negli Atti del 5 ° Simposio di Berkeley sulle statistiche matematiche e la probabilità 1 : 281–297 p .. Accesso 7 aprile 2009.
H. Steinhaus , " Sulla divisione dei corpi materiali in parti ", Bull. Acad. Polon. Sci. , vol. 4, n o 12,1957, p. 801–804 ( Recensioni matematiche 0090073 , zbMATH 0079.16403 ).
SP Lloyd , " Least square quantization in PCM ", Bell Telephone Laboratories Paper ,1957Pubblicato sulla rivista molto più tardi: SP Lloyd. , " Quantizzazione dei minimi quadrati in PCM ", IEEE Transactions on Information Theory , vol. 28, n o 21982, p. 129-137 ( DOI 10.1109 / TIT.1982.1056489 , letto online , accesso 15 aprile 2009 ).
EW Forgy, " Cluster analysis of multivariate data: efficiency versus interpretability of classifications ", Biometrics , vol. 21,1965, p. 768–769 ( JSTOR 2528559 ).
JA Hartigan, algoritmi di clustering , John Wiley & Sons, Inc.,1975.
JA Hartigan e MA Wong , " Algorithm AS 136: A K-Means Clustering Algorithm " , Journal of the Royal Statistical Society, serie C , vol. 28, n o 1,1979, p. 100-108 ( JSTOR 2346830 ).
David Arthur e Sergei Vassilvitskii, “ peggior caso e analisi livellato del algoritmo ICP, con un'applicazione per il k-Means Method ”, SIAM J. Comput. , vol. 39, n o 2 2009, p. 766-782.
Arthur, David e Vassilvitskii, Sergei, " k-means ++: i vantaggi di un attento seeding ", simposio ACM-SIAM sugli algoritmi discreti , 2007( leggi online ).
Vedi il numero di Stirling per maggiori dettagli.
Andrea Vattani, " k -means richiede esponenzialmente molte iterazioni anche nel piano " , Discrete & Computational Geometry , vol. 45, n o 4, 2011, p. 596-616
Bodo Manthey e Heiko Röglin, " Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences ", JoCG , vol. 4, n o 1, 2013, p. 94-132.
David Arthur, Bodo Manthey e Heiko Röglin, " Smoothed Analysis of the k-Means Method ", Journal of the ACM , vol. 58, n o 5, 2011, p. 19 ( leggi in linea )
The Hardness of Kmeans Clustering Sanjoy Dasgupta, Technical Report CS2008-06, Dipartimento di Informatica e Ingegneria, Università della California, San Diego
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman e Angela Y. Wu, " Un algoritmo di approssimazione di ricerca locale per clustering k-means ", Comput. Geom. , vol. 28 Niente ossa 2-3, 2004, p. 89-112 ( leggi in linea )

Vedi anche

Bibliografia

(it) Richard O. Duda, Peter E. Hart, David G. Stork, Pattern Classification , Wiley-interscience,2001( ISBN 0-471-05669-3 ) [ dettaglio delle edizioni ]

link esterno

Implementazioni gratuite

Implementazioni commerciali

SAS FASTCLUS
MATLAB  : kmeans