3.2. КЛАССИФИКАЦИЯ ОБРАЗОВ ПО КРИТЕРИЮ МИНИМУМА РАССТОЯНИЯ

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

3.2.1. Случай единственности эталона

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

Рассмотрим М классов; пусть эти классы допускают представление с помощью эталонных образов Евклидово расстояние между произвольным вектором образа эталоном Определяется следующим выражением:

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

Формуле (3.2.1) можно придать более удобный вид. Возведение всех членов в квадрат дает

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

где образ относится к классу если условие справедливо для всех .

Отметим, что — линейная решающая функция, т. е. если — компоненты вектора гпричем

и

то (3.2.3) можно представить в обычной линейной форме

где .

Рис. 3.3. Граница, разделяющая два класса, каждый из которых определяется одним эталоном.

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

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