«Возможные решения данной проблемы появляются как листья дерева, каждый узел которого представляет точку обсуждения и решения». — Никлаус Вирт

Что такое дерево решений?

Дерево решений — это подход к машинному обучению, который использует перевернутую древовидную структуру для моделирования связи между независимыми переменными и зависимой переменной. — Фредерик Нванганга

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

Определение: теория принятия решений – это раздел прикладной теории вероятностей, связанный с теорией принятия решений, основанной на присвоении вероятностей различным факторам и приписывании числовых последствий результату.

Деревья решений с разных сторон

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

Дерево решений настолько удобно, что его использование сильно различается, а более точное определение больше зависит от его функции. Есть несколько других способов обучения деревьям решений:

  • Набор вопросов — вопросов, которые используются для принятия решения — которые имеют несколько результатов. Эти результаты могут привести к менее важным последующим вопросам. И эти дополнительные вопросы могут привести к нескольким результатам с большим количеством дополнительных вопросов и так далее, пока не будет принято окончательное решение, отвечающее на все вопросы и последующие действия.
  • Или просто набор правил «если-то», которые принимают решение на основе заданного набора условий.

Дерево решений в машинном обучении

Дерево решений — это метод контролируемого машинного обучения, который можно использовать для завершения задач как регрессии, так и классификации.

Способ разделения данных, используемый деревьями решений, называется рекурсивным секционированием.

  • В задачах классификации данные разбиваются на подгруппы таким образом, чтобы максимизировать сходство (чистоту/однородность) между элементами подгрупп.
  • В то время как в задачах регрессии рекурсивное разбиение используется для создания дочерних узлов, которые являются более чистыми, чем их родительские узлы.

Пример классификации

Взяв в качестве примера настроение Губки Боба Квадратные Штаны, на основе исторических данных можно выделить два фактора, влияющих на то, счастлив он или расстроен. В следующей таблице приведены некоторые из них:

Итак, если всю таблицу настроений мистера Квадратных Штанов визуализировать в виде точечной диаграммы, она будет выглядеть следующим образом:

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

Пытаясь разделить данные, проводится вертикальная линия, чтобы отделить счастливого Губку Боба от расстроенного Губки Боба, принимая во внимание только одну особенность — количество медуз, на которых охотились. Вертикальная линия под номером 10 по оси x может работать как разделитель, поэтому, если количество добытых медуз меньше 10, Губка Боб расстраивается, иначе он счастлив.

Но, как видно из графика, есть несколько неправильно классифицированных образцов. Чтобы сделать классификацию лучше, рассмотрение другой функции также может повысить производительность. Таким образом, добавление горизонтальной линии (в точке 20 по оси Y) может улучшить разделение данных.

Как можно заметить, горизонтальная линия усилила классификацию.

Эти линии представляют собой условия, на основе которых производится классификация. Линии на графике делят график на 4 области. Интерпретация этих областей как условий будет следующей:

  • Если количество медуз ‹ 10 и температура ‹ 20, то Мистер Квадратные Штаны счастлив.
  • Если количество медуз ‹ 10 и температура › 20, то Мистер Квадратные Штаны расстроен.
  • Если количество медуз › 10 и температура ‹ 20, то Мистер Квадратные Штаны расстроен.
  • Если количество медуз › 10 и температура › 20, то Мистер Квадратные Штаны счастлив.

Но при наличии всего 2 линий на графике несколько образцов классифицируются неправильно. Таким образом, добавление дополнительных строк может повысить эффективность классификации, но также может привести к переоснащению, что является одним из недостатков деревьев решений.

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

Представление дерева решений

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

Измерения чистоты

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

Цель состоит в том, чтобы максимально уменьшить количество неточностей или неопределенности в данных.

Прирост информации иэнтропия (используется в ID3):

Энтропия – это показатель теории информации (варьируется от 0 до 1), который используется для измерения степени нечистоты (несходства/беспорядка) в данных. . Чем он меньше, тем чище данные.

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

Индекс Джини (используется в CART):

Статистическая функция для измерения того, насколько хорошо было разбито дерево решений. Он выводит значение (варьируется от 0 до 1), где:

  • 0 указывает, что все данные принадлежат только одному классу.
  • 1 подразумевает, что данные распределены по оси z случайным образом по разным классам.
  • 0.5 предполагает, что данные равномерно распределены по некоторым классам.

Более высокий индекс Джини указывает на большую разницу.

Заключительные слова

Деревья решений помогают вам оценить варианты. Деревья решений — отличные инструменты, помогающие выбрать один из нескольких вариантов действий. Они представляют собой высокоэффективную структуру, в рамках которой вы можете раскладывать варианты и исследовать возможные результаты выбора этих вариантов. — команда контента Minds Tool

Дерево решений — очень эффективная модель как для задач классификации, так и для задач регрессии, и оно лежит в основе очень функциональных и эффективных моделей, таких как модели случайного леса и XGBoost.