Free Press

Un compito che coinvolge l’apprendimento automatico può non essere lineare, ma ha una serie di passi ben noti:

• Definizione del problema.
• Preparazione dei dati.
• Apprendere un modello sottostante.
• Migliorare il modello sottostante attraverso valutazioni quantitative e qualitative.
• Presentare il modello.

Un buon modo per venire a capo di un nuovo problema è lavorare attraverso l’identificazione e la definizione del problema nel miglior modo possibile e imparare un modello che catturi informazioni significative dai dati. Mentre i problemi di Pattern Recognition e Machine Learning possono essere di vari tipi, possono essere ampiamente classificati in tre categorie:

• Supervised Learning:
  Al sistema vengono presentati degli esempi di input e i loro output desiderati, dati da un “insegnante”, e l’obiettivo è quello di imparare una regola generale che mappa gli input agli output.
• Unsupervised Learning:
  Non vengono date etichette all’algoritmo di apprendimento, lasciandolo solo a trovare la struttura nel suo input. L’apprendimento non supervisionato può essere un obiettivo in sé (scoprire modelli nascosti nei dati) o un mezzo per raggiungere un fine (apprendimento delle caratteristiche).
• Apprendimento di rinforzo:
  Un sistema interagisce con un ambiente dinamico in cui deve eseguire un certo obiettivo (come guidare un veicolo o giocare una partita contro un avversario). Il sistema riceve un feedback in termini di ricompense e punizioni mentre naviga nel suo spazio problematico.

Tra l’apprendimento supervisionato e quello non supervisionato c’è l’apprendimento semi-supervisionato, dove l’insegnante dà un segnale di formazione incompleto: un set di formazione con alcuni (spesso molti) output di destinazione mancanti. Ci concentreremo sull’apprendimento non supervisionato e sul clustering dei dati in questo post del blog.

Apprendimento non supervisionato

In alcuni problemi di riconoscimento dei modelli, i dati di allenamento consistono in un insieme di vettori di input x senza alcun valore target corrispondente. L’obiettivo in tali problemi di apprendimento non supervisionato può essere quello di scoprire gruppi di esempi simili all’interno dei dati, dove si parla di clustering, o di determinare come i dati sono distribuiti nello spazio, noto come stima della densità. Per dirla in termini più semplici, per uno spazio n-campionato da x1 a xn, le vere etichette di classe non sono fornite per ogni campione, quindi conosciuto come apprendimento senza insegnante.

Problemi con l’apprendimento non supervisionato:

• L’apprendimento non supervisionato è più difficile rispetto ai compiti di apprendimento supervisionato.
• Come facciamo a sapere se i risultati sono significativi dato che non sono disponibili etichette di risposta?
• Lasciare che l’esperto guardi i risultati (valutazione esterna)
• Definire una funzione obiettivo sul clustering (valutazione interna)

Perché l’apprendimento non supervisionato è necessario nonostante questi problemi?

• Annotare grandi dataset è molto costoso e quindi possiamo etichettare solo pochi esempi manualmente. Esempio: Riconoscimento vocale
• Ci possono essere casi in cui non sappiamo in quante/quali classi sono divisi i dati. Esempio: Data Mining
• Potremmo voler usare il clustering per ottenere qualche informazione sulla struttura dei dati prima di progettare un classificatore.

L’apprendimento non supervisionato può essere ulteriormente classificato in due categorie:

• Apprendimento parametrico non supervisionato
  In questo caso, si assume una distribuzione parametrica dei dati. Si assume che i dati campione provengano da una popolazione che segue una distribuzione di probabilità basata su un set fisso di parametri. Teoricamente, in una famiglia di distribuzioni normali, tutti i membri hanno la stessa forma e sono parametrizzati da media e deviazione standard. Ciò significa che se si conoscono la media e la deviazione standard, e che la distribuzione è normale, si conosce la probabilità di qualsiasi osservazione futura. L’apprendimento parametrico non supervisionato comporta la costruzione di modelli di miscele gaussiane e l’utilizzo dell’algoritmo di massimizzazione dell’aspettativa per prevedere la classe del campione in questione. Questo caso è molto più difficile dell’apprendimento supervisionato standard perché non ci sono etichette di risposta disponibili e quindi non c’è una misura corretta di accuratezza disponibile per controllare il risultato.
• Apprendimento non supervisionato non parametrico
  Nella versione non parametrica dell’apprendimento non supervisionato, i dati sono raggruppati in cluster, dove ogni cluster (si spera) dice qualcosa sulle categorie e classi presenti nei dati. Questo metodo è comunemente usato per modellare e analizzare i dati con piccole dimensioni del campione. A differenza dei modelli parametrici, i modelli non parametrici non richiedono che il modellatore faccia alcuna ipotesi sulla distribuzione della popolazione, e quindi sono talvolta indicati come un metodo senza distribuzione.

Che cos’è il clustering?

Il clustering può essere considerato il più importante problema di apprendimento non supervisionato; quindi, come ogni altro problema di questo tipo, si occupa di trovare una struttura in una collezione di dati senza etichetta. Una definizione libera di clustering potrebbe essere “il processo di organizzazione di oggetti in gruppi i cui membri sono simili in qualche modo”. Un cluster è quindi una collezione di oggetti che sono “simili” tra loro e sono “dissimili” agli oggetti appartenenti ad altri cluster.

Clustering basato sulla distanza.

Dato un insieme di punti, con una nozione di distanza tra i punti, raggruppare i punti in un certo numero di cluster, tali che

• le distanze interne (all’interno del cluster) dovrebbero essere piccole, cioè i membri dei cluster sono vicini tra loro.I membri dei cluster sono vicini/simili tra loro.
• Le distanze esterne (intra-cluster) dovrebbero essere grandi, cioè i membri dei diversi cluster sono dissimili.

Gli obiettivi del clustering

L’obiettivo del clustering è determinare il raggruppamento interno in un insieme di dati senza etichetta. Ma come decidere cosa costituisce un buon clustering? Si può dimostrare che non esiste un criterio assoluto “migliore” che sia indipendente dallo scopo finale del raggruppamento. Di conseguenza, è l’utente che dovrebbe fornire questo criterio, in modo tale che il risultato del clustering si adatti alle sue esigenze.

Nell’immagine sopra, come facciamo a sapere qual è la migliore soluzione di clustering?

Per trovare una particolare soluzione di clustering, dobbiamo definire le misure di similarità per i cluster.

Misure di prossimità

Per il clustering, dobbiamo definire una misura di prossimità per due punti dati. La prossimità qui significa quanto simili/differenti sono i campioni l’uno rispetto all’altro.

• Misura di similarità S(xi,xk): grande se xi,xk sono simili
• Misura di difformità (o distanza) D(xi,xk): piccola se xi,xk sono simili

Ci sono varie misure di similarità che possono essere usate.

• Vettori: Distanza Coseno

• Insiemi: Jaccard Distance

• Punti: Euclidean Distance
  q=2

Una “buona” misura di prossimità dipende MOLTO dalle applicazioni. I cluster dovrebbero essere invarianti sotto le trasformazioni “naturali” del problema. Inoltre, durante il clustering non è consigliabile normalizzare i dati che sono tratti da più distribuzioni.

Algoritmi di clustering

Gli algoritmi di clustering possono essere classificati come segue:

• Clustering esclusivo
• Clustering sovrapposto
• Clustering gerarchico
• Clustering probabilistico

Nel primo caso i dati sono raggruppati in modo esclusivo, così che se un certo punto dati appartiene ad un determinato cluster allora non può essere incluso in un altro cluster. Un semplice esempio di ciò è mostrato nella figura qui sotto, dove la separazione dei punti è ottenuta da una linea retta su un piano bidimensionale.

Al contrario, il secondo tipo, il clustering sovrapposto, usa insiemi fuzzy per raggruppare i dati, così che ogni punto può appartenere a due o più cluster con diversi gradi di appartenenza. In questo caso, i dati saranno associati a un valore di appartenenza appropriato.

Un algoritmo di clustering gerarchico si basa sull’unione tra i due cluster più vicini. La condizione iniziale è realizzata impostando ogni punto di dati come un cluster. Dopo alcune iterazioni raggiunge i cluster finali desiderati.

Infine, l’ultimo tipo di clustering utilizza un approccio completamente probabilistico.

In questo blog parleremo di quattro degli algoritmi di clustering più usati:

• K-means
• Fuzzy K-means
• Hierarchical clustering
• Mix of Gaussians

Ognuno di questi algoritmi appartiene a uno dei tipi di clustering elencati sopra. Mentre K-means è un algoritmo di clustering esclusivo, Fuzzy K-means è un algoritmo di clustering sovrapposto, Hierarchical clustering è ovvio e infine Mixture of Gaussians è un algoritmo di clustering probabilistico. Discuteremo di ogni metodo di clustering nei paragrafi seguenti.

K-Means Clustering

K-means è uno dei più semplici algoritmi di apprendimento non supervisionato che risolve il ben noto problema del clustering. La procedura segue un modo semplice e facile per classificare un dato set di dati attraverso un certo numero di cluster (supponiamo k cluster) fissati a priori. L’idea principale è quella di definire k centri, uno per ogni cluster. Questi centri dovrebbero essere posizionati in modo intelligente, perché una posizione diversa causa un risultato diverso. Quindi, la scelta migliore è quella di posizionarli il più lontano possibile l’uno dall’altro. Il passo successivo è quello di prendere ogni punto appartenente a un dato set di dati e associarlo al centroide più vicino. Quando nessun punto è in sospeso, il primo passo è completato e viene fatto un primo groupage. A questo punto dobbiamo ricalcolare k nuovi centroidi come baricentri dei cluster risultanti dal passo precedente. Dopo aver ottenuto questi k nuovi centroidi, un nuovo legame deve essere fatto tra gli stessi punti del set di dati e il nuovo centroide più vicino. Si è generato un ciclo. Come risultato di questo ciclo possiamo notare che i k centroidi cambiano la loro posizione passo dopo passo fino a quando non vengono fatti più cambiamenti. In altre parole i centroidi non si muovono più.

Infine, questo algoritmo mira a minimizzare una funzione obiettivo, in questo caso una funzione di errore al quadrato. La funzione obiettivo

dove

è una misura di distanza scelta tra un punto dati xi e il centro cluster cj, è un indicatore della distanza degli n punti dati dai loro rispettivi centri di cluster.

L’algoritmo è composto dai seguenti passi:

• Lasciamo che X = {x1,x2,x3,……..,xn} sia l’insieme dei punti dati e V = {v1,v2,…….,vc} sia l’insieme dei centri.
• Selezionare casualmente ‘c’ centri di cluster.
• Calcolare la distanza tra ogni punto dati e centri di cluster.
• Assegnare il punto dati al centro del cluster la cui distanza dal centro del cluster è minima tra tutti i centri del cluster.
• Ricalcolare il nuovo centro del cluster usando:

dove, ‘ci’ rappresenta il numero di punti dati nel cluster ith.

• Ricalcolare la distanza tra ogni punto di dati e i nuovi centri di cluster ottenuti.
• Se nessun punto di dati è stato riassegnato allora fermarsi, altrimenti ripetere dal punto 3).

Anche se si può dimostrare che la procedura terminerà sempre, l’algoritmo k-means non trova necessariamente la configurazione più ottimale, corrispondente al minimo della funzione obiettivo globale. L’algoritmo è anche significativamente sensibile ai centri di cluster iniziali selezionati a caso. L’algoritmo k-means può essere eseguito più volte per ridurre questo effetto.

K-means è un algoritmo semplice che è stato adattato a molti domini problematici. Come vedremo, è un buon candidato per l’estensione a lavorare con vettori di caratteristiche fuzzy.

La procedura k-means può essere vista come un algoritmo greedy per partizionare gli n campioni in k cluster in modo da minimizzare la somma delle distanze quadrate dai centri dei cluster. Ha alcune debolezze:

• Il modo di inizializzare le medie non è stato specificato. Un modo popolare per iniziare è quello di scegliere a caso k dei campioni.
• Può succedere che l’insieme dei campioni più vicini a mi sia vuoto, così che mi non possa essere aggiornato. Questo è un problema che deve essere gestito durante l’implementazione, ma è generalmente ignorato.
• I risultati dipendono dal valore di k e non esiste un modo ottimale per descrivere un “k” migliore.

Questo ultimo problema è particolarmente fastidioso, poiché spesso non abbiamo modo di sapere quanti cluster esistono. Nell’esempio mostrato sopra, lo stesso algoritmo applicato agli stessi dati produce il seguente clustering a 3 mezzi. È migliore o peggiore del clustering a 2 mezzi?

Purtroppo non esiste una soluzione teorica generale per trovare il numero ottimale di cluster per qualsiasi dato set di dati. Un approccio semplice è quello di confrontare i risultati di più esecuzioni con diverse classi k e scegliere la migliore secondo un dato criterio, ma dobbiamo stare attenti perché aumentando k si ottengono valori più piccoli della funzione di errore per definizione, ma aumenta anche il rischio di overfitting.

Fuzzy K-Means Clustering

Nel clustering fuzzy, ogni punto ha una probabilità di appartenere a ciascun cluster, piuttosto che appartenere completamente a un solo cluster come avviene nel k-means tradizionale. Fuzzy k-means cerca specificamente di affrontare il problema in cui i punti sono in qualche modo tra i centri o altrimenti ambigui, sostituendo la distanza con la probabilità, che naturalmente potrebbe essere qualche funzione della distanza, come avere la probabilità relativa all’inverso della distanza. Fuzzy k-means usa un centroide ponderato basato su queste probabilità. I processi di inizializzazione, iterazione e terminazione sono gli stessi usati in k-means. I cluster risultanti sono meglio analizzati come distribuzioni probabilistiche piuttosto che un’assegnazione rigida di etichette. Ci si deve rendere conto che il k-means è un caso speciale di fuzzy k-means quando la funzione di probabilità utilizzata è semplicemente 1 se il punto dati è più vicino a un centroide e 0 altrimenti.

L’algoritmo fuzzy k-means è il seguente:

• Assumiamo un numero fisso di cluster K.
• Inizializzazione: Inizializzare casualmente i k-means μk associati ai cluster e calcolare la probabilità che ogni punto dati Xi sia un membro di un dato cluster K,
  P(PointXiHasLabelK|Xi,K).
• Iterazione: Ricalcolare il centroide del cluster come centroide ponderato date le probabilità di appartenenza di tutti i punti dati Xi :

• Fine: Iterare fino alla convergenza o fino al raggiungimento di un numero di iterazioni specificato dall’utente (l’iterazione può essere intrappolata in alcuni massimi o minimi locali)

Per una migliore comprensione, possiamo considerare questo semplice esempio monodimensionale. Dato un certo insieme di dati, supponiamo di rappresentarlo come distribuito su un asse. La figura qui sotto lo mostra:

Guardando l’immagine, possiamo identificare due cluster in prossimità delle due concentrazioni di dati. Ci riferiremo a loro usando ‘A’ e ‘B’. Nel primo approccio mostrato in questo tutorial – l’algoritmo k-means – associavamo ogni punto di dati a un centroide specifico; quindi, questa funzione di appartenenza si presentava così:

Nell’approccio Fuzzy k-means, invece, lo stesso punto di dati dato non appartiene esclusivamente a un cluster ben definito, ma può essere collocato in una via di mezzo. In questo caso, la funzione di appartenenza segue una linea più morbida per indicare che ogni punto dati può appartenere a diversi cluster con diversi gradi di appartenenza.

Nella figura sopra, il punto dati mostrato come un punto rosso marcato appartiene più al cluster B che al cluster A. Il valore 0.2 di ‘m’ indica il grado di appartenenza ad A per tale punto dati.

Algoritmi di clustering gerarchico

Dato un insieme di N elementi da clusterizzare e una matrice di distanza (o somiglianza) N*N, il processo base del clustering gerarchico è questo:

• Iniziare assegnando ogni elemento ad un cluster, così che se si hanno N elementi, si hanno ora N cluster, ognuno contenente un solo elemento. Lascia che le distanze (somiglianze) tra i cluster siano uguali alle distanze (somiglianze) tra gli elementi che contengono.
• Trova la coppia di cluster più vicini (più simili) e uniscili in un unico cluster, così che ora hai un cluster in meno.
• Computa le distanze (somiglianze) tra il nuovo cluster e ciascuno dei vecchi cluster.
• Ripeti i passi 2 e 3 finché tutti gli elementi sono raggruppati in un unico cluster di dimensione N.

Clustering as a Mixture of Gaussians

C’è un altro modo di affrontare i problemi di clustering: un approccio basato sul modello, che consiste nell’utilizzare determinati modelli per i cluster e tentare di ottimizzare il fit tra i dati e il modello.

In pratica, ogni cluster può essere rappresentato matematicamente da una distribuzione parametrica, come una gaussiana. L’intero set di dati è quindi modellato da una miscela di queste distribuzioni.
Un modello di miscela con alta probabilità tende ad avere i seguenti tratti:

• le distribuzioni componenti hanno alti “picchi” (i dati in un cluster sono stretti);
• il modello di miscela “copre” bene i dati (i modelli dominanti nei dati sono catturati dalle distribuzioni componenti).

I principali vantaggi del clustering basato sul modello:

• sono disponibili tecniche di inferenza statistica ben studiate;
• flessibilità nella scelta della distribuzione dei componenti;
• ottenere una stima della densità per ogni cluster;
• è disponibile una classificazione “soft”.

Miscela di gaussiane
Il metodo di clustering più usato di questo tipo è basato sull’apprendimento di una miscela di gaussiane:

Un modello di miscela è una miscela di k distribuzioni componenti che collettivamente fanno una distribuzione di miscela f(x):

L’αk rappresenta il contributo del kesimo componente nella costruzione di f(x). In pratica, le distribuzioni parametriche (ad esempio le gaussiane), sono spesso utilizzate poiché è stato fatto molto lavoro per capire il loro comportamento. Se si sostituisce ogni fk(x) con una gaussiana si ottiene ciò che è noto come modelli a miscela gaussiana (GMM).

L’algoritmo EM

Massimizzazione dell’aspettativa presuppone che i dati siano composti da più distribuzioni normali multivariate (si noti che questa è un’assunzione molto forte, in particolare quando si fissa il numero di cluster!) In alternativa, EM è un algoritmo per massimizzare una funzione di verosimiglianza quando alcune delle variabili nel vostro modello non sono osservate (cioè quando avete variabili latenti).
Si potrebbe chiedere, se stiamo solo cercando di massimizzare una funzione, perché non usiamo semplicemente il meccanismo esistente per massimizzare una funzione. Bene, se si cerca di massimizzare questa funzione prendendo le derivate e ponendole a zero, si scopre che in molti casi le condizioni del primo ordine non hanno una soluzione. C’è un problema dell’uovo e della gallina, in quanto per risolvere i parametri del vostro modello avete bisogno di conoscere la distribuzione dei vostri dati non osservati; ma la distribuzione dei vostri dati non osservati è una funzione dei vostri parametri del modello.

L’Expectation-Maximization cerca di aggirare questo problema indovinando iterativamente una distribuzione per i dati non osservati, poi stimando i parametri del modello massimizzando qualcosa che è un limite inferiore della funzione di verosimiglianza attuale, e ripetendo fino alla convergenza:

L’algoritmo di Expectation-Maximization

• Inizia con un’ipotesi di valori dei parametri del modello
• fase E: Per ogni punto dati che ha valori mancanti, usate l’equazione del vostro modello per risolvere la distribuzione dei dati mancanti data la vostra ipotesi attuale dei parametri del modello e dati i dati osservati (notate che state risolvendo una distribuzione per ogni valore mancante, non per il valore atteso). Ora che abbiamo una distribuzione per ogni valore mancante, possiamo calcolare l’aspettativa della funzione di verosimiglianza rispetto alle variabili non osservate. Se la nostra ipotesi per il parametro del modello era corretta, questa verosimiglianza attesa sarà la verosimiglianza effettiva dei nostri dati osservati; se i parametri non erano corretti, sarà solo un limite inferiore.
• M-step: Ora che abbiamo una funzione di verosimiglianza attesa senza variabili non osservate, massimizziamo la funzione come faremmo nel caso completamente osservato, per ottenere una nuova stima dei parametri del modello.
• Ripetiamo fino alla convergenza.

Problemi associati al clustering

Ci sono una serie di problemi con il clustering. Tra questi:

• gestire un gran numero di dimensioni e un gran numero di dati può essere problematico a causa della complessità temporale;
• l’efficacia del metodo dipende dalla definizione di “distanza” (per il clustering basato sulla distanza). Se non esiste una misura di distanza ovvia dobbiamo “definirla”, il che non è sempre facile, specialmente in spazi multidimensionali;
• il risultato dell’algoritmo di clustering (che in molti casi può essere esso stesso arbitrario) può essere interpretato in modi diversi.

Applicazioni possibili

Gli algoritmi di clustering possono essere applicati in molti campi, per esempio:

• Marketing: trovare gruppi di clienti con comportamenti simili dato un grande database di dati sui clienti contenenti le loro proprietà e i loro record di acquisti passati;
• Biologia: classificazione di piante e animali date le loro caratteristiche;
• Assicurazioni: identificazione di gruppi di titolari di polizze assicurative auto con un alto costo medio dei sinistri; identificazione delle frodi;
• Studi sui terremoti: raggruppamento degli epicentri dei terremoti osservati per identificare le zone pericolose;
• World Wide Web: classificazione dei documenti; raggruppamento dei dati dei weblog per scoprire gruppi di modelli di accesso simili.