_учебник_ Журавлёв Ю.И. Математические основы теории пронозирования (2008) (1185334), страница 3
Текст из файла (страница 3)
. . ∨ yk ∨ y k+1 ∨ . . . ∨ y l ∨ yl+1 ∨ . . . ∨ yn ) ·· (y1 ∨ . . . ∨ yk ∨ y k+1 ∨ . . . ∨ y l ∨ y l+1 ∨ . . . ∨ y n ) == y1 ∨ . . . ∨ yk ∨ y k+1 ∨ . . . ∨ y l ∨ yl+1 · y l+2 ∨ . . . ∨ yn+1 · y n ∨ yn · y l+1 )Таким образом, д.н.ф., реализующую функцию с двумя нулями можно построить, использовав только n конъюнкций. Оказывается, что, обобщив приведенные выше построения,можно легко получить д.н.ф. относительно невысокой сложности, если число нулей функции невелико.Пусть таблица нулей булевой функции имеет вид(α11 .
. .α1i . . . α1n ) = α̃1(α21 . . .α2i . . . α2n ) = α̃2...(αk1 . . .αki . . . αkn ) = α̃kФормулы, реализующая функцию, нуля которой суть наборы α̃1 , α̃2 , · · · α̃k имеет видkY(x1αi1 ∨ xα2 i2 ∨ . . . ∨ xαnin )i=111(2.1)Приведем произведение (2.1) к д.н.ф. Сразу исключим из таблицы нулевой и единичный столбцы, так соответствующие им переменные в (2.1) можно сразу вынести за скобкии написать xu1 ∨. . .∨xup ∨xt1 ∨. .
.∨xtv , соответственно,для нулевых и единичных столбцов.iσВыполним преобразование xi → xj ij , σij ∈ {0, 1},— подстановка, таким образом,jчтобы строка α̃1 перешла в строку (0 0 . . . 0 . . . 0 0) = 0̃, одинаковые столбцы таблицыkαij kk×n получили последовательные номера, объединившись в блоки, число которых неможет превосходить 2k−1 − 1 (столбцы образует k − 1 строка и нет нулевого столбца).Пример 2 Исходная таблица T1 :x1011x2101x3011x4101x5011x6101Проведем сначала преобразование x1 → x1 ,x6 , x7 → x7 , x8 → x8 , x9 → x9 , x10 → x10 ,подстановкой1 3 5 8 10 21 2 3 4 5 6x7010x8100x9010x10100x 2 → x2 , x 3 → x3 , x 4 → x4 , x 5 → x5 , x 6 →а затем номера переменных преобразуем4 6 7 97 8 9 10Получим таблицу:y1011y2011y3011y4011y5011y6010y7010y8010y9010y10010Если рассматривать блок отдельно, то имеем функцию, принимающую значения 0 нанулевом и единичном наборах.
Напишем формулу:ϕ = y1 y 2 ∨ y2 y 3 ∨ y3 y 4 ∨ y4 y 5 ∨ y5 y 1 ∨ y6 y 7 ∨ y7 y 8 ∨ y8 y 9 ∨ y9 y 10 ∨ y10 y 6Функция ϕ равно 0 на всех трех строках таблицы, но также имеются и "лишние"нули,например:0 0 0 0 0 1 1 1 1 1ϕ = 0 на любом наборе, имеющем одинаковые первые 5 и вторые 5 координат. Чтобыотбросить лишние нули, построим функцию ψ: она зависит от первых переменных каждогоиз блоков (в нашем случае от y1 и y6 ).
Образуем таблицу нулей функции ψ из столбцовзначений этих переменных. На остальных наборах ψ = 1 (в нашем случае это набор (0 1).Реализуем ψ с помощью д.н.ф.: ψ = y 1 · y6 .y10110y61101ψ0001Формула ϕ ∨ ψ реализует функцию, нули которой заданы таблицей T1 : ϕ равна 0 налюбых наборах, которые в каждом из блоков имеют одинаковые значения координат, ψ"отбрасывает"лишние нули, оставляя те, которые реально задаются таблицей.12Теперь достаточно выполнить обратное преобразование, и мы получим формулу дляфункции, нули которой заданы таблицей T1 .
Заметим, что для функции от 10 переменныхмы получили д.н.ф. из 10 + 1 конъюнкции.В "наихудшем случае"в преобразованной таблице получится 23−1 − 1 = 3 блока, ифункция ψ примет вид:y1001y i1010y i2011ψ100На остальных наборах ψ = 1. Легко написать д.н.ф. для ψ:ψ = y 1 y i1 yi2 ∨ y1 y i2 ∨ y i2 yi1 ∨ y1 y i2Таким образом для функций с тремя нулями д.н.ф. для ψ не может состоять более, чемиз 4 элементарных конъюнкций.В общем случае, для функций с k нулевыми наборами α̃1 , .
. . , α̃k процесс построенияд.н.ф. полностью повторяет действия примера.Находим преобразование, которое приводит таблицу нулей к виду: 1) первая строкастановится нулевой, 2) таблица состоит из блоков одинаковых столбцов (различные блокисостоят из разных столбцов). В каждом блоке присутствуют только строки 0̃ = (0 . . . 0)и 1̃ = (1 . . . 1). Пусть таблица разбита на блоки B1 , B2 , .
. . , Bi , . . . , Bq , q ≤ 2k−1 − 1. Пустьблок Bi состоит из столбцов значений переменныхxti , xti +1 , . . . , xti +viЗапишем формулу X (Bi ) = xti · xti +1 ∨ xti +1 · xti +2 ∨ . . . ∨ xti +vi −1 · xti +vi ∨ xti +vi · xti . Д.н.ф.qWD=X (Bi ) реализует функцию, равную 0 на (и только на) наборах, таких, что значенияi=1координат в каждом блоке одинаковы.Для исключения "лишних"нулей образуем (как в примере) функцию, зависящую отпеременных, взятых по одному из каждого блока (например, от первых переменных блока). Соответствующие столбцы образуют множество нулей функции ψ (столбцы значенийвыбранных переменных).
Остальные наборы образуют множество единиц функции ψ, чтоисключает "лишние"нули и позволяет написать для функции с нулями α̃1 , . . . , α̃k формулуq_X (Bi ) ∨ ψi=1Написав д.н.ф. для ψ (ψ зависит не более, чем от 2k−1 − 1 переменной), получим искомуюд.н.ф. Применив к ней преобразованияxi K ∨ xi K0 → xi K ∨ xi K0 ∨ KK0 , K ∨ KK0 → Kпостроим сокращенную д.н.ф. с нулями α̃1 , . . . , α̃k .Замечание. Умножение "тестовых"уравнений приводит к д.н.ф., в которой нет переменных с отрицаниями .
Поэтому сокращенная д.н.ф. (совокупность всех простых импликант) получается применением только преобразованияK ∨ KK0 ⇒ KНо K · K0 не может соответствовать тупиковой тест, так как тест, соответствующих K,получается из него удалением некоторых столбцов. Заметим также, что полученная д.н.ф.является единственной тупиковой (для доказательства применить критерий поглощенияи заметить, что д.н.ф., не содержащая отрицаний переменных, не может быть равной 1на всех наборах значений переменных).13Применение к построению алгоритмов распознавания.
Пусть в исходной бинарной таблице наборы α̃i = (αi1 , . . . , αin ), i = 1 . . . k принадлежат K1 , наборы β̃ j = (βj1 , . . . , βjn ),j = 1 . . . l принадлежат K2 , K1 ∩ K2 = . Построим семейство логических алгоритмов распознавания. Введем две не всюду определенные булевские функции:(1 на наборах α̃i , i = 1 . . .
kF1 (x1 , . . . , xn ) =0 на наборах β̃ j , j = 1 . . . l(1 на наборах β̃ j , j = 1 . . . lF2 (x1 , . . . , xn ) =0 на наборах α̃i , i = 1 . . . kС помощью описанной выше процедуры по нулям F1 и F2 построим д.н.ф. для функций, равных 0 только на этих наборах, и с помощью преобразований Блейка построимсокращенные д.н.ф этих функций (на практике число добавлеяемых конъюнкций ограничивается). Из сокращенной д.н.ф. удалим все конъюнкции, интервалы которых имеютпустое пересечение с множеством единиц соответствующей функции.Пусть после этих процедур для F1 остались интервалы NK1 , .
. . , NKr , имеющие непустое пересечение с M1 = {α̃1 . . . α̃k }, и для F2 — NK10 , . . . , NKr0 с непустым пересечением сM2 = {β̃ 1 , . . . , β̃ l }. Схематически это можно изобразить так:Здесь α̃ = (α1 , . . . , αn ) — распознаваемый объект. Построим совокупность тупиковыхд.н.ф D11 , .
. . , D1p для F1 и D21 , . . . , D2q — для F2 . При этом можно пользоваться критериемпоглощения. Но можно проверить условия[M1 ∩ NKi ⊆NKj ∩ M1j6=iM2 ∩ NK0 i ⊆[NK0 j ∩ M2j6=iи удалить интервалы, пересечение которых с M1 (M2 ) покрывается остающимися интервалами. Для такой проверки существуют более сложный критерий поглощения (см. Ю. И.14Журавлев, "Об отделимости подмножеств вершин единичного n-мерного куба [1]). Пустьпостроены тупиковые д.н.ф.
T11 , . . . , T1K1 для F1 и T21 , . . . , T2K2 для F2 .Пусть число выполненных равенств T1i (α̃) = 1, i = 1 . . . K1 равно Q1 , а выполненныхравенств T2i (α̃) = 1, i = 1, . . . K2 равно Q2 .Простейшее решающее правило:Q1 > Q2 → α̃ ∈ K1 ,Q1 < Q2 → α̃ ∈ K2при Q1 = Q2 алгоритм отказывается от распознавания.Возможно усложнение введением порога сQ1 − c > Q2 → α̃ ∈ K1 ,Q2 − c > Q1 → α̃ ∈ K2в остальных случаях алгоритм отказывается от распознавания.На базе описанного выше алгоритма может быть построено параметрическое семейство— тупиковым д.н.ф.
приписаны веса w, и суммируется не число вхождений α̃, а суммавесов тупиковых д.н.ф., интервалы которых содержат точку α̃.Возможна оптимизация весов по текущему контролю или независимому контрольномуматериалу (см. подбор значений параметров алгоритмов вычисления оценок).15Лекция 33.1Алгоритмы вычисления оценокВ эвристическом алгоритме “Тест” было проведено сравнение объектов из таблицыобучения и распознаваемого объекта по подмножествам признаков, образующих тупиковые тесты. Очевидно, такие сравнения могут выполняться и по другим подмножествам,например, выбираемым экспертами.
При формировании величин Γ(S, K1 ), Γ(S, K2 ) добавлялась 1 при выявлении любого совпадения. Однако в реальности признаки и объекты изтаблицы обучения не равноценны, и при формировании Γ(S, Ki ) следует учитывать — скакими объектами по каким признакам произошло совпадение. Это можно делать, задавая различные веса признакам и объектам из таблицы обучения — эталонным объектам.При самом определении близости, если признаки не бинарные, можно также использовать различные возможности, определенные, например, параметрами 1 , . . . , n . Наконец,“поощрения” при формировании Γ(S, Ki ) возможны также за отсутствие близости к объектам другого класса, а штраф — за наличие близости к объектам класса, для которогоне формируется оценка и отсутствие близости к объектам, для которых оценка формируется.
Указанные обстоятельства могут реализовываться многими различными способами.Формальное описание таких способов приводит к формированию класса алгоритмов, получившего название “алгоритмы вычисления оценок”, или “алгоритмы голосования”.Как и ранее, будем рассматривать исходную (или обучающую) информацию, заданнуюв виде двух таблиц:kaij km×n — совокупность m объектов, заданных наборами n признаков,kαij km×l — информационная матрица (таблица), где строка (αi1 . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
