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

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

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

Как работают деревья решений?

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

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

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

Чистые листовые узлы или точки данных, принадлежащие одному классу, легче получить в небольших деревьях. По мере роста дерева становится все труднее сохранять эту чистоту, что обычно приводит к тому, что в определенное поддерево попадает слишком мало данных. Это называется фрагментацией данных и часто приводит к переоснащению. Из-за этого деревья решений отдают предпочтение деревьям меньшего размера. Другими словами, деревья решений должны увеличивать сложность только в случае крайней необходимости. В конце концов, самое простое объяснение часто оказывается самым лучшим. Отсечение обычно используется для уменьшения сложности и предотвращения переобучения; это включает в себя отсечение ветвей, которые расходятся по несущественным чертам.

Выбор атрибутов узла

Получение информации

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

Рассмотрим пример вычисления энтропии:

примесь Джини

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

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

Деревья решений в играх

Теперь давайте посмотрим на роль деревьев решений в разработке игр. Я рассказывал о роли ИИ в разработке игр в предыдущем блоге, так что загляните сюда, если интересно.

Я возьму в качестве примера обычную игру: теннис. Цель переместить ракетку так, чтобы мяч отскакивал от нее, а не проходил мимо нее. У ИИ относительно простая задача решить, в каком направлении двигать ракетку.

Серия операторов if по сути представляет собой дерево решений. Этот пример тенниса аналогичен формальной идее искусственного интеллекта, известной как «дерево решений». Алгоритм должен перемещаться по древовидному расположению суждений этой системы, чтобы прийти к «листу», который несет в себе окончательное определение того, какой образ действий следует следовать.

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

  1. Узлы решений: решение между двумя вариантами в зависимости от оценки условия, при этом каждый вариант представлен в виде отдельного узла;
  2. Конечные узлы: направление движения, обозначающее окончательный выбор дерева.

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

Дерево решений явно выполняет ту же функцию, что и операторы if в предыдущем разделе, поэтому может быть не сразу ясно, в чем преимущество в этой ситуации. Однако здесь действует довольно общая структура, где каждый выбор имеет ровно 1 условие и 2 возможных исхода. Этот подход позволяет разработчику создавать ИИ из данных, отражающих решения в дереве, а не жестко кодировать их. Легко представить себе простой формат данных для описания дерева следующим образом:

Действие

1

Остался ли мяч от ракетки?

Да? Проверьте узел 2

Нет? Проверьте узел 3

2

Конец

Переместить ракетку влево

3

Мяч находится справа от ракетки?

Да? Перейти к узлу 4

Нет? Перейти к узлу 5

4

Конец

Переместите ракетку вправо

5

Конец

Ничего не делать

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

Заключение

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