Онлайн-дерево решений
- Автор метода
- Domingos, P. & Hulten, G.
- Год
- 2000
- Тип
- Incremental supervised classifier
- Семейство
- Machine learning
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Онлайн-дерево решений — это дерево решений, которое инкрементально растет на непрерывном потоке данных, не обращаясь повторно к прошлым примерам.
Доминирующий алгоритм, дерево Хоффдинга (VFDT), использует границу Хоффдинга, чтобы определить, когда на узле было замечено достаточно примеров для уверенного разделения, что обеспечивает масштабируемую классификацию в реальном времени на потенциально бесконечных потоках данных.
Интуиция метода
Стандартное дерево решений строится путем многократного сканирования всего набора данных для поиска наилучших разбиений. В потоковых условиях это невозможно, поскольку данные поступают по одному и не могут быть сохранены. Онлайн-подход сохраняет только текущую статистику в каждом листе. Когда накапливается достаточно примеров, граница Хоффдинга — статистическая гарантия — подтверждает, что кажущееся наилучшее разбиение останется наилучшим, даже если бы мы видели каждый возможный пример. Только тогда дерево фактически разделяется, вырастая из одного листа в постоянно углубляющуюся структуру, никогда не оглядываясь на прошлые данные.
История
Основополагающий алгоритм, очень быстрое дерево решений (VFDT) или дерево Хоффдинга, был представлен Домингосом и Халтеном на конференции KDD 2000. Он применил неравенство Хоффдинга для ограничения ошибки при выборе атрибутов разбиения из потока данных, что позволило асимптотически корректную индукцию дерева без хранения примеров. Халтен, Спенсер и Домингос расширили это на потоки с концептуальным дрейфом в 2001 году. Этот подход стал краеугольным камнем фреймворка MOA (Massive Online Analysis) и повлиял на поколение потоковых ансамблевых методов.
Когда применять
Используйте онлайн-дерево решений, когда данные поступают в виде непрерывного потока, когда хранение всего набора данных нецелесообразно из-за объема или ограничений конфиденциальности, или когда модель должна обновляться в реальном времени с каждым новым наблюдением. Оно хорошо подходит для потоков данных с IoT-датчиков, классификации кликстримов, обнаружения мошенничества с меняющимися паттернами и любой ситуации, где ожидается концептуальный дрейф и модель должна адаптироваться без переобучения с нуля. Не используйте его, когда набор данных мал и статичен — стандартное дерево решений или случайный лес будут быстрее в реализации и точнее. Также избегайте его, если интерпретируемость точных порогов разбиения критична без принятия того, что пороги могут меняться со временем.
Ограничения и замечания
- Точность на малых наборах данных обычно ниже, чем у пакетного дерева решений, потому что граница Хоффдинга требует много примеров, прежде чем будут сделаны ранние разбиения.
- Решения о разбиении необратимы в базовом алгоритме; плохое раннее разбиение может сохраняться, если не добавлена явная замена поддерева.
- Настройка параметра доверия delta и льготного периода между оценками разбиения требует предметных знаний.
- Интерпретируемость дерева меняется со временем по мере добавления новых разбиений, что затрудняет статическую отчетность.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Обрабатывает данные за один проход с постоянным объемом памяти на узел, масштабируясь до теоретически бесконечных потоков.
- Предоставляет теоретические гарантии через границу Хоффдинга, что разбиения асимптотически идентичны разбиениям пакетного дерева при достаточном количестве данных.
- Может включать детекторы дрейфа для адаптации к нестационарным распределениям без полного переобучения.
- Предоставляет пригодную для использования модель с самого первого примера, в отличие от пакетных методов, которые требуют полного набора данных до получения какого-либо предсказания.
- Естественно обрабатывает сценарии с высокой пропускной способностью, где хранение данных непрактично или юридически ограничено.
Применение
- Обнаружение мошенничества в реальном времени в потоках финансовых транзакций.
- Обнаружение сетевых вторжений, где статистика трафика поступает непрерывно.
- Классификация данных IoT и датчиков с ограниченными по памяти периферийными устройствами.
- Моделирование кликстримов или поведения пользователей, где объем данных исключает полное хранение.
- Адаптивная фильтрация спама по мере эволюции лингвистических паттернов в электронных письмах.
- Базовый потоковый классификатор, по отношению к которому сравниваются более сложные потоковые ансамбли.
Как это работает
Как это работает
Каждый размеченный пример поступает по одному из потока данных. Дерево направляет его от корня через существующие разбиения к соответствующему листу, делая предсказание для экземпляра до его разметки.
Достаточные статистики для всех атрибутов-кандидатов для разбиения — такие как условные по классам счетчики или гауссовы среднее и дисперсия — обновляются в листе, который получил экземпляр. Исходные данные не сохраняются; растут только эти компактные сводки.
Граница Хоффдинга (или Чернова) epsilon = sqrt(R^2 * ln(1/delta) / (2n)) количественно определяет максимальную ошибку между наблюдаемым наилучшим атрибутом разбиения и истинным наилучшим разбиением с вероятностью не менее 1 - delta. По мере роста n, epsilon стремится к нулю.
Формула
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}Если разница в приросте информации между лучшим и вторым лучшим кандидатами на разбиение превышает текущую границу Хоффдинга, лист заменяется внутренним узлом разбиения по выигрышному атрибуту, и инициализируются два новых счетчика листьев. В противном случае узел ожидает поступления дополнительных данных.
Каждый поступающий экземпляр получает предсказание класса от текущего дерева до того, как его метка будет использована для обновления. Опционально, детекторы дрейфа (например, ADWIN) отслеживают частоту ошибок листьев; при обнаружении концептуального дрейфа поддеревья могут быть заменены для поддержания актуальности модели.
Частые ошибки
- Слишком свободная установка параметра доверия Хоффдинга delta, что приводит к преждевременным разбиениям на нерепрезентативных ранних данных.
- Игнорирование концептуального дрейфа — запуск стационарного онлайн-дерева на данных с меняющимися распределениями приводит к незаметному снижению точности.
- Сравнение точности с пакетной моделью, обученной на всем наборе данных того же потока, что дает пакетной модели несправедливое преимущество.
- Забывание о том, что листья до их первого разбиения всегда предсказывают наиболее часто встречающийся класс, что может вводить в заблуждение на ранних этапах с несбалансированными потоками.
Часто задаваемые вопросы
Чем дерево Хоффдинга отличается от стандартного дерева решений CART?
Дерево CART сканирует весь набор данных в каждом узле, чтобы найти глобально лучшее разбиение. Дерево Хоффдинга вместо этого наблюдает за поступлением примеров по одному и принимает решение о разбиении только тогда, когда статистическая теория гарантирует, что кажущийся победитель все равно победит даже при большем количестве данных — без использования каких-либо сохраненных исходных примеров.
Обрабатывает ли онлайн-дерево решений концептуальный дрейф?
Базовое дерево Хоффдинга не обнаруживает дрейф автоматически. Расширения, такие как концептуально адаптирующееся очень быстрое дерево решений (CVFDT) и версии, объединенные с детекторами дрейфа ADWIN или Page-Hinkley, могут заменять устаревшие поддеревья при обнаружении дрейфа.
Что такое льготный период и как его следует устанавливать?
Льготный период — это количество примеров, поступающих в лист между последовательными оценками разбиения. Большее значение уменьшает вычисления, но задерживает разбиения; меньшее значение оценивает разбиения чаще при более высокой стоимости ЦП. Типичные значения по умолчанию варьируются от 200 до 1000 примеров.
Подходит ли онлайн-дерево решений для небольших, статических наборов данных?
Нет. Для небольших, полностью доступных наборов данных стандартное пакетное дерево решений или случайный лес почти всегда достигают лучшей точности с гораздо меньшей сложностью. Онлайн-деревья разработаны специально для потокового, крупномасштабного или ресурсно-ограниченного режима.
Как точность сравнивается с пакетными методами на фиксированном наборе данных?
При достаточном количестве данных дерево Хоффдинга сходится к тому же дереву, которое произвел бы пакетный алгоритм, поэтому точность в конечном итоге совпадает. В начале потока, до того как листья увидели много примеров, точность ниже, чем у пакетного дерева, обученного на тех же данных, которые были замечены к этому моменту.
Похожие методы
Источники
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.
Открыть ссылку на публикациюСкопировано.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.
Открыть ссылку DOIСкопировано.