Technische Samenvatting: Randomized PCA Forest voor Ongesuperviseerde Buitengewone Detectie

Probleemstelling

Buitengewone detectie is een fundamentele taak in data mining en machine learning, van cruciaal belang voor toepassingen zoals inbraakdetectie, storingsdiagnose en fraudeopsporing. Ondanks de proliferatie van nieuwe algoritmen geven uitgebreide evaluaties aan dat klassieke methoden zoals K-Nearest Neighbor (KNN) en Local Outlier Factor (LOF) vaak nog steeds de state-of-the-art vertegenwoordigen. Deze methoden adresseren effectief uitdagingen zoals onnauwkeurige grenzen tussen normale en abnormale data en de aanwezigheid van ruis, maar lijden onder een hoge computationele complexiteit vanwege de noodzaak van exacte zoekopdrachten naar de dichtstbijzijnde buren. Hoewel boomgebaseerde methoden zoals Isolation Forest (iForest) efficiëntie bieden, vertrouwen ze op willekeurige feature-selectie, wat niet altijd de onderliggende structuur van hoog-dimensionale data effectief kan vastleggen. Er is behoefte aan een methode die computationele efficiëntie afweegt tegen robuustheid, waarbij dimensiereductie wordt benut zonder het vermogen om zowel globale als lokale buitengewone waarden te detecteren, in te leveren.

Methodologie

De auteurs stellen een nieuwe ongesuperviseerde methode voor buitengewone detectie voor, gebaseerd op Randomized Principal Component Analysis (RPCA) Forests. De aanpak past de RPCA Forest, oorspronkelijk ontworpen voor benaderde K-Nearest Neighbor (KNN)-zoekopdrachten, aan voor buitengewone detectie door een specifieke buitengewone score af te leiden uit de intrinsieke eigenschappen van de forest.

Kerncomponenten

1. Constructie van RPCA Forest:

   • De methode bouwt een ensemble van bomen op. In tegenstelling tot iForest, dat willekeurig features selecteert, maken RPCA Forests gebruik van Randomized PCA (Halko et al., 2011) op elk knooppunt.
   • Op de root en daaropvolgende knooppunten worden datapunten geprojecteerd naar een lager-dimensionale deelruimte met behulp van een klein aantal hoofdcomponenten ($p$). Dit behoudt de informatiewaarde van de oorspronkelijke feature-ruimte terwijl de dimensionaliteit wordt gereduceerd.
   • Splitsingscriterium: In plaats van willekeurige snijlijnen, steekt het algoritme splitsingspunten voor elke hoofdcomponent uit een Laplace-verdeling die gecentreerd is rond het gemiddelde. Datapunten worden toegewezen aan linker- of rechterkinderen op basis van een meerderheidsstem over de $p$ componenten.
   • Stopcriterium: De groei van de boom gaat door totdat de bladerknooppunten een aantal punten bevatten dat kleiner is dan of gelijk is aan een vooraf gedefinieerde omgevingsgrootte ($k$).

2. Formulering van Buitengewone Score:
   De voorgestelde methode definieert een buitengewone score ($RPCAForestScore$) voor een query-punt $q$ door twee onderscheiden criteria te combineren:

   • Op diepte gebaseerde buitengewoonheid ($P(q)$): Gebaseerd op de observatie dat buitengewone waarden vaak eerder in de boom worden geïsoleerd (on dieper diepte). Dit wordt berekend als de genormaliseerde inverse diepte van het bladerknooppunt dat $q$ bevat, over de forest heen.
   • Op afstand gebaseerde buitengewoonheid ($\mu_{dist}(q)$): Berekend als de gemiddelde Euclidische afstand tussen het query-punt $q$ en alle andere punten binnen hetzelfde bladerknooppunt in de oorspronkelijke feature-ruimte.
   • Eindscore: De eindscore is het product van deze twee componenten:
     $$RPCAForestScore(q) = P(q) \times \mu_{dist}(q)$$
     Deze combinatie zorgt ervoor dat zelfs als een buitengewone waarde in een blad wordt gegroepeerd met inliers (vanwege de projectie), de grote afstand tot het clustercentrum in de oorspronkelijke ruimte resulteert in een hoge anomalie-score.

3. Classificatie:
   Een drempelwaarde voor buitengewone waarden wordt bepaald met behulp van een contaminatieparameter ($\alpha$), die het verwachte percentage buitengewone waarden vertegenwoordigt. Punten met scores die de $(1-\alpha)$-quantiel van de scoreverdeling overschrijden, worden gelabeld als buitengewone waarden.

Belangrijkste Bijdragen

• Nieuwe Integratie: Het artikel introduceert de eerste toepassing van RPCA Forests specifiek voor ongesuperviseerde buitengewone detectie, waardoor de kloof wordt overbrugd tussen benaderde zoekopdrachten naar de dichtstbijzijnde buren en anomaliedetectie.
• Hybride Scoremechanisme: Het stelt een samengestelde buitengewone score voor die zowel de structurele isolatiediepte (vergelijkbaar met iForest) als de lokale dichtheid/afstand in de oorspronkelijke feature-ruimte (vergelijkbaar met KNN/LOF) benut, met als doel de beperkingen van het gebruik van slechts één van deze metrieken te overwinnen.
• Efficiëntie via Randomized PCA: Door gebruik te maken van random SVD bereikt de methode hoge computationele efficiëntie, met name voor hoog-dimensionale data, aangezien de complexiteit afhangt van het aantal hoofdcomponenten in plaats van de volledige data-dimensionaliteit.
• Robuustheid: De methode is ontworpen om robuust te zijn tegen hyperparameter-tuning, waarbij alleen de selectie van het aantal bomen, hoofdcomponenten ($p$) en bladgrootte ($k$) vereist is.

Experimentele Resultaten

De auteurs evalueerden de methode op 22 diverse datasets uit een standaard benchmark-repository, waarbij ze deze vergeleken met klassieke en state-of-the-art methoden, waaronder KNN, KNNW, LOF, SLOF, ODIN, DAO en iForest. Prestaties werden gemeten met behulp van het Oppervlak Onder de Receiver Operating Characteristic Curve (AUC).

• Prestaties: De RPCA Forest vertoonde op veel datasets superieure of tweede beste prestaties en bleef op andere concurrerend. Het toonde een bijzonder sterke prestatie op hoog-dimensionale datasets waar iForest (dat willekeurige feature-selectie gebruikt) moeite had.
• Robuustheid: De methode behield concurrerende prestaties met slechts twee instellingen voor het aantal hoofdcomponenten ($p=1$ en $p=5$), terwijl concurrerende methoden werden getest met 100 verschillende hyperparameter-configuraties. Dit suggereert dat de voorgestelde methode minder gevoelig is voor hyperparameter-tuning.
• Ablatie-studie: Experimenten waarbij de op diepte gebaseerde en op afstand gebaseerde componenten werden gescheiden, onthulden dat de gecombineerde score significant beter presteerde dan de op diepte gebaseerde component en over het algemeen concurrerend was met of superieur aan de op afstand gebaseerde component alleen.
• Efficiëntie: Hoewel iForest de snelste methode bleef, vertoonde RPCA Forest aanzienlijk betere schaalbaarheid dan op KNN gebaseerde methoden naarmate de dataset-grootte toenam, met behoud van efficiënte looptijden die geschikt zijn voor big data.
• Waargenomen Beperkingen: De methode vertoonde lagere prestaties op specifieke datasets (bijv. ALOI, InternetAds, Annthyroid, Wilt). De auteurs schrijven dit toe aan:
  • Hoge dimensionaliteit waarbij weinig hoofdcomponenten ($p=1, 5$) onvoldoende waren om buitengewone waarden te isoleren (InternetAds).
  • Buitengewone waarden die zeer vergelijkbaar waren met inliers, waardoor meer informatie nodig was dan de geselecteerde $p$ kon bieden (Annthyroid, Wilt).
  • De aard van lokale versus globale buitengewone waarden in datasets met specifieke feature-extractie (ALOI), waarbij methoden voor lokale structuur (LOF) beter presteerden dan de globale projectie-aanpak.

Betekenis en Claims

Het artikel claimt dat de RPCA Forest een robuust en computationeel efficiënt alternatief biedt voor ongesuperviseerde buitengewone detectie. De betekenis ervan ligt in het vermogen om:

1. Efficiëntie en Nauwkeurigheid in Evenwicht te Brengen: Het biedt een "whitebox"-benadering voor benaderde omgevingszoekopdrachten die de interne structuur van de boom benut (via PCA-projecties) in plaats van de zoekopdracht als een black box te behandelen.
2. Goed te Generaliseren: De methode presteert concurrerend over een breed scala aan datasets zonder de noodzaak van exhaustieve hyperparameter-optimalisatie, waarmee het de kwestie aanpakt waarbij veel nieuwe methoden alleen uitblinken op specifieke probleeminstanties.
3. Zowel Globale als Lokale Buitengewone Waarden te Detecteren: Theoretisch is de methode ontworpen om globale buitengewone waarden te detecteren (via vroege isolatie in de boom) en lokale buitengewone waarden (via afstands-metrieken in diepere knooppunten), hoewel de auteurs beperkingen erkennen met betrekking tot geclusterde anomalieën.

De auteurs concluderen dat hoewel de methode geen universele oplossing is voor alle typen buitengewone waarden (met name geclusterde anomalieën), het een sterke keuze vertegenwoordigt voor buitengewone detectie voor algemeen gebruik, met een gunstige afweging tussen de computationele snelheid van boomgebaseerde methoden en de nauwkeurigheid van op afstand gebaseerde methoden.