6.4. Приближения, основанные на алгоритмах ограниченного просмотра вперед

6.4.0. Алгебраический подход

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

Как и раньше, пусть задана последовательность Рассмотрим две возможные альтернативы. Первая заключается в том, что по имеющимся наблюдениям проводится наилучшая возможная классификация. Стоимость альтернативы определяется по (9). Назовем эту альтернативу и пусть ее стоимость равна Применяемая в процедуре просмотра на один шаг вперед альтернатива заключается в том, что делается точно одно дополнительное измерение (при этом, конечно, выбирается наилучшее), после чего проводится классификация объекта. Стоимость альтернативы равна

Оценка стоимости классификации в этом узле при помощи процедуры, определенной алгоритмом просмотра на один шаг вперед, есть

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

6.4.1. Проблема выборки

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

Таблица 6.2

Пример задачи для алгоритма просмотра на один шаг вперед

Для простоты стоимость ошибочной классификации принимается равной 0, если классификация проведена верно, и 1 в противном случае. Предполагается, что стоимость

(кликните для просмотра скана)

любого измерения равна 0,1. Поэтому

и

Вначале классификация должна проводиться на основе нулевой последовательности При этом вероятность получения определенных значений в классах оценивается по их относительным частотам в выборке. В этом случае первоначально а ожидаемые потери при классификации на основе нулевой последовательности независимо от результата классификации равны 0,5. Для определения ожидаемых потерь, вызванных результатом только одного измерения и последующей классификации, необходимо для каждого измерения оценить ожидаемые потери, чтобы быть уверенным, что после выполнения этого измерения проводятся наилучшие возможные классификации. Это можно осуществить перекрестной классификацией классов по отношению к значениям измерений, причем для каждого измерения выбирается своя классификация. В рассматриваемом примере мы исходим из таблиц классификации и соответствующих тестов, представленных в табл. 6.3. Поскольку использование для измерения четвертой компоненты минимизирует стоимость алгоритма и ее оценка становится меньше в первом узле осуществляется тест на признак 4. Расщепление выборки относительно измерения 4 приводит к четырем подвыборкам (табл. 6.4). Каждая из них связана с одним из узлов, непосредственно следующих после первого.

Таблица 6.4 (см. скан) Подвыборки после расщепления относительно измерения 4

Выполняя аналогичные вычисления для каждого из этих подмножеств, находим, что в подвыборке 1 для разделения классов можно использовать измерение 1, в подвыборке 2 — измерение 2, в подвыборке 3 самое лучшее прекратить измерения и в подвыборке

Рис. 6.4. Дерево решения, построенное просмотром на один шаг вперед.

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