Loading AI tools
средство поддержки принятия решений Из Википедии, свободной энциклопедии
Дерево принятия решений (также называют деревом классификации или регрессионным деревом) — средство поддержки принятия решений, использующееся в машинном обучении, анализе данных и статистике. Структура дерева представляет собой «листья» и «ветки». На рёбрах («ветках») дерева решения записаны признаки, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — признаки, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.
Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе.
Каждый лист представляет собой значение целевой переменной, изменённой в ходе движения от корня по рёбрам дерева до листа. Каждый внутренний узел сопоставляется с одной из входных переменных.
Дерево может быть также «изучено» разделением исходных наборов переменных на подмножества, основанные на проверке значений признаков. Это действие повторяется на каждом из полученных подмножеств. Рекурсия завершается тогда, когда подмножество в узле имеет те же значения целевой переменной, таким образом, оно не добавляет ценности для предсказаний. Процесс, идущий «сверху вниз», индукция деревьев решений (TDIDT)[1], является примером поглощающего «жадного» алгоритма, и на сегодняшний день является наиболее распространённой стратегией деревьев решений для данных, но это не единственная возможная стратегия.
В интеллектуальном анализе данных деревья решений могут быть использованы в качестве математических и вычислительных методов, чтобы помочь описать, классифицировать и обобщить набор данных, которые могут быть записаны следующим образом:
Зависимая переменная Y является целевой переменной, которую необходимо проанализировать, классифицировать и обобщить. Вектор состоит из входных переменных , , и т. д., которые используются для выполнения этой задачи.
При анализе решений посредством «дерева решений» используют визуальный и аналитический инструмент поддержки принятия решений для расчёта ожидаемых значений (или ожидаемой пользы) конкурирующих альтернатив.
Дерево решений состоит из трёх типов узлов:
На рисунке, представленном выше, дерево решений следует читать слева направо. Дерево решений не может содержать в себе циклические элементы, то есть каждый новый лист впоследствии может лишь расщепляться, отсутствуют сходящиеся пути. Таким образом, при конструировании дерева вручную, мы можем столкнуться с проблемой его размерности, поэтому, как правило, дерево решений мы можем получить с помощью специализированного программного обеспечения. Обычно дерево решений представляют в виде схематического чертежа, благодаря которому его проще воспринимать и анализировать.
Деревья решений, используемые при добыче данных, бывают двух основных типов:
Упомянутые выше термины впервые были введены Брейманом и др.[2] Перечисленные типы имеют некоторые сходства (рекурсивный алгоритмы построения), а также некоторые различия, такие, как критерии выбора разбиения в каждом узле.[2]
Некоторые методы позволяют построить более одного дерева решений (ансамбли деревьев решений):
Есть различные способы выбирать очередной признак:
На практике, в результате работы этих алгоритмов часто получаются слишком подробные деревья, которые при их дальнейшем применении дают много ошибок. Это связано с явлением переобучения. Для сокращения деревьев используют отсечение ветвей[англ.] (англ. pruning).
В отличие от остальных методов добычи данных, метод дерева принятия решений имеет несколько достоинств:
Регулирование глубины дерева — это техника, которая позволяет уменьшать размер дерева решений, удаляя участки дерева, которые имеют маленький вес.
Один из вопросов, который возникает в алгоритме дерева решений — это оптимальный размер конечного дерева. Так, небольшое дерево может не охватить ту или иную важную информацию о выборочном пространстве. Тем не менее, трудно сказать, когда алгоритм должен остановиться, потому что невозможно спрогнозировать, добавление какого узла позволит значительно уменьшить ошибку. Эта проблема известна как «эффект горизонта». Тем не менее, общая стратегия ограничения дерева сохраняется, то есть удаление узлов реализуется в случае, если они не дают дополнительной информации[12].
Регулирование глубины дерева должно уменьшить размер обучающей модели дерева без уменьшения точности её прогноза или с помощью перекрестной проверки. Есть много методов регулирования глубины дерева, которые отличаются измерением оптимизации производительности.
Сокращение дерева может осуществляться сверху вниз или снизу вверх. Сверху вниз — обрезка начинается с корня, снизу вверх — сокращается число листьев дерева. Один из простейших методов регулирования — уменьшение ошибки ограничения дерева. Начиная с листьев, каждый узел заменяется на самый популярный класс. Если изменение не влияет на точность предсказания, то оно сохраняется.
Предположим, что нас интересует, выиграет ли наша любимая футбольная команда следующий матч. Мы знаем, что это зависит от ряда параметров; перечислять их все — задача безнадёжная, поэтому ограничимся основными:
У нас есть некоторая статистика на этот счёт:
Соперник | Играем | Лидеры | Дождь | Победа |
---|---|---|---|---|
Выше | Дома | На месте | Да | Нет |
Выше | Дома | На месте | Нет | Да |
Выше | Дома | Пропускают | Нет | Нет |
Ниже | Дома | Пропускают | Нет | Да |
Ниже | В гостях | Пропускают | Нет | Нет |
Ниже | Дома | Пропускают | Да | Да |
Выше | В гостях | На месте | Да | Нет |
Ниже | В гостях | На месте | Нет | Да |
Хочется понять, выиграет ли наша команда в очередной игре.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.