Введение - Деревья решений

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

пример дерева

Рисунок 1. - Пример дерева

С помощью деревьев можно решить следующие задачи:

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

На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений CART, C4.5, ID3. Но наибольшее распространение и популярность получили следующие три:

    - ID3. В основе этого алгоритма лежит понятие информационной энтропии - то есть, меры неопределенности информации (обратной мере информационной полезности величины). Для того чтобы определить следующий атрибут, необходимо подсчитать энтропию всех неиспользованных признаков относительно тестовых образцов и выбрать тот, для которого энтропия минимальна. Этот атрибут и будет считаться наиболее целесообразным признаком классификации. - C4.5 - алгоритм построения дерева решений, количество потомков у узла не ограничено. Не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации. Алгоритм C4.5 использует теоретико-информационный подход. Для выбора наиболее подходящего атрибута, предлагается следующий критерий:

Множества T1, T2, ... Tn получены при разбиении исходного множества T по проверке X. Выбирается атрибут, дающий максимальное значение по критерию(1).

- CART (Classification and Regression Tree) - это алгоритм построения бинарного дерева решений - дихотомической классификационной модели. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, решает задачи классификации и регрессии. Алгоритм CART использует так называемый индекс Gini, который оценивает "расстояние" между распределениями классов.

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

Похожие статьи




Введение - Деревья решений

Предыдущая | Следующая