Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

Разделяющая функция д(х) представляет собой алгебраическое расстояние от х до гиперплоскости. Это становится более очевидным, если выразить х в следукнцем виде: х = хр+ г — -))-, где хр — нормальная проекция х на гиперплоскость Н, а г — соответствующее алгебраическое расстояние, положительное, если х находится с положительной стороны гнперплоскости, и отрица- е.2.

Линейные разделяющие (йуяхйии и пееерхиесши реиыяиа 147 тельное, если х находится с отрицательной стороны гиперплоскостн. Тогда, поскольку н(х„)=0, й' (х) = ттгх + ае = т ~) хе (1, или я (х) т= —. )(ый ' В частности, расстояние от начала координат до гиперплоскости Н выРажаетсЯ отношением гве/Пхе((. Если ше(0, начало кооРДинат находится с положительной стороны Н; если сне~О,— с отрицательной стороны Н. Если и~а=О, то функция л(х) становится одно- Рнс. 5.1. Лннейнея граница областей решений й(х)=геен+ве=О. одной хе'х, и гиперплоскость проходит через начало координат. еометрическая интерпретация 'данных результатов приведена на рис.

5.1. В заключение можно сделать вывод, что линейная разделяющая функция делит пространство признаков поверхностью решений, представляющей собой гиперплоскость. Способ ориентации данной поверхности задается нормальным вектором хе, а положение ее— величиной порога гве, Разделяющая функция д (х) пропорциональна взятому со знаком расстоянию от х до гиперплоскости, при этом д(х))0, когда х находится с положительной стороны гиперплоскости, и д(х)~0, когда х находится с отрицательной стороны. Гк, б. Линейные разделяюгцие функции 5.2.2.

СЛУЧАЙ МНОГИХ КЛАССОВ Существует немало способов создания классификаторов для многих классов, основанных на использовании линейных разделяющих функций. Например, можно свести задачу к с — 1 задачам для двух классов, где решением (-й задачи служит линейная разделяющая функция, определяющая границу между точками, соответствующими решению сон и точками, не соответствующими решению ш;. При ином подходе следовало бы использовать с(й — 1)/2 линейных разделяющих функций, по одному для каждой пары классов.

Как показано на рис. 5.2, оба эти подхода могут приводить к обла- Рнс. 6.2. Линейные гранады областей решений для задачи трех классов. а — дихотомия ич/не мь б — дихотомия ач/ш/. стям, аналогичным представленным здесь заштрихованными областями, в которых классификация не определена. При данном исследовании указанная трудность будет исключена в результате использования подхода, принятого в гл. 2, при котором определяется с линейных разделяющих функций вида д,(х)=вг,'х+гнг„ /=1, ..., с, (2) и х приписывается к шы если д;(х))д/(х) для всех /Ф1; в случае равенства классификация остается неопределенной.

Получаемый таким путем классификатор называется линейной лииииной. Линейная машина делит пространство признаков на области решений, при этом д; (х) является наибольшей из разделяющих функций, если х находится в области Яь Если области Я1 и Я/ соприкасающиеся, то границей между ними будет часть гиперплоскости Ом, определяемая следующим соотношением: д~ (х)=д/(х), или (зу — /) г х + (гнею — /е) = О.

бХ Обобщенные аииебкме риаделлющие функции 149 Из этого сразу же следует, что вектор ту,— шэ нормален гиперплоскости Оц, а взятое со знаком расстояние от х до Ои выражается отношением (дз — д~)/11(туз — тут)11. Таким образом, в случае использования линейной машины важны не сами векторы веса, а их разности. При наличии с(с — 1)~2 пар областей не требуется,. чтобы все они были соприкасающимися, и общее число участков гиперплоскостей, входящих в поверхности решения, часто может быть менее чем с(с — 1)12. Примеры двумерных случаев для таких поверхностей представлены на рис.

5.3. и 8 Рнс. 5.3. Границы областей решений, полученные с помощью линейной машины. и — задача дла трех классов, б — задача дла, пати классов. Легко показать, что области решений для линейной машины являются выпуклыми. Данное ограничение определенно снижает возможности классификатора. В частности, каждая область решения должна быть односвязной; это делает линейную машину в наибольшей мере соответствующей задачам, для которых условная плотность р(х(оз,) унимодальна. В рамках этих ограничений линейная машина представляет собой достаточно гибкую конструкцию, допускающую простое аналитическое исследование.

й,а. ОБОБЩЕННЫЕ ЛИНЕЙНЫЕ РАЗДЕЛЯЮЩИЕ ФУНКЦИИ Линейная разделяющая функция н(х) может быть записана в следующем виде: я(х) =сне+ ~ ге~хо (3) с ! где коэффициенты снз являются компонентами весового вектора ш. Добавив в это уравнение члены, содержащие произведения двух Гл. Е.

линейные разделяющие функции компонент вектора х, получим квадратичную раэделяккцую функцию д(х) =ю,+ ~~'., ю;х;+ ~ ~ и;гх;хр Не нарушая общности, можно положить гегт — — инь поскольку х;х~ —— =хгхь Таким образом, в формулу квадратичной разделяющей функции входят й(й+1)/2 дополнительных коэффициентов; это позволяет получать более сложные разделяющие поверхности.

Разделяющая поверхность, определяемая уравнением а(х)=0, является поверхностью второго порядка, или гиперквадрикой. Если симметричная матрица %7=[ви) невырожденна, то линейные члены в а(х) могут быть исключены путем преобразования системы координат, и основное свойство разделяющей поверхности может быть описано с помощью масштабированной матрицы Ж'= Иг((в'Ф'-'ив — 4иь). Если матрица гг" является положительным кратным единичной матрицы, разделяющая поверхность будет гиперсферой. Если %' — положительно определенная матрица, то разделяющая поверхность — гиперэллипсоид, Если некоторые характеристические числа матрицы Ф положительны, а другие отрицательны, то поверхность является одним из гипергиперболоидов.

Как было отмечено в гл. 2, это все виды разделяющих поверхностей, которые появляются в общем случае многомерного нормального распределения. Продолн1ая вводить дополнительные члены, такие, как иьм„х;х~х„, можно получить класс полиномиальных разделяюи(их функций. Указанные функции можно рассматривать как усеченные разложения в ряд некоторой произвольной функции у (х), что в свою очередь ведет к представлению об сбоби(енных линейных раэделяюи(их функциях, имеющих следующий вид: у д (х) = ~~,', а;у; (х), (4) или д(х) = а'у, (5) где а есть Н-мерный весовой вектор, а 3 функций у;(х) (иногда называемых «р-функциями) могут быть произвольными функциями от х.

Выбирая указанные функции соответствующим образом и полагая й достаточно большим, можно аппроксимировать любую заданную разделяющую функцию таким разложением в ряд. Полученная разделяющая функция нелинейна относительно х, однако линейна относительно у. Отображение точек й-мерного пространства х в Й- мерное пространство у осуществляют 3 функций у~ (х). Однородная разделяющая функция а'у разделяет точки в данном отображенном пространстве посредством гиперплоскости, проходящей через на- 5.8.

Обобеирнные линейные риэделлеощие ф нн ии 151 чало координат. Таким образом, переход от х к у сводит задачу к определению однородной линейной разделяющей функции. Некоторые преимущества и недостатки данного подхода можно продемонстрировать на простом примере. Пусть д(х) будет квадратичной разделяющей функцией ае(х) =а,+а,х+а,х', так что трехмерный вектор у задается матрицей -И Переход от х к у показан на рис. 5.4.

Данные, по существу, остаются одномерными, поскольку изменение х соответствует появлению кривой в трехмерном пространстве у. Таким образом, отсюда сразу 0 х Рвс. 5,4. Отсбражение в случае у= (!ххе)е. вытекает тот факт, что, если х подчиняется вероятностному закону р(х), отображенная функция плотности р(у) становится вырожденной, обращаясь в нуль везде, кроме кривой, где она принимает бесконечно большие значения. Приведенный пример представляет собой общую задачу, возникающую в случае, когда «Ъ4, и отображение точек происходит из пространства с меньшей размерностью в пространство с большей размерностью.

Плоскость Й, определяемая уравнением аеу=О, делит пространство у на две области решений: И, и й(е. На рис. 5.5 показана разделяющая плоскость, определяемая вектором а=( — 1 1 2)', и соответствующие области решений й(, и Яе в пространстве х. Квадратич- Гл. 8. Линейные равделяющае функции ная разделяющая функция д (х)= — 1+х+2х' положительна, если х( — 1 нлн если х~0,5, так что область Я! является многосвязной.

Таким образом, хотя области решений в у-пространстве выпуклые, это отнюдь не обязательно имеет место в х-пространстве. Даже прн наличии сравнительно простых функций уе(х) поверхности решений, отображенные в х-пространство, могут быть весьма сложными. К сожалению, «проклятяе размерности» усложняет практнческое использование возможностей классификатора. Полная квадратячная разделяющая функция включает Ы=(д+1)(е(+2)12 членов.

Если е( сравнительно велико, скзжем е(=50, то требуется вы- -йо О ч5 Рис. 5.5. Области решения в х-пространстве и у-простраиства. чнсленне большого числа членов. Включение кубнчных членов н членов с более высоким порядком приводит к еще большим значенням Э. Более того, 3 компонент весового вектора а должны определяться нз выборок. Если Й придается смысл числа степеней свободы разделяющей функции, то естественным будет требование, чтобы число выборок было не меньше, чем это число степеней свободы.

Характеристики

Список файлов книги