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

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

1 Информативность

Рассмотрим множество точек X, и некоторый классификатор φ(X) → { 0, 1}.

Неформально – классификатор φ тем более информативен, чем больше он выделяет объектов ”своего” класса по сравнению с объектами всех остальных ”чужих” классов.

Свои объекты назовём позитивными, а чужие – негативными.

Введём следующие обозначения:

P ≥ 1 – число объектов класса c в выборке X

p(φ) – из них число объектов, для которых выполняется условие φ(x) = 1 (правильный результат)

N ≥ 1 – число объектов всех остальных классов в выборке X

n(φ) – из них число объектов, для которых выполняется условие φ(x) = 1 (ошибки классификатора)

Информативность классификатора φ тем выше, чем больше объектов он выделяет, и чем меньше среди них негативных.

p(φ) → max   ;   n(φ) → min

Введём формальное определение информативности.

Рассмотрим два исхода w₀,w₁ с вероятностями q₀ и q₁ = 1 −q₀, количество информации, связанное с исходом w_i, по определению равно − log ₂q_i. Это математическое ожидание числа бит, необходимых для записи информации о реализации исходов w_i.

Энтропия определяется как мат.ожидание количества информации:

Будем считать появление объекта класса c исходом w₀, а появление объекта любого другого класса исходом w₁. Тогда можно оценить энтропию выборки X:

Энтропия всей выборки после получения информации φ становится равна:

В итоге уменьшение энтропии составляет

Это есть энтропийное определение информативности.

2 Построение решающего дерева

Рассмотрим учебный набор (X,Y ) в n-мерном пространстве признаков, где X – объекты, Y – соответствующие объектам номера классов. Процедура построение решающего дерева представляем собой рекурсивное разделение этого множества точек на две части с максимизацией информативности этого разделения на каждом шаге.

Алгоритм обучения выглядит следующим образом.

1. если X содержит точки только одного класса
   то переход на п.6
2. выбрать признак номер i и найти для него пороговое значение b ( min(X_i) < b < max(X_i) ) с максимальной информативностью разделения
3. сохранить найденную пару (i,b)
4. разделить X на две части по признаку i и его порогу b
5. выполнить рекурсивно с п.1 для каждого полученного на пред.шаге подмножества
6. конец работы

3 Реализация

На рисунке ниже проиллюстрирована результаты работы решающего дерева

 

Рис.1: результат работы

 
  Реализация в системе Octave [  здесь  ].

 
 

Список литературы

При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.