Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 24
Текст из файла (страница 24)
(3. 50) Всегда ЛН; ) О. Для доказательства неравенства оНт) 0 подставим значения всех членов, :,составляющих выражение (3.50). Тогда м м Рю+Чт чч Рт 5Н1= — У (р + о ) 1ок Р+Ц + л рм!оя — + т 1 м=! М + ~, 4„,1оя —. и=1 При этом исходное неравенство приводится к виду М М м р ~~ — !ок — + 1г ~ — !оя — (Р+!)) ~а ~Х (В) Р+О Рю Чт Введем обозначения а,„= Р, ьж= м,.
А = Р+ 11! В = Р Р) (). Тогда (Ьиеравенство (В) запишется в виде м М м А ~и~', а„, !ода,„-)- В ~~~ Ьм 1ок Ь„, — ~чз~ (Аа,„-1-ВЬ,„) Х п~ 1 и=! и=! Х !оя(Аа +ВЬ ) ~0, (С) .1 где 0 ~ а,„~ 1, О ( А < 1; О < Ьы < 1, О ( В ( 1. ,! м ф;; Если через Н (а) и Н (Ь) обозначить функции Н(а)= ~~', аю !ок аю, ./,' м=! ч ! М Н(ь) = Х Ь 10КЬ Ф м 1 то неравенство (С) примет вид А Н (а) + ВН (Ь) — Н (А а + ВЬ) ) О.
Последнее справедливо для функций Н (а), выпуклых вниз. У.: Составим матрицу вторых произиодных функции Н (аз, аз, ..., ам): дз Н (а) Ф: О, если 1ЧЬ/! да! да! д' Н (а) > О, если 1=-/, так как 0 (а! <1. да! да/ 103 Тогда матрица 1 а( 1 ав ФН(а) да(в 1 ам и будет положительно определена. Следовательно, функция Н (а) выпукла вина, неравенство (О) справедливо, а исходное неравенство (В) доказано. Таким образом можно рассчитать потерю информативности признака при ликвидации любых границ между его градациями, В качестве условия окончания цикла отбрасывания градаций служит величина порога потерь информативности по всем признакам (ЕЛ/д) „либо по конкретному признаку (У (Л/д) „,. Можно также задать максимальное число градаций, которое необходимо остал вить в процессе минимизации.
На рис. 3.16 для признаков х„хв, хв при- ведены характерные кривые изменения их инду формативностей в зависимости от числа градаций признаков. Анализ этих кривых по всем признакам позволяет провести минимизацию () г б !р (р у() 7' числа градаций с точки зрения затрат памяти распознающего устройства и суммарных по- !6 ~~афин." 'ави терь информативности параметров Распозна'призиаков «ь «„«, вания.
Поэтому целесообразно выбрать 7 = 5 по точке перелома большинства кривых. В табл. 3.2. приведены результаты минимизации системы признаков. В эксперименте использовались три класса объектов, описываемые системой из 15 признаков и их градаций (У = 30). Потеря информативно- и в результате минимизации по всем признакам и их градациям 'оставила в среднем 0,1126 бит на признак, а экономия памяти при м оказалась шестикратной. Признаки в таблице расположены в порядке убывания значений их информативностей до н после минимизации.
,й 3.9, ИНФОРМАТИВНОСТЬ СТАТИСТИЧЕСКИ СВЯЗАННЫХ ПРИЗНАКОВ ПРИ РАСПОЗНАВАНИИ ОБЪЕКТОВ Оценить информативность группы статистически связанных приз;иаков, использовав шенноновскую меру, затруднительно из-за сложности нахождения многомерных распределений вероятностей признаков. Между тем сравнительно легко определить индивидуальные информативности признаков уд (А = 1,2, ..., и).
Информационное содерание группы и признаков 7 равно сумме информативностей отдель',ных признаков только в случае их статистической независимости, т.е. л ьг = .л'.( (д д=! Чтобы обойти сложности оценки многомерных распределений веро' ятностей признаков, а вместе с тем учесть статистические связи между , ними, можно использовать следующий полуэвристический прием. '.
Сначала определяются индивидуальные информативности признаков уд. После этого отдельно оцениваются статистические связи между ! всеми парными комбинациями признаков. Затем вычисляется оконча: тельная оценка информативности группы признаков с учетом их индивидуальных информативностей н статистических связей между ни- л д — ! 7 1 ~и~~ 7 ! ~~~ а в!яп 1 — идр т (3.51) УЗ ~ (1, если [ 1~0: Таблица 3.2 Прнзнвк «), Информзтнвность (! Признак «), информативность (! номер в мининвльном м врыруто помор в минимзльном мзршруто порядко- вые номер нзчвльнзя (прн ао) конечная (прн .(=а) лоряако- выа яомср нзчвльлвя (прл л -зе) конвчнзя (прн .(=а) 9 10 11 12 13 !4 15 2 4 14 8 11 15 3 1, 0380 1,0829 1,0704 1,0!22 1,0129 0,9628 0,8283 0,9939 0,9762 0,9488 0,9056 0,9055 0,8799 0,7226 105 12 5 9 13 1О 1 6 7 1,2105 1,2545 1,1804 1,1749 1,1652 1,1640 1,!122 1,0629 1,1150 1,0750 1,0691 1,0599 1,0467 1,043! 1,0085 1,0029 7д и уз — индивидуальные информативности соответственно А-го и ":- ()-го признаков о; (7 з) „— максимально возможная информатив:: ность ()-го признака; ад 6 — коэффициент, характеризующий статисти, ческую связь между и-м и ()-м признаками.
Важное достоинство этого критерия оценки информативности при:.. знаков — возможность его связи с вероятностью правильного распознавания. Это позволяет не только сравнивать признаки между собой, ',' ио и формировать минимальные описания классов обьектов, потенци' :, ально обеспечивающие заданную вероятность их классификации (рис. ,3.17 и 3.18). На рис. 3.17 представлен график зависимости информа.тивности пРизнака хд от абсолютных значений Разности Условных веРо,, ятностей его наличия в двух классах !(р (хд(А!)) — (р (хд(Аз)1! и раз- в 11ризнаки могут иметь набор своих частных значений (градаций). ности вероятностей наличия самих классов!р (А,) — р (Аз) [.
Информативность й-го признака для разделения классов А, и А, 1(д>ь >=1!"г> — [р(А„)р (хд/А!)+Р(Аз) р(хд/АзЦ1оя[р(А,)р(хд/Аз)+ +р(А,) р(хд/АвЦ вЂ” (р(А1) [! — Р(хд!А!)1+р(Аз)11 — р(хд/Аз) 1)х Х 1оа(р(Ат) [1 — Р(хд(А!)1+Р(Ав) [1 — Р(хд(АзЦ)+ + р (А!) (р (хд/А!) 1оц р (хд/А<) +[1 — р (хд(А,Ц 1ок [1 — р (хд/А!)Ц+ +р (Аз) (р (хд/Ах)+ [1 — р (хд/А Ц !оя [! — р (хд/АзЦ). (3.52) На рис.
3.17 сплошные линии соответствуют условию р (хд/А,) + + р (хд/А,) = 1 и представляют собой нижние границы изменения информативности признака (наихудший случай) при различных абсо- лютных значениях разности 07 [р (А,) — р (А,) [. Верхняя пунДу ктирная линия является верх- ней границей изменений ин- ((1 -- ( ~~ [р/х ул,( р/у щ формативности признака для дд .. л) х случая р (Ат) = р (Аз) = О,б й( .8, .-- и получается при фиксироР1 (, ванном значении ! р (хд/Аз) = 1 Р,б и (изменении р (хд/А,) от ! до О. йб Такие же верхние границы бу- (.() дут и для других значений ~~/А!(-Р(Аг([ [р (А,) — р (А,) [. Рис.
3.!7. Графики зависимостей (а П р и и е ч а н и е. В дальней- =Р<[[Р(ха/Аг) — р(ха/АзЦ при [р(А,) — шем будем рассматривать только — р(Аз) [=сопз! и рпр/ Рз [[р(х„(А,) — нижнюю границу (наихудший слу— Р(ха/Аз)[1 при р(А,) — р(Аз)[=сола<; чай) изменения информативности 11,.
! — б — кривые, настроенные прн Р<х(,<лп+ +и<ха(дз)=! ° Р(х)(Л,) ! н измевеннв Из рисунков видно, что заРд( д(л.> о да о,з с ° ам од висимости /д = Р, [[Р (хд/А,)— — р(хд/Аз)11, р,р — — РДр(хд/А!)— — р (хд/Аа) [), а следовательно, и зависимость р,р = Рз (/д) при [р (А,) — р (Аз) [,= сопз1 (построение графиков будет пояснено в 5 3.11) не являются однозначными, т.
е. характеризуются !не кривыми, а областями значений. При постоянном значении информативности 1д значение вероятности р р зависит от соотношения величин р (хд/А,) и р (хд/Аа). При выборе системы признаков интерес представляет нижняя грайица области изменения р,р Р,(1д), которая получается фиксированием величины р (хд (А,) = ! и изменением величины р (хд/А,) от О до 1. Статистические связи между признаками в (3.51) учитываются во всех их парных комбинациях, т. е. только в первом приближении. Связи более высоких порядков не учитываются из-за сложности их определения и несущественности для практических расчетов.
Для оценки статистических связей между признаками, характеризуемых коэффициентом ада, можно было бы воспользоваться коэффициентом корреляции или корреляционным отношением, так как в общем случае полагают, что связь между парами признаков нелиней- 106 ,ная, однако более удобно р использовать критерии со- „ 1 ;ответствия, основанные на . вычислении степени рас- Ра ХОЖДЕНИЯ ЗаМЕРЕННЫХ Ча- ау у /стог совместного появле- Цб ~Т [, ния дискретных значений ; б ! ~ (~ признаков с распределе: пнем выравнивающих ча- д( ' Стст, СООтВЕтСтВувщИМ уС- д( ! ' >! [Рг!х/Л,)-Р/Хл(Аг)1 - ловию независимости приз- аб а /л ' иаков. абу( Сначала полагаем, что ° признаки статистически не„зависимы. Гипотетическое : распределение выравнивающих частот, соответствующее этому условию, необходимо подвергнуть статистической проверке.
Такая проверка на равномерность обычно осуществляется по известным критериям соответствия. П р и и е ч а н и е. В дальнейшем будем пользоваться критерием Пирсона, илн Хз. Таблица 3.3 <) ()( д( ду дгг Р,у р,б д7 1, Рис. 3.18. Графики зависимостей р Р=рз(1а) при [р(А<) — р(А,) 1 = сопл<: 1 — б — вспанагатзланые кривые, настроенные прв Р(Л )+Р(Л,)=1; (1 — Р(ЛИ=<, Р(Л,)=е; г — Р(Л,)-ОЛ, Р(Л,>-О,<; З вЂ” Р<Л,>-О,З, Р<Л,>-егг З вЂ” р(Л,>=п,т, Р<Л,)-О,З; б — Р(ЛД Об, Р(дг) 04; б — Р<Л,)=Р<лз) ' '-ол> Граданнн признака ха Градапнн прнзнзкз х, хзг ! х„ [дг ! з11 ((г!1 [(У)о) 1(((! з1 дгзз~ ((г! (хто) [дга 1 Гчз< [д(а 1 а) зз [(<гвг ) г)(то (<(з (хзч) х, [дгз 1 (<(ет ! [л рг) Р(рз [а(з 1 д(рз [дга 1 Р(рч 1(р(х ) Хзи ((<з(хзр) ! Л,(х,р) <уо(л зр) П р н м с ч а н в с.
дгз(х ) — нтагавыс частоты саатвстствующнх строк днскрстных значенва зч градапва первого признака (Мз(х ) =- ~ Мет прн с=сапа<); дгт (г,р) — ктагсвые частоты 4 з зч т=! Р соответствующих сталблав дискретных зваченна второго признака (Л'т (хз ) ~ Мзт прн в=! вающнс частоты. ( 107 Р в у сапа<! и' Ха Мз(хгт)=- ) Му(х)з) — сумма всех зачгзрсннзгх частот сазчсстнага л е=! у=) панвленн» дискретных значенна прнзнакав. [ызт]=[мг (х )1[у(т (х РЦ (уг — выравнв- Таблица 3.4 Условные вероятности р (ха/Ад! признаков х! Классы Л! р (х,/Ад) р (хи/Ад) Ад р (хд/Ад) р (хи/А,) р (кв/А,) Ав р (хд/Ав) (3.
53) р (хп/Апз) р (хв/Аиз) р (хд/Апз) Таблица 3.5 Признаки ка к, р (хди/А!) р (хдв/А!) где (Х',р)„,„= [Р, р (хвл/А!) р (хм/Ай р (х„д/А!) р (хпв/ 4 () 169 Предположим, что необходимо определить количественно статистическую связь между признаками х, и х„могущими иметь в общем случае ряд градаций (частных значений), т. е. х(;! и х(т! (е 1, 2, р; Т =* 1, 2,..., ()). Вначале составим таблицу (табл. 3.3) распределений замеренных частот А/,т совместного поЯвлениЯ е-го значениЯ х,-го пРизнака и Т-го значения х,-го признака, Сформируем взвешенные суммы квадратов отклонений величин Агат от их гипотетических частот [А/еот]: р Тв ~ч;' ~ (М [Ага )в)з/[д(е ) е дт=! Эта двойная сумма распределена приблизительно как Хавр с числом степеней свободы $ = (р — 1) (() — 1), Поэтому будем считать, что Х15 = Тв.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
