Appunti seconda parte Data Mining

C

+

esempi classificati correttamente, cioè il numero di e coperti dalla regola,

l’accuratezza del training set è data da P(+|c)=n /n.

C

Più correttamente, essa è la precision della regola, perché è la frazione degli esempi

classificati come positivi che sono effettivamente positivi (probabilità della classe

positiva data la regola).

Questa stima prende il nome di stima attraverso la frequenza relativa (si tratta di un

rapporto fra conteggi).

Questa stima ha dei problemi nel caso di pochi esempi.

Infatti, se n = 0, cioè se la regola copre 0 positivi, allora l’accuratezza sarà P(+|c)=0

C

anche se n è molto piccolo, cioè n potrebbe essere una stima molto affidabile.

Inoltre, se la regola copre 0 esempi, cioè n=0, allora P(+|c) diventa 0/0 e non si può

calcolare.

In questi casi si dimostra che la stima attraverso la frequenza relativa non è affidabile

+1

n c

(+¿ ) =

ed è meglio usare la stima di Laplace, che nel caso di due classi vale ,

P c n+2

+1

n c

(+¿ ) =

mentre nel caso di N classi è .

P c n+2

Questo non crea problemi nel caso di n e n pari a 0 e in tal caso la precision verrà

C

esattamente ½.

Per n ed n grandi, i fattori 1 e 2 sono trascurabili ed entrano in gioco solamente per

C

piccoli valori di n e n.

C

Questa stima di Laplace assume che le 2 (o N) classi siano uniformemente distribuite

nel training set.

Se non è vero, allora bisogna usare la stima-m, cioè data p la probabilità che un

esempio estratto a caso dal training set abbia la classificazione assegnata dalla regola

+

n m∗p

c

(+¿ ) =

(classe p) e m un peso, allora .

P c n+m

Questa è una forma generale della stima della precision e che comprende tutte le altre

viste prima.

Infatti, se m=0, si ottiene l’accuratezza, mentre se m=N e p=1/N, cioè tutte le classi

sono ugualmente probabili, ottengo la stima di Laplace.

Infine, si nota che per grandi valori di n e n la stima-m e la stima di Lapalce si

C

avvicinano alla frequenza relativa, cioè queste correzioni non influenzano la stima.

Tipicamente, la ricerca da generale a specifico è la ricerca hill-climbing senza

backtracking, cioè si sceglie di specializzare la regola con le performance più alte

(sempre nel caso apprendimento di attributi booleani).

Il problema di tale ricerca è che è molto greedy e che può portare a scelte subottimali

in alcuni passi.

Per ridurre quest’ultimo rischio viene a volte effettuata una ricerca beam, in cui ad

ogni passi non si mantiene una sola ipotesi, la migliore, ma una lista dei migliori k

candidati (tra i sistemi che compiono ricerca beam top-down ci sono CN2 e AQ,

quest’ultimo basato su un esempio seme per guidare la ricerca).

Se l’attributo target NON è booleano (più di due classi) non apprendiamo più

solamente regole che hanno nel conseguente vero, cioè classe positiva, ma si

apprende un insieme di regole con diversi conseguenti.

In tal caso esistono due approcci:

Si tiene una lista ordinata di regole, in cui per classificare un nuovo esempio si

 scorrono dalla prima regola all’ultima e la prima che fa match fornisce nel

conseguente la classificazione dell’esempio

L’ultima regola dell’insieme è una regola di default che classifica tutti gli esempi

che non fanno match nessuna regola (procedura utilizzata dal sistema CN2)

Si tiene una lista NON ordinata di regole, in cui si prende l’esempio da

 classificare, si controlla se fa match con ogni regola ed infine si raccolgono tutte

le regole che fanno match, restituendo come classe quella più frequente fra gli

esempi di training coperti dalle regole che fanno match.

Se non fa match con nessuna regola, la classificazione è data dalla classe più

frequente tra gli esempi di training (procedura utilizzata dal sistema AQ)

Consideriamo ora l’algoritmo

d’apprendimento sequenziale di CN2, il

quale differisce da quello sequenziale

visto prima, perché in grado di imparare

regole per diversi concetti e la

procedura APPRENDI_UNA_REGOLA non

restituisce una regola, ma solo un

antecedente e il cui conseguente è

aggiunto solo successivamente.

Entrando nel dettaglio, l’algoritmo ha

come input l’attributo target, gli attributi

e gli esempi.

Dopo aver inizializzato l’insieme delle regole apprese con l’insieme vuoto, viene

effettuato un ciclo in cui si richiama la procedura APPRENDI_UN_ANTECEDENTE per

apprendere il miglior antecedente possibile e con l’attributo di input k è la dimensione

del beam.

Successivamente chiamo E’ l’insieme di esempi coperti da Best_ant e lo rimuoviamo

dall’insieme di esempi.

Dopodiché chiamo C la classe più comune fra gli esempi di E’ e aggiungo la regola “if

Best_ant then class=C’” alla fine dell’insieme Regole_apprese e ripeto questo

procedimento finché Best_ant è nullo, oppure l’insieme degli esempi è vuoto.

Infine, aggiungiamo alla fine di Regole_apprese la regola di default “class=C” dove C è

la classe più frequente in Esempi e restituisco l’insieme Regole_apprese.

Entrando ne dettaglio, la

funzione

APPRENDI_UN_ANTECEDENTE

parte da un beam, che

contiene da un antecedente

vuoto, e da una variabile

Best_ant inizializzata

anch’essa con l’antecedente

vuoto.

Dopodiché viene effettuato

un ciclo ripetuto finché Beam non è vuoto e in cui si specializzano tutti gli antecedenti

di beam predisponendo due insiemi: il primo è All_contraints ed è un insieme di vincoli

nella forma attributo=valore (nel caso di attributi tutti discreti), mentre il secondo è

Nuovo_beam.

Quest’ultimo è costruito iterando per ciascun h in Beam e in ciascun vincolo c in

All_contraints, creando una specializzazione di h aggiungendo c.

A questo punto si rimuove da Nuovo_beam tutte le ipotesi duplicate, inconsistenti (es.

se aggiungo a=v e a=w, otterrò un antecedente che non sarà mai vero) o che erano

già in Beam. Successivamente, com’è riportato a

lato,

aggiorniamo il miglior antecedente.

Specificatamente, per ciascun

antecedente h in Nuovo_beam se le

performance di h sono migliori del

miglior antecedente, allora assegno h

alla variabile best_ant e aggiorniamo il

beam.

Quest’ultima operazione farà si che la

nuova versione del beam sia i migliori k membri di Nuovo_beam secondo la misura di

performance.

Dato un concetto c, gli esempi positivi per gli altri concetti sono esempi negativi per c.

Di conseguenza, quando tolgo un esempio di un concetto c nel ciclo di covering

rimuovo anche degli esempi negativi per gli altri concetti, rischiando di generare

regole apprese in seguito troppo generali per gli altri concetti, che quindi ci sia la

possibilità che coprano esempi NEGATIVI nel training set.

Questo problema è risolto dal fatto che le regole sono valutate in ordine, per cui anche

se le ultime regole sono molto generali, non è un problema perché le regole precedenti

intercettano gli esempi.

Come misura di performance, in APPRENDI_UN_ANTECEDENTE si usa l’Entropia, ed

( )

(| |) (| |)

S S

k k

∑ ∑

j j ( )

( )=−

essa è pari a , cioè meno la somma di j

= )

info S log P c log P(c

2 j 2 j

| | | |

S S

j=1 j=1

che va da 1 a k della probabilità della classe j fra gli esempi coperti dalla regola.

Quindi, se S è l’insieme degli esempi coperti dall’antecedente, c /c sono le classi e

1 k

S /S gli esempi di S che appartengono alla classe j, allora l’entropia è pari alla

1 k

relazione sopra, la quale viene calcolata stimando le probabilità delle classi con la

frequenza relativa (cardinalità di S fratto la probabilità della classe j).

j

Esempio: consideriamo nuovamente l’esempio relativo alle giornate adatte a giocare a

tennis, in cui tutti gli attributi sono discreti e applichiamo l’algoritmo.

Partiamo dalla prima

chiamata di

APPRENDI_UN_ANTECEDENTE, inizializzando beam l’insieme con l’antecedente vuoto e

best_ant con l’antecedente vuoto.

Successivamente specializzo gli antecedenti di beam, prendendoli e tutti e

specializzandoli in tutti i modi.

Nello specifico, dal momento che l’antecedente è l’insieme vuoto, i vincoli che posso

aggiungere sono tutti quelli nella forma attributo = valore (outlook=sunny,

outlook=overcast, outlook=rain, ecc..).

A questo punto valuto le performance, mediante il colcolo

dell’entropia dell’insieme di esempi coperti da questi

antecedenti.

Per esempio, nel caso di outlook=sunny, abbiamo 2 esempi

positivi e 3 negativi (tabella precedente), per cui l’entropia

vale 0.97 (calcolo a lato).

Per outlook=overcast, abbiamo esempi provenienti solo

dalla classe positiva (D5, D6, D7, D8), per cui avrò

l’entropia pari a 0.

Si osserva che l’attributo con il valore dell’entropia più alto è proprio quest’ultimo,

mentre tutti gli altri hanno sono negativi.

A questo punto aggiorno il best_ant, assegnadogli

outlook=overcast, e il beam, scegliendo una dimensione

pari a 2 e mettendo i assegnadogli i due antecedenti

migliori, quindi outlook=overcast e humid=normal.

Successivamente procedo con una nuova iterazione, in cui

Nuovo_beam sarà dato dall’aggiunta agli antecedenti

precedenti di un’altra condizione.

Nel nostro caso di outlook=overcast, dovrò aggiungere le

condizioni per tutti gli attributi eccetto outlook (tempo=hot,

tempo=mild, ecc…).

In maniera analoga procedo anche per l’attributo

humid=normal. A questo punto si osserva che calcolando le

performance di ciascuna antecedente, l’entropia

è pari a 0 in ogni caso, perché outlook=overcast

identificava già un insieme uniforme, per cui se

aggiungo un'altra condizione vado a restringere

tale insieme (che rimane comunque uniforme).

Invece, nel caso degli antecedenti che hanno

humid=normal, abbiamo valori d’entropia

diversi (es. -0.92 e -0.81).

A questo punto mi chiedo se debba aggiornare

il migliore antecedente (NO, perché non ho

trovato degli antecedenti con una misura di

performance più alta di quella di

outlook=overcast).

In questo caso aggiorno solo il Beam, tenendo i due antecedenti con le performance

migliori (prendo una qualsiasi coppia di antecedenti con