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

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

Как использовать: Набор для обучения вводится в виде csv списка, в качестве разделителя используется точка с запятой. Первая строка считается метками характеристик и класса объекта (сначала характеристики, потом класс). Данные по умолчанию взяты из известного примера дерева решений играть или нет в теннис на улице. Объекты принадлежат к двум классам: "Играть" и "Не играть", в качестве характеристик используются "Осадки", "Температура", "Влажность" и "Ветер".

Дерево решений

Осадки;Температура;Влажность;Ветер;Класс Солнечно;Жарко;Высокая;Нет;Не играть Солнечно;Жарко;Высокая;Да;Не играть Переменная облачность;Жарко;Высокая;Нет;Играть Пасмурно;Умеренно;Высокая;Нет;Играть Пасмурно;Прохладно;Нормальная;Нет;Играть Пасмурно;Прохладно;Нормальная;Да;Не играть Переменная облачность;Прохладно;Нормальная;Да;Играть Солнечно;Умеренно;Высокая;Нет;Не играть Солнечно;Прохладно;Нормальная;Нет;Играть Пасмурно;Умеренно;Нормальная;Нет;Играть Солнечно;Умеренно;Нормальная;Да;Играть Переменная облачность;Умеренно;Высокая;Да;Играть Переменная облачность;Жарко;Нормальная;Нет;Играть Пасмурно;Умеренно;Высокая;Да;Не играть

Набор для обучения

Рассчитать

Дерево решений

 

 Ссылка  Сохранить  Виджет

Деревья решений

Дерево принятия решений (также может называться деревом классификации или регрессионным деревом) — средство поддержки принятия решений, использующееся в машинном обучении, анализе данных и статистике. Структура дерева представляет собой «листья» и «ветки». На рёбрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.¹

Разберем, как работает дерево решений, на примере данных по умолчанию.

Классифицируемые объекты обладают следующими свойствами (атрибутами):

• Осадки: Солнечно/Переменная облачность/Пасмурно
• Влажность: Высокая/Нормальная
• Ветер: Да/Нет
• Температура: Жарка/Умеренно/Прохладно

Классы объектов: Играем/Не играем

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

Дерево. построенное на данных по умолчанию сначала предлагает выполнить разбиение по значению атрибута "Осадки".

• Если это значение - "Солнечно", следующее разбиение выполняется по атрибуту "Влажность".
  • Если "Влажность" "Высокая", то объект принадлежит классу "Не играем".
  • Если "Влажность" "Нормальная", то объект принадлежит классу "Играем".
• Если это значение - "Переменная облачность", то объект принадлежит классу "Играем" и дальнейших разбиений не требуется.
• Если это значение - "Пасмурно", следующее разбиение выполняется по атрибуту "Ветер" и т.д.

Обратите внимание, что дерево решений не использует атрибут "Температура"!

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

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