K-medoids

Il K-medoids è un algoritmo di clustering partizionale correlato all'algoritmo K-means. Prevede in input un insieme di $n$ oggetti e un numero $k$ 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.

Algoritmo

L'algoritmo di clustering è il seguente:

1. si inizia con una selezione arbitraria di $k$ oggetti come punti medoid da un insieme di $n$ punti dati (con $n>k$);
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 $O';$
4. si calcola il costo totale $S_{i},$ che è la somma dei costi dei singoli elementi dal corrispondente medoid, nel caso del medoid iniziale e il costo totale $S_{f}$ nel caso del medoid $O'$ e se ne calcola la differenza $S=S_{f}-S_{i};$
5. se $S<0,$ allora si scambia il medoid iniziale con il nuovo (se $S<0,$ 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.

Esempio

Si deve clusterizzare il seguente data set di 10 oggetti in 2 cluster, quindi $n=10$ e $k=2:$

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 1

Si inizializzano i $k$ centri. Assumiamo che $C_{1}=(3,4)$ e $C_{2}=(7,4)$ siano i nostri medoid iniziali.

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

Iniziamo quindi il clustering:

• Cluster 1 = $\{(3,4)(2,6)(3,8)(4,7)\};$
• Cluster 2 = $\{(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)\}.$

Essendo $(3,4),(2,6),(3,8)$ e $(4,7)$ punti vicini a $C_{1}$ 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:

$\mathrm {Cost} (x,c)=\sum _{i=1}^{d}|x_{i}-c_{i}|,$

dove $x=(x_{1},\ldots ,x_{d})$ è un qualunque elemento, $c=(c_{1},\ldots ,c_{d})$ è il medoid e $d$ è la dimensione dello spazio degli elementi, in questo caso $d=2.$

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

${\text{Costo totale}}={\mathrm {Cost} ((3,4),(2,6))+\mathrm {Cost} ((3,4),(3,8))+\mathrm {Cost} ((3,4),(4,7))}+{\mathrm {Cost} ((7,4),(6,2))+\mathrm {Cost} ((7,4),(6,4))+\mathrm {Cost} ((7,4),(7,3))+\mathrm {Cost} ((7,4),(8,5))+\mathrm {Cost} ((7,4),(7,6))}=3+4+4+3+1+1+2+2=20.$

Cluster dopo il 1° passo

Passo 2

Selezione di un nonmedoid $O'$ in modo casuale. Assumiamo $O'=(7,3).$

I medoid sono quindi $C_{1}(3,4)$ e $O'(7,3).$ Se $C_{1}$ e $O'$ sono nuovi medoid, si calcola nuovamente il costo totale usando la formula al passo 1.

Cluster dopo il passo 2

${\text{Costo totale}}=3+4+4+2+2+1+3+3=22.$

Così il costo per cambiare il medoid da $C_{2}$ a $O'$ è:

$S={\text{Costo totale attuale}}-{\text{Costo totale precedente}}=22-20=2>0.$

Quindi cambiare medoid in $O'$ 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.