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

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

.

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