Las izolacyjny - Isolation forest

Las izolacji to pierwszy algorytm wykrywania anomalii, który identyfikuje anomalie za pomocą izolacji. Zostało ono początkowo zaproponowane i opracowane przez Fei Tony Liu, Kai Ming Tinga i Zhi-Hua Zhou w 2008 roku. Znaczenie tych badań polega na odejściu od głównej filozofii leżącej u podstaw istniejących wówczas detektorów anomalii, w której normalne instancje są profilowane przed anomaliami. są identyfikowane jako przypadki, które nie są zgodne. Las izolacji wprowadza zupełnie inną metodę, która jawnie izoluje anomalie przy użyciu drzew binarnych, demonstrując nową możliwość szybkiego detektora anomalii, który bezpośrednio kieruje anomalie bez intensywnego procesu profilowania normalnych wystąpień. Algorytm charakteryzuje się liniową złożonością czasową z niską stałą i małym zapotrzebowaniem na pamięć, co sprawdza się dobrze w problemach wielowymiarowych, które mają dużą liczbę nieistotnych atrybutów oraz w sytuacjach, gdy zbiór uczący nie zawiera żadnych anomalii.

Rys. 1 - przykładowy ruch sieciowy z potencjalnie nietypowymi punktami.

W statystykach anomalia (inaczej odstająca ) to obserwacja lub zdarzenie, które tak bardzo odbiega od innych zdarzeń, aby wzbudzić podejrzenia, że ​​zostało wygenerowane przez inną średnią. Na przykład wykres na rys. 1 przedstawia ruch przychodzący do serwera WWW wyrażony jako liczba żądań w odstępach 3-godzinnych przez okres jednego miesiąca. Wystarczy spojrzeć na obraz, aby zauważyć, że niektóre punkty (zaznaczone czerwonym kółkiem) są niezwykle wysokie, do tego stopnia, że ​​można podejrzewać, że serwer sieciowy mógł być w tym czasie atakowany. Z drugiej strony płaski segment oznaczony czerwoną strzałką również wydaje się niezwykły i może być oznaką, że serwer nie działał w tym czasie.

Anomalie w dużym zbiorze danych mogą mieć bardzo skomplikowane wzorce, które w większości przypadków są trudne do wykrycia wizualnie. To jest powód, dla którego dziedzina wykrywania anomalii jest dobrze dostosowana do zastosowania technik uczenia maszynowego .

Najpowszechniejsze techniki stosowane do wykrywania anomalii opierają się na konstrukcji profilu tego, co jest „normalne”: anomalie są zgłaszane jako te wystąpienia w zbiorze danych, które nie są zgodne z normalnym profilem. Isolation Forest stosuje inne podejście: zamiast próbować zbudować model normalnych instancji, wyraźnie izoluje anomalne punkty w zbiorze danych. Główną zaletą tego podejścia jest możliwość wykorzystania technik próbkowania w stopniu nie dopuszczonym do metod opartych na profilach, tworząc bardzo szybki algorytm o niskim zapotrzebowaniu na pamięć.

Historia

Algorytm Isolation Forest (iForest) został pierwotnie zaproponowany przez Fei Tony Liu, Kai Ming Ting i Zhi-Hua Zhou w 2008 roku. Autorzy wykorzystali dwie ilościowe właściwości anomalnych punktów danych w próbie:

1. Niewiele - stanowią mniejszość składającą się z mniejszej liczby instancji i
2. Różne - mają wartości atrybutów, które bardzo różnią się od tych z normalnych instancji

Ponieważ anomalie są „nieliczne i różne”, łatwiej je „wyizolować” w porównaniu z normalnymi punktami. Isolation Forest tworzy zestaw „Drzew izolacji” (iTrees) dla zestawu danych, a anomalie to punkty, które mają krótszą średnią długość ścieżki na iTrees.

W późniejszym artykule, opublikowanym w 2012 roku, ci sami autorzy opisali zestaw eksperymentów, aby udowodnić, że iForest:

• ma niską złożoność czasu liniowego i małe wymagania dotyczące pamięci
• jest w stanie poradzić sobie z danymi wielkowymiarowymi o nieistotnych atrybutach
• można trenować z anomaliami lub bez w zestawie treningowym
• może dostarczać wyniki wykrywania o różnych poziomach szczegółowości bez ponownego szkolenia

W 2013 r. Zhiguo Ding i Minrui Fei zaproponowali platformę opartą na iForest, aby rozwiązać problem wykrywania anomalii w przesyłaniu danych. Więcej zastosowań iForest do danych strumieniowych opisano w artykułach Tan i in., Susto i in. i Weng i in.

Jednym z głównych problemów związanych z zastosowaniem iForest do wykrywania anomalii nie był sam model, ale sposób obliczania „wyniku anomalii”. Na ten problem zwrócili uwagę Sahand Hariri, Matias Carrasco Kind i Robert J. Brunner w artykule z 2018 roku, w którym zaproponowali ulepszony model iForest o nazwie Extended Isolation Forest (EIF). W tym samym artykule autorzy opisują ulepszenia wprowadzone do oryginalnego modelu oraz sposób, w jaki są one w stanie zwiększyć spójność i wiarygodność wyniku anomalii uzyskanego dla danego punktu danych.

Algorytm

Rys. 2 - przykład wyodrębnienia punktu nieanomalnego w dwuwymiarowym rozkładzie Gaussa.

Na podstawie algorytmu Isolation Forest istnieje tendencja do łatwiejszego oddzielenia anomalnych wystąpień w zbiorze danych od reszty próbki (izolowania) w porównaniu z normalnymi punktami. Aby wyizolować punkt danych, algorytm rekursywnie generuje partycje w próbce, losowo wybierając atrybut, a następnie losowo wybierając wartość podziału dla atrybutu, między minimalną i maksymalną wartością dozwoloną dla tego atrybutu.

Rys. 3 - przykład wyodrębnienia punktu anomalnego w dwuwymiarowym rozkładzie Gaussa.

Przykład losowego partycjonowania w zbiorze danych 2D z punktami o normalnym rozkładzie podano na Rys. 2 dla punktu nieanomalnego i Rys. 3 dla punktu, który z większym prawdopodobieństwem może być anomalią. Na zdjęciach widać, że anomalie wymagają wyizolowania mniejszej liczby losowych partycji w porównaniu z normalnymi punktami.

Z matematycznego punktu widzenia partycjonowanie rekurencyjne może być reprezentowane przez strukturę drzewa o nazwie Drzewo izolacji , podczas gdy liczba partycji wymaganych do wyizolowania punktu może być interpretowana jako długość ścieżki w drzewie, aby dotrzeć do węzła końcowego rozpoczynającego się od korzenia. Na przykład długość ścieżki punktu na rys. 2 jest większa niż długość ścieżki na rys. 3. ${\displaystyle x_{i}}$${\displaystyle x_{j}}$

Bardziej formalnie niech będzie zbiorem d-wymiarowych punktów i . Drzewo izolacji (iTree) jest zdefiniowane jako struktura danych o następujących właściwościach: ${\ Displaystyle X = \ {x_ {1}, \ kropki, x_ {n} \}}$${\displaystyle X'\podzbiór X}$

1. dla każdego węzła w Drzewie jest albo węzłem zewnętrznym bez dziecka, albo węzłem wewnętrznym z jednym „testem” i dokładnie dwoma węzłami potomnymi ( i )${\displaystyle T}$${\displaystyle T}$${\displaystyle T_{l}}$${\displaystyle T_{r}}$
2. test w węźle składa się z atrybutu i wartości podziału w taki sposób, że test określa przejście punktu danych do albo lub .${\displaystyle T}$${\displaystyle q}$${\displaystyle p}$${\displaystyle q<p}$${\displaystyle T_{l}}$${\displaystyle T_{r}}$

W celu zbudowania iTree algorytm rekursywnie dzieli , losowo wybierając atrybut i podzieloną wartość , aż do ${\displaystyle X'}$${\displaystyle q}$${\displaystyle p}$

1. węzeł ma tylko jedną instancję lub
2. wszystkie dane w węźle mają te same wartości.

Kiedy iTree jest w pełni rozwinięty, każdy punkt w jest izolowany w jednym z zewnętrznych węzłów. Intuicyjnie, anomalne punkty to te (łatwiejsze do wyizolowania) o mniejszej długości ścieżki w drzewie, gdzie długość ścieżki punktu jest zdefiniowana jako liczba krawędzi przechodzących od węzła głównego do węzła zewnętrznego. ${\ Displaystyle X}$${\ Displaystyle h (x_ {i})}$${\ Displaystyle X_ {i} \ w X}$${\displaystyle x_{i}}$

Probabilistyczne wyjaśnienie iTree jest zawarte w oryginalnym artykule iForest.

Właściwości lasu izolacyjnego

• Próbkowanie podrzędne : ponieważ iForest nie musi izolować wszystkich normalnych instancji, często może zignorować dużą większość próbki uczącej. W konsekwencji iForest działa bardzo dobrze, gdy wielkość próbkowania jest niewielka, co jest właściwością, która kontrastuje z większością istniejących metod, w których zwykle pożądana jest duża wielkość próbkowania.
• Swamping : gdy normalne instancje są zbyt blisko anomalii, zwiększa się liczba partycji wymaganych do oddzielenia anomalii. Jest to zjawisko znane jako swamping , które utrudnia iForestowi odróżnienie anomalii od punktów normalnych. Jedną z głównych przyczyn zasypywania jest obecność zbyt wielu danych w celu wykrycia anomalii, co sugeruje, że jednym z możliwych rozwiązań problemu jest podpróbkowanie. Ponieważ iForest bardzo dobrze reaguje na podpróbkowanie pod względem wydajności, zmniejszenie liczby punktów w próbce jest również dobrym sposobem na zmniejszenie efektu zasypywania.
• Maskowanie : gdy liczba anomalii jest wysoka, możliwe jest, że niektóre z nich akumulują się w gęste i duże skupisko, co utrudnia oddzielenie pojedynczych anomalii i, z kolei, wykrycie takich punktów jako anomalnych. Podobnie jak w przypadku zalewania, zjawisko to (znane jako „ maskowanie ”) jest również bardziej prawdopodobne, gdy liczba punktów w próbie jest duża i można je złagodzić poprzez podpróbkowanie.
• Dane wysokowymiarowe : jednym z głównych ograniczeń standardowych metod opartych na odległości jest ich nieefektywność w radzeniu sobie z wysokowymiarowymi zestawami danych:. Głównym tego powodem jest to, że w przestrzeni wielowymiarowej każdy punkt jest równie rzadki, więc użycie miary separacji opartej na odległości jest dość nieefektywne. Niestety, dane wysokowymiarowe mają również wpływ na wydajność wykrywania iForest, ale wydajność można znacznie poprawić, dodając test wyboru funkcji, taki jak Kurtosis, w celu zmniejszenia wymiarowości przestrzeni próbki.
• Tylko normalne instancje : iForest działa dobrze, nawet jeśli zbiór uczący nie zawiera żadnego punktu anomalnego, ponieważ iForest opisuje rozkłady danych w taki sposób, że wysokie wartości długości ścieżki odpowiadają obecności punktów danych. W konsekwencji obecność anomalii jest zupełnie nieistotna dla wydajności wykrywania przez iForest.${\ Displaystyle h (x_ {i})}$

Wykrywanie anomalii za pomocą lasu izolacji

Wykrywanie anomalii za pomocą Isolation Forest to proces składający się z dwóch głównych etapów:

1. w pierwszym etapie zestaw danych uczących jest używany do budowania iTrees, jak opisano w poprzednich sekcjach.
2. w drugim etapie każda instancja w zbiorze testowym przechodzi przez kompilację iTrees z poprzedniego etapu i przypisywana jest jej odpowiednia „wynik anomalii” za pomocą opisanego poniżej algorytmu

Gdy wszystkim instancjom w zestawie testowym zostanie przypisana ocena anomalii, możliwe jest oznaczenie jako „anomalii” dowolnego punktu, którego wynik jest większy niż wstępnie zdefiniowany próg, który zależy od domeny, do której stosowana jest analiza.

Wynik anomalii

Algorytm obliczania wyniku anomalii w punkcie danych opiera się na obserwacji, że struktura iTrees jest równoważna strukturze binarnych drzew wyszukiwania (BST): zakończenie do zewnętrznego węzła iTree odpowiada nieudanemu wyszukiwaniu w BST . W konsekwencji oszacowanie średniej dla zakończeń węzłów zewnętrznych jest takie samo jak dla nieudanych wyszukiwań w BST, czyli ${\ Displaystyle h (x)}$

${\ Displaystyle c (m) = {\ zacząć {przypadki} 2 H (m-1) - {\ Frac {2 (m-1)} {n}} i {\ tekst {dla}} m> 2 \ \ 1 i {\text{dla }}m=2\\0&{\text{otherwise}}\end{cases}}}$

gdzie jest rozmiarem danych testowych, jest rozmiarem zbioru próbek i jest liczbą harmoniczną, którą można oszacować przez , gdzie jest stałą Eulera-Mascheroniego . ${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle H}$${\ Displaystyle H (i) = ln (i) + \ gamma}$${\ Displaystyle \ gamma = 0,5772156649}$

Wartość c(m) powyżej reprezentuje średnią danego , więc możemy jej użyć do normalizacji i uzyskania oszacowania wyniku anomalii dla danej instancji x: ${\ Displaystyle h (x)}$${\ Displaystyle m}$${\ Displaystyle h (x)}$

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

gdzie jest średnią wartością z kolekcji iTrees. Warto zauważyć, że w każdym przypadku : ${\ Displaystyle E (h (x))}$${\ Displaystyle h (x)}$${\displaystyle x}$

• jeśli jest blisko to jest bardzo prawdopodobne, że będzie anomalią${\displaystyle s}$${\ Displaystyle 1}$${\displaystyle x}$
• jeśli jest mniejsza niż wtedy jest prawdopodobne, aby być wartością normalną${\displaystyle s}$${\ Displaystyle 0.5}$${\displaystyle x}$
• jeśli dla danej próbki wszystkie instancje mają przypisany wynik anomalii około , można bezpiecznie założyć, że próbka nie ma żadnej anomalii${\ Displaystyle 0.5}$

Rozszerzony las izolacji

Jak opisano w poprzednich sekcjach, algorytm Isolation Forest działa bardzo dobrze zarówno z punktu widzenia obliczeniowego, jak i zużycia pamięci. Główny problem z oryginalnym algorytmem polega na tym, że sposób, w jaki odbywa się rozgałęzianie drzew, wprowadza błąd, który prawdopodobnie zmniejszy wiarygodność wyników anomalii w rankingu danych. Jest to główna motywacja wprowadzenia algorytmu Extended Isolation Forest (EIF) przez Hariri et al.

Rys. 4 - dwuwymiarowe punkty o rozkładzie normalnym z zerową średnią i macierzą kowariancji jedności

Aby zrozumieć, dlaczego pierwotny Las Izolacji cierpi z powodu tego błędu, autorzy podają praktyczny przykład oparty na losowym zbiorze danych pobranym z rozkładu normalnego 2D ze średnią zerową i kowariancją podaną przez macierz tożsamości. Przykład takiego zbioru danych pokazano na rys. 4.

Łatwo to zrozumieć, patrząc na obrazek, na którym punkty znajdujące się blisko (0, 0) są prawdopodobnie punktami normalnymi, podczas gdy punkt leżący daleko od (0, 0) jest prawdopodobnie nienormalny. W konsekwencji wynik anomalii punktu powinien wzrastać w sposób niemal kołowy i symetryczny, gdy punkt przesuwa się promieniowo na zewnątrz „środka” rozkładu. W praktyce tak nie jest, co wykazali autorzy, generując mapę wyników anomalii stworzoną dla rozkładu przez algorytm Isolation Forest. Chociaż wyniki anomalii prawidłowo rosną, gdy punkty przesuwają się promieniowo na zewnątrz, generują również prostokątne obszary o niższym wyniku anomalii w kierunkach x i y, w porównaniu z innymi punktami, które spadają mniej więcej w tej samej promieniowej odległości od środka.

Rys. 5 - losowe partycjonowanie z EIF

Możliwe jest wykazanie, że te nieoczekiwane prostokątne regiony na mapie wyników anomalii są rzeczywiście artefaktem wprowadzonym przez algorytm i wynikają głównie z faktu, że granice decyzyjne Lasu Izolacji są ograniczone do pionowego lub poziomego (patrz rys. 2). i rys. 3).

To jest powód, dla którego w swoim artykule Hariri i in. proponują ulepszenie oryginalnego Lasu Izolacji w następujący sposób: zamiast wybierać losową cechę i wartość z zakresu danych, wybierają cięcie gałęzi, które ma losowe „nachylenie”. Przykład losowego partycjonowania za pomocą EIF pokazano na rys. 5.

Autorzy pokazują, w jaki sposób nowe podejście jest w stanie pokonać ograniczenia oryginalnego Lasu Izolacji, prowadząc ostatecznie do ulepszonej mapy wyników anomalii.

Implementacje open source

Oryginalna realizacja:

• Isolation Forest , algorytm wykrywający anomalie danych przy użyciu drzew binarnych napisanych w języku R . Wydany przez pierwszego autora gazety Liu, Fei Tony w 2009 roku.

Inne realizacje (w porządku alfabetycznym):

• EIF – Implementacja Extended Isolation Forest do wykrywania anomalii autorstwa Sahanda Hariri .
• Extended Isolation Forest by H2O-3 - Implementacja Extended Isolation Forest do wykrywania anomalii przez H2O-3.
• Isolation Forest — implementacja Spark/Scala, stworzona przez Jamesa Verbusa z zespołu LinkedIn Anti-Abuse AI.
• Isolation Forest by H2O-3 - Implementacja Isolation Forest for Anomaly Detection by H2O-3.
• Wdrożenie pakietu samotności w języku R autorstwa Srikanth Komala Sheshachala .
• Implementacja Pythona z przykładami w scikit-learn .
• Spark iForest — rozproszona implementacja w Scala i Python, która działa na Apache Spark . Napisane przez Yang, Fangzhou .

Zobacz też

• Wykrywanie anomalii
• Losowy las

Bibliografia