Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 35
Текст из файла (страница 35)
Возможно также разделение исходной совокупно- сти классов на группы ло принципу: первый класс и все остальные, , второй класс и все остальные, исключая первый, и т. д. Число порогов :;в этом случае равно и (т — 1), а число этапов опознавания может ко- лебаться от 1 до т — 1. Иногда удобно выделить олределенную груп'.пу классов, рассматривая ее на этапе 1 как один класс.
Однако чаще 'Всего назначение порогов ло признакам в лороговых системах произ,:'Водится в соответствии с первой процедурой, изложенной 'для случая многоальтериативной ситуации. При этом используются развитые в ,„,,леории статистических решений методы назначения порога Пц» ло 1(ВРизнакУ х, лРи дихотомии классов Аг и А» только ло этомУ пРизнакУ.
П р н м е ч а н я е. Вопрос об оптямальностн всей совокупности назначен;ных такам образом порогов остается, конечно, открытым. Типичные кривые хг»1 (х;) и х»» (х,) в случае пересечения классов "приведены на рис. 4.17. Так, например, критерий Бейеса, для применения которого помимо плотностей распределения д»1 (х») и я»» (х,) надо знать априорные ве- роятностн $», $» и цены решений каждого типа, минимизирует бейесов риск Т ($, и).
Если условиться, что ае как возможное решение исключается, то, используя (4.16), можно показать, что Т(6, н) минимизируется в данном случае, например, при следующих нерандомизированных решающих функциях: )'1, если й»С»скс»(хс)+й»С»сксс(хс))1»С»»кс»(хс)+1сСс»басс(хс), [О в остальных случаях; [ 1, если 4»С»скс»(хс)+4»Сссксс(хс) < к»С»»яс»(хс)+й Сс» асс(хс), [ О в остальных случаях. (4.26) Далее положим, что коэффициент правдоподобия Л (хс) = дсс х Х (хс)/йс» (хс) — монотоннаЯ фУнкциЯ своего аРгУмента.
Тогда, как видим из (4.26), можно фиксировать такое единственное значение при- знака хс — — Пць 'при котором Т($, м)=Т(6)=$»[С»»чс»с+С»срс»с[+$с[Спрсц+Сцчсс»1, (4.27) где с)с»с = 1 — рць рцс = [йс» (хс) с[хс, с)сс» — — 1 — рц;, »ссс» —— ссп» = ) ягсс (х,) с(хс; значение П,», нахоДитсЯ из соотношениЯ Псс» ) ап (нцс) 5»(сп — сн) цс = яс»(Нцч) йс(Сс» — Сп) ( ) 4.28 Для случая использования критерия «идеального наблюдателя» С»» — — Сц — — О, С», = С,» — — 1 и найденное из (4.28) значение порога П,», в этих условиях минимизирует полную вероятность ошибки: пцс ..=Ь» ~ а.»(..)...+Ь "~ „,(.,)", цс Минимаксный критерий соответствует критерию Бейеса при наи- более неблагоприятных значениях 6» и $с.
Дифференцируя (4.27) по О, найдем, что для минимаксного решения сц ос я+ с»с лыс сп лсц+ сц с»сс». (4. 29) И скомое значение Пцс удовлетворяет этому соотношению, каждая часть которого дает величину минимаксного риска. Для приведенно- го выше выбора цен уравнение (4.29) будет иметь видпсн вц(хс) ссхс = ( лсс (хс) Ахс, (4. ЗО) пс.с с где каждый из интегралов равен минимаксной полной вероятности ошибки по данному признаку.
Если при этом распределения ясс (хс) и 8'сс (хс) нормальные, то и = ъс,'ят-яш сд = ос»+ос» 160 де спс», йссс, ас», оц — оценки математических ожиданий и средних квадРатичных отклонений этих распределений. Пример графического решения уравнения (4.30) на основе опытных 'данных приводится на рис. 4.18, где Я (хс) и 1 — бс» (хс) — частоты событий Хс ( х; и Хс ) х, для классов А, и А», Ас», Ась Ас»»в интервалы значений х, для А;, А, и обсций интервал соответственно. Величина Пс»с определяется как абсцисса середины участка оси :абсцисс, для которого [1 — 6;» (х,) — Я (хс) [ имеет минимальное ,значение.
Иногда плотности распределения пс» (хс) и дсс (хс) имеют такой вид, при котором коэффициент правдоподобия является немонотонной функцией своего аргумента. Тогда для 'случая соотношения (4.28) возникает не- ~сс»гс) ».8Я(г») .обходимость в назначении по признаку У ' хс нескольких порогов. Если же классы не пересекаются по отдельным признакам, то выбор порогов по этим призна- рй СсИ , кам не представляет затруднений. сс л ш После назначения порога П,»с в со- с' ' ответствии с некоторым критерием зна. чение минимизируемого этим критерием р 4 Гб Рис.
4,18, Графическое решифункцнонала можно использовать для иие задачи иазиачеиия порога оЦенки РазДеЛителъных свОйств или»ус»с пРи дихотомии классов Ас степени его информативности, а также и Ас по признаку хс ';для сопоставления признаков с этой точ:ки зРения с целью установления минимального маршрута измере,',ния реализации х. Пороговые системы в значительно меньшей степени реагируют на . фоРму плотностей распределения признаков. Достоинством рассмо- тренных выше алгоритмов опознавания является также их сравнитель;, ная простота, а изложенная методика назначения порогов по призна- ~ кам пригодна для широкого круга алгоритмов (в том числе и алгорит- ', мов Розенблатта и Гамба).
5 4.6. ОБучение эвм НО этАлОнным ОписАниям Предпосылки к разработке алгоритма обучения ЭВМ по эталон, ным описаниям классов. Выскажем некоторые соображения, пояс'; няющие описанные ниже алгоритмы обучения и классификации, ис; пользующие эталонные (наиболее представительные) описания ,': классов объектов. Принятие решения о принадлежности неизвестной реализации к тому или иному классу в этом случае делается в соответствии со значением ее функции принадлежности.
При выборе эталонных представителей каждого класса полностью ,' откажемся от статистического подхода и воспользуемся принципами [ выделения эталонов, основанными на методах нахождения минималь,'' ных покрытий (см. [20, 21!). Метод наложения минимальных покры[' '" тий по матрице функций принадлежности пригоден н для случая много' связных и многомерных областей обучающих реализаций классов ' 6 з .сека 1б! объектов. Единственное ограничение к использованию этого метода— необходимость не иметь полного совпадения изображений (векторов реализаций) двух классов объектов (в многомерном пространстве признаков это ограничение не является жестким). С целью приведения всей совокупности реализаций к матричной форме, удобной для последующего выделения эталонов, воспользуемся методикой вычисления функций принадлежности, полностью некритичной к вероятностным характеристикам классов и обеспечивающей практически стопроцентное распознавание при наличии представительной обучающей выборки. Задачу обучения машины по эталонным описаниям можно сформулировать следующим образом.
Пусть в и-мерном пространстве признаков задано множество реализаций объектов « = (х»„х»», ..., х»!„..., х«) (! = 1, 2, ..., и; е = 1, 2, ..., й), которое разбито на ряд подмножеств вида х = (х„х„..., ««), соответствующих множеству классов объектов А; (!' = 1, 2, ..., и!).
Требуется выделить в пространстве реализаций х минимальное число областей (эталонов), позволяющих классифицировать лк»бую реали- . зацию из этого множества со стопроцентной вероятностью. Прежде чем перейти к непосредственному рассмотрению алгоритма обучения, сделаем несколько предварительных замечаний.
При реализации параметрического пути распознавания основные трудности заключаются в оптимальном выборе системы координат (признаков) и в отыскании метода минимизации описаний объектов в этой системе признаков. Непосредственное запоминание описаний классов А объектов, представленных й! реализациями каждый, в л-мерном пространстве признаков потребует ой!а ячеек памяти машины и время для распознавания 1„м« = тй»пМ„ю где Г»г',р — время одного сравнения неизвестной реализации х,! с реализациями множества х.
Такой способ хранения информации об объектах в реальных задачах приводит к неоправданному увеличению объема памяти ЭВМ и времени распознавания. Поэтому необходимо минимизировать объем исходной информации, например, выделением минимального числа наиболее представительных для каждого класса эталонов. Формированию эталонов должны предшествовать, как правило, некоторые преобразования пространства признаков, обеспечивающие наилучшие условия дальнейшей процедуры минимизации.
Существуют следующие критерии, определяющие оптимальность преобразования системы признаков (см. [8]): а) минимум среднеквадратичного расстояния между реализациями одного класса объектов; б) минимум максимального расстояния между реализациями одного класса объектов; в) минимум среднеквадратичного расстояния внутри классов при максимуме его между классами. Поскольку описанный ниже алгоритм распознавания по эталонам хлассов работает на каждом шаге по дихотомическому принципу разделения (один класс — все остальные), целесообразно на каждом шаге рассматривать лишь тот габарит (область пространства признаков, габаритная область), в котором находятся все реализации минимизируе1б« ого класса. Это предусматривает такое преобразование системы ко'(»рдинат и выбор в ней габарита, которое осуществит минимизацию ' реднего расстояния между реализациями основного («своего») класса 'и числом реализаций остальных («чужих») классов, попавших в га' барит.
Из интегральной геометрии известно, что для произвольных зам:,;кнутых ограниченных множеств 3 справедливо изопараметрическое '', неравенство вида Р (3) ~» йо«ы о (3)!» — !!!«, где Р (3) — поверхность , множества 3; о (3) — объем множества 3; ы», — объем л-мерного еди' ничного шара. Для шара это неравенство обращается в равенство, т. е. ,шар имеет минимальную поверхность из всех тел равного объема.
Так ;, как минимум среднего расстояния между точками множества при его ли, нейных преобразованиях с сохранением объема достигается для мини,,'мальной поверхности множества, т. е. для гиперсферы, то, приняв в ка- . честве разделяющих классы поверхностей гиперсферы, целесообразно 'решать задачу распознавания в классе евклидовых метрик, для кото' рого « »! («! «г) ~/ ~)„»»~ («ж — «р«1» »=-1 где ы« — весовой коэффициент л-го признака; «и «р — 1-й и р-й век' р тор-реализации; х!ю хр„— координаты вектор-реализаций х! и хр по й-му признаку.
Евклидова метрика наиболее удобна и наглядна в случае использования непрерывных признаков. Для систем дискретных признаков чаще применяют хэммингово расстояние вида ч »!»(«!, «г)= ~ »»«~ «ц,— «~ц,~. «=1 В качестве разделяющих поверхностей здесь обычно используются гиперпараллелепипеды. При использовании метрики !!! (хь хр) для описания одного эталона потребуется и + 1 число, для второго — 2а чисел. Для сравнения .реализации с эталоном в первом случае необходимо произвести ц + 1 .вычитаниеип умножений, во втором — 2п вычитаний, так что проигрыш во времени при евклидовой метрике будет незначительным. При выборе в дальнейшем евклидовой метрики помимо указанных соображений следует принимать во внимание наглядность ее и удобство представления результатов в процессе проверки работы сложной ф, программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
