Metodi di base del Machine Learning

Metodi di machine learning

In generale non è necessario conservare tutte le istanze di training nel modello. Tipicamente si creano delle regioni rettangolari che racchiudono istanze della stessa classe. Istanze sconosciute che ricadono in uno dei rettangoli saranno assegnate a quella classe. Le istanze che ricadono fuori dai rettangoli saranno soggette alle usuali tecniche di nearest neighbor. Naturalmente utilizzando i rettangoli otteniamo decisioni differenti rispetto al caso precedente e riusciamo ad essere più conservativi perché, come detto, se un’istanza non ricade in alcun rettangolo si usa la tecnica nearest neighbor.

Clustering

Il clustering è una tecnica di machine learning in cui vengono raggruppati i dati in base a delle loro similarità. L’output per un modello di clustering è un diagramma che mostra come le varie istanze vanno nei diversi cluster. La più semplice forma di cluster è quella in cui ad ogni istanza si associa il numero del cluster a cui potrebbe portare a partizionare le istanze su un piano bidimensionale. Alcuni algoritmi permettono ad un’istanza di appartenere a più cluster contemporaneamente, quindi possono formarsi dei cluster sovrapposti. Altri ancora associano i cluster in maniera probabilistica, quindi ogni istanza ha dei gradi di appartenenza ad ogni cluster. Come output possiamo avere anche dei cluster gerarchici che vengono rappresentati con dei dendrogrammi.

Capitolo 4: metodi di base

Analizziamo i metodi di base per risolvere i quattro tipi di problemi illustrati: classificazione, associazione, predizione numerica e clustering. In generale gli algoritmi semplici sono quelli che funzionano meglio.

R1

R1 è un algoritmo molto semplice di generazione di un albero di decisione con un singolo livello che esprime un set di regole di classificazione per un singolo attributo. L’algoritmo genera delle regole testando ogni attributo, creando dei rami su questi valori; il ramo migliore è determinato dalla classe che ricorre più frequentemente nel dataset ed il tasso di errore della regola è valutato sempre sui dati di training. L’algoritmo genera un set di regole per ogni attributo che minimizza l’errore.

R1 è quindi un algoritmo molto semplice e conveniente in termini di costi, è molto semplice da implementare e può essere applicato a dataset con un grande numero di attributi. È efficace in molti casi per la sua semplicità, adattandosi bene alla struttura dei dati reali con alta accuratezza; infatti i set di regole semplici spesso sono interpretati ed applicati meglio rispetto a quelli più complessi. R1 presenta però alcune limitazioni. L’algoritmo può generare regole non accurate se la struttura dei dati su cui si applica è complessa o richiede più di un attributo per determinare la classe. Quindi è fortemente dipendente dal dataset, l’algoritmo inoltre è sensibile al rumore ed agli outliers.

Riassunti Machine Learning 9

Con R1 poi si possono trattare anche attributi numerici, basta fare una discretizzazione. La discretizzazione implica il partizionamento di questa sequenza utilizzando dei breakpoint. Una possibilità è quella di piazzare i breakpoint ogni volta che la classe cambia generando diversi gruppi.

Il problema della discretizzazione è che il numero di categorie costruite è abbastanza elevato e la presenza degli outliers può essere critica. Ad esempio, tra 64 e 70 ho tutti yes e un solo no, quindi quel no potrebbe essere un valore non significativo o rumore. Posso quindi definire un numero minimo di campioni che devono appartenere a un bin.

Infine, se un attributo numerico ha valori mancanti, si crea per essi una categoria aggiuntiva e si applica la procedura di discretizzazione solo per quelle istanze i cui valori degli attributi sono definiti.

Modelli probabilistici

Un approccio diverso da quello di R1 è quello di considerare tutti gli attributi di uguale importanza e statisticamente indipendenti, sicuramente non realistico ma che funziona molto bene con set di dati reali. Lo schema noto come Naive Bayes può essere implementato in maniera rapida e non richiede la messa a punto di alcun parametro, a differenza di altri classificatori. Maggiore è il numero di parametri, più complicato è trovare il loro giusto valore. Consideriamo un esempio.

Riassunti Machine Learning 10

Consideriamo una nuova istanza da classificare: la classe e l’attributo, la probabilità è di 2/9, perché sono le 9 istanze del training set in cui la classe è yes. Per outlook, 3/9 e così via. Abbiamo così per temperature che la probabilità della classe yes e no sono:

Likelihood of yes = 2/9 3/9 3/9 3/9 9/14 0.0053

Likelihood of no = 3/5 1/5 4/5 3/5 5/14 0.0206

Questi valori devono essere normalizzati per ottenere delle probabilità cosicché la loro somma faccia 1.

Da qui possiamo utilizzare il teorema di Bayes che ci permette di calcolare la probabilità di un’ipotesi H dato un certo evento E. L’evento E è dato da una serie di osservazioni sugli attributi, quindi E è un’istanza:

Riassunti Machine Learning 11

Teorema di Bayes

Considerando l’esempio di prima, le probabilità combinate dei tre attributi è:

Per quanto riguarda il denominatore viene eliminato attraverso una normalizzazione e quindi la probabilità finale di yes è detta a priori poiché è calcolata non sapendo le evidenze di un giorno specifico ma solamente quelli presenti nelle istanze di training.

Il problema di questo approccio consiste nel fatto che se uno dei valori che assume un attributo non compare mai nel dataset, la probabilità che quell’attributo abbia quel valore data la classe è zero, questo poiché le probabilità sono moltiplicate nel teorema. Per risolvere questo possiamo aggiungere alle singole probabilità degli attributi al numeratore e al denominatore per compensare così 1 3 da non avere mai probabilità nulle. Questa tecnica è detta Laplace Estimator.

Invece di aggiungere 1 potremmo utilizzare una costante piccola µ così da ottenere.

Il valore di µ che è stato impostato a 3 in precedenza fornisce efficacemente un peso che determina quanto influenti sono i valori a priori di 1/3, 1/3 e 1/3 per ciascuno dei tre possibili valori attributo. Un µ grande indica che questi valori a priori sono molto importanti rispetto alle nuove evidenze provenienti dal set di formazione, mentre un µ piccolo li rende meno influenti. Infine, non c’è una particolare ragione per dividere µ in tre parti uguali nei numeratori: potremmo utilizzare una diversa distribuzione se ritenuto opportuno.

Riassunti Machine Learning 12

Dove p1, p2 e p3 hanno somma 1.

Valori mancanti ed attributi numerici

Uno dei punti di forza del classificatore Naive Bayes è che i valori mancanti non sono un problema. Per esempio, se un valore di un attributo fosse assente nel calcolo, verrebbe semplicemente omesso nel conteggio delle frequenze e le probabilità sono calcolate in base al numero di valori che realmente ci sono piuttosto che sul numero totale di istanze.

Per quanto riguarda i valori numerici, per gestirli facciamo l’assunzione che abbiano una distribuzione normale o gaussiana e quindi utilizzo la seguente funzione di densità andando a calcolare dai dati di training la media e la deviazione standard.

La funzione densità di probabilità di un evento è strettamente correlata alla probabilità dell’evento stesso, anche se non è la stessa cosa. Infatti, la densità di probabilità può essere anche maggiore di 1 e di fatto non è una probabilità. Tuttavia l’area sottesa dalla curva densità di probabilità deve essere 1. La relazione tra probabilità e densità di probabilità è approssimativamente la seguente:

Alberi di decisione

L’algoritmo R1 permette la costruzione di un albero con un solo nodo; se però vogliamo costruire un albero con più nodi bisogna operare una scelta degli attributi da inserire nei nodi e generare le partizioni. Questo approccio utilizza un metodo ricorsivo di tipo Divide and Conquer che prevede quattro passaggi:

• Selezionare un test per il nodo radice.
• Creare un ramo per ogni possibile risultato del test.
• Dividere le istanze in sottoinsiemi, uno per ogni ramo che si estende dal nodo.
• Applicare il processo in modo ricorsivo per ogni ramo utilizzando solo le istanze che raggiungono quel ramo.

La ricorsione per un ramo viene fermata quando tutte le sue istanze appartengono alla stessa classe. Tuttavia, se si ha una foglia per ogni istanza si otterrà un albero che classifica il 100% delle istanze ma si potrebbe avere il problema dell’overfitting con tutte le foglie pure. Per ridurre questi problemi si useranno tecniche di pruning.

Riassunti Machine Learning 13

Per scegliere quale attributo usare come radice si seleziona l’attributo che garantisce la purezza complessiva migliore. Un insieme di istanze è considerato puro se tutte le istanze appartengono alla stessa classe e quindi si può chiudere quel ramo arrivando a una foglia, ottenendo un albero più piccolo. Per misurare la purezza si ricorre all’informazione che è misurata in bits. Associata ad ogni nodo dell’albero rappresenta la quantità di informazione da specificare quando viene classificata una nuova istanza. Tra tutti gli attributi disponibili per fare lo split scelgo l’attributo che mi dà il maggior incremento dell’information gain.

Ad esempio consideriamo gli alberi sulle condizioni meteorologiche:

Nell’attributo outlook calcoliamo l’information gain come il numero di istanze della classe yes ed il numero di quella no, quindi in questo caso avremo 2, 3, 4, 0, 3, 2. Questa misura si traduce poi in bits info bits info 3, 2. Info ([2, 3]) = 0.971 bits, info ([4, 0]) = 0.0 bits, info ([3, 2]) = 0.971 bits. Calcoliamo quindi il valore informativo medio dell’intero split:

Riassunti Machine Learning 14

E quindi l’information gain creato dallo split dell’attributo outlook è.

Calcolando il gain per ogni attributo possiamo decidere come dividere i dati nell’albero.

La scelta migliore è quella che ha come figlio un nodo completamente puro, quindi outlook. Da qui possiamo continuare a dividere i rami calcolando l’information gain degli altri attributi dopo lo split.

L’informazione quindi risulta fondamentale per scegliere l’ordine degli attributi con la quale sviluppare l’albero. Come misura però deve soddisfare alcune proprietà, consideriamo l’esempio fatto prima:

Quando il numero di sì o di no è zero l’informazione.