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 scrivendo: “necessary conditions […] that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.” L’ottimizzazione si basa sul criterio di minimizzare la potenza media del rumore di quantizzazione, concetto che corrisponde alla minimizzazione dell’errore quadratico medio, oggi al centro del metodo K-means . 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.

K-means presenta però alcune limitazioni:

• 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.

• E' soggetto alla convergenza verso minimi locali della funzione obiettivo senza esplorare quelli globali.

• E' sensibile 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, 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.”

Questo approccio, noto anche come PAM (Partitioning Around Medoids), si basa sulla minimizzazione di una funzione di costo calcolata sulle dissimilarità tra elementi, e può essere applicato anche in presenza di dati non numerici o con outlier significativi.

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ᵫ.

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.

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.