Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 21
Текст из файла (страница 21)
4.12. Реализация кусочио-лииейиого классификатора. определяемые условиями (4.116), не обязательно покрывают все пространство. Если объект попадает в эту область, то кусочно- линейный классификатор не может принять решение о его при- ф 4.5. ДРУГИЕ РАЗДЕЛЯЮЩИЕ ФУНКЦИИ надлежности к определенному классу; эту область называют областью отказов. Решающее правило (4.116) состоит из М вЂ” 1 линейных разделяющих функций и логического элемента И(АХР) с М вЂ” 1 входами, которые принимают значения в1ен (Ь(; (Х) 1. Соответствующая блок-схема изображена на рис. 4.12. Поскольку каждая из параллельных цепей состоит из двух последовательно соединенных элементов, то такой кусочно-линейный классификатор иногда называют двуслойной машиной.
Если предположение о выпуклости областей не выполняется, то необходимо определить взаимные пересечения М вЂ” 1 гиперплоскостей и строить решающее правило в соответствии с этими пересечениями. Однако при этом классификатор становится весьма сложным для решения практических задач. Поэтому в данной книге рассмотрение будет ограничено только выпуклыми областямп. Вероятность ошибки решения для каждого класса е( можно- выразить через (М вЂ” 1)-мерну1о функцию распределения вероятности: е; =- 1 — Рг (Ь; (Х) ) О,..., Ь;м (Х) ) О/Х е= со;)— = 1 — 1 ..
~Р (й~~,..., (в;лю,'иЗВЬ1и~ . ЫА м (4.1171 о о '(функция Ьв (Х) — исключена пз рассмотрения) . Тогда общая. ошибка решения е = ~) Р(о,.) е,. (4. '118) 1 — 1 Задача теперь состоит в том, чтобы определить значения 1т п го для данного множества М распределений, прн наличии информации о структуре кусочно-линейного классификатора. Вследствие сложности этой задачи ее решение не является таким наглядным, как для линейного классификатора. Кратко отметим три приближенных метода решения задачи. 1) Можно подстраивать коэффициенты 1т и ио так, чтобы минимизировать вероятность ошибки решения е, определяемую формулой (4.118). Поскольку для е трудно получить явное математическое выражение, то е следует оценивать численными методами всякий раз, когда корректируются параметры 1т и ро.
Если случайные величины Х для всех классов распределены по нормальному закону, то возможно некоторое упрощение решения, так как в этом случае разделяющие функции Ьв(Х) также распределены нормально, а для р(Ь(1, ..., Ь(м/со() существует явное математи- 6,7 2,3 2,5 4,7 12,3 0,9 33 1,3 3,5 ага 3,6 24,5 Е14 4 еЦ У 2-.= 1 34,8 8,1 5,9 17,9 Л1 -уй -44 0птпененпе Рис. 4.13. Изменение 1 24'.
( ) ~ 240) Приме 30,4 5,2 16,0 4 1 е = — 7 е1= 13 75 т 4 1=1 *) [Фукунага, 1970а). гл. 4. линеиные клАссиФикАтоРы ческое выражение. Однако даже в этом случае интегрирование (М вЂ” 1) -мерного нормального распределения в первом квадранте, по-видимому, проще выполнить численным методом, например, таким, как метод Монте-Карло. 2) Линейная разделяющая функция между парой классов строится с помощью одного из методов, ранее рассмотренных М для случая распознавания двух классов. Вычисляются раз- 2 деляющих функций.
Эти функции без дальнейшей коррекции используются в качестве кусочно-линейной разделяющей функции. Если распределения всех классов нормальные с равными ковариационными матрицами, т. е. Х1 =... = Хм, описанная процедура эквивалентна применению бай ес овского классификатора. Если распределения существенно отличаются между собой, то дальнейшая коррекция решаюшего правила может привести к уменьшению ошибки. Однако часто оказывается, что уменьшение ошибки за счет подстройки параметров 1' и го относительно невелико.
3) Можно задать требуемый выход ((Х) кусочно-линейной разделяющеи функции и для нахождения оптимальных значе- Таблица 42 Вероятность ошибки для задачи с четырьмя классами *) ний У и го минимизировать среднеквадратичную ошибку между требуемым и действительным выходом. Требуемые выходные величины могут быть фиксированными или подстраиваемыми, как переменные, на которые наложены ограничения. К сожалению, з 4.5.
ДРУГие РАЗДеля1ощие ФУНКЦии даже для случая кусочно-линейной разделимости классов не существует доказательства сходимости этой процедуры. П р и м е р 4.5. Рассматривается задача с четырьмя классами, каждый из которых характеризуется нормальным распределением вероятностей. Эти распределения представлены в стандартных данных в гл. 2 (см. задания для составления программ). Поскольку все распределения нормальные, то можно для каждой пары классов определить линейный классификатор, оптимальный по критери1о минимума вероятности ошибки. В табл.
4.2 для различных пар классов приведены вероятности ошибок ен, 1, 1 = 1, 2, 3, 4, обусловленных использованием соответствующих оптимальных линейных классификаторов. Кроме того, в табл. 4.2 приводится сумма вероятностей ошибок: Хеп, В случае, когда кусочно-линейный классификатор был синтезирован с помощью линейных классификаторов без дополнительной коррекции параметров, ошибка решения вычислялась е„,% Ы пе е Пг Р4 лмпененл р~~ пп~ пппшмальных зиачиний общей ошибки ег в зависимости от компонент вектора ( — ) г'241 (- - - -) г'242', ( — — ) г'242 [Фукунага, 1970а] ч а ни е: )г244 — 1-я компонента вектора $'24.
по формулам (4.117) и (4.118) и обозначена в таблице 4.2 через н ет. Для того чтобы приблизить ошибку решения е, к оптимальному значению, осуществлялась коррекция решения путем изменения коэффициентов У и 129. При этом вычислялись соответствующие ошибки ег. На рис. 4.13 пзображено влияние параметра У24 на ошибку е,. Этот график приведен потому, что ве- 128 ГЛ. 4. ЛИНЕЙНЫЕ ПЛАССИФИКАТОРЫ 129 ЗАДАЧИ х СО1 й(Х) =,~~~ и,д;(Х) 0- Х ~ гив (4.119) представляет собои в функциональном пространстве линейнуго разделяющу1о функци1о, где г переменных ~;(Х) заменяют и переменных х в исходном пространстве. Аналогичным примером для бинарных входов является выражение (4.111), где исполь.зуется 2" новых переменных.
Другим важным случаем является использование квадратичных поверхностей, где г переменных д;(Х) задают так, что пер- 2 ными и переменнымп являются г;, г = 1, 2, ..., и, следующими и(и — 1)/2 — все парых;хь г, 1 = 1, ..., и, г Ф1, а последние гг переменных представляют собой хо г = 1, 2, ..., и. Относительно этого преобразования можно сказать, что для каждой квадратичной разделяющей функции в пространстве Х существует соответствующая линейная разделяющая функция в пространстве функции д,(Х). Переменные д,(Х) называются иризнаками. Выбор эффективной системы признаков представляет собой самостоятельный раздел теории распознавания образов и будет рассмотрен в главах 8,9и 10. ЗАДАНИЕ НА СОСТАВЛЕНИЕ ПРОГРАММ Составьте следующие программы: 4.1.
Синтез линейного классификатора, минимизирующего вероятность ошибки в случае нормальных распределений. роятности в24 и е42 явля1отся преобладающими слагаемыми в е,. 1так видно из рпс. 4.13, оптимальное значение ~24 смещено от-. носительно значения 1'24, соответствующего линейному классификатору для классов ш2, ги4. Однако при этом изменение ошибки ет находится в пределах 0,3%.
Влияние же других компонент вектора 1' намного меньше. Этот результат оправдывает для ,данного частного примера применение совокупности оптимальных классификаторов без дополнительной коррекции параметров. 4.5.3. Обобщенные линейные разделяющие функции. До сих пор, за небольшим исключением, нами рассматривались линейные разделяющие функции.
Одна из причин этого заключается в том, что при высокой размерности наблюдаемых векторов только линейные или кусочно-линейные разделяющие функции дают приемлемый компромисс между качеством распознавания и простотой реалнзацип. Другая важная причина заключается в том, что даже нелинейная разделя1ощая функцня может быть интерпретирована в функциональном пространстве как линейная разделяющая функция, т. е.
выражение Исходныс данные: стандартные данные 1 = 1, 2. О т в е т: рпс. 4.8. 4.2. Совместная нормировка двух нормальных распределений. После нор- мировки прпмеиитч корреляционный метод классификации. Проверить влия- ние величины порога на вероятность ошибки. Исходные данные: стандартные данные 1 = 1, 2, 4.3. Минимизация среднеквадратичной ошибки между требуемыми и действительныип выходами линейной разделя1ощей функции для следующих вариантов: а) использовать выражение (4.45), где Г= [1 1 ... 1]', б) использовать выражение (4.75), где Г = [1 1... 11т; в) использовать выражения (4.76) и (4.77) с соответству1ощим г,(1); г) использовать выражение (4.74). Исходныс данные: стандартные данные 1= 1, 2, 4.4.
Минимизация среднеквадратичной ошибки между требуемыми и действительнымп выходами линейной разделяющей функции для бинарных входов. Требуемые выходы следует определить в соответствии с выражени- еи Р(оэ,) р(Х/оэ,) — Р(ю~) р(Хгю~). Найти линейную разделяющу1о функцию, в случае трех входов. Исследовать влияние величины порога на вероятность ошибки. 4.5. Использовать задание 4.3, б) для синтеза линейных классификато- ров для всевозможных пар классов и вычислить ошибку для случая иногих классов. Исходные данные: стандартные данные 1 = 1, 2, 3, 4.
ЗАДАЧ1Л 4.1. Распределения Пирсона типов 11 н УП определяются следующими выражениями: п и т тнп П. Р(У(ю,) = А П сс.1 1 — ~ а;; (у. — а..)з ;=1 п н — т тип у11: Р(У!ю,) =:-' Ц~;;] 1+.'Е ~1,(у; — ";1)в а) Покажите, что байесовскне классификаторы для этих распределений являются квадратичными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
