57. Правило ближайшего соседа как пример непараметрического метода распознавания: оценка вероятности ошибки классификации. Правило ближайшего соседа.

Пусть дана СДСВ и её реализация . Классы определены как .

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

Кроме того, пары образуют независимую систему случайных величин.

вероятность ошибки классификации (результирующая) (Байесовского решающего правила).

вероятность ошибки классификации (Байесовского решающего правила).

Классификация (в Байесовском решающем правиле) осуществляется по следующему принципу: .

Тогда вероятность ошибки .

Результирующая вероятность ошибки: .

Теперь же рассмотрим собственно правило ближайшего соседа.

размер выборки.

Задание: найти асимптотическую оценку , выразив верхнюю и нижнюю границы (через вероятность ошибки Байесовского правила):

безошибочная классификация для класса.

безошибочная классификация для всех классов .

Утверждение 1.

Утверждение 2.

58, 59 Мгуа

Большинство задач распознавания образов, решаемых с помощью алгоритмов МГУА, сводится к прямому восстановлению обобщенной классифицирующей функции по небольшим обучающим последовательностям.

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

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

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

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

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

Формальное представление алгоритма:

Вся выборка делится на обучающую и проверочную: . Входной вектор имеет размерность N .

1-ый ряд - на основе обучающей последовательности строятся частные описания от всех попарных комбинаций исходных аргументов, приближающие по МНК выходную переменную:

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

2-ой ряд - полученные переменные принимаются в качестве аргументов второго ряда, и снова строятся все частные описания от двух аргументов:

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