Правило ближайшего соседа

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

.

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