2010 Лекции МОТП. Записки (1185265), страница 5
Текст из файла (страница 5)
Создание методов поискаДля создания эффективных методов их поиска рассмотрим "болееслабый" вариант, основанный на следующих двух ограничениях.1. Множество логических закономерностей "базируется" на эталонах. Нагеометрическом языке, в центре каждого искомого гиперпараллелипипеданаходится один из эталонов класса.2. Вместо стандартного функционала качества предикатов рассматриваетсянекоторый линейный по признакам эвристический функционал.Пусть фиксирован произвольный эталон St ∈ Kλ .Будем искать предикаты видаPt Ω,ε ( x) = & Ptj (ε j , x j ) ,Ω ⊆ {1,2,..., n} ,гдеj∈Ω1, atj − ε j ≤ x j ≤ atj + ε j ,Ptj (ε j , x j ) = иначе.0,(2)Отметим, что Pt(St)=1, т.е.
первое условие определения логическихзакономерностей класса Kλ выполнено. Объект St будем называть опорнымдля предикатов (2).В качестве критерия оптимальности предиката возьмем функционалf ( Pt Ω ,ε ) = ∑ ϕtj (ε j ) ,j∈ωϕ tj (ε j ) =1Kλ∑ρSi ∈K λj(ε j , S t , S i ) +1CK λ∑ (1 − ρSi ∈CK λj(ε j , S t , S i )) (3)0,где антиблизость ρ j (ε j , St , Si ) = ρ j (ε j , x j ( S t ), x j ( S i )) = 1,ЗдесьK λ , CK λозначаютчислоatj − aij ≤ ε j ,иначе.эталонныхобъектовпринадлежащих и не принадлежащих отмеченному классу соответственно.Лекция № 7Вычислим значенияразличные их значенияпоследовательностейa tj − a ijпоrj : rj1 , rj 2 ,..., rju j , rjv < rjwОчевидно, r j 0 = 0., i=1,2,…,m, и упорядочим всевозрастаниюпри v<w.ввидеследующих(4)28rju , u = v, v + 1,...v + w,1.
Подпоследовательностьназовемподпоследовательностью первого типа последовательности (4), еслиа) для любого ее элементаrju , v ≤ u ≤ v + w, не существует строкSi ∈ CKλ: atj − aij = rju ,б) любое возможное расширение подпоследовательности дополнениемэлементов слева или справа нарушает свойство a).rju , u = v, v + 1,...v + w,2. Подпоследовательностьназовемподпоследовательностью второго типа последовательности (4), еслиа) для любого ее элементаrju , v ≤ u ≤ v + w, не существует строкSi ∈ Kλ:, atj − aij = rju ,б) любое возможное расширение подпоследовательности дополнениемэлементов слева или справа нарушает свойство a).Докажем, что областьпараметровтаким, чтоD={εj≥ 0, j=1,2,…n}допустимых значенийε можно ограничить некоторым конечным множеством D*⊆Dmin f ( Pt Ω ,ε ) = min f ( Pt Ω ,ε ) .ε ∈D(5)ε ∈D*Очевидно, что условие (5) будет выполнено, если в качествеD* взятьмножество D'={ε=(ε1,ε2,…,εn): εi∈ ri , i=1,2,…n}.Покажем, что множество D' может быть далее существенно сокращенос помощью трех алгоритмов сокращения последовательностей (4) (или ихподпоследовательностей, которые будем обозначать так же).1.
Первый алгоритм сокращения.В последовательноститипаrjвыделяется подпоследовательность первогоrju , u = v, v + 1,..., v + w.Изданной подпоследовательности кромеповторяетсядлявсехjпоследовательностей r .rjвычеркиваются все элементыr ju , u = v + w.подпоследовательностейДанная процедурапервоготипа2. Второй алгоритм сокращения.В последовательности rj выделяется подпоследовательность второготипа r ju , u = v, v + 1,..., v + w.
Из rj вычеркиваются все элементы даннойподпоследовательности. Данная процедура повторяется для всехподпоследовательностей второго типа последовательностей rj.293. Пусть дана произвольная числовая последовательность…,ckС: c1 ,c2 ,ψ(x)≥ 0. Последовательностипоследовательность ψ (c1), ψ (c2),…, ψ (ck),и функция действительного аргументаС соответствует числоваякоторую будем называть функциональной.Третий алгоритм сокращения произвольной конечной числовойпоследовательности С состоит в выделении такой ее подпоследовательностиci1 , ci2 ,..., cih ,(6)которойсоответствуетспециальнаястрогоподпоследовательность функциональной последовательностиубывающаяψ (c1), ψ (c2),…, ψ (ck).Третий алгоритм сокращения.1.Полагаем v=w=1,w≥ 1. Пусть из c1 ,c2 ,…,cwci1 , ci2 ,..., civ , v ≤ w .ЕслиШаг2.i1=1.подпоследовательностьвыделенаw=kподпоследовательность (6) считается построенной и переход на этап 3.В противном случае w увеличивается на единицу.Еслиψ (civ ) > ψ (cw ) ,тогда v увеличивается на единицу, iv=w иосуществляется переход на начало этапа 2.3.Конец алгоритма.Pt Ω,ε ( x)Пусть- произвольный допустимый предикат такой, чтоjεj∈ rj , ε j ∈ {rju , u = v, v + 1,..., v + w} ⊆ r , где rj - последовательность(4)илиееподпоследовательность,аrju , u = v, v + 1,..., v + w-подпоследовательность первого типа последовательности rj.Рассмотрим предикатPtΩ ,eЯсно, что если предикатдопустимым также и предикатi ≠ j, εi ,r j , v + w , i = j.( x) , для которого ei = Pt Ω ,ε ( x)- допустимый, то будетPt Ω ,e ( x) .30Из условийρ j (e j , S t , S i ) ≤ ρ j (ε j , S t , S i )ρ j (e j , S t , S i ) = ρ j (ε j , S t , S i )длядляSi ∈ KλSi ∉ Kλиследует, чтоf ( Pt Ω,e ) ≤ f ( Pt Ω,ε ) .Рассмотрим теперь случай, когдаrju , u = v, v + 1,..., v + w-подпоследовательность второго типа последовательности rj.Ω ,eРассмотрим предикатPtТогда, если предикатPt Ω ,ε ( x)также и предикатвыполненоPt Ω ,e ( x)( x) , для которого ε i , i ≠ j,ei = r j ,v −1 , i = j.- допустимый, то будет допустимымв силу неравенстваеj<εj.
Кроме тогоf ( Pt Ω ,e ) ≤ f ( Pt Ω ,ε ) .Таким образом, после последовательного применения первого ивторого алгоритмов сокращения к последовательностям rj , j=1,2,…n,вычисляется такое подмножество D'' множества D' , минимум на которомосновного функционала совпадает с минимумом на D'. Обозначимсокращенные последовательности снова как rj , D''=r1 × r2 × … × rn .Применим к последовательностям rj , j=1,2,…n, третий алгоритмсокращения, рассматривая в качестве соответствующих функциональныхпоследовательностей последовательностиϕ tj (rji ), i = 1,2,..., u j .В итоге получим множество D*=ε1× ε2 × … × εn,где εj={εji ,i=1,2,…,kj },εju <εjv ,при u<v.ВсилусвойствтретьегоалгоритмасокращениядлялюбогоPt Ω ,ε ( x) , εj∈ rj, существует e=(e1 ,e2 ,…,en),ej=εjv(j)≤ εj , для которого ϕ tj (e j ) ≤ ϕ tj (ε j ) , т.е. ∃ допустимый предикатPt Ω ,e ( x) , для которого f ( Pt Ω ,e ) ≤ f ( Pt Ω ,ε ) .допустимого предикатаПосле явного описания процедуры нахождения множества D*покажем, что задача поиска логических закономерностей может бытьсформулирована в виде специальной задачи целочисленного линейногопрограммирования.Введем следующие обозначения:31cij = ϕti (ε ij ),y = ( y11 , y12 ,..., y1k1 , y21 , y22 ,..., y2 k2 ..., yn1 , yn 2 ,..., ynkn ),yij ∈ {0,1}, i = 1,2,..., n, j = 1,2,..., ki ,biju = ρi (ε ij , xi ( St ), xi ( Su )) ,nki∑ ∑ci =1nijj =1ki∑ ∑bi =1j =1uijyij → min ,yij ≥ 1, u = 1,2,..., m,(7)Su ∉ K λ .(8)По определению коэффициентов и в силу свойств третьего алгоритмасокращения для задачи (7-8) имеют место следующие свойствакоэффициентов:ciu > civ ≥ 0,приu < v, biju ≥ bijv ≥ 0, biju ∈ {0,1}.(9)В силу свойств коэффициентов (9) задачу (7-8) будем называть задачейцелочисленного линейного программирования с блочно-монотоннымистолбцами (задача БМС-ЦЛП).Пример задачи (7-8).i=10.5 0.411101111101011..11В силуi=i=2n0.
0. 0.8 0. 0. … 0.9 0. 0. 0. 0. cij3163864210111… 1111000111… 1111100100… 00000u00110… 10000 bij00000… 0000000100… 1110011000… 00000.....… .....10110… 11000свойств коэффициентов функции (7) оптимальное решениеy* = ( y *11 , y *12 ,... y *1k1 , y *21 , y *22 ,... y *2 k2 ,..., y *n1 , y *n 2 ,... y *nkn )содержит не более одной единичной компоненты для каждой из n групппараметровy *i1 , y *i 2 ,... y *iki .32Примечание.
В случаеciki > 0это проверяется просто. Приciki = 0,по построению, ki =1 и данное свойство также выполняется.Множество единичных компонент однозначно определяет предикатΩ ,εPt ( x ) . Действительно, множество Ω признаков предиката определяетсяy*ij , асоответствующие значения ε-порогов задаются вторыми индексами (εi =εij).первымииндексамиединичныхзначенийкомпонентНайденные предикаты естественно называть оптимальными окрестностямипредставительных наборов, поскольку алгоритм находит фрагментыэталонных описаний и их окрестности.Лекция № 83. Распознавание на основе логических закономерностей.Пусть имеется некоторый алгоритм поиска локально-оптимальныхрешений задачи (7-8). Найденному множеству локально-оптимальныхрешений задачи (7-8) соответствует некоторое множество логическихзакономерностей{ Pt Ω,ε ( x) },связанных с объектом Stфункционалом f. Обозначим через P j =PttΩ ,εкласса Kj и( x) множество логическихKj как объединение множеств предикатов { Pt Ω,ε ( x)}, найденных для всех эталонов класса Kj.закономерностей классаОбщая схема, которая используется в алгоритмах распознавания,основанных на голосовании по системам логических закономерностей,включает три последовательных этапа и является частным случаем общейпоследовательности выполнения этапов в моделях вычисления оценок.1.
Для каждого класса Kj по обучающей информации I0 согласноописанномуранееалгоритмунаходитсямножествологическихзакономерностейPj ,из которого вычеркиваются предикаты с малымизначениями стандартного функционала качества.2. Для произвольного распознаваемого объектаSвычисляется "мераΩ ,εGj=∑βt Pt ( S ) объекта S к классу Kj, где суммированиеΩ ,εпроводится по всем Pt ( x) ∈ Pj . Здесь Gj является "взвешенной суммойблизости"голосов" за класс Kj , или, следуя терминологии [2], оценкой S за классНормировочные коэффициенты βi могут вычислятьсяспособами и задают тип процедуры голосования.Kj .различными33Gj3.
По значениямвычисляется информационный векторαA2(S), …, αAl(S)).Например, αAr(I(S))=1противном случае αAr(I(S))=0., если(αA1(S),Gr=max{Gj, j=1,2,...,l}.ВСтрока αA(S) = (αA1(S), αA2(S),..., αAl(S)),содержащая ровно одну единицу, означает однозначное решение задачираспознавания - отнесение алгоритмом распознавания A объекта S в один изклассов. Строка αA(S), содержащая несколько единиц, означаетмногозначное решение задачи распознавание. В данной ситуации алгоритмраспознавания указывает несколько классов, которым может принадлежатьlобъект S.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
