|
143 b где A(k,N,X) объем множества всех точек, расстояния которых до X меньше, евклидово множество представляет собой гипершар радиуса г, объем которого о_п_п/2 A(k,N,X)= , v ' пГ(п/2) (4.9) Величина А является случайной величиной, зависящей от выбранного множеft ства N объектов. Оценка (4.8) может использоваться для классификации следующим обрал зом. Когда требуется классифицировать неизвестный объект X, среди имеющихся N объектов, из которых Nj объектов принадлежит классу со1э a N2 объектов —классу со2 »находят к ближайших к точке X объектов. Пусть kj и к2 —соответственно числа объектов из класса a>j и со2 среди этих k-ближайших соседей. Тогда оценка (4.8) принимает вид М х / < 0 = ^ Т ’ 1 = 1 > 2 <4 1 0 > 1 N . А ь Так как к( и к2 объектов извлечены из одного и того же гипершара, то объем А один и тот же как для класса ©j, так и для класса га2. Следовательно, байесовский критерий, минимизирующий ошибку, будет иметь вид • I 1 ( N i/N ^ X /w ^ N i/N jM X /r a ^ X e r 1, ' (4.11) [(й2 или, подставляя (4.9) в (4.10) получим < Iю! k1;>k2—>X € (4.12) 4 щ |
124 2г жn_n/2 A(k,N,X) = у (4.9) v ; пГ(п/ 2) Величина А является случайной величиной, зависящей от выбранного множества N объектов. Оценка (4.8) может использоваться для классификации следующим образом. Когда требуется классифицировать неизвестный объект X, среди имеющихся N объектов, из которых N, объектов принадлежит классу ю,, а N2 объектов классу со2, находят к ближайших к точке X объектов. / Пусть к, и к2 соответственно числа объектов из класса со, и со2 среди I • , этих к ближайших соседей. Тогда оценка (4.8) принимает вид pNl(X/ffi1) = ^ 2 2 > i = i,2. (4.10) N А Так как к, и к2 объектов извлечены из одного и того же гипершара, то объем А один и тот же как для класса со,, так и для класса со2. Следовательно, байесовский критерий, минимизирующий ошибку, будет иметь вид гсо (N1/N )pNi(X /® ,)i(N 2/N )pNi(X/co2)-4.X e \ (4.11) I®2 или, подставляя (4.9) в (4.10) получим k, 1ю2' (4.12) Таким образом, решение о принадлежности объекта X к тому или другому классу можно принять непосредственно после нахождения к ближайших соседей и сравнения к, и к2. Данное решающее правило легко обобщается для задачи классификации Мs I классов. Аналогично, как и для двух классов, выбираются из обучающих выборок к ближайших к точке X точек. Пусть к,,к2,...,км число наблюдений из ®,,со2,...,сом соответственно. Наблюдение X относится к тому классу i, из которого в числе к ближайших точек присутствует больше точек, чем из любого другого класса j Фi (j = 1,2,...,М). Решающее правило для классификации М совокупностей имеет вид [96] к, = max{k,,k2,...,kM}-» X ею ,. (4.13) Процедура классификации по правилу к ближайших соседей не требует знания плотностей вероятности и является достаточно простой. Недостатком данного метода классификации является необходимость хранить в памяти машины все объекты и сравнивать каждый из них с неизвестным объектом. В общем случае непараметрические методы классификации требуют большего объема вычислений при классификации новых наблюдений, чем параметрические методы при наличии обучения. В упомянутой литературе приводятся алгоритмы работы непараметрических классификаторов по методу к ближайших соседей. Однако производить I |