Dimensjonsreduksjon og anomalideteksjon

Et datasett med høyde og vekt kan tegnes på et ark. Med 300 sensormålinger per maskin går ikke det, og problemet er større enn at vi ikke kan tegne. Dimensjonalitetens forbannelse er en samlebetegnelse for det som skjer når antall dimensjoner $d$ vokser mens antall punkter står stille.

Volumet vokser eksponentielt. Del hver akse i ti intervaller: i 2D gir det 100 celler, i 10D ti milliarder. Med noen tusen punkter er nesten alle cellene tomme. Dataene blir glisne, og et «lokalt» nabolag må dekke store deler av rommet for å inneholde noen naboer. Samtidig havner nesten alt volum nær kantene: i en enhetskube ligger bare andelen $0,9^d$ av volumet i den indre kuben med sidelengde $0,9$, og den andelen går mot null når $d$ vokser.

Den mest praktiske konsekvensen gjelder avstander. Når $d$ er stor, blir avstanden fra et punkt til den nærmeste naboen nesten like stor som avstanden til den fjerneste. Metoder som bygger på at «nær betyr lik», som k-means, DBSCAN og nærmeste nabo, mister da mye av signalet sitt. Flere features er altså ikke det samme som mer nyttig informasjon: mange av dem kan være støy eller måle nesten det samme.

Dimensjonsreduksjon lager en representasjon med færre koordinater som bevarer strukturen vi bryr oss om, for eksempel varians (PCA) eller lokale naboskap (t-SNE). Til forskjell fra featurevalg, som beholder noen av de opprinnelige featurene, lager den nye akser som kombinerer mange.

import numpy as np
import matplotlib.pyplot as plt

n = 500  # antall punkter
d = 1000  # @param 1..5000

def kontrast(dim):
    rng = np.random.default_rng(dim)
    X = rng.random((n, dim))               # punkter jevnt fordelt i enhetskuben
    q = rng.random(dim)                    # et spørrepunkt
    avstand = np.linalg.norm(X - q, axis=1)
    return avstand.min(), avstand.max(), (avstand.max() - avstand.min()) / avstand.min()

for dim in sorted({2, d}):                 # d = 2 står med som referanse
    lav, hoy, k = kontrast(dim)
    print(f"d = {dim:4d}: nærmeste {lav:5.2f}, fjerneste {hoy:5.2f}, relativ kontrast {k:6.2f}")

dims = [2, 5, 10, 30, 100, 300, 1000, 3000, 5000]
plt.figure()
plt.loglog(dims, [kontrast(m)[2] for m in dims], marker="o", label="relativ kontrast")
plt.scatter([d], [kontrast(d)[2]], color="C1", zorder=3, label=f"d = {d}")
plt.xlabel("Dimensjon d")
plt.ylabel("Relativ kontrast")
plt.legend()
plt.tight_layout()
plt.show()

PCA (prinsipalkomponentanalyse) finner nye, ortogonale akser sortert etter hvor mye varians dataene har langs dem. Tenk deg en avlang punktsky og en pinne gjennom midten. Projiser hvert punkt ned på pinnen og se hvor spredt skyggene blir. Retningen der skyggene sprer seg mest, er første hovedkomponent, og den bevarer mest av informasjonen om hvor punktene ligger i forhold til hverandre.

Oppskriften har fire steg:

1. 1.Sentrer ved å trekke gjennomsnittet fra hver feature (ƒsentrering). Da roterer vi rundt datasettets sentrum og ikke rundt et tilfeldig origo.
2. 2.Regn ut kovariansmatrisen (ƒkovariansmatrise). Diagonalen er variansen til hver feature, og elementene utenfor diagonalen sier hvordan featurepar varierer sammen.
3. 3.Finn egenvektorene (ƒegenvektorligning). Hver egenvektor $v_j$ av $S$ er en komponentretning, og egenverdien ${\lambda }_j$ er variansen langs den. Sorter etter synkende $\lambda$.
4. 4.Projiser på de $k$ første retningene (neste steg).

Den første hovedkomponent er retningen med størst varians. Den andre er retningen med størst gjenværende varians blant dem som står vinkelrett på den første, og så videre. Fordi kovariansmatrisen er symmetrisk, er egenvektorene ortogonale, og det har en viktig konsekvens: koordinatene langs ulike hovedkomponenter er ukorrelerte. Hver komponent bærer informasjon som de andre ikke allerede har, uten overlapp. Derfor er PCA nyttig når mange features måler nesten det samme: høyde, skrittlengde og armlengde kan smelte sammen til én «størrelse»-komponent.

Fortegnet til en egenvektor er vilkårlig. $v$ og $-v$ beskriver samme akse, så to programmer kan gi motsatte fortegn uten å være uenige.

Når komponentene er sortert, må vi velge hvor mange vi beholder. Forklart varians sier hvor stor andel av den totale variansen en komponent fanger (ƒforklart variansandel): egenverdien delt på summen av alle egenverdiene. Andelene summerer til 1, og den kumulative andelen for de $k$ første er summen av deres andeler (ƒkumulativ forklart varians).

Et scree-plott viser andelen per komponent. Typisk faller kurven bratt for de første komponentene og flater så ut. To vanlige regler er å beholde komponentene før kurven flater ut, omtrent som albuen i k-means, eller å beholde den minste $k$ som gir for eksempel 90 % kumulativ forklart varians.

Selve projeksjonen er en matrisemultiplikasjon (ƒPCA-projeksjon): $Z=X_c{W}_k$, der kolonnene i $W_k$ er de $k$ første egenvektorene. Hver rad i $Z$ er punktets nye koordinater. Fordi $W_k$ læres én gang, kan nye punkter projiseres med den samme matrisen, og det er dette transform gjør i scikit-learn. Lærer vi middelverdi og komponenter bare fra treningsdata, unngår vi lekkasje.

To forbehold er viktige. PCA er variansbasert, så skala betyr mye: en lengde målt i millimeter får hundre ganger så stor varians som den samme lengden målt i centimeter og tar over PC1. Standardiser derfor når featurene har ulike enheter. Og PCA er uveiledet: høy varians er ikke det samme som nyttig for en senere klassifikasjon, og en retning med lite varians kan være akkurat den som skiller klassene.

PCA er lineær: den kan bare rotere og kutte bort akser. Ligger dataene på en buet flate, kan PCA legge punkter som er langt fra hverandre i originalrommet oppå hverandre. T-SNE er en ikke-lineær metode laget for én ting: visualisering i to eller tre dimensjoner, der punkter som er naboer i originalrommet også skal være naboer i kartet.

Metoden gjør avstander om til sannsynligheter. I originalrommet får hvert par $(i,j)$ en likhet $P_{ij}$ som er stor når punktene er nære og nesten null ellers. I kartet defineres en tilsvarende $Q_{ij}$ med en t-fordeling, som har tyngre haler. Så flytter t-SNE punktene i kartet for å minimere KL-divergensen (ƒKL-divergens):

KL-divergensen er asymmetrisk. Et par med stor $P_{ij}$ og liten $Q_{ij}$, altså nære naboer som havner langt fra hverandre, koster mye. Et par med liten $P_{ij}$ koster lite uansett hvor det havner. Derfor bevarer t-SNE lokale naboskap godt, mens globale avstander er nesten ubestemte.

Tre konsekvenser er viktige. For det første optimaliseres koordinatene til de konkrete punktene direkte. Det læres ingen funksjon fra originalrommet til kartet, så det finnes ingen transform for nye punkter: nye data krever en ny kjøring. For det andre styrer perplexity omtrent hvor mange naboer hvert punkt tar hensyn til, typisk 5 til 50. Lav perplexity gir mange småklynger, høy visker ut lokale detaljer. For det tredje er optimaliseringen tilfeldig, så ulike frø gir ulike kart. Resultatet er en embedding som skal leses for lokale grupper, ikke for avstander mellom klynger, klyngestørrelser eller aksenes retning.

I praksis brukes PCA og t-SNE ofte sammen. PCA er rask, deterministisk og har transform, så den egner seg til å komprimere data før en modell. t-SNE er tregere og egner seg bare til å se på data. Et vanlig oppsett er å redusere til rundt 50 dimensjoner med PCA for å fjerne støy og spare tid, og så kjøre t-SNE på resultatet for å lage kartet.

Anomalideteksjon handler om å finne observasjoner som avviker fra det normale mønsteret: en sensor som plutselig viser feil, en transaksjon som ikke ligner kundens vanlige, en server med uvanlig trafikk. Ofte har vi ingen eller svært få merkede avvik, så metodene er gjerne uveiledede. De lærer hva som er normalt og gir hvert punkt en score for hvor unormalt det er.

En terskel gjør scoren om til flagg, og da oppstår de samme feiltypene som i klassifikasjon. En falsk positiv er et normalt punkt som blir flagget. Fordi normale punkter er i stort flertall, kan selv en lav andel falske positive gi langt flere falske alarmer enn ekte avvik, og hver alarm koster en manuell sjekk. Terskelen, i scikit-learn ofte satt via contamination, må derfor velges ut fra hva et oversett avvik og en falsk alarm koster.

Isolation Forest bygger på en enkel observasjon: avvik er få og annerledes, og derfor lette å isolere. Et isolasjonstre velger en tilfeldig feature og en tilfeldig splittverdi mellom minimum og maksimum, og deler dataene. Slik fortsetter det til hvert punkt står alene. Et punkt langt ute fra resten havner ofte alene etter bare et par splitter, mens et punkt midt i en tett gruppe trenger mange. Stilengden $h(x)$, antall splitter fra roten til punktet, er altså kort for avvik.

Ett tilfeldig tre er støyete, så skogen bruker gjennomsnittlig stilengde $E[h(x)]$ over mange trær og gjør den om til en score (ƒIsolation Forest-score). Normaliseringen $c(n)$ (ƒnormalisering i Isolation Forest) er forventet stilengde for et vanlig punkt i et utvalg på $n$, slik at scoren kan sammenlignes på tvers av utvalgsstørrelser. Kort sti gir $s$ nær 1 (sannsynlig avvik), mens en stilengde rundt $c(n)$ gir $s\approx 0,5$ (normalt). Scoren er en rangering, ikke en kalibrert sannsynlighet for avvik.

Isolation Forest er ikke den eneste veien. DBSCAN-støy og stor rekonstruksjonsfeil etter PCA kan også brukes som avviksmål, men metodene stiller ulike spørsmål. DBSCAN spør om punktet mangler tette naboer innen $\epsilon$, PCA spør om punktet passer dårlig med de vanlige variasjonsretningene, og Isolation Forest spør hvor lett punktet skilles ut med tilfeldige splitter. Derfor kan de flagge ulike punkter.