Izolační les - Isolation forest

Isolation forest je první algoritmus detekce anomálií, který identifikuje anomálie pomocí izolace. Původně byl navržen a vyvinut Fei Tony Liu, Kai Ming Ting a Zhi-Hua Zhou v roce 2008. Význam tohoto výzkumu spočívá v jeho odchylce od mainstreamové filozofie, která je základem existujících detektorů anomálií v té době, kde jsou normální instance profilovány před anomáliemi jsou identifikovány jako instance, které neodpovídají. Isolation forest zavádí zásadně odlišnou metodu, která explicitně izoluje anomálie pomocí binárních stromů, což ukazuje novou možnost rychlého detektoru anomálií, který přímo cílí na anomálie bez procesu náročného na zdroje normálního profilování instance. Algoritmus má lineární časovou složitost s nízkou konstantou a malým požadavkem na paměť, což funguje dobře u problémů s vysokými rozměry, které mají velký počet irelevantních atributů, a v situacích, kdy tréninková sada neobsahuje žádné anomálie.

Obr. 1 - příklad webového provozu s potenciálně neobvyklými body.

Ve statistikách je anomálie (aka outlier ) pozorování nebo událost, která se natolik odchyluje od ostatních událostí, aby vzbudila podezření, že byla generována jiným průměrem. Například graf na obr. 1 představuje příchozí provoz na webový server, vyjádřený jako počet požadavků ve 3hodinových intervalech, po dobu jednoho měsíce. Při pohledu na obrázek je zcela evidentní, že některé body (označené červeným kruhem) jsou neobvykle vysoké, což vyvolává podezření, že webový server mohl být v té době napaden. Na druhou stranu plochý segment označený červenou šipkou se také zdá neobvyklý a může to být známkou toho, že server byl v daném časovém období mimo provoz.

Anomálie ve velké datové sadě mohou mít velmi komplikované vzorce, které je ve velké většině případů obtížné vizuálně detekovat. To je důvod, proč se oblast detekce anomálií dobře hodí pro aplikaci technik strojového učení .

Nejběžnější techniky používané pro detekci anomálií jsou založeny na konstrukci profilu, který je „normální“: anomálie jsou uvedeny jako ty instance v datové sadě, které neodpovídají normálnímu profilu. Isolation Forest používá jiný přístup: namísto pokusu o vytvoření modelu normálních instancí výslovně izoluje anomální body v datové sadě. Hlavní výhodou tohoto přístupu je možnost využití vzorkovacích technik v rozsahu, který není povolen metodám založeným na profilech, čímž se vytvoří velmi rychlý algoritmus s nízkými nároky na paměť.

Dějiny

Algoritmus Isolation Forest (iForest) původně navrhli Fei Tony Liu, Kai Ming Ting a Zhi-Hua Zhou v roce 2008. Autoři využili výhody dvou kvantitativních vlastností anomálních datových bodů ve vzorku:

Několik - jsou menšinou sestávající z méně instancí a
Různé - mají hodnoty atributů, které se velmi liší od hodnot běžných instancí

Protože anomálií je „málo a jsou různé“, lze je snáze „izolovat“ ve srovnání s normálními body. Isolation Forest vytváří soubor „izolačních stromů“ (iTrees) pro sadu dat a anomálie jsou body, které mají na iTrees kratší průměrné délky cesty.

V pozdějším článku, publikovaném v roce 2012, stejní autoři popsali soubor experimentů, které mají dokázat, že iForest:

má nízkou lineární časovou složitost a malý požadavek na paměť
je schopen vypořádat se s vysokodimenzionálními daty s irelevantními atributy
lze trénovat s anomáliemi v tréninkové sadě nebo bez nich
může poskytovat výsledky detekce s různými úrovněmi granularity bez přeškolování

V roce 2013 Zhiguo Ding a Minrui Fei navrhli rámec založený na iForest k vyřešení problému s detekcí anomálií ve streamovaných datech. Další aplikace iForest na streamování dat jsou popsány v dokumentech Tan et al., Susto et al. a Weng et al.

Jedním z hlavních problémů aplikace iForest na detekci anomálií nebyl samotný model, ale spíše způsob výpočtu „skóre anomálie“. Tento problém zdůraznili Sahand Hariri, Matias Carrasco Kind a Robert J. Brunner v dokumentu z roku 2018, kde navrhli vylepšený model iForest s názvem Extended Isolation Forest (EIF). Ve stejném článku autoři popisují vylepšení původního modelu a způsob, jakým jsou schopni zlepšit konzistenci a spolehlivost skóre anomálií vytvořeného pro daný datový bod.

Algoritmus

Obr. 2 - příklad izolace neanomálního bodu ve 2D Gaussově distribuci.

Na základě algoritmu Isolation Forest je tendence anomálních instancí v datové sadě snáze oddělit od zbytku vzorku (izolovat) ve srovnání s normálními body. Aby bylo možné izolovat datový bod, algoritmus rekurzivně generuje oddíly ve vzorku náhodným výběrem atributu a poté náhodným výběrem hodnoty rozdělení pro atribut mezi minimální a maximální hodnotou povolenou pro tento atribut.

Obr. 3 - příklad izolace anomálního bodu ve 2D Gaussově distribuci.

Příklad náhodného rozdělení v 2D datové sadě normálně distribuovaných bodů je uveden na obr. 2 pro neanomální bod a obr. 3 pro bod, u kterého je větší pravděpodobnost, že bude anomálií. Z obrázků je patrné, jak anomálie vyžadují k izolování méně náhodných oddílů ve srovnání s normálními body.

Z matematického hlediska může být rekurzivní dělení reprezentováno stromovou strukturou s názvem Isolation Tree , zatímco počet oddílů potřebných k izolaci bodu lze interpretovat jako délku cesty v rámci stromu k dosažení koncového uzlu počínaje od kořene. Například délka dráhy bodu na obr. 2 je větší než délka dráhy na obr. 3. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {j}}$

Formálněji nechť je to soubor d-rozměrných bodů a . Izolační strom (iTree) je definován jako datová struktura s následujícími vlastnostmi: ${\ Displaystyle X = \ {x_ {1}, \ tečky, x_ {n} \}}$ ${\ displaystyle X '\ podmnožina X}$

pro každý uzel ve stromu je buď externí uzel bez potomka, nebo interní uzel s jedním „testem“ a přesně dvěma dceřinými uzly ( a ) ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$
test v uzlu se skládá z atributu a hodnoty rozdělení tak, že test určuje procházení datového bodu buď nebo . ${\ displaystyle T}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ Displaystyle q <p}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$

Aby bylo možné sestavit iTree, algoritmus se rekurzivně dělí náhodným výběrem atributu a hodnoty rozdělení , dokud buď ${\ displaystyle X '}$ ${\ displaystyle q}$ ${\ displaystyle p}$

uzel má pouze jednu instanci, popř
všechna data v uzlu mají stejné hodnoty.

Když je iTree plně dospělý, každý bod v je izolován v jednom z externích uzlů. Intuitivně jsou anomální body ty (snadněji izolovatelné, tedy) s menší délkou cesty ve stromu, kde délka dráhy bodu je definována jako počet hran, které procházejí z kořenového uzlu, aby se dostaly do externího uzlu. ${\ displaystyle X}$ ${\ displaystyle h (x_ {i})}$ ${\ displaystyle x_ {i} \ v X}$ ${\ displaystyle x_ {i}}$

Pravděpodobnostní vysvětlení iTree je uvedeno v původním dokumentu iForest.

Vlastnosti izolačního lesa

Sub-vzorkování : od iForest nemusí izolovat všechny normálních případech to může často ignorovat velkou většinu tréninkového vzorku. V důsledku toho iForest funguje velmi dobře, když je velikost vzorků udržována malá, což je vlastnost, která je v kontrastu s velkou většinou stávajících metod, kde je obvykle žádoucí velká velikost vzorkování.
Swamping : když jsou normální instance příliš blízko anomáliím, zvyšuje se počet oddílů potřebných k oddělení anomálií, což je jev známý jako zaplavení , což ztěžuje iForest rozlišování mezi anomáliemi a normálními body. Jedním z hlavních důvodů zaplavení je přítomnost příliš velkého množství dat pro účely detekce anomálií, což znamená, že jedním z možných řešení problému je subvzorkování. Vzhledem k tomu, že iForest velmi dobře reaguje na dílčí vzorkování, pokud jde o výkon, je snížení počtu bodů ve vzorku také dobrým způsobem, jak snížit účinek bažiny.
Maskování : když je počet anomálií vysoký, je možné, že některé z nich se agregují v hustém a velkém klastru, což ztěžuje oddělení jednotlivých anomálií a následně detekovat takové body jako anomálie. Podobně jako u bažin je tento jev (známý jako „ maskování “) také pravděpodobnější, když je počet bodů ve vzorku velký, a lze jej zmírnit dílčím vzorkováním.
High Dimensional Data : jedním z hlavních omezení standardních metod založených na vzdálenosti je jejich neúčinnost při práci s vysokorozměrnými datovými soubory :. Hlavním důvodem je to, že ve vysokodimenzionálním prostoru je každý bod stejně řídký, takže použití vzdálenosti založené na vzdálenosti je docela neúčinné. Vysoce dimenzionální data bohužel také ovlivňují výkon detekce iForest, ale výkon lze výrazně zlepšit přidáním testu výběru funkcí, jako je Kurtosis, ke snížení rozměrnosti prostoru vzorku.
Pouze normální instance : iForest funguje dobře, i když tréninková sada neobsahuje žádný anomální bod, důvodem je, že iForest popisuje distribuci dat takovým způsobem, že vysoké hodnoty délky cesty odpovídají přítomnosti datových bodů. V důsledku toho je přítomnost anomálií zcela irelevantní pro výkon detekce iForest. ${\ displaystyle h (x_ {i})}$

Detekce anomálií s lesem izolace

Detekce anomálií pomocí Isolation Forest je proces složený ze dvou hlavních fází:

v první fázi se k sestavení iTrees používá tréninková datová sada, jak je popsáno v předchozích částech.
ve druhé fázi každá instance v testovací sadě projde sestavením iTrees v předchozí fázi a instanci je přiřazeno správné „skóre anomálie“ pomocí níže popsaného algoritmu

Jakmile jsou všem instancím v testovací sadě přiřazeno skóre anomálie, je možné označit jako „anomálii“ jakýkoli bod, jehož skóre je větší než předem definovaný práh, který závisí na doméně, na kterou se analýza aplikuje.

Skóre anomálií

Algoritmus pro výpočet skóre anomálií datového bodu je založen na pozorování, že struktura iTrees je ekvivalentní struktuře Binary Search Trees (BST): ukončení externího uzlu iTree odpovídá neúspěšnému hledání v BST . V důsledku toho je odhad průměru ukončení externích uzlů stejný jako u neúspěšných vyhledávání v BST, tj. ${\ displaystyle h (x)}$

${\ Displaystyle c (m) = {\ begin {cases} 2H (m-1)-{\ frac {2 (m-1)} {n}} & {\ text {for}} m> 2 \\ 1 & {\ text {for}} m = 2 \\ 0 & {\ text {else}} \ end {cases}}}$

kde je velikost testovacích dat, velikost souboru vzorku a harmonické číslo, které lze odhadnout podle toho , kde je Eulerova-Mascheroniho konstanta . ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle H}$ ${\ Displaystyle H (i) = ln (i)+\ gamma}$ ${\ displaystyle \ gamma = 0,5772156649}$

Hodnota c (m) výše představuje průměr daných hodnot , takže ji můžeme použít k normalizaci a získání odhadu skóre anomálie pro danou instanci x: ${\ displaystyle h (x)}$ ${\ displaystyle m}$ ${\ displaystyle h (x)}$

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

kde je průměrná hodnota ze sbírky iTrees. Je zajímavé poznamenat, že pro jakýkoli daný případ : ${\ Displaystyle E (h (x))}$ ${\ displaystyle h (x)}$ ${\ displaystyle x}$

pokud je blízko, pak je velmi pravděpodobné, že se jedná o anomálii ${\ displaystyle s}$ ${\ displaystyle 1}$ ${\ displaystyle x}$
pokud je menší než pak, bude pravděpodobně normální hodnotou ${\ displaystyle s}$ ${\ displaystyle 0,5}$ ${\ displaystyle x}$
pokud jsou pro daný vzorek všem instancím přiřazeno skóre anomálií kolem , pak lze bezpečně předpokládat, že vzorek nemá žádnou anomálii ${\ displaystyle 0,5}$

Rozšířený izolační les

Jak je popsáno v předchozích částech, algoritmus Isolation Forest funguje velmi dobře z hlediska výpočtu i spotřeby paměti. Hlavním problémem původního algoritmu je to, že způsob větvení stromů přináší zkreslení, které pravděpodobně sníží spolehlivost skóre anomálií pro hodnocení dat. Toto je hlavní motivace zavedení algoritmu Extended Isolation Forest (EIF) od Hariri et al.

Obr. 4 - dvourozměrné normálně distribuované body s nulovým průměrem a jednotkovou kovarianční maticí

Abychom pochopili, proč původní izolační les trpí touto předpojatostí, autoři poskytují praktický příklad založený na náhodném souboru dat převzatém z 2-D normální distribuce s nulovým průměrem a kovariancí danou maticí identity. Příklad takového souboru dat je znázorněn na obr.

Při pohledu na obrázek je snadné pochopit, že body spadající blízko (0, 0) budou pravděpodobně normální body, zatímco bod, který leží daleko od (0, 0), bude pravděpodobně anomální. V důsledku toho by se skóre anomálie bodu mělo zvyšovat s téměř kruhovým a symetrickým vzorem, když se bod pohybuje radiálně ven „středem“ distribuce. V praxi tomu tak není, jak autoři demonstrují generováním mapy skóre anomálií vytvořené pro distribuci algoritmem Isolation Forest. Ačkoli se skóre anomálií správně zvyšuje, když se body pohybují radiálně směrem ven, generují také obdélníkové oblasti s nižším skóre anomálií ve směrech xay, ve srovnání s jinými body, které spadají zhruba ve stejné radiální vzdálenosti od středu.

Obr. 5 - náhodné dělení s EIF

Je možné prokázat, že tyto neočekávané obdélníkové oblasti v mapě skóre anomálií jsou skutečně artefaktem zavedeným algoritmem a jsou dány hlavně skutečností, že hranice rozhodování Isolation Forest jsou omezeny na svislé nebo vodorovné (viz obr. 2) a obr. 3).

To je důvod, proč ve svém příspěvku Hariri et al. navrhnout vylepšit původní izolační les následujícím způsobem: namísto výběru náhodného prvku a hodnoty v rozsahu dat vyberou řez větví, který má náhodný „sklon“. Příklad náhodného rozdělení s EIF je znázorněn na obr.

Autoři ukazují, jak je nový přístup schopen překonat limity původního lesa izolace, což nakonec vede ke zlepšení mapy skóre anomálií.

Implementace open source

Původní implementace:

Izolace Forest , algoritmus, který detekuje datově anomálie pomocí binárních stromů napsané v R . Vydal první autor listu Liu, Fei Tony v roce 2009.

Další implementace (v abecedním pořadí):

EIF - Implementace Extended Isolation Forest pro detekci anomálií od Sahand Hariri .
Extended Isolation Forest pomocí H2O-3 -Implementace Extended Isolation Forest pro detekci anomálií pomocí H2O-3.
Isolation Forest - implementace Spark/Scala, kterou vytvořil James Verbus z týmu AI Anti -Abuse AI.
Isolation Forest pomocí H2O-3 -Implementace izolačního lesa pro detekci anomálií pomocí H2O-3.
Implementace balíkové samoty v R od Srikanth Komala Sheshachala .
Implementace Pythonu s příklady v scikit-learn .
Spark iForest - Distribuovaná implementace ve Scale a Pythonu, která běží na Apache Spark . Napsal Yang, Fangzhou .

Languages

In other projects