Data Mining e Text Mining - Riassunti

Data mining

Dati

Diversi tipi di dato:

• Categorici (Qualitativi): Nominali (sesso, colore degli occhi...), Ordinali (Possono essere ordinati: voto...)
• Numerici (Quantitativi): Di intervallo (la differenza tra dati ha significato: date...), Di rapporto (il rapporto tra dati ha significato: quantità di denaro, età...)

Oppure:

• Binaridi
• Discreticontinui

Oppure:

• Asimmetrici: hanno rilevanza solo le istanze che assumono valori diversi da zero
• Simmetrici

Transazione

Ogni record coinvolge più item, per esempio acquisto in un supermercato. Transazione = acquisto Item = prodotti.

Qualità dei dati

• Rumore
• Outlier
• Dati mancanti
• Dati duplicati

Gestione dei dati mancanti:

• Usare la media
• Predire i valori (con altri algoritmi di data mining)
• Usare unknown o 0

Preprocessing dei dati

Aggregazione: Combinare uno o più attributi in uno solo.

Campionamento:

• Casuale semplice: ogni elemento ha la stessa probabilità
• Stratificato: si suddividono i dati in più partizioni poi si usa campionamento casuale semplice su ognuna

Riduzione della dimensionalità

• Principle Component Analysis
• Singular Value Decomposition

Selezione degli attributi

Selezione degli attributi con tecniche supervisionate (alcuni algoritmi lo fanno da soli e.g decision tree)

Creazione di attributi

Discretizzazione

Bisogna trovare gli intervalli e definire gli split point.

Può essere non supervisionata:

• Equi-larghezza
• Equi-frequenza
• K-mediani: k raggruppamenti in modo da minimizzare la distanza tra i punti appartenenti allo stesso raggruppamento

Supervisionata:

• Entropia: massimizzare la purezza degli intervalli

Binarizzazione

Rappresentazione di un attributo discreto mediante un insieme di attributi binari.

Trasformazione di attributi

Normalizzazione (min-maz o Z-score).

Similarità e dissimilarità

Similarità: misura numerica che esprime il grado di somiglianza tra due oggetti. Solitamente compresa tra [0,1].

Dissimilarità: misura numerica che esprime il grado di differenza. Compresa tra [0,1] o [0,∞].

Dissimilarità particolarmente utilizzate sono le distanze.

Similarità di vettori binari

Dati due vettori p e q, si definiscono le seguenti grandezze:

• Numero di attr. in cui p=0 e q=0, M₀₀
• p=0, q=1, M₀₁
• p=1, q=0, M₁₀
• p=1, q=1, M₁₁

Simple Matching Coefficient (SMC) = (M₀₀ + M₁₁)/(M₀₀ + M₀₁ + M₁₀ + M₁₁)

Non utilizzabile in presenza di attributi asimmetrici.

Indice di Jaccard: M₁₁/(M₀₁ + M₁₀ + M₁₁)

Decision tree

Algoritmi esistenti

• Hunt's Algorithm
• C4.5, ID3
• CART...

Varie problematiche

• Definire la split policy
• Definire la stop policy
• Underfitting/Overfitting...

Hunt's Algorithm

Algoritmo Ricorsivo che suddivide un set di record in sottogruppi "puri".

1. Se contiene solo elementi di una classe, allora è un nodo foglia con classe.
2. Se è vuoto, allora è una foglia con la stessa label del padre.
3. Se contiene elementi di varie classi, si trova il miglior attributo separatore e la migliore split policy, poi si continua ricorsivamente.

Trovare la split condition

Dipende dal tipo di attributo (nominale, categorico, continuo) e dai possibili split (binary, n-ari).

Split di attributi nominali

• Split n-ario: Tanti split quanti i valori assumibili dall'attributo.
• Split binario: Si creano solo 2 split che suddividono i valori assumibili in 2 gruppi.

Split di attributi ordinali

Va preservato l'ordine. N-aria e binaria come nei nominali.

Split di attributi continui

• Split n-ario: Lo split è un test booleano su range di valori (x < 10, 10 < x < 20, 20 < x < 30,...).
• Split binario: Si creano solo 2 split (x > 10 ? yes, no).

Per semplificare la ricerca gli attributi continui vengono discretizzati:

• Discretizzazione statica: si applica prima di eseguire l'algoritmo.
• Discretizzazione dinamica: viene fatta ad ogni ricorsione.

Trovare il best split

Deve permettere di trovare insiemi di dati più puri. Dato un nodo p con record presi da K classi e un partizionamento in n figli si definiscono questi indici di impurità:

• Gini index: GI(i) = 1 − ∑ p(j|i)²
• Entropia: Entropy(i) = − ∑ p(j|i) log₂ p(j|i)
• Misclassification Error: Error(i) = 1 − max p(j|i)

Il valore di impurità si definisce come: ∑ (meas(i) * m_i/m), dove meas è uno dei 3 indici, m è il numero di record nel padre, p è il numero di record nel i-esimo figlio, m_i è il numero di record nel figlio.

Per gli attributi continui bisogna calcolare l'index per ogni possibile split point -> inefficiente.

Quando si effettua lo split lo scopo è massimizzare il Gain, dove Gain = Entropy(p) − ∑ (Entropy(i) * m_i/m).

Farlo in questo modo porta a creare molti figli con pochi record. Spesso si tende a massimizzare il Gain Ratio, dove:

Gain Ratio = Gain / SplitINFO, dove SplitINFO = − ∑ (m_i/m) log (m_i/m).

Più nodi figli si creano e più SplitINFO è grande quindi il Gain Ratio diminuisce.

Criterio di stop

• Quando un nodo ha elementi di una stessa classe
• Quando tutti i record hanno attributi simili (lo split dipenderebbe da piccole fluttuazioni)
• Quando nel nodo ci sono pochi record (lo split non sarebbe statisticamente rilevante)

Valutazione del decision tree

Confusion Matrix

• Accuratezza = (TP + TN) / (TP + FP + TN + FN)
• Error Rate = (FP + FN) / (TP + FP + TN + FN)
• Precision (p) = TP / (TP + FP)
• Recall (r) = TP / (TP + FN)
• F-measure = 2rp / (r + p) (media armonica di precision e recall)

Valutazione cost-sensitive

Le misure descritte trattano tutti gli errori allo stesso modo. Spesso questo si vuole evitare ed è preferibile utilizzare una matrice di costi da minimizzare.

Curve ROC

Mettono in relazione False Positive Rate (FP / (FP + TN)) e True Positive Rate (TP / (TP + FN)) cambiando il threshold di appartenenza ad una classe nei classificatori probabilistici (che associano una probabilità ad ogni classe).

Data una curva ROC la sua Area Under the Curve (AUC) rappresenta un buon valore di bontà del classificatore.

Evitare overfitting

• Pre-pruning: definire una early stopping rule (stop split se non migliori information gain...)
• Post-pruning: una volta generato l'albero si collassano dei nodi se si riduce l'errore di generalizzazione sul validation set

Bisogna stimare l'errore di generalizzazione:

• Re-substitution error: numero di errori nel training
• Generalization error: numero di errori nei dati reali

Metodi di stima:

• Approccio ottimistico: e'(t) = e(t)
• Approccio pessimistico: l'errore di classificazione è dato da quello sul training aggiungendo un costo basato sulla complessità del modello

Minimum description length (MDL)

1. Per descrivere un modello devo dire quali classi riconosce e descriverne la struttura e gli errori che commette.
2. MDL dice che dati 2 modelli bisogna scegliere quello più facile da descrivere.

Cost(model,data)=Cost(model)+Cost(data|model)

Test set: l'errore di generalizzazione è uguale a quello sul test set. Per generare il test set si può usare:

• Un partizionamento 1/3 - 2/3
• K fold cross validation
• Bootstrap

Classificatori rule based

Classificano i record usando un insieme di regole if...then.... Ogni regola è del tipo (Condizione) → classe. Sono equivalenti ai decision tree. Facili da interpretare/generare. Costo elevato di costruzione al crescere del training set. Risentono del rumore sui dati.

Definizioni

Una regola r: copre un'istanza x se x soddisfa A. Coverage(r) = |A|/|D| (|D|: grandezza del dataset, |A|: numero di record che soddisfano le condizioni r). Accuracy(r) = |A ∩ y|/|A| (frazione di record che soddisfano sia A che y).

Tipi di regole

• Mutuamente esclusive: Indica un set di regole che non possono essere soddisfatte contemporaneamente da uno stesso record. Non sempre è soddisfacibile: definire ordine di attivazione (rule-based: basato sulla qualità delle regole o class-based: basato sull'importanza delle classi) criteri di voto.
• Esaustive: Esiste una regola per ogni set di attributi. Non sempre soddisfacibile: Utilizzare una classe default.

Costruzione delle regole

Metodi diretti

Estraggono le regole direttamente dai dati.

Sequential covering: Ordinamento delle regole basato sulle classi.

Creazione di regole basato su Learn One Rule:

• Trovare una regola che copra quanti più possibili esempi positivi e quanto meno possibili (o nessun) esempio negativo.
• Si sceglie progressivamente un nuovo predicato (una coppia [Attributo, Valore]).
• Poi bisogna avere un criterio per aggiungere predicati alla regola: n = istanze coperte dalla regola, nr = istanze correttamente classificate dalla regola, k = numero di classi.

Accuracy = n/(n + 1) (pesa l'accuracy in base alla coverage).

Oppure:

Laplace(r) = (n_p + 1)/(n + k)

F oilGain(r, r') = t * (log (p_p/(p_p + n_p)) − log (p_n/(p_n + n_n)))

(t: esempi positivi coperti sia da r che da r'; p: esempi positivi coperti da r; n: esempi negativi coperti da r) Questo indice tende a favorire regole che hanno alta coverage ed accuracy.

Non si aggiungono più regole se il gain non supera una certa soglia.

Anche qui possono essere usate tecniche di pruning.

Eliminazione di istanze dal training set. Serve a evitare di generare sempre la stessa regola e sovrastimare l’accuracy della prossima regola. Evitare di sottostimare l’accuracy della prossima regola.

Criterio di stop

RIPPER:

• Basato su sequential covering
• Per problemi a 2 classi impara le regole per una classe e l'altra diventa il DEFAULT;
• Per problemi multi-classe ordina le classi in base ad un criterio poi ne sceglie una come positiva e tutte le altre come negative e genera le regole. Ripete l'operazione per ogni classe.
• Criterio di stop basato sul description length: Interrompi la costruzione quando il nuovo valore di description length è superiore di d bits rispetto a quello precedente

Learn-One-Rule:

• Parte da una regola vuota
• Aggiunge predicati finché aumenta il foil gain
• Pruning incrementale: incremental reduced error pruning (fa pruning dopo ogni step di aggiunta di regole)
• Pruning finale: elimina i predicati in modo da massimizzare sul validation set

Metodi indiretti

Estraggono le regole dal risultato di altri metodi di classificazione come per esempio i decision tree.

Ad ogni percorso radice-foglia corrisponderà una regola. Si applicano poi tecniche di pruninig.

Decision tree vs Regole

Sono generalmente equivalenti in espressività. Differenza fondametale tra i 2:

• La bontà del criterio di split scelto in ogni nodo dell’albero considera la qualità di tutti i figli generati
• Il criterio con cui viene aggiunto un predicato alla regola valuta solo la bontà della classe che si viene a determinare

Classificatori k-NN

Classificano in base alla somiglianza rispetto ai record del training set. (lazy learners)

• Rote-Learner: Classifica un record se coincide con uno del training set
• Nearest Neghbour: Classifica in base alla somiglianza dei vicini
• K Nearest Neighbour

Richiede:

• Training Set
• Metrica di distanza tra record
• Valore dei k vicini da utilizzare
• Funzione di classificazione di un record z: ỹ = argmax ∑ I(y = y_i) (dove I() restituisce 1 se l'argomento è TRUE, 0 altrimenti)

Questa funzione è molto sensibile ai valori di k. Solitamente si aggiunge un peso in base alla distanza:

ỹ = argmax ∑ I(y = y_i)/d(z, x_i)

È importante scegliere il giusto k:

• k piccolo -> sensibile a rumore
• k grande -> include troppe classi

È anche necessario normalizzare i dati per avere delle distanze 'sensate' (può non essere sufficiente in presenza di diverse distribuzioni; in quel caso distanza di Mahalanobis)

Pro:

• Non serve un modello
• Costruiscono contorni non lineari

Contro:

• Richiedono misura di similarità
• Richiedono pre-processing
• Suscettibili al rumore
• Sensibili ad attributi irrilevanti
• Costo di classificazione elevato

Strutture ad Indice

Servono a ridurre il costo del calcolo delle distanze

Dati attributi A₁, A₂, ..., A_n

1. Costruzione di un B⁺-TREE ordinato in base ad A₁, A₂, ..., A_n. Le foglie saranno ordinate in modo che contengano i più piccoli valori di A₁, i seguenti ecc... Non si cattura il concetto di distanza spaziale.
2. Utilizzare un B⁺-TREE con query di range. Se sappiamo che i k-NN di un punto stanno all'interno di possiamo usare n query [l₁, h₁] × [l₂, h₂] indipendenti del tipo BETWEEN AND poi intersecare il risultato.
3. Utilizzare gli R-TREE: estensioni multidimensionali dei B⁺-TREE. Permettono di gestire i dati in intervalli multidimensionali sovrapposti.

Classificatori Bayesiani

Approccio probabilistico alla classificazione. Modellano relazioni probabilistiche tra gli attributi e la classe.

Teorema prob. condizionata: P (A, C) = P (A|C)P (C)

Teorema di Bayes: P (A|C)P (C)/P (A) = P (C|A)

Teorema prob. assoluta: P (A = a) = ∑ P (A = a, B = b_i) = ∑ P (A = a|B = b_i)P (B = b_i)

Dato il vettore di attributi A = (A₁, A₂, ..., A_n) e C la variabile di classe, i classificatori bayesiani assegnano un record A alla classe C che massimizza P (A|C) · P (C)

Naive Bayes

Assume indipendenza tra gli attributi. Una variabile aleatoria X si dice indipendente da Y dato Z se P (X|Y, Z) = P (X|Z)

Grazie a questa assunzione si ha che: P (X, Y, Z)/P (Z) = P (X|Z) · P (Y|Z)

Quindi P (A₁, A₂, ..., A_n|C) = P (A₁|C) · P (A₂|C) ... P (A_n|C)

Non è quindi più necessario calcolare la probabilità condizionata per ogni valore di A ma è sufficiente ricavare i vari N_ij dal training set tramite la formula P (A_i|C) = N_ij/N_j dove N_ij è il numero di istanze che hanno attributi a_i e classe c_j e N_j è il n. di tutte le istanze con classe c_j.

Un record viene così classificato con la classe se: C = c_j n_j = argmax P (C = c_j) ∏ P (A_k = a_k|C = c_j)

Accorgimenti

Particolari accorgimenti se A è continuo:

• Discretizzazione
• Associare all'attributo una funzione di densità (solitamente funzione normale) e stimarne i parametri dal training set.

Correttori:

P (A_i = a_i|C = c_j) = N_ij/_Nj

• Laplace: (N_ij + 1)/(N_j + c) dove c è il numero di label di classe
• m-estimate: (N_ij + mp)/(N_j + m) dove p è la probabilità e m è l'equivalent sample size che determina l'importanza della probabilità a priori rispetto a quella osservata.

Pro

• Robusti al rumore
• Gestiscono i dati mancanti non considerando l'evento
• Robusti rispetto ad attributi irrilevanti

Contro

• Attributi correlati riducono l'efficacia

Multiclassificatori

L'idea è costruire più classificatori per predire la classe di appartenenza di un record. È necessario che:

• I classificatori siano indipendenti
• L'error rate dei singoli classificatori sia inferiore a 0.5

Com generare più classificatori?

• Cambiando training set: costruire più training set da quello dato
• Bagging: si costruiscono vari classificatori ottenuti come bootstrap di un medesimo TS
• Boosting: Approccio iterativo. Adatta il TS per concentrarsi sugli errori