Метод К-ближайших соседей

Метод К ближайших соседей - один из наиболее простых алгоритмов классификации, относящийся к группе структурных методов.

В качестве обучающей выборки используется набор объектов, каждый из которых принадлежит к одному из двух или более классов. Каждый объект может быть представлен точкой в n-мерном пространстве, где n – число аналититических признаков, используемых для классификации.

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

Метод к -ближайших соседей
Этот метод, как и оценки Парзена, относится к локальным методам оценивания плотности распределения. Для оценивания плотности в точке х выбирается такой минимальный интервал с центром в х, что в него попадает к представителей класса. За оценку плотности вероятности в точке х принимают величину
1
(33)
N A(k,N,xy
где А (к, N, х) — длина интервала .(или объема ячейки в много мерпом случае). Показано, что при выполнении условий
limA(JV) = 0, Hm^ = 0
iV-»co
N
величина Jn(x) является асимптотически несмещенной и состоятельной оценкой плотности распределения f(x\H).
В практике метод /с-ближайших соседей используется для непосредственного построения решающего правила. Если в объеме А (к, N, х") с центром в точке х° попадает kt представителей класса //, и кг представителей класса Я2, то
2>1 Т<1
#2>
(34)
Нетрудно показать, что этот метод основан на байесовом критерии. Действительно, согласно критерию правдоподобия решающее правило имеет вид
f(x°\Hl)Pl<- \xo^Hv
(35)
Подставляя в (35) оценки f(x°IHh) из (33) и припяв
N
N,
получим после упрощений правило (34). Таким образом, процедура /с-соседей является, по существу, байесовой, где замена истинных вероятностей их оценками должна отразиться на величине ошибки классификации, причем в силу сходимости оценки f(x) к j(x) следует ожидать, что уровень ошибки е метода /с-соседей будет стремиться к соответствующей величине е* для байесовой классификации. Было доказано, что при к = 1 справедливы неравенства
е*<е «S2e*(t— е*).
Это означает, что в наихудшем случае (к = 1) уровень ошибки метода превосходит не более чем в 2 раза уровень ошибки байесовой классификации прп малых е*.