Автореферат (1137434), страница 2
Текст из файла (страница 2)
Множество существенных содержаний является множествомзаключений импликаций из минимального базиса импликаций (любого минимального базиса импликаций).В разделе 2.2 описывается структура минимальных базисов импликаций. Базис импликаций J минимален тогда и только тогда, когда для любойимпликации → ∈ J квазизамыкание посылки является псевдосодержанием и у различных импликаций квазизамыкания посылок различны.В разделе 2.3 приводится ранее известный результат о полиномиальнойэквивалентности задачи поиска минимального базиса импликаций формального контекста и задачи поиска минимального покрытия функциональных зависимостей реляционной базы данных.В разделе 2.4 рассматривается задача:Задача 1.
Распознавание псевдосодержания (PI)ВХОД: Формальный контекст K = (, , ) и подмножество признаков ⊆ .ВОПРОС: Является ли псевдосодержанием контекста K?и доказываетсяТеорема 1. Задача PI co -трудна.В разделах 2.5 и 2.6 приводятся несколько простых следствий Теоремы 1. В частности доказывается, что посылки минимального базиса импликаций не могут быть перечислены в обратном лектическом порядке (лексикографическом порядке на характеристических векторах множеств) с полиномиальной задержкой, если ̸= . Также доказывается, что задачараспознавания существенных содержаний NP-полна.В разделе 2.7 рассматривается задача эквивалентности систем замыканий заданных контекстом и набором импликаций, в котором у всех импликаций посылки по мощности не больше 2.
Доказывается, что такая задача непроще задачи, в которой нет ограничения на мощности посылок.В разделе 2.8 рассматривается новая модель импликативных зависимостей – приближенный базис импликаций:8Определение 1. Набор импликаций называется приближенным базисом формального контекста K = (, , ), если для случайно и равномерно выбранного подмножества ⊆ выполняется условие ( ′′ = ) > 1 − , 0 < < 1.Таким образом 1 − соответствует точности приближения.Преимущества, предложенной модели по сравнению с точным базисом:∙ Существенно меньшее количество импликаций∙ Существенно более быстрое время построения, которое линейно от −1∙ Высокая точность приближения (1 − )Приведем псевдокод алгоритма построения приближенного базиса импликаций формального контекста K = (, , ), основанного на результатах[Д.
Англуин и др. 1992] об обучении Хорновской Конъюнктивной НормальнойФормы (КНФ) при помощи двух оракулов.UpdateBase(K, , )1 for each → ∈ 2do if * And ( ∩ )′′ ̸= ∩ 3then заменить в импликацию → 4на ∩ → ( ∩ )′′5return J6 ← ∪ { ← ′′ }7 return JApproximateImplicationBase(K, )1 J ←∅2 for ← 1 to 3do выбрать случайное замкнутое множество базиса 4if ′′ ̸= 5then J ← UpdateBase(K, , )6 return JДанный алгоритм использует следующий метод генерации случайногомножества, замкнутого в базисе :GenerateRandomClosedSet()1 X ← random subset of 2 X ← (, )3 return XЗдесь LinClosure – линейный алгоритм вычисления замыкания в базисе импликаций [Д.
Мейер 1987]. Доказывается теорема:9Теорема 2. Математическое ожидание времени работы алгоритма, до достижения точности 1− (0 < < 1)для контекста K = (, , ), равно (| || | · (||| | + | || |) · −1 ),где – минимальный базис импликаций.В разделе 2.8.1 приводятся результаты компьютерных экспериментовприближенного базиса импликаций на реальных данных.̂︁база данных || | | | | ||| |Chess3197 39 76 43,1 0,9988 595Zoo101 28 433,3 0,9999 1,853P.-Op. P.9025 855,0 0,9989 2,06Grav707 473 53 233,4 0,9999 3129Grav_a707 156 39 286,6 0,9999 92,05Таблица 0.1. Результаты вычисления приближенного базиса.∙ – приближенный базис импликаций∙ – точный базис импликаций̂︁ – оценка вероятности ( ′′ = ) того, что для случайного под∙ множества ⊆ замыкания совпадают∙ – время построения точного базиса алгоритмом Гантера∙ – время построения приближенного базисаВ третьей главе приводятся результаты связанные с общими содержаниями формальных контекстов.В разделах 3.1–3.3 показывается связь базиса импликаций с общимисодержаниями и приводится общий алгоритм поиска минимального базисаимпликаций.
Пусть даны два формальных контекста с общим множествомпризнаков: K1 = (1 , , 1 ) с базисом импликаций (не обязательно минимальным) J1 и контекст K2 = (2 , , 2 ) с базисом импликаций J2 . Очевидно, что множество их общих содержаний является системой замыканий.Поэтому мы можем рассмотреть контекст K = (, , ), объектные содержания, которого будут неразложимыми элементами системы замыканий общих содержаний. Будем называть контекст K, контекстом общих содержаний.Можно предложить следующий общий алгоритм построения минимальногобазиса импликаций:FindMinBase(K = (, , ))1 Представить контекст K множеством контекстов K1 , K2 , . . .
, K ,для которых K будет являться контекстом общих содержаний2 Для каждого контекста K найти минимальный базис импликаций J .3 J ← J1 ∪ J2 ∪ . . . ∪ J4 J ← ()5 return J10В разделе 3.4 показывается, что описанный в статье [Ф. Дистель и др.2011] алгоритм поиска собственных посылок, является частным случаем приведенного общего алгоритма поиска базиса импликаций.В разделе 3.5 описывается модель сходства формальных понятий - интенсиональная связность.В разделе 3.6 исследуются задачи, связанные с общими содержаниями формальных контекстов.
Предлагается алгоритм вычисления операторазамыканий общих содержаний (·) контекстов K1 = (1 , , 1 ), . . . , K =( , , ):GetClosure()1 answer ← 2 for ← 1 to 3do remove all rows from [] that do not contain 4 for ← 1 to 5do for ← 1 to | |6do if not answer [m]7then if [][][] = true for all 1 ≤ ≤ | |8then answer [] ← true9push in shared -attributes10else for each 1 ≤ ≤ | | such that not [][][]11do push (, ) in not-in[]12counter [][] ← counter [][] + 113 while shared -attributes not empty14do pop from shared -attributes15while not-in[] not empty16do pop (object-index , context-index ) from not-in[]17for ← 1 to | |18do if not [][context-index ][object-index ]19then counter [context-index ][i ] ←← counter [context-index ][i ] −120if counter [context-index ][i ] ≤ 0and not answer [i ]21then answer [i ] = true22push in shared -attributes23 return answerЗдесь [] - это бинарная матрица, задающая отношение , counter [][]равно количеству объектов из для которых не выполнено, sharedattributes и not-in[] могут быть реализованы как стеки или как любые другиеструктуры данных, поддерживающие операции “вытащить"(pop) любой объект и “вставить"(push) любой объект за время (1).Доказывается, что время работы этого алгоритма линейно от размеравхода:11Теорема 3.
Алгоритм () вычисляет для произвольного подмножества признаков ⊆ ∑︀ и контекстов K1 =(1 , , 1 ), . . . , K = ( , , ) за время (| | 1≤≤ | |).Также рассматривается случай, когда все контексты заданы спискамипризнаков своих объектов (а не матрицами, как в предыдущем алгоритме) иприводится алгоритм вычисления оператора замыканий общих содержаний залинейное от входа время.Теорема 4. Алгоритм _2() вычисляет для произвольного подмножества признаков ⊆∑︀ и контекстов K1 =(1 , , 1 ), . .
. , K = ( , , ) за время ( 1≤≤ | |).Используя алгоритм (·) (_2(·)) в качестве оракула, можно перечислять все общие содержания с полиномиальной задержкой, применяя стандартные алгоритмы АФП (такие как Norris, Next Closure,Close-by-One).В разделе 3.8 показывается как сцепления формальных контекстов могутбыть представлены через общие содержания.В четвертой главе рассматриваются вопросы связанные с обучением гипотезам.Пусть признаки из описывают "структуру"объектов, а - целевойпризнак, отличный от всех признаков из . Например, в фармакологическихприложениях структурные признаки могут соответствовать подграфам молекулярных графов химических соединений, а целевой признак - биологическимсвойствам этих соединений.Входные данные для контекста обучения могут быть представлены множествами положительных, отрицательных и неопределенных примеров.
Положительные примеры (или (+)-примеры) – это объекты, о которых известно,что они обладают признаком , а отрицательные примеры (или (−)-примеры)– это объекты, о которых известно, что они не обладают признаком Определение 2. Рассмотрим положительный контекст K+ =(+ , , ℐ+ ) и отрицательный контекст K− = (− , , ℐ− ). КонтекстK± = (+ ∪ − , ∪ {}, ℐ+ ∪ ℐ− ∪ + × {}) называется контекстомобучения.
Оператор Галуа для этого контекста обозначается как ±.Определение 3. Подмножество ⊆ называется положительнойгипотезой (или (+)-гипотезой) контекста обучения K± если - содержание контекста K+ и не является подмножеством ни одного содержания контекста K− .Аналогично определяются отрицательные гипотезы (или (-)-гипотезы).Содержание контекста K+ , которое принадлежит хотя бы одному отрицательному примеру, называется фальсифицированным (+)-обобщением.Помимо положительных и отрицательных примеров обычно имеютсяобъекты, для которых значение целевого признака неизвестно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
