
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:


Lo scarto quadratico medio (o deviazione standard o scarto tipo) è un indice di dispersione statistico, vale a dire una stima della variabilità di una popolazione di dati o di una variabile casuale.
È uno dei modi per esprimere la dispersione dei dati intorno ad un indice di posizione, quale può essere, ad esempio, la media aritmetica o una sua stima. Ha pertanto la stessa unità di misura dei valori osservati (al contrario della varianza che ha come unità di misura il quadrato dell'unità di misura dei valori di riferimento). In statistica la precisione si può esprimere come lo scarto quadratico medio.
Il termine ""standard deviation"" è stato introdotto in statistica da Pearson nel 1894 assieme alla lettera greca formula_1 (sigma) che lo rappresenta. Il termine italiano "deviazione standard" ne è la traduzione più utilizzata nel linguaggio comune; il termine dell'Ente Nazionale Italiano di Unificazione è tuttavia "scarto tipo", definito come la radice quadrata positiva della varianza per lo meno fin dal 1984.
Se non indicato diversamente, lo scarto quadratico medio è la radice quadrata della varianza, la quale viene coerentemente rappresentata con il quadrato di sigma (formula_2).
In statistica lo scarto quadratico medio di un carattere rilevato su una popolazione di formula_3 unità statistiche si definisce esplicitamente come:
dove formula_5 è la media aritmetica di formula_6.
Formalmente lo scarto quadratico medio di una variabile può essere calcolata a partire dalla funzione generatrice dei momenti, in particolare è la radice quadrata della differenza tra il momento secondo ed il momento primo elevato al quadrato.
A partire dallo scarto quadratico medio si definisce anche il coefficiente di variazione o la "deviazione standard relativa" come il rapporto tra lo scarto tipo formula_7 e il valore assoluto della media aritmetica della variabile in esame:
Questo indice relativo (che viene spesso espresso in termini percentuali) consente di effettuare confronti tra dispersioni di dati di tipo diverso, indipendentemente dalle loro quantità assolute.
Nell'ambito della statistica inferenziale (dove è noto solo un campione della popolazione), soprattutto nell'ambito della teoria della stima, a volte si rimpiazza il denominatore formula_3 con formula_10 ottenendo:
Sostanzialmente, poiché non è nota la media dell'intera popolazione, ma solo una sua stima (la media del campione), bisogna utilizzare formula_10 per ottenere uno stimatore corretto formula_13 della varianza incognita formula_7 di formula_6 sull'intera popolazione a partire dai dati del campione. La sua radice quadrata diviene lo scarto quadratico medio "corretto".
Questa correzione al denominatore fa sì che la nuova definizione sia un po' più grande della precedente, correggendo così la tendenza della precedente a sottostimare le incertezze soprattutto nel caso in cui si lavori con pochi dati (formula_3 piccolo).
Osserviamo il caso limite di formula_17, cioè quando si ha un campione di un solo elemento: la prima definizione dà il risultato formula_18, che ovviamente non è molto ragionevole nell'ambito della statistica inferenziale, mentre quella "corretta" dà un risultato non definito del tipo formula_19, rispecchiando così la totale ignoranza inerente all'incertezza su una singola misura. In questo senso, si dice che la statistica non dice nulla sul singolo caso.
Osserviamo che la differenza tra le due definizioni per campioni molto estesi è spesso numericamente insignificante.
Il calcolo può essere semplificato come segue:
cioè, applicando il tutto alla formula originale:
Sia formula_6 una variabile aleatoria, lo scarto quadratico medio è definito come la radice quadrata della varianza di formula_6
Formalmente lo scarto quadratico medio di una variabile aleatoria può essere calcolato a partire dalla funzione generatrice dei momenti, in particolare è la radice quadrata della differenza tra il momento secondo ed il momento primo elevato al quadrato, cioè
dove formula_26 è il valore atteso di formula_6.
In ambito finanziario, lo scarto quadratico medio viene usato per indicare la variabilità di un'attività finanziaria e dei suoi payoff (rendimenti). Esso fornisce quindi, implicitamente, una misura della volatilità dell'attività, quindi del suo rischio.
In fisica, è un ottimo indice dell'errore casuale della misurazione di una grandezza fisica.
In ambito sportivo è utilizzato per valutare la prestazione di un giocatore di bowling in riferimento ad un certo numero di partite. Il valore trovato non incide sul punteggio ma sintetizza le capacità e i miglioramenti del giocatore.
In ingegneria, è uno dei parametri da considerare per valutare la capacità di un processo produttivo.
Nelle applicazioni informatiche, è a volte conveniente utilizzare la formula
che consente, con sole tre variabili formula_29, di calcolare lo scarto quadratico medio, oltre che la media, di un flusso di numeri di lunghezza formula_3 senza dover ricorrere ad una memorizzazione degli stessi.
