Apprendimento non supervisionato

Apprendimento non supervisionato

L’apprendimento non supervisionato è una forma di apprendimento automatico in cui gli algoritmi analizzano dati non etichettati, ovvero privi di indicazioni esplicite su categorie, classi o risultati attesi.

A differenza dell’apprendimento supervisionato — dove ogni esempio nei dati è associato a una risposta nota (come un’etichetta di classe o un valore numerico) — nell’apprendimento non supervisionato l’algoritmo non riceve alcuna guida su cosa dovrebbe imparare.

Il sistema riceve soltanto gli input grezzi e cerca di scoprire, in modo autonomo, schemi, raggruppamenti o relazioni nascoste nei dati. L’obiettivo è individuare strutture latenti che possano descrivere in modo utile l’organizzazione interna dell’insieme di dati.

Clustering

Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato. È una tecnica che mira a raggruppare "oggetti" 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à.

Per esempio, si consideri il caso in cui vengano registrati gli spettri di centomila stelle. È possibile identificare, a partire da questi dati, diversi tipi di stelle? E quanti sarebbero, con quali caratteristiche distintive? Termini come “gigante rossa” o “nana bianca” risultano familiari, ma non corrispondono a etichette esplicite presenti in natura: si tratta di categorie costruite a posteriori attraverso un'attività umana di analisi e classificazione. Gli astronomi, infatti, hanno dovuto applicare tecniche di clustering non supervisionato, analizzando le somiglianze negli spettri per raggruppare le stelle in classi omogenee sulla base delle loro proprietà fisiche.

Tuttavia, quando i dati sono rappresentati in spazi ad alta dimensione, cioè con un numero elevato di caratteristiche (o feature) per ciascun oggetto, l’individuazione di tali gruppi diventa computazionalmente onerosa e può compromettere la qualità dell’apprendimento. Inoltre, differenti sottoinsiemi di caratteristiche possono produrre cluster tra loro differenti ma ugualmente coerenti, rendendo ambigua l’interpretazione dei risultati.

Per questi motivi, ovvero l’elevato costo computazionale e la variabilità dei risultati dovuta all’alta dimensionalità, si rende necessario l’impiego di tecniche di selezione delle caratteristiche (feature selection) nell’ambito del clustering, al fine di ridurre l’impatto negativo della dimensionalità elevata e migliorare la qualità dei gruppi individuati.

Validazione del clustering

Poiché il clustering è un compito non supervisionato, risulta fondamentale disporre di misure di validazione per valutare la qualità delle partizioni ottenute. Senza tali strumenti, sarebbe difficile stabilire se i gruppi trovati riflettano realmente una struttura coerente nei dati.

Le misure di validazione si suddividono in due categorie principali:

Le misure di validazione esterna si basano su informazioni esterne al dataset (come etichette di classe note) per confrontare la struttura del clustering con una classificazione di riferimento. Esempi comuni sono l’entropia, l’indice Rand e la F-measure.

Le misure di validazione interna valutano invece la bontà del clustering esclusivamente sulla base della distribuzione interna dei dati, senza bisogno di etichette. Un esempio ampiamente utilizzato è l’indice di Silhouette, che misura la compattezza dei cluster e la separazione tra essi.

Le misure interne sono particolarmente utili quando non sono disponibili dati etichettati, come accade spesso nei casi reali. Tuttavia, entrambe le famiglie di misure presentano limiti: ad esempio, le etichette possono non riflettere fedelmente la struttura dei dati, o le metriche interne possono risultare sensibili al rumore o alla presenza di sottocluster.

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

"condizioni necessarie […] che i quanti e gli intervalli di quantizzazione associati in uno schema di quantizzazione finito ottimale devono soddisfare."

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 introdotto precedentemente da James MacQueen nel 1967, nell’articolo Some Methods for Classification and Analysis of Multivariate Observations, in cui propose una versione stocastica dell’algoritmo. Tale formulazione differisce da quella oggi comunemente utilizzata, che è più riconducibile al metodo deterministico descritto da Lloyd.

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 dati D = {x₁, x₂, ..., xₙ}, con xᵢ ∈ ℝᵈ, e una partizione in cluster C = {C₁, C₂, ..., C_K}, l’obiettivo è minimizzare la seguente funzione di costo, detta Sum of Squared Errors (SSE):

SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) || xᵢ − c_k ||²

dove: c_k è il centroide del cluster C_k, calcolato come: c_k = (1 / |C_k|) ∑ (xᵢ ∈ C_k) xᵢ

Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.

Il funzionamento dell’algoritmo può essere descritto sinteticamente con il seguente pseudocodice:

Algoritmo K-means
==============================
1: Scegliere K punti iniziali come centroidi 
2: Ripetere
3: Assegnare ciascun punto al centroide più vicino 
4: Ricalcolare ogni centroide come media dei punti assegnati 
5: Fino a che non viene soddisfatto un criterio di convergenza 

In pratica, il procedimento inizia con l’inizializzazione casuale di K centroidi. Successivamente, ciascun punto viene associato al centroide più vicino secondo la distanza euclidea, e i centroidi vengono aggiornati ricalcolando la media dei punti che sono stati loro assegnati. Questa fase di riassegnazione e aggiornamento continua fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più in modo significativo.

K-means presenta però alcune limitazioni:

• Richiede di specificare a priori il numero k di cluster.

• Presuppone che i cluster abbiano forma sferica e dimensione simile (non adatto a cluster non convessi o con densità variabile).

• È sensibile all’inizializzazione: scelte diverse dei centroidi iniziali possono portare a soluzioni differenti.

• È soggetto alla convergenza verso minimi locali della funzione obiettivo.

• È influenzato dagli outlier, che possono spostare i centroidi in modo significativo.

• Assume implicitamente che tutte le feature abbiano lo stesso peso e la stessa scala: richiede quindi normalizzazione preventiva dei dati.

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

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

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:

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. 

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.

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.

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.

Lloyd, S. P. (1982). Least Squares Quantization in PCM. IEEE Transactions on Information Theory, 28(2).

Kaufman, L., & Rousseeuw, P. J. (1987). Clustering by means of medoids.