Drzewo decyzyjne online
- Autor metody
- Domingos, P. & Hulten, G.
- Rok
- 2000
- Typ
- Incremental supervised classifier
- Rodzina
- Machine learning
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Drzewo decyzyjne online to drzewo decyzyjne, które rośnie przyrostowo z ciągłego strumienia danych, bez ponownego przeglądania przeszłych przykładów.
Dominujący algorytm, Drzewo Hoeffdinga (VFDT), wykorzystuje granicę Hoeffdinga, aby zdecydować, kiedy wystarczająca liczba przykładów została zaobserwowana w węźle, aby pewnie go podzielić, umożliwiając skalowalną klasyfikację w czasie rzeczywistym na potencjalnie nieskończonych strumieniach danych.
Intuicja stojąca za metodą
Standardowe drzewo decyzyjne jest budowane poprzez wielokrotne skanowanie pełnego zbioru danych w celu znalezienia najlepszych podziałów. W ustawieniach strumieniowych jest to niemożliwe, ponieważ dane przybywają pojedynczo i nie mogą być przechowywane. Podejście online przechowuje jedynie bieżące statystyki w każdym liściu. Gdy zgromadzi się wystarczająca liczba przykładów, granica Hoeffdinga — gwarancja statystyczna — potwierdza, że pozornie najlepszy podział pozostałby najlepszym podziałem, nawet gdybyśmy zobaczyli wszystkie możliwe przykłady. Dopiero wtedy drzewo faktycznie się dzieli, rosnąc z pojedynczego liścia w coraz głębszą strukturę, nigdy nie patrząc wstecz na przeszłe dane.
Historia
Podstawowy algorytm, Very Fast Decision Tree (VFDT) lub Hoeffding Tree, został wprowadzony przez Domingosa i Hultena na KDD 2000. Zastosowali oni nierówność Hoeffdinga do ograniczenia błędu w wyborze atrybutów podziału ze strumienia danych, umożliwiając asymptotycznie poprawne indukcję drzewa bez przechowywania przykładów. Hulten, Spencer i Domingos rozszerzyli to na strumienie z dryfem koncepcji w 2001 roku. Podejście to stało się kamieniem węgielnym frameworka MOA (Massive Online Analysis) i wpłynęło na pokolenie metod zespołowych strumieniowych.
Kiedy stosować
Użyj drzewa decyzyjnego online, gdy dane przybywają jako ciągły strumień, gdy przechowywanie pełnego zbioru danych jest niewykonalne ze względu na ograniczenia objętości lub prywatności, lub gdy model musi być aktualizowany w czasie rzeczywistym z każdą nową obserwacją. Jest dobrze przystosowany do strumieni czujników IoT, klasyfikacji strumieni kliknięć, wykrywania oszustw z ewoluującymi wzorcami i każdego ustawienia, w którym oczekiwany jest dryf koncepcji, a model musi się dostosować bez ponownego uczenia od podstaw. Nie używaj go, gdy zbiór danych jest mały i statyczny — standardowe drzewo decyzyjne lub las losowy będzie szybsze do wdrożenia i dokładniejsze. Unikaj go również, jeśli interpretowalność dokładnych progów podziału jest krytyczna, bez akceptacji, że progi mogą się zmieniać w czasie.
Ograniczenia i uwagi
- Dokładność na małych zbiorach danych jest zazwyczaj niższa niż w przypadku wsadowego drzewa decyzyjnego, ponieważ granica Hoeffdinga wymaga wielu przykładów, zanim zostaną dokonane wczesne podziały.
- Decyzje o podziale są nieodwracalne w podstawowym algorytmie; zły wczesny podział może się utrzymać, chyba że dodano jawne zastępowanie poddrzew.
- Dostrajanie parametru ufności delta i okresu karencji między ewaluacjami podziałów wymaga wiedzy dziedzinowej.
- Interpretowalność drzewa zmienia się w czasie w miarę dodawania nowych podziałów, co utrudnia statyczne raportowanie.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Przetwarza dane w jednym przebiegu ze stałą pamięcią na węzeł, skalując się do teoretycznie nieskończonych strumieni.
- Zapewnia teoretyczne gwarancje poprzez granicę Hoeffdinga, że podziały są asymptotycznie identyczne z podziałami drzewa wsadowego przy wystarczającej ilości danych.
- Może zawierać detektory dryfu, aby dostosować się do niestacjonarnych rozkładów bez pełnego ponownego uczenia.
- Dostarcza użyteczny model od pierwszego przykładu, w przeciwieństwie do metod wsadowych, które wymagają pełnego zbioru danych przed wygenerowaniem jakiejkolwiek predykcji.
- Naturalnie obsługuje ustawienia o wysokiej przepustowości, gdzie przechowywanie danych jest niepraktyczne lub prawnie ograniczone.
Zastosowania
- Wykrywanie oszustw w czasie rzeczywistym na strumieniach transakcji finansowych.
- Wykrywanie intruzji w sieci, gdzie statystyki ruchu przybywają w sposób ciągły.
- Klasyfikacja danych IoT i czujników na urządzeniach brzegowych z ograniczoną pamięcią.
- Modelowanie strumieni kliknięć lub zachowań użytkowników, gdzie objętość danych wyklucza pełne przechowywanie.
- Adaptacyjne filtrowanie spamu, gdy wzorce językowe w wiadomościach e-mail ewoluują w czasie.
- Klasyfikator strumieniowy bazowy, w stosunku do którego porównywane są bardziej złożone zespoły strumieniowe.
Jak to działa
Jak to działa
Każdy oznakowany przykład przybywa pojedynczo ze strumienia danych. Drzewo kieruje go od korzenia w dół przez istniejące podziały do odpowiedniego liścia, dokonując predykcji dla instancji przed jej oznakowaniem.
Wystarczające statystyki dla wszystkich kandydackich atrybutów podziału — takie jak warunkowe zliczenia klas lub średnia i wariancja Gaussa — są aktualizowane w liściu, który otrzymał instancję. Nie są przechowywane surowe dane; rosną tylko te zwarte podsumowania.
Granica Hoeffdinga (lub Chernoffa) epsilon = sqrt(R^2 * ln(1/delta) / (2n)) kwantyfikuje maksymalny błąd między obserwowanym najlepszym atrybutem podziału a prawdziwym najlepszym podziałem z prawdopodobieństwem co najmniej 1 - delta. W miarę wzrostu n, epsilon maleje do zera.
Wzór
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}Jeśli różnica w zysku informacyjnym między najlepszym a drugim najlepszym kandydatem na podział przekracza bieżącą granicę Hoeffdinga, liść jest zastępowany przez wewnętrzny węzeł podziału na zwycięskim atrybucie, a dwa nowe liczniki liści są inicjalizowane. W przeciwnym razie węzeł czeka na więcej danych.
Każda przybywająca instancja otrzymuje predykcję klasy z bieżącego drzewa, zanim jej etykieta zostanie użyta do aktualizacji. Opcjonalnie, detektory dryfu (np. ADWIN) monitorują wskaźniki błędów liści; gdy wykryty zostanie dryf koncepcji, poddrzewa mogą zostać zastąpione, aby model pozostał aktualny.
Częste pułapki
- Ustawienie granicy ufności Hoeffdinga delta zbyt luźno, powodując przedwczesne podziały na niereprezentatywnych wczesnych danych.
- Ignorowanie dryfu koncepcji — uruchamianie stacjonarnego drzewa online na danych ze zmieniającymi się rozkładami prowadzi do cichej degradacji dokładności.
- Porównywanie dokładności z modelem wsadowym wytrenowanym na wszystkich danych z tego samego strumienia, co daje modelowi wsadowemu niesprawiedliwą przewagę.
- Zapominanie, że liście przed pierwszym podziałem zawsze przewidują większość klasy widzianą do tej pory, co może być mylące we wczesnych fazach z niezbalansowanymi strumieniami.
Najczęściej zadawane pytania
Czym Drzewo Hoeffdinga różni się od standardowego drzewa decyzyjnego CART?
Drzewo CART skanuje pełny zbiór danych w każdym węźle, aby znaleźć globalnie najlepszy podział. Drzewo Hoeffdinga zamiast tego obserwuje przybywające pojedynczo przykłady i dopiero gdy teoria statystyczna gwarantuje, że pozornie najlepszy kandydat nadal wygrałby nawet z większą ilością danych — nie przechowując żadnych surowych przykładów — decyduje się na podział.
Czy drzewo decyzyjne online obsługuje dryf koncepcji?
Podstawowe Drzewo Hoeffdinga nie wykrywa dryfu automatycznie. Rozszerzenia, takie jak Concept-adapting Very Fast Decision Tree (CVFDT) i wersje połączone z detektorami dryfu ADWIN lub Page-Hinkley, mogą zastępować nieaktualne poddrzewa po wykryciu dryfu.
Czym jest okres karencji i jak go ustawić?
Okres karencji to liczba przykładów przybywających do liścia między kolejnymi ewaluacjami podziału. Większa wartość zmniejsza obciążenie obliczeniowe, ale opóźnia podziały; mniejsza wartość częściej ocenia podziały przy wyższym koszcie CPU. Typowe wartości domyślne wahają się od 200 do 1000 przykładów.
Czy drzewo decyzyjne online jest odpowiednie dla małych, statycznych zbiorów danych?
Nie. Dla małych, w pełni dostępnych zbiorów danych standardowe drzewo decyzyjne wsadowe lub las losowy prawie zawsze osiągnie lepszą dokładność przy znacznie mniejszej złożoności. Drzewa online są zaprojektowane specjalnie dla reżimu strumieniowego, wielkoskalowego lub ograniczonego zasobami.
Jak dokładność porównuje się z metodami wsadowymi na stałym zbiorze danych?
Przy wystarczającej ilości danych Drzewo Hoeffdinga zbiega do tego samego drzewa, które wyprodukowałby algorytm wsadowy, więc dokładność ostatecznie się wyrównuje. Na początku strumienia, zanim liście zobaczyły wiele przykładów, dokładność jest niższa niż w przypadku drzewa wsadowego wytrenowanego na tych samych danych widzianych do tej pory.
Pokrewne metody
Źródła
Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.
Otwórz odnośnik do publikacjiSkopiowano.Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.
Otwórz odnośnik DOISkopiowano.