Data Mining and Analytics - Risposte domande di teoria

Data mining and analytics - Domande teoria

Apprendimento induttivo da esempi

Nell'apprendimento induttivo il sistema parte da osservazioni fornite da un addestratore o da un ambiente. Le rappresentazioni sono generalizzate: l'obiettivo è di ottenere una conoscenza che sia valida anche in casi non ancora osservati, tramite induzione.

Nell'apprendimento da esempi, le osservazioni sono raggruppate in un set di esempi positivi (ossia istanze di un concetto che devono essere imparate) e in un set di esempi negativi (ossia che non sono istanze del concetto).

Dati

• Universo U: Insieme di tutte le istanze di un dominio.
• Concetto C: Sottoinsieme di U (anche detto classe).
• Linguaggio di descrizione degli oggetti (istanze) Lo.
• Linguaggio di descrizione dei concetti Lc.

L'apprendimento induttivo da esempi è una procedura che verifica se una descrizione Dc di un concetto C è soddisfatta da una descrizione Dx di un oggetto x: se è verificata, allora x appartiene a C. Informalmente, imparare un concetto C significa trovare una descrizione Dc del concetto C tale che, per tutti gli oggetti x dell'universo U, x appartiene al concetto se Dx soddisfa Dc. L'apprendimento induttivo da esempi può anche essere visto come un problema di predizione di una delle colonne della tabella del training set usando i valori delle altre colonne.

Apprendimento induttivo descrittivo

Nell'apprendimento induttivo descrittivo l'obiettivo è trovare la regolarità nei dati: a differenza dell'apprendimento da esempi non si hanno due classi di esempi, ma si analizzano i dati per descriverli.

Completezza e consistenza di una ipotesi induttiva

Un'ipotesi H è completa se copre tutti gli esempi positivi, ossia covers(H,E+) = E+. Un'ipotesi H è consistente se non copre alcun esempio negativo, ossia covers(H,E-) = ∅. Un'ipotesi può essere completa e consistente, incompleta e consistente, completa e inconsistente, incompleta e inconsistente.

Linguaggi di rappresentazione per il machine learning

I linguaggi di rappresentazione possono essere di due tipi:

• Linguaggi attributo-valore (proposizionali): Ogni istanza è descritta da valori presi da un set di attributi, fissati per tutte le istanze. Il training set può essere rappresentato come una tabella, in cui ogni attributo è una colonna.

• Booleani o binari (2 valori)
• Discreti o nominali (più di 2 valori)
• Ordinati (valori discreti ordinati)
• Continui o numerici (intervalli o rapporti di intervalli, interi o reali)

Se ci sono k attributi, ogni istanza può essere descritta da un punto in uno spazio di k-dimensioni. Problemi dei linguaggi proposizionali: si hanno problemi con le parti, sottoparti, attributi di parti e relazioni tra le parti. Ad esempio, una famiglia può avere un numero variabile di componenti e ogni componente può avere un numero variabile di attributi.

Per la rappresentazione dei concetti attributo-valore possono essere usati:

• Alberi decisionali: Ogni nodo corrisponde a un test su un attributo, ogni figlio corrisponde al risultato del test e ogni foglia è associata ad una classe.
• Reti bayesiane: Rappresentano la dipendenza probabilistica tra gli attributi. I genitori di un nodo sono gli attributi che direttamente influenzano il nodo e viene usata una tabella per determinare la forza di una dipendenza.

Linguaggi del 1o ordine: Si utilizzano teorie logiche per descrivere le istanze: permettono di rappresentare più facilmente parti di oggetti, attributi di parti o relazioni tra le parti.

Vantaggi:

• Rappresentazione uniforme delle istanze e delle ipotesi.
• La semantica di questi linguaggi è ben definita e ampiamente studiata.
• Disponibilità di interpreti ben progettati.

Matrice di confusione, accuratezza, error rate, precision e recall

Una matrice di confusione è una tabella che viene utilizzata per descrivere le prestazioni di un modello di classificazione su un set di dati di test per i quali sono noti i valori reali. Ogni riga della matrice rappresenta le istanze in una classe prevista, mentre ogni colonna rappresenta le istanze in una classe effettiva.

Si possono verificare 4 casi:

• TP (True Positive): La classe prevista è positiva ed è uguale alla classe effettiva. Il modello ha risposto correttamente con la classe positiva.
• FN (False Negative): La classe prevista è negativa ed è diversa dalla classe effettiva, ossia quella positiva. Il modello ha sbagliato rispondendo con la classe negativa.
• FP (False Positive): La classe prevista è positiva ed è diversa dalla classe effettiva, ossia quella negativa. Il modello ha sbagliato rispondendo con la classe positiva.
• TN (True Negative): La classe prevista è negativa ed è uguale a quella effettiva. Il modello ha risposto correttamente con la classe negativa.

• Accuratezza: (TP+TN)/(TP+TN+FP+FN) -> è la frazione di esempi classificata bene.
• Error rate: (FP+FN)/(TP+TN+FP+FN) = 1-Accuratezza -> è la frazione di esempi classificati male.
• Precision: TP/(TP+FP) -> è la percentuale delle previsioni corrette sul totale delle previsioni positive del modello.
• Recall: TP/(TP+FN) -> è la percentuale delle previsioni positive corrette sul totale delle istanze positive.

Teoria della probabilità e il teorema di Bayes

Regola della somma: Qualsiasi evento A può essere scritto come l’or di due eventi disgiunti.

P(A) = P(A,B) + P(A,¬B)

In generale, se Bi con i=1,...,n è un insieme esaustivo e mutualmente esclusivo di proposizioni: P(A) = Ʃi P(A,Bi)

Regola del prodotto: P(A,B) = P(A|B)*P(B)

Teorema di Bayes: P(A|B) = (P(B|A) * P(A)) / P(B)

Regola della catena: P(En,...,E1) = ∏i=1..n P(Ei|Ei-1,...,E1)

Ipotesi più generale o uguale ad un'altra

Date due ipotesi Hg e Hs, Hg è più generale o uguale a Hs (Hg >=g Hs) se e solo se ogni istanza di Hs soddisfa anche Hg (ossia l’insieme delle istanze coperte da Hg è un soprainsieme di quelle coperte da Hs). Hg è strettamente più generale di Hs (Hg >g Hs) se e solo se Hg >=g Hs e ¬(Hs >=g Hg).

Spazio delle versioni e dei confini generale e specifico

Lo spazio delle versioni VSh,d, rispetto allo spazio delle ipotesi H e al training set D, è il sottoinsieme delle ipotesi in H coerenti con gli esempi in D. (Coerente significa che copre tutti i positivi e non copre alcun negativo).

Lo spazio delle versioni può essere rappresentato dai suoi membri più generali e più specifici, grazie al teorema di rappresentazione dello spazio delle versioni. Il confine generale G, rispetto allo spazio delle ipotesi H e ai dati di training D, è l’insieme dei membri di H massimamente più generali che sono coerenti con D. Il confine specifico S, rispetto allo spazio delle ipotesi H e ai dati di training D, è l’insieme dei membri di H minimamente generali (ovvero massimamente specifici) che sono coerenti con D.

Bias induttivo

Il bias induttivo è un’assunzione a priori che l’algoritmo di apprendimento fa riguardo l’identità del concetto target.

Definizione formale

Si consideri:

• Un algoritmo di apprendimento di concetti L
• Un insieme di istanze X
• Un concetto target c
• Un insieme di esempi Dc={<x,c(x)>}

Sia L(xj,Dc) la classificazione assegnata all’istanza xj da L dopo il training sui dati Dc. Il bias induttivo di L è ogni minimo insieme di asserzioni che aggiunte ai dati di training e al nuovo esempio fa sì che la classe restituita dall’algoritmo sia uguale alla classe che si deriva per deduzione dalle asserzioni più i dati. Il bias induttivo è un modo non procedurale per caratterizzare la politica dell’algoritmo di apprendimento per generalizzare oltre i dati osservati.

Esempio: nell’algoritmo Candidate-Elimination, il bias induttivo è che il concetto target appartiene allo spazio delle ipotesi. Nell’algoritmo Find-S è invece che il concetto target appartiene allo spazio delle ipotesi positive e che tutte le istanze sono negative a meno che non si provi l’opposto.

Algoritmo per l'apprendimento degli alberi di decisione

L’algoritmo usato per l’apprendimento degli alberi di decisione è c4.5. c4.5 esegue il metodo build_tree(T), che prende in ingresso un training set e restituisce un albero:

• Se T contiene gli esempi di una stessa classe, ritorna una foglia con etichettata la classe.
• Se T contiene esempi appartenenti a più classi:
• T è partizionato in sotto-insiemi T1, T2,..., Tn in base ad un test su un attributo.
• L’algoritmo viene chiamato ricorsivamente sui sotto-insiemi.
• Ritorna un sotto-albero con la radice associata al test e ai figli.

I test sugli attributi possono essere:

• Uguaglianza con un valore costante (2 possibili uscite, yes or no)
• Uguaglianza con un certo valore (n possibili uscite)
• Appartenenza ad un insieme (2 possibili uscite, yes or no)
• Appartenenza ad un insieme di partizioni, con gli insiemi che sono mutualmente esclusivi ed esaustivi (1 uscita per insieme)

Per costruire l’albero è impraticabile fare una ricerca nello spazio di tutti i possibili alberi tramite backtracking, per cui si esegue una ricerca greedy in cui non è più possibile cambiare la scelta dei test sui nodi. La greedy si basa sulla scelta di un’euristica per la scelta dell’attributo su cui costruire l’albero, come l’entropia o l’indice di Gini. c4.5 termina l’apprendimento quando:

• Trova un insieme uniforme
• Trova un insieme vuoto: restituisce una foglia con etichetta la classe più frequente nel padre.
• Nessun test è tale che almeno due sottoinsiemi contengano un numero minimo di casi.

Euristiche per l'apprendimento degli alberi di decisione

Le euristiche più utilizzate sono:

• Entropia: L’entropia è la misura di un’incertezza associata a una variabile random discreta. Data una variabile random C con k possibili valori c1,...,ck, l’entropia H(C) è data da: H(C) = -Ʃj=1..k P(cj)log2(P(cj))
• H(T) misura il numero minimo di bit necessari per codificare senza perdita un messaggio della forma “l’esempio corrente, selezionato in modo casuale dal training set, appartiene alla classe cj”.

L’entropia misura la non-uniformità o impurità di un set di dati:

• È minima quando il set è il più puro possibile, ossia contiene esempi di solo una classe.
• È massima quando il set è il meno puro possibile, ossia contiene un numero equo di esempi delle due classi.

Nel caso di due classi, il valore massimo dell’entropia è 1 ed è ottenuto con p+=p-=0.5, mentre il valore minimo è 0 ed è ottenuto con p+=1,p-=0 (o viceversa). In generale, il valore massimo dell’entropia con gli esempi appartenenti a k classi è ottenuto con P(cj)=1/k e Hmax(T)=log2(k).

• Indice di Gini: L’indice di Gini è un’altra misura di impurità. È dato da: gini(T) = 1 - Ʃj=1..k P(cj)²
• Il valore massimo è ottenuto con p+=0.5, p-=0.5 ed è gini(T)=0.5.
• Il valore minimo è ottenuto con p+=0 o p-=0 ed è gini(T)=0.

In generale, l’indice di Gini ha il massimo per p1=p2=...=pk=1/k. Il valore massimo è gini(T)=1-1/k. Si ha che all’aumentare di K l’indice di Gini aumenta, come nell’entropia, ma l’indice di Gini ha sempre valore <1, mentre nell’entropia si possono avere valori >1.

Scelta dei test sugli attributi continui nell'apprendimento degli alberi di decisione

I test sugli attributi continui necessitano di determinare una soglia di valutazione dei valori degli attributi. Dati <V1,V2,...,Vm> valori ordinati, il test X<=Vi divide gli m elementi in 2 gruppi:

• X<=Vi: {V1,V2,...,Vi}
• X>Vi: {Vi+1,...,Vm}

Si hanno quindi m-1 candidati per le soglia: ogni candidato deve essere valutato. Per la valutazione del test:

1. Vengono ordinati gli esempi in base all’attributo X.
2. Si contano gli esempi:
• eji è il numero di esempi che hanno valore Vi per X e appartengono alla classe cj
• ej è il numero di esempi che appartengono alla classe cj
3. Ogni test ha due possibili risultati: yes or no

Si ha quindi che:

1. dj,yes sono gli esempi della classe j nel ramo X<=Vi
2. dj,no sono gli esempi della classe j nel ramo X>Vi
3. Si aggiornano i valori aggiungendo gli esempi che hanno valore Vi dell’attributo X e si toglie tale numero di esempi da dj,no

Tali conteggi sono sufficienti per calcolare l’euristica per ogni valore di X con Vi che va da 1 a m-1. In sintesi:

1. Si ordinano gli esempi
2. Si scansionano le soglie
3. Si aggiornano i conteggi
4. Tali conteggi sono sufficienti per calcolare l’euristica per ogni valore di X con Vi che va da 1 a m-1.

Gestione dei valori sconosciuti nell'apprendimento degli alberi di decisione

Si effettua la valutazione del test: Si considera un attributo discreto X con n valori {x1,...,xn}. F è il set di esempi del training set T che hanno X conosciuto. F fornisce una distribuzione congiunta del valore xi con la classe cj, ossia P(xi,cj). Si assume che i valori sconosciuti abbiano la stessa distribuzione P(xi,cj) rispetto all’attributo e alla classe. Gli esempi con valori sconosciuti non alterano i valori dell’entropia o dell’indice di Gini.

Nel calcolo dell’entropia il valore sconosciuto è considerato come un valore in più, calcolando di fatto l’entropia di un partizionamento. Tn+1 è il set di esempi di T con valore sconosciuto di X. L’entropia è data da: H(X) = -Ʃi=1..n+1 * log2(∣Ti∣/∣T∣)∣Ti∣/∣T∣

c4.5 penalizza ulteriormente gli attributi con valori sconosciuti moltiplicando il gain per la probabilità che l’attributo sia conosciuto: gain(X) = * (H(F) - Hx(F))∣F∣/∣T∣

Classificazione delle istanze con attributi sconosciuti con gli alberi di decisione

Dato un nodo di test in un albero di decisione, a ciascun esempio del training set T viene assegnato un peso per decidere in quale sottoinsieme ottenuto dal test bisogna inserire l’esempio. Se l’attributo sottoposto al test è noto allora l’esempio va inserito nel ramo opportuno con w=1 e negli altri rami con w=0. Se invece l’attributo non è noto, l’esempio viene ripartito nei rami con peso pari alla probabilità che quell’attributo assuma quel valore, ossia w = P(xi), dove P(xi) può essere stimato in base alla frequenza relativa dell’attributo in F.

Bias induttivo di c4.5

Il bias induttivo di c4.5 è che:

• Gli alberi più corti sono preferiti a quelli più lunghi.
• Gli alberi che mettono più vicino alla radice gli attributi con i valori di information gain più alti sono preferiti.

Anche se lo spazio delle ipotesi di c4.5 è il powerset di X, grazie a questo bias induttivo c4.5 è comunque in grado di generalizzare. Il bias induttivo di c4.5 è detto preference bias, mentre quello di Candidate-Elimination è detto restriction bias. In generale, il preference bias è migliore perché permette di lavorare con uno spazio delle ipotesi completo: non corre il rischio che il concetto target non sia presente nello spazio delle ipotesi. Differenza rispetto al Candidate-Elimination: il Candidate-Elimination ricerca in un modo completo uno spazio delle ipotesi incompleto, mentre c4.5 ricerca in un modo incompleto uno spazio delle ipotesi completo.

Rasoio di Occam

Il rasoio di Occam dice che è meglio preferire le ipotesi più semplici che descrivono i dati. Nella scienza, le teorie più semplici sono preferibili a quelle più complesse perché possono essere testate più facilmente.

Overfitting

Un’ipotesi causa l’overfitting dei dati quando esiste un’ipotesi più semplice e meno accurata sul training set ma più accurata sull’universo. L’overfitting può verificarsi quando il training set contiene errori o quando è piccolo: un albero fa overfitting quando si adatta troppo ai dati di training e perde di vista l’universo, comportandosi bene solo sui dati di training.

Riduzione dell'overfitting

Ci sono 2 tecniche per evitare l’overfitting:

• Prepruning: Fermare la crescita dell’albero prima che l’albero classifichi perfettamente gli esempi di training.
• Postpruning: Lasciare crescere l’albero e lo si pota dopo. Per determinare la dimensione ottimale dell’albero:
• Approccio training and validation set: Usare un set di esempi separato per la valutazione dell’albero.
• Usare tutti gli esempi disponibili per il training, ma usando un test statistico per decidere se tenere un nodo oppure no.
• Minimum description length principle: Usare una misura esplicita di complessità di codifica dell’albero e degli esempi che sono eccezioni e scegliere un albero che localmente minimizza questa misura.

Il Reduced error pruning è un approccio postpruning e “training and test validation”. Divide i dati in un training e in un validation set.