Apprendimento non supervisionato

Apprendimento non supervisionato

L’apprendimento non supervisionato è una tipologia di apprendimento automatico in cui un algoritmo analizza dati non etichettati, cioè privi di indicazioni su categorie o risultati attesi.

A differenza dell’apprendimento supervisionato dove ogni esempio è associato a un’etichetta che ne specifica la classe o il valore corretto qui il sistema non riceve alcuna guida esplicita su cosa cercare o come organizzare le informazioni.

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.

Clustering

Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato. E' una tecnica che mira a raggruppare campioni simili all’interno di un unico gruppo, detto cluster. Ogni cluster è caratterizzato da una massima somiglianza interna e da una minima somiglianza rispetto agli altri cluster, secondo un determinato indice di similarità .

Ad esempio, supponiamo di registrare gli spettri di centomila stelle: esistono diversi tipi di stelle che possono essere identificati a partire dagli spettri? E se sì, quanti tipi ci sono e quali sono le loro caratteristiche? Tutti conosciamo termini come “gigante rossa” o “nana bianca”, ma le stelle non portano queste etichette scritte sul cappello: gli astronomi hanno dovuto eseguire un'analisi di clustering non supervisionato per identificare queste categorie .

Tuttavia, quando i dati si trovano in spazi ad alta dimensione, l’individuazione di tali gruppi diventa computazionalmente onerosa e può compromettere la qualità dell’apprendimento. Inoltre, anche sottoinsiemi differenti di caratteristiche (feature) possono produrre cluster altrettanto validi, ma diversi tra loro. Per questo motivo, si rende necessario utilizzare tecniche di selezione delle caratteristiche (feature selection) nell’ambito del clustering, al fine di ridurre gli effetti negativi dell’alta dimensionalità .

Algoritmo K-means

L’algoritmo K-means fu presentato per la prima volta da Stuart P. Lloyd nell’articolo “Least Squares Quantization in PCM” (1982). L’autore descrive un metodo iterativo per la quantizzazione vettoriale, oggi riconosciuto come la base computazionale del K-means, e ne espone il principio con le parole: “A method is given for choosing the set of vectors which minimizes the average distortion.”

Il termine “K-means” fu poi introdotto da James MacQueen nel 1967, contribuendo alla diffusione dell’algoritmo in ambito statistico e nell’apprendimento automatico.

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.

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. (2022). Artificial Intelligence. A Modern Approach, Ed. Pearson.

Charu C. Aggarwal, Chandan K. Reddy (2014). Data Clustering: Algorithms and Applications, CRC Press.