Isoleringsskog - Isolation forest

Isolationsskogen är den första avvikelsedetekteringsalgoritmen som identifierar avvikelser med hjälp av isolering. Den föreslogs och utvecklades ursprungligen av Fei Tony Liu, Kai Ming Ting och Zhi-Hua Zhou 2008. Betydelsen av denna forskning ligger i dess avvikelse från den vanliga filosofin som ligger till grund för befintliga anomaliedetektorer vid den tiden, där normala fall profileras före avvikelser identifieras som instanser som inte överensstämmer. Isolation forest introducerar en fundamentalt annorlunda metod som uttryckligen isolerar avvikelser med hjälp av binära träd, vilket visar den nya möjligheten för en snabb anomaliedetektor som direkt riktar anomalier utan den resurskrävande processen med normal instansprofilering. Algoritmen har en linjär tidskomplexitet med en låg konstant och ett lågt minneskrav, vilket fungerar bra i högdimensionella problem som har ett stort antal irrelevanta attribut och i situationer där träningsuppsättningen inte innehåller några avvikelser.

Fig. 1 - exempel på webbtrafik med potentiellt avvikande punkter.

I statistik är en anomali (aka outlier ) en observation eller händelse som avviker så mycket från andra händelser för att väcka misstänksamhet att den genererades av ett annat medel. Till exempel representerar grafen i figur 1 inträngningstrafik till en webbserver, uttryckt som antalet förfrågningar i 3-timmarsintervall, under en period av en månad. Det är helt uppenbart genom att helt enkelt titta på bilden att vissa punkter (markerade med en röd cirkel) är ovanligt höga, så att de misstänker att webbservern kan ha varit under attack vid den tiden. Å andra sidan verkar det platta segmentet som indikeras av den röda pilen också ovanligt och kan möjligen vara ett tecken på att servern var nere under den tidsperioden.

Anomalier i en stor datamängd kan följa mycket komplicerade mönster, som är svåra att upptäcka visuellt i de allra flesta fall. Detta är anledningen till att området för avvikelse av avvikelse är väl lämpad för tillämpning av maskininlärningstekniker .

De vanligaste teknikerna som används för detektering av avvikelser är baserade på konstruktionen av en profil av vad som är "normalt": avvikelser rapporteras som de instanser i datamängden som inte överensstämmer med den normala profilen. Isolation Forest använder ett annat tillvägagångssätt: istället för att försöka bygga en modell av normala instanser, isolerar det uttryckligen avvikande punkter i datamängden. Den största fördelen med detta tillvägagångssätt är möjligheten att utnyttja provtagningstekniker i en utsträckning som inte är tillåten för de profilbaserade metoderna, vilket skapar en mycket snabb algoritm med lågt minnesbehov.

Historia

Algoritmen Isolation Forest (iForest) föreslogs ursprungligen av Fei Tony Liu, Kai Ming Ting och Zhi-Hua Zhou 2008. Författarna utnyttjade två kvantitativa egenskaper hos avvikande datapunkter i ett urval:

Få - de är minoriteten som består av färre instanser och
Olika - de har attributvärden som skiljer sig mycket från normala instanser

Eftersom avvikelser är "få och olika" är de lättare att "isolera" jämfört med normala punkter. Isolation Forest bygger en ensemble av "Isolation Trees" (iTrees) för datamängden, och avvikelser är de punkter som har kortare genomsnittlig väglängd på iTrees.

I ett senare papper, publicerat 2012, beskrev samma författare en uppsättning experiment för att bevisa att iForest:

har en låg linjär tidskomplexitet och ett litet minneskrav
kan hantera högdimensionella data med irrelevanta attribut
kan tränas med eller utan avvikelser i träningsuppsättningen
kan ge detekteringsresultat med olika nivåer av granularitet utan omträning

År 2013 föreslog Zhiguo Ding och Minrui Fei ett ramverk baserat på iForest för att lösa problemet med att upptäcka avvikelser i strömmande data. Mer tillämpning av iForest för strömmande data beskrivs i artiklar av Tan et al., Susto et al. och Weng et al.

Ett av huvudproblemen med tillämpningen av iForest för avvikelsedetektering var inte med själva modellen, utan snarare på det sätt som "anomali poängen" beräknades. Detta problem belystes av Sahand Hariri, Matias Carrasco Kind och Robert J. Brunner i ett 2018 -papper, där de föreslog en förbättrad iForest -modell med namnet Extended Isolation Forest (EIF). I samma uppsats beskriver författarna de förbättringar som gjorts av den ursprungliga modellen och hur de kan förbättra konsistensen och tillförlitligheten hos avvikelsepoängen som produceras för en given datapunkt.

Algoritm

Fig. 2 - ett exempel på isolering av en icke -avvikande punkt i en 2D -gaussisk fördelning.

På grundval av Isolation Forest -algoritmen finns det en tendens att avvikande instanser i en datamängd är lättare att skilja från resten av urvalet (isolera), jämfört med normala punkter. För att isolera en datapunkt genererar algoritmen rekursivt partitioner i urvalet genom att slumpmässigt välja ett attribut och sedan slumpmässigt välja ett delat värde för attributet, mellan de lägsta och högsta tillåtna värdena för det attributet.

Fig. 3 - ett exempel på isolering av en avvikande punkt i en 2D -Gauss -fördelning.

Ett exempel på slumpmässig uppdelning i en 2D-dataset med normalt fördelade punkter ges i fig. 2 för en icke-avvikande punkt och fig. 3 för en punkt som mer sannolikt är en anomali. Det framgår av bilderna hur avvikelser kräver att färre slumpmässiga partitioner isoleras jämfört med normala punkter.

Ur matematisk synvinkel kan rekursiv partitionering representeras av en trädstruktur som heter Isolation Tree , medan antalet partitioner som krävs för att isolera en punkt kan tolkas som längden på banan, inom trädet, för att nå en avslutande nod som startar från roten. Till exempel är banlängden för punkten i Fig. 2 större än banlängden i Fig. 3. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {j}}$

Mer formellt, låt vara en uppsättning d-dimensionella punkter och . Ett isoleringsträd (iTree) definieras som en datastruktur med följande egenskaper: ${\ displaystyle X = \ {x_ {1}, \ dots, x_ {n} \}}$ ${\ displaystyle X '\ delmängd X}$

för varje nod i trädet är antingen en extern nod utan barn eller en intern nod med ett "test" och exakt två dotternoder ( och ) ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$
ett test vid noden består av ett attribut och ett delat värde så att testet bestämmer genomgången av en datapunkt till antingen eller . ${\ displaystyle T}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle q <p}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$

För att bygga ett iTree delar algoritmen rekursivt genom att slumpmässigt välja ett attribut och ett delat värde , tills antingen ${\ displaystyle X '}$ ${\ displaystyle q}$ ${\ displaystyle p}$

noden har bara en instans, eller
all data vid noden har samma värden.

När iTree är fullväxt isoleras varje punkt i i en av de externa noder. Intuitivt, de avvikande punkter är sådana (lättare att isolat, därav) med den mindre våglängden i trädet, där banlängden av punkt definieras som antalet kanter polygontåg från rotnoden för att komma till en extern nod. ${\ displaystyle X}$ ${\ displaystyle h (x_ {i})}$ ${\ displaystyle x_ {i} \ i X}$ ${\ displaystyle x_ {i}}$

En sannolikhetsförklaring av iTree finns i iForest originalpapper.

Egenskaper för isoleringsskog

Sub-sampling : eftersom iForest behöver inte isolera alla normala fall kan det ofta ignorera den stora majoriteten av träningsprovet. Som en konsekvens fungerar iForest mycket bra när provtagningsstorleken hålls liten, en egenskap som står i kontrast till de flesta befintliga metoder, där stor provtagningsstorlek vanligtvis är önskvärd.
Träsk : När normala fall är för nära avvikelser ökar antalet partitioner som krävs för att separera avvikelser, ett fenomen som kallas träskning , vilket gör det svårare för iForest att skilja mellan avvikelser och normala punkter. En av de främsta orsakerna till översvämning är närvaron av för många data för avvikelsedetektering, vilket innebär en möjlig lösning på problemet är delprovtagning. Eftersom iForest reagerar mycket bra på delprovtagning när det gäller prestanda är minskningen av antalet poäng i urvalet också ett bra sätt att minska effekten av träsk.
Maskering : när antalet avvikelser är högt är det möjligt att några av dem samlas i ett tätt och stort kluster, vilket gör det svårare att skilja de enskilda avvikelserna och i sin tur att upptäcka sådana punkter som avvikande. På samma sätt som träsk är detta fenomen (känt som " maskering ") också mer troligt när antalet punkter i urvalet är stort och kan lindras genom delprovtagning.
Högdimensionella data : en av de största begränsningarna till standard, avståndsbaserade metoder är deras ineffektivitet i att hantera högdimensionella datamängder :. Huvudorsaken till det är att i ett högdimensionellt utrymme är varje punkt lika gles, så att använda ett distansbaserat mått på separation är ganska ineffektivt. Tyvärr påverkar högdimensionella data också iForests detekteringsprestanda, men prestandan kan förbättras avsevärt genom att lägga till ett funktionsteststest som Kurtosis för att minska provutrymmet.
Endast normala instanser: iForest presterar bra även om träningsuppsättningen inte innehåller någon avvikande punkt, anledningen är att iForest beskriver datafördelningar på ett sådant sätt att höga värden för banlängden motsvarar närvaron av datapunkter. Som en konsekvens är förekomsten av avvikelser ganska irrelevant för iForests upptäcktsprestanda. ${\ displaystyle h (x_ {i})}$

Avvikelsedetektering med isoleringsskog

Anomali -upptäckt med Isolation Forest är en process som består av två huvudsteg:

i det första steget används en utbildningsdataset för att bygga iTrees enligt beskrivningen i tidigare avsnitt.
i det andra steget passeras varje instans i testuppsättningen genom iTrees -byggnaden i föregående steg, och en korrekt "anomali poäng" tilldelas instansen med hjälp av algoritmen som beskrivs nedan

När alla instanser i testuppsättningen har tilldelats ett avvikelsepoäng, är det möjligt att markera som "anomali" varje punkt vars poäng är högre än ett fördefinierat tröskelvärde, vilket beror på den domän som analysen tillämpas på.

Anomali poäng

Algoritmen för att beräkna avvikelsepoängen för en datapunkt är baserad på observationen att strukturen för iTrees är ekvivalent med den för Binary Search Trees (BST): en avslutning till en extern nod av iTree motsvarar en misslyckad sökning i BST . Som en konsekvens är uppskattningen av genomsnittet för externa nodavslutningar densamma som för de misslyckade sökningarna i BST, det vill säga ${\ displaystyle h (x)}$

${\ displaystyle c (m) = {\ begin {cases} 2H (m-1)-{\ frac {2 (m-1)} {n}} & {\ text {för}} m> 2 \\ 1 & {\ text {för}} m = 2 \\ 0 & {\ text {annars}} \ slut {fall}}}$

var är testdatastorleken, är storleken på provuppsättningen och är det harmoniska antalet, som kan uppskattas med , var är Euler-Mascheroni-konstanten . ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle H}$ ${\ displaystyle H (i) = ln (i)+\ gamma}$ ${\ displaystyle \ gamma = 0.5772156649}$

Värdet av c (m) ovan representerar genomsnittet av givet , så vi kan använda det för att normalisera och få en uppskattning av anomali poängen för en given instans x: ${\ displaystyle h (x)}$ ${\ displaystyle m}$ ${\ displaystyle h (x)}$

${\ displaystyle s (x, m) = 2^{\ frac {-E (h (x))} {c (m)}}}$

var är medelvärdet av från en samling av iTrees. Det är intressant att notera att för en given instans : ${\ displaystyle E (h (x))}$ ${\ displaystyle h (x)}$ ${\ displaystyle x}$

om är nära då är det mycket troligt att det är en anomali ${\ displaystyle s}$ ${\ displaystyle 1}$ ${\ displaystyle x}$
om är mindre än då är det sannolikt ett normalvärde ${\ displaystyle s}$ ${\ displaystyle 0.5}$ ${\ displaystyle x}$
om för ett givet prov alla instanser tilldelas ett anomali -poäng på runt , är det säkert att anta att provet inte har någon anomali ${\ displaystyle 0.5}$

Utökad isoleringsskog

Såsom beskrivits i föregående avsnitt fungerar Isolation Forest -algoritmen mycket bra ur både beräkningssynpunkt och minnesförbrukningssynpunkt. Huvudproblemet med den ursprungliga algoritmen är att sättet att förgrena sig på träd introducerar en snedvridning, vilket sannolikt kommer att minska tillförlitligheten hos anomalipoängen för rangordning av data. Detta är den främsta motivationen bakom introduktionen av algoritmen Extended Isolation Forest (EIF) av Hariri et al.

Fig. 4 - tvådimensionella normalt fördelade punkter med nollmedelvärde och enhetskovariansmatris

För att förstå varför den ursprungliga Isolationsskogen lider av den förspänningen ger författarna ett praktiskt exempel baserat på en slumpmässig datamängd från en 2-D normalfördelning med noll medelvärde och kovarians som ges av identitetsmatrisen. Ett exempel på en sådan datamängd visas i figur 4.

Det är lätt att förstå genom att titta på bilden att punkter som faller nära (0, 0) sannolikt är normala punkter, medan en punkt som ligger långt ifrån (0, 0) sannolikt kommer att vara avvikande. Som en konsekvens bör anomalipoängen för en punkt öka med ett nästan cirkulärt och symmetriskt mönster när punkten rör sig radiellt utåt "mitten" av fördelningen. Detta är inte fallet i praktiken, vilket författarna visar genom att generera den anomali -poängkarta som produceras för distributionen av algoritmen Isolation Forest. Även om anomalipoängen korrekt ökar när punkterna rör sig radiellt utåt, genererar de också rektangulära områden med lägre anomali -poäng i x- och y -riktningarna, jämfört med andra punkter som faller ungefär på samma radiella avstånd från mitten.

Fig. 5 - slumpmässig uppdelning med EIF

Det är möjligt att visa att dessa oväntade rektangulära regioner i kartan över avvikelseskåran verkligen är en artefakt som introducerats av algoritmen och huvudsakligen beror på att beslutsgränserna för Isolation Forest är begränsade till antingen vertikala eller horisontella (se figur 2 och fig. 3).

Detta är anledningen till att Hariri et al. föreslår att förbättra den ursprungliga isoleringsskogen på följande sätt: i stället för att välja en slumpmässig funktion och värde inom dataområdet väljer de en grenavsnitt som har en slumpmässig "lutning". Ett exempel på slumpmässig uppdelning med EIF visas i fig. 5.

Författarna visar hur det nya tillvägagångssättet kan övervinna gränserna för den ursprungliga isolationsskogen, vilket så småningom leder till en förbättrad avvikelseskarta.

Open source -implementeringar

Ursprunglig implementering:

Isolering Forest , en algoritm som upptäcker uppgifter-anomalier använder binärträd skrivna i R . Släpptes av tidningens första författare Liu, Fei Tony 2009.

Andra implementeringar (i alfabetisk ordning):

EIF - En implementering av Extended Isolation Forest for Anomaly Detection av Sahand Hariri .
Extended Isolation Forest av H2O-3- En implementering av Extended Isolation Forest for Anomaly Detection av H2O-3.
Isolation Forest - En Spark/Scala -implementering, skapad av James Verbus från LinkedIn Anti -Abuse AI -team.
Isolation Forest av H2O-3- En implementering av Isolation Forest for Anomaly Detection av H2O-3.
Paket ensamhet implementering i R av Srikanth Komala Sheshachala .
Python-implementering med exempel i scikit-learn .
Spark iForest - En distribuerad implementering i Scala och Python, som körs på Apache Spark . Skrivet av Yang, Fangzhou .

Languages

In other projects