
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 matematica, una funzione di densità di probabilità (o PDF dall'inglese "probability density function") è l'analogo della funzione di probabilità di una variabile casuale nel caso in cui la variabile casuale formula_1 sia continua, cioè l'insieme dei possibili valori che ha la potenza del continuo.
Essa descrive la "densità" di probabilità in ogni punto nello spazio campionario.
La funzione di densità di probabilità di una variabile casuale formula_1 è un'applicazione formula_3 non negativa integrabile secondo Lebesgue e reale di variabile reale tale che la probabilità dell'insieme "A" sia data da
per tutti i sottinsiemi "A" dello spazio campionario.
Intuitivamente, se una distribuzione di probabilità ha densità formula_3, allora l'intervallo formula_6 ha probabilità formula_7. Da ciò deriva che la funzione formula_3 è un'applicazione definita come
Assumendo formula_10, ciò corrisponde al limite della probabilità che formula_11 si trovi nell'intervallo formula_6 per formula_13 che tende a zero. Di qui il nome di funzione di 'densità', in quanto essa rappresenta il rapporto tra una probabilità e un'ampiezza.
Per la condizione di normalizzazione l'integrale su tutto lo spazio di formula_3 deve essere 1. Di conseguenza ogni funzione non negativa, integrabile secondo Lebesgue, con integrale su tutto lo spazio uguale a 1, è la funzione densità di probabilità di una ben definita distribuzione di probabilità. Una variabile casuale che possiede densità si dice "variabile casuale continua".
Per le variabili casuali multivariate (o vettoriali) la trattazione formale è assolutamente identica: formula_15 si dice assolutamente continua se esiste una funzione a valori reali definita in formula_16, detta densità congiunta, tale che per ogni sottoinsieme "A" dello spazio campionario
Essa conserva tutte le proprietà di una densità scalare: è una funzione non negativa a integrale unitario su tutto lo spazio. Una proprietà importante è che se formula_15 è assolutamente continua allora lo è ogni sua componente; il viceversa invece non vale. La densità di una componente, detta densità marginale, si ottiene con un ragionamento analogo al teorema della probabilità assoluta, cioè fissando l'insieme di suoi valori di cui si vuole determinare la probabilità e lasciando libere di variare tutte le altre componenti. Infatti (nel caso bivariato per semplicità) l'evento formula_19 è l'evento formula_20, dunque
utilizzando il teorema di Fubini. La densità marginale di formula_1 è data dunque da
La funzione di densità della variabile casuale normale di media 0
e varianza 1 (detta "normale standard"), di cui a destra è riportato il grafico e l'espressione analitica della corrispondente densità nel caso generico (media formula_24 e varianza formula_25).
Un altro esempio può essere dato dalla densità di probabilità uniforme su un segmento (0,1). Si può verificare immediatamente che è densità di probabilità facendo l'integrale tra (0,1).
