Appunti esame di Data Mining

∣A∣

C overage(r) = ​

∣D∣

Accuratezza, frazione dei record che soddisfano l’antecedente, soddisfano anche il

conseguente della regola ∣A ⋂ y∣

Accuracy(r) = ​

∣A∣

Regole mutuamente esclusive: un insieme di regole R è detto mutuamente esclusivo se

nessuna coppia di regole può essere attivata dallo stesso record, ogni record è coperto al più

da una regola.

Regole esaustive: un insieme di regole R ha una copertura esaustiva se esiste una regola per

ogni combinazione di valori degli attributi, ogni record è coperto da almeno una regola.

Non sempre è possibile determinare un insieme di regole esaustive e mutualmente esclusive.

Mancanza di mutua esclusività

Un record può attivare più regole dando vita a classificazioni alternative

Soluzione

Definire un ordine di attivazione delle regole. Si parla in questo caso di liste di

decisione

Assegnare il record alla classe per la quale vengono attivate più regole

Mancanza di esaustività

Un record può non attivare nessuna regola

Soluzione

Riassunto Data Mining 35

Utilizzare una classe di default a cui il record viene associato in caso di non attivazione

delle regole

Le regole sono ordinate secondo una data priorità, un insieme ordinato di regole è anche

chiamato lista di decisione

Quando un record è sottomesso al classificatore, è assegnato alla classe della prima regola

che viene attivata e se nessuna regola è attivata, è assegnato a una classe di default.

Modalità di ordinamento

Ordinamento Rule-based, le singole regole sono ordinate in base alla loro qualità

Ordinamento Class-based,

Gruppi di regole che determinano la stessa classe compaiono di seguito nella lista.

Il rischio con questa soluzione è che una regola di buona qualità sia superata da una regola

di qualità inferiore ma appartenente a una classe importante

Costruzione delle regole

Metodi diretti, estraggono le regole direttamente dai dati

Metodi indiretti, estraggono le regola dal risultato di altri metodi di classificazione come, ad

esempio, i decision tree

Metodo diretto: sequential covering

1. Inizio da una regola vuota

2. Incrementa la regola usando la funzione Learn One Rule

3. Rimuovi i record di training coperti dalla regola

4. Ripeti i passaggi (2) e (3) fino a quando il criterio di arresto non viene soddisfatto

Eliminazione delle istanze dal training set

Serve a:

Per le istanze correttamente classificate, evitare di generare sempre la stessa regola o

evitare di sovrastimare l’accuracy della prossima regola

Per le istanze non classificate correttamente, evitare di sottostimare l’accuracy della

prossima regola

Chiameremo esempi positivi (+) tutte le tuple del training set che appartengono alla

classe y. Sono esempi negativi (-) tutti gli altri.

Learn one rule: 2 strategie diverse

Riassunto Data Mining 36

L’obiettivo dell’algoritmo è trovare una regola che copra quanti più possibili esempi positivi e

quanto meno possibili esempi negativi, il problema è complesso dato che lo spazio di ricerca è

esponenziale.

Le regole sono costruite considerando progressivamente un nuovo possibile atomo ossia una

possibile coppia (Attributo, Valore).

Valutazione delle regole: Accuracy

E’ necessario un criterio per scegliere quale atomo aggiungere

: numero di istanze coperte dalla regola r (coverage)

n : numero di istanze correttamente classificate da r

n r ​

: numero di classi

k n r ​

Accuracy(r) = ​

n

Limitata applicabilità poiché non considera la copertura

Valutazione delle regole: Likelihood Ratio

Un test statistico che può essere usato per potare regole che hanno una copertura scarsa è:

k f i ​

2 og

R = ∑ f l

i

​ ​ ​

e i ​

i=1

dove:

 è il numero di classi,

k  è la frequenza osservata degli esempi di classe e che sono coperti dalla regola,

f i ​

 è la frequenza prevista di una regola che effettua previsione a casa

e i ​

Valutazione delle regole: Laplace

Metriche che considerano la coverage: pesano l’accuracy in base alla coverage

f + 1

+ ​

Laplace(r) = ​

n+

dove:

 è il numero di classi,

k  è il numero di esempi coperti dalla regola r

n è il numero di esempi positivi coperti dalla regola r

f +

Note:

Riassunto Data Mining 37

Se la copertura è 0, assumendo distribuzione uniforme dei dati, l’indice si riduce alla

probabilità a priori della classe (1/k)

Se la copertura è alta, l’indice tende asintoticamente al valore dell’accuracy

Per i valori bassi di copertura k tende a ridurre il valore dell’indice

Valutazione delle regole: m-estimate

Metriche che considerano la coverage: pesano l’accuracy in base alla coverage

f + kp

+ +

​ ​

m − estimate(r) = ​

n + k

dove:

 è il numero di classi

k  è il numero di esempi coperti della regola

n r

è il numero di esempi positivi coperti dalla regola 

f r

+  è la probabilità a priori della classe +

p + ​

Valutazione delle regole: FOIL

Misura la variazione dovuta all’incremento della regola con l’aggiunta di un nuovo atomo.

Supponiamo che la regola  copra  esempi positivi e  esempi negativi.

r : A → p n

o 0 0

​ ​ ​

Dopo aver aggiunto un nuovo atomo B, la regola estesa :

r 1 ​

 copre  esempi positivi e  esempi negativi.

A, B → + p n

1 1

​ ​

Il guadagno di informazioni di FOIL della regola estesa è definito come segue:

p p

1 0

​ ​

F oilGain(r , r ) = p log

(log −

0 1 1 2 2

​ ​ ​ ​ ​ ​ ​

p + n p + n

1 1 0 0

​ ​ ​ ​

Tende a favorire regole che hanno elevate coverage e accuracy

Criterio di stop dell’estensione di una regola

Calcola il gain, se il gain non è significativo stop e ripeti i passi precedenti fino a quando c’è un

miglioramento.

Rule Pruning: ha l’obiettivo di semplificare le regole per migliorare l’errore di generalizzazione

delle regole, può essere utile visto che l’approccio di costruzione è greedy, o possono essere

utilizzate le tecniche viste per gli alberi decisionali.

Esempio (Reduced error pruning):

Rimuovi a turno un atomo dalla regola

Riassunto Data Mining 38

Elimina l’atomo la cui rimozione comporta il massimo miglioramento dell’error rate sul

validation set

Ripeti i passi precedenti se c’è un miglioramento

Metodi diretti: RIPPER

Approccio basato sul sequential covering.

Per problemi a 2 classi, scegli una delle classi come classe positiva e l’altra come classe

negativa

Costruisci le regole per la classe positiva

La classe negativa sarà la classe di default

Per problemi multiclasse

Ordina le classi in base a un criterio di rilevanza della classe

Costruisce le regole a partire dalla classe più piccola e considerando il resto delle istanze

come classe negativa

Ripeti l’operazione con le classi successive

Costruzione del set di regole:

Usa l’algoritmo “sequential covering”

Trova la regola migliore che copre l’attuale serie di esempi positivi

Elimina sia gli esempi positivi che quelli negativi coperti dalla regola

Ogni volta che una regola viene aggiunta al set di regole, calcola la lunghezza della descrizioni,

interrompi l’aggiunta di nuove regole quando la lunghezza della descrizione è d bit più lunga

della lunghezza della descrizione più piccola ottenuta finora.

Learn-one-rule:

Inizia con una regola vuota

Aggiungi atomi finché determinano un miglioramento del FoilGain

Interrompi quando la regola non copre più esempi negativi

Esegui il pruning utilizzando la tecnica dell’incremental reduced error pruning, esegue il

pruning dopo ogni passo di growing

Metodi di pruning: elimina dalla regola gli atomi la cui rimozione massimizza: v = (p −

.

n)/(p + n)

: numero di esempi positivi coperti dalla regola nel validation set

p : numero di esempi negativi coperti dalla regola nel validation set

n

Riassunto Data Mining 39

Ottimizzazione del set di regole:

Per ciascuna regola  nel set di regole R

r

Considera 2 regole alternative:

Regola di sostituzione (r*): Sviluppa una nuova regola da zero

Revised rule (r’): estendi r con l’aggiunta di un atomo

Confronta il set di regole per r con il set di regole per r* e r’

Scegli l’insieme di regole che minimizzano MDL (Minimum Description Lenght)

Ripeti la generazione delle regole e l’ottimizzazione delle regole per gli esempi positivi

rimanenti

Metodi indiretti

E’ possibile trasformare un decision tree in un insieme di regole.

Ad ogni percorso radice-foglia corrisponderà una foglia (sono mutualmente esclusive per

definizione di albero), saranno poi applicati opportune tecniche di pruning

Metodi indiretti: C4.5rules

Estrai le regole da un albero di decisione non potato.

Per ogni regola, ,

r : A → y

Considera una regola alternative  dove  è ottenuto rimuovendo un atomo da

′ ′ ′

r : A → y A

A

Confronta il tasso di errore pessimistico per r con quello di tutte le regole 

′

r

Taglia l’atomo se una delle regole alternative ha un tasso di errore pessimistico inferiore

Ripeti fino a quando non è più possibile più migliorare l’errore di generalizzazione

Invece di ordinare le regole, ordina sottoinsieme di regole (ordinamento di classe)

Ogni sottoinsieme di regole ha lo stesso conseguente (classe)

Calcola la description length di ciascun subset

Description length = L(error) + gL(model)

g è un parametro che prende in considerazione la presenza di attributi ridondanti in un

insieme di regole

Albero decisionali vs regole

L’insieme delle regole prodotte è generalmente diverso, la differenza fondamentale tra le due

tecniche consiste nel fatto che nel procedimento di costruzione:

Riassunto Data Mining 40

la bontà del criterio di partizionamento scelto in ogni nodo dell’albero considera la qualità di

tutti i figli generati

il criterio con cui viene aggiunto un atomo alla regola valuta solo la bontà della classe che

si viene a determinare

Vantaggi dei classificatori Rule-based

Hanno caratteristiche abbastanza simili agli alberi decisionali

Altamente espressivi come alberi decisionali

Facile da interpretare

Prestazioni paragonabili agli albe