K-means

Da Wikipedia, l'enciclopedia libera.

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 aspettazione-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.

Descrizione generale[modifica | modifica wikitesto]

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.

Descrizione formale[modifica | modifica wikitesto]

Dati N oggetti con i attributi, modellizzati come vettori in uno spazio vettoriale i-dimensionale, definiamo X={X_1,X_2,\ldots,X_N} come insieme degli oggetti. Ricordiamo che si definisce partizione degli oggetti il gruppo di insiemi P={P_1,P_2,\ldots,P_K} che soddisfano le seguenti proprietà:

  • \bigcup_1^{K} P_i = X : l'unione di tutti i cluster deve contenere tutti gli oggetti di partenza;
  •  P_i \cap P_j = \varnothing, i ≠ j : ogni oggetto può appartenere ad un solo cluster;
  • \varnothing \subset P_i \subset X : almeno un oggetto deve appartenere ad un cluster e nessun cluster può contenere tutti gli oggetti.

Ovviamente deve valere anche che 1 < K < N; 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 U \in \mathbb{N}^{K \times N}, il cui generico elemento u_{ij} = {0,1} indica l'appartenenza dell'oggetto j al cluster i. Indichiamo quindi con C={C_1,C_2,\ldots,C_K} l'insieme dei K centroidi. A questo punto definiamo la funzione obiettivo come:

V(U,C) = \sum_{i=1}^{K} \sum_{X_j \in P_i} ||X_j - C_i ||^2

e di questa calcoliamo il minimo seguendo la procedura iterativa vista sopra:

  1. Genera U_v e C_v casuali
  2. Calcola U_n che minimizza V(U,C_v)
  3. Calcola C_n che minimizza V(U_v,C)
  4. Se l'algoritmo converge ci si ferma, altrimenti U_v = U_n , C_v=C_n e torna al passo 2

Tipici criteri di convergenza sono i seguenti:

  • Nessun cambiamento nella matrice U;
  • la differenza fra i valori della funzione obiettivo in due iterazioni successive non supera una soglia prefissata.

Pregi e difetti[modifica | modifica wikitesto]

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, 2^{\Omega(\sqrt{n})}, a convergere. Più recentemente, A. Vattani ha migliorato questo risultato mostrando che l'algoritmo può impiegare tempo esponenziale, 2^{\Omega(n)}, 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.

K-Means in Matlab[modifica | modifica wikitesto]

È 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

%Sintassi:
%img_segm(nome_file,N_CLUSTER)
%
%Descrizione:
%Data un’immagine rappresentata in scala di grigio, la segmenta in un
%numero dato di segmenti, utilizzando algoritmi di clustering. 
%
%Inputs:
%nome_file - Nome del file contenente l'immagine
%N_CLUSTER - Numero di segmenti
if nargin < 2
    error('Numero di parametri insufficiente');
end
immagine = imread(nome_file);
MO = [];
righe=size(immagine,1);
colonne=size(immagine,2);
for i = 1:righe
    for j = 1:colonne
        c = immagine(i,j,3);
        MO = [MO;i,j,c];
    end
end
MO=double(MO);
U = kmeans(MO, N_CLUSTER);
for k = 1:N_CLUSTER
    ris = 255 .* ones(righe,colonne);
    temp = find(U == k);
    for i = 1:length(temp)
        riga = floor(temp(i)/colonne) + 1;
        colonna = mod(temp(i),colonne) + 1;
        ris(riga,colonna) = 0;
    end
    figure('name',sprintf('Cluster %d',k));
    image(ris);
    colormap(gray(256));
end

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 k_{ij} 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:

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations", Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297
  • D. Arthur, S. Vassilvitskii (2006): "How Slow is the k-means Method?," Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
  • A. Vattani (2009): "k-means requires exponentially many iterations even in the plane," Proceedings of the 2009 Symposium on Computational Geometry (SoCG).
  • D. Arthur, B. Manthey, H. Roeglin (2009): "k-means has polynomial smoothed complexity," Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS).

Collegamenti esterni[modifica | modifica wikitesto]