4.6.2. СХОДИМОСТЬ ПРИ ИСПОЛЬЗОВАНИИ МЕТОДА БЛИЖАЙШЕГО СОСЕДА

Теперь мы хотим оценить среднюю вероятность ошибки для правила ближайшего соседа. В частности, если Р„ (е) есть уровень ошибки с п выборками и если

то мы хотим показать, что

Начнем с замечания, что при использовании правила ближайшего соседа с конкретным множеством п выборок результирующий уровень ошибки будет зависеть от случайных характеристик выборок. В частности, если для классификации х использутотся различные множества п выборок, то для ближайшего соседа вектора х будут получены различные векторы х'„. Так как решающее правило зависит от ближайшего соседа, мы имеем условную вероятность ошибки Рп (е\х, х'п ), которая зависит как от х, так и от х), . Усредняя по х^, получаем

Обычно очень трудно получить точное выражение для условной плотности распределения р (х^, [х). Однако, поскольку х'„ по определению является ближайшим соседом х, мы ожидаем, что эта плотность будет очень большой в непосредственной близости от х и очень малой во всех других случаях. Более того, мы ожидаем, что по мере устремления п к бесконечности р (х;, ] х) будет стремиться к дельта-функции с центром в х, что делает оценку, задаваемую (29), тривиальной. Для того чтобы показать, что это действительно так, мы должны допустить, что плотность р для заданного х непрерывна и не равна нулю. При таких условиях вероятность попадания любой выборки в гиперсферу S с центром в х есть некое положительное число

Таким образом, вероятность попадания всех п независимо взятых выборок за пределы этой гиперсферы будет (1—Ps)", стремящейся к нулю по мере устремления п к бесконечности. Итак, х'„ сходится к X по вероятности и р (х; I х) приближается к дельта^функ- ции, как и ожидалось. Вообще говоря, применяя методы теории ые*

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