Online Random Forest
- Autor metody
- Saffari, A. et al.
- Rok
- 2009
- Typ
- Incremental ensemble (streaming decision trees)
- Rodzina
- Machine learning
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Online Random Forest (ORF) rozszerza klasyczny Random Forest na ustawienia strumieniowe, aktualizując każde drzewo przyrostowo w miarę napływania nowych obserwacji, bez przechowywania lub odtwarzania pełnego zbioru treningowego.
Algorytmy takie jak Adaptive Random Forests (ARF) dodają detekcję dryfu, dzięki czemu zespół adaptuje się, gdy rozkład danych zmienia się w czasie.
Intuicja stojąca za metodą
Klasyczny Random Forest wymaga całego zbioru danych z góry do wzrostu swoich drzew. Online Random Forest zastępuje próbkowanie bootstrap wsadowy sztuczką ważenia Poissona online: każda napływająca obserwacja jest przekazywana do każdego drzewa, które decyduje — poprzez losowanie liczby Poissona — ile razy potraktować ten przykład jako nowy punkt treningowy. Drzewa rosną przyrostowo, używając kryteriów wyszukiwania podziałów online (np. ograniczeń Hoeffdinga), a moduł detekcji dryfu monitoruje dryf koncepcji, zastępując przestarzałe drzewa nowymi. Wynikiem jest las, który uczy się ciągle ze strumienia, jednocześnie łącząc wiele zróżnicowanych drzew w celu redukcji wariancji.
Historia
Online bagging został sformalizowany przez Oza & Russella (2001) jako aproksymacja ważona Poissona do agregacji bootstrap. Saffari i in. (2009) wprowadzili On-line Random Forests, łącząc online bagging z losowym wyborem cech i kryteriami podziału opartymi na Hoeffdingu dla strumieni wizji komputerowej. Gomes i in. (2017) wprowadzili Adaptive Random Forests (ARF), dodając detekcję dryfu na drzewo za pomocą ADWIN, i zademonstrowali stan techniki w zadaniach klasyfikacji strumieni danych. ARF stał się standardową bazą w ramach MOA (Massive Online Analysis).
Kiedy stosować
Używaj Online Random Forest, gdy dane napływają ciągle lub w dużych partiach, których nie można przechowywać w pamięci, gdy dryf koncepcji jest prawdopodobny (np. strumienie finansowe, sieci czujników, logi zachowań użytkowników) lub gdy wymagane są predykcje o niskim opóźnieniu przed dostępnością pełnego zbioru danych. Jest to również naturalne dopasowanie do zastosowań, gdzie oznakowane dane napływają stopniowo w czasie. Unikaj go, gdy pełny zbiór danych mieści się komfortowo w pamięci, a ponowne trenowanie jest opłacalne — w takim przypadku standardowy Random Forest trenowany offline zazwyczaj będzie dokładniejszy i prostszy do walidacji. Unikaj go również, gdy potrzebujesz stabilnych, powtarzalnych rankingów ważności cech, ponieważ lasy online generują mniej stabilne oszacowania ważności niż ich odpowiedniki wsadowe.
Ograniczenia i uwagi
- Decyzje o podziale podjęte wcześnie przy rzadkich danych mogą być suboptymalne i trudne do poprawienia.
- Oszacowania ważności cech są mniej stabilne niż w przypadku wsadowego Random Forest.
- Strojenie hiperparametrów (liczba drzew, progi detekcji dryfu) jest bardziej złożone w kontekście strumieniowym.
- Ewaluacja wymaga dedykowanych protokołów strumieniowych (prekwencyjnych/testuj-następnie-trenuj), które różnią się od standardowej walidacji krzyżowej.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Uczy się ze strumieniowych danych ze stałą pamięcią na drzewo, niezależnie od długości strumienia.
- Adaptuje się do dryfu koncepcji w połączeniu z mechanizmami detekcji dryfu, takimi jak ADWIN.
- Dziedziczy korzyści z redukcji wariancji agregacji zespołu nawet w ustawieniu online.
- Zapewnia użyteczne predykcje od pierwszych kilku obserwacji, poprawiając się w czasie.
- Brak potrzeby przechowywania lub odtwarzania pełnego historycznego zbioru danych.
Zastosowania
- Wykrywanie oszustw i intruzji w czasie rzeczywistym na strumieniach sieciowych lub transakcyjnych.
- Konserwacja predykcyjna ze strumieni czujników, gdzie rozkłady przesuwają się wraz ze starzeniem się sprzętu.
- Predykcja współczynnika klikalności w reklamie, gdzie zachowania użytkowników ewoluują codziennie.
- Monitorowanie medyczne, gdzie stan pacjenta stale się zmienia w czasie.
- Sondowanie środowiska i klimatu z niestacjonarnymi wzorcami sezonowymi.
Jak to działa
Jak to działa
Inicjalizowany jest zbiór T drzew (lub drzew Hoeffdinga). Każde drzewo przechowuje statystyki wystarczające na liść — zliczenia klas lub sumy kwadratów dla regresji — zamiast przechowywać surowe obserwacje, co sprawia, że model ma stałą pamięć na drzewo.
Dla każdej napływającej obserwacji, każde drzewo niezależnie losuje k z rozkładu Poissona(1) i traktuje obserwację jako k wirtualnych replikacji siebie. Gdy k = 0, drzewo pomija punkt (działając jako jego próbka poza torbą). Aproksymuje to próbkowanie bootstrap bez konieczności posiadania całego zbioru danych.
Wzór
k \sim \text{Poisson}(\lambda),\; \lambda=1Każde drzewo aktualizuje statystyki wystarczające na swoim aktywnym liściu. Podział jest wyzwalany, gdy kryterium oparte na podstawach statystycznych (takie jak ograniczenie Hoeffdinga) wskazuje, że najlepszy podział prawdopodobnie się nie zmieni przy większej ilości danych, po czym liść jest rozwijany w węzeł wewnętrzny i inicjalizowane są nowe liście.
Opcjonalny moduł detekcji dryfu (np. ADWIN) monitoruje błąd predykcji każdego drzewa na strumieniu poza torbą. Gdy wykryte zostanie statystycznie istotne pogorszenie, dotknięte drzewo jest resetowane lub zastępowane nowo zainicjowanym drzewem, utrzymując zespół aktualnym z ewoluującymi rozkładami.
W dowolnym momencie wszystkie aktywne drzewa głosują: głos większościowy dla klasyfikacji lub średnia predykcja dla regresji. Drzewa, które przetworzyły bardzo mało przykładów, mogą być ważone niżej lub wykluczone, dopóki nie zgromadzą wystarczającej ilości danych, aby oddać wiarygodne głosy.
Wzór
\hat{y} = \text{mode/mean of active trees}Częste pułapki
- Ewaluacja za pomocą standardowej walidacji krzyżowej k-krotnej, która zakłada dane i.i.d. i ignoruje porządek czasowy.
- Ignorowanie dryfu koncepcji: brak uwzględnienia komponentu detekcji dryfu, gdy rozkład danych zmienia się w czasie.
- Porównywanie dokładności lasu online bezpośrednio z wsadowym Random Forest wytrenowanym na pełnym historycznym zbiorze danych — ten ostatni ma inherentną przewagę informacyjną.
- Używanie zbyt małej liczby drzew na wczesnym etapie strumienia, zanim każde drzewo zobaczyło wystarczająco dużo danych, aby dokonać wiarygodnych podziałów.
- Zapominanie, że ważenie Poissona aproksymuje bootstrap — nie odtwarza dokładnie właściwości statystycznych bootstrapu wsadowego.
Najczęściej zadawane pytania
Czym Online Random Forest różni się od standardowego Random Forest?
Standardowy Random Forest trenuje wszystkie drzewa jednocześnie na pełnym zbiorze danych przy użyciu próbkowania bootstrap. Online Random Forest zastępuje bootstrap wsadowy ważeniem Poissona online, aktualizuje podziały drzew przyrostowo w miarę napływania każdej obserwacji i opcjonalnie wykrywa dryf koncepcji i adaptuje się do niego — wszystko bez przechowywania przeszłych danych.
Co to jest sztuczka ważenia Poissona?
Każdy napływający przykład jest pokazywany każdemu drzewu k razy, gdzie k jest losowane z Poissona(1). Ponieważ wartość oczekiwana k wynosi 1, a k = 0 z prawdopodobieństwem ~37%, statystycznie aproksymuje to proces bootstrap (próbkowanie ze zwracaniem) bez potrzeby posiadania całego zbioru danych w pamięci.
Jak powinienem ocenić las online?
Użyj protokołu prekwencyjnego (testuj-następnie-trenuj): dla każdej napływającej obserwacji najpierw przewiduj za pomocą obecnego modelu, zapisz błąd, a następnie zaktualizuj model. Daje to nieobciążone, uporządkowane czasowo oszacowanie wydajności predykcyjnej bez wycieku danych.
Kiedy powinienem dodać detekcję dryfu?
Zawsze, gdy proces generowania danych prawdopodobnie się zmieni w czasie — na przykład preferencje użytkowników, rynki finansowe lub systemy mechaniczne, które się zużywają. Bez detekcji dryfu gromadzą się przestarzałe drzewa i obniżają dokładność zespołu. ADWIN jest powszechnym, dobrze przetestowanym wyborem.
Czy Adaptive Random Forest to to samo?
ARF jest najszerzej stosowanym wariantem Online Random Forest. Łączy online bagging, losowy wybór cech i detekcję dryfu ADWIN na drzewo, i jest dostępny w bibliotekach MOA i scikit-multiflow/River. Termin 'Online Random Forest' często odnosi się ogólnie do rodziny; ARF jest specyficzną, wysoce zalecaną implementacją.
Pokrewne metody
Źródła
Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.
Otwórz odnośnik do publikacjiSkopiowano.Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.
Otwórz odnośnik DOISkopiowano.