K-medoids

Il K-medoids è un algoritmo di clustering partizionale correlato all'algoritmo K-means. Prevede in input un insieme di oggetti e un numero che determina quanti cluster si vogliono in output.

Entrambi gli algoritmi sono partizionali (suddividendo il dataset in gruppi) ed entrambi cercano di minimizzare l'errore quadratico medio, la distanza tra punti di un cluster e il punto designato per esserne il centro. In K-means il punto è "artificiale", infatti è il baricentro di tutti i punti nel cluster. Nel K-medoids è usato il punto, tra quelli dati, collocato "più centralmente", in questo modo il centro è uno dei dati osservati. Il K-medoids è più robusto al rumore e agli outlier rispetto al K-means.

Un medoid può essere definito come un elemento di un cluster la cui dissimilarità media rispetto a tutti gli oggetti nel cluster è minima, in questo modo esso sarà il punto più centrale di un dato insieme di punti.

AlgoritmoModifica

L'algoritmo di clustering è il seguente:

  1. si inizia con una selezione arbitraria di   oggetti come punti medoid da un insieme di   punti dati (con  );
  2. si associa ogni elemento nel dato insieme al più simile medoid, dove la similarità è data dalla funzione di costo che è definita usando distanze come la distanza euclidea, la distanza di Manhattan o la distanza di Minkowski;
  3. si seleziona in modo casuale un elemento non medoid  
  4. si calcola il costo totale   che è la somma dei costi dei singoli elementi dal corrispondente medoid, nel caso del medoid iniziale e il costo totale   nel caso del medoid   e se ne calcola la differenza  
  5. se   allora si scambia il medoid iniziale con il nuovo (se   allora ci sarà un nuovo insieme di medoid);
  6. si ripetono i passi dal 2 al 5 sino a quando si hanno cambiamenti nell'insieme dei medoid.

EsempioModifica

Si deve clusterizzare il seguente data set di 10 oggetti in 2 cluster, quindi   e  

 
Distribuzione dei dati
Oggetti (Xi) Coordinata X Coordinata Y
X1 2 6
X2 3 4
X3 3 8
X4 4 7
X5 6 2
X6 6 4
X7 7 3
X8 7 4
X9 8 5
X10 7 6

Passo 1Modifica

Si inizializzano i   centri. Assumiamo che   e   siano i nostri medoid iniziali.

Calcoliamo la distanza così da associare ogni elemento al suo medoid più vicino.  

Iniziamo quindi il clustering:

  • Cluster 1 =  
  • Cluster 2 =  

Essendo   e   punti vicini a   essi formeranno un cluster mentre i punti rimanenti ne formeranno un altro.

Il costo totale sarà 20.

Il costo tra due punti qualsiasi è trovato usando la distanza di Manhattan che è espressa dalla seguente formula:

 

dove   è un qualunque elemento,   è il medoid e   è la dimensione dello spazio degli elementi, in questo caso  

Il costo totale è la somma dei costi per gli oggetti dal proprio medoid:

 
 
Cluster dopo il 1° passo

Passo 2Modifica

Selezione di un nonmedoid   in modo casuale. Assumiamo  

I medoid sono quindi   e   Se   e   sono nuovi medoid, si calcola nuovamente il costo totale usando la formula al passo 1.

 

 
Cluster dopo il passo 2
 

Così il costo per cambiare il medoid da   a   è:

 

Quindi cambiare medoid in   non è una buona idea, la scelta precedente è stata buona e l'algoritmo termina in questo punto (in quanto non ci sono cambiamenti per i medoid).

Può accadere che qualche data point possa migrare da un cluster a un altro, ciò dipende dalla vicinanza rispetto al nuovo medoid scelto.

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica