Anomaly detection

Dopo l'apprendimento supervisionato si passa a quello non supervisionato: in questa nota il rilevamento di anomalie, nella successiva il clustering (Clustering e k-meansIl clustering raggruppa osservazioni simili senza etichette, come preprocessing (un modello per ogni cluster) o come obiettivo (segmentazione clienti, organizzazione di documenti). K-means: si sceglie $K$, si inizializzano $K$ centroidi, si alterna assegnazione di ogni punto al centroide più vicino e aggiornamento di ogni centroide alla media dei suoi punti, fino a convergenza; minimizza $\mathrm{MSE}{\text{within}}=\frac1N\sum_k\sum{x_i\in C_k}|x_i-\mu_k|^2$ ma solo fino a un minimo locale, quindi dipende dall'inizializzazione. Il numero di cluster si sceglie col metodo del gomito (la dispersione cala sempre, si cerca dove rallenta) o con la gap statistic $\mathrm{Gap}(K)=E[\log W_K^{ref}]-\log W_K$ (si prende il più piccolo $K$ con $\mathrm{Gap}(K)\ge\mathrm{Gap}(K+1)-s_{K+1}$). Il clustering gerarchico agglomerativo parte da un cluster per punto e fonde i due più vicini (linkage single, complete, average, Ward) costruendo un dendrogramma; quello divisivo parte da un solo cluster. Programma di Telecomunicazioni: clustering.Clustering e k-means →). Gli esercizi sono Esercizio - Statistica T2 di Hotelling e soglia chi quadro e Esercizio - Isolation forest da zero e anomalie sul dataset delle abitazioni.

Apprendimento non supervisionato

Si ricordi la differenza (Introduzione al machine learningIl machine learning (ML) è la parte dell'intelligenza artificiale che costruisce soluzioni a partire dai dati e non da regole scritte a mano: un modello matematico con parametri liberi viene addestrato su esempi storici e poi usato su dati nuovi. Si distingue tra apprendimento supervisionato (dati $(x,y)$, si impara la mappa $x\mapsto y$: regressione se $y$ è un numero, classificazione se è una categoria), non supervisionato (solo $x$, si cercano struttura e gruppi) e per rinforzo (stato, azione, ricompensa). Un progetto ML non è «plug and play»: segue le fasi problema, raccolta, pulizia, modellazione, rilascio, e va valutato su dati mai visti; senza dati non c'è modello, alcuni fenomeni sono imprevedibili, la generalizzazione fuori dal dominio di addestramento non è garantita.Introduzione al machine learning →): nell'apprendimento supervisionato i dati sono coppie $(x,y)$ e si impara la mappa $x\mapsto y$; nel non supervisionato si hanno solo gli ingressi $x$, senza etichette, e il compito è scoprire la struttura o la distribuzione sottostante dei dati. Alcuni compiti non supervisionati: clustering (trovare gruppi), riduzione di dimensione (Analisi delle componenti principali (PCA)Con $p>3$ variabili non si può disegnare il dataset. La PCA (analisi delle componenti principali) lo proietta su pochi assi ortogonali, le componenti principali: dopo aver centrato (e di solito standardizzato) i dati, le direzioni sono gli autovettori della matrice di covarianza $S=\frac1{n-1}X_c^TX_c$ ordinati per autovalore $\lambda_1\ge\lambda_2\ge\dots$; $\lambda_k$ è la varianza lungo la componente $k$ e $\lambda_k/\sum\lambda_j$ la frazione spiegata (scree plot). Trovare la retta che minimizza le distanze dai punti equivale a massimizzare la varianza delle proiezioni (Pitagora). È lineare e conserva la struttura globale, non quella locale; t-SNE e UMAP sono alternative non lineari solo per visualizzare. Approfondimento: non nel programma di Telecomunicazioni.Analisi delle componenti principali (PCA) →), stima di densità, regole di associazione, topic modelling per testi, rilevamento di anomalie. Un compito non supervisionato può essere l'obiettivo finale del progetto o un passo di preprocessing.

Che cos'è un'anomalia

Definizione (anomalia o outlier). «Un outlier è un'osservazione che si discosta così tanto dalle altre da destare il sospetto di essere stata generata da un meccanismo diverso» (Hawkins, 1980). In un dataset, per definizione, gli outlier dovrebbero essere pochi.

Esempio. Un sensore di temperatura che segna $2000$ gradi invece di $200$ per un guasto del sensore.

Perché rilevare le anomalie

1. Preprocessing (pulizia). Gli outlier possono essere errori di inserimento o di misura che distorcono i risultati; toglierli può migliorare molto le prestazioni. Va fatto con attenzione, perché togliere i dati «difficili» migliora sempre le metriche.
   • Ha senso (non è barare): (i) sono errori o rumore (sensore guasto, «2000» al posto di «200»); (ii) si prepara il dato per un modello che assume la normalità, e la regressione lineare (Regressione lineareNell'apprendimento supervisionato si impara una funzione $F(x)$ dagli esempi $(x,y)$: regressione se $y$ è continua, classificazione se è categorica. Il modello lineare è $F_\beta(x)=\beta_0+\beta_1x_1+\dots+\beta_px_p=X\beta$ (con una colonna di uni per $\beta_0$) e i parametri si scelgono minimizzando l'errore quadratico medio $\mathrm{MSE}=\frac1n\sum_i(y_i-F_\beta(x_i))^2$, funzione convessa dei parametri. Annullando il gradiente di $J(\beta)=|y-X\beta|^2$ si ottengono le equazioni normali $X^TX\beta=X^Ty$ e la soluzione dei minimi quadrati ordinari $\beta=(X^TX)^{-1}X^Ty$. Il coefficiente di determinazione $R^2=1-SS_{res}/SS_{tot}$ misura la qualità del fit (0 = come la media, negativo = peggio della media). Un modello va valutato su un test set mai usato per addestrare: l'errore sul training è ottimistico e un polinomio di grado alto lo azzera senza generalizzare.Regressione lineare →) è molto influenzata dai valori estremi; (iii) si analizza il comportamento «tipico» (acquisto medio di un cliente).
   • È barare: (i) si tolgono solo per migliorare le metriche (per esempio togliendo i casi difficili dal test set: è fuga di informazione); (ii) gli outlier sono proprio ciò che interessa (frodi, diagnosi, guasti): toglierli annulla lo scopo. La decisione non è sempre facile: può servire la competenza di dominio e conviene tenere traccia delle scelte fatte.
2. Obiettivo finale. In molti ambiti il rilevamento è l'obiettivo: frodi, diagnostica di produzione industriale, cybersicurezza, transazioni nel marketing digitale.
3. Monitoraggio di una soluzione in produzione. Un modello distribuito va controllato: i dati devono rimanere coerenti con quelli dell'addestramento. Se compaiono outlier, si può non fidarsi della singola previsione o riaddestrare (principi di MLOps).

Metodi semplici

Box plot. Gli outlier sono i punti oltre i «baffi», cioè oltre $1{,}5\times\mathrm{IQR}$ da $Q_1$ e $Q_3$ (Correlazione e visualizzazione dei datiLa correlazione di Pearson $r=\sum(X_i-\bar X)(Y_i-\bar Y)/\big(\sqrt{\sum(X_i-\bar X)^2}\sqrt{\sum(Y_i-\bar Y)^2}\big)\in[-1,1]$ misura la relazione lineare tra due variabili (covarianza divisa per le deviazioni standard); correlazione non implica causalità. Serve a capire quali variabili contano per il target e a eliminare quelle quasi duplicate (|r| molto alto). Gli indicatori di sintesi non bastano (quartetto di Anscombe, Datasaurus): vanno affiancati ai grafici: istogramma, KDE, box plot, violin plot, heatmap di correlazione, scatter plot e matrice di scatter plot.Correlazione e visualizzazione dei dati →, Statistica per il machine learningI dati di un problema ML si organizzano nella matrice di progetto $X$ ($n$ osservazioni, $p$ variabili). La statistica serve a capirli, ripulirli e prepararli: i momenti (media $\mu$, varianza $\sigma^2$, asimmetria, curtosi), i quartili con lo scarto interquartile $\mathrm{IQR}=Q_3-Q_1$ (all'esame senza interpolazione), la moda per i dati categorici. Con queste quantità si imputano i dati mancanti (media o mediana), si eliminano le variabili costanti e si standardizza con lo z-score $z=(x-\mu)/\sigma$, usando sempre media e deviazione standard del solo training set.Statistica per il machine learning →).

Carte di controllo univariate. Molto usate in industria per il monitoraggio on-line. Una carta di controllo è il grafico nel tempo di una variabile (o di un indicatore di processo, KPI) con una linea centrale (la media attesa del processo) e due soglie, il limite di controllo superiore (UCL) e inferiore (LCL), che definiscono l'intervallo «normale»: $$\mathrm{UCL}=\mu_x+A\,\sigma_x,\qquad\mathrm{LCL}=\mu_x-A\,\sigma_x,$$ con $\mu_x,\sigma_x$ media e deviazione standard stimate. Con $A=3$ («tre sigma») e una variabile gaussiana (Distribuzione gaussiana (normale)N(μ, σ²) ha densità e^(−(x−μ)²/(2σ²)) / √(2πσ²), a campana centrata in μ con larghezza σ; media μ, varianza σ²; si standardizza con Z = (X − μ)/σ ~ N(0, 1) e si calcola P(X ≤ x) = Φ((x − μ)/σ), con Φ(−z) = 1 − Φ(z); aX + b è ancora gaussiana, N(aμ + b, a²σ²).Distribuzione gaussiana (normale) →) il $99{,}73\%$ dei dati è «inlier» (cioè $P(|X-\mu|\le3\sigma)=0{,}9973$).

Esempio. $\mu=50$, $\sigma=2$: $\mathrm{UCL}=56$, $\mathrm{LCL}=44$; la misura $57$ è un'anomalia.

Da dove viene il $99{,}73\%$ (passaggi). Se $X\sim N(\mu,\sigma^2)$ si standardizza $Z=(X-\mu)/\sigma\sim N(0,1)$ (Distribuzione gaussiana (normale)N(μ, σ²) ha densità e^(−(x−μ)²/(2σ²)) / √(2πσ²), a campana centrata in μ con larghezza σ; media μ, varianza σ²; si standardizza con Z = (X − μ)/σ ~ N(0, 1) e si calcola P(X ≤ x) = Φ((x − μ)/σ), con Φ(−z) = 1 − Φ(z); aX + b è ancora gaussiana, N(aμ + b, a²σ²).Distribuzione gaussiana (normale) →, Funzioni di una variabile aleatoriaPer trovare la legge di Y = g(X) si calcola la FdD: F_Y(y) = P(g(X) ≤ y) = P(X ∈ g⁻¹((−∞, y])), poi si deriva; se g è strettamente monotona e derivabile vale la formula f_Y(y) = f_X(g⁻¹(y)) · |(g⁻¹)'(y)|; se g è costante a tratti Y è discreta; se g non è iniettiva (es. X²) si spezza l'evento.Funzioni di una variabile aleatoria →). L'evento $|X-\mu|\le3\sigma$ equivale a $|Z|\le3$, quindi $P(|X-\mu|\le3\sigma)=\Phi(3)-\Phi(-3)=2\Phi(3)-1$, usando la simmetria $\Phi(-3)=1-\Phi(3)$ (Funzione di distribuzioneLa funzione di distribuzione (FdD) F_X(x) = P(X ≤ x) è definita per ogni v.a., è crescente, continua a destra, va da 0 a 1 e determina la legge; per una v.a. discreta è a gradini, con salti in corrispondenza dei valori e di altezza pari alla densità.Funzione di distribuzione →). Con $\Phi(3)=0{,}99865$ si ha $2\cdot0{,}99865-1=0{,}9973$. La probabilità di un falso allarme (punto normale fuori dai limiti) è $1-0{,}9973=0{,}0027$, cioè in media $1$ campione su $370$. Con $A=2$ la copertura sarebbe $0{,}9545$ ($1$ falso allarme su $22$ campioni), con $A=1$ solo $0{,}6827$: più $A$ è piccolo, più si rilevano anomalie vere ma più falsi allarmi si ricevono. Nell'esempio, la misura $57$ dista $\frac{57-50}{2}=3{,}5\sigma$: la probabilità di un valore così lontano per caso è $2(1-\Phi(3{,}5))=0{,}0005$.

Problemi. Con molte variabili servono molte carte: la complessità del monitoraggio cresce, c'è sovraccarico cognitivo e falsi allarmi. E soprattutto le carte univariate non vedono le anomalie multivariate, in cui ogni variabile è nella norma ma la combinazione no.

Statistica $T^2$ di Hotelling

Definizione (statistica $T^2$ di Hotelling). Per $p$ variabili, con media campionaria $\bar x$ e matrice di covarianza $S=\frac1{n-1}\sum_i(x_i-\bar x)(x_i-\bar x)^T$: $$T^2(x)=(x-\bar x)^T\,S^{-1}\,(x-\bar x).$$ È uno z-score multivariato: misura quanto un'osservazione è lontana dalla media tenendo conto delle correlazioni. Un punto è un outlier multivariato se $T^2>\mathrm{UCL}$.

Perché proprio $S^{-1}$ (idea). Nel caso di una variabile $T^2=(x-\bar x)^2/s^2=z^2$ è il quadrato dello z-score (Statistica per il machine learningI dati di un problema ML si organizzano nella matrice di progetto $X$ ($n$ osservazioni, $p$ variabili). La statistica serve a capirli, ripulirli e prepararli: i momenti (media $\mu$, varianza $\sigma^2$, asimmetria, curtosi), i quartili con lo scarto interquartile $\mathrm{IQR}=Q_3-Q_1$ (all'esame senza interpolazione), la moda per i dati categorici. Con queste quantità si imputano i dati mancanti (media o mediana), si eliminano le variabili costanti e si standardizza con lo z-score $z=(x-\mu)/\sigma$, usando sempre media e deviazione standard del solo training set.Statistica per il machine learning →): la distanza dalla media misurata in deviazioni standard. Con $p$ variabili la «deviazione standard» diventa la matrice di covarianza $S$ (Covarianza e coefficiente di correlazioneCov(X, Y) = E[(X − E X)(Y − E Y)] = E[XY] − E[X]E[Y] misura quanto X e Y variano insieme; è bilineare, Cov(X, X) = Var(X), Var(X + Y) = Var X + Var Y + 2Cov(X, Y); ρ = Cov / (σ_X σ_Y) sta in [−1, 1] e vale ±1 solo per legami lineari. Indipendenti ⇒ non correlate, ma non viceversa (tranne per i vettori gaussiani).Covarianza e coefficiente di correlazione →: sulla diagonale le varianze, fuori le covarianze), e dividere per $s^2$ diventa moltiplicare per l'inversa $S^{-1}$ (Matrice inversaL'inversa di una matrice quadrata A è la matrice A⁻¹ con A A⁻¹ = A⁻¹ A = I; esiste se e solo se rango(A) = n e si calcola con Gauss-Jordan riducendo (A | I) fino a (I | A⁻¹).Matrice inversa →). Se le variabili sono indipendenti con varianze $s_j^2$, $S$ è diagonale e $T^2=\sum_j\frac{(x_j-\bar x_j)^2}{s_j^2}$: la somma dei quadrati degli z-score, con ogni variabile pesata per la propria scala. Con correlazioni, $S^{-1}$ corregge anche per esse.

Per dati gaussiani, $T^2$ segue una distribuzione chi-quadro con $p$ gradi di libertà (Vettori gaussianiX = (X₁, ..., Xₙ) è un vettore gaussiano N(m, Σ) se ogni combinazione lineare a·X è gaussiana (equivalentemente X = m + AZ con Z gaussiane standard indipendenti); se Σ è invertibile ha densità exp(−½(x−m)ᵀΣ⁻¹(x−m)) / √((2π)ⁿ det Σ). Proprietà chiave: AX + b ~ N(Am + b, AΣAᵀ), le marginali sono gaussiane e componenti non correlate sono indipendenti.Vettori gaussiani →; il chi-quadro è un caso della Distribuzione gammaΓ(α, λ) ha densità λ^α x^(α−1) e^(−λx) / Γ(α) per x > 0, dove Γ(α) = ∫ x^(α−1) e^(−x) dx è la funzione Gamma (Γ(n) = (n − 1)!, Γ(1/2) = √π); media α/λ, varianza α/λ²; Γ(1, λ) = Exp(λ), e la somma di n esponenziali Exp(λ) indipendenti è Γ(n, λ), il tempo d'attesa dell'n-esimo evento.Distribuzione gamma →), e $$\mathrm{UCL}=\chi^2_{p,\,1-\alpha},$$ dove $p$ è il numero di variabili e $\alpha$ quanto si vuole essere severi (valori tipici $0{,}05$ o $0{,}01$): è il quantile di livello $1-\alpha$ del chi-quadro, che si legge su tabelle.

Esempio. Quantili: per $p=1$ e $\alpha=0{,}05$, $\chi^2=3{,}841$ (uguale a $1{,}96^2$); per $p=2$: $5{,}991$ ($\alpha=0{,}05$) e $9{,}210$ ($\alpha=0{,}01$); per $p=3$: $7{,}815$. Caso univariato: con media $\bar x$ e varianza $s^2$ la statistica è $(x-\bar x)^2/s^2$: nel laboratorio, per $100$ valori da $N(0,1)$ il punto $x=5$ ha $T^2\approx24$, ben oltre $3{,}841$: anomalo.

Esempio bidimensionale. Si abbiano due variabili con media $(0,0)$, varianze $1$ e covarianza $0{,}8$: $S=\begin{pmatrix}1&0{,}8\\0{,}8&1\end{pmatrix}$. L'inversa (Matrice inversaL'inversa di una matrice quadrata A è la matrice A⁻¹ con A A⁻¹ = A⁻¹ A = I; esiste se e solo se rango(A) = n e si calcola con Gauss-Jordan riducendo (A | I) fino a (I | A⁻¹).Matrice inversa →) ha determinante $1-0{,}64=0{,}36$ e vale $S^{-1}=\frac1{0{,}36}\begin{pmatrix}1&-0{,}8\\-0{,}8&1\end{pmatrix}$. Per il punto $x=(1,-1)$ si ha $x^TS^{-1}x=\frac1{0{,}36}\big(1\cdot1+2\cdot(-0{,}8)\cdot1\cdot(-1)+1\cdot1\big)=\frac{1+1{,}6+1}{0{,}36}=10$. Poiché $10>5{,}991$ il punto è un outlier, anche se ciascuna coordinata, presa da sola, vale $\pm1$ cioè è entro una deviazione standard: le due variabili sono molto correlate e vederle di segno opposto è insolito. La distanza euclidea normale darebbe invece $x^Tx=2$.

(Per $x=(2,2)$: $\frac{4-1{,}6\cdot4+4}{0{,}36}=\frac{1{,}6}{0{,}36}=4{,}44$.)

Perché l'ellisse è allungata lungo la diagonale (autovalori). La regione $T^2\le c$ è $\{x:\ x^TS^{-1}x\le c\}$, un'ellisse i cui assi sono gli autovettori di $S$ (Autovalori e autovettoriUn autovettore è un vettore non nullo che una funzione lineare manda in un suo multiplo; si trovano gli autovalori come radici del polinomio caratteristico det(A − λI) e gli autovettori come nucleo di A − λI. Matrici simili hanno gli stessi autovalori.Autovalori e autovettori →, Teorema spettrale e forme quadraticheUna funzione lineare è simmetrica se f(v)·w = v·f(w); in una base ortonormale ha matrice simmetrica. Teorema spettrale: f è simmetrica se e solo se esiste una base ortonormale di autovettori, cioè A simmetrica ⇔ PᵀAP diagonale con P ortogonale. Applicato alle forme quadratiche, permette di scriverle come somma di quadrati con gli autovalori come coefficienti.Teorema spettrale e forme quadratiche →: $S$ è simmetrica, quindi gli autovettori sono ortogonali). Qui $S=\begin{pmatrix}1&0{,}8\\0{,}8&1\end{pmatrix}$:

1. equazione caratteristica $\det(S-\lambda I)=(1-\lambda)^2-0{,}64=0$, quindi $1-\lambda=\pm0{,}8$ e $\lambda_1=1{,}8$, $\lambda_2=0{,}2$;
2. autovettore di $\lambda_1=1{,}8$: $(S-1{,}8I)v=0$ dà $-0{,}8v_1+0{,}8v_2=0$, $v=(1,1)/\sqrt2$ (la diagonale); per $\lambda_2=0{,}2$: $v=(1,-1)/\sqrt2$ (l'antidiagonale);
3. lungo un autovettore $v$ di $S$ con autovalore $\lambda$ vale $S^{-1}v=v/\lambda$, quindi un punto $x=d\,v$ ha $T^2=d^2/\lambda$ (distanza al quadrato divisa per la varianza in quella direzione). La semilunghezza dell'ellisse è allora $d=\sqrt{c\lambda}$: con $c=5{,}991$, $\sqrt{5{,}991\cdot1{,}8}=3{,}28$ lungo la diagonale e $\sqrt{5{,}991\cdot0{,}2}=1{,}09$ lungo l'antidiagonale. Per i punti dell'esempio: $(2,2)$ sta sulla diagonale a distanza $\sqrt8=2{,}83$, $T^2=\frac{8}{1{,}8}=4{,}44$; $(1,-1)$ sta sull'antidiagonale a distanza $\sqrt2=1{,}41>1{,}09$, $T^2=\frac2{0{,}2}=10$. Il grafico mostra gli assi dell'ellisse.

Limiti. Le variabili reali sono raramente gaussiane e raramente unimodali (con un solo picco): nei dati industriali reali spesso molte anomalie restano non rilevate perché la nube ha più gruppi o forme non ellittiche.

Rilevamento multivariato non supervisionato

I metodi multivariati non supervisionati producono un anomaly score: un unico indicatore quantitativo del grado di «anomalia» di un sistema con molte variabili. Vantaggi: (1) non servono dati etichettati; (2) si possono considerare decine o centinaia di variabili insieme; (3) non serve che i dati siano gaussiani o unimodali. Famiglie di metodi (per dati tabellari, per esempio nella libreria PyOD): basati sulla densità (LOF, DBSCAN), sulla distanza (k-NN, Classificazione e k-nearest neighborsNella classificazione l'uscita $y$ è una categoria (con $C$ classi; $C=2$ è il caso binario). Il classificatore più semplice è il k-nearest neighbors: una nuova osservazione prende la classe più frequente (voto di maggioranza) tra i suoi $k$ vicini più prossimi nel training, con distanza euclidea $\sqrt{\sum(A_i-B_i)^2}$ o di Manhattan $\sum|A_i-B_i|$ (per la regressione si fa la media dei vicini). $k$ è un iperparametro: $k$ piccolo dà bordi frastagliati e overfitting, $k$ grande underfitting. È un metodo basato su istanze e «pigro» (nessun addestramento, costo alla predizione), sensibile a scala e feature irrilevanti e alla maledizione della dimensionalità; gli ingressi categorici si codificano con one-hot. Approfondimento: non nel programma di Telecomunicazioni.Classificazione e k-nearest neighbors →), sul clustering (CBLOF), su reti neurali (autoencoder, Autoencoderapprofondimento: non nel programma di Telecomunicazioni. Un autoencoder è una rete non supervisionata che impara a ricostruire il proprio ingresso passando per un collo di bottiglia: encoder $z=e(x)$ (dimensione bassa), decoder $\hat x=d(z)$, loss $|x-d(e(x))|^2$. Con attivazioni lineari equivale alla PCA; con non linearità impara rappresentazioni latenti più ricche (ipotesi del manifold). Varianti: sparse (penalità $\ell_1$ sulle attivazioni), denoising (ingresso corrotto, bersaglio pulito), convolutivi (inpainting). Anomaly detection: si addestra su dati normali e si segnala come anomalo ciò che ha errore di ricostruzione sopra una soglia. VAE: l'encoder produce media e deviazione standard di una gaussiana, il campione si ottiene con il trucco di riparametrizzazione $z=\mu+\sigma\odot\zeta$, $\zeta\sim\mathcal N(0,I)$, e la loss è errore di ricostruzione più KL verso $\mathcal N(0,I)$, con $KL=\frac12\sum(\mu^2+\sigma^2-1-\ln\sigma^2)$; il $\beta$-VAE pesa il KL con $\beta>1$ per rappresentazioni disaccoppiate. Cenno ai GAN.Autoencoder →), e l'isolation forest.

Isolation forest

L'isolation forest (Liu et al.) è un algoritmo efficiente che supera altri metodi in molti ambiti. Si basa su un procedimento di partizione (che costruisce gli isolation tree) e sull'idea che outlier e inlier siano influenzati in modo diverso: un punto anomalo, lontano dagli altri, viene separato con pochi split casuali; un punto in una zona densa ne richiede molti. È un metodo ensemble (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 →): lo score è la media della profondità su molti alberi.

Esempio (dalle slide). Isolare un inlier in mezzo ai dati richiede 4 split; isolare un outlier isolato in un angolo, 1 solo.

L'albero di isolamento

Si costruisce un albero binario in modo ricorsivo su un sottoinsieme dei dati:

• a ogni nodo si sceglie a caso una feature e a caso un valore di split tra il minimo e il massimo di quella feature nei dati del nodo;
• si ferma quando il nodo ha un solo punto, oppure si raggiunge la profondità massima (di solito $\lceil\log_2n\rceil$ con $n$ la dimensione del campione), oppure tutti i punti sono uguali.

Ogni cammino dalla radice a una foglia isola un punto: la profondità della foglia, cioè il numero di split necessari, misura quanto il punto è facile da isolare.

Perché tanta casualità. L'obiettivo non è apprendere un modello preciso ma separare le anomalie dal resto in fretta. (1) Le anomalie sono rare e molto diverse: gli split casuali le isolano presto (a poca profondità). (2) Non servono split «buoni» come nei decision tree (Gini, entropia): conta solo quanti split servono per isolare un punto, quindi il caso va bene, anzi è ideale. (3) Mediare su molti alberi con split casuali diversi rende la stima robusta. La scelta casuale della feature evita bias ed esplora tutte le dimensioni; quella casuale del valore semplifica e accelera.

Un esempio in una dimensione, con i numeri. Cinque valori $\{1,2,3,4,100\}$ e split uniforme tra il minimo e il massimo dei punti del nodo, cioè in $[1,100]$ al primo passo (ampiezza $99$). Il punto $100$ è isolato al primo split se la soglia cade in $(4,100)$, che ha ampiezza $96$: probabilità $\frac{96}{99}=0{,}97$ (Distribuzioni uniforme continua ed esponenzialeU(a, b) ha densità costante 1/(b − a) su [a, b], media (a + b)/2 e varianza (b − a)²/12; Exp(λ) ha densità λe^(−λx) per x ≥ 0, FdD 1 − e^(−λx), P(X > t) = e^(−λt), media 1/λ, varianza 1/λ², ed è l'unica legge continua senza memoria (versione continua della geometrica).Distribuzioni uniforme continua ed esponenziale →: la soglia ha densità uniforme, quindi la probabilità è la lunghezza dell'intervallo diviso per $99$). Il punto $1$ si isola subito solo se la soglia cade in $(1,2)$: probabilità $\frac1{99}=0{,}01$. Su $20\,000$ simulazioni la profondità media (numero di split per isolare il punto) è $1{,}03$ per il punto $100$, $2{,}80$ per $1$, $3{,}49$ per $2$, $3{,}49$ per $3$, $2{,}83$ per $4$: l'anomalia $100$ ha profondità circa tre volte più piccola di quelle dei punti centrali. Gli estremi della nube sono più facili da isolare dei punti centrali, ma il valore $100$, lontano dagli altri, lo è molto di più.

Passi dell'algoritmo

1. Sottocampionare: da tutto il dataset si estrae a caso un sottoinsieme (per esempio $256$ punti): riduce il costo e migliora la generalizzazione.
2. Costruire un albero per ciascun sottocampione con le regole sopra.
3. Ripetere per costruire una foresta (tipicamente $100$ alberi), ciascuno su un campione diverso.
4. Calcolare le lunghezze dei cammini: ogni punto del dataset originale è fatto scendere in tutti gli alberi e si registra la profondità raggiunta.
5. Calcolare l'anomaly score. Per il punto $x$, con $E(h(x))$ la lunghezza media del cammino su tutti gli alberi:

   $$s(x,n)=2^{-E(h(x))/c(n)},\qquad c(n)=2H(n-1)-\frac{2(n-1)}{n},\qquad H(m)=1+\frac12+\frac13+\dots+\frac1m\ \ (\approx\ln m+0{,}5772).$$ $c(n)$ è la lunghezza media di una ricerca senza successo in un albero binario di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca → con $n$ nodi: è la lunghezza attesa di un cammino in un albero con $n$ punti e serve a normalizzare, perché un cammino breve in un dataset piccolo non è uguale a uno breve in un dataset grande. Perché proprio questa analogia: un isolation tree divide i dati con soglie casuali come un albero di ricerca costruito inserendo i punti in ordine casuale, e arrivare a una foglia corrisponde a cercare un valore che non c'è. Controlli sui valori piccoli: $c(2)=2H(1)-\frac{2\cdot1}{2}=2-1=1$ (con due punti serve un solo split); $c(3)=2\big(1+\frac12\big)-\frac{2\cdot2}3=3-1{,}333=1{,}667$. La somma armonica $H(m)=\sum_{j=1}^m\frac1j$ cresce come $\ln m$ (Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →): quindi $c(n)\approx2\ln n$ cresce lentamente, e per questo con soli $256$ punti per albero il cammino medio è circa $10$, non $256$. L'esponente $-E/c(n)$ e la base $2$ servono a mettere lo score tra $0$ e $1$: $E=c(n)$ dà $2^{-1}=0{,}5$.

Costo. Ogni albero ha profondità al più $\lceil\log_2\psi\rceil$ (con $\psi$ punti nel campione, $\psi=256$ quindi $8$ livelli) e ogni livello tocca al più $\psi$ punti, quindi un albero costa $O(\psi\log\psi)$ e la foresta di $t$ alberi $O(t\,\psi\log\psi)$ (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →, Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →): non dipende dal numero $n$ di punti del dataset, a differenza dei metodi basati su distanze come il k-NN (Classificazione e k-nearest neighborsNella classificazione l'uscita $y$ è una categoria (con $C$ classi; $C=2$ è il caso binario). Il classificatore più semplice è il k-nearest neighbors: una nuova osservazione prende la classe più frequente (voto di maggioranza) tra i suoi $k$ vicini più prossimi nel training, con distanza euclidea $\sqrt{\sum(A_i-B_i)^2}$ o di Manhattan $\sum|A_i-B_i|$ (per la regressione si fa la media dei vicini). $k$ è un iperparametro: $k$ piccolo dà bordi frastagliati e overfitting, $k$ grande underfitting. È un metodo basato su istanze e «pigro» (nessun addestramento, costo alla predizione), sensibile a scala e feature irrilevanti e alla maledizione della dimensionalità; gli ingressi categorici si codificano con one-hot. Approfondimento: non nel programma di Telecomunicazioni.Classificazione e k-nearest neighbors →), che costano $O(n^2)$ per confrontare tutte le coppie. La profondità $\log_2\psi$ è quella di un albero binario bilanciato con $\psi$ foglie (Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →).

Esempio. Con $n=256$: $c(256)=2H(255)-\frac{2\cdot255}{256}=12{,}241-1{,}992=10{,}25$. Se un punto ha cammino medio $E=10{,}25=c(n)$ (cioè «medio»), $s=2^{-1}=0{,}5$. Per $E=4$: $s=2^{-4/10{,}25}=0{,}763$ (quasi anomalo); per $E=10$: $0{,}508$; per $E=12$: $0{,}444$. In generale: $s\to1$ se $E\to0$ (isolato subito: anomalia certa), $s\approx0{,}5$ se $E\approx c(n)$ (punto «normale»), $s\to0$ se $E$ è molto maggiore di $c(n)$ (in zone molto dense).

6. Soglia. Un punto è dichiarato anomalo se $s>\tau$. Un modo per ricavare $\tau$ è la contaminazione: una proporzione (tra $0$ e $0{,}5$, di solito) che indica la frazione attesa di outlier nel dataset. La soglia è il percentile $1-\text{contaminazione}$ degli score di training: con contaminazione $0{,}01$ il $1\%$ dei punti con score più alto è dichiarato anomalo. La contaminazione è una manopola tra falsi positivi (punti normali dichiarati anomali) e falsi negativi (anomalie non segnalate).

Esempio (verificato con un'implementazione da zero). $200$ punti gaussiani standard in 2D più $5$ punti molto lontani ($(5,5)$, $(-6,4)$, $(6,-5)$, $(0,7)$, $(-5,-6)$). Con $100$ alberi e profondità massima $8$ i cammini medi dei cinque punti iniettati valgono tra $2{,}9$ e $4{,}6$ (contro $13$ per il punto mediano), e i loro score $0{,}72$-$0{,}82$ superano quello di ogni punto normale (massimo $0{,}615$, mediana $0{,}40$): i cinque punti sono i primi cinque nella classifica.

Correzione della profondità. Se si ferma un albero alla profondità massima con più punti nel nodo, la profondità si corregge sommando $c(\text{numero di punti nel nodo})$: $d\leftarrow d+c(n_{\text{nodo}})$. Il nodo con un solo punto ha $c(1)=0$. (Nel notebook, per comodità, $H(m)$ è approssimata con $\ln m+\gamma$, $\gamma=0{,}5772$: per $n=256$ dà $10{,}245$ invece di $10{,}249$, per piccoli $n$ è meno precisa: $c(3)=1{,}667$ esatta e $1{,}207$ approssimata, e per $n=2$ si pone $c=1$.)

Esempi e limiti

Nel laboratorio, sul dataset delle abitazioni della California con due variabili (MedInc, AveRooms), la foresta da zero segnala i punti con valori estremi. Per valutare senza etichette si possono iniettare anomalie sintetiche (per esempio punti a $+7\sigma$ e $+10\sigma$ dalla media) e vedere se vengono trovate. Un limite («bias» dell'isolation forest): lo score può essere incoerente con i dati, perché gli split casuali paralleli agli assi lasciano zone vuote, anche lontane dai cluster, con score basso (cioè «normali»), dove un punto anomalo non verrebbe rilevato. Nelle prove d'esame è stata proposta una variante «meno casuale» (per esempio non riusare una feature già usata nel ramo): non ci si aspetta che migliori, perché la casualità è un punto di forza dell'algoritmo.

Altri approcci

• PCA non è adatta al rilevamento di anomalie: cerca le direzioni di massima varianza assumendo che lì stia l'informazione, ma le anomalie sono rare e contribuiscono poco alla varianza, quindi la PCA tende a ignorarle (Analisi delle componenti principali (PCA)Con $p>3$ variabili non si può disegnare il dataset. La PCA (analisi delle componenti principali) lo proietta su pochi assi ortogonali, le componenti principali: dopo aver centrato (e di solito standardizzato) i dati, le direzioni sono gli autovettori della matrice di covarianza $S=\frac1{n-1}X_c^TX_c$ ordinati per autovalore $\lambda_1\ge\lambda_2\ge\dots$; $\lambda_k$ è la varianza lungo la componente $k$ e $\lambda_k/\sum\lambda_j$ la frazione spiegata (scree plot). Trovare la retta che minimizza le distanze dai punti equivale a massimizzare la varianza delle proiezioni (Pitagora). È lineare e conserva la struttura globale, non quella locale; t-SNE e UMAP sono alternative non lineari solo per visualizzare. Approfondimento: non nel programma di Telecomunicazioni.Analisi delle componenti principali (PCA) →). Esiste una variante, la PCA con sovracampionamento (osPCA): le direzioni principali rappresentano gli attributi «normali» e un outlier cambia la direzione delle componenti; per renderlo evidente si ripete il campione molte volte.
• Spiegare lo score. L'anomaly score avverte di una situazione potenzialmente anomala, ma tocca all'utente scoprire la causa: per l'analisi delle cause serve un'informazione aggiuntiva, come un ordinamento delle variabili. DIFFI (Depth-based Isolation Forest Feature Importance) è un metodo di intelligenza artificiale spiegabile (Explainable AI (XAI)approfondimento: non nel programma di Telecomunicazioni. L'interpretabilità è l'arte di produrre descrizioni di un modello abbastanza semplici da essere capite da un umano; la spiegabilità aggiunge la completezza (permettere di anticipare la previsione). I metodi si classificano in intrinseci o post-hoc, agnostici o specifici del modello, globali o locali. Modelli intrinsecamente interpretabili: regressione lineare (pesi $\beta_j$, intervalli di confidenza, LASSO per la sparsità), regressione logistica ($\log\frac y{1-y}=\beta_0+\sum\beta_jx_j$), alberi. Importanza nelle foreste: MDI $=\sum_{\text{nodi}}\frac{n_p}{n_{TOT}}\Delta Gini$ (con feature selection bias). Metodi agnostici: permutation importance (aumento dell'errore dopo aver mescolato una feature), PDP $\hat f_S(x_S)=\frac1n\sum_if(x_S,x_C^{(i)})$ (media delle curve ICE), LIME (modello semplice locale pesato sui punti perturbati), SHAP (valori di Shapley: media dei contributi marginali su tutti gli ordini, somma $=f(x)-f(\text{base})$). Per le reti profonde: mappe di salienza, Grad-CAM, occlusione. Valutazione: livello applicativo, umano, funzionale. Lab: cardiopatia AHD con logistica, LASSO, random forest, ICE, PDP, SHAP.Explainable AI (XAI) →) per l'isolation forest: una feature è «importante» se isola gli outlier a piccola profondità (vicino alla radice) e allo stesso tempo non contribuisce all'isolamento degli inlier; dà un ordinamento globale (variabili importanti per tutto il modello) e locale (per una singola previsione), non richiede etichette, ha basso costo e non richiede regolazioni.
• Carte di controllo contro anomaly score. Le informazioni, per consentire decisioni, devono essere complete, concise e interpretabili.

Valutare un sistema non supervisionato

È il vero svantaggio dei metodi non supervisionati: senza etichette, valutare è difficile. Se non si hanno etichette si cercano etichette approssimate: (i) chiedere a esperti di dominio di rivedere le prime $N$ anomalie segnalate: hanno senso? (ii) usare eventi noti (guasti, allarmi, anomalie nei log) come etichette parziali; (iii) iniezione sintetica: aggiungere anomalie note (rumore, punti fuori distribuzione) e controllare se il modello le trova.

Codice

import numpy as np
from scipy.stats import chi2

class HotellingT2:
    def __init__(self, alpha=0.05): self.alpha = alpha
    def fit(self, X):
        self.mean = X.mean(axis=0)
        self.inv_cov = np.linalg.inv(np.cov(X, rowvar=False))
    def t2(self, X):
        d = X - self.mean
        return np.einsum("ij,jk,ik->i", d, self.inv_cov, d)       # (x-m)^T S^-1 (x-m) per riga
    def predict(self, X):
        return self.t2(X) > chi2.ppf(1 - self.alpha, df=X.shape[1])   # True = anomalo

# isolation forest: from sklearn.ensemble import IsolationForest; IsolationForest(contamination=0.01).fit(X)
# nel laboratorio e nell'esame lo si implementa da zero (albero con split casuali, c(n), soglia a percentile)

Errori tipici

• Togliere gli outlier per migliorare le metriche, o togliere proprio ciò che si vuole trovare.
• Applicare le carte di controllo variabile per variabile e credere di coprire le anomalie multivariate.
• Usare $T^2$ con soglia chi-quadro su dati non gaussiani o multimodali.
• Dimenticare di normalizzare con $c(n)$: il numero di campioni cambia la scala dei cammini.
• Scambiare il verso: score alto (cammino corto) = anomalia.
• Interpretare la contaminazione come una proprietà dei dati noti: è una scelta che regola il compromesso tra falsi positivi e falsi negativi.