Линейные решающие правила

Само название говорит о том, что граница, разделяющая в признаковом пространстве области различных образов, описывается линейной функцией (рис. 4)

= .

Рис. 4. Линейное решающее правило для распознавания двух образов

Одна граница при этом разделяет области двух образов. Если >2, то требуется несколько линейных функций и граница является, вообще говоря, кусочно линейной. Для наглядности будем считать =2. Если на множестве объектов выполняется условие

,

если  – реализация первого образа ,

если  – реализация второго образа ,

то образы и называют линейно разделимыми.

Существуют различные методы построения линейных решающих правил. Рассмотрим один из них, реализованный в 50-х годах Розенблатом, в устройствах распознавания изображений, названных персептронами (рис. 5).

Пусть

если , , если ,

где  – некоторый объект одного из образов, .

Рис. 5. Упрощённая схема однослойного персептрона

Выбор осуществляется пошаговым образом. Текущее значение заменяется новым после предъявления персептрону очередного объекта обучающей выборки. Эта корректировка производится по следующему правилу:

1.  , если и или если и .

2.  , если и , .

3.  , если и .

Это правило вполне логично. Если очередной объект системой классифицирован правильно, то нет оснований изменять . В случае (2) следует изменить так, чтобы увеличить . Предложенное правило удовлетворяет этому требованию. Действительно,

.

Соответственно в случае (3) .

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

, если ,

, если .

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

Метод ближайших соседей

Обучение в данном случае состоит в запоминании всех объектов обучающей выборки. Если системе предъявлен нераспознанный объект , то она относит этот объект к тому образу (рис. 7), чей "представитель" оказался ближе всех к .

Рис. 6. Пример линейно неразделимых множеств

Рис. 7. Решающее правило "Минимум расстояния до ближайшего соседа"

Это правило ближайшего соседа. Правило ближайших соседей состоит в том, что строится гиперсфера объёма с центром в . Распознавание осуществляется по большинству "представите­лей" какого-либо образа, оказавшихся внутри гиперсферы. Здесь тонкость состоит в том, чтобы правильно (разумно) выбрать объём гиперсферы. должен быть достаточно большим, чтобы в гиперсферу попало относительно большое число "представителей" разных образов, и достаточно маленьким, чтобы не сгладить нюансы разделяющей образы границы. Метод ближайших соседей имеет тот недостаток, что требует хранения всей обучающей выборки, а не её обобщённого описания. Зато он даёт хорошие результаты на контрольных испытаниях, особенно при больших количествах объектов, предъявленных для обучения.

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

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