Versione delle 13:10, 14 apr 2013 modifica 151.51.52.2 (discussione) →‎Pregi e difetti ← Differenza precedente		Versione delle 19:10, 27 apr 2013 modifica annulla Veneziano (discussione \| contributi) Utenti autoverificati 26 860 modifiche mNessun oggetto della modifica Differenza successiva →
Riga 4: L'obiettivo che l'algoritmo si prepone è di minimizzare la varianza totale intra-cluster. Ogni cluster viene identificato mediante un centroide o punto medio. L'algoritmo segue una procedura iterativa. Inizialmente crea K partizioni e assegna ad ogni partizione i punti d'ingresso o casualmente o usando alcune informazioni euristiche. Quindi calcola il centroide di ogni gruppo. Costruisce quindi una nuova partizione associando ogni punto d'ingresso al cluster il cui centroide è più vicino ad esso. Quindi vengono ricalcolati i centroidi per i nuovi cluster e così via, finché l'algoritmo non converge. ==Descrizione formale== Line 31 ⟶ 30: L'algoritmo ha acquistato notorietà dato che converge molto velocemente. Infatti, si è osservato che generalmente il numero di iterazioni è minore del numero di punti. Comunque, l'algoritmo puo' essere molto lento nel caso peggiore: D. Arthur e S. Vassilvitskii hanno mostrato che esistono certi insiemi di punti per i quali l'algoritmo impiega un tempo superpolinomiale, <math>2^{\Omega(\sqrt{n})}</math>, a convergere. Più recentemente, A. Vattani ha migliorato questo risultato mostrando che l'algoritmo puo' impiegare tempo esponenziale, <math>2^{\Omega(n)}</math>, a convergere anche per certi insiemi di punti sul piano. D'altra parte, D. Arthur, B. Manthey e H. Roeglin hanno mostrato che la smoothed complexity dell'algoritmo è polinomiale, la qual cosa e' a supporto del fatto che l'algoritmo è veloce in pratica. In termini di ~~qualita'~~qualità delle soluzioni, l'algoritmo non garantisce il raggiungimento dell'[[Ottimo_paretiano\|ottimo]] globale. La qualità della soluzione finale dipende largamente dal set di cluster iniziale e può, in pratica, ottenere una soluzione ben peggiore dell'ottimo globale. Dato che l'algoritmo è di solito estremamente veloce, è possibile applicarlo più volte e fra le soluzioni prodotte scegliere quella più soddisfacente. Un altro svantaggio dell'algoritmo è che esso richiede di scegliere il numero di cluster(k) da trovare. Se i dati non sono naturalmente partizionati si ottengono risultati strani. Inoltre l'algoritmo funziona bene solo quando sono individuabili cluster sferici nei dati. Line 37 ⟶ 36: == K-Means in Matlab == È possibile applicare l'algoritmo K-means in Matlab utilizzando la funzione '''KMEANS(DATA, N_CLUSTER)''', che individua N_CLUSTER numeri di cluster nel data set DATA. Il seguente m-file mostra una possibile applicazione dell'algoritmo per la clusterizzazione di immagini basata sui colori. ''img_segm.m'' Line 78 ⟶ 77: end La funzione legge ~~l’immagine~~l'immagine utilizzando la funzione ~~matlab~~Matlab imread, che riceve in ingresso il nome del file contenente ~~l’immagine~~l'immagine e restituisce una matrice il cui elemento <math>k_{ij}</math> contiene il codice di colore del pixel i,j. Successivamente costruisce la matrice delle osservazioni con due semplici cicli for. Viene infine passata in ingresso ~~all’algoritmo~~all'algoritmo di clustering la matrice delle osservazioni e, dopo aver generato le matrici utili per visualizzare i cluster prodotti in ~~un’immagine~~un'immagine, queste vengono mostrate a video con la funzione image. Ad esempio, eseguendo il comando:<br> Line 91 ⟶ 90: == Voci correlate == [[Clustering]] [[K-medoids]] * [[Region growing]] ==Bibliografia== * J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations", Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297 * [http://www.stanford.edu/~darthur D. Arthur], [http://www.stanford.edu/~sergeiv S. Vassilvitskii] (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG). * [http://cseweb.ucsd.edu/~avattani A. Vattani] (2009): "k-means requires exponentially many iterations even in the plane," Proceedings of the 2009 Symposium on Computational Geometry (SoCG). * [http://www.stanford.edu/~darthur D. Arthur], [http://wwwhome.math.utwente.nl/~mantheyb B. Manthey], [http://www.roeglin.org H. Roeglin] (2009): "k-means has polynomial smoothed complexity," Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). Line 108 ⟶ 104: * [http://www.leet.it/home/lale/clustering/ Esempi di applicazioni che usano il clustering K-means per ridurre il numero di colori nelle immagini] [http://www.matematicamente.it/il_magazine/numero_9%3a_aprile_2009/112._data_mining%3a_esplorando_le_miniere_alla_ricerca_della_conoscenza_nascosta_clustering_200905305380/ (IT) Articolo divulgativo su Clustering e Data Mining] [http://pgxn.org/dist/kmeans/ ~~estensione~~Estensione dei PostgreSQL per k-means] [[Categoria:Intelligenza artificiale]]

K-means: differenze tra le versioni