Содержание к диссертации
Введение
1 Построение зависимостей в данных с помощью решеток замкнутых множеств: основные понятия и состояние предметной области 10
1.1 Основные определения 10
1.1.1 Частично упорядоченные множества и решетки . 10
1.1.2 Анализ формальных понятий 14
1.1.3 Теория алгоритмов и вычислительная сложность . 18
1.2 Модели зависимостей и их вычисление 27
1.3 Минимальная модель знаний о предметной области: минимальный базис импликаций 32
1.4 Задачи и алгоритмы построения гипотез 36
2 Базисы импликаций и функциональных зависимостей 42
2.1 Квазизамкнутые множества и псевдосодержания 42
2.2 Структура минимальных базисов импликаций 43
2.3 Функциональные зависимости и импликации 45
2.4 Распознавание псевдосодержаиий 46
2.5 Лектически максимальные псевдосодержанпя и перечисление максимальных псевдосодержаний 54
2.6 Распознавание существенных содержаний 56
2.6.1 Посылка импликации из минимального базиса . 57
2.7 Базис импликаций с двухэлементными посылками 60
2.8 Приближенный базис импликаций 62
2.8.1 Результаты экспериментов 65
3 Базисы импликаций и общие содержания 67
3.1 Связь базиса импликаций с общими содержаниями 67
3.2 Общий метод поиска минимального базиса импликаций через общие содержания 68
3.2.1 Поиск собственных посылок через общие содержания 68
3.3 Интенсионально связанные понятия 69
3.4 Понятия с общими содержаниями 71
3.5 Сцепления и общие содержания 80
4 Обучение гипотезам 84
4.1 Теоретико-решеточная интерпретация гипотез и классификации 86
4.2 Перечисление гипотез и дуализация монотонных булевых функций па решетках 90
4.3 Распределенное обучение гипотезам 99
4.4 Устойчивость понятий и гипотез 101
4.5 Приближенный подсчет числа замкнутых и незамкнутых множеств 103
4.6 Индекс вероятностной устойчивости 106
4.7 Анализ результатов вычислений индекса вероятностной устойчивости 109
4.8 Устойчивые гипотезы: Результаты экспериментов с данными по токсичности химических соединений 111
5 Комплекс программ 114
5.1 Программный комплекс Cordiet 114
5.2 Программная реализация построения базисов импликаций . 114
5.3 Программная реализация алгоритма вычисления оператора замыкания общих содержаний 116
5.4 Программная реализация распределенного обучения гипотезам 117
Заключение 118
Литература 121
Приложения 134
- Теория алгоритмов и вычислительная сложность
- Распознавание псевдосодержаиий
- Понятия с общими содержаниями
- Приближенный подсчет числа замкнутых и незамкнутых множеств
Введение к работе
Актуальность работы. Стремительный рост объема данных разной природы, наблюдающийся в последние десятилетия, приводит к необходимости разработки эффективных методов их автоматического и интерактивного анализа. Одной из распространенных математических моделей, позволяющих описывать методы и алгоритмы анализа данных, является анализ формальных понятий.
Анализ формальных понятий (АФП) является ветвью прикладной алгебраической теории решеток, широко используемой для описания методов анализа данных. АФП предлагает средства моделирования онтологий и так- сономий предметных областей на основе решеток понятий, а также модели точных и приближенных зависимостей в данных.
Для многих ключевых задач анализа формальных понятий до сих пор неизвестны эффективные алгоритмы и какие-либо теоретические оценки их сложности. Основной целью большинства существующих исследований является анализ данных на основе методов АФП, в то время как эффективные алгоритмы и вычислительная сложность этих методов уходит на второй план. Примерами актуальных задач являются:
Модели импликативных зависимостей, позволяющие более сжатое представление и эффективную алгоритмическую реализацию
Эффективные алгоритмы порождения приближенных базисов импликаций, множества минимальных ДСМ-гипотез
Эффективные алгоритмы распознавания псевдосодержаний, задающих оптимальный базис импликаций
Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостей
Так например, эффективные алгоритмы порождения и сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей (импликаций) была одной из основных открытых задач АФП на протяжении многих лет (список открытых задач АФП [U. Priss 2006] задачи 2,8,9).
Объектом исследования являются модели импликативных зависимостей в данных и их эффективная алгоритмическая реализация.
Целью исследования является разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, а также решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.
Методы исследования. В диссертации применяются методы анализа формальных понятий, дискретной оптимизации, вероятностных алгоритмов и теории вычислительной сложности алгоритмов.
Научная новизна. В диссертации получены следующие основные новые научные результаты, которые выносятся на защиту:
-
-
Доказана трудноразрешимость задач, связанных с вычислением классического минимального базиса импликаций.
-
Предложена новая модель приближенного базиса импликаций формального контекста, алгоритм его вычисления и эффективная программная реализация.
-
Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке
-
Предложена и экспериментально проверена модель распределенного обучения гипотезам - импликативным зависимостям для задачи машинного обучения.
-
Предложен линейный по времени алгоритм поиска всех гипотез по распределенной обучающей выборке и его программная реализация.
-
Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий - вероятностный индекс устойчивости.
-
Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.
-
Решены давно сформулированные и остававшиеся открытыми задачи создания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний.
-
Показана полиномиальная эквивалентность задачи перечисления минимальных гипотез и задачи дуализации монотонной булевой функции на решетке.
10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделении прикладной математики и информатики НИУ ВШЭ комплекс программ.
Теоретическая значимость подтверждается тем, что были предложены новые модели импликативных зависимостей, а также средства их оценивания, показана их адекватность практическим задачам и возможность эффективной алгоритмической реализации. Были решены открытые теоретические задачи прикладной теории решеток и анализа данных.
Практическая значимость подтверждена экспериментами по построению приближенного базиса импликаций, распределенному обучению гипотезам и вычислению вероятностной устойчивости. Эти эксперименты показали значительные улучшения во времени вычисления и в качестве полученных результатов. Был разработан комплекс программ, в который вошли алгоритмы, опубликованные в данной работе.
Достоверность результатов подтверждена строгими математическими доказательствами теоретических утверждений, экспериментальной проверкой результатов численных расчетов и практической эффективности программных реализаций.
АПРОБАЦИЯ РАБОТЫ Основные результаты работы докладывались и обсуждались на следующих научных конференциях:
-
-
-
8-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Агадир, Марокко, 2010.
-
7-ой международной конференции по решеткам понятий и их приложениям (7th International Confere6nce on Concept Lattices and Their Applications), Севилья, Испания, 2010. [Награда за лучшую статью]
-
9-ой международной конференции по анализу формальных понятий (9th International Conference on Formal Concept Analysis), Никосия, Кипр, 2011.
-
10-ой международной конференции по анализу формальных понятий (8th International Conferenceon Formal ConceptAnalysis), Лёвен, Бельгия, 2012.
Публикации. Основные результаты работы изложены в 6 научных статьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК.
Структура и объем диссертации. Диссертация состоит из пяти глав, заключения, списка литературы и приложений. Общий объем основного текста работы — 133 страницы. Список литературы включает 100 наименований.
Теория алгоритмов и вычислительная сложность
Индивидуальная задача принадлежит D\\ в том и только том случае, когда она может быть получена из стандартной формы описания подстановкой конкретных значений во все компоненты условия. Индивидуальная задача принадлежит Уц В том и только том случае, когда ответом на вопрос задачи будет "да". Задачи разрешения могут быть формально представлены в виде языков. Для любого конечного множества символов через Е обозначается множество всех конечных цепочек (слов), составленных из символов алфавита . Произвольное подмножество L С называется языком в алфавите X.
Соответствие между задачами разрешения и языками устанавливается с помощью схем кодирования (encoding schemes). Для данной задачи П, схема кодирования е описывает каждую индивидуальную задачу из П подходящим словом в некотором фиксированном алфавите S. Таким образом, задача П и ее схема кодирования е разбивают множество на три класса: слова, не являющиеся кодами индивидуальных задач из П, слова, являющиеся кодами индивидуальных задач из П с ответом "нет"на вопрос и слова, являющиеся кодами индивидуальных задач из П с ответом "да". Третий класс слов и есть язык 1/[П,е], ставящийся в соответствие задаче П при кодировании е. С каждой задачей разрешения связана не зависящая от схемы кодирования формальная мера длины (размера) входа (input length). Она определяется как функция Length: Du — Z , которая при любой "разумной схеме кодирования" е (подразумевающей "естественную краткость" или экспоненциальную несжимаемость и "декодируемость", обсуждение этих понятий можно найти в [8]) полиномиально эквивалентна длине кода индивидуальной задачи, т.е. существуют два полинома р и р такие, что если I есть индивидуальная задача из Du и слово х есть код I при кодировании е, то Length[7] р(\х\) и ж р\Length[J]), где \х\ -длина слова х.
Время работы алгоритма (программы для детерминированной машины Тьюринга или ДМТ-программы) решения индивидуальной задачи І Є Du с размером входа п определяется как число шагов до момента остановки программы. Временная сложность алгоритма для решения задачи Du определяется как максимальное время работы алгоритма среди всех индивидуальных задач со входом размера п. Временную сложность алгоритма будем обозначать как функцию Тм{п). Алгоритм называется полиномиальной ДМТ-программой, если существует такой полином р, что для всех п Є N Тд/(гг) р(п).
Класс полиномиально вычислимых функций Р определяется как множество языков: Р = {L: существует полиномиальная ДМТ-программа М для которой L = LM Для определения классов NP и #Р, которые мы будем использовать в дальнейшем, используется понятие недетерминированной машины Тьюринга (НДМТ), которая состоит из двух модулей: обычной ДМТ и модуля угадывания. Вычисление на НДМТ состоит из двух стадий - стадии угадывания и стадии проверки: 1) на стадии угадывания, при получении индивидуальной задачи 7, происходит угадывание некоторой структуры (слова) 5G S ; 2) / и S подаются на вход ДМТ на стадии проверки, которая выполняется как обычная программа ДМТ и либо заканчивается ответом "да" (если S есть решение задачи /) либо ответом "нет", либо продолжается без остановки. Слово S также называют свидетелем. Недетерминированный алгоритм (ПДА) определяется как пара (угадай некоторое слово S; проверь S детерминированным алгоритмом А). НДА "решает"задачу разрешения П, если следующие два свойства имеют место для всех индивидуальных задач / Є D\\\ 1) Если І Є Уц, то существует такая структура 5, угадывание которой для входа / приведет к тому, что стадия проверки, начиная работу на входе (I,S) закончится ответом "да". 2) Если / 0 Уп, то не существует такой структуры S, угадывание которой для входа / обеспечило бы окончание стадии на входе (1, S) с ответом "да". Недетерминированный алгоритм, решающий задачу разрешения П работает в течение "полиномиального времени", если найдется полином р такой, что для любой индивидуальной задачи /п Є Уп найдется догадка S1, приводящая на стадии детерминированной проверки на входе (I, S) к ответу "да"за время (Length /). Неформально, класс NP - это класс всех задач разрешения П, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за полиномиальное время или, другими словами, -это класс задач, для которых существует полиномиальное решение (свидетель), которое может быть проверено за полиномиальное время. Полиномиальная сводимость (по Карпу) задачи разрешения Пі к задаче разрешения П2 (обозначается Пі ос П2) означает наличие функции /: Diij —ї Du21 удовлетворяющая следующим двум условиям: 1. Существует полиномиальная ДМТ-программа, вычисляющая /; 2. Для всех / Є -Drij выполнение / Є Угії имеет место тогда и только тогда, когда /(/) Є Уп2. Полиномиальная эквивалентность задачи разрешения Пі и задачи разрешения П2 имеет место, когда Пі ос П2 и П2 ос Пі. Задача разрешения П называется NT -трудной, если к ней полиномиально сводятся все задачи разрешения из класса NP. Задача разрешения называется NP-полной, если она лежит в классе NP и является NP-трудной. Неформально, NP-полная задача- эта самая (пеединствепная) трудоемкая задача в классе NP. Классическим справочником по NP-полным задачам является книга [55] (см. русский перевод [8]), а также продолжающаяся серия статей "The ongoing guide of NP-complete problems", которую ведет Д. Джонсон в Journal of Algorithms. В дальнейшем изложении нам понадобятся следующие полезные свойства (см. [8]), выполняющиеся для произвольных задач разрешения Пь П2, Ну.
Распознавание псевдосодержаиий
Содержательно оно означает, что недоопределенный пример V классифицируется положительно (то есть как предположительно обладающий свойством W) если он содержит в качестве подмножества какую-либо положительную гипотезу и не содержит ни одной отрицательной. Недоопределенный пример классифицируется отрицательно в противоположном случае (т.е. если он содержит отрицательную гипотезу и не содержит положительной гипотезы). Если недоопределенный пример содержит как положительные гипотезы, так и отрицательные гипотезы в качестве подмножеств, то его классификация противоречива, если не содержит ни тех и не других - то его классификация неопределенна. Логическая конструкция ДСМ-метода допускает возможность итеративного пополнения множества положительных и отрицательных примеров результатами классификации. Этот процесс, описываемый на языке бесконечнозначной логики предикатов, может продолжаться вплоть до стабилизации, т.е. шага итерации при котором новых классификаций не возникает [23]. Тем не менее в нашей работе мы ограничимся рассмотрением одного шага этого процесса, состоящего из однократного порождения гипотез с дальнейшим применением их для классификации. В силу громоздкости логических формул, с помощью которых описывается порождение гипотез и классификаций, и необходимости предварительного введения логических языков, мы не приводим их здесь, а отсылаем читателя за полными формулировками к работе [23]. В главе 2 нами будут сформулированы некоторые основные понятия ДСМ-метода на алгебраическом языке АФП.
По определению гипотез и классификации на их основе (ДСМ-метод) достаточно использовать только минимальные по вложению гипотезы. Таким образом множество минимальных гипотез является полным множеством гипотез (с помощью него можно произвести те же классификации, что и с помощью множества всех гипотез). В связи с этим встает вопрос о возможности порождения минимальных гипотез с полиномиальной задержкой (или хотя бы за полиномиальное от выхода время), как это имеет место для множества всех гипотез. Вопросы, связанные с обучением минимальным гипотезам, исследованы в статье [68, 74]. Задача о вычислительной сложности порождения минимальных гипотез оставалась до сих пор открытой.
Особое место в ДСМ-мстоде занимают обобщенные гипотезы [22, 23], в определении которых варьируется основная идея: сходство положительных примеров V как гипотетическая причина целевого свойства может тормозиться элементами отрицательных примеров, причем тормозами выступают минимальные сходства отрицательных примеров, содержащие V в качестве подмножества. Ввиду громоздкости логической формулировки обобщенного метода, мы не приводим их здесь, а отсылаем за ними читателя к работам [25, 22, 23, 24]. Формулировка обобщенного метода на языке АФП приводится в главе 2. Заметим, что обобщенная гипотеза является гипотезой в вышеуказанном смысле только если множество тормозов пусто.
Применение обобщенных гипотез основанно на более сильных допущениях о природе причинности (ее тернарной природе: причина - блокиратор - следствие) и происходит обычно при отутствии или малом количестве "обычных" (простых в терминологии [23]) гипотез описанных выше.
На основе представления о тернарной причинности в [24] предложен также ситуационный ДСМ-метод, где ситуация, в отличии от блокиратора в обобщенном методе, может содействовать причине, а не противодействовать ей. В ситуационном методе возможно наличие противоречивости в исходных данных (что может приводить к противоречивым классификациям без наличия положительных и отрицательных гипотез).
Подмножество X С М удовлетворяет импликации А В, если из Л С. X следует ВСХ. Любое множество импликаций $ на множестве М определяет оператор замыкания (-)3 на М, где подмножество М замкнуто тогда и только тогда, когда это множество удовлетворяет всем импликациям из 2- Подмножество импликаций, из которого все остальные импликации контекста могут быть выведены по правилам Армстронга называется покрытием импликаций. Заметим, что 3 является покрытием импликаций контекста К. тогда и только тогда, когда система замыканий, которую задает 3, совпадает с системой замыканий контекста ЕС. О/цю из минимальных по мощности (далее будем писать просто минимальный) покрытие импликаций (минимальный базис импликаций) было приведено в [41]. Это подмножество импликаций называется базисом Дюкена-Гига, каноническим базисом или stembase в литературе. Множество посылок импликаций в каноническом базисе является в точности множеством псевдосодержаний(см. например [54]): множество Р С М называется псевдосодержанием, если Р ф Р" и Q" С Р для любого псевдосодержания Q С Р. Для множества АСМ такого, что Р А и А является содержанием или псевдосодержа-иием пересечение АПР является содержанием (см. [54]). Таким образом,
Понятия с общими содержаниями
Операции U, П и \ для списков а и 6 можно делать за время 0(\а\ + 6), используя алгоритм слияния, аналогичный алгоритму в сортировке слияниями. Следовательно, время работы выполнения строк 14 и 15 можно оценить как 0(o6jecs[i] + / [г][т]), а новое значение o6jecis[i] можно оценить как 0(/ [г][т]). Поэтому для каждого 1 і г, суммарное время выполнения строк 14 и 15 оценивается как 0{J2KJ \M\ и1ШтА\ + І- И[т-;-і]І) = 0(У [г]). Если время выполнения всех операций структуры PQ равно O(l), то время выполнения цикла на строках 16-19 можно оценить как 0 oervmmivd_6bjt,rls\o \). Для каждого г г, любой объект из массива removed_objects встречается ровно 1 раз. Поэтому суммарное время выполнения цикла на строках 16-19 можно оценить как г гО(/ [г]). Следовательно суммарное время работы алгоритма можно оценить как Y,i r ((1Л?:]) +(1 Й1)) = Х)г г (1 Н1) Осталось описать устройство структуры данных PQ. Структура данных PQ это приоритетная очередь, которая поддерживает операции: узнать минимум (get_min), удалить минимум (extract_min), а также операции - уменьшить все ключи па 1 (decrease all) и увеличить значение ключа, данного элемента на 1 (increase(а)). Если изначально все ключи принимают только целые значения от 0 до \М\, а также операции decrease_all и increase вызывается не более \М\ раз, то эту структуру данных можно реализовать так, чтобы ее инициализация занимала 0(М) времени, а все операции выполнялись за 0(1). Для этого достаточно создать массив размера 2М, элементы которого будут хранить списки, добавляемых в структуру элементов. Также для каждого, хранимого элемента нужно запоминать где он в этом массиве и соответствующем списке находится (завести вспомогательный массив для этого). Кроме того нужно завести две переменных: к Є {0,1,..., М}, которая будет равна количеству вызовов операции decrease_all() и і, которая будет равна индексу первого непустого списка. При инициализации элемент с ключом х добавляется в х-\\ список (set(a,a;) добавляет элемент а с ключом х). При вызове increase(a) нужно переложить элемент из его текущего списка в список с индексом на 1 больше текущего (список и место в списке, где находится элемент а можно узнать с помощью вспомогательного массива). Операция get_min возвращает і — к, а при вызове extract_min необходимо увеличивать і до тех пор, пока не встретится непустой список.
Алгоритм GetClosure_2(X) вычисляет Xs для произвольного подмножества признаков X С М и контекстов К і = (G\, М, її),. .., Kr = {Gr, M, Ir) за время 0{J2i i r \Ы) Задача поиска максимального (по мощности) замкнутого множества относительно операторов () и () , очевидно решается за полиномиальное время: достаточно просто проверить все объектные содержания и найти максимальное. Но в отличие от этих операторов замыкания, аналогичная задача поиска максимального общего содержания, отличного от М (на практике это может соответствовать "максимальной схожести двух контекстов") для оператора (-)s NP-иолна, как показано в следующей теореме. Утверэ/сдение 9. Задача ВХОД Два формальных контекста К\ = (G\, М, Д), К2 = (С?2, М,/2), и целое число 0 /с \М\. ВОПРОС Существует ли такое X, что X = XS,X С М п \Х\ kl Л Р-полна. Доказательство. По теореме 5 X = Xs может быть проверено за полиномиальное время, таким образом эта задала лежит в NP. Для доказательства iVP-трудности мы сведем хорошо известную iVP-полную задачу 0 минимальном покрытии (МП) к нашей. Задача МП формулируется сле дующим образом [55]: ВХОД Конечное множество S, множество его подмножеств V := {S\, S-2 Sm}, Sj, С S, и целое число к. ВОПРОС Существует ли подмножество Т С V такое, что {jXeTX = Sn\r\ k? РаССМОТрИМ ПрОИЗВОЛЬНОе КОНСЧПОе МНОЖеСТВО S = {в], S2, ,sn}, и множество его подмножеств V := {S], 5г, . , Sm}, Si С S для всех 1 г га, и целое число 0 к \Р\. Пусть М = {7711,777.2,..., т і+ітої} и G\ = { Теперь построим контекст К\ = (Gi, М, /і), где 1\ определено как: g\l\mj для j 5, если и только если Sj S{ и gjlirrij для j \S\ тогда и только тогда, когда j — \S\ ф г. Тогда покрытия S нахо дятся во взаимно однозначном соответствии с содержаниями К\, которые не содержат ни одного гаг- Є М, г \S\. Более того, для любого покрытия размера N, соответствующее содержание будет размера \Р\ — N. Теперь построим контекст К2 = {G 2, М,/2), где G-2 = {9b9l,---- 9\v\t, h определено как: для д\, Очевидно, множество всех содержаний этого контекста это в точности множество всех подмножеств множества М, которые не пересекаются с S. Следовательно существует взаимно однозначное соответствие между общими содержаниями контекстов К\ и А 2 отличными от М, и множеством всех покрытий S. Более того минимальные покрытия соответ ствуют максимальным общим содержаниям, и наоборот. Сведение доказано и его полиномиалыгость очевидна. Насколько большим может быть минимальный контекст, задающий общие содержания двух заданных контекстов? Ответ дан в следующем утверждении: Утверждение 10. Существуют два контекста К\ и Кч такие, что множество их максимальных (по включению) общих содержаний экспоненциально относительно размеров К\ и К . Доказательство. Рассмотрим конечное множество S = {si, S2,..., S3n}, и множество его подмножеств V — Uo i n-i tts3i+b S37+2}, W+i, sM+3},s3i+2, s3i+3}}. Существует ровно 3n минимальных покрытий S, поскольку для любого 0 і п — 1 подмножество {s3,;+i, S[\j+2, S3J+3} может быть покрыто только тремя способами, используя ровно 2 элемента из V. Таким образом, если построить контексты К\ и К2 как в Утверждении 9 в СООТВЄТСТВИРІ с 5І и , у этих контекстов будет Зп максимальных (по мощности) общих содержаний. D Следствие. Существуют два контекста К\ и К2 такие, что минимальное количество объектов в контексте с оператором замыкания (-)6 экспоненциально относительно размеров К\ и Ki
Приближенный подсчет числа замкнутых и незамкнутых множеств
Алгоритм распределенного обучения гипотезам был реализован на языке C++ (около 300 строк) в среде MS Visual Studio 2010 с использованием стандартной библиотеки STL.
Реализация вошла в комплекс программ встроенный в программную систему Cordiet-FCA. Структура программы распределенного обучения гипотезам имеет следующий вид: 1. 13 файле JSM_test.cpp (приложение 3.1) функция vector _mset find_shared hypotheses(const vector Context & pK, const vector Context & nK) находит все общие гипотезы наборов положительных и отрицательных контекстов рК и пК, соответственно. 2. В файле JSM_test.cpp (приложение 3.1) функция mset next_closure_JSM(const mset& X, const Contexts К) возвращает следующую гипотезу в лексикографическом порядке на объемах соответствующих формальных понятий. 3. В файле JSM_test.cpp (приложение 3.1) функция int classify(const vector mset & pH, const vector mset & nH, const mset& X) возвращает результат классификации X при использовании множества положительных гипотез рН и множества отрицательных гипотез пН. Данная функция возвращает 1, если результат классификации положителен, — 1, если результат классификации отрицателен, и 0, если классификация неопределена. В диссертационной работе приведен обзор методов поиска строгих зависимостей в данных. В 2006 году участниками конференции ICFCA в Ленсе (Lens, Франция) был составлен список наиболее важных открытых задач в АФП. Одной из них была задача о сложности распознавания псевдосодержаний, которая была решена в данной диссертационной работе и опубликована в [31] (публикации, где рассматривалась данная задача и считалась открытой: [74, 89, 90, 91, 92, 38]). Эта задача была также представлена как открытая на Дрезденской конференции по дискретной математике в 2002 году. В отличие от классического минимального базиса импликаций, для которого все известные алгоритмы построения имеют экспоненциальную оценку сложности, среднее время работы построения приближенного базиса импликаций полиномиально и оценивается как где J минимальный базис импликаций, а є - параметр точности приближенного базиса импликаций. Проведенные на реальных данных эксперименты показали, что размер приближенного базиса был значительно меньше (иногда в сотни раз). В работе было доказано, что если Р ф NP, то невозможно найти все минимальные ДСМ-гипотезы за полиномиальное от размера выхода время. Модель распределенного обучения гипотезам показала значительное сокращение количества гипотез по отношению к числу ДСМ-гипотез в стандартной постановке. Линейный по времени алгоритм вычисления оператора замыканий системы замыканий общих содержаний позволил быстро перечислять все общие гипотезы. В данной работе была доказана трудность аппроксимации индекса классической устойчивости формальных понятий (с полиномиально ограниченной относительной ошибкой). Была предложена модель вероятностного индекса устойчивости формальных понятий, которая соответствует аппроксимации классического индекса устойчивости с ограниченной абсолютной ошибкой и может быть вычислена за полиномиальное время. Проведенные эксперименты показали, что применение вероятностного индекса устойчивости, при использовании ДСМ-метода, уменьшает число пекласси-фицируемых объектов на 43% при увеличении количества ошибок классификации на « 23% (число неклассифицируемых объектов, при использовании стандартных ДСМ-гипотез 46%). Основные результаты и выводы работы: 1. Результаты, связанные с базисами импликаций: 1.1 Доказана трудноразрешимость (в терминах NP- и coNP-полноты и трудности) задач, связанных с вычислением классического минимального базиса импликаций. 1.2 Предложена модель приближенного базиса импликаций формального контекста, эффективный алгоритм его вычисления и программная реализация. 2. Результаты, связанные с минимальными гипотезами: 2.2 Предложена и экспериментально проверена модель распределенного обучения гипотезам - имнликативных зависимостей для задачи машинного обучения. 2.3 Предложен эффективный алгоритм поиска всех гипотез но распределенной обучающей выборке и его программная реализация. 3. Результаты, связанные с индексом устойчивости формальных понятий и гипотез: 3.1 Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий - индекс вероятностной устойчивости. 3.2 Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.
Похожие диссертации на Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств
-
-
-
