Cybernetics Wiki
Advertisement

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

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

Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.

Пример задачи[]

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

  • выше ли находится соперник по турнирной таблице;
  • дома ли играется матч;
  • пропускает ли матч кто-либо из лидеров команды;
  • идет ли дождь.

У нас есть некоторая статистика на этот счет:

Соперник Играем Лидеры Дождь Победа
Выше Дома На месте Да Нет
Выше Дома На месте Нет Да
Выше Дома Пропускают Нет Да
Ниже Дома Пропускают Нет Да
Ниже В гостях Пропускают Нет Нет
Ниже Дома Пропускают Да Да
Выше В гостях На месте Да Нет
Ниже В гостях На месте Нет ???

Хочется понять, выиграет ли наша команда в очередной игре.

Один из вариантов дерева принятия решений для этой задачи приведен на рис. 1.

Файл:DecisionTreeSample1.jpg

Рис. 1. Дерево принятия решений

Алгоритмы построения дерева[]

Общая схема построения дерева принятия решений по тестовым примерам выглядит следующим образом:

  • Выбираем очередной атрибут , помещаем его в корень.
  • Для всех его значений :
    • Оставляем из тестовых примеров только те, у которых значение атрибута равно
    • Рекурсивно строим дерево в этом потомке

Основной вопрос: как выбирать очередной атрибут?

Есть различные способы выбирать очередной атрибут:

  • Алгоритм ID3
  • Алгоритм ID3 с выбором атрибута с помощью Gain Ratio
  • Алгоритм ID3 с выбором атрибута с помощью индекса Гини

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

См. также[]

Ссылки[]

Литература[]

  • Ананий В. Левитин Глава 10. Ограничения мощи алгоритмов: Деревья принятия решения // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 409-417. — ISBN 0-201-74395-7
Advertisement