K-means

L'algoritmo K-means è un algoritmo di analisi dei gruppi 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.

Un algoritmo che risolve K-means in modo approssimato è l'algoritmo di Lloyd.

Descrizione generale

L'obiettivo che l'algoritmo si prepone è di minimizzare la varianza totale intra-gruppo; ogni gruppo viene identificato mediante un centroide o punto medio. L'algoritmo segue una procedura iterativa: inizialmente crea k partizioni e assegna i punti d'ingresso a ogni partizione o casualmente o usando alcune informazioni euristiche; quindi calcola il centroide di ogni gruppo; costruisce in seguito una nuova partizione associando ogni punto d'ingresso al gruppo il cui centroide è più vicino ad esso; infine vengono ricalcolati i centroidi per i nuovi gruppi e così via, finché l'algoritmo non converge.

Descrizione formale

Dati N oggetti con ${\displaystyle i}$ attributi, modellizzati come vettori in uno spazio vettoriale ${\displaystyle i}$-dimensionale, definiamo ${\displaystyle X={X_{1},X_{2},\ldots ,X_{N}}}$ come insieme degli oggetti. Ricordiamo che si definisce partizione degli oggetti il gruppo di insiemi ${\displaystyle P={P_{1},P_{2},\ldots ,P_{K}}}$ che soddisfano le seguenti proprietà:

• ${\displaystyle \bigcup _{1}^{K}P_{i}=X}$ : l'unione di tutti i cluster deve contenere tutti gli oggetti di partenza;
• ${\displaystyle P_{i}\cap P_{j}=\varnothing ,i\neq j}$ : ogni oggetto può appartenere ad un solo cluster;
• ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle U\in \mathbb {N} ^{K\times N}}$, il cui generico elemento ${\displaystyle u_{ij}=\{0,1\}}$ indica l'appartenenza dell'oggetto ${\displaystyle j}$ al cluster ${\displaystyle i}$. Indichiamo quindi con ${\displaystyle C={C_{1},C_{2},\ldots ,C_{K}}}$ l'insieme dei ${\displaystyle K}$ centroidi. A questo punto definiamo la funzione obiettivo come:

${\displaystyle 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 ${\displaystyle U_{v}}$ e ${\displaystyle C_{v}}$ casuali
2. Calcola ${\displaystyle U_{n}}$ che minimizza ${\displaystyle V(U,C_{v})}$
3. Calcola ${\displaystyle C_{n}}$ che minimizza ${\displaystyle V(U_{v},C)}$
4. Se l'algoritmo converge ci si ferma, altrimenti ${\displaystyle U_{v}=U_{n},C_{v}=C_{n}}$ e torna al passo 2

Tipici criteri di convergenza sono i seguenti:

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

Pregi e difetti

L'algoritmo ha acquistato notorietà dato che converge molto velocemente: si è osservato infatti che generalmente il numero d'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 ${\displaystyle 2^{\Omega ({\sqrt {n}})}}$ a convergere. Più recentemente, A. Vattani ha migliorato questo risultato, mostrando che l'algoritmo può impiegare tempo esponenziale ${\displaystyle 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 dall'insieme di gruppi 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 scegliere la soluzione più soddisfacente fra quelle prodotte. Un altro svantaggio dell'algoritmo è che esso richiede di scegliere il numero di gruppi k da identificare; se i dati non sono naturalmente partizionati si ottengono risultati strani. Inoltre, l'algoritmo funziona bene solo quando sono individuabili gruppi sferici nei dati.

K-means in Matlab

È possibile applicare l'algoritmo K-means in Matlab utilizzando la funzione kmeans(DATA, N_CLUSTER), che individua N_CLUSTER numeri di cluster fra i dati DATA. Il seguente file m mostra una possibile applicazione dell'algoritmo per il raggruppamento di dati di un'immagine basato sul colore.

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 ${\displaystyle 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.

Bibliografia

• 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).

Voci correlate

• Clustering
• K-medoids
• Region growing

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul k-means

Collegamenti esterni

• Esempi numerici del clustering con K-means, su people.revoledu.com.
• Esempi di applicazioni che usano il clustering K-means per ridurre il numero di colori nelle immagini, su leet.it.
• (IT) Il data mining, su intelligenzaartificiale.it.
• (IT) Data mining: cos’è, come funziona, esempi e software, su ita.myservername.com.
• Estensione di PostgreSQL per k-means, su pgxn.org.

Portale Informatica

Portale Matematica