Метод ближайших соседей. Метод потенциальных функций

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

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

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

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

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

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

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

Метод потенциальных функций

Название метода в определенной степени связано со следующей аналогией ( для простоты будем считать, что распознается два образа). Представим себе, что объекты являются точками некоторого пространства . В эти точки будем помещать заряды , если объект принадлежит образу , и , если объект принадлежит образу  (рис. 8).

Рис. 8. Иллюстрация синтеза потенциальной функции 
в процессе обучения:

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

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

 Распознавание может осуществляться следующим способом. В точке , где находится неопознанный объект, вычисляется потенциал . Если он оказывается положительным, то объект относят к образу . Если отрицательным – к образу .

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

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