Вопрос 22. Построение дерева индуктивного вывода. Применение деревьев принятия решений в СОВ

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

Построение по базе данных всех возможных деревьев – NP полная задача. Есть два принципа – принцип Оккама – «самое простое решение является правильным». То есть самое короткое дерево является хорошим.

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

А - Множество

S - свойство, классифицированное при помощи атрибута

Q - атрибут, у него q возможных значений

Ai -множество элементов А, для которых атрибут Q имеет значение i

Если S не бинарное а имеет s значений, каждое из которых реализуется в mi случаях

Прирост информации

Чтобы не плодить херни, вводим критерий уменьшения желательности с ростом количества значений. SplitInfo - поправка, GainRatio - новый, взвешенный критерий.

Выбирают более короткие деревья и деревья, помещающие атрибуты с наибольшим приростом информации ближе к корню дерева.

Типовые алгоритмы: ID3, C4.5

Плюсы:

· схема одновременного ветвления, которая позволяет изучать эффект влияния отдельных переменных и производить последующий анализ их вклада

· отсутствие предварительных представлений о законах распределения данных

Применимость:

· образцы представлены в виде пар атрибут-значение

· целевая функция имеет дискретные выходные значения

· целесообразно представление знаний в виде дизъюнкций

· существуют модификации, делающие метод устойчивым к ошибкам.

· обучающие данные могут содержать пропуски в значениях атрибутов

Существует проблема переобучения → что делается:

· ограничение глубины дерева

· отсечение лишних ветвей

Дата добавления: 2014-01-15