Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 23
Текст из файла (страница 23)
Признаки, имеющие высокие значения добротности а„в заданном алфавите, должны получать преимущественные веса по сравнению с признаками, имеющими низкие или нулевые значения добротности. Вес уь Ьго признака естественно определить как отношение добротности ««„ этого признака к средней добротности а признака в описании: те=се»/а. (3,41) Полученная указанным образом система весов уь (й = 1, и) дает характеристику эффективности каждого из и признаков исходного описания при заданном решающем правиле.
Достоинство изложенной методики оценки эффективности признаков исходного описания в том, что она непосредственно учитывает конкретный, принятый в данной системе алгоритм распознавания и может быть применима как при бинарных, так и непрерывных значениях признаков; на ее основе может быть осуществлена дальнейшая, более тонкая (точная) оценка эффективности признаков. Подавляющая доля ошибок при распознавании отдельных классов объектов приходится на сравнительно небольшое число «трудных» для классификации классов, т. е.
классов, расстояния между которыми в проатранстве признаков относительно малы. Вместе с тем для дру- 98 ' их классов («легких» классов) расстояния до ближайшего из классов в пространстве признаков настолько велики, что ошибки при их рас.познавании практически могут отсутствовать. При этом целесообразны пути на повышение эффективности описания «трудных» классов при снижении эффективности описания (в разумных пределах) «легких» 'классов. Часто при этом приходится поступаться эффективностью описания большего количества классов в угоду эффективности описания меньшего числа классов.
Поэтому средняя эффективность описания всех классов снижается. Переоценка эффективности признаков исходного описания находит : свое количественное выражение в изменении весов признаков, что может быть представлено следующим образом. На базе матрицы Е„и вычисленных весов у» признаков определяют;; ся взвешенные матрицы Е» (й = 1, п): (3,42) !! Не )!='Ь)! Ней! ,, они характеризуют попарную различимость классов по й-му признаку с учетом его веса в описании.
Сумма матриц Ее по всем й признакам дает матрицу Е', характери' зующую попарную различимость классов в рамках исходного описа;, ния с учетом эффективности каждого из признаков: а !! н' !! = ~ )! не )!. е=! (3.43) (3.44) 4» 4 Среди элементов матрицы Е' отыскивается наименьший по величи.', не (поскольку матрица Е' симметричная, то рассматриваются только ~' элементы над главной диагональю или под ней). Если в матрице имеется ,' несколько элементов с равным и наименьшим значением, то выбираетея один, любой их них. Выбранный элемент е 1' матрицы Е' указывает, что наихудшей различимостью характеризуются классы А, и А1, а его ',величина дает количественную меру расстояния между этими клас.',, сами. Далее из матрицы Ее выбирается такая, для которой различи,р мость классов А; и А1 минимальна.
Этот фактлегко устанавливается : по минимуму суммы средних полезностей в 1'-м и (ъм классах, т. е. :Ь ' ш(п (ее~и + е«)13). Если таких матриц несколько, то выбирается одна, любая из них. ю) Признак, характеризующийся выбранной матрицей, исключается «'".".. иа исходного описания (т. е. ему присваивается вес, равный нулю). 4)„, Исключение этого бесполезного (вредного) при разделении классов А ! я ~~",.'"А1 признака может попутно улучшить различение некоторых других классов, но в общем случае найдутся и классы, для которых будут иметь место ухудшение классификации классов. Исключение й-го признака означает одновременно и исключение матрицы Ее. Ф Следовательно, ее нужно вычесть из матрицы Е'.
!! е' (! — )! н» ))= !! н )! Описанная выше процедура повторяется для матрицы Е", затем для матрицы Е'" и т. д. Процесс может быть остановлен либо по достижении наименьшим по величине элементом матрицы Ед некоторого заранее выбранного порога, либо по достижении следующей конфликтной ситуации: попытка увеличить различие для некоторой наиболее трудно классифицируемой пары классов приводит на некотором шаге к появлению другой, до этого шага не наихудшей, пары трудно разделимых классов. Таким образом, описанная методика оценки эффективности признаков распознавания позволяет из исходного описания классов исключить наименее информативные признаки, оставив наиболее информативные, и тем самым повысить вероятность распознавания классов объектов.
й 3.8. ИНФОРМАТИВНОСТЬ СТАТИСТИЧЕСКИ НЕЗАВИСИМЫХ ПРИЗНАКОВ И МЕРА НАДЕЖНОСТИ ПРИ РАСПОЗНАВАНИИ ОБЪЕКТОВ. МИНИМИЗАЦИЯ ПРОСТРАНСТВА ПРИЗНАКОВ В настоящее время ие существует единого мнения о способе формирования оптимальной сисп!емы признаков распознавания — такого их набора, который использует минимально необходимое число признаков и их частных значений (градаций), обеспечивающих заданную вероятность распознавания. Поэтому поступают следующим образом. На основании предыдущего опыта и интуиции человека выбирается система из большого числа признаков с большим числом возможных значений каждого, после чего в процессе обучения машины эту систему минимизируют по тому или иному критерию (см.
(12, 13]). Цаиболее широко в теории распознавания применяется понятие информативности признаков по Шеннону (см. П4]). В соответствии с этой мерой информативность некоторого й-го параметра относительно множества классов объектов А! (! = 1, т) можно оценить как разность начальной энтропии системы и энтропии решения по этому параметру: /д =Но(А) — Н (А/хд), (3.45) где Н, (А) — начальная энтропия системы; Н (А(хд) — энтропия решения по параметру хд.
Пусть параметр хд может принимать / дискретных значений (градаций) хд/ (/ = 1,2,..., '/). Тогда энтропия решения (см. (13]) по /-му значению параметра хд определится как ' Н (Ат/хд/) — ~~ Р (А;/хд/) !ае р (А 1/хд/), (3.40) 1 1 где р (А1/хд/) — условная вероятность отнесения объекта к классу А, о /-й градации признака хд. Условная вероятность по критерию Бейеса будет равна р(А1)р(хд//А1) р(АВ р(хд//А1) р (А 1/х1,/) Р (хд/) т ~ р(А1) р(хд /А;) 100 где р (А !) — априорная вероятность класса А! среди всех и! классов; ' р (хд/) — вероятность появления /-й градации /г-го признака по всем , классам объектов; р (хд/(А1) — условная вероятность появления /-го " значения й-го признака в классе А! объектов. После подстановки этого выражения в уравнение (3.46) получим формулу для расчета энтропии решения в следующем виде: 1 Н (А„,/х1,/) — лР р(АП р (хд//А1) Х р (хд/) х 1аи ' ' — — Р Р(АВ Р(хд//А1)х р (А;) р (х!и/А!) т р (хд/) ~ р(АВР(хд//А1) (3.47) К 1акр(А1)р (хд./А1) — ~~ р(АВ р(хд//А1) 1аи ~' р(А!) Р(хд//А1) 1 — ! 1 Для получения энтропии решения следует найти сумму значений величин Н (А /хд/) по всем градациям / = У с весами, пропорциональными вероятности появления каждой градации, т.
е. р (хд/). Тогда з га Н(А/хд) = — ~ р(хд/)Н(Ад!/хд/)= — ~ ~ р(А1, х1, ) Х 1=1 / 1! 1 х 1аир(А1, х1/)+ ~' ~~~~ р(А1, х1/) 1аи ~Ч'" р(А1, хд/), /=11=1 1 1 (3. 48) где р (Аь хд/) = р (А !) р (хд//А !) — совместное распределение вероятностей значений признака хд для класса А,. Так как начальная энтропия системы Нд(А) = — ,'д~', р (А1) 1аи р (А1), 1=1 101 то, подставив найденные слагаемые в (3.45), получим окончательное выражение для определения информативности й-го параметра: т т /д= — Ча р(А!) 1аяр(А!)+ ~~ ~ р(А!. Хд/)!ах р(А1, Хд/)— 1=1 /=1!=1 — ~~ ', р(А1, хд/) 1ак ~„! Р(А1, хд/). (3,49) 1=11=1 1 Это выражение основное для вычисления информативности призна- ков.
Из него следует, что чем точнее измеряется значение каждого пара,(у' метра и чем больше используется количество градаций признаков тем большую информацию можно извлечь при использовании этого при- 4) ' знака. Однако следует помнить, что этот путь ведет к увеличению затрат памяти ЭВМ и расходу машинного времени при реализации этапов обучения и классификации. Поэтому желательно найти наименьшее число признаков и их градаций, обеспечивающих требуемую вероятность распознавания.
Минимизация пространства признаков. Иногда этот процесс называют нахождением минимального описания классов объектов. Этот путь минимизации системы признаков можно интерпретировать следующим образом [15). Если по оси абсцисс отложить значения вероятнастей р (ха!) последовательно для всех градаций /' какого-либо признака хю а по оси ординат — соответствующие им значения Н (А!/ /хь,), то можно построить график, аналогичный графику, показанному на рис. 3.15, Площадь, ограниченная осью абсцисс и кривой, пропорциональна энтропии решения по параметру хю а площадь между уров- нем Н, (А) и характеристикой — инфор/А1 к// мационному содержанию г'а парамет- ра хз. /к Для сокращения общей системы признаков можно отбросить некоторые градации параметров. При этом величина потери информативности признака Мт при ликвидации границы между /ьй и (/ — 1) -й градациями связана корреляционной зависимостью (с коэффициентом взаимной корреляции, равным рис, 3.15. График зависимости 0,95) с величиной!р (хат) + р (хам г)) ! н(А /хз!)=/!Р(хаг)1 ~Нт (А,./х„) Нг ! (К1/ха)! (на Рис,3.15 этому произведению соответствует густо заштрихованная площадь).
Процесс минимизации системы признаков и будет состоять в том, чтобы лчквндировать те границы, для которых эта площадь минимальна. Следует иметь в виду, что после отбрасывания очередной границы характер распределения вероятностей признаков меняется, что заставляет всякий раз вновь строить характеристику Н (А !/хю!) = / !Р (хьг)] и по ней выбирать следующую для отбрасывания границу. Поясним основные принципы работы алгоритма минимизации системы признаков (вычисление величины потерь информативности признака А!1 при отбрасывании очередной границы между смежными градациями признака проводилось непосредственно прямым путем). Рассмотрим смежные границы между градациями / — 1 и /, Соответствующие им составляющие энтропии решения по ха-му признаку в соответствии с (ЗА8) будут равны: Нт-! = ~ч~~ р; 1оя р! + Р 1оя Р = — ~~~~ р1 1оя р;/Р; ! 1 1=! и1= Х Ф!оке!+!г!ока= — ~ 41!оке!Я, ! 1 1=1 где Р! Р (А;; ха ! — !), Р = ~~'.~ Рг, !)1 = Р (Аь ха ), 1=! 1 102 После удаления границы между этими градациями составляющую нтропии, соответствующую объединенным градациям, можно найти как ННГ ! — — — ~~~~ (Р1+О;) 1О5 (Р1+4!)+(Р+!)) 1ед(Р+~) 1=! — (р;+рл) 1ок— Р! +Е! Р+О' Результирующая потеря информативности признака равна разности новой и старой энтропий: ! е ец-т3 аН =Н// ! — (Нг+Н !).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
