Riassunto Data and Web Mining

Ruotare validation e training set mantenendo invariato il tuning degli iperparametri per valutare la performance del modello

Quando si fa un sampling da un dataset per dividere in training/validation, prendere dati in modo tale da mantenere una proporzione delle classi del dataset originale

k Nearest Neighbor classifier.

A livello di training non fa altro che indicizzare i dati in input (è chiamato lazy learner). Quando gli viene chiesto di predire un risultato, cerca i \(k\) valori più vicini al dato e conta la classe più frequente, dando quella come predizione. In particolare per \(k = \infty\) il kNN ritorna la moda tra le classi.

Ci sono vari modi di definire la distanza e dipende dal problema che si ha in mano. Esempi

Minkowski : \(d_p(x,y) = \sum_i \left|x_i - y_i\right|^\frac{1}{p}\)

Generalizzazione delle distanze in \(\mathbb{R}^n\) (euclidea per \(p=2\), manhattan per \(p=1\));

Coseno \(d(\vec{x}, \vec{y}) = \frac{\vec{x}\cdot\vec{y}}{||\vec{a}||\cdot||\vec{b}||}\)

differenza di inclinazione tra due vettori, utile ad esempio in text processing;

Jaccardi \(d(A,B) = 1- \frac{|A \cap B|}{|A \cup B|}\)

Confronto di un attributo tra tutti i dati, simile al Coseno;

Hamming

distanza in termini di quanti caratteri sono diversi tra due stringhe binarie.

I kNN sono estremamente sensibili agli outliers.

Potrebbe essere utile scalare i dataset in modo tale da avere le stesse "unità di misura" per tutte le features. In particolare:

Standard Scaler

I dati sono normalizzati in modo tale che \(x_i \sim N(\mu_i, \sigma_i^2)\) dove i parametri sono media e varianza delle features;

Min-max sclaer

I dati sono normalizzati in un intervallo \([0, 1]\).

Utilizzati sia per classificazione che regressione. Si costruisce un albero che, a partire dal nodo inziale, compie delle scelte ad ogni passo fino ad arrivare ad una classificazione. Ogni nodo dell'albero corrisponde ad una scelta (binaria e non), mentre ogni foglia corrisponde a una decisione.

Costruire l'albero ottimale è un problema computazionale di classe \(NP-hard\), dunque è necesario utilizare un algoritmo greedy per costruire l'albero. La costruzione dipende dalla scelta di come calcolare il gain e l'errore.

\[Gain(Split|D) = Error(D) - \left(\frac{|D_L|}{Error(D_L)} + \frac{|D_R|}{Error(D_R)}\right)\] Varie tipologie di errore:

Errore di classificazione

\(Error(D) = 1 - \max_i p_i\);

Errore di informazione

\(Error(D) = Info(D) = \sum_ip_i\log(p_1)\);

Gain ratio

\(Error(D) = \frac{Info(D)}{SplitInfo(D)}\); \(SplitInfo(D) = -\sum_i\frac{|D_i|}{|D|}\log\frac{|D_i|}{|D|}\);

Indice di Gini

\(Error(D) = 1 - \sum_i p_i\);

Regressione

\(Error(D) = MSE(D)\).

Regressione utilizzando la sigmoide come link function. Non c'è molto altro da dire

Lo scopo è "disegnare" un iperpiano nello spazio dei punti, ottenendo così una classificazione. Gli SVM offrono solo una classificazione di tipo binario; per classificare tra una categoria non binaria, è necessario utilizzare più SVM in serie. Questo è possibile per il teorema del panino al prosciutto (vorrei star scherzando)

In pratica è come risolvere il seguente problema di ottimizzazione: \[\text{Minimizzare }f(w) = \frac{|w|_2^2}{2} \text{ con vincolo } g(x):\;y_i(w^Tx_i + b) \geq 1\] Se i punti non sono separabili linearmente, è possibile introdurre un "soft margin", tramite un errore: \[\text{Minimizzare }f(w) = \frac{|w|_2^2}{2} + C\sum_ix_i \text{ con vincolo } g(x):\;y_i(w^Tx_i + b) \geq 1 - x_i\]

Metodo per ridurre la varianza del modello.

1. Dato un dataset grande \(N\), effettuare \(N\) sampling dallo stesso dataset per \(k\) volte, contemplando anche duplicati;
2. La probabilità che un dato sia presente più di una volta per \(N\) grande è \(\lim_{n\to\infty} 1 - (1 - \frac{1}{n})^n = 1 - e^{-1} \approx 63\%\);
3. Effettuare un training di \(k\) modelli in parallelo sui dataset diversi;
4. La predizione totale è la media delle predizioni per tutti i modelli.

Metodo per ridurre il bias del modello.

1. Effettuare un training del dataset;
2. Trovare i punti che sono classificati erroneamente;
3. Creare un nuovo dataset tramite sampling in cui i dati classificati erroneamente hanno più probabilità di essere pescati;
4. Ripetere step 1-3 finché non si ha un'accuratezza desiderata.

Essenzialmente è un bagging modificato per un Albero di Decisione completo, in modo tale da migliorare la varianza di un modello a bias già basso. La tecnica porta a un modello molto efficiente in quanto è possibile costruire alberi in parallelo. Il rischio è avere overfitting.

Una delle differenze dal bagging tradizionale è che per ogni diverso nodo che va a costruire durante il training, per ogni albero parallelo, l'algoritmo seleziona a caso un subset di feaure ogni volta.

• Scelte binarie diventano \(Bool\);
• Variabili categoriali possono diventare variabili numeriche crescenti;
• Variabili categoriali possono anche essere codificate in One Hot Encoding;
• Variabili numeriche sono mappate a \(\mathbb{R}\);
• Per valori non esistenti, rimpiazzare con media (numeriche) o mediana (categoriali)

Siano \(\lambda\) label reale, \(\hat{\lambda}\) label predetto, \(c\) una classe:

Matrice di confusione (Confusion matrix)

Tabella con \(\lambda\) nelle righe e \(\hat{\lambda}\) nelle colonne;

Precisione \(P\)

Rapporto tra numero di predizioni correttamente classificate come \(c\) e numero di quelle classificate come \(c\);

Recall \(R\)

Rapporto tra numero di predizioni correttamente classificate come \(c\) e numero di quelle che sono realmente in \(c\);

F-measure

\[ F = \frac{2PR}{P+R}\]

È possibile avere diversi tipi di statistiche sui dati:

Macrostatistica

Media su tutti i dati;

Statistica pesata

I pesi sono pesati in base al numero di istanze di una classe;

Apprendimento sensibile ai costi

Celle diverse della matrice di confusione hanno errori differenti (ovvero non sono sempre \(\pm 1\)).

ROC sta per curva "Receiver Operating Characteristic". L'idea è che è preferibile avere un Recall molto alto, che implica un alto numero di "true positives", opposto ad un numero basso di falsi positivi.

Quindi, in genere per una selezione binaria, si crea un grafico dove si disegna il True Positive Rate contro il False Positive Rate. \(AOC\), ovvero Area Under the Curve, altro non è che una misura di quanto meglio è. per \(AOC = 1\) si ha la situazione ideale (molto bene), mentre per \(AOC = 0.5\) si ha la situazione di selezione casuale (molto male).

In genere per processare un documento di testo si può trattare il testo come una sequenza di parole. Si conta la frequenza delle ricorrenze di ogni parola.

Grandezze interessanti:

Frequenza dei termini nel testo

\(tf(t) = \#\text{ delle occorrenze di t nel testo}\).

(no term)

Numero di documenti contenenti un termine:: \(df(t)\).

Frequenza inversa nei documenti

\(idf(t) = \ln{\frac{N}{df(t)}}\).

Si dice stemming il processo di rimozione di suffissi, lemming quello di rimpiazzare una parola composta con la parola primitiva.

Si utilizza il teorema di Bayes per classificare dei documenti (ad esempio per definire se un messaggio di email è spam oppure no) a partire dal contenuto delle proprie parole. \[P(Y|X) = \frac{P(Y)P(X|Y)}{P(X)}\] \[P(C_i|X) = \frac{P(C_i)\prod_jP(x_j|C_i)}{P(X)}\] In generale si assume indipendenza tra le varie \(P(x_i|Y)\).

I valori di \(P(x_j|C_i)\) si possono calcolare in uno dei due modi seguenti:

Ntive BAyes Multinomiale

\(P(x_j|C_j)\) è il numero di istanze di \(C_i\) la cui feature j-esima ha valore \(X_j\), tutto diviso per la cardinalità di \(C_i\);

Native Bayes Gaussiano

Assumere che \(P(x_j|C_i) \sim N(\mu_D, \sigma_D^2)\).

Onde evitare che l'assenza di un termine provochi il "collasso" del metodo, si applica la coorezione di Laplace, ovvero si aggiunge 1 a tutte le le istanze onde evitare l'esistenza di zeri. Durante il training si salta un valore non trovato, mentre testando si assume una disribuzione \(P(x_j|C_i)\) uguale per ogni \(C_i\).

Spesso si trasformano i \(P(C_i|X)\) per motivi di stabilità numerica e computazionale.

"Normalized Discounted Cumulative Gain". Usato generalmente per dare una misura della qualità dei motori di ricerca.

Il principio è cercare i primi \(k\) documenti e sommare assieme il loro contributo (gain \(G(r)\)); più avanti nella pagina stanno, meno significatività hanno (descritto dal termine discount \(D(r)\)). \[NDCG = \sum_r \frac{2^r - 1}{\log_2(1+r)} = \sum_r G(d_r)\cdot D(r)\]

Generare il ranking \(r\) non è facile. Si può

• Chiedere agli utenti di dare un voto ai risultati di ricerca
• Processare gli input (fissazione, click, riformulazione della ricerca…) come indicazione
• Tracciare il movimento degli occhi
• Chiedere un feedback agli utenti per i primi due risutati

Algoritmo usato da Google per determinare un ranking delle pagine web da mostrare.

Funziona contando il numero e la qualità dei link a una pagina per stimare quanto importante sia una pagina. L'assunzione è che siti web più importanti hanno più probabilità di avere link esterni da altri siti web.

Un vero neurone è qualcosa con numerosi input (dendriti) e un solo output (assone).

Allo stesso modo un neurone artificiale è una funzione di numerosi input (vettori e matrici)e un solo output. A differenza dei neuroni naturali, questi sono deterministici.

Utilizza molti layer nascosti di neuroni tra input e output, utilizzando il metodo Gradient Descent (con un learning rate) per trovare un minimo della funzione di loss, possibilmente un minimo globale. Si possono usare diverse strategie per ottimizzare il processo:

Stochastic Gradient Descent (SDG)

utilizza metodi di random sampling per la risoluzione del problema del Gradient Descent

Metodo dei momenti

Ottimizzazione del layer di neuroni in sé

Esiste un teorema chiamato Universal Approximation Theorem che dice che un network composto da trre layer con abbastanza nodi nascosti può approsimare qualsiasi funzione continua.

Utilizzando funzioni di attivazione non lineari, il modello riesce a imparare anche funzioni non lineari.

La funzione di loss serve a misurare l'errore tra la predizione e il valore vero. Esistono vari modi in cui definirne una, tra cui:

• \(MSE\) o anche \(MAE\) per problemi di regressione;
• Crossentrpy binaria o categorica per problemi di classificazione

I Convolutional Neural Networks (CNN) sono delle reti particolari in cui all'interno sono presenti neuroni che effettuano l'operazione matematica della convoluzione. Sono usati ad esempio nei problemi di classificazione di immagini.

Quando un Neural Network si adatta troppo ad un dataset, l'accuratezza del training aumenta ma l'accuratezza nel test diminuisce. Succede per varie ragioni:

• Il modello è troppo complesso e non ci sono abbastanza dati
• Il dataset di training e test non sono campionati correttamente

Pe ril primo caso, se non si può semplificare il modello, occorre aggiungere più dati ed espandere il dataset (data augumentation). Inoltre si possono utilizzare dei dropout per avere dei pesi più generici.

Un dropout altro non è che scollegare un certo numero di neuroni a caso dalla rete neurale.

Il processo di utilizzare uno o più layer di neuroni su cui è già stato fatto il training in un altro modello, facendo semplicemente un fine-tuning dei parametri in modo tale da poter cambiare obbiettivo in output o anche numero di classi in input.

Scegliere la misura della qualità all'inizio del lavoro

Cosa mi interessa che classifichi? Quanto accurata?

Fissa il processo di valutazione

Training e testing sempre uguali

Prepara i dati

In forma matriciale, scegli gli encoding…

Trova un caso base "ovvio"

Ad esempio la classe più prevalente

Trova un caso base migliore

Ad esempio fai una classificazione lineare

Costruisci un modello

Stai attento alla funzione di loss e all'ultimo layer di attivazione (nel dubbio ReLU e rmsprop)

Lascia che il modello vada in overfitting

Per essere sicuro che stia effettivamente imparando qualcosa

Sistema l'overfitting

rimuovi layer, aggiungi dropout, aggiungi dati, sistema la dimensione della batch…

…

😳

Profit!

Il modello funziona

Se necessario, crea un modello nuovo da zero

Ci sta rifare da capo

L'obbiettivo è raggruppare oggetti simili o relazionati tra loro e oggetti sufficentemente diversi in altri gruppi. L'analisi dei clustering serve a trovare similarità tra i dati.

Il clustering è un tipo di unsupervised learning, ovvero un modello che non ha informazioni sulle classi del dataset. Potrebbe essere che si conoscono ma non si vogliono fornire al modello, oppure non si sanno proprio. Può essere usato come una cosa a sé stante oppure come preprocesso ad altri algoritmi.

Un buon clustering ha una alta similarità tra gli oggetti della stessa classe e una grande differenza dagli oggetti delle altre classi. La qualità dipende moltissimo dalla qualità della misura della similarità, l'algoritmo e la sua abilità a trovare pattern.

Se le classi vere non si conoscono, è difficile misurare la qualità. Inoltre, per spazi ad alte dimensioni, i punti sono più vicini (fenomeno detto curse of dimensionality).

Ci sono molte cose da tenere in considerazione:

Criteri di partizionamento

Livello singolo o gerarchico

Separazione dei cluster

Esclusivo (ad ogni cluster corrisponde una classe) oppure non esclusivo, (classi multiple con livelli differenti, anche detto fuzzy)

Misure di similitudine

Ad esemipio, basate sulla distanza o sulla connettività dei punti

Spazio di clustering

Spazio completo oppure un sottospazio dei dati (ad esempio, usato per dati in alte dimensioni)

Le distanze possono essere dipendenti (Minkowski) oppure invarianti (coseno, correlazione) rispetto alla scala del problema.

Costruisce delle partizioni dei dati e le analissa basandosi su un criterio (chiamato la distanza). La soluzione esatta è un problema \(NP-hard\), quindi spesso si utilizza un approccio euristico: minimizzare una funzione obiettivo (come ad esempio minimizzare \(\sum_{a,b\in C} (d(b) - d(a))^2\), la somma dei quadrati delle distanze all'interno dello stesso cluster \(C\)).

Si crea una decomposizione gerarchica del dataset per poi selezionare un certo numero di tagli del dataset. Anche questo metodo usa una distanza o una matrice di similarità.

L'approccio può essere agglomerativo (costruisce, bottom up) oppure divisivo (taglia, top down).

Questi approcci si basano sull'utilizzo di una funzione di densità e sulla connettività tra i punti. Il vantaggio è l'arbitrarietà delle forme dei cluster e una minore suggestività agli outlier.