Решающие деревья. 
Искусственный интеллект и когнитивная графика

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

Бинарным корневым деревом (БД) называется дерево, имеющее следующие свойства:

• а) каждая вершина (кроме корневой) имеет одну входящую дугу;
• б) каждая вершина имеет либо две, либо ни одной выходящей дуги.

Вершины, имеющие две выходящие дуги, называются внутренними, а остальные — терминальными или листьями.

Пусть задано N предикатов.

.

определенных на множестве допустимых признаковых описаний {S}, именуемые признаковыми предикатами. Каждый предикат отвечает на вопрос, выполняется ли некоторое свойство на объекте S или нет. Примерами признаковых предикатов могут быть.

Каждой строке.

таблицы обучения.

поставим в соответствие бинарную строку значений предикатов на описании.

.

В результате, таблице.

будет соответствовать бинарная таблица.

бинарных «вторичных описаний» объектов обучения.

Бинарное дерево называется решающим, если выполнены следующие условия:

• 1. каждая внутренняя вершина помечена признаковым предикатом из ;
• 2. выходящие из вершин дуги помечены значениями, принимаемыми предикатами в вершине;
• 3. концевые вершины помечены метками классов;
• 4. ни в одной ветви дерева нет двух одинаковых вершин.

Пример подобного дерева для конфигурации из трех классов (рис.7) приведен на рис. 8.

Рис. 7 Конфигурация объектов трех классов. Объекты классов обозначены, соответственно, символами, ,

Рис. 8 Решающее дерево для классов рис. 7

На рис. 8 приведено некоторое решающее дерево, позволяющее правильно распознавать объекты трех классов, изображенных на рис. 7. Вершины дерева помечены следующими предикатами:

Данному решающему дереву соответствуют характеристические функции классов.

, ,.

принимающие значение 1 на объектах «своего» класса и 0 на объектах остальных классов.

Приведем еще один пример решающего дерева (рис.9), построенного непосредственно по таблице обучения:

=. (1.2).

В качестве признаковых предикатов используются.

Рис. 9 Решающее дерево бинарной таблицы обучения (1.2)

Здесь в качестве приближений для характеристических функций классов выбраны функции.

.

В данном примере, для построения решающего дерева использованы только два признака.

Задача построения решающего дерева по обучающим данным решается неоднозначно, методам построения решающих деревьев посвящена обширная литература. 4].