Pădure de izolare - Isolation forest

Pădurea de izolare este primul algoritm de detectare a anomaliilor care identifică anomaliile folosind izolarea. Acesta a fost inițial propus și dezvoltat de Fei Tony Liu, Kai Ming Ting și Zhi-Hua Zhou în 2008. Semnificația acestei cercetări constă în abaterea sa de la filosofia principală care stă la baza detectoarelor de anomalii existente la acea vreme, unde instanțele normale sunt profilate înainte de anomalii. sunt identificate ca instanțe care nu se conformează. Pădurea de izolare introduce o metodă fundamental diferită care izolează în mod explicit anomaliile folosind arbori binari, demonstrând noua posibilitate a unui detector rapid de anomalii care vizează direct anomaliile fără procesul intensiv de resurse al profilării instanțelor normale. Algoritmul are o complexitate liniară a timpului cu o constantă scăzută și o cerință de memorie redusă, care funcționează bine în probleme cu dimensiuni ridicate care au un număr mare de atribute irelevante și în situații în care setul de antrenament nu conține nicio anomalie.

Fig. 1 - exemplu trafic web cu puncte potențial anormale.

În statistici , o anomalie (cunoscută și ca outlier ) este o observație sau eveniment care se abate atât de mult de la alte evenimente pentru a trezi suspiciunea că a fost generată de o altă medie. De exemplu, graficul din Fig.1 reprezintă traficul de intrare către un server web, exprimat ca număr de solicitări în intervale de 3 ore, pentru o perioadă de o lună. Este destul de evident prin simpla examinare a imaginii că unele puncte (marcate cu un cerc roșu) sunt neobișnuit de mari, până la punctul de a induce suspectul că serverul web ar fi putut fi atacat în acel moment. Pe de altă parte, segmentul plat indicat de săgeata roșie pare, de asemenea, neobișnuit și ar putea fi un semn că serverul a fost oprit în perioada respectivă.

Anomaliile dintr-un set mare de date pot urma modele foarte complicate, care sunt dificil de detectat vizual în marea majoritate a cazurilor. Acesta este motivul pentru care domeniul detectării anomaliilor este potrivit pentru aplicarea tehnicilor de învățare automată .

Cele mai frecvente tehnici utilizate pentru detectarea anomaliilor se bazează pe construirea unui profil a ceea ce este „normal”: anomaliile sunt raportate ca acele instanțe din setul de date care nu sunt conforme cu profilul normal. Isolation Forest folosește o abordare diferită: în loc să încerce să construiască un model de instanțe normale, izolează în mod explicit punctele anormale din setul de date. Principalul avantaj al acestei abordări este posibilitatea de a exploata tehnicile de eșantionare într-o măsură care nu este permisă metodelor bazate pe profil, creând un algoritm foarte rapid cu o cerere redusă de memorie.

Istorie

Algoritmul Isolation Forest (iForest) a fost inițial propus de Fei Tony Liu, Kai Ming Ting și Zhi-Hua Zhou în 2008. Autorii au profitat de două proprietăți cantitative ale punctelor de date anormale dintr-un eșantion:

Puțini - sunt minoritatea constând din mai puține instanțe și
Diferite - au valori de atribut care sunt foarte diferite de cele ale instanțelor normale

Deoarece anomaliile sunt „puține și diferite”, ele sunt mai ușor de „izolat” în comparație cu punctele normale. Isolation Forest construiește un ansamblu de „Copaci de izolare” (iTrees) pentru setul de date, iar anomaliile sunt punctele care au o lungime medie mai mică a traseului pe iTrees.

Într-o lucrare ulterioară, publicată în 2012, aceiași autori au descris un set de experimente pentru a demonstra că iForest:

are o complexitate de timp liniară scăzută și o cerință mică de memorie
este capabil să facă față datelor cu dimensiuni ridicate cu atribute irelevante
poate fi antrenat cu sau fără anomalii în setul de antrenament
poate oferi rezultate de detectare cu diferite niveluri de granularitate fără re-antrenament

În 2013, Zhiguo Ding și Minrui Fei au propus un cadru bazat pe iForest pentru a rezolva problema detectării anomaliilor în fluxul de date. Mai multe aplicații ale iForest pentru streaming de date sunt descrise în lucrări de Tan și colab., Susto și colab. și Weng și colab.

Una dintre problemele principale ale aplicării iForest la detectarea anomaliilor nu a fost cu modelul în sine, ci mai degrabă cu modul în care a fost calculat „scorul anomaliei”. Această problemă a fost evidențiată de Sahand Hariri, Matias Carrasco Kind și Robert J. Brunner într-o lucrare din 2018, în care au propus un model îmbunătățit iForest numit Extended Isolation Forest (EIF). În aceeași lucrare, autorii descriu îmbunătățirile aduse modelului original și modul în care sunt capabili să sporească consistența și fiabilitatea scorului de anomalie produs pentru un anumit punct de date.

Algoritm

Fig. 2 - un exemplu de izolare a unui punct non-anormal într-o distribuție gaussiană 2D.

La baza algoritmului Isolation Forest, există tendința instanțelor anormale dintr-un set de date de a fi mai ușor de separat de restul eșantionului (izolat), comparativ cu punctele normale. Pentru a izola un punct de date, algoritmul generează recursiv partiții pe eșantion selectând aleatoriu un atribut și apoi selectând aleatoriu o valoare divizată pentru atribut, între valorile minime și maxime permise pentru acel atribut.

Fig. 3 - un exemplu de izolare a unui punct anormal într-o distribuție gaussiană 2D.

Un exemplu de partiționare aleatorie într-un set de date 2D de puncte distribuite în mod normal este dat în Fig. 2 pentru un punct non-anormal și în Fig. 3 pentru un punct care este mai probabil să fie o anomalie. Din imagini se vede cum anomaliile necesită mai puține partiții aleatorii pentru a fi izolate, în comparație cu punctele normale.

Din punct de vedere matematic, partiționarea recursivă poate fi reprezentată de o structură de arbore numită Izolație , în timp ce numărul de partiții necesare pentru a izola un punct poate fi interpretat ca lungimea căii, în interiorul arborelui, pentru a ajunge la un nod de terminare pornind din rădăcină. De exemplu, lungimea traseului punctului din Fig. 2 este mai mare decât lungimea traseului din Fig. 3. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {j}}$

Mai formal, să fie un set de puncte d-dimensionale și . Un arbore de izolare (iTree) este definit ca o structură de date cu următoarele proprietăți: ${\ displaystyle X = \ {x_ {1}, \ dots, x_ {n} \}}$ ${\ displaystyle X '\ subset X}$

pentru fiecare nod din Tree, este fie un nod extern fără copil, fie un nod intern cu un „test” și exact două noduri fiice ( și ) ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$
un test la nod constă dintr-un atribut și o valoare divizată astfel încât testul să determine traversarea unui punct de date către oricare sau . ${\ displaystyle T}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle q <p}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$

Pentru a construi un iTree, algoritmul se împarte recursiv selectând aleatoriu un atribut și o valoare divizată , până când ${\ displaystyle X '}$ ${\ displaystyle q}$ ${\ displaystyle p}$

nodul are o singură instanță sau
toate datele de la nod au aceleași valori.

Când iTree este complet dezvoltat, fiecare punct este izolat la unul dintre nodurile externe. Intuitiv, punctele anormale sunt acelea (mai ușor de izolat, deci) cu lungimea mai mică a căii în copac, unde lungimea căii punctului este definită ca numărul de muchii traversate de la nodul rădăcină pentru a ajunge la un nod extern. ${\ displaystyle X}$ ${\ displaystyle h (x_ {i})}$ ${\ displaystyle x_ {i} \ în X}$ ${\ displaystyle x_ {i}}$

O explicație probabilistică a iTree este furnizată în lucrarea originală iForest.

Proprietățile pădurii de izolare

Sub-eșantionare : deoarece iForest nu trebuie să izoleze toate cazurile normale, poate ignora frecvent marea majoritate a eșantionului de antrenament. În consecință, iForest funcționează foarte bine atunci când dimensiunea eșantionării este menținută mică, o proprietate care este în contrast cu marea majoritate a metodelor existente, unde dimensiunea eșantionării mari este de obicei de dorit.
Swamping : atunci când instanțele normale sunt prea apropiate de anomalii, crește numărul de partiții necesare pentru separarea anomaliilor, fenomen cunoscut sub numele de swamping , ceea ce face mai dificil pentru iForest să facă discriminări între anomalii și puncte normale. Unul dintre principalele motive ale mlaștinării este prezența a prea multe date în scopul detectării anomaliilor, ceea ce implică o posibilă soluție a problemei este sub-eșantionarea. Deoarece iForest răspunde foarte bine la sub-eșantionare în ceea ce privește performanța, reducerea numărului de puncte din eșantion este, de asemenea, o modalitate bună de a reduce efectul mlaștinării.
Mascare : atunci când numărul de anomalii este mare, este posibil ca unele dintre acestea să se agregeze într-un grup dens și mare, ceea ce face mai dificilă separarea anomaliilor individuale și, la rândul lor, detectarea unor astfel de puncte ca fiind anormale. Similar cu înmuierea, acest fenomen (cunoscut sub numele de „ mascare ”) este, de asemenea, mai probabil atunci când numărul de puncte din eșantion este mare și poate fi atenuat prin sub-eșantionare.
Date cu dimensiuni ridicate : una dintre principalele limitări la metodele standard, bazate pe distanță, este ineficiența lor în tratarea seturilor de date cu dimensiuni ridicate:. Principalul motiv pentru aceasta este că, într-un spațiu cu dimensiuni ridicate, fiecare punct este la fel de rar, astfel încât utilizarea unei măsuri de separare bazată pe distanță este destul de ineficientă. Din păcate, datele de înaltă dimensiune afectează, de asemenea, performanța de detectare a iForest, dar performanța poate fi mult îmbunătățită prin adăugarea unui test de selecție a caracteristicilor, cum ar fi Kurtosis, pentru a reduce dimensionalitatea spațiului eșantion.
Numai instanțe normale : iForest funcționează bine chiar dacă setul de antrenament nu conține niciun punct anormal, motivul fiind că iForest descrie distribuțiile de date în așa fel încât valorile ridicate ale lungimii traseului să corespundă prezenței punctelor de date. În consecință, prezența anomaliilor este destul de irelevantă pentru performanța de detectare a iForest. ${\ displaystyle h (x_ {i})}$

Detectarea anomaliilor cu pădure de izolare

Detectarea anomaliilor cu Isolation Forest este un proces compus din două etape principale:

în prima etapă, un set de date de instruire este utilizat pentru a construi iTrees așa cum este descris în secțiunile anterioare.
în a doua etapă, fiecare instanță din setul de testare este trecută prin construcția iTrees în etapa anterioară și un „scor de anomalie” adecvat este atribuit instanței utilizând algoritmul descris mai jos

Odată ce tuturor instanțelor din setul de testare li s-a atribuit un scor de anomalie, este posibil să se marcheze ca „anomalie” orice punct al cărui scor este mai mare decât un prag predefinit, care depinde de domeniul căruia i se aplică analiza.

Scorul de anomalie

Algoritmul pentru calcularea scorului de anomalie al unui punct de date se bazează pe observația că structura iTrees este echivalentă cu cea a Binary Search Trees (BST): o terminare la un nod extern al iTree corespunde unei căutări nereușite în BST . În consecință, estimarea mediei pentru terminările nodurilor externe este aceeași cu cea a căutărilor nereușite în BST, adică ${\ displaystyle h (x)}$

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

unde este dimensiunea datelor de testare, este dimensiunea setului de eșantioane și este numărul armonic, care poate fi estimat de , unde este constanta Euler-Mascheroni . ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle H}$ ${\ displaystyle H (i) = ln (i) + \ gamma}$ ${\ displaystyle \ gamma = 0.5772156649}$

Valoarea lui c (m) de mai sus reprezintă media datei , deci o putem folosi pentru a normaliza și a obține o estimare a scorului de anomalie pentru o instanță dată x: ${\ displaystyle h (x)}$ ${\ displaystyle m}$ ${\ displaystyle h (x)}$

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

unde este valoarea medie dintr-o colecție de iTrees. Este interesant de observat că, pentru orice caz dat : ${\ displaystyle E (h (x))}$ ${\ displaystyle h (x)}$ ${\ displaystyle x}$

dacă este aproape de atunci este foarte probabil să fie o anomalie ${\ displaystyle s}$ ${\ displaystyle 1}$ ${\ displaystyle x}$
dacă este mai mic decât atunci este probabil să fie o valoare normală ${\ displaystyle s}$ ${\ displaystyle 0.5}$ ${\ displaystyle x}$
dacă pentru un eșantion dat tuturor instanțelor li se atribuie un scor de anomalie de aproximativ , atunci este sigur să presupunem că eșantionul nu are nicio anomalie ${\ displaystyle 0.5}$

Pădure de izolare extinsă

Așa cum s-a descris în secțiunile anterioare, algoritmul Isolation Forest funcționează foarte bine atât din punct de vedere de calcul, cât și din punct de vedere al consumului de memorie. Principala problemă cu algoritmul original este că modul în care are loc ramificarea arborilor introduce o prejudecată, care este de natură să reducă fiabilitatea scorurilor de anomalie pentru clasarea datelor. Aceasta este principala motivație din spatele introducerii algoritmului Forest Isolation Extended (EIF) de către Hariri și colab.

Fig. 4 - puncte bidimensionale distribuite în mod normal cu medie zero și matrice de covarianță de unitate

Pentru a înțelege de ce pădurea de izolare originală suferă de această prejudecată, autorii oferă un exemplu practic bazat pe un set de date aleatoriu preluat dintr-o distribuție normală 2-D cu medie zero și covarianță dată de matricea de identitate. Un exemplu de astfel de set de date este prezentat în Fig. 4.

Este ușor de înțeles uitându-se la imagine că punctele care se apropie de (0, 0) sunt probabil puncte normale, în timp ce un punct care se află departe de (0, 0) este probabil anomal. În consecință, scorul de anomalie al unui punct ar trebui să crească cu un model aproape circular și simetric pe măsură ce punctul se deplasează radial spre exterior „centrul” distribuției. Acest lucru nu este cazul în practică, așa cum demonstrează autorii prin generarea hărții scorului de anomalie produsă pentru distribuția de către algoritmul Isolation Forest. Deși scorurile de anomalie cresc corect pe măsură ce punctele se deplasează radial spre exterior, ele generează și regiuni dreptunghiulare cu scor de anomalie mai mic în direcțiile x și y, comparativ cu alte puncte care cad aproximativ la aceeași distanță radială de centru.

Fig. 5 - partiționarea aleatorie cu EIF

Este posibil să se demonstreze că aceste regiuni dreptunghiulare neașteptate din harta scorului anomaliei sunt într-adevăr un artefact introdus de algoritm și se datorează în principal faptului că limitele decizionale ale Pădurii de izolare sunt limitate fie să fie verticale, fie orizontale (vezi Fig. 2 și Fig. 3).

Acesta este motivul pentru care în lucrarea lor, Hariri și colab. propun să îmbunătățească pădurea de izolare originală în felul următor: mai degrabă decât să selecteze o caracteristică și o valoare aleatorii în intervalul de date, selectează o tăietură de ramură care are o „pantă” aleatorie. Un exemplu de partiționare aleatorie cu EIF este prezentat în Fig. 5.

Autorii arată cum noua abordare este capabilă să depășească limitele pădurii de izolare originale, ducând în cele din urmă la o hartă îmbunătățită a scorului anomaliilor.

Implementări open source

Implementare originală:

Izolarea Forest , un algoritm care detectează date-anomalii folosind arbori binare scrise în R . Lansat de primul autor al lucrării Liu, Fei Tony în 2009.

Alte implementări (în ordine alfabetică):

EIF - O implementare a pădurii de izolare extinsă pentru detectarea anomaliilor de către Sahand Hariri .
Pădure de izolare extinsă prin H2O-3 - O implementare a pădurii de izolare extinsă pentru detectarea anomaliilor de către H2O-3.
Isolation Forest - O implementare Spark / Scala, creată de James Verbus de la echipa LinkedIn Anti-Abuse AI.
Isolation Forest by H2O-3 - O implementare a Isolation Forest pentru detectarea anomaliilor prin H2O-3.
Implementarea pachetului de singurătate în R de către Srikanth Komala Sheshachala .
Implementarea Python cu exemple în scikit-learn .
Spark iForest - O implementare distribuită în Scala și Python, care rulează pe Apache Spark . Scris de Yang, Fangzhou .

Languages

In other projects