_учебник_ Журавлёв Ю.И. Математические основы теории пронозирования (2008) (1185334), страница 5
Текст из файла (страница 5)
Пусть система {Ω}A состоит из всех k-элементных подмножеств множества {1, 2, . . . , n}.Функция близости определяется только параметрами 1 , 2 , . . . , n . Пусть такжеSi = (ai1 , . . . , aik , . . . , ain ), S = (a1 , . . . , ak , . . . , an ). Выпишем неравенстваρ1 (a1 , ai1 ) ≤ 1···ρk (ak , aik ) ≤ k···ρn (an , ain ) ≤ nСовокупность номеров признаков, для которых выполнены или, соответственно, невыполнены неравенства, обозначим через M + , M − , а мощности соответствующихмножеств через |M + |, |M − |.+Легко видеть, что R(N = 1, t) равно |Mk−1|−1 для t ∈ M + , и равно 0 для t ∈ M − . Таккак число подмножеств, содержаших t в {Ω}A , равно n−1, тоk−1(R(N = 0, t) =Из последнего видно, чтоnPn−1−k−1 n−1,k−1|M + |−1k−1wt · R(N = 1, t),t=1, для t ∈ M +для t ∈ M − .nPwt · R(N = 0, t) в рассматривае-t=1мом случае заменится более “простыми” суммами, так как величины R(N = 1, t),R(N = 0, t) для каждой строки Si принимают только два различных значения.
Так,! nXX|M + | − 1wt · R(N = 1, t) =Pt ·.k−1+t=1t∈MАналогично упрощаются и другие введенные ранее формулы.2. Рассмотрим ту же, что и в 1, систему опорных множеств и функцию близости с параметрами 1 , . . . , n , ν, ν < [ k2 ]−1. Аналогично предыдущему пункту, при сравнениистрок S и Si образуем подмножества признаков-координат M + и M − .Пусть t ∈ M + .
Тогда функция близости равна 1, если она содержит 0, 1, 2, . . . ,min(ν, |M − |) признаков из M − и, соответственно, k − 1, k − 2, . . . , k − min(ν, |M − |) −− 1 признаков из M + (для упрощения выкладок мы рассматриваем только случайk ≥ min(ν, |M − |) + 1). Тогда число опорных подмножеств, содержащих t и таких, чтоN (ω̃S, ω̃Si ) = 1, очевидно, равно + − + − + −|M | − 1|M ||M | − 1|M ||M | − r|M |·+·+ ... +·+ ...+k−10k−21k−1−rr + −|M | − 1|M |+·.k−1−ννВсе t из M + имеют одинаковый только что выписанный коэффициент при Pt . Остальные случаи вычисляются так же просто.213.
В качестве опорных рассматриваются все непустые подмножества множества {1, 2, . . . , n}.Тогда( +2|M |−1 , для t ∈ M +R(N = 1, t) =0,для t ∈ M − .( +−2|M |−1 · (2|M | − 1), для t ∈ M +R(N = 0, t) =2n−1 ,для t ∈ M − .Подставляя полученные значения в (3.2), получаемwix11 ·Xwt|M + |−1·2+ x10t∈M +Xwt · (2|M+ |−1) · (2|M−|− 1)+t∈M +!!X n−1+wt · 2t∈M −Аналогичный вид принимает после соответствующих подстановок формула (3.3).4. Совокупность характеристических векторов опорных множеств образует интервал вE n , т.е. удовлетворяет условию: K = 1, K — элементарная конъюнкция. Не ограничивая общности, можно полагатьK = x1 · . .
. · xr · xr+1 · . . . · xr+k .Тогда в систему опорных множеств не войдут признаки 1, . . . , r; в каждое из опорныхмножеств войдут признаки r + 1, . . . , r + k, и к ним последовательно присоединятсявсе подмножества (включая пустое, если K =6 0) или все непустые подмножествамножества r + k + 1, . . . , n, если K = 0. Будем рассматривать K 6= 0 и рассмотримфункцию близости с параметрами 1 , . . . , n .Если не выполнено включение {r + 1, .
. . , r + k} ⊆ M + , то R(N = 1, t) = 0,R(N = 0, t) = 2n−(r+k+1) . Последнее следует из того, что |{Ω}A | = 2n−(r+k) , и хотя бы один из признаков любого опорного подмножества принадлежит M − .Пусть имеет место: {r + 1, . . . , r + k} ⊆ M + . Тогда для t ∈ {r + 1, . . . , r + k}:R(N = 1, t) = 2|M+ |−k|M − |R(N = 0, t) = 2,− 1.Для t ∈ M + \{r + 1, . . . , r + k}:R(N = 1, t) = 2|M+ |−k−1R(N = 0, t) = 2|M+ |−k−1,· (2n−(k+r) − 1).Наконец, для t ∈ M − : R(N = 1, t) = 0, R(N = 0, t) = 2|M− |−1.После соответствующих подстановок, получаем эффективные формулы вычисленияΓj (S), j = 1, . . . , l.Последний случай (4) можно использовать при решении прикладных задач.
Рассмотрим булевскую функцию, равную 1 на элементах {ω̃}A . Если реализовать ееrWдизъюнктивной нормальной формойKi , где Ki — элементарные конъюнкции, иi=122TNKu NKv = ∅, то, написав по 4 формулы для каждой Ki и сложив их, получим формулу для вычисления Γj (S), j = 1, . . . , l. Достаточно и реализации в классе д.н.ф., вкоторых интервалы некоторых пар конъюнкций пересекаются (интервалы конъюнкций из разных пар не пересекаются). Пусть оценка по системе опорныхS множеств, задаваемых конъюнкцией K, есть Γj (K, S).
Пусть, также, {ω̃}A = K1 K2 , K1 · K2 6≡ 0.Тогда, очевидно, Γj (S) = Γj (S, K1 ) + Γj (S, K2 ) − Γj (S, K1 · K2 ).23Лекция 44.1Вычисление характеристик, определяющих алгоритмвычисления оценокКак было показано в лекции 3, алгоритм распознавания определяется заданием системы опорных множеств {Ω}A и числовых параметров 1 , . . .
, n , w1 , . . . , wn , w1 , . . . , wm , x11 ,x00 , x01 , x10 , c1 , c2 .В своей работе алгоритм использует исходную (обучающую) информацию, состоящуюиз таблицы обучения kaij km×n и ее информационной матрицы kαij km×l . Рассматриваетсязадача с l, вообще говоря, пересекающимися классами K1 , .
. . , Kl .Параметры подбираются таким образом, чтобы обеспечить максимальную точностьраспознавания на определенном заранее множестве объектов.I. Текущий контроль. Из исходной матрицы последовательно изымаются строки Si ,i = 1 . . . m, вместе с информационным вектором α̃(Si ), и для строки Si по оставшейсяисходной информации строится квази-информационный вектор β̃(Si ) = (βi1 . . . βil ),i = 1...mВ матрице kαij −̇βij km×l определяется число единиц. Операция αij −̇βij определяетсяследующим образом:HHijαij HβHH0101∆011011Алгоритм A подбирается таким образом, чтобы число единиц (т.е.
сумма ошибок иотказов) была бы минимальной.II. Независимый контроль. формируется контрольное множество S 1 , . . . , S q ,Si = (bi1 . . . bin ), i = 1 . . . q и таблицы информационных векторов kβij kq×l . С использованием алгоритма A и всей исходной информации формируется совокупностьγ̃ = (γi1 .
. . γil ) квази-информационных векторов и минимизируется число единиц вматрице kβij −̇γij kq×l .1) Система опорных множеств определяется (задается) экспертами и последовательно рассматриваются алгоритмы в набором всех k-элементарных√ подмножеств: k = 2, 3, . . . , r. Как правило, достаточно ограничиться r ≤ 3 π.2) Параметры xij определяются перебором вариантов. Как правило, рассматриваются целочисленные значения x11 = 1, 2, 3, 4, 5, 6, 7; x00 ≤ [ 21 x11 ], x01 , x10 принимают отрицательные или нулевые значения.
В большинстве действующих систем полагают: x11 = 1, x00 = x01 = x10 = 0.243) Пусть определения все характеристика за исключением 1 , . . . , n (о них позднее).Рассмотрим задачу с независимым контролем и напишем систему неравенствΓj (S i ) > c2 , ∀βij = 1Γj (S i ) < c1 , ∀βij = 0i = 1, 2, . . . , q, j = 1, . . . , l(4.1)В левой части системы неравенств (4.1) находятся билинейные формыΣwu · wv . Полагаем w1 = . .
. = wn = 1. Получаем систему линейных относительно w1 . . . wq неравенств. Находим максимальную совместную подсистему иее решение w11 , . . . , w1q . Подставляем эти значения в левую часть (4.1) и получаемлинейную относительно w1 , . . .
, wn систему. Находим совместную максимальнуюподсистему и ее решение w11 , . . . , wn1 . Подставляем эти значения левую часть(4.1) и т.д. Процесс заканчивается либо когда удастся получить наборы параметров, удовлетворяющие всем неравенствам (4.1), либо когда после очереднойитерации число неравенств в совместной подсистеме уменьшится.4) Для определения 1 , . . . , n существует большое число эвристических методов.Приведем один из них (может быть, не лучший).
Оставим в таблице обученияи контроля только k-е столбцы: b1ka1k a2k b2k .. , .. . . amkblkДля каждой пары (aik bjk ) вычислим kα̃(Si ) + β̃(S k )mod2 k, то есть число различных координат в этом векторе.Если l − kα̃(Si ) + β̃(S k )k > kα̃(Si ) + β̃(S k )k, то формируем неравенство|aik − bjk | < kПри изменении знака:|aik − bjk | > k .При l − kα̃(Si ) + β̃(S k )k = kα̃(Si ) + β̃(S k )k выписываем одно из неравенств|aik − bjk | ≤ k ,|aik − bjk | ≥ k .Значение k находится из условия: данное значение удовлетворяет наибольшемучислу построенных неравенств.254.2Алгебры над алгоритмамиРанее мы видели, что алгоритм вычисления оценок делится на две части: распознающий оператор B и решающее правило C: A = B · C.
A(I, S) = (Γ1 (S), . . . , Γl (S)) = Γ~l (S),C(Γ~l (S)) = (C(Γ1 (S)), . . . , C(Γl (S)))1, Γj (S) > c2C(Γj (S)) = 0, Γj (S) < c1c1 < c2∆, c1 ≤ Γj (S) ≤ c2Оказывается, что подобное представление имеет место для большого класса алгоритмов.Пусть A — алгоритм, работающий с исходной информацией I ∈ {I}, A ∈ {A}, и каждыйиз A по любой I ∈ {I} должен получить ответ на фиксированные вопросы Q1 , .
. . Ql ,причем число возможных ответов равно трем: 1, 0, ∆. ТогдаТеорема 4 Каждый A может быть представлен в виде A = B·C, B(I) = (a1 . . . aj . . . al )— числовой вектор ~a, C(~a) = (C(a1 ), . . . , C(al )), причем1, ai > c2C(ai ) = 0, ai < c1∆, c1 ≤ ai ≤ c2где c1 и c2 — константы, фиксированные для всех алгоритмов. Заметим, чтоA(I) = (C(a1 ), .
. . , C(al )) = (δ1 . . . δl ) = ~δДоказательство. Введем вспомогательный оператор C −1 (~δ) = (C −1 (β1 ) . . . C −1 (βl )) == (a1 , . . . , al ) = ã. Тогда B = A · C −1 , A = (A · C −1 ) · C. Теорема доказана.Класс алгоритмов {A} порождает класс операторов {B}, которые можно складывать,умножать, умножать на число.Действительно, если B1 (I) = (a11 . . .
ail ), B2 (I) = (a21 . . . a2l ), то (B1 + B2 )(I) = (a11 ++ a21 , . . . , a1l + a2l ), B1 · B2 (I) = (a11 · a21 , . . . , a1l · a2l ), (d · B1 )(I) = (d · a11 , . . . , d · a1l ).Нетрудно видеть, что используя операторы из {B}, A = B · C, можно построить полиномыB̃ = Σci1 ...ik · Bir11 · . . .
· Birkk ,где роль переменных играют операторы; ci1 ...ik — константы.Совокупность {B̃} называют алгебраическим замыканием семейства {B}, а {B̃} · C —алгебраическим замыканием класса алгоритмов {A} — обозначения U{B}, U{A}.Оказывается (Ю. И. Журавлев), что в U{A} при выполнении простых легко проверяемых условий можно построить алгоритм, не делающий ошибок на контрольной совокупности.Алгоритм имеет вид:(d · Σ(ci Bi )ki ) · C.Bi представимы линейными формами от распознающих операторов вычисления оценок.Условия:Пусть I = {kaij km×n kαij km×l }.Контрольный материал: kbuv kq×n , kβij kq×l .261. в матрице kαij km×l нет одинаковых столбцов.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
