Esercizio - Isolation forest da zero e anomalie sul dataset delle abitazioni

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

Testo (laboratorio LAB6 e 3° appello 2025).

1. Implementare da zero un isolation tree (split casuali, feature e soglia, profondità massima $8$, profondità corretta $d+c(n)$) e una isolation forest (sottocampioni di $256$ punti, $100$ alberi, anomaly score $2^{-E[h]/c(n)}$, soglia dalla contaminazione).
2. Sul dataset California Housing con le due variabili MedInc e AveRooms (20 640 punti): trovare i 10 e i 100 punti più anomali; iniettare $6$ anomalie sintetiche e verificare che vengano trovate.
3. (Appello) Con le sole colonne Longitude e Latitude del dataset delle abitazioni modificato (20 649 punti), identificare l'$1\%$ di punti più anomali; commentare dove cadono.

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 → (isolation forest, $c(n)$, contaminazione, valutazione con anomalie sintetiche); 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 → per la struttura ad albero; gli alberi di isolamento sono la parte non supervisionata di 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 →. Ripasso delle stesse idee: Esercizio - Albero di isolamento passo per passo (laboratorio di ripasso).

1. Implementazione

Normalizzazione $c(n)$. $c(n)=2H(n-1)-\frac{2(n-1)}n$, con $H(m)\approx\ln m+0{,}5772$; $c(1)=0$, $c(2)=1$. Per $n=256$: $c=10{,}25$.

Albero. Si parte da un sottocampione $X$ (256 punti):

• foglia se il nodo ha $\le1$ punto, o la profondità è $8$, o tutti i punti sono uguali; la profondità della foglia è $d+c(n_{\text{nodo}})$ (correzione per i nodi interrotti con più punti);
• altrimenti si sceglie a caso una feature $f$ e una soglia $t\sim U(\min X_f,\max X_f)$, e si divide in $X_f\le t$ e $X_f>t$.

class IsolationTree:
    def _build(self, X, depth, node_id):
        n = len(X)
        if n <= 1 or depth >= self.max_depth or all(len(np.unique(X[:, f])) == 1 for f in range(X.shape[1])):
            self.nodes[node_id] = Node(None, None, depth + c(n)); return    # foglia con profondità corretta
        f = np.random.randint(X.shape[1]); t = np.random.uniform(X[:, f].min(), X[:, f].max())
        self.nodes[node_id] = Node(f, t, depth)
        left = X[:, f] <= t
        self._build(X[left], depth + 1, 2 * node_id + 1); self._build(X[~left], depth + 1, 2 * node_id + 2)

Foresta. Per ognuno dei 100 alberi: sottocampione di $256$ punti senza rimpiazzo, albero. Score di $x$: profondità media su tutti gli alberi $E[h(x)]$ e $s=2^{-E[h]/c(256)}$. Soglia: percentile $100(1-\text{contaminazione})$ degli score di training.

2. California Housing: MedInc e AveRooms

Con contaminazione $0{,}1$: mediana degli score $0{,}42$, soglia $0{,}52$, massimo $0{,}81$. I punti più anomali sono casi estremi:

(reddito altissimo con molte stanze, o reddito bassissimo con un numero enorme di stanze per abitazione: dati rari e quasi certamente atipici). Un punto «normale» ha score intorno a $0{,}4$ perché è isolato solo dopo $\approx13$ split (profondità corretta), un outlier dopo $3$-$5$.

Iniezione di 6 anomalie. Con media $(\mu_1,\mu_2)=(3{,}87;\ 5{,}43)$ e deviazione standard $(1{,}90;\ 2{,}47)$ si aggiungono $6$ punti a $(+7\sigma_1,+3\sigma_2)$, $(+3\sigma_1,+10\sigma_2)$, $(+6\sigma_1,+5\sigma_2)$, $(+4\sigma_1,+12\sigma_2)$, $(+3\sigma_1,+8\sigma_2)$, $(+4\sigma_1,+3\sigma_2)$. Dopo il riaddestramento i ranghi dei sei punti iniettati nella classifica degli score sono $8,\ 9,\ 3,\ 2,\ 11,\ 72$ (su $20\,646$), con score $0{,}783;\ 0{,}782;\ 0{,}796;\ 0{,}807;\ 0{,}778;\ 0{,}756$: cinque su sei sono nei primi 11 e superano quasi tutti i punti naturali del dataset. L'ultimo, $(+4\sigma,+3\sigma)$, è il meno estremo (a soli $4$ e $3$ deviazioni standard dalla media) e si confonde con le code naturali (rango 72, score $0{,}756$ comunque alto). Questa è la valutazione per iniezione sintetica (si veda 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 →): senza etichette si controlla almeno che gli outlier noti siano trovati. I punti naturali più anomali (per esempio quello con MedInc $=15$) restano comunque nelle prime posizioni (rango 1, 4, 5, ... nella classifica con le iniezioni).

Limite («bias»). Con gli split paralleli agli assi, nelle zone vuote tra i gruppi gli score possono restare bassi; per un esempio con due gruppi gaussiani ruotati il grafico degli score mostra zone scure (score basso, «normali») anche lontane dai cluster. Un nuovo punto lì non verrebbe segnalato.

3. Appello: solo latitudine e longitudine

Con contaminazione $0{,}01$ (soglia: 99-esimo percentile degli score), $300$ alberi e sottocampioni di $1000$ punti si segnalano $207$ punti su $20\,649$ ($1\%$): score soglia $0{,}66$, mediana $0{,}44$. Dove cadono? Il $70\%$ degli anomali ha latitudine $>39{,}5$ (in tutto il dataset solo il $2{,}9\%$ dei distretti è lì, il nord scarsamente popolato della California), il $56\%$ ha longitudine $<-123$ (costa nord-occidentale) e il $24\%$ longitudine $>-117$ (deserto e zone orientali), mentre le zone dense (Los Angeles: score $0{,}39$; San Francisco: $0{,}43$) hanno score bassi. Il metodo individua quindi le zone poco popolate: sono «anomali» i distretti isolati, non per forza errori. Una domanda del tema: ci sono punti che a occhio sembrano anomali ma che il modello non segnala? Può succedere nelle zone vuote interne: per esempio il punto $(-120{,}5;\,35)$, in una zona poco popolare dell'interno, ha score $0{,}55$, sotto la soglia $0{,}66$. Le zone lontane dagli altri cluster ma che gli split casuali (paralleli agli assi) non riescono a isolare presto ottengono score moderati: è il limite del metodo già visto per il «bias» dell'isolation forest.

Variante meno casuale (domanda del tema). Per esempio non riusare una feature già usata nel ramo. Non ci si aspetta che migliori: con soli due feature dopo due split non ci sono più feature e l'albero si ferma, riducendo la capacità di isolare; la casualità è un punto di forza dell'algoritmo (medie su alberi diversi).