Skip to content
Назад к результатам поиска

Чрезвычайно случайные деревья

Автор метода
Geurts, P.; Ernst, D.; Wehenkel, L.
Год
2006
Тип
Ensemble (extremely randomized decision trees)
Семейство
Machine learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Extra Trees (чрезвычайно случайные деревья), представленный Geurts, Ernst и Wehenkel в 2006 году, представляет собой ансамбль деревьев решений, который заходит дальше в рандомизации, чем Random Forest.

Как кандидатные признаки, так и пороги разбиения выбираются полностью случайным образом на каждом узле, что исключает жадный поиск по порогам. Эта дополнительная случайность снижает дисперсию, часто соответствует или превосходит точность Random Forest и работает значительно быстрее во время обучения.

Интуиция метода

Random Forest уже декореллирует деревья, случайным образом выбирая подмножества признаков при каждом разбиении, но он все еще ищет лучший порог среди этих признаков. Extra Trees идет на шаг дальше: для каждого кандидатного признака он выбирает случайный порог, а не оптимизирует его. На первый взгляд это может показаться вредным для точности, но поскольку результирующие деревья еще меньше коррелируют друг с другом, усреднение по ансамблю компенсирует больше дисперсии. Потери от любого отдельного плохого разбиения ничтожны при усреднении по многим деревьям, а выигрыш в скорости от отсутствия поиска оптимального порога существенен.

История

Extra Trees был предложен Пьером Гертсом, Дамьеном Эрнстом и Луисом Веенкелем в статье по Machine Learning 2006 года. Авторы показали, что введение полной рандомизации порогов разбиения — вместо поиска оптимальных разрезов — существенно снижает дисперсию при небольшом увеличении смещения. С тех пор метод стал стандартной альтернативой Random Forest в экосистеме scikit-learn и широко используется как быстрая, высокоточная базовая линия для бенчмарков табличных данных.

Когда применять

Используйте Extra Trees, когда вам нужна быстрая тренировка и высокая точность на табличных данных с непрерывными или смешанными типами признаков. Он особенно полезен, когда время обучения ограничено — его отказ от оптимизации порогов делает его значительно быстрее Random Forest при сопоставимой точности. Он подходит для задач классификации и регрессии с умеренными или большими выборками (примерно 50 или более наблюдений). Предпочитайте Random Forest или градиентный бустинг, если вам нужны встроенные оценки вне выборки или если шум в данных очень высок и вы подозреваете, что полностью случайные пороги вредят точности. Для очень маленьких наборов данных более простые модели, такие как логистическая регрессия или одно дерево решений, безопаснее и более интерпретируемы.

Ограничения и замечания

  • Отсутствие встроенной оценки вне выборки (в отличие от Random Forest), поэтому для несмещенной оценки ошибок требуется кросс-валидация.
  • Полностью случайные пороги могут навредить на очень зашумленных данных, где оптимальные разбиения информативны.
  • Черный ящик: не предоставляет явных коэффициентов, что ограничивает интерпретируемость для аудиторий, ожидающих оценки величины эффекта.
  • Потребление памяти растет с количеством деревьев и глубиной дерева.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Более быстрая тренировка, чем у Random Forest, поскольку на каждом разбиении не выполняется оптимизация порогов.
  • Высокое разнообразие между деревьями приводит к сильному снижению дисперсии и часто соответствует или превосходит точность Random Forest.
  • Обрабатывает смешанные типы признаков и нелинейные взаимодействия без предположений о предварительной обработке.
  • Предоставляет собственные оценки важности признаков для ранжирования и отбора переменных.
  • Хорошо масштабируется на высокоразмерные данные с множеством нерелевантных признаков.

Применение

  • Быстрые базовые модели классификации и регрессии на табличных данных.
  • Отбор признаков и ранжирование важности в высокоразмерных наборах данных.
  • Предиктивное моделирование в биоинформатике, дистанционном зондировании и анализе данных с датчиков.
  • Поиск гиперпараметров в конвейере, где скорость обучения имеет решающее значение.
  • Сценарии с большими данными, где время обучения Random Forest является непомерно высоким.

Как это работает

Как это работает

1

В отличие от Random Forest, Extra Trees по умолчанию обучает каждое дерево на всем обучающем наборе, а не на бутстреп-выборке. Это снижает смещение, вносимое выборкой, но означает отсутствие встроенного набора вне выборки (out-of-bag); поэтому для честной оценки ошибок требуется кросс-валидация.

2

На каждом внутреннем узле выбирается случайное подмножество признаков. Для каждого кандидатного признака порог разбиения выбирается равномерно случайным образом из наблюдаемого диапазона значений этого признака — оптимальная точка отсечения не ищется. Выбирается пара признак-порог, дающая наилучшую оценку (например, снижение Gini impurity) среди этих случайных кандидатов.

3

Деревья по умолчанию растут до полной глубины, что означает, что листья максимально чисты. Полная глубина в сочетании со случайными разбиениями снижает дисперсию по всему ансамблю: отдельные деревья имеют высокую дисперсию, но очень разнообразны.

4

Предсказания всех деревьев объединяются: голосование большинством для классификации и среднее значение для регрессии. Сильное разнообразие между деревьями означает, что индивидуальные ошибки имеют тенденцию к взаимной компенсации, что делает ансамбль более стабильным, чем любое отдельное дерево.

Формула
\hat{y} = \text{mode/mean of } T \text{ trees}

Частые ошибки

  • Пропуск кросс-валидации и полагание на точность внутри выборки, поскольку по умолчанию оценка вне выборки не производится.
  • Игнорирование дисбаланса классов — используйте class_weight='balanced' или ресемплинг перед подгонкой.
  • Отчетность только по точности без дополнительных метрик, таких как F1, AUC или RMSE.
  • Рассмотрение рангов важности признаков как стабильных без проверки воспроизводимости по разным сидам (seeds).

Часто задаваемые вопросы

Чем Extra Trees отличается от Random Forest?

Оба являются ансамблями деревьев решений со случайными подмножествами признаков при каждом разбиении. Ключевое отличие в том, что Extra Trees выбирает пороги разбиения полностью случайным образом, а не оптимизирует их, и по умолчанию обучает на полном обучающем наборе, а не на бутстреп-выборках. Это делает Extra Trees быстрее и обычно приводит к более разнообразным, менее коррелированным деревьям.

Что мне следует предпочесть — Extra Trees или Random Forest?

Когда важна скорость обучения или данные относительно чистые, Extra Trees часто соответствует или превосходит точность Random Forest при более низких вычислительных затратах. Если вам нужна встроенная оценка вне выборки или ваши данные зашумлены (где лучшие пороги разбиения помогают), Random Forest безопаснее.

Сколько деревьев мне нужно?

Начните со 100 деревьев и увеличивайте их, пока производительность не стабилизируется на валидационном наборе или в кросс-валидации. Большее количество деревьев улучшает стабильность, но увеличивает потребление памяти и задержку предсказания.

Переобучается ли Extra Trees?

Отдельные деревья растут до полной глубины и могут переобучаться в изоляции, но усреднение по ансамблю сильно снижает дисперсию. Переобучение полного ансамбля обычно редко, хотя на очень маленьких наборах данных с большим количеством признаков оно все же может произойти.

Как оценить производительность модели без набора вне выборки?

Используйте k-кратную кросс-валидацию — обычно 5 или 10 фолдов. Оценивайте задачи классификации с помощью точности, F1 и AUC; оценивайте задачи регрессии с помощью RMSE и R-squared.

Похожие методы

Источники

  1. Geurts, P., Ernst, D. & Wehenkel, L. (2006). Extremely randomized trees. Machine Learning, 63(1), 3–42.

    Открыть ссылку DOI
    Скопировано.
  2. Extra-Trees. Wikipedia.

    Открыть ссылку на публикацию
    Скопировано.