§ 4.6. Предварительное преобразование исходного описания весьма высокой размерности

Из-за вычислительных трудностей реализация рассмотренных в § 4.4-4.5 методов оптимизации системы линейных признаков на ЭЦВМ среднего класса может быть осуществлена, если исходное описание образов имеет размерность не выше 50-100. В то же время на практике приходится сталкиваться с задачами опознания, имеющими весьма высокую размерность исходного описания, достигающую нескольких сот. В этом случае необходимо иметь некоторую, пусть не оптимальную, процедуру для предварительного нахождения подпространства признаков размерности меньше 100-50, чтобы для дальнейшей минимизации системы признаков использовать критерии, более близкие к оптимальному, например, описанные в § 4.4-4.5.

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

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

степенного вида с показателем степени α, стремящимся к ∞ (здесь q≠p).

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

Идея алгоритма заключается в нахождении признаков, обеспечивающих заданное расстояние между парами образов. Признаки находятся последовательно для пар образов, начиная с наиболее близких (см. также [4.11]).

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

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

На третьем шаге точно так же находится трехмерное подпространство и т. д. до полного разделения всех пар центров тяжести.

Этой процедурой обеспечивается нахождение подпространства, в котором расстояния между центрами тяжести образов имеет величину, большую d().

Для нахождения подпространства, обеспечивающего разделимость всех реализаций учебной выборки с порогом d*₀ < d₀, аналогичным образом находятся дополнительные признаки.

Алгоритм нахождения предварительного преобразования в случае исходного описания большой размерности приводится в приложении 4.VI.