Esercizio - Albero di isolamento passo per passo (laboratorio di ripasso)

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (laboratorio di ripasso). Si costruisce un albero di isolamento (isolation tree) in modo iterativo, con una coda invece della ricorsione, su dati senza etichette: $500$ punti normali (gaussiana bidimensionale) e $10$ anomalie lontane dal centro. Si risponda a:

1. Come si costruisce un albero di isolamento e cosa c'è di casuale?
2. Perché si fissa una profondità massima e cosa è la correzione $c(n)$? Si calcolino $c(2)$, $c(10)$, $c(256)$.
3. Come si calcola il punteggio di anomalia di un punto con una foresta di alberi? Si calcoli per profondità medie $3$, $8$, $12$ con $\psi=256$ campioni per albero.
4. Un esempio in una dimensione: dati $\{1,2,3,4,100\}$.

Teoria usata: Anomaly detectionUn'anomalia (outlier) è un'osservazione che si discosta tanto dalle altre da far pensare che sia generata da un meccanismo diverso. Rilevarle serve come pulizia dei dati (solo se sono errori o rumore, non per migliorare artificialmente le metriche), come obiettivo finale (frodi, guasti, cybersicurezza) e per il monitoraggio di un modello in produzione. Metodi semplici: box plot (oltre $1{,}5,\mathrm{IQR}$), carte di controllo univariate ($\mu\pm3\sigma$) e la statistica multivariata di Hotelling $T^2=(x-\bar x)^TS^{-1}(x-\bar x)$ con soglia $\chi^2_{p,1-\alpha}$, valida per dati gaussiani e unimodali. Metodi non supervisionati multivariati danno un anomaly score: l'isolation forest isola ogni punto con split casuali (le anomalie hanno cammini corti) e calcola $s(x,n)=2^{-E(h(x))/c(n)}$, con soglia scelta dalla contaminazione. Senza etichette si valuta con esperti, eventi noti o anomalie sintetiche. Approfondimento: non nel programma di Telecomunicazioni.Anomaly detection →, Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione →, Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →, Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →.

1. Costruzione

Idea. I punti anomali sono pochi e diversi: bastano pochi tagli casuali per isolarli, mentre un punto normale, circondato da altri, richiede molti tagli. L'albero non usa etichette (è non supervisionato).

Procedura per un nodo con insieme di punti $X_{sub}$ e profondità $d$:

1. è una foglia se $d\ge$ max_depth, oppure ha al più $1$ punto, oppure tutti i punti sono uguali;
2. altrimenti si sceglie una feature a caso; si sceglie una soglia a caso, uniforme tra il minimo e il massimo di quella feature nel nodo ($\text{uniform}(\min,\max)$);
3. si dividono i punti: a sinistra quelli con valore $\le$ soglia, a destra gli altri (è un iperpiano parallelo agli assi);
4. si creano due figli a profondità $d+1$ e li si mettono in coda.

Le scelte casuali sono: la feature e la soglia a ogni nodo (e, nella foresta, il sottocampione di dati di ogni albero).

Inferenza. Per un nuovo punto si scende l'albero con le stesse regole fino a una foglia e si restituisce la profondità della foglia (più è bassa, più il punto è isolabile, quindi anomalo).

2. Profondità massima e correzione $c(n)$

Si ferma la crescita a una profondità massima (circa $\log_2\psi$) perché a noi interessano i punti isolati presto. Se una foglia a profondità massima contiene ancora $n>1$ punti non isolati, la sua profondità viene corretta aggiungendo $c(n)$: la profondità media attesa di una ricerca non riuscita in un albero binario di ricerca con $n$ punti,

$$c(n)=2\big(\ln(n-1)+\gamma_E-\tfrac{n-1}{n}\big)\ \ (n>2),\qquad c(2)=1,\ \ c(n\le1)=0,$$

con $\gamma_E=0{,}5772$ la costante di Eulero-Mascheroni. È la profondità che l'albero avrebbe avuto se si fosse proseguito fino all'isolamento.

Esempi. $c(2)=1$. $c(10)=2(\ln9+0{,}5772-0{,}9)=2(2{,}1972+0{,}5772-0{,}9)=3{,}7489$. $c(256)=2(\ln255+0{,}5772-255/256)=2(5{,}5413+0{,}5772-0{,}9961)=10{,}2448$.

3. Punteggio di anomalia

Si addestrano $T$ alberi (nel lab $100$) ognuno su un sottocampione di $\psi$ punti (per esempio $256$), con profondità massima $6$ per i dati del lab. Per un punto $x$ si calcola la profondità media $E[h(x)]$ sugli alberi e

$$s(x)=2^{-E[h(x)]/c(\psi)}.$$

Interpretazione: $E[h]\to0$ dà $s\to1$ (anomalo); $E[h]=c(\psi)$ dà $s=0{,}5$ (tipico); $E[h]$ grande dà $s\to0$ (molto normale).

Con $\psi=256$, $c(256)=10{,}245$:

Un punto con profondità media $3$ è isolato molto presto, punteggio alto ($0{,}82$): candidato anomalo. Quello con profondità $12$ sta in una zona densa ($0{,}44<0{,}5$). La soglia (per esempio l'$1\%$ più alto dei punteggi) si sceglie sui dati: si segnalano come anomalie i punti con punteggio sopra il percentile prefissato.

4. Esempio in una dimensione

Dati $\{1,2,3,4,100\}$. Il primo taglio è uniforme in $[1,100]$ (lunghezza $99$): cade tra $4$ e $100$ con probabilità $96/99=0{,}97$, e in tal caso divide $\{1,2,3,4\}\mid\{100\}$, quindi il punto $100$ è isolato già a profondità $1$. Per isolare invece uno dei punti vicini, per esempio $4$, serve prima un taglio verso $100$ (che lo separa dal valore estremo) e poi altri tagli dentro l'intervallo $[1,4]$, quindi almeno profondità $2$ e in media di più. La profondità media di $100$ è dunque vicina a $1$ e quella dei punti $1$-$4$ è maggiore: $100$ ha il punteggio di anomalia più alto, come ci si aspetta.

Codice (scheletro del lab, completato)

def get_depth(node, x):
    while not node.is_leaf:
        node = node.left_node if x[node.feature] <= node.threshold else node.right_node
    return node.depth

def predict_isolation_forest(trees, X, c_n):
    depths = np.zeros((X.shape[0], len(trees)))
    for j, t in enumerate(trees):
        depths[:, j] = [get_depth(t, x) for x in X]
    return 2 ** (-depths.mean(axis=1) / c_n)             # punteggio di anomalia