§ 1. Правило k ближайших соседей (алгоритм λ-NNR)Этап обучения в алгоритме -NNR состоит из следующих процедур (см. рис. 32). Для каждого образа в отдельности строится полный граф, соединяющий точки его обучающей выборки. Среди ребер графа образа находится самое длинное и обозначается через . Для каждой точки запоминается смежное ему ребро минимальной длины . Вычисляется самое большое значение характеристики локального скачка плотности . Рис. 32 На этапе распознавания определяется функция принадлежности распознаваемой точки ко всем образам поочередно. Среди точек образа находится «ближайший сосед» — точка , удаленная от точки на минимальное расстояние . Нормированное расстояние между точками и равно . Теперь можно определить величину и нормированное значение этой величины . Затем вычисляется характеристика . Введем понятие функция принадлежности объекта к образу : . Аналогичным путем найдем значение функции принадлежности точки ко всем другим образам: . Точка считается принадлежащей тому образу, функция принадлежности к которому имеет наибольшее значение. Можно ввести пороговое значение для (например, ) и считать, что точка не принадлежит ни одному из образов, если все функции принадлежности меньше . Легко видеть, что такое правило в точности соответствует гипотезе локальной -компактности: в некоторой окрестности обучающей реализации некоторого образа могут появиться объекты того же образа. Границы этих окрестностей проходят по точкам, в которых функция принимает нулевое значение (окружности на рис. 32). Функция играет роль ядерной функции с центром в точках обучающей выборки, и параметры каждого ядра адаптивно меняются в зависимости от расстояния до соседних точек. Если некоторая точка пространства входит в окрестности точек, принадлежащих разным образам, то решение принимается в пользу того образа, которому соответствует большее значение функции принадлежности . Решающая граница между и образами проходит по точкам, в которых . Для защиты от помех можно измерять не до одного, а до ближайших соседей из каждого образа. Решение при этом можно принимать по максимальному значению средней величины функции принадлежности к каждому образу. Принятие решения по -расстоянию имеет определенные преимущества по сравнению с решениями, основанными на обычном евклидовом расстоянии. На рис. 33, а объект эксперты уверенно присоединяют к образу , хотя евклидово расстояние до ближайшего соседа относит его к образу . При использовании же -расстояния этот объект распознается в качестве представителя образа . Если найти точки на плоскости, функции принадлежности которых к образам и одинаковы, то они образуют линию (-границу), показанную на рис. 33, а. В главе 5 говорилось, что при неравных дисперсиях распределений образов оптимальная граница между ними представляет поверхность второго порядка. След такой поверхности показан на рис. 33, б. Очевидно сходство границ на этих рисунках. Рис. 33 Было бы интересно исследовать вопрос о том, стремится ли при увеличении объема выборки двух образов решающее правило, основанное на сравнении -расстояний до ближайших соседей, к оптимальному статистическому решающему правилу. Обратим внимание на тот факт, что статистические решающие правила разработаны только для самых простых законов распределений образов, для которых оптимальными являются линейные или квадратичные разделяющие поверхности. При усложнении этих законов такие правила представляли бы собой поверхности -го порядка, где . Как показано в [69], использование таких разделяющих границ требует быстро растущих в функции от затрат машинных ресурсов. При этом эффективность решающих функций (отношение разделяющей способности к затратам ресурсов) быстро падает. Так, эффективность использования поверхности 5-го порядка в тысячу раз меньше эффективности использования набора поверхностей 2-го порядка. Сложность же правила ближайших соседей от вида распределения не зависит. С ростом объема обучающей выборки машинное время и затраты памяти растут в зависимости от линейно. Для уменьшения этих затрат необходимо предварительно сократить объем обучающих реализаций, оставив минимальный набор точек-прецедентов, достаточный для безошибочного распознавания всех точек обучающей выборки. С этой целью можно использовать алгоритм -STOLP.
|