
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 probabilità, date due variabili aleatorie "X" e "Y", definite sullo stesso spazio di probabilità, si definisce la loro distribuzione congiunta come la distribuzione di probabilità associata al vettore formula_1. Nel caso di due sole variabili, si parla di distribuzione bivariata, mentre nel caso di più variabili si parla di distribuzione multivariata.
La funzione di ripartizione di una distribuzione congiunta è definita come
o più generalmente
Nel caso di variabili aleatorie discrete, la densità discreta congiunta (o funzione di massa di probabilità congiunta) è data da
Siccome la densità congiunta è anch'essa una densità, è soddisfatta la seguente equazione:
Nel caso di variabili aleatorie continue, la densità congiunta è data da
dove "f"("y"|"x") e "f"("x"|"y") sono le distribuzioni condizionate di Y dato X=x e di X dato Y=y, mentre "f"("x") e "f"("y") sono le distribuzioni marginali della densità congiunta, rispettivamente per X e Y.
Anche in questo caso, è soddisfatto
