§ 8. Решающие правила, опирающиеся на прецеденты

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

Исходя из этого можно предложить в качестве решающего правила следующую процедуру: оставить в памяти машины все реализации обучающей выборки и контрольную точку  относить к тому образу, чья реализация оказалась ближе всего к точке . Это правило действительно используется в практике решения некоторых задач, и оно носит название правила ближайшего соседа [103]. Однако следует учитывать, что реальные измерения признаков нередко сопровождаются помехами и ошибками, так что свидетельству одного прецедента доверять опасно. Целесообразно учитывать свидетельства и других объектов обучающей выборки. С этой целью обращают внимание не на одну, а на несколько ближайших точек. Такие правила называются правилами  ближайших соседей. Если больше половины из  соседей принадлежат образу , то и точка  относится к -му образу.

Иногда в голосовании принимают участие все реализации обучающей выборки, но с разными весами, зависящими от их расстояний до распознаваемой точки . Одним из первых алгоритмов такого рода был алгоритм потенциальных функций [4]. Его сущность иллюстрирует рис. 17. Реализации образа «крестики» как бы излучают потенциал, величина которого убывает с расстоянием  от точки . Характер убывания может быть самым разным: , ,  и т. д.

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

Если окажется, что какая-нибудь из точек обучающей выборки распознается по этому правилу с ошибкой, то картину потенциального поля можно скорректировать. Для этого потенциал в этой точке увеличивается в нужную сторону до тех пор, пока эта точка не станет распознаваться правильно. Авторами метода доказана его сходимость к оптимальному при увеличении объема обучающей выборки и конечность числа шагов обучения (коррекции поля) для случаев образов, хорошо разделяемых с помощью «не слишком вычурных» границ.

Рис. 17