Алгоритмы деревьев принятия решений: обзор. Часть 2

Алгоритмы ДР обычно работают, выбирая атрибут, который обеспечивает наилучшее разделение на подмножества в обучающем наборе данных. Критерий, используемый для поиска «лучшего» атрибута, называется критерием разбиения [1] или методом выбора атрибута. После выбора создается ветвь для каждого подмножества, полученного в результате разбиения входящих данных по значению выбранного атрибута. Таким образом, по крайней мере два дочерних узла должны быть созданы для родительского узла. Функция разделения применяется к каждому дочернему узлу рекурсивно. Когда все объекты подмножества принадлежат одному классу, алгоритм прекращает дальнейшее разбиение. Наконец, конечный узел предсказывает класс, к которому принадлежат объекты в случае дерева классификации или значение признака, если строится дерево регрессии. Различные алгоритмы используют разные метрики в качестве метода выбора атрибута.

Критерии разбиения бывают двух типов:

• одномерные критерии разбиения,

• многомерные критерии разбиения.

Одномерные критерии предназначены для разделения объектов внутреннего узла в соответствии со значением одного атрибута. Алгоритм ищет лучший атрибут для разбиения узла. Некоторые одномерные критерии приведены в Таблице 1 (цитаты см. в [2]).

Таблица 1

Многомерные критерии распределяют объекты внутреннего узла на подмножества на основе значений нескольких атрибутов, в отличие от одномерных критериев, в которых проверяется один атрибут. Очевидно, что определить наилучшие многомерные критерии сложнее, чем одномерные. Большинство многомерных критериев зависят от линейных комбинаций входных переменных. Хотя многомерное разбиение улучшает эффективность ДР, но эти критерии не так популярны, как одномерное разбиение. Некоторые многомерные критерии приведены в Таблицах 2 и 3 (цитаты см. в [3]).

Таблица 2

Таблица 3