1.3.2. Древообразные классификаторы.

В основе описываемой ниже группы методов лежит понятие бинарного дерева—графа. Эти деревья принято изображать в перевернутом виде: корень — сверху, листья — внизу (рис. 1.5), при этом Под словом «корень» понимаем самый верхний узел (вершину) графа, а под словом «лист» — узел, из которого вниз не выходят стрелки к расположенным ниже узлам.

С каждым узлом t дерева связаны следующие объекты:

— подмножество пространства наблюдения

— подмножество генеральной совокупности (1.46) с

- правило классификации из разрешенного набора правил для

Кроме того, для узлов «не-листьев» вводится правило разбиения на два подмножества таких, что

Рис. 1.5. Пример графа древообразного классификатора: О — промежуточный узел; — концевой узел — «лист»

Древообразные классификаторы определяются рекурсивно. Для этого задаются: 1) критерий качества классификации на разрешенный класс правил для построения способ построения правило объявления узла листом, т. е. правило прекращения последующих делений.

В качестве корневого (нулевого) узла принимается узел с совпадающим со всем пространством возможных значений

Критерий качества классификации. Пусть штраф за ошибочную классификацию, когда верна гипотеза и функция потерь Q классификатора определена согласно (1.32). Возьмем в качестве меры качества классификации на классификатора

При этом чем Q меньше, тем классификатор лучше.

Разрешенный класс правил. Используются максимально простые классификаторы: линейные, линейные с дополнительными предположениями, например о структуре зависимостей признаков; простейшие, относящие все наблюдения к одной из классифицируемых совокупностей.

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

Правило разделения. Рассмотрим шкалу, в которой измерена координата . Если шкала номинальная, то элементарными событиями Т будем называть события вида — а или , где а — одно из возможных значений Если же шкала порядковая или интервальная, то элементарными событиями будем называть события вида а. Рассмотрим теперь всевозможные разбиения с помощью элементарных событий , таких, что

где — некоторое заданное число. Тогда по определению критерия качества классификации (1.47)

Нижняя грань в правой части (1.49) берется по всем допустимым классификаторам. Пусть — одно из элементарных событий, удовлетворяющих (1.48), на котором достигается максимальная разность между левой и правой частями (1.49); положим тогда

Правило объявления узла листом. Узел t объявляется листом, если не существует элементарного события, удовлетворяющего условию (1.48), или такое событие существует, но

Наглядный смысл условий (1.48), (1.50) очевиден: от усложнения классификатора должен быть заметный выигрыш и не следует слишком мельчить разбиения.

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

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

В отечественной литературе древообразные правила называют также логическим методом классификации [94].