Apprendimento non supervisionato

Cosa si intende per apprendimento non supervisionato

L'apprendimento non supervisionato, o unsupervised learning, è un tipo di apprendimento automatico in cui un sistema riceve dati in ingresso senza etichette o risposte corrette associate. L'algoritmo osserva solo gli input e cerca autonomamente di individuare regolarità, somiglianze o differenze tra essi, senza esempi da imitare o guide su cosa dovrebbe imparare.

Secondo Russell e Norvig (2021), l'apprendimento non supervisionato può essere inteso come la capacità di "apprendere modelli nel mondo osservando solo gli input, senza ricevere alcuna indicazione esplicita su quale sia il comportamento corretto". Mitchell (1997) sottolinea che in questi scenari l'obiettivo è scoprire regolarità che permettano di rappresentare i dati in forma più compatta o significativa.

Clustering

Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato. Consiste nel raggruppare dati simili tra loro, senza sapere in anticipo quanti gruppi esistono o come dovrebbero essere. L'idea è che, osservando i dati, si possano scoprire gruppi naturali, ovvero insiemi di elementi che condividono caratteristiche comuni.

Formalmente, il clustering mira a suddividere un insieme di dati in gruppi distinti, detti cluster, tali che i dati appartenenti allo stesso gruppo risultino più simili tra loro rispetto a quelli appartenenti a gruppi differenti. La similarità è solitamente definita in termini di distanza, come la distanza euclidea o manhattan, oppure mediante funzioni più complesse adattate al contesto del problema.

Una peculiarità del clustering è che non esiste una soluzione univoca: lo stesso dataset può dare origine a molteplici suddivisioni valide, ciascuna potenzialmente adatta a obiettivi diversi. Il presupposto alla base di questa tecnica è l'esistenza di una struttura latente nei dati che l'algoritmo può rivelare.

Algoritmo K-means

L'algoritmo K-means è stato proposto da Stuart P. Lloyd nel 1957 presso i Bell Laboratories come tecnica per la modulazione a impulsi codificati. Tuttavia, il suo lavoro non fu pubblicato fino al 1982. Il termine "K-means" è stato successivamente coniato da James MacQueen nel 1967.

K-means è uno degli strumenti più noti e ampiamente utilizzati per l'analisi non supervisionata. Assume che il numero di cluster sia fissato a priori e che ciascun cluster possa essere descritto da un centroide, inteso come media dei punti che lo compongono. L'obiettivo è minimizzare la somma delle distanze quadratiche tra ogni punto del dataset e il centroide del cluster cui viene assegnato.

Dal punto di vista matematico, dato un insieme di punti X = {x₁, x₂, ..., xₙ} in uno spazio euclideo di dimensione d, il problema si traduce nella minimizzazione della funzione obiettivo:

J = somma per i=1 a n del minimo su j da 1 a k di ||xᵢ − μⱼ||²

dove μⱼ rappresenta il centroide del cluster j-esimo. Alternativamente, introducendo una funzione di assegnazione c(i), che assegna a ciascun punto il proprio cluster, la formulazione diventa:

J = somma per i=1 a n di ||xᵢ − μ_{c(i)}||²

Il procedimento iterativo inizia con l'inizializzazione casuale di k centroidi. Successivamente, ciascun punto viene associato al centroide più vicino in base alla distanza euclidea, e i centroidi vengono aggiornati calcolando la media dei punti assegnati. Questa fase di riassegnazione e aggiornamento prosegue fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più significativamente.

L'algoritmo converge sempre in un numero finito di passi, anche se non è garantito che il minimo trovato sia globale. Tuttavia, K-means presenta alcune limitazioni: è sensibile all'inizializzazione casuale, richiede di specificare a priori il numero k di cluster e non funziona bene se i cluster hanno forme non sferiche o variano molto in densità e dimensione. Inoltre, è soggetto alla convergenza verso minimi locali della funzione obiettivo senza esplorare quelli globali. Un'altra criticità ben nota è la sensibilità all'inizializzazione: scelte diverse dei centroidi iniziali possono portare a soluzioni differenti.

Russell e Norvig osservano che K-means può essere interpretato come un caso particolare dell'algoritmo Expectation-Maximization, nel quale l'assegnazione dei punti ai cluster e il ricalcolo dei centroidi corrispondono rispettivamente alle fasi E (Expectation) e M (Maximization).

Algoritmo K-medoids

L'algoritmo K-medoids è stato introdotto da Leonard Kaufman e Peter J. Rousseeuw nel 1987 nel loro libro "Finding Groups in Data: An Introduction to Cluster Analysis".

K-medoids è affine al K-means, ma si differenzia per un aspetto cruciale: il rappresentante di ciascun cluster non è la media dei punti, bensì un punto reale del dataset, denominato medoide. Questa scelta lo rende particolarmente robusto nei confronti degli outlier, poiché evita che valori estremi influenzino il centro del cluster.

Formalmente, dato un insieme di dati X = {x₁, x₂, ..., xₙ}, si seleziona un sottoinsieme M = {m₁, ..., m_k} contenuto in X tale da minimizzare il costo totale:

J = somma per j=1 a k della somma su xᵢ appartenenti a Cⱼ di d(xᵢ, mⱼ)

dove d(·,·) è una funzione di distanza, e mⱼ è il medoide del cluster Cⱼ.

L'algoritmo PAM (Partitioning Around Medoids) rappresenta una delle implementazioni più note di K-medoids. 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.

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.

Bibliografia

Russell, S. J., & Norvig, P. (2021). Intelligenza artificiale. Un approccio moderno. Ed. Pearson, Vol. 1.

Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.