Data mining

Se una istanza (e-mail) passa il test del descrittore dell’oggetto, al-

lora viene riconosciuto come ”spam”, altrimento come ”non spam”.

6

Se un ipotesi verifica che un oggetto é in un concetto, si dice

covers(H,e)

Dove H é l’ipotesi, ed e l’oggetto. L’insieme E contiene tutti gli oggetti,

+

i risultati positivi di E sono contenuti in H, mentre i risultati negativi di

−

E non sono contenuti in H. 7

2 Alberi di decisione

1 • Ogni nodo non foglia é associato ad un test e ad un attributo

• Ogni foglia é una classe

Ogni elemento dell’albero é un test booleano per ogni ramo, ecco che possono

essere scritte delle equazioni logiche.

⇒

Esempio, a and b d

3 Reti bayesiane

• Componente qualitativa

• Componente quantitativa, per ogni nodo fornisco la probabilitá di ogni

nodo

1 Vedi slide 21 di ”02-ML introuction” 8

4 Linguaggi Proposizionali

I linguaggi proposizionali sono i piú utlizzati, tuttavia é complicato generare

delle istanze che hanno un numero diverso di variabili e di classi.

Esempio: una famiglia ha un numero n di persone, e ogni persona ha un

numero diverso di attributi (ha o non ha figli ecc...).

5 Linguaggi di Primo Ordine

Viene identificato un attributo ad ogni oggetto, in questo modo non ho

vincoli sul numero di componenti della classe e sul numero di attributi di

ogni istanza, un esempio é la famiglia jones, con nonno dave, padre mike e

figlio junior.

family(jones,dave).

family(jones,mike).

family(jones,junior).

age(dave,70).

hair(dave,white).

age(mike,35).

age(junior,3).

father(dave,mike).

father(mike,junior).

La soluzione dei problemi é di tipo logico, infatti le tabelle dei database,

vengono viste come relazioni, in maniera da poter risolvere delle query in

modo pi semplice (per il programmatore) e logico.

9

pos—neg—Predizione della classe

TP—FN—pos

FP—TN—neg

6 Metodo di valutazione

Nel caso in cui si hanno due valori, la tabella di valutazione viene calcolata

nel seguente modo. TP=true positive

FN=false negative

FP=false positive

TN=true negative

P=TP+FN=positive

N=FP+TN=negative

Accuracy=(TP+TN)/(TP+TN+FN+FP)

Error rate=(FP+FN)/(TP+TN+FN+FP)=1-Accuracy

TP Rate=TP/(TP+FN)=TP/P

FP Rate=FP/(FP+TN)=FP/N

Precision=TP/(TP+FP)

Recall=TP/(TP+FN)=TP Rate

F-meaure=2*Precision*Recall/(Precision+Recall)

10

7 Calcolo Combinatorio

≤ ≤

Una probabilitá 0 P (A) 1 é un valore che rappresenta la probabilitá di

manifestare l’evento A. Esso puó essere calcolato

• in frequenza

• in Bayes (Probabilitá Bayesiana)

7.1 Regola della somma

Due eventi se sono mutualmente esclusivi, la probabilitá dei due eventi pos-

sono essere sommati tra loro (Regola della somma o margizalization).

P (A) = P (A and B or A and !B = P (A and B) + P (A and !B)

7.2 Regola del prodotto

La probabilitá che un evento A sia vero dato che l’evento B é vero

P (A,B)

P (A|B) = P (B) 11

8 Apprendimento di Ricerca

La fase di training avviene attraverso la ricerca all’interno dello spazio delle

ipotesi H.

Per ogni ipotesi H si ha:

• dei valori specifici (1:N)

• un valore qualunque (?)

• un valore nullo (φ)

Un ipotesi generale viene descritta nel seguente modo: H=<?,?,...,?>,

un’ipotesi specifica invece dei valori qualunque ha dei valori specifici, un

esempio: H=<pioggia, 6, vento,...,>

Nel caso in cui ottenga un insieme generale dato da tutti ”?” e un insieme

specifico dato dagli insiemi vuoti φ probabilmente il test é errato, oppure le

ipotesi non sono corrette.

8.1 Update-S

Parto da un ipotesi specifica e verifico che l’ipotesi sia coerente, se non lo

é la si generalizza attraverso un processo di minime generalizzazioni fino a

raggiungere l’insieme ”generale” piú specifico.

Esempio

• s=”sunny, warm, normal, strong, warm, same”

• d=”sunny,warm,high,strong,warm,same”, EnjoySport=yes

• h=”sunny, warm, ?, strong, warm, same”

8.2 Update-G

Parto da un’ipotesi generale (la piú generale con tutti ”?”) e provo tutte le

minime specializzazioni (cambiando un solo attributo per volta), il risultato

é che ne si ottengono piú di una, fino ad avere un insieme G di ”specializ-

zazioni” piú generali.

Esso si applica solo con ipotesi negative. Esempio

g=”?,?,?,?,?,?”

• d=”rainy,cold,high,strong,warm,change”, EnjoySport=no

• h1=”sunny,?,?,?,?,?”

• h2=”cloudy,?,?,?,?,?” 12

• h3=”?,warm,?,?,?,?”

• h4=”?,?,normal,?,?,?”

• h5=”?,?,?,weak,?,?”

• h6=”?,?,?,?,cool,?”

• h7=”?,?,?,?,?,same”

9 Attributi mancanti

Spesso puó capitare che delle informazioni vengano perse, una soluzione pos-

sibile puó essere di eliminare quel record, tuttavia esistono delle soluzioni

migliori. Se pensiamo di avere l’attributo ”Acqua” che puøessere dolce i

salata, abbiamo generato un attributo discreto che puó assumere 2 valori.

Immaginiamo che in una mole di dati, alcune informazioni sull’acqua man-

cano, possiamo pensare di aggiungere lo stesso quel record e di inserirlo in

tutti i sottoinsieme con una probabilitá frazionata.

Dividiamo dunque quel record in due record di peso inferiore

50% Acqua dolce + 50% Acqua salata

Tuttavia potremo migliorare questa probabilitá calcolando attraverso il Tran-

ing Set la probabilitá che sia Acqua dolce o Acqua salata.

Esempio

75% Acqua dolce + 25% Acqua salata

In questo modo creiamo due foglie dell’albero di decisione aventi gli attributi

”Dolce” e ”Salata” ma con probabilitá maggiore in Acqua dolce, cosı́ da

riuscire a sfruttare anche i valori mancanti del Traning Set.

13

10 c4.5

É una tecnica di ricerca negli alberi di decisione che non utilizza il back

tracking. L’inductive BIAS é un algoritmo che preferisce i rami degli

alberi piú corti per semplificarne la descrizione.

Questo potrebbe generare del overfitting, l’errore sui dati di test é piú

grande dell’errore dei dati sul traning set; le prestazioni (cioé la capacitá

di adattarsi/prevedere) sui dati di allenamento aumenteranno, mentre le

prestazioni sui dati non visionati saranno peggiori.

Figure 1: L’interpolazione non é necessaria per interpolare il grafo,

un’approssimazione lineare é piú efficente

11 Dimensione dell’albero di decisione

• Traning Data, aumentando il numero di foglie dell’albero arrivo asin-

toticamente ad arrivare a ciascuna foglia ad un ciascun esempio, quindi

ogni foglia ha un’accuratezza del 100 percento, infatti con piú dati ho

con piú il mio algoritmo é accurato.

• Test Data, aumentando eccessivamente il numero di foglie, il risultato

non é ottimale, perché ogni foglia rappresenta un esempio rischiando

di avere troppi esempi poco accurati, perché aumentando il numero

di foglie é possibile che i casi possibili aumentino e alcuni casi non

vengano visti, per questo motivo é meglio un albero di Data Test

potato 14

12 Ridurre la dimensione dell’albero

Attraverso un algoritmo ricorsivo di potatura dell’albero é possibile ridurlo

senza diminuirne l’accuratezza. L’algoritmo sostituisce un sottoalbero con

una foglia, sceglie se questa scelta migliora l’accuratezza e si ripete cosı́ il

procedimento. L’algoritmo lavora sul validation set.

12.1 Pessimistic pruning

Un altro algoritmo che non utilizza il validation set sostituisce un sot-

toalbero con una foglia o un sottoalbero con un sottosottoalbero. La sosti-

tuzione avviene attraverso il calcolo di una stima statistica data dalla dis-

tribuzione binomiale, una curva a campana che tiene in considerazione

in tutti i casi la probabilitá che l’evento si manifesti ”mai”, ”1 volta”,...,

”sempre” (i valori sono discreti). 15

Stima pessimistica

U (E, N ) con E=casi di errore e N=totale casi

75

Il risultato é una stima pessimistica dei casi possibili, l’errore si avvicinerá

a 0 per N molto grande. L’algoritmo sostituisce un sottoalbero con una

foglia avente come valore la somma delle stime pessimistiche delle foglie del

sottoalbero.

Una stima é piú accurata con tanti valori aventi qualche errore piut-

tosto di pochi valori senza errori é utile nei valori di data test, perché

un data test piú semplice é piú accurato, vengono inglobati anche dei casi

non visti. Esempio

U (0, 1) = 0, 75

75 16

13 ARFF

Un formato di file con due sezioni

• Header, le intestazioni iniziano con ”@”

– @relation

– @attribute

• Data

Esempio

% labor.arff

@relation ’labor-neg-data’

@attribute ’duration’ real

@attribute ’wage-increase-first-year’ real

@attribute ’wage-increase-second-year’ real

@attribute ’wage-increase-third-year’ real

@attribute ’cost-of-living-adjustment’ {’none’,’tcf’,’tc’}

@attribute ’working-hours’ real

@attribute ’pension’ {’none’,’ret_allw’,’empl_contr’}

@attribute ’standby-pay’ real

@attribute ’shift-differential’ real

@attribute ’education-allowance’ {’yes’,’no’}

@attribute ’statutory-holidays’ real

@attribute ’vacation’ {’below_average’,’average’,’generous’}

@attribute ’longterm-disability-assistance’ {’yes’,’no’}

@attribute ’contribution-to-dental-plan’ {’none’,’half’,’full’}

@attribute ’bereavement-assistance’ {’yes’,’no’}

@attribute ’contribution-to-health-plan’ {’none’,’half’,’full’}

@attribute ’class’ {’bad’,’good’}

I commenti iniziano con il ”percento”.

I formati possono essere

• String

• Integer

• Date

14 Inferenza

Conoscendo la probabilitá congiunta, é possibile rispondere a tutte le query

possibili. 17

15 Nomenclatura

I<X,,Y>, X e Y sono variabili indipendenti tra loro:

P (X|Y ) = P (X) se P (Y ) = 0 18

Part II

Reti Bayesiane

Una rete Bayesiana BN(G,θ) con

• G∈DAG

• ∈variabili |π

θ dipendenti, condizionate. θ , π = P (x )