Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 28
Текст из файла (страница 28)
Неяаралетрические лещаЪ 142 для классификации х заключается в присвоении х метки, наиболее часто представляемой в Яа(х). Рвссь)отрйм задачу с двумя классами с Р(в,)=Р(вз)=1(2. Допустим далее, что условные плотности р(х!вй однородны в единичных гиперсферах, рзгположемных на расстоянии десяти единиц друг от друга. а) Покажите, что если й нечетнсе, то средняя вероятность ошибки задается посредством б) Покажите, что для этого случая уровень ошибки у правила единственного ближайшего соседа будет ниже, чем у бравила й ближайших соседей, й)1.
в) (Не обязательно.) Если В позволяется возрастать с ростом л, но онв ограничивается й(а Г' и, покажите, что Рч(е)-ьО при и-+ос. 4. Легко заметить, что уровень ошибки правила ближайшего соседа Р может быть равным уровню Байеса Рч, если Р'=0 (наилучшая возможность) или если Рч=(с — 1)lс (наихудшая возможность). Может вознцкнуть вопрос, существуют лн задачи, для которых Р=Р', когда Рч находится между этими крайними воэможностями. а) Покажите, что у((звень Байсса для одномерного случая, где Р(в;)=1/с и 1, О~хета — ' гг с — !' р(х1вг)= ..
сг 1, (~х~(+! — —, с — 1' 0 в остальных случаяк, будет Р*=г. б) Покажите, что для этого случая'Р=Р*. б. Рассмотрим мяожество из семи двумерных векторов хг= (1 0), хз= (О 1), хз= (Π— 1), ха= (О 0), ха= (О 2), ха=(0 — 2), хе= ( — 2 0). Допустим, что первые тря имеют метку в„а другие четыре — метку вэ. а) Нарисуйте границу областей решений, полученную в результате применения правила ближайшего соседа. (Она должна состоять из девяти отрезков прямых.) б) Найдите средние значения выборок ш, и шэ и нарисуйте границу решения, соотиетствующую классификации х при присваивании ему хласса среднего значения ближайшей выборки. 6, Пусть ~р(х) У(0, 1), и пусть Аппроксимируйте эту оценку путем факторизации функции окна и разложе- ~11ав ння коэффцциента е ' " в ряд Тейлора в начале коордйнат.
а) Покажите, что при использовании нормированной переменной и=х(йч, т.тленная аппроксимация задается посредством в ! У2 й Задачи 1 'Кч 1 ! !1/2! 21 Ьу= — Š—.и,е =в,-', !! б) Положим, что н выборок очень тесно сгруппированы вокруг и=из. Покажите, что двучленная аппроксимация имеет два локальных максимума в точках, где из+и/ие — 1=0.
Покажите, что один максимум имеет место приблизительно прн и=не, как и требуется, если из((1, но что он сдвигается только к и=1 для из~~1. Нарисуйте кривую функции р„з от и для из=0,1; ! н 10. 7. пусть р„(х!в!) будет произвольной плотностью со средним !1; и коварна. цноиной матрицей Хв 1=1, 2.
Пусть у=в!к, и пуси индуцнрованная плотность р,(у)вг) имеет среднее значение ун и дисперсию огз. а) Покажете, что функция критерия (в) (Р1 )22) а12+ 2 минимизируется посредством в = (Х1+ ХЕ)-1 ()21 — )ьз). б) Если Р(вг) есть априорная вероитность для ви похажите, что (И1 РЕ) Р (в,) о;+ Р (в,) о; минимнзнруется посредством Ю (Р (в1) 21+ Р (в2) ХЕ) 1 (!21 )22) в) С какой нз зтнх функций критерия теснее всего связано У(н) из соотношения (70)? 8. Выражение — (у! — уг)' ! П,ПЕ в;Ечгг вуе.'и явно измеряет разброс между группами двух множеств выборок, из которых одно содержит в1 выборок, помеченных вз, а другое содержит лз выборок, помеченных вз. Аналогично у=~ Е Е (уг-уу)'+ — „; Е Х (уг-уу)' 1 1 У Е21 вуе,т'1 У Ез Вуе,т явно измеряет полный разброс внутри групп.
а) Покажите, что 21 = (В21 — 1ПЕ) + — 21+ — 22 ! 2 1 В1 П2 ! 2 ! 2 Е" 2 = — З1+ — З,. п, л, б) Если у=вгх, покажите, что м, минимизирующее 11, при наложенном ограничении /2=1 задается посредством г! ! ~= Х ~ — 51+ — 5~у! (ш — шз), Гл. 4.
Неларлиевричасхиа мешодаг 144 где г/1 ! й=(в,,)г l — 5,+ — 5,' (,—,), ~л, лз 1 к"~ в/= — х лг х еЯ/ 51 = ~ч~~ ~(х — в;) (х- в;)т. х еЯ/ 9. Пользуясь определением матрицы разброса между группами, данным для случая многих классов: с 5В = ~~~~~ лг (вг — гп) (вй — пг), 1=1 покажете, что 5и =- ((игла)/л) (вг — ва) (вг — ва)г, если с=2. 1О. Если 5л и 5п/ являются любыми веществеиныии симметричными матрицами размера йХ г(, то хорошо известно, что существует множество л собственных значений Д» ..., йю удовлетворяющих 15л — )г/5гн(=О, и что существует соответствующее множество л собственных векторов еи ..., е„, удовлетворяющих равенству 5ле/=х/5ц е; Далее, если 5гр — положительно определенная матрица, собственные векторы можно всегда нормировать таким образом, что е/г3 е =6/ е/Зле/ — — ач6//.
Пусть 5к=-%/15цЛГ и 5л=йг/5ийт, где %' — матрица размера йХл, столбцы которой соответсгвуют л различным собственным векторам. а) Покажите, что 5гп есть единичная матрица размера лхл и что 5л— диагональная матрица, элементы которой суть соответствующие собственные значения '). б) Каково значение,/=!5в!/!5~4? в) Пусть у=йггх преобразуется сначала масштабированием асей, что описывается невырождениой диагональной матрнцей Р размера лХл и последующим вращением, описываемым 'ортогональной матрицей Я: у'=()Ру. Покажите, что а' инвариантна относительно этого преобразования. ') Это показывает, что разделяющие функции в множественном днскриминантном анализе не коррелированы, Глава 5 ЛИНЕЙНЫЕ РАЗДЕЛЯЮЩИЕ Ф~НКЦИИ згк ВВЕДЕНИЕ В гл.
3 предполагалось, что вид рассматриваемых распределений вероятностей известен, и с помощью выборок производилась оценка их параметров. В данной главе известным будет считаться вид разделяющая функций, и выборки будут использоваться для оценки значений параметров классификаторов. Исследованию подлежат различные процедуры, применяемые для определения разделяющих функций, имеющие как статистический, так и нестатистический характер. Однако ни для одной из них не требуется, чтобы был известен вид рассматриваемых распределений вероятностей, и в этом смысле все их можно считать непарамегрическими. В данной главе будут рассматриваться разделяющие функции, линейные либо по компонентам вектора х, либо по некоторому данному множеству функций от х. Линейные разделяющие функции наиболее удобны с точки зрения аналитического исследования.
Как было показано в гл. 2, они могут быть оптимальными, если рассматриваемые распределения согласованы. Даже когда они не оптимальны, может быть следует пренебречь некоторыми качествами ради выигрыша в простоте. Вычислительный процесс значительно упрощается при использовании линейных разделяющих функций, и классификатор определенной структуры представляется наиболее подходящим средством для реализации в качестве машины специального назначения. Линейный дискриминант Фишера является моделью в принятом нами подходе.
Задача определения линейной разделяющей функции будет сформулирована как задача минимизации некоторой функции критерия. Вполне оправданным является использование выборочного риска в качестве критерия для задач классификации, т. е. средних потерь при классификации множества конструктивных выборок. Однако поскольку получение линейного дискриминаита, дающего минимальный риск, представляется достаточно трудным, в данной главе будет исследовано несколько аналогичных функций критерия, имеющих более простые аналитические выражения.
Наибольшее внимание уделяется исследованию сходимости различных процедур градиентного спуска для минимизации этих функций. Сходство многих процедур иногда затрудняет выделение очевидных раз- 146 Гл. Б. Линеонею разделяющие функции личий между ними. По этой причине в изложение материала включена сводка основных результатов, данная в табл. 5.1 в конце разд. 5.10. 6.2. ЛИНЕЙНЫЕ РАЗДЕЛЯЮЩИЕ ФУНКЦИИ И ПОВЕРХНОСТИ РЕШЕНИЙ 6.2Л.
СЛУЧАЙ ДВУХ КЛАССОВ Разделяющая функция, представляемая линейной комбинацией компонент вектора х, может быть записана в следующем виде: д (х) = ~чек+ ш„ (1) где че называется еесоеым вектором, а гое — ееличаной порога. В основу линейного классификатора для двух классов положено следующее решающее правило: принять решение озю если п(х)->0, н еею если д(х)(0. Таким образом, х приписывается к ее„если ска- ЛярНОЕ ПрОИЗВЕдЕНИЕ 4Ч'Х ПрЕВЫШаЕт ПОРОà — Еле. ЕСЛИ д(Х)=0, то обычно х можно отнести к любому из классов, однако в данной главе это соответствие будет считаться неопределенным. Уравнение д(х)=0 определяет поверхность решений, отделяющую точки, соответствующие решению ео„от точек, соответствующих решению еа,.
Когда функция д(х) линейна, данная поверхность представляется гилерллоекоетью. Если и х„ и х, принадлежат поверхности решений, то справедливо следующее выражение: зе'х, + еое = ячехе+ш„ или 4че(х,— х,) =О, так что 4ч есть нормаль по отношению к любому вектору, лежащему в гиперплоскости. В общем случае гиперплоскость Н делит пространство признаков на два полупростраиства: область решений Я, для ее, и область решений э1, для еае. Поскольку д(х))0, если х находится в области Я„то из этого следует, что нормальный вектор яе направлен в сторону э1ю В этом случае иногда говорят, что любой вектор х, находящийся в области аа„лежит на положительной стороне гиперплоскости Н, а любой вектор х, находящийся в области э(„лежит на отрицательной стороне Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
