Metodi di base del Machine Learning

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 di del cluster a che

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 Metodi di base

4:

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 .

R

1

R è un algoritmo molto semplice di generazione di un albero di decisione con un

1

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 della classe che ricorre più

,

frequentemente nel dataset ed il tasso di errore della regola è valutato sempre sui

dati di traning L algoritmo genera un set di regole per ogni attributo che minimizza

. ʼ

l errore

ʼ .

R è quindi un algoritmo molto semplice e conveniente in termini di costi è molto

1 ,

semplice da implementare e può essere applicato a dataset con un grande

numero di attributi E 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 R

. 1

Riassunti Machine Learning 9

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

.

Con R poi si possono trattare anche attributi numerici basta fare una

1 ,

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

. ,

e ho tutti yes e un solo no quindi quel no potrebbe essere un valore non

64 70 ,

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 R è quello di considerare tutti gli attributi di

1

uguale importanza e statisticamente indipendenti sicuramente non realistico ma

,

che funziona molto bene con set di dati reali Lo schema noto come Naive

. ,

può essere implementato in maniera rapida e non richiede la messa a

Bayes ,

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 perché sono le istanze

ʼ , 2/9, 9 9

yes outlook e così via Abbiamo così

del training set in cui la classe è yes Per 3/9 .

. 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 che ci permette di calcolare la

teorema di Bayes

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 traning

.

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 Estiamtor

. .

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

1

ottenere

Il valore di µ che è stato impostato a in precedenza fornisce efficacemente un

, 3 ,

peso che determina quanto influenti sono i valori a priori di e per

1/3, 1/3 1/3

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 p p e p hanno somma

1, 2, 3 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 omessa 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 e di fatto non è una probabilità

1 .

Tuttavia l area sottesa dalla curva densità di probabilità deve essere La

, ʼ 1.

relazione tra probabilità e densità di probabilità è approssimativamente la

seguente

:

Alberi di decisione

L algoritmo R permette la costruzione di un albero con un solo nodo se però

ʼ 1 ,

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 e applicare il processo in modo ricorsivo per ogni ramo utilizzando solo le

,

istanze che raggiungono quel ramo La ricorsione per un ramo viene fermata

.

Riassunti Machine Learning 13

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 delle istanze ma

, 100% ,

si potrebbe avere il problema dell overfitting con tutte le foglie pure Per ridurre

' .

questi problemi si useranno tecniche di pruning .

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 che è misurata in Associata ad ogni nodo

ʼ informazione bits .

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 metereologiche

, :

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 ,

Questa misura si traduce poi in bits info bits info

3, 2 . , ([2, 3])= 0.971 , ([4, 0])= 0.0

bits info bits Calcoliamo quindi il valore informativo medio

, ([3, 2])= 0.971 .

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 mogliore è quella che ha come figlio unn noodo 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 attibuti son

ʼ ʼ

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 informazi