Методы построения деревьев решений



Построение деревьев решений реализуется на основе методики «разделяй и властвуй», предполагающей рекурсивное разбиение множества объектов из обучающей выборки на подмножества (классы) объектов. При заданном аналитиком множестве классов  и обучающей выборке  возможны следующие ситуации [1]:

• множество  содержит один или более объектов одного класса и дерево решений представляет собой лист, ассоциированный с классом ;

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

• множество  содержит объекты, относящиеся к разным классам. Множество  следует разбить на подмножества. С этой целью выбирается одна из независимых переменных , которая имеет отличные друг от друга значения. Исходное множество  разбивается на подмножества, каждое из которых содержит все объекты, имеющие значения  для выбранного атрибута. Процедура рекурсивно повторяется до формирования подмножеств с объектами одного класса.

Построение дерева решений производится сверху вниз. При этом алгоритмы построения деревьев решений являются «жадными алгоритмами» [4]. При построении деревьев решений решается две задачи [1]. Первая задача связана с определением на каждом внутреннем узле условия разделения множество объектов на подмножества. Условие определяется с применением одной независимой переменной. Эта переменная должна обеспечивать разбиение множества, при котором подмножества состоят из объектов одного класса или максимально отвечали требованию минимального количества в подмножестве объектов других классов.

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

Все объекты заранее отнесены к известным классам, такой процесс построения дерева решений называется обучением с учителем (supervised learning). Процесс обучения также называют индуктивным обучением или индукцией деревьев (tree induction).


Дата добавления: 2018-10-26; просмотров: 473; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!