4.7. ПРАВИЛО к БЛИЖАЙШИХ СОСЕДЕЙ

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

Основным поводом к рассмотрению правила k ближайших соседей послужило сделанное нами ранее наблюдение о согласовании вероятностей с реальностью. Сначала мы заметили, что если k фиксировано и количеству выборок п позволить стремиться к бесконечности, то все k ближайших соседей сойдутся к х. Следовательно, как и в случае с единственным ближайшим соседом, метками каждого из k ближайших соседей будут случайные величины, независимо принимающие значение с вероятностью Р(сог|х), і=1, 2. Если Р((й„Іх) является самой большой апостериорной вероятностью, то решающее правило Байеса всегда выбирает со^. Правило единственного ближайшего соседа выбирает с вероятностью Р(о)„[х). Правило k ближайших соседей выбирает ю„, если большинство из

k ближайших соседей имеют метку о)„, с вероятностью

В общем чем больше значение к, тем больше вероятность, что будет выбрана со„.

Мы могли бы проанализировать правило k ближайших соседей так же, как мы анализировали правило единственного ближайшего

соседа. Однако ввиду того, что здесь потребуются более сложные рассуждения, которые мало что проясняют, мы удовлетворимся только констатацией результатов. Можно показать, что при нечетном k величина ошибки в случае с двумя классами и большим количеством выборок для правила k ближайших соседей ограничивается сверху функцией С* (Р*), где по определению есть наименьшая вогнутая функция от Р*, большая, чем

Теперь совершенно ясно, что очень мало можно увидеть, глядя на приведенную функцию, разве что только можно отметить ее род-

ство с биномиальным распределением. К счастью, можно легко вычислить С^(Р*) и изучить результаты. На рис. 4.5 показаны границы уровней ошибок правила к ближайших соседей дЛя нескольких значений k. Случай с k=l соответствует случаю с двумя классами из рис. 4.4. С возрастанием k верхние границы все более приближаются к нижней границе, уровню Байеса. В пределе, когда k стремится к бесконечности, две границы встречаются и правило k ближайших соседей становится оптимальным.

Рискуя произвести впечатление, что мы повторяемся, закончим снова упоминанием о ситуации с конечным числом выборок, встречаемой на практике. Правило k ближайших соседей можно рассматривать как еще одну попытку оценить апостериорные вероятности Р(сО(|х) на основании выборок. Чтобы получить надежную оценку, нам желательно использовать большое значение k. С другой стороны, мы хотим, чтобы все k ближайших соседей х' были очень близки к X с тем, чтобы быть уверенными, что Р (co; |х') приблизительно такая же, как Р(со;|х). Это заставляет нас выбрать среднее значение k, являющееся небольшой частью всего количества выборок. Только в пределе при устремлении k к бесконечности можем мы быть уверены в почти оптимальном поведении правила k ближайших соседей.