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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылка скопирована в буфер обмена
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Построение дерева решений

Комментарии