
 è 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.
L'algoritmo di clustering è il seguente:
Si deve clusterizzare il seguente data set di 10 oggetti in 2 cluster, quindi n è 10 e k è 2:
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.
Iniziamo quindi il clustering:
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
formula_1
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
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.
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.


In matematica, la distanza di Minkowski è una distanza in uno spazio euclideo che può essere considerata una generalizzazione sia della distanza euclidea sia della distanza di Manhattan.
La distanza di Minkowski di ordine formula_1 tra due punti formula_2 e formula_3 in formula_4 è definita come:
Questa distanza si usa tipicamente con formula_6 o formula_7: il primo la distanza di Manhattan e il secondo rappresenta la distanza euclidea.
Per formula_8 la distanza di Minkowski è una "metrica", nel senso che soddisfa la disuguaglianza triangolare come conseguenza della disuguaglianza di Minkowski. Quando formula_9, la distanza tra formula_10 e formula_11 è formula_12, ma il punto formula_13 è a distanza 1 da entrambi.
Nel caso limite in cui formula_1 tende a infinito si ha la distanza di Čebyšëv:
Per formula_1 che tende a formula_17, in modo simile si ha:
