4.2. Метод попутного разделения (ПОРА) [66]

Если построить оптимальную разделяющую границу между образами  и , то можно обнаружить, что эта граница попутно разделяет и другие некоторые пары образов с ошибкой , не превышающей допустимого значения. Так, решающая граница (см. рис. 13), построенная для разделения образов 2 и 4, может использоваться также для разделения образов 1 и 3 от образов 5, 6 и 7.

Рис. 13

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

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

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

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

Эксперимент проводился для  при числе образов  для надежности оптимального распознавания . Для каждого такого сочетания условий проводилось по 10 опытов, отличающихся случайным расположением образов друг относительно друга. Оказалось, что число  меньше числа  в тех случаях, когда надежность оптимального распознавания находится в диапазоне от 0,9 до 1. От числа образов этот результат не зависит. Отсюда следует, что пользоваться методом попутного разделения вместо определения расстояний до математических ожиданий целесообразно тогда, когда надежность распознавания при оптимальных решающих границах равна или больше 90 %.

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