Che materia stai cercando?

Data mining

Appunti di Data Mining basati su appunti personali del publisher presi alle lezioni del prof. Riguzzi dell’università degli Studi di Ferrara - Unife, facoltà di Scienze matematiche fisiche e naturali, Corso di laurea in informatica. Scarica il file in formato PDF!

Esame di Data mining docente Prof. F. Riguzzi

Anteprima

ESTRATTO DOCUMENTO

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 )

x i i

Una rete B. é migliore con meno archi nella rete.

16 Come costruire la rete

• Si ordinano i vettori x , x , ..., x

1 2 n

• Si aggiunge un nodo x i

• Si setta il padre π

i

• |π

Si assegna un valore P (x i i

17 Indipendenza tra i nodi

Un nodo V é indipendente se é tail-to-tail :

Il nodo ha n archi uscenti

Un nodo V é dipendente se é tail-to-head o head-to-head

Il nodo ha almeno un arco entrante e almeno un arco uscente.

19


PAGINE

21

PESO

347.38 KB

PUBBLICATO

5 mesi fa


DETTAGLI
Esame: Data mining
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Ferrara - Unife
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher alan.bimbati di informazioni apprese con la frequenza delle lezioni di Data mining e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Ferrara - Unife o del prof Riguzzi Fabrizio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in informatica

Sistemi operativi
Appunto
Calcolo numerico
Appunto