1.3.2. Древообразные классификаторы.
В основе описываемой ниже группы методов лежит понятие бинарного дерева—графа. Эти деревья принято изображать в перевернутом виде: корень — сверху, листья — внизу (рис. 1.5), при этом Под словом «корень» понимаем самый верхний узел (вершину) графа, а под словом «лист» — узел, из которого вниз не выходят стрелки к расположенным ниже узлам.
Среди всех допустимых правил в качестве
выбирается правило, минимизирующее выбранную функцию риска. При этом ограничимся классами правил, на которых минимум достигается. Простота разрешенного класса правил компенсируется структурой дерева.
Правило разделения. Рассмотрим шкалу, в которой измерена
координата
. Если шкала номинальная, то элементарными событиями Т будем называть события вида — а или
, где а — одно из возможных значений
Если же шкала порядковая или интервальная, то элементарными событиями будем называть события вида
а. Рассмотрим теперь всевозможные разбиения
с помощью элементарных событий
, таких, что
где
— некоторое заданное число. Тогда по определению критерия качества классификации (1.47)
Нижняя грань в правой части (1.49) берется по всем допустимым классификаторам. Пусть
— одно из элементарных событий, удовлетворяющих (1.48), на котором достигается максимальная разность между левой и правой частями (1.49); положим тогда
Правило объявления узла листом. Узел t объявляется листом, если не существует элементарного события, удовлетворяющего условию (1.48), или такое событие существует, но
Наглядный смысл условий (1.48), (1.50) очевиден: от усложнения классификатора должен быть заметный выигрыш и не следует слишком мельчить разбиения.
Древообразные классификаторы обладают рядом привлекательных свойств. Они относительно просты: при уменьшении
и соответствующем росте числа ветвей сходятся к классификатору, минимизирующему выбранную функцию потерь; инвариантны относительно монотонных преобразований координат; легко интерпретируемы;
при выборе в качестве допустимого класса простейших правил допускают наличие в классифицируемом векторе X ненаблюдаемых, так называемых «стертых», координат, если, конечно, эти координаты не используются в качестве аргументов ветвления.
В отечественной литературе древообразные правила называют также логическим методом классификации [94].