
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, una correlazione è una relazione tra due variabili tale che a ciascun valore della prima corrisponda un valore della seconda, seguendo una certa regolarità .
Il termine apparve per la prima volta in un'opera di Francis Galton, "Hereditary Genius" (1869). Non fu definita in modo più approfondito (la moralità di un individuo e la sua instabilità morale sono non correlate).
Otto anni dopo, nel 1877, lo stesso Galton scoprì che i coefficienti di regressione lineare tra X e Y sono gli stessi se - ad entrambe le variabili - viene applicata la deviazione standard σ e σ: Galton utilizzò in realtà lo scarto interquartile, definendo il parametro "coefficiente di co-relazione" e abbreviando "regressione" in "r".
In base alle caratteristiche presentate, la correlazione può definirsi:
Inoltre, le correlazioni possono essere:
Il grado di correlazione tra due variabili viene espresso tramite l'indice di correlazione. Il valore che esso assume è compreso tra −1 (correlazione inversa) e 1 (correlazione diretta e assoluta), con un indice pari a 0 che comporta l'assenza di correlazione; il valore nullo dell'indice non implica, tuttavia, che le variabili siano indipendenti.
I coefficienti di correlazione sono derivati dagli indici, tenendo presenti le grandezze degli scostamenti dalla media. In particolare, l'indice di correlazione di Pearson è calcolato come rapporto tra la covarianza delle due variabili e il prodotto delle loro deviazioni standard.:
Va comunque notato che gli indici e i coefficienti di correlazione siano da ritenersi sempre approssimativi, a causa dell'arbitrarietà con cui sono scelti gli elementi: ciò è vero, in particolare, nei casi di correlazioni multiple.
Contrariamente a quanto si potrebbe intuire, la correlazione non dipende da un rapporto di causa-effetto quanto dalla tendenza di una variabile a cambiare in funzione di un'altra. Le variabili possono essere tra loro dipendenti (per esempio la relazione tra stature dei padri e dei figli) oppure comuni (relazione tra altezza e peso di una persona). 
Nel cercare una correlazione statistica tra due grandezze, per determinare un possibile rapporto di causa-effetto, essa non deve risultare una correlazione spuria.
