ПРИЛОЖЕНИЕ Е. ВЫЧИСЛЕНИЯ, НЕОБХОДИМЫЕ ДЛЯ ЭКСПЕРИМЕНТОВ ПО УПОРЯДОЧЕНИЮ ПРИЗНАКОВ И КЛАССИФИКАЦИИ ОБРАЗОВ С ПОМОЩЬЮ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

В этом приложении дается детальная вычислительная процедура для примера из § 4.6. На каждом шаге процесса классификации, включавшего расчет решающих границ для упорядочения признаков, использовалось квантование пространства вероятностей на 210 частей. Пусть, например, в начале 8-го шага процесса имелось уже 7 измеренных признаков и остается один.

Рис. Е.1а. Решающая поверхность отбора признаков. Цифра 3 в каждой позиции указывает, что должен измеряться 3-й признак, а буквы указывают на необходимость принятия соответствующего классифицирующего решения.

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

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

входного образа и выполнением измерения последнего из имеющихся признаков. Следовательно, на этом шаге процесса должны быть вычислены восемь множеств решающих границ, по одному для каждого признака, который может быть остающимся признаком в начале 8-го шага. Рис. Е.1 показывает в качестве примера решающую границу, полученную для случая, когда остается измерить только признак Число 3 на рис. E.la показывает, что при измерении ожидается меньший риск, чем при принятии классифицирующего решения; буква же указывает на необходимость принятия соответствующего классифицирующего решения.

Таблица Е.1 (см. скан) Число решающих границ и требуемый объем памяти

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

Для 7-го шага процедура продолжается таким же образом. В начале 7-го шага имеется два признака для измерения. Так как всего будет возможных пар из восьми признаков, то необходимо вычислить 28 решающих границ, используя (4.20).

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

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