
L'algoritmo K-means è un algoritmo di clustering partizionale che permette di suddividere un insieme di oggetti in K gruppi sulla base dei loro attributi. È una variante dell'algoritmo di aspettativa-massimizzazione (EM) il cui obiettivo è determinare i K gruppi di dati generati da distribuzioni gaussiane. Si assume che gli attributi degli oggetti possano essere rappresentati come vettori, e che quindi formino uno spazio vettoriale.
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.
Dati N oggetti con formula_1 attributi, modellizzati come vettori in uno spazio vettoriale formula_1-dimensionale, definiamo formula_3 come insieme degli oggetti. Ricordiamo che si definisce partizione degli oggetti il gruppo di insiemi formula_4 che soddisfano le seguenti proprietà:
Ovviamente deve valere anche che formula_8; non avrebbe infatti senso né cercare un solo cluster né avere un numero di cluster pari al numero di oggetti.
Una partizione viene rappresentata mediante una matrice formula_9, il cui generico elemento formula_10 indica l'appartenenza dell'oggetto formula_11 al cluster formula_1.
Indichiamo quindi con formula_13 l'insieme dei formula_14 centroidi.
A questo punto definiamo la funzione obiettivo come:
e di questa calcoliamo il minimo seguendo la procedura iterativa vista sopra:
Tipici criteri di convergenza sono i seguenti:
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 può 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, formula_24, a convergere. Più recentemente, A. Vattani ha migliorato questo risultato mostrando che l'algoritmo può impiegare tempo esponenziale, formula_25, 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 è a supporto del fatto che l'algoritmo è veloce in pratica.
In termini di qualità delle soluzioni, l'algoritmo non garantisce il raggiungimento dell'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.
È 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"
La funzione legge l'immagine utilizzando la funzione Matlab imread, che riceve in ingresso il nome del file contenente l'immagine e restituisce una matrice il cui elemento formula_26 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 di clustering la matrice delle osservazioni e, dopo aver generato le matrici utili per visualizzare i cluster prodotti in un'immagine, queste vengono mostrate a video con la funzione image.
Ad esempio, eseguendo il comando:
img_segm('kmeans0.jpg',2);
si ottiene il seguente risultato:


In statistica, il clustering o analisi dei gruppi (dal termine inglese "cluster analysis" introdotto da Robert Tryon nel 1939) è un insieme di tecniche di analisi multivariata dei dati volte alla selezione e raggruppamento di elementi omogenei in un insieme di dati. Le tecniche di "clustering" si basano su misure relative alla somiglianza tra gli elementi. In molti approcci questa similarità, o meglio, dissimilarità, è concepita in termini di distanza in uno spazio multidimensionale. La bontà delle analisi ottenute dagli algoritmi di "clustering" dipende molto dalla scelta della metrica, e quindi da come è calcolata la distanza. Gli algoritmi di "clustering" raggruppano gli elementi sulla base della loro distanza reciproca, e quindi l'appartenenza o meno ad un insieme dipende da quanto l'elemento preso in esame è distante dall'insieme stesso.
Le tecniche di "clustering" si possono basare principalmente su due "filosofie":
Esistono varie classificazioni delle tecniche di clustering comunemente utilizzate. Una prima categorizzazione dipende dalla possibilità che un elemento possa o meno essere assegnato a più cluster:
Un'altra suddivisione delle tecniche di clustering tiene conto del tipo di algoritmo utilizzato per dividere lo spazio:
Queste due suddivisioni sono del tutto trasversali, e molti algoritmi nati come "esclusivi" sono stati in seguito adattati nel caso "non-esclusivo" e viceversa.
Gli algoritmi di clustering di questa famiglia creano una partizione delle osservazioni minimizzando una certa funzione di costo:
dove formula_2 è il numero dei cluster, formula_3 è il formula_4-esimo cluster e formula_5 è la funzione di costo associata al singolo cluster. L'algoritmo più famoso appartenente a questa famiglia è il k-means, proposto da MacQueen nel 1967. Un altro algoritmo abbastanza conosciuto appartenente a questa classe è il Partitioning Around Medioid (PAM).
Le tecniche di clustering gerarchico non producono un partizionamento "flat" dei punti, ma una rappresentazione gerarchica ad albero. 
Questi algoritmi sono a loro volta suddivisi in due classi:
Una rappresentazione grafica del processo di clustering è fornita dal dendrogramma.
In entrambi i tipi di clustering gerarchico sono necessarie funzioni per selezionare la coppia di cluster da fondere ("agglomerativo"), oppure il cluster da dividere ("divisivo").
Nel primo caso, sono necessarie funzioni che misurino la "similarità" (o, indistintamente, la "distanza") tra due cluster, in modo da fondere quelli più simili. Le funzioni utilizzate nel caso agglomerativo sono:
Nei 4 casi precedenti, formula_10 indica una qualsiasi funzione distanza su uno spazio metrico.
Invece nel clustering divisivo è necessario individuare il cluster da suddividere in due sottogruppi. Per questa ragione sono necessarie funzioni che misurino la compattezza del cluster, la densità o la sparsità dei punti assegnati ad un cluster. Le funzioni normalmente utilizzate nel caso divisivo sono:
Nel "Clustering density-based", il raggruppamento avviene analizzando l'intorno di ogni punto dello spazio. In particolare, viene considerata la densità di punti in un intorno di raggio fissato.
Un esempio è il metodo di clustering Dbscan.
Algoritmi di clustering molto usati sono:
Il QT ("Quality Threshold") Clustering (Heyer et al., 1999) è un metodo alternativo di partizionare i dati, inventato per il clustering dei geni. Richiede più potenza di calcolo rispetto al "K"-Means, ma non richiede di specificare il numero di cluster "a priori", e restituisce sempre lo stesso risultato quando si ripete diverse volte.
L'algoritmo è:
La distanza tra un punto ed un gruppo di punti è calcolata usando il concatenamento completo, cioè come la massima distanza dal punto di ciascun membro del gruppo (vedi il "Clustering gerarchico agglomerativo" sulla distanza tra i cluster nella sezione clustering gerarchico).
