Содержание к диссертации
Введение
Глава I. Некоторые оценки степени достоверности гипотез закономерностях 17
1. Модель импликативных закономерностей и логическое распознавание образов, необходимые сведения 17
2. Верхняя оценка и оценка по грешности для оценки 24
3. Нижние оценки и определение максимального допустимого значения ранга имшшкативных закономерностей... 28
Глава II. Модель стохасжеских ймшшкативных закономерностей и распознавание образов 41
4. Стохастические импликативные закономерности и оценки степени достоверности соответствующих гипотез 41
5. Аппроксимация оценок известными вероятностны ми распределениями 45
6. Логико-статистические правила предсказания. 54
Глава III. Модель функциональных закономерностей и логическое распознавание образов ...63
7. Описание модели и необходимые сведения 63
8. Оценки степени достоверности гипотез о функциональных закономерностях 67
9. Некоторые свойства системы частичных булевых функций, представляющих данную схему функцио нальных закономерностей 77
10. Распознавание как логический вывод 84
Литература 95
- Верхняя оценка и оценка по грешности для оценки
- Аппроксимация оценок известными вероятностны ми распределениями
- Оценки степени достоверности гипотез о функциональных закономерностях
- Некоторые свойства системы частичных булевых функций, представляющих данную схему функцио нальных закономерностей
Введение к работе
В настоящей работе предлагаются некоторые методы распознавания образов в булевом пространстве признаков. Они основываются на решении задачи "реконструкции" множества абстрактных объектов, представляемых соответствующими точками булева пространств ва, по его случайной выборке при предположении, что структура упомянутого множества удовлетворяет определенным свойствам или "закономерностям". Рассматриваются некоторые типы закономерностей. Оценивается степень достоверности соответствующих гипотез в зависимости от их сложности, размера булева пространства и объема обучающей выборки. На базе закономерностей, обнаруживаемых при обучении, строятся процедуры дифференцированного предсказания, позволяющие обоснованно распознавать любой признак частично описанных объектов, не вошедших в обучающую выборку.
Предлагаемые методы можно отнести к числу логических методов в теории распознавания образов, где для построения решающих правил привлекаются аппарат алгебры логики, исчисление высказываний или теория логических выводов [l-5, 12-14, 29] . Одновременно подход к решению задачи реконструкции множества и использованию найденной системы закономерностей для распознавания образов, восходящий к работе [l2] , намечается в рамках более общей проблемы обнаружения закономерностей в потоке данных, проблемы преобразования последних в "знание", т.е. некую адекватную модель исследуемого класса данных, позволяющую оперативно находить решение разнообразных задач типа распознавания образов, классификации, прогнозирования, автоматической группировки, заполнения пропусков в экспериментальных таблицах [5—10J .
Наиболее известными среди логических алгоритмов распознавания являются алгоритм Ю.И.Журавлева, основанный на использовании понятия "тупиковых тестов" [I] и алгоритм КОРА [2,ЗІ , предназначенный для определения логических закономерностей в виде конъюнкций значений признаков. Решающее правило в обоих случаях задается в виде алгоритмической процедуры: для распознавания объектов используется голосование либо по конъюнкциям, либо по "тупиковым тестам".
В работах Ханта и других [4] рассматриваются вопросы построения процедур формирования понятий, использующих различные эвристические соображения. В основном это сводится к анализу и выбору наименьшего числа правил, разделяющих эталонные классы объектов.
В работах [П-14] строятся логические разделители для классов в задаче распознавания образов на основе методов минимизации ДНФ булевых и частичных булевых функций.
Более полное и систематическое введение, развитие и применение аппарата исчисления высказываний и методов алгебры логики для решения задачи распознавания в булевом случае признаков изложено в работе А.А.Горелика и В.А.Скрипкина [5] .
В последнее время возрос интерес к проблеме обнаружения закономерностей в таблицах экспериментальных данных. Современное состояние этой проблемы отражено в материалах трех всесоюзных симпозиумах: М03-І (Новосибирск, 1976), М03-ІІ (Рига, 1979) и М03-ІІІ (Новосибирск, 1980) [7,8,9] и также в монографиях Н.Г.За-горуйко [б] , Г.С.Лбова [I0J .С точки зрения машинных методов обнаружения закономерностей(МОЗ) задача распознавания образов является лишь частичным случаем задачи эмпирического предсказания [б] и процедура распознавания обычно распадается на два этапа. Первый этап (обучение) представляет собой процесс обнаруже-
ния (поиска) закономерностей определенных типов. Второй этап (распознавания) - использование найденных закономерностей ("знание") для предсказания значения целевого признака новых объектов. Некоторые рано возникшие логические методы распознавания можно разбирать также по этой схеме (например, алгоритмы: КОРА, "Тупиковых тестов" ...). Отметим, что проблема представления закономерностей, проблема поиска закономерностей и проблема их использования для решения задач эмпирического предсказания (классификацию таких задач можно найти в [l5J ) являются главными вопросами направления исследований, известных под названием МОЗ ( [7]- с. 2-3, [8] - с. 3-4 ).
Одним из центральных понятий МОЗ является понятие "закономерность". Формулировка этого понятия представляется довольно сложной проблемой и обсуждается в работах [l6,I7] . В общих словах это понятие сводится к следующему: закономерность есть некоторое гипотетическое утверждение об определенных свойствах изучаемых объектов и само обладающее определенными характеристиками (такими как простота, мощность, подтвержденность, красота ... ). До сих пор задачу определения этого понятия нельзя считать полностью решенной. Несмотря на это предлагают все больше методов эмпирического предсказания. При этом в каждом отдельном случае понятие закономерности конкретизируется. Эвристический выбор типа закономерностей и различие методов их использования объясняют разнообразие существующих методов эмпирического предсказания. Остановимся на некоторых важных работах.
Видимо, первыми алгоритмами, описанными в рамках МОЗ являются алгоритм ЭМП-I Н.Г.Загоруйко и Б.П.Гаврилко [їв] и алгоритм ЭМП-2 Е.Е.Витяева [l9] . В алгоритме ЭМП-I используются многоместные отношения на объектах и для выбора допустимых решений применяется критерий предпочтения отношений по их простоте. Алго-
ритм ЭМП-2 предназначается для предсказания значения многоместного предиката относительно некоторого объекта и ищет закономерность в виде "посылок-следствий", если последняя связь удовлетворяет некоторому статистическому критерию. Процедура предсказания основана на дополнительном предположении о независимости найденных закономерностей и оценке достоверности предсказуемого значения данного предиката на совокупностях закономерностей "за" и закономерностей "против".
В.И.Котюков в работе [20 ] предлагает метод "обобщающих закономерностей" для распознавания образов в случае булевых признаков. В этом методе решающее правило синтезируется на классе условных парных корреляций признаков.
Для многозначных признаков В.Е.Голендер в работе [21J излагает метод обнаружения логических закономерностей в виде конъюнкций значений признаков.
В работе Л.А.Растригина [22] рассматривается проблема синтеза эффективного правила предсказания значения выхода объекта по значениям входа, содержащимся в обучающей выборке. Алгоритм синтеза основан на методе многомерной линейной экстраполяции.
Г.С.Лбову принадлежит обоснование подхода, использующего логические функции для решения различных задач эмпирического предсказания, возникающих при обработке эмпирических таблиц, характерной особенностью которых является наличие большого числа признаков, замеренных в шкалах разных типов [ю] . Большое внимание в
[Ю] уделяется алгоритмической проблеме перебора при поиске закономерностей и реализации метода на ЭВМ.
Как отмечают многие авторы, например, в [Ю, 23-25J , в работах по распознаванию образов, основанных на поиске наилучшего решающего правила из некоторого класса без предварительного восстановления функций распределения вероятности при ограниченной вы-
борке, возникает задача определения связи между сложностью класса и объемом выборки. Этот вопрос является наиболее важным и трудным в общих теоретических исследованиях.
В работе В.Н.Вапника и А.ЯЛервоненкиса [23] для решения данной задачи используется понятие равномерной сходимости частот появления событий к их вероятностям. Эта работа установила важный теоретический результат: для надежного распознавания необходимо ограничиться классами решающих правил небольшой сложности. Однако оценка объема обучающей выборки, рассматриваемая в [23] слишком завышена, что не позволяет точно количественно определить указанную связь.
Подобные задачи для различных типов классификаторов исследовались в работе Ш.Ю.Раудиса [24] , где мерой сложности классификаторов служит размерность пространства переменных и предполагается, что имеет место нормальное распределение.
Для произвольного распределения Г.С.Лбов (см., например, [io] ) предлагает один Байесовский подход к решению данной проблемы. Приведен: пример, показывающий преимущество данного подхода по сравнению с подходом В.Н.Вапника. Однако, в большинстве случаев, не удается выразить изучаемую зависимость в явном виде.
Для практического табулирования указанной зависимости обычно используются моделирование на ЭВМ, аналитический метод или асимптотические разложения. Например, в [10] применяется метод моделирования, в [24] - метод моделирования в сочетании с аппроксимацией, приближенного вычисления, в [25] - асимптотический метод...
Вопросы о соотношении сложности класса решающих правил и объема выборки в задачах предсказания количественного признака рассмотрены в работе [26] , для метода распознавания образов, основанных на логических решающих функциях - в работе [27] , а для задачи упорядочения объектов - в работе [28] .
Вообще аналогичные вопросы для задач эмпирического предсказания еще мало исследованы. Во многих алгоритмах эмпирического предсказания выбор максимальной допустимой сложности класса решающих правил или закономерностей, используемых для их построения, опирается либо на эвристические и практические соображения, либо на общую теоретическую рекомендацию (см., например, [з] - с.ПО;
[ю] - с. 14, с. 38; [21] - с. III; [34] - с. 79 ...) и таким образом остается нестрого обоснованным.
А.Д.Закревский в работах [12,30,31J предлагает основывать распознавание образов в булевом пространстве признаков на предварительном построении "области запрета", описываемой посредством ДНФ с конъюнкциями ограниченного ранга. Упомянутые конъюнкции, задающие запретные интервалы в булевом пространстве, интерпретируются как импликативные закономерности. Простота этой закономерности оценивается, естественно, числом переменных, входящих в нее, т.е. рангом конъюнкции, а мощность - объемом области запрета. Распознавание основано на решении задачи реконструкции множества "реальных" объектов, подчиняющегося определенным имплика-тивным закономерностям по его случайной выборке. При этом необходимо определить степень достоверности гипотезы об импликативных закономерностях, выдвигаемой при анализе выборки. В работе [12] было предложено оценить эту степень достоверности через вероятность Р (м, n, I) появления хотя бы одной закономерности данного типа ранга Ь в случайной выборке объема по при фактическом отсутствии всяких закономерностей в пространстве г\ признаков.
Введение величины \(yy\,y),1) и условие где 6 - достаточно малое пороговое значение, позволяют установить зависимость между параметрами т , п , Ь и обосновывают выбор максимального допустимого значения ранга v при заданных
т.п.
Выборка, не содержащая ни~ одной импликативной закономерности ранга Ь t называется "протыкающей" (см. [Зб] ), так как в этом случае каждый интервал ранга . в пространстве п признаков "протыкается" по крайней мере одной точкой из выборки. Оценки минимальной длины "протыкающей" выборки даются в работах [36,37]. А оценка числа "протыкающих" выборок, фактически, была получена впервые (снизу) в работе [30] .
Распознавание сводится к логическому выводу, т.е. к выбору значений целевого признака, не вступающих в противоречие с системой обнаруживаемых на этапе обучения закономерностей.
Данный метод распознавания образов имеет следующие важные особенности:
1. Выбранная форма закономерностей универсальна в смысле
описания любых закономерностей в булевом пространстве. Причем та
кая форма позволяет использовать хорошо развитую теорию миними
заций булевых функций для сжатого представления закономерностей
в виде ДНФ-модели [l2f3lj . Практически удобные алгоритмы построения ДНФ-модели изложены в работах [32,33] .
В отличие от традиционных методов распознавания образов, в данном подходе предусматривается случай отказа от предсказания, если для последнего нет достаточных оснований. В то же время этот метод позволяет решить задачу распознавания в ее самой широкой постановке - предсказать любой неизвестный признак частично заданного объекта.
Численные результаты по вычислению верхней оценки для вероятности P(w;^/V показывают, что для выполнения условия
P(m;>i;-6J^ ранг закономерностей должен быть малым по сравнению с размером пространства [30 ] . Это существенно ограничивает перебор, производимый при поиске закономерностей и делает реальной его реализацию на ЭВМ. Поэтому алгоритмическая проблема
перебора не возникает.
На наш взгляд, предложенный подход представляет новый - логико-комбинаторный подход к изучению связи между сложностью закономерностей и объемом выборки в задачах эмпирического предсказания, использующих метод логического вывода для предсказания на основе закономерностей данного класса, выявляемых при обучении.
Настоящая диссертационная работа может рассматриваться как некоторые попытки продолжить исследования А.Д.Закревского и других авторов в вышеуказанном направлении. Наряду с обоснованием некоторых логических правил предсказания в булевом пространстве, в работе доказываются различные оценки достоверности используемых закономерностей, что позволяют довольно точно и эффективно определить связь между объемом выборки и сложностью этих закономерностей.
В соответствии с вышепоставленными целями диссертация разбита на 3 главы и 10 параграфов. Приступаем к ее краткому изложению.
Верхняя оценка и оценка по грешности для оценки
Возможны 4 исхода предсказания. Учитываются ситуации, в которых оба значения признака д-с оказываются допустимыми или ни одно из них не удовлетворяют функции запрета D . В последнем случае существование объекта Jl с характеристикой к вступает в противоречие с построенной на обучающей выборке моделью, что может послужить основанием к ее корректировке, или, ставить под сомнение сам объект К . Впрочем такое событие следует считать маловероятным, учитывая способ оценки степени достоверности модели, излагаемый ниже.
Оценка степени достоверности гипотез об импликативных закономерностях Находимые при анализе обучающей выборки /VI9 пустые ин тервалы ранга і служат основанием для выдвижения гипотез о Ч соответствующих импликативных закономерностях в множестве-ре 22 альных"объектов VL. Однако следует оценить степень достоверности таких гипотез.
В работе [30] предлагается оценить степень достоверности гипотез о импликативных заномерностях ранга I через вероятность Р (м,я, 2) появления хотя бы одного пустого интервала ранга і в выборке М длины in , если последняя выбирается из булева пространства п признаков по равномерному закону распределения. Ясно чем меньше эта вероятность, тем больше степень достоверности. В дальнейшем, когда речь идет о степени достоверности упомянутых гипотез, мы будем иметь ввиду соответствующее значение вероятности Р(пгп,0 Искомая вероятность Г О АО имеет довольно сложное аналитическое выражение. Для оценки ее сверху в работе [30] была предложена формула POW) WCm,n,E) = CU i- f, (І) где W{YY\,v\,i) - математическое ожидание числа пустых интервалов ранга С в выборке Мэ
Для нахождения граничного допустимого значения ранга I импликативных закономерностях, о которых можно выдвигать соответствующие гипотезы с достаточно высокой степенью достоверности при заданных значениях тип, условие Р(т,пД) & (2) заменяется легко проверяемым условием W(m;n,e) U. (3)
На основании этого условия были выполнены расчеты по определению граничных допустимых значений ранга iw в некотором диапазоне значений параметров т,У) (см. [30] или таблицы 2, 3). Как видно из теоремы о вероятности суммы событий, в области малых значений величина W І АЧ должна хорошо аппроксимировать вероятность гіт/ Л) . Но для практического использования этой оценки необходимо определить ее точность. В связи с этим возникают следующие вопросы:
Как можно определить погрешность оценки W(m,n,t) 2. Значения w , вычисляемые с помощью условия (3) совпадают ли со значениями іулах. » удовлетворяющими условию (2)? Оставшаяся часть данной главы посвящена этим вопросам. Необходимые формулы. В заключение этого параграфа приведем несколько формул из комбинаторного анализа, которыми часто будем пользоваться в дальнейшем изложении [35] . I. Пусть даны N элементов OLL,(XZ}... , Сім , которые могут обладать или не обладать некоторыми свойствами At , Ag, ..., Aiv Обозначим через г\_ (ft) сумму элементов, обладающих точно К свойствами и через \\у {її) сумму элементов, обладающих не менее чем fi свойствами. Имеет место следующая формула: vA/t» Aj r-V Aj») "" Умма элементов, обладающих фиксированными свойствами Au , Aj" ,..., Aj» одновременно.
Аппроксимация оценок известными вероятностны ми распределениями
В этой главе будем рассматривать задачу реконструкции множества Мр и задачу распознавания образов, сформулированные в предыдущей главе, в более общем случае. Обобщения сделаем; на вид закономерностей, упомянутых в условии б) Задачи реконструкции множества ( I) и на данные обучающей выборки М$ .
Вместо рассмотренных детерминированных имшшкативных закономерностей будем вводить стохастические импликативные закономерности, которые удобно интерпретировать как зашумлеяные детерминированные. Т.е. закономерностями будем считать не только непересекающиеся с выборкой М5 интервалы определенного ранга С , но и интервалы, содержащие некоторые элементы из нее, но их там достаточно мало.
На практике часто встречаются случаи, когда экспериментальные данные фиксируются не полностью. Поэтому будем предполагать еще, что объекты, входящие в выборку М » представляются троичными векторами. Црочерки стоящие в этих векторах, интерпретируются как знак неопределенности соответствующих признаков. В связи с этим обучающую выборку можно рассматривать как троичную матрицу, а конкретную импликативную закономерность -троичный вектор. Будем говорить, что троичный вектор V" имплицируется тро 42 ичным вектором ьс (или и имплицирует ), если все компо-ненты вектора VT , отличающиеся от прочерка совпадают с соответствующими компонентами вектора
Троичные векторы называются ортогональными, если найдутся такие одноименные компоненты, этих векторов, что они отличаются друг от друга и от прочерков " - ". Троичный вектор Оу называется ортогональным к троичной матрице U если V" ортогонален к всем ее строкам.
Конъюнкция к- называется импликантой функции если функция t-»sl . Бели, кроме того, не существует конъюнкции % , такая, что ,то к. называется простой импликантож функции -f .
При наличии пропусков в обучающей выборке, стохастическими имшшкативными закономерностями будем считать интервалы определенного ранга, если представляющий его троичный вектор либо ортогонален матрице Мэ , либо имплицируется некоторыми строками из М9 , но таких строк не больше j3 -допустимая степень "шума"
В зависимости от предположения о распределении прочерков в матрице М в дальнейшем будем рассматривать два случая. Будем сохранять все обозначения из I.
Будем считать, что число пропусков в описании каждого объекта (в каждой строке матрицы М9 ) равно f . Число матриц размера ЙТхЛ с такими строками, очевидно, равно (См Z ) В этом случае степень достоверности гипотез о стохастических им-пликативных закономерностях будем оценивать через вероятность появления хотя бы одной закономерности данного типа в выборке длины ГА , если последняя выбирается из мно 43 жества всех упомянутых троичных матриц с вероятностью Оказывается справедливой следующая оценка. Утверждение где символом (Я-Ур, обозначено произведение Доказательство.
Оценим вероятность Г о(т v сверху математическим ожиданием числа различных интервалов ранга ь , не имплицируемых достаточно большим количеством строк (не меньше т-оС ) каждой матрицы класса На основе работы [30] и результата главы I, можно заключить, что эта величина дает хорошую аппроксимацию вероятность В области ее малых значе ний. Для доказательства оценки, нам остается лишь определить значение Представляем это математическое ожидание в виде разложения: число пар (U/t) » в которых матрица троичный вектор, компонент которого отличается от символа причем І имплицируется точно .1 выделенными зафиксированными строками матрицы
Оценки степени достоверности гипотез о функциональных закономерностях
Если NY-NZ. , то НУ- HZ для любого подмножества N с N . Обратное утверждение в общем случае неверно. Но если наложить некоторое условие на рассматриваемую зависимость, то с достаточно высокой степенью достоверности можно сказать, что из N/- N2 следует иЫУ— Ы2 Это замечание служит основанием для решения задач реконструкции множества и распознавания образов.
Алгебраическая модель системы функциональных зависимостей между признаками Х1,Хг,.--;Хп по некоторому подмножество \сДД впервые предложил Кодд [55] . Он назвал ее реляционной моделью для баз данных. В терминологии теории Кодда, признаки Xi, L= 1,П называются атрибутами и каждый из них имеет свою область значений. Потом эта теория получила развитие в ряде работ. Перечисляем некоторые важные и нужные для дальнейшего изложения работы [41-44] , [55-60] . Вкратце приводим некоторые понятия и результаты теории реляционной модели Кодда.
Совокупность всех пар образует структуру функциональных зависимостей множества М . Как показали в работах [56,58,60] , эта структура характеризуется следующей системой аксиом 1) Структура функциональных зависимостей представляет собой бинарное отношение м между подмножествами множества А , удовлетворяющее условиям I) - 3). Вообще для любого конечного множества X , будем говорить, что на А задана структура функциональных зависимостей, если на булеане Зо(Х) задано бинарное отношение , удовлетворяющее условиям I) - 3). Эту структуру будем обозначать через
В структуре S(X) Z полно функционально зависит от У , если У - 2Е и никакое собственное подмножество Усі У этим свойством не обладает. Полная функциональная зависимость У- 2. называется также элементарной. функциональную зависимость, определенную по аксиоме I) называется тривиальной. С точки зрения задачи распознавания образов такие функциональные зависимости ничего полезного не дают.
Множество Кс X называется ключом структуры SCX) » если X полно функционально зависит от К .
Среди структур S(X) имеется наименьшая и наибольшая. Для наименьшей структуры SminOO У- Z будет иметь место тогда и только тогда, когда 2 Я У (т.е. такая структура содержит только тривиальные функциональные зависимости). Для наибольшей структуры Smax(X) У- 2. имеет место для любых У2 С X.
Пересечение структур функциональных связей (как бинарных отношений на ) есть структура функциональных зависимостей. Отсюда следует, что эти структуры образуют решетку. Поэтому для любого множества G - \ = (У )/ У, Х,У- 2.]ї существует наименьшая структура G = 09( ), содержащая G Множество \Э называется системой образующих структуры Ъг (X) і а сама структура S/ (X) - замыканием (9
Система образующих G называется базисом своего замыкания О , если удаление из \Э любого элемента уменьшает замыкание. Базис называется элементарным, если он состоит из элементарных функциональных зависимостей.
Можно считать, что все элементы системы образующих имеют вид У- Х .У Х.Х-вХ 9то слеДУет из того, что набор зависимостей J у . . і є]Ч эквивалентен одной зависи мости У - " и Х(, . Поэтому не умаляя общности, в дальнейшем мы будем рассматривать функциональные зависимости только такого вида.
Структура функциональных зависимостей S(X ) } Х сХ , называется полной подструктурой структуры S(X) » если для любых тогда и только тогда, когда (У,2) О S(X). Следуя Делобелю и Кейси [57] , для каждой системы функциональных зависимостей: сопоставляется ДНФ где: Ус =xtx4...xift . если УсЧХч,Хсй ...,Хі J 2 определяется аналогично,
Обратно, каждой ДНФ ф , которая записана в виде (37), сопоставляется набор функциональных зависимостей (36). Замыкание G в этом случае будет обозначаться через БСФ).
Основной результат работы [57] состоит в утверждении, что булева функция гіхі}хгу..уХп) не зависит от системы образующих (5 . Другими словами, эквивалентные ДНФ вида (37) соответствуют эквивалентным системам образующих. При этом под эквивалентными системами образующих будем понимать те, которые образуют одну и ту же структуру S(X)
Некоторые свойства системы частичных булевых функций, представляющих данную схему функцио нальных закономерностей
Отмечаем, что в реляционной модели базы данных Кодца каждый признак имеет свою область значений. Поэтому предлагаемая в данной главе модель обнаружения закономерностей и распознавания образов может быть распространена на более общий случай, например, на случай -u-значных признаков. В этом случае степень достоверности закономерностей может оцениваться формулой, аналогичной формуле (40). В то же время, условие реализуемости и максимальности для системы -Я-значных логических функций и также его связь с структурой функциональных закономерностей требует дополнительных исследований.
Предложена оценка Wj{w,Y),l) для степени достоверности гипотезы о функциональных закономерностях pWwAО (40). Для ее практического вычисления доказано предельное соотношение (41). Проведены численные эксперименты на ЭВМ по вычислению величины VW(m,fi,0 и определению максимального допустимого значения ранга функциональных закономерностей, которые можно найти при ограниченной образующей выборки Mg . Полученные результаты подтверждают применимость приближенной формулы (41) (таблица 9).
Оценена достаточная длина обучающей выборки lV\9 для полного выявления всех булевых функций, представляющих данную структуру функциональных зависимостей 5(Х) (оценки (46), (48)). Установлены некоторые свойства системы булевых функций, представляющих данную структуру функциональных зависимостей (утверждения 3.5 - 3.8).
На основании результатов теории реляционной модели банка данных и вышеуказанных результатов дано решение задачи реконструкции множества в случае функциональных закономерностей и связанной с ней задачи распознавания образов. Обоснованы логические правила предсказания любого неизвестного признака частично описанного объекта в случае дополняемой системы функциональных закономерностей и в случае максимальной системы функциональных закономерностей. Приведен пример, иллюстрирующий данный метод распознавания.
В случае У- Х{ф S(X) и Си Є МЭ[У] всегда тождественно истинно булево выражение (fexi= I]) = о) V V {кХ = х) о) . Поэтому в таблице 12 присутствуют только случаи 7,8,9, соответствующие данной ситуации. Отметим, что в случае максимальной системы G функциональных зависимостей, обнаруживаемой по Мэ из того, что У-»ХС в S(X) и со фЫ\э[У] сразу следует тождественную истинность булева выражения ( кхь == D - v д( кХі =) =ii} , т.к. в противном случае функция :А/1Э/- МЭХ дополняема бы на новом аргументе (л о или со і.
Так что случаи 3,4,5 в таблице 12 невозможны. Т.е. в такой ситуации система Q либо дает определенный ответ на прогноз признака Х , либо данное значение со объекта противоречит системе найденных закономерностей G ( Мр).
Если же система G максимальна и У- Х- ф S(X) » то для предсказания признака А удобно использовать область NTY" Нетрудно показать, что в этом случае таблица 12 упрощается до таблицы 13. В таблице 13 NTN+ оГХЛ обозначает проекцию по признаку /\L тех элементов множества N T)" " , имеющих характеристику h\y J = СО
Подведем итоги решения задачи реконструкции множества реальных объектов Мр и связанной с ней задачи распознавания образов. Согласно условию б) в I, структура множества М-р подчинена достаточно сильным функциональным закономерностям. Это требование можно удовлетворить, если налагать ограничение на ранг элементарных функциональных зависимостей вида У — Х(, » Х в X » УСХ То есть, если структура множества подчинена системе закономерностей ранга не выше некоторого поро гового значения max то всегда можно определить длину вы борки w = Mj І чтобы система G элементарных зависимостей, обнаруживаемая по М3 , могла быть принята за систему элементарных зависимостей и в множестве Мр с достаточно высокой степенью достоверности (8). Тем самым по \/э будет восстановлена вся структура 5(Х) .По этой структуре и информации, содержащейся в Мл , получаем систему булевых функций Q (или/ достаточно, одну систему функций, составляющую базис структуры 5(х) ). Отсюда можем составлять функции D , D (см. (50)). Область Nry не зависит от выбора системы образующих G Множество ДДр » в общем случае восстанавливается приближенно, путем непротиворечивого продолжения системы G в области М . Мр точно восстанавливается только при условии максимальности системы (э (см. утверждение 3.8): Мр = NJV"
