Modifica di Apprendimento non supervisionato (sezione)

== Algoritmo K-medoids ==

L’algoritmo K-medoids è stato introdotto da Leonard Kaufman e Peter J. Rousseeuw nel 1987, nel volume ''Finding Groups in Data: An Introduction to Cluster Analysis'', come alternativa robusta al K-means. A differenza di quest’ultimo, che utilizza la media aritmetica dei punti come centroide, il K-medoids rappresenta ciascun cluster con un oggetto reale del dataset, selezionato in modo da minimizzare la dissimilarità media all’interno del gruppo.

“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”<ref>Kaufman e Rousseeuw, ''Clustering by Means of Medoids'', p. 1.</ref>

"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."

K-medoids è il nome del metodo generale di clustering basato sui medoidi. L’algoritmo più noto per implementarlo è PAM (Partitioning Around Medoids), che fornisce un procedimento esplicito per trovare i medoidi ottimali. PAM lavora minimizzando una funzione di costo basata sulle dissimilarità tra punti, calcolando per ogni possibile scambio tra un medoide e un punto non-medoide l’impatto sulla qualità del clustering.<<ref>Aggarwal e Reddy, ''Data Clustering'', p. 93.</ref>

Dal punto di vista formale, dato un insieme di dati X = {x₁, x₂, ..., xₙ}, si cerca un insieme di medoidi M = {m₁, ..., mₖ} ⊆ X che minimizzi la seguente funzione obiettivo:

J = ∑_{j=1}^{k} ∑_{xᵢ ∈ Cⱼ} d(xᵢ, mⱼ)

dove:
* d(xᵢ, mⱼ) è la distanza (o dissimilarità) tra il punto e il medoid del proprio cluster,

* mⱼ è il medoid di Cⱼ, il j-esimo cluster.

L’algoritmo PAM procede nel modo seguente:

<pre>
Algoritmo K-medoids PAM 
==============================
1: Selezionare K punti iniziali come medoidi. 
2: ripeti 
3: Assegnare ogni punto al medoide più vicino. 
4: Per ogni medoide m e punto non-medoide xᵢ: 
5: Calcolare il costo dello scambio tra m e xᵢ. 
6: Se lo scambio migliora la funzione obiettivo, effettuarlo. 
7: fino alla convergenza. 
</pre>
<ref>Aggarwal e Reddy, ''Data Clustering'', p. 94.</ref>


Si inizia con la selezione casuale di k medoidi, quindi assegna ciascun punto al medoide più vicino. In seguito, valuta iterativamente se la sostituzione di un medoide con un altro punto del dataset riduce il costo complessivo; in tal caso, la sostituzione viene effettuata. Il processo continua fino a stabilizzazione.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 94.</ref>

Rispetto a K-means, K-medoids presenta una maggiore robustezza e può operare con qualsiasi metrica di distanza, anche non euclidea. Tuttavia, ciò avviene a scapito della complessità computazionale, che risulta più elevata, specialmente su dataset di grandi dimensioni.

L’algoritmo K-medoids presenta infatti alcune limitazioni rilevanti, specialmente in termini di efficienza e scalabilità:

* Alta complessità computazionale, che lo rende inadatto a dataset di grandi dimensioni.

* Sensibilità all’inizializzazione, con rischio di convergere a soluzioni subottimali.

* Prestazioni ridotte in alta dimensionalità, a causa della scarsa discriminabilità delle distanze.

* Scarsa scalabilità, mitigabile solo tramite versioni approssimate (es. CLARA, CLARANS).

* Difficoltà con cluster non convessi o di forma irregolare, analogamente a K-means.