Online Random Forest
- Автор метода
- Saffari, A. et al.
- Год
- 2009
- Тип
- Incremental ensemble (streaming decision trees)
- Семейство
- Machine learning
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Online Random Forest (ORF) расширяет классический Random Forest для потоковых сценариев, инкрементально обновляя каждое дерево по мере поступления новых наблюдений без хранения или повторного использования полного обучающего набора.
Алгоритмы, такие как Adaptive Random Forests (ARF), добавляют обнаружение дрейфа, чтобы ансамбль адаптировался при изменении распределения данных с течением времени.
Интуиция метода
Классический Random Forest требует весь набор данных заранее для построения своих деревьев. Online Random Forest заменяет пакетную бутстрэп-выборку трюком с онлайн-бэггингом, взвешенным по Пуассону: каждое поступающее наблюдение передается каждому дереву, которое решает — путем выборки пуассоновского числа — сколько раз использовать этот пример в качестве новой точки обучения. Деревья растут инкрементально, используя критерии онлайн-поиска разбиений (например, границы Хоффдинга), а модуль обнаружения дрейфа следит за дрейфом концепции, заменяя устаревшие деревья новыми. Результатом является лес, который непрерывно обучается на потоке, при этом объединяя несколько разнообразных деревьев для снижения дисперсии.
История
Онлайн-бэггинг был формализован Oza & Russell (2001) как пуассоновская взвешенная аппроксимация бутстрэп-агрегации. Saffari et al. (2009) представили On-line Random Forests, объединяющие онлайн-бэггинг со случайным выбором признаков и критериями разбиения на основе Хоффдинга для потоков компьютерного зрения. Gomes et al. (2017) представили Adaptive Random Forests (ARF), добавив обнаружение дрейфа на дерево с помощью ADWIN, и продемонстрировали точность на уровне современных на эталонных задачах классификации потоков данных. ARF стал стандартным базовым решением в фреймворке MOA (Massive Online Analysis).
Когда применять
Используйте Online Random Forest, когда данные поступают непрерывно или большими пакетами, которые не могут храниться в памяти, когда дрейф концепции вероятен (например, финансовые потоки, сенсорные сети, журналы поведения пользователей) или когда требуются предсказания с низкой задержкой до того, как полный набор данных будет доступен. Он также естественно подходит для приложений, где размеченные данные поступают со временем. Избегайте его, когда полный набор данных удобно помещается в памяти, а переобучение доступно — в этом случае стандартный Random Forest, обученный офлайн, обычно будет более точным и простым в проверке. Избегайте его также, когда вам нужны стабильные, воспроизводимые ранжирования важности признаков, поскольку онлайн-леса дают менее стабильные оценки важности, чем их пакетные аналоги.
Ограничения и замечания
- Решения о разбиении, принятые на ранних этапах при разреженных данных, могут быть субоптимальными и трудными для пересмотра.
- Оценки важности признаков менее стабильны, чем в пакетном Random Forest.
- Настройка гиперпараметров (количество деревьев, пороги обнаружения дрейфа) более сложна в потоковом контексте.
- Оценка требует специализированных протоколов на основе потока (преквенциальных/тест-перед-обучением), которые отличаются от стандартной кросс-валидации.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Обучается на потоковых данных с постоянной памятью на дерево, независимо от длины потока.
- Адаптируется к дрейфу концепции при сопряжении с механизмами обнаружения дрейфа, такими как ADWIN.
- Наследует преимущества снижения дисперсии ансамблевой агрегации даже в онлайн-режиме.
- Предоставляет пригодные для использования предсказания с первых нескольких наблюдений, улучшаясь со временем.
- Нет необходимости хранить или повторно использовать полный исторический набор данных.
Применение
- Обнаружение мошенничества и вторжений в реальном времени на сетевых или транзакционных потоках.
- Прогнозирование предиктивного обслуживания по потокам датчиков, где распределения смещаются по мере старения оборудования.
- Прогнозирование коэффициента кликабельности в рекламе, где поведение пользователей меняется ежедневно.
- Медицинский мониторинг, где состояние пациента постоянно меняется со временем.
- Экологический и климатический мониторинг с нестационарными сезонными закономерностями.
Как это работает
Как это работает
Инициализируется набор из T деревьев (или деревьев Хоффдинга). Каждое дерево хранит достаточные статистики на узел — счетчики классов или сумму квадратов для регрессии — вместо хранения необработанных наблюдений, что делает модель константной по памяти для каждого дерева.
Для каждого поступающего наблюдения каждое дерево независимо выбирает k из распределения Пуассона(1) и рассматривает наблюдение как k виртуальных репликаций самого себя. Когда k = 0, дерево пропускает точку (действуя как его внемешочная выборка). Это аппроксимирует бутстрэп-выборку без необходимости полного набора данных.
Формула
k \sim \text{Poisson}(\lambda),\; \lambda=1Каждое дерево обновляет достаточные статистики в своем активном листе. Разбиение инициируется, когда статистически обоснованный критерий (такой как граница Хоффдинга) указывает, что лучшее разбиение вряд ли изменится с большим количеством данных, после чего лист расширяется в узел, и инициализируются новые листья.
Необязательный модуль обнаружения дрейфа (например, ADWIN) отслеживает ошибку предсказания каждого дерева на потоке внемешочных объектов. Когда обнаружено статистически значимое ухудшение, затронутое дерево сбрасывается или заменяется свежеинициализированным деревом, поддерживая актуальность ансамбля для развивающихся распределений.
В любой момент все активные деревья голосуют: большинство голосов для классификации или среднее предсказание для регрессии. Деревья, обработавшие очень мало примеров, могут быть взвешены меньше или исключены до тех пор, пока они не накопят достаточно данных для надежных голосов.
Формула
\hat{y} = \text{mode/mean of active trees}Частые ошибки
- Оценка с использованием стандартной k-кратной кросс-валидации, которая предполагает i.i.d. данные и игнорирует временной порядок.
- Игнорирование дрейфа концепции: отказ от включения компонента обнаружения дрейфа, когда распределение данных меняется со временем.
- Сравнение точности онлайн-леса напрямую с пакетным Random Forest, обученным на полном историческом наборе данных — последний имеет присущее ему информационное преимущество.
- Использование слишком малого количества деревьев в начале потока до того, как каждое дерево увидит достаточно данных для надежных разбиений.
- Забывание о том, что бэггинг, взвешенный по Пуассону, аппроксимирует бутстрэп — он не воспроизводит точно статистические свойства пакетного бутстрэпа.
Часто задаваемые вопросы
Чем Online Random Forest отличается от стандартного Random Forest?
Стандартный Random Forest обучает все деревья одновременно на полном наборе данных с использованием бутстрэп-выборки. Online Random Forest заменяет пакетный бутстрэп пуассоновским взвешенным онлайн-бэггингом, инкрементально обновляет разбиения деревьев по мере поступления каждого наблюдения и опционально обнаруживает и адаптируется к дрейфу концепции — все это без хранения прошлых данных.
Что такое трюк с пуассоновским взвешиванием?
Каждый поступающий пример показывается каждому дереву k раз, где k выбирается из Пуассона(1). Поскольку математическое ожидание k равно 1, а k = 0 с вероятностью ~37%, это статистически аппроксимирует процесс бутстрэпа (выборка с возвращением) без необходимости полного набора данных в памяти.
Как следует оценивать онлайн-лес случайных деревьев?
Используйте преквенциальный протокол (тест-перед-обучением): для каждого поступающего наблюдения сначала предскажите с помощью текущей модели, запишите ошибку, затем обновите модель. Это дает несмещенную, упорядоченную по времени оценку предсказательной производительности без утечки данных.
Когда следует добавлять обнаружение дрейфа?
Всякий раз, когда процесс генерации данных, вероятно, изменится со временем — например, предпочтения пользователей, финансовые рынки или механические системы, которые изнашиваются. Без обнаружения дрейфа накапливаются устаревшие деревья и снижают точность ансамбля. ADWIN — распространенный, хорошо протестированный выбор.
Является ли Adaptive Random Forest тем же самым?
ARF — наиболее широко используемый вариант Online Random Forest. Он объединяет онлайн-бэггинг, случайный выбор признаков и обнаружение дрейфа ADWIN на дерево, и доступен в библиотеках MOA и scikit-multiflow/River. Термин 'Online Random Forest' часто относится к семейству в целом; ARF — это конкретная, высоко рекомендуемая реализация.
Похожие методы
Источники
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.
Открыть ссылку на публикациюСкопировано.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.
Открыть ссылку DOIСкопировано.