Detekcja anomalii algorytmem RRCF
Zapotrzebowanie biznesowe na gromadzenie coraz większych ilości danych wiąże się niestety z utratą ich jakości. Jednocześnie często niemożliwa jest ręczna weryfikacja okiem eksperta. Jednym z wielu problemów, z którymi muszą mierzyć się analitycy, są anomalie. Ich występowanie jest na ogół niepożądane, ponieważ wpływają niekorzystnie na dalszą analizę oraz utrudniają modelowanie danych. Mogą również wskazywać na sytuacje wymagające natychmiastowych reakcji, takie jak próby oszustwa związanego z kartą kredytową lub błędy w automatycznych procesach. Ważne jest więc odpowiednio szybkie wykrywanie takich obserwacji, w czym z pomocą przychodzi uczenie maszynowe.
Jednym z algorytmów stosowanych do detekcji anomalii jest RRCF, czyli Robust Random Cut Forest [1].
Algorytm oparty został na założeniu, zgodnie z którym anomalie są względnie łatwe do wyodrębnienia z populacji. Są to punkty, które wyróżniają się ze swojego otoczenia pod względem jednej lub wielu cech. Są one także na tyle odległe od zwykłych obserwacji, że dzieląc zbiór w losowy sposób mamy duże prawdopodobieństwo oddzielenia anomalii od pozostałych danych. Działanie omawianego algorytmu polega właśnie na tworzeniu takich losowych podziałów. Podziały te tworzą drzewa decyzyjne, z których powstaje model zbliżony do lasu losowego, skąd nazwa opisywanej metody.
Ślepe poszukiwania
Pojedyncze drzewo decyzyjne konstruowane jest przy pomocy algorytmu rekurencyjnego. W pierwszym kroku tego procesu wybierany jest losowy wymiar zbioru danych. Szansa wyboru wymiaru zależy od jego wariancji – im szerszy jest przedział wartości należących do danego wymiaru, tym większe prawdopodobieństwo jego wyboru. Następnie wybierana jest losowa wartość zmiennej, względem której zbiór danych podzielony zostanie na dwa mniejsze. W ten sposób z tak zwanego korzenia drzewa utworzone zostają dwie gałęzie. Proces powtarzany jest rekurencyjnie dla każdej z nich aż do momentu, w którym wszystkie gałęzie będą składały się z tylko jednej obserwacji. Takie gałęzie nazywane są liśćmi drzewa. W efekcie otrzymujemy zbiór losowych reguł, które opisują każdą obserwację. Ponieważ anomalie znacznie różnią się od pozostałych punktów, możemy oczekiwać, że przy wyborze miejsca podziału „na ślepo” zostaną one względnie szybko oddzielone od reszty zbioru danych. Łatwo jest wyobrazić to sobie rysując poziomą lub pionową linię prostą w dowolnym miejscu na rysunku 1. – odstający pomarańczowy punkt ma największe prawdopodobieństwo osamotnienia w wyniku takiej operacji.
Oczywiście tworzenie losowych podziałów niesie ze sobą duże ryzyko popełnienia przypadkowych błędów, dlatego w ostatecznej punktacji uwzględnione zostają decyzje pochodzące z wielu takich drzew. Po zbudowaniu lasu losowego, uśrednienie wyników zmniejsza ryzyko pomyłki, ponieważ punkty znacznie różniące się od pozostałych powinny najczęściej zostać od nich oddzielone w początkowych regułach [2].
Konkurs na odmienność
Po opisaniu punktów w taki sposób, potrzebna jest reprezentacja liczbowa, na podstawie której anomalie mogą zostać jednoznacznie zidentyfikowane. W tym celu autorzy RRCF zaproponowali mierzenie stopnia zaburzeń, jakim ulegnie drzewo po usunięciu danego punktu. Aby zrozumieć tę punktację, należy przyjrzeć się budowie binarnego drzewa decyzyjnego.
Proces decyzyjny w drzewie binarnym można zobrazować jako drogę, którą punkt musi pokonać od korzenia drzewa do swojego liścia. W każdym wierzchołku drzewa podejmowana jest decyzja, którą z dwóch gałęzi podąży dany punkt. Przyjmijmy, że takiej decyzji przypisywana jest liczba 0, jeśli punkt wędruje lewą gałęzią, oraz 1 w przeciwnym przypadku. W ten sposób poszczególne punkty możemy jednoznacznie opisać pewnym ciągiem binarnym. Przykładowo, punkt a z rysunku 2. można przedstawić jako (0 0), natomiast punkt c jako (0 1 1). Zauważmy, że liczba bitów w takim ciągu odpowiada głębokości, na jakiej znajduje się dany punkt. Zbiór takich punktów w postaci ciągów binarnych pośrednio reprezentuje stopień skomplikowania drzewa. W algorytmie RRCF liczba bitów potrzebna do opisania wszystkich punktów w drzewie jest miarą jego złożoności [1].
Rys, 2 - Schemat reprezentacji drzewa przy pomocy ciągów binarnych
W lewej części rysunku 3. przedstawione zostało drzewo decyzyjne, które składa się z poddrzew A i B oraz punktu x. Po usunięciu punktu x z tego drzewa tracimy odpowiadającą mu regułę decyzyjną, która oddzieliła ten punkt, a tym samym prowadzący do niego wierzchołek. W wyniku powstaje drzewo przedstawione z prawej strony. Zauważmy, że po takiej operacji zmienia się reprezentacja bitowa wszystkich punktów należących do poddrzewa A – każdy z nich traci jeden bit. Oznacza to, że usunięcie x zmniejszyło złożoność drzewa o wartość równą liczbie punktów znajdujących się w A.
W ten sposób możliwe jest przypisanie każdemu punktowi wartości liczbowej, która wskazuje liczbę punktów znajdujących się w gałęzi wychodzącej z tego samego węzła. Losowe tworzenie podziałów sprawia, że im bardziej pewien punkt oddalony jest od pozostałych, tym większe prawdopodobieństwo jego oddzielenia w początkowych etapach procesu. Jednocześnie można oczekiwać, że do „bliźniaczej” gałęzi takiego punktu trafi większa liczba pozostałych obserwacji. Tym prostym sposobem otrzymana zostaje punktacja dla poszczególnych punktów. Im większa jest relatywna wartość tej miary, tym bardziej punkt może różnić się od pozostałych. Autorzy algorytmu nazwali ją mianem przemieszczenia (z ang. displacement) oraz dowiedli, że możliwe jest wyliczanie jej w efektywny sposób. Co ważne, algorytm jest odporny na grupy punktów odstających dzięki obliczaniu wartości przemieszczenia dla całych poddrzew. Pozwala to na zachowanie jakości detekcji nawet w sytuacjach, gdy do zbioru wkradły się niewykryte wcześniej anomalie.
Szybki, lekki i odporny
Choć algorytm dobrze sprawdza się w detekcji anomalii w standardowych zbiorach danych, to został skonstruowany głównie z myślą o szeregach czasowych. Dla takiego rodzaju danych wykrywane są nagłe i nieoczekiwane różnice, które nie pasują do historii obserwacji. Przykład działania algorytmu widoczny jest na rysunku 4. Dzięki swojej budowie RRCF jest odporny na zmiany danych w czasie spowodowane trendem oraz sezonowością.
Niewątpliwą zaletą algorytmu jest szybkość działania – RRCF nie wymaga skomplikowanego procesu trenowania, a anomalie mogą być wykrywane już od pierwszych obserwacji. Dodatkowo algorytm uczy się na bieżąco, natychmiast uwzględniając każdy nowo poznany punkt do oceny kolejnych. Na uwagę zasługuje również skuteczność detekcji w porównaniu z podobnymi metodami oraz wszechstronność. Dobrze sprawdza się także w wielowymiarowych zbiorach danych. Implementacja algorytmu dostępna jest w open-sourcowej bibliotece rrcf dostępnej dla języka Python, która pozwala na szybkie i łatwe wykorzystanie go do własnych potrzeb [3].
Adrian Stworzyjanek
Data Scientist
adrian.stworzyjanek@bitpeak.pl
Bibliografia
[1] S. Guha, N. Mishra, G. Roy, i O. Schrijvers, „Robust random cut forest based anomaly detection on streams”, w International conference on machine learning, 2016, s. 2712–2721.
[2] „How RCF Works - Amazon SageMaker”. https://docs.aws.amazon.com/sagemaker/latest/dg/rcf_how-it-works.html (udostępniono grudz. 11, 2020).
[3] M. D. Bartos, A. Mullapudi, i S. C. Troutman, „rrcf: Implementation of the Robust Random Cut Forest algorithm for anomaly detection on streams”, Journal of Open Source Software, t. 4, nr 35, s. 1336, 2019.