K-medoids

Da Wikipedia, l'enciclopedia libera.

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" — è la pura media di tutti i punti nel cluster. Nel K-medoids è usato il punto collocato più centralmente, in questo modo il centro è uno dei datapoint attuali. K-medoids è più robusto al rumore e agli outlier rispetto al k-means.

Un medoid può essere definito come un oggetto 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 dataset.

Algoritmo[modifica | modifica wikitesto]

L'algoritmo di clustering è il seguente:

  1. L'algoritmo inizia con una selezione arbitraria di k oggetti come punti medoid da un insieme di n data point (n>k)
  2. In seguito alla selezione di k punti medoid, si associa ogni oggetto nel dato dataset al più simile medoid. La similarità è definita usando misure di distanza quali distanza euclidea, distanza di Manhattan o distanza di Minkowski.
  3. Si seleziona in modo casuale un oggetto non medoid O’
  4. Si calcola il costo totale S per lo scambio del medoid iniziale nell'oggetto O’
  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 nel medoid.

Esempio[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Si inizializzano i k centri. Assumiamo che C1=(3,4) e C2=(7,4) siano i nostri medoid iniziali.

Calcoliamo la distanza così da associare ogni data object al suo medoid più vicino. Kmedoidt2.jpg

Iniziamo quindi il clustering:

  • Cluster1 = {(3,4)(2,6)(3,8)(4,7)}
  • Cluster2 = {(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 c1 essi formeranno un cluster mentre i punti rimanenti ne formeranno un altro.

Il costo totale sarà 20.

Il costo tra 2 punti qualsiasi è trovato usando la formula

\mathrm{Cost}(x,c)=\sum_{i=1}^d\vert x-c \vert

  • x è un qualunque oggetto e c è il medoid
  • d è la dimensione dell'oggetto, in questo caso 2

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

Costo totale= {cost((3,4),(2,6)) + cost((3,4),(3,8)) + cost((3,4),(4,7))} + {cost((7,4),(6,2)) + cost((7,4),(6,4)) + cost((7,4),(7,3)) + cost((7,4),(8,5)) + cost((7,4),(7,6))} = 3 + 4 + 4 + 3 + 1 + 1 + 2 + 2 = 20

Cluster dopo il 1° passo

Passo 2[modifica | modifica wikitesto]

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

I medoid sono quindi c1(3,4) e O’(7,3). Se c1 e O’ sono nuovi medoid, si calcola il costo totale usando la formula al passo 1.

Kmedoidt3.jpg

Cluster dopo il passo 2

Costo totale = 3 + 4 + 4 + 2 + 2 + 1 + 3 + 3 = 22

Così il costo per cambiare il medoid da c2 a O’ sarà:

S = Costo totale attuale – 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 ad un altro, ciò dipende dalla vicinanza rispetto al nuovo medoid scelto.

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