автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств

На правах рукописи

Бабин Михаил Александрович

Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

О 4 ОКТ 2012

Москва — 2012

005052443

Работа выполнена в Национальном исследовательском университете «Высшая школа экономики» (НИУ ВШЭ).

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук Кузнецов Сергей Олегович

доктор физико-математических наук, профессор,

профессор кафедры математики, логики и интеллектуальных систем Института лингвистики РГГУ

Аншаков Олег Михайлович

кандидат физико-математических наук, старший научный сотрудник отдела теоретических и прикладных проблем информатики ВИНИТИ РАН

Виноградов Дмитрий Вячеславович

Институт проблем передачи информации им. А.А. Харкевича (ИППИ) РАН

Защита состоится "29" октября 2012 г. в 14.00 на заседании диссертационного совета Д 212.048.09 в Национальном исследовательском университете «Высшая школа экономики» (НИУ ВШЭ) по адресу: 105187, Москва, ул. Кирпичная, д. 33., ауд. 505

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики».

Автореферат разослан сентября 2012 г.

Учёный секретарь диссертационного совета доктор технических наук В.А. Фомичев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы. Стремительный рост объема данных разной природы, наблюдающийся в последние десятилетия, приводит к необходимости разработки эффективных методов их автоматического и интерактивного анализа. Одной из распространенных математических моделей, позволяющих описывать методы и алгоритмы анализа данных, является анализ формальных понятий.

Анализ формальных понятий (АФП) является ветвью прикладной алгебраической теории решеток, широко используемой для описания методов анализа данных. АФП предлагает средства моделирования онтологий и так-сономий предметных областей на основе решеток понятий, а также модели точных и приближенных зависимостей в данных.

Для многих ключевых задач анализа формальных понятий до сих пор неизвестны эффективные алгоритмы и какие-либо теоретические оценки их сложности. Основной целью большинства существующих исследований является анализ данных на основе методов АФП, в то время как эффективные алгоритмы и вычислительная сложность этих методов уходит на второй план. Примерами актуальных задач являются:

• Модели импликативных зависимостей, позволяющие более сжатое представление и эффективную алгоритмическую реализацию

• Эффективные алгоритмы порождения приближенных базисов импликаций, множества минимальных ДСМ-гипотез

• Эффективные алгоритмы распознавания псевдосодержаний, задающих оптимальный базис импликаций

• Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостей

Так например, эффективные алгоритмы порождения и сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей (импликаций) была одной из основных открытых задач АФП на протяжении многих лет (список открытых задач АФП [II. Рпбэ 2006] задачи 2,8,9).

Объектом исследования являются модели импликативных зависимостей в данных и их эффективная алгоритмическая реализация.

Целью исследования является разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, а также решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.

Методы исследования. В диссертации применяются методы анализа формальных понятий, дискретной оптимизации, вероятностных алгоритмов и теории вычислительной сложности алгоритмов.

Научная новизна. В диссертации получены следующие основные новые научные результаты, которые выносятся на защиту:

1. Доказана трудноразрешимое^ задач, связанных с вычислением классического минимального базиса импликаций.

2. Предложена новая модель приближенного базиса импликаций формального контекста, алгоритм его вычисления и эффективная программная реализация.

3. Доказана трудноразрешимое^ вычисления минимальных гипотез в стандартной постановке

4. Предложена и экспериментально проверена модель распределенного обучения гипотезам - импликативным зависимостям для задачи машинного обучения.

5. Предложен линейный по времени алгоритм поиска всех гипотез по распределенной обучающей выборке и его программная реализация.

6. Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий - вероятностный индекс устойчивости.

7. Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.

8. Решены давно сформулированные и остававшиеся открытыми задачи создания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний.

9. Показана полиномиальная эквивалентность задачи перечисления минимальных гипотез и задачи дуализации монотонной булевой функции на решетке.

10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделении прикладной математики и информатики НИУ ВШЭ комплекс программ.

Теоретическая значимость подтверждается тем, что были предложены новые модели импликативных зависимостей, а также средства их оценивания, показана их адекватность практическим задачам и возможность эффективной алгоритмической реализации. Были решены открытые теоретические задачи прикладной теории решеток и анализа данных.

Практическая значимость подтверждена экспериментами по построению приближенного базиса импликаций, распределенному обучению гипотезам и вычислению вероятностной устойчивости. Эти эксперименты показали значительные улучшения во времени вычисления и в качестве полученных результатов. Был разработан комплекс программ, в который вошли алгоритмы, опубликованные в данной работе.

Достоверность результатов подтверждена строгими математическими доказательствами теоретических утверждений, экспериментальной проверкой

результатов численных расчетов и практической эффективности программных реализаций.

АПРОБАЦИЯ РАБОТЫ Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

1. 8-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Агадир, Марокко, 2010.

2. 7-ой международной конференции по решеткам понятий и их приложениям (7th International Confere6nce on Concept Lattices and Their Applications), Севилья, Испания, 2010. [Награда за лучшую статью]

3. 9-ой международной конференции по анализу формальных понятий (9th International Conference on Formal Concept Analysis), Никосия, Кипр, 2011.

4. 10-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Лёвен, Бельгия, 2012.

Публикации. Основные результаты работы изложены в б научных статьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК.

Структура и объем диссертации. Диссертация состоит из пяти глав, заключения, списка литературы и приложений. Общий объем основного текста работы — 133 страницы. Список литературы включает 100 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы, сформулированы цели и задачи исследования, научная новизна, теоретическая и практическая значимость полученных результатов, основные положения, выносимые на защиту, а также приведены данные о структуре и объеме диссертации.

В первой главе описываются основные результаты и определения используемые в диссертации.

Ниже приводятся основные определения анализа формальных понятий, используемые в диссертационной работе.

Пусть G и М - конечные множества, называющиеся множествами объектов и признаков соответственно. Пусть I - бинарное отношение I С G х М между объектами и признаками: для д € G,m е М,д1т выполнено тогда и только тогда, когда объект д обладает признаком т. Тройка К = (G,M,I)

называется (формальным) контекстом. Если А С G, В С M - произвольные подмножества, то следующая пара операторов, называемых операторами Гэлуа,

А' = {m є M I glm V5 є А}

В'= {g Є G І glm Vm Є В}

задает соответствие Галуа между частично упорядоченными множествами (2g,ç)h(2m,Ç).

Пара (А, В), где А С G, В С М, А! = В, и В' = А (следовательно, А" = А и В" = В), называется (формальным) понятием (контекста К) с объемом А и содержанием В.

Оператор (•)" является оператором замыкания, т.е. он идемпотентен (X"" = X"), экстенсивен (X С X") и монотонен {X С Y => X" С Y"). Множества A Q G,B С M называются замкнутыми если А" = А и В" = В. Очевидно, объемы и содержания (и только они) замкнуты. Множество всех замкнутых множеств относительно данного оператора замыкания называется системой замыканий.

Основная теорема анализа формальных понятий (см. [Ganter В., Wille R., 1999]) говорит, что множество понятий контекста К= (G,M,I) образует полную решетку со следующими операциями инфинума (inf) и супремума (sup) соответственно:

Понятие (А, В) называется супремум-неразложимым, если оно не может быть представлено как супремум каких-то других понятий.

Множество признаков В следует из множества признаков А, или выполнена импликация А -> В, если все объекты из б, которые обладают всеми признаками из А, также обладают всеми признаками из В, т.е. А' С В'.

Импликации подчиняются правилам Армстронга:

Во второй главе приводятся основные результаты диссертации, связанные с оптимальными базисами импликаций формального контекста.

В разделе 2.1 приводятся основные определения, связанные с минимальными базисами импликаций, такие как определения псевдосодержаний, существенных содержаний и квазизамкнутых множеств.

Подмножество X С М удовлетворяет импликации А —> В, если из А С X следует В С I. Любое множество импликаций 3 на множестве М определяет оператор замыкания (•)' на М, где подмножество М замкнуто

А-> В Л-»Б,ВиС-»£>

А-+А' AUC->B' AUC-+D

тогда и только тогда, когда это множество удовлетворяет всем импликациям из 3- Набор импликаций, из которого все остальные импликации могут быть выведены по правилам Армстронга, называется базисом импликаций. Другое, эквивалентное определение базиса импликаций это совпадение операторов замыкания (•)" и (•)'. Одним из минимальных базисов импликаций является базис Дюкена-Гига (канонический базис). Множество посылок импликаций в каноническом базисе является в точности множеством псевдосодержаний. Множество Р С М называется псевдосодержанием, если Р ф Р" и Q" С Р для любого псевдосодержания Q С Р. Подмножество Q С М ква-зизамкнуто, если его пересечение с любым замкнутым множеством замкнуто. Множество квазизамкнутых множеств образует систему замыканий. Множество АС. М называется существенным содержанием (существенно замкнутое подмножество признаков), если существует псевдосодержание Р С М такое, что Р" = А. Множество существенных содержаний является множеством заключений импликаций из минимального базиса импликаций (любого минимального базиса импликаций).

В разделе 2.2 описывается структура минимальных базисов импликаций. Базис импликаций Д минимален тогда и только тогда, когда для любой импликации А —> В € 0 квазизамыкание посылки А является псевдосодержанием и у различных импликаций квазизамыкания посылок различны.

В разделе 2.3 приводится ранее известный результат о полиномиальной эквивалентности задачи поиска минимального базиса импликаций формального контекста и задачи поиска минимального покрытия функциональных зависимостей реляционной базы данных.

В разделе 2.4 рассматривается задача:

Задача 1. Распознавание псевдосодержания (PI)

ВХОД: Формальный контекст К = (G, М, I) и подмножество признаков РСМ.

ВОПРОС: Является ли Р псевдосодержанием контекста К?

и доказывается Теорема 1. Задача PI coNР-трудна.

В разделах 2.5 и 2.6 приводятся несколько простых следствий Теоремы 1. В частности доказывается, что посылки минимального базиса импликаций не могут быть перечислены в обратном лектическом порядке (лексикографическом порядке на характеристических векторах множеств) с полиномиальной задержкой, если Р ф coNP. Также доказывается, что задача распознавания существенных содержаний NP-полна.

В разделе 2.7 рассматривается задача эквивалентности систем замыканий заданных контекстом и набором импликаций, в котором у всех импликаций посылки по мощности не больше 2. Доказывается, что такая задача не проще задачи, в которой нет ограничения на мощности посылок.

В разделе 2.8 рассматривается новая модель импликативных зависимостей - приближенный базис импликаций:

Определение 1. Набор импликаций Jc называется приближенным базисом формального контекста К = (G, М, I), если для случайно и равномерно выбранного подмножества X С М выполняется условие

Pr(X" = XJ') > 1 - е, 0 < е < 1.

Таким образом 1-е соответствует точности приближения. Преимущества, предложенной модели по сравнению с точным базисом:

• Существенно меньшее количество импликаций

• Существенно более быстрое время построения, которое линейно от е-1

• Высокая точность приближения (1 — е)

Приведем псевдокод алгоритма построения приближенного базиса импликаций формального контекста К = (G, М,/), основанного на результатах [Д. Англуин и др. 1992] об обучении Хорновской Конъюнктивной Нормальной Формы (КНФ) при помощи двух оракулов.

updatebase(k, J, X) 1 for each Л -» В e J

2 do if A<£X And (А П X)" ф А П X

3 then заменить в J импликацию A В

4 наАпХ^(ЛпХ)"

5 return J

6 J <r- JKJ{X±-X")

7 return J

ApproximateImplicationBase(K, N)

1 7 0

2 for i 1 to N

3 do выбрать случайное замкнутое множество X базиса J

4 if X" ф X

5 then J UpdateBase(K, J, X)

6 return J

Данный алгоритм использует следующий метод генерации случайного множества, замкнутого в базисе J:

GenerateRandomClosedSet (J)

1 X random subset of M

2 X LinClosure(J, X)

3 return X

Здесь LinClosure - линейный алгоритм вычисления замыкания в базисе импликаций [Д. Мейер 1987]. Доказывается теорема:

Теорема 2. Математическое ожидание времени работы алгоритма ApproximateImplicationBa.se, до достижения точности 1 — е (0 < е < 1) для контекста К = (в,М,1), равно 0(\Л\М\ • (\в\\М\ + \Jl\M\) ■ е-1), где 3 - минимальный базис импликаций.

В разделе 2.8.1 приводятся результаты компьютерных экспериментов приближенного базиса импликаций на реальных данных.

база данных |G| \M\ 1Л1 И Ш Pr t ta

Chess 3197 39 lb 43,1 0,9988 595

Zoo 101 28 43 3,3 0,9999 1,853

Р.-Ор. P. 90 2b 8b b,U 0,9989 2,06

Grav /0/ 4/3 b3 233,4 0,9999 3129

Grav a /0/ 1Ь6 39 286,6 0,9999 92,05

Таблица 0.1. Результаты вычисления приближенного базиса.

• J€ - приближенный базис импликаций

• J - точный базис импликаций

• Рт - оценка вероятности Pr(X" = XJt) того, что для случайного подмножества X С М замыкания совпадают

• t - время построения точного базиса алгоритмом Гантера

• ta - время построения приближенного базиса

В третьей главе приводятся результаты связанные с общими содержаниями формальных контекстов.

В разделах 3.1-3.3 показывается связь базиса импликаций с общими содержаниями и приводится общий алгоритм поиска минимального базиса импликаций. Пусть даны два формальных контекста с общим множеством признаков: Ki = (Gi,M,I\) с базисом импликаций (не обязательно минимальным) и контекст Кг = (G2.M,/2) с базисом импликаций Зг- Очевидно, что множество их общих содержаний является системой замыканий. Поэтому мы можем рассмотреть контекст К = (G,M,I), объектные содержания, которого будут неразложимыми элементами системы замыканий общих содержаний. Будем называть контекст К, контекстом общих содержаний. Можно предложить следующий общий алгоритм построения минимального базиса импликаций:

flndmlnbase(k = (g, м, /))

1 Представить контекст К множеством контекстов Ki, Кг,..., К*, для которых К будет являться контекстом общих содержаний

2 Для каждого контекста Ki найти минимальный базис импликаций 0».

3 3<-3iU32U...u;fc

4 3 Minimize(J)

5 return 3

В разделе 3.4 показывается, что описанный в статье [Ф. Дистель и др. 2011] алгоритм поиска собственных посылок, является частным случаем приведенного общего алгоритма поиска базиса импликаций.

В разделе 3.5 описывается модель сходства формальных понятий - интенсиональная связность.

В разделе 3.6 исследуются задачи, связанные с общими содержаниями формальных контекстов. Предлагается алгоритм вычисления оператора замыканий общих содержаний (-)5 контекстов К1 = (С?1, М, 1\),..., Кг =

(а, М,/г):

СЕТСЬОЗШ1Е(Х)

1 answer X

2 for i 1 to r

3 do remove all rows from I[i] that do not contain X

4 for i 1 to r

5 do for m f- 1 to \M\

6 do if not answer[m]

7 then if /[¿][j'][m] = TRUE for all 1 < j < |Gj|

8 then answer[m] true

9 push m in shared-attributes

10 else for each 1 <j< |Gj| such that not /[¿][?'][m]

11 do push {j, i) in not-in[m]

12 counter[i][m] counter[i][m] + 1

13 while shared-attributes not empty

14 do pop m from shared-attributes

15 while not-in[m] not empty

16 do pop (object-index, context-index) from not-in[m]

17 for i ^— 1 to \M\

18 do if not I\i]\context-index][object-index]

19 then counter[context-index][i] •<—

counter[context-index][i] —1

20 if counter\context-index][i] < 0

and not answer[i]

21 then answer[i] = true

22 push i in shared-attributes

23 return answer

Здесь /[г] - это бинарная матрица, задающая отношение /¿, counter[i][m] равно количеству объектов д из G; для которых glim не выполнено, shared-attributes и not-in[m] могут быть реализованы как стеки или как любые другие структуры данных, поддерживающие операции "вытащить"(pop) любой объект и "вставить"(ри5Ь) любой объект за время 0(1).

Доказывается, что время работы этого алгоритма линейно от размера входа:

Теорема 3. Алгоритм GetClosure(X) вычисляет Xs для произвольного подмножества признаков X С М и контекстов Ki = (Gb Af, /,),..., Kr = (Gr, M, Ir) за время 0(\M\ Ех<{<г |G«|).

Также рассматривается случай, когда все контексты заданы списками признаков своих объектов (а не матрицами, как в предыдущем алгоритме) и приводится алгоритм вычисления оператора замыканий общих содержаний за линейное от входа время.

Теорема 4. Алгоритм GetClosure_2(X) вычисляет Xs для произвольного подмножества признаков X С М и контекстов Ki = (Gu М, h),..., Кг = {Gr, М,1Г) за время C(Ei<i<r

Используя алгоритм GetClosure(-) (GetClosure_2(•)) в качестве оракула, можно перечислять все общие содержания с полиномиальной задержкой, применяя стандартные алгоритмы АФП (такие как Norris, Next Closure, Close-by-One).

В разделе 3.8 показывается как сцепления формальных контекстов могут быть представлены через общие содержания.

В четвертой главе рассматриваются вопросы связанные с обучением гипотезам!

Пусть признаки из М описывают "структуру"объектов, a w - целевой признак, отличный от всех признаков из М. Например, в фармакологических приложениях структурные признаки могут соответствовать подграфам молекулярных графов химических соединений, а целевой признак - биологическим свойствам этих соединений.

Входные данные для контекста обучения могут быть представлены множествами положительных, отрицательных и неопределенных примеров. Положительные примеры (или (+)-примеры) - это объекты, о которых известно, что они обладают признаком w, а отрицательные примеры (или (—)-примеры) - это объекты, о которых известно, что они не обладают признаком w

Определение 2. Рассмотрим положительный контекст К+ = (G+, М,Х+) и отрицательный контекст К_ = (G_,M,Z_). Контекст К± = (G+ U G-,M U {w},I+ U U G+ х {го}) называется контекстом обучения. Оператор Голу а для этого контекста обозначается как ±.

Определение 3. Подмножество Н С М называется положительной гипотезой (или (+)-гипотезой) контекста обучения К± если Н - содержание контекста К+ и Н не является подмножеством ни одного содержания контекста К_.

Аналогично определяются отрицательные гипотезы (или (-)-гипотезы). Содержание контекста К+, которое принадлежит хотя бы одному отрицательному примеру, называется фальсифицированным (+)-обобщением.

Помимо положительных и отрицательных примеров обычно имеются объекты, для которых значение целевого признака неизвестно. В работе [В. Финн 1991] эти объекты называются неопределенными примерами, они могут

быть заданы контекстом Кт := (GT,M,IT), соответствующий оператор Галуа обозначается через (-)т.

Гипотезы могут быть использованы для классификации неопределенных примеров: если содержание

дт:={теМ\ (д,т) е 1Т)

объекта д 6 GT содержит положительную и ни одной отрицательной гипотезы, то дт классифицируется положительно. Отрицательные классификации определяются аналогично. Если дт содержит гипотезы обоих знаков, то классификация противоречива. Если дт вообще не содержит гипотез, то классификация не определена. В этом случае можно применять методы другого типа, например, основанные на статистических подходах.

В работе [С. Кузнецов и Б. Гантер, 2000] отмечалось, что для классификации можно ограничиться только минимальными (по вложению С) гипотезами, положительными и отрицательными, поскольку объектное содержание содержит положительную (отрицательную) гипотезу тогда и только тогда, когда оно содержит некоторую минимальную гипотезу.

В разделах 4.1-4.2 приводится теоретико-решеточная интерпретация гипотез и показывается эквивалентность задач поиска минимальных гипотез и дуализации монотонной булевой функции на решетке. Также, показывается трудноразрешимость задачи поиска минимальных гипотез.

Задача 2. Перечисление минимальных гипотез (МНЕ)

ВХОД: Положительные и отрицательные контексты К+ =

(G+,M,X+),K_ = (G_,M,I_)

ВЫХОД: Все минимальные гипотезы контекста К±.

Теорема 5. Минимальные гипотезы не могут быть перечислены за полиномиальное от выхода время, если Р ф NP

В разделе 4.3 описывается метод распределенного обучения гипотезам. Часто бывает ситуация, когда ДСМ-гипотез слишком много (даже минимальных), что затрудняет обучение гипотезам и последующую классификацию. Пусть есть несколько обучающих контекстов с одинаковым множеством признаков: ... ,К±. В качестве гипотез будем использовать только те гипотезы, которые являются гипотезами в каждом из контекстов. Формально:

SharedHypotheses(K±1, К±2,... ,K±fc)

1 С ч- AllIntents(GetClosure(-),K+1,K+2, ... ,К+*)

2 Н <- {X \ Х € С, X <£Y VY € К-1 U К_2 U ... U К_*}

3 MlNIMIZE(tf)

4 return Я

Где GetClosure — оператор замыкания общих содержаний, a Alllntents -любой алгоритм АФП поиска всех замкнутых множеств, использующий оператор замыканий (например Next Closure)

Условиями применения данной модели обучения могут служить следующие ситуации:

1. Несколько исследовательских групп проводят один и тот же эксперимент

2. Несколько наборов данных с одинаковым набором признаков описывают одну и ту же задачу, но объекты отличаются по своей природе.

3. Общих содержаний намного меньше, чем содержаний в каждом из положительных контекстов.

Ниже приводятся результаты экспериментов по классификации токсичности химических соединений ДСМ-методом с использованием общих гипотез:

support Err.* Err. Mis.' Mis.

30 4.6 10.0 6Ь.У Ь4,б Ù 24,1)

20 12,/ 12,1 3b,b 45,8 Ь2 134,0

10 14,b іи,ь 18,3 45,4 104 270,0

Ъ 16,0 10,4 1Ь,1 45,8 151 389,75

• Err." - процент ошибочной классификации при использовании общих гипотез

• Err. - процент ошибочной классификации при использовании классических гипотез

• Mis." - процент неклассифицируемых объктов при использовании общих гипотез

• Mis. - процент неклассифицируемых объктов при использовании классических гипотез

• фНур." - количество минимальных общих гипотез

• Hyp. - среднее количество минимальных классических гипотез по 4 базам данных.

Таблица 0.2. Результаты классификации токсичности молекул.

В разделе 4.4 даются основные определения устойчивости формальных понятий и гипотез.

Определение 4. Пусть К = (G, M, I) - формальный контекст и (Л, В) - формальное понятие контекста К. Индекс (интенсиональной) устойчивости ain(A, В), или сг{П(А), определяется следующим образом:

„ (л m - \с^А\с' = в\

ain(A, В) ---

Индекс экстенсиональной устойчивости определяется двойственным образом: (7а(Л,В) = оех{В) = I^Jg, . Обычно, когда это не приводит к неправильному пониманию, индексы ¿„ и ^ опускаются.

В разделе 4.5 исследуются задачи приближенного подсчета числа замкнутых и незамкнутых множеств. В частности рассматривается задача:

Задача 3. Количество незамкнутых множеств (#N0) ВХОД: А Формальный контекст К = (С?, М, I) ВЫХОД: Количество множеств Л с М таких, что А" ф А

Доказывается, что эта задача не может быть решена за полиномиальное время, если ЫР ф ЯР. Простым следствием этого результата является факт, что, если ТУР ф ЯР, то не существует полиномиального алгоритма для приближенного вычисления устойчивости формального понятия с полиномиально ограниченной относительной ошибкой.

В разделе 4.6 описывается вероятностная модель устойчивости формального понятия.

Определим модель вероятностной устойчивости формального понятия, следующим образом:

Определение 5 (Вероятностный индекс устойчивости). <7дг(Л) =

£(,4) _ независимые и одинаково распределенные случайные величины, определяемые как:

когда X С М выбрано случайно и равномерно

Вероятностный индекс устойчивости можно вычислять методом Монте-Карло.

Утверждение 1. Метод Монте-Карло аппроксимирует о(А) с вероятностью не меньше 1 — 5 и абсолютной погрешностью є при условии, что

В разделе 4.7 приводится анализ вычисления вероятностной устойчивости. Топ устойчивых понятий находится, используюя следующий несложный алгоритм:

TopStableConcepts(K, 7о)

1 answer •<— 0

2 for каждого понятия С = (А, А') контекста К

3 do if approxStability(A) > ag

4 then answer <— answer U{(A, A')}

5 return answer

В разделе 4.8 приводятся результаты экспериментов с данными по токсичности химических соединений, используя устойчивые гипотезы. В данном тестировании для классификации выбирались только устойчивые гипотезы. Гипотеза считалась устойчивой, если ее индекс вероятностной устойчивости (750 в соответствующем контексте (положительном, для положительной гипотезы и отрицательном, для отрицательной гипотезы) больше заданного порога

если X" — А; (замыкание случайного подмножества совпало с А) если X" ф А," (.замыкание случайного подмножества не совпало с А)

0.65.

support Err.* Err. Mis.* Mis.

30 31,0 10,0 49.7 54,6 9.8 24,0

20 10,У 12,1 44.6 45,8 79,7 134,0

10 12,Ь 10, Ь 34.Ь 4Ъ,4 265,7b 270,0

Ь 12,8 10,4 31.9 4Ь,8 393, Ь 389,75

• Err.* - процент ошибочной классификации при использовании устойчивых гипотез с <jn > 0,65

• Err. - процент ошибочной классификации при использовании классических гипотез

• Mis.* - процент неклассифицируемых объектов при использовании устойчивых гипотез с UN > 0,65

• Mis. - процент неклассифицируемых объектов при использовании классических гипотез

• фНур.* - среднее количество минимальных устойчивых гипотез по 4 базам данных

• фНур. - среднее количество минимальных классических гипотез по 4 базам данных

Таблица 0.3. Результаты классификации токсичности молекул.

В пятой главе приводится описание системы Cordiet-FCA и вошедшего в нее комплекса программ, реализующего алгоритмы, описанные в диссертации. Система Cordiet-FCA разрабатывается отделением прикладной математики и информатики НИУ ВШЭ (ОПМИ). На основе предложенных моделей и алгоритмов, описанных в разделах 2.8, 3.4, 4.3 и 4.6, был разработан комплекс программ вошедший в систему Cordiet-FCA.

В разделе 5.2 описывается структура программы построения и тестирования базисов импликаций:

Алгоритмы построения и тестирования базисов импликаций были реализованы на языке С++ (около 1000 строк кода).

Эти реализации вошли в комплекс программ, встроенный в программную систему Cordiet-FCA и могут быть использованы для построения приближенного базиса импликаций.

Структура программы построения и тестирования базисов импликаций имеет следующий вид:

1. В файлах mset.h и mset.cpp (приложение 1.1) реализованы структуры и функции для работы с множествами, представленными списками элементов.

2. В файлах implications.h и implications.срр (приложение 1.2) реализованы структуры и функции для работы с импликациями. Функция lin_closure(const std::vector<lmplication>& implications, const mset& X) вычисляет замыкание множества X в базисе implications, используя алгоритм linclosure [Д. Мейер 1987]

3. В файлах context.h и context.cpp (приложение 1.3) реализован класс Context для работы с формальными разреженными контекстами.

4. В файлах min_transversals.h и min_transversal.cpp (приложение 1.4) реализован алгоритм поиска минимальных трансверсалей гиперграфа из работы [Д. Каввадиас и др. 2005], который используется для поиска минимальных генераторов и собственных посылок.

5. В файлах angluin.h и angluin.cpp (приложение 1.5) реализован алгоритм поиска приближенного базиса импликаций. Функция std::vector<lmplication> get_approximate_base(const sparse_context::Context& К, int no_steps) возвращает приближенный базис импликация контекста К, после no_steps шагов.

6. В файлах proper_premise.h и proper_premise.cpp (приложение 1.6) реализован алгоритм поиска собственных посылок из работы [Д. Боркманн и др. 2011].

В разделе 5.3 описывается программная реализация алгоритма вычисления оператора замыкания общих содержаний

Были реализованы две версии алгоритма вычисления оператора замыкания общих содержаний: для случая, когда контекст задан бинарной матрицей и случая, когда контекст задан списками признаков.

Оба алгоритма были реализованы на языке С++ (около 170 строк) в среде MS Visual Studio 2010 с использованием стандартной библиотеки STL.

Реализация вошла в комплекс программ, встроенный в программную систему Cordiet-FCA и может быть использована для анализа сходства больших динамических массивов данных.

Структура программы вычисления оператора замыканий общих содержаний имеет следующий вид:

1. В файле shared_closure.cpp (приложение 2.1) функция mset closure(const std::vector<sparse_context::Context>& К, const mset& X) вычисляет оператор замыкания общих содержаний для случая когда контексты заданы списками признаков.

2. В файлах shared_closure.h и shared_closure.cpp (приложение 2.1) реализована структура данных PQ (специальная приоритетная очередь с поддержкой дополнительный операций), используемая алгоритмом GetClosure_ 2.

В разделе 5.4 описывается программная реализация распределенного обучения гипотезам.

Алгоритм распределенного обучения гипотезам был реализован на языке С++ (около 300 строк) в среде MS Visual Studio 2010 с использованием стандартной библиотеки STL.

Реализация вошла в комплекс программ, встроенный в программную систему Cordiet-FCA.

Структура программы распределенного обучения гипотезам имеет следующий вид:

1. В файле JSM_test.cpp (приложение 2.1) функция vector<mset> find_shared_hypotheses(const vector<Context>& рК, const vector<Context>& пК) находит все общие гипотезы наборов положительных и отрицательных контекстов рК и пК, соответственно.

2. В файле JSM_test.cpp (приложение 2.1) функция mset next_closure_JSM(const mset& X, const Context^ К) возвращает следующую гипотезу в лексикографическом порядке на объемах соответствующих формальных понятий.

3. В файле JSM_test.cpp (приложение 2.1) функция int classify(const vector<mset>& pH, const vector<mset>& nH, const mset& X) возвращает результат классификации X при использовании множества положительных гипотез pH и множества отрицательных гипотез пН. Данная функция возвращает 1, если результат классификации положителен, —1, если результат классификации отрицателен, и 0, если классификация неопределена.

В заключении приведены основные результаты и выводы диссертации. В отличие от классического минимального базиса импликаций, для которого все известные алгоритмы построения имеют экспоненциальную оценку сложности, среднее время работы построения приближенного базиса импликаций полиномиально и оценивается как 0(\J\\M\ • (|G||M| + |*Я|М|) - е-1), где J - минимальный базис импликаций, а £ - параметр точности приближенного базиса импликаций. Проведенные на реальных данных эксперименты показали, что размер приближенного базиса был значительно меньше (иногда в сотни раз).

В работе было доказано, что если Р ф NP, то невозможно найти все минимальные ДСМ-гипотезы за полиномиальное от размера выхода время. Модель распределенного обучения гипотезам показала значительное сокращение количества гипотез по отношению к числу ДСМ-гипотез в стандартной постановке. Линейный по времени алгоритм вычисления оператора замыканий системы замыканий общих содержаний позволил быстро перечислять все общие гипотезы.

В данной работе была доказана трудность аппроксимации индекса классической устойчивости формальных понятий (с полиномиально ограниченной относительной ошибкой). Была предложена модель вероятностного индекса устойчивости формальных понятий, которая соответствует аппроксимации классического индекса устойчивости с ограниченной абсолютной ошибкой

и может быть вычислена за полиномиальное время. Проведенные эксперименты показали, что применение вероятностного индекса устойчивости, при использовании ДСМ-метода, уменьшает число неклассифицируемых объектов на и 43% при увеличении количества ошибок классификации на ка 23% (число неклассифицируемых объектов, при использовании стандартных ДСМ-гипотез т 46%).

Основное содержание диссертационной работы изложено в следующих публикациях:

Публикации в журналах, входящих в перечень ВАК

1. Бабин М.А. и Кузнецов С.О. О теоретико-решеточной интерпретации задач поиска гипотез и зависимостей //Научно-техническая информация. Серия: Информационные процессы и системы, №10, 2011, С. 18-22, 0.72 п.л. (вклад автора 0,6 п.л.)

2. Бабин М.А. и Кузнецов С.О. Связи между решетками понятий и сложность их вычисления // Труды МФТИ, том 4 №2(14), 2012, С. 73-80, 0.7 п.л (вклад автора 0,6 п.л.)

Другие публикации в рецензируемых научных изданиях и журналах

1. Babin М. A. and Kuznetsov S.O. On Links between Concept Lattices and Related Complexity Problems // Lecture Notes in Artificial Intelligence, № 5986, 2010, C. 138-144, Springer 0.54 п.л. (вклад автора 0,4 п.л.)

2. Babin М. A. and Kuznetsov S.O. Recognizing Pseudo-Intent is coNP-complete // CLA 2010: Proceedings of the 7th International Conference on Concept Lattices and Their Applications, C. 294-301, 0.6 п.л. (вклад автора 0,5 п.л.)

3. Babin М. A. and Kuznetsov S.O. Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices // Lecture Notes in Artificial Intelligence, № 6628, 2011, C. 42^18, Springer 0.51 п.л. (вклад автора 0,4 п.л.)

4. Babin М. A. and Kuznetsov S.O. Approximating Concept Stability // Lecture Notes in Artificial Intelligence, № 7278, 2012, C. 7-15, Springer 0.62 п.л. (вклад автора 0,5 п.л.)

Лицензия ЛР N5 020832 от 15 октября 1993 г. Подписано в печать сентября 2012 г. Формат 60 х 84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1 Тираж 100 экз. Заказ N9

Типография издательства Национального исследовательского университета «Высшая

экономики», 125319, г. Москва, Кочновский проезд, д.З

Введение

1 Построение зависимостей в данных с помощью решеток замкнутых множеств: основные понятия и состояние предметной области

1.1 Основные определения.

1.1.1 Частично упорядоченные множества и решетки

1.1.2 Анализ формальных понятий.

1.1.3 Теория алгоритмов и вычислительная сложность

1.2 Модели зависимостей и их вычисление

1.3 Минимальная модель знаний о предметной области: минимальный базис импликаций.

1.4 Задачи и алгоритмы построения гипотез

2 Базисы импликаций и функциональных зависимостей

2.1 Квазизамкнутые множества и псевдосодержания.

2.2 Структура минимальных базисов импликаций.

2.3 Функциональные зависимости и импликации.

2.4 Распознавание псевдосодержапий.

2.5 Лектически максимальные псевдосодержания и перечисление максимальных псевдосодсржаний.

2.6 Распознавание существенных содержаний.

2.6.1 Посылка импликации из минимального базиса

2.7 Базис импликаций с двухэлементными посылками.

2.8 Приближенный базис импликаций.

2.8.1 Результаты экспериментов.

3 Базисы импликаций и общие содержания

3.1 Связь базиса импликаций с общими содержаниями

3.2 Общий метод поиска минимального базиса импликаций через общие содержания.

3.2.1 Поиск собственных посылок через общие содержания

3.3 Интенсионально связанные понятия.

3.4 Понятия с общими содержаниями.

3.5 Сцепления и общие содержания

4 Обучение гипотезам

4.1 Теоретико-решеточная интерпретация гипотез и классификации

4.2 Перечисление гипотез и дуализация монотонных булевых функций па решетках.

4.3 Распределенное обучение гипотезам.

4.4 Устойчивость понятий и гипотез.

4.5 Приближенный подсчет числа замкнутых и незамкнутых множеств.

4.6 Индекс вероятностной устойчивости.

4.7 Анализ результатов вычислений индекса вероятностной устойчивости

4.8 Устойчивые гипотезы: Результаты экспериментов с данными по токсичности химических соединений.

5 Комплекс программ

5.1 Программный комплекс Cordiet

5.2 Программная реализация построения базисов импликаций

5.3 Программная реализация алгоритма вычисления оператора замыкания общих содержаний

5.4 Программная реализация распределенного обучения гипотезам

Актуальность работы. Стремительный рост объема данных разной природы, наблюдающийся в последние десятилетия, приводит к необходимости разработки эффективных методов их автоматического и интерактивного анализа. Одной из распространенных математических моделей, позволяющих описывать методы и алгоритмы анализа данных, является анализ формальных понятий.

Анализ формальных понятий (АФП) является ветвью прикладной алгебраической теории решеток, широко используемой для описания методов анализа данных. АФП предлагает средства моделирования онтологий и таксономий предметных областей на основе решеток понятий, а также модели точных и приближенных зависимостей в данных.

Для многих ключевых задач анализа формальных понятий до сих пор неизвестны эффективные алгоритмы и какие-либо теоретические оценки их сложности. Основной целью большинства существующих исследований является анализ данных на основе методов АФП, в то время как эффективные алгоритмы и вычислительная сложность этих методов уходит на второй план. Примерами актуальных задач являются:

• Модели импликативных зависимостей, позволяющие более сжатое представление и эффективную алгоритмическую реализацию

• Эффективные алгоритмы порождения приближенных базисов импликаций, множества минимальных ДСМ-гипотез

• Эффективные алгоритмы распознавания псевдосодержаний, задающих оптимальный базис импликаций

• Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостей

Так например, сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей (импликаций) была одной из основных открытых задач АФГ1 на протяжении многих лет (список открытых задач АФГТ [89] задачи 2,8,9).

Объектом исследования является модель импликативных зависимостей данных и ее эффективная алгоритмическая реализация.

Целью исследования является разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, а также решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.

Методы исследования. В диссертации применяются методы анализа формальных понятий, дискретной оптимизации, вероятностных алгоритмов и теории вычислительной сложности алгоритмов.

Научная новизна. В диссертации получены следующие основные новые научные результаты, которые выносятся на защиту:

1. Доказана трудноразрешимость задач, связанных с вычислением классического минимального базиса импликаций.

2. Предложена новая модель приближенного базиса импликаций формального контекста, алгоритм его вычисления и эффективная программная реализация.

3. Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке

4. Предложена и эксперимен тально проверена модель распределенного обучения гипотезам - импликативным зависимостям для задачи машинного обучения.

5. Предложен линейный по времени алгоритм поиска всех гипотез но распределенной обучающей выборке и его программная реализация.

6. Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий вероятностный индекс устойчивости.

7. Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.

8. Решены давно сформулированные и остававшиеся открытыми задачи создания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний.

9. Показана полиномиальная эквивалентность задачи перечисления минимальных гипотез и задачи дуализации монотонной булевой функции на решетке.

10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделении прикладной математики и информатики НИУ ВШЭ комплекс программ.

Теоретическая значимость подтверждается тем, что были предложены новые модели имнликативиых зависимостей, а также средства их оценивания, показана их адекватность практическим задачам и возможность эффективной алгоритмической реализации. Были решены открытые теоретические задачи прикладной теории решеток и анализа данных.

Практическая ценность подтверждена экспериментами по построению приближенного базиса импликаций, распределенному обучению гипотезам и вычислению вероятностной устойчивости. Эти эксперименты показали значительные улучшения во времени вычисления и в качестве полученных результатов. Был разработан комплекс программ, в который вошли алгоритмы, опубликованные в данной работе.

Достоверность результатов подтверждена строгими математическими доказательствами теоретических утверждений, экспериментальной проверкой результатов численных расчетов и практической эффективности программных реализаций.

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

1. 8-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Агадир, Марокко, 2010.

2. 7-ой международной конференции по решеткам понятий и их приложениям (7th International ConfereGnce on Concept Lattices and Their

Applications), Севилья, Испания, 2010. [Награда за лучшую статью]

3. 9-ой международной конференции но анализу формальных понятий (9th International Conference on Formal Concept Analysis), Никосия, Кипр, 2011.

4. 10-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Лёвен, Бельгия, 2012.

Публикации. Основные результаты работы изложены в б научных статьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК. Также 1 статья принята к публикации в международный рецензируемый журнал.

Основные результаты и выводы работы:

1. Результаты, связанные с базисами импликаций:

1.1 Доказана трудноразрешимость (в терминах и со^-полноты и трудности) задач, связанных с вычислением классического минимального базиса импликаций.

1.2 Предложена модель приближенного базиса импликаций формального контекста, эффективный алгоритм его вычисления и программная реализация.

2. Результаты, связанные с минимальными гипотезами:

2.1 Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке.

2.2 Предложена и экспериментально проверена модель распределенного обучения гипотезам - имнликативных зависимостей для задачи машинного обучения.

2.3 Предложен эффективный алгоритм поиска всех гипотез но распределенной обучающей выборке и его программная реализация.

3. Результаты, связанные с индексом устойчивости формальных понятий и гипотез:

3.1 Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий - индекс вероятностной устойчивости.

3.2 Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.

Заключение

В диссертационной работе приведен обзор методов поиска строгих зависимостей в данных. В 2006 году участниками конференции ICFCA в Ленсе (Lens, Франция) был составлен список наиболее важных открытых задач в АФП. Одной из них была задача о сложности распознавания псевдосодержаний, которая была решена в данной диссертационной работе и опубликована в [31] (публикации, где рассматривалась данная задача и считалась открытой: [74, 89, 90, 91, 92, 38]). Эта задача была также представлена как открытая на Дрезденской конференции по дискретной математике в 2002 году.

В отличие от классического минимального базиса импликаций, для которого все известные алгоритмы построения имеют экспоненциальную оценку сложности, среднее время работы построения приближенного базиса импликаций полиномиально и оценивается как 0(\J\\М\ ■ (|С||М| + |J7"||M|) • £-1), где J ~ минимальный базис импликаций, а е - параметр точности приближенного базиса импликаций. Проведенные на реальных данных эксперименты показали, что размер приближенного базиса был значительно меньше (иногда в сотни раз).

В работе было доказано, что если Р ф NP, то невозможно найти все минимальные ДСМ-гипотезы за полиномиальное от размера выхода время. Модель распределенного обучения гипотезам показала значительное сокращение количества гипотез по отношению к числу ДСМ-гипотез в стандартной постановке. Линейный по времени алгоритм вычисления оператора замыканий системы замыканий общих содержаний позволил быстро перечислять все общие гипотезы.

В данной работе была доказана трудность аппроксимации индекса классической устойчивости формальных понятий (с полиномиально ограниченной относительной ошибкой). Была предложена модель вероятностного индекса устойчивости формальных понятий, которая соответствует аппроксимации классического индекса устойчивости с ограниченной абсолютной ошибкой и может быть вычислена за полиномиальное время. Проведенные эксперименты показали, что применение вероятностного индекса устойчивости, при использовании ДСМ-метода, уменьшает число некласси-фицируемых объектов па ~ 43% при увеличении количества ошибок классификации на « 23% (число неклассифицируемых объектов, при использовании стандартных ДСМ-гипотез ^ 46%).

1. Бабин М.А. О приближенном базисе импликаций // Научно-техническая информация. Серия: Информационные процессы и системы, №8, С. 20-23, 2012.

2. Бабин М.А., Кузнецов С.О. О теоретико-решеточной интерпретации задач поиска гипотез и зависимостей // Научно-техническая информация. Серия: Информационные процессы и системы, №10, С. 18-22, 2011.

3. Бабин М.А., Кузнецов С.О. Связи между решетками понятий и сложность их вычисления // Труды МФТИ, том 4 №2(14), С. 73-80, 2012.

4. Биркгоф Г. Теория решеток // М.: Наука, 1984.

5. Банник В.Н., Червоненкис А.Я. Теория распознавания образов // М., Наука, С.418, 1974.

6. Виноградов Д.В. Формализация правдоподобных рассуждений в логике предикатов // НТИ, Сер.2. №11, С.17-20, 2000.

7. Гретцер Г. Общая теория решеток // М.: Мир, 1982.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982.

9. Кузнецов С.О. Интерпретация на графах и сложностные характеристики задач поиска закономерностей определенного вида // НТИ, Сер.2, Ш., С.23 28, 1989.

10. Кузнецов С.О. Устойчивость как оценка обоснованности гипотез, получаемых на основе операционального сходства // НТИ, Сер.2, №12, С.21-29, 1990.

11. Кузнецов С.О. Введение в ДСМ-метод // Семиотика и информатика, Вып. 31, С.5-40, 1991.

12. Кузнецов С.О. ДСМ-метод как система автоматического обучения // Итоги науки и техники, Сер. Информатика, №15, С. 17-54, 1991.

13. Кузнецов С.О. Сложность алгоритмов обучения и классификации, основанных на поиске пересечения множеств // НТИ, Сер.2, №9, С.8-15, 1991.

14. Кузнецов С.О. Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки // НТИ, Сер.2, №1, С.17-20, 1993.

15. Кузнецов С.О. Алгоритмическая сложность порождения гипотез и классификаций, основанных на поиске пересечения множеств // Доклады АН.-335, №3, С.300-303, 1994.

16. Кузнецов С.О., Финн В.К. О модели обучения и классификации, основанной на операции сходства // Обозрение Прикладной и Промышленной Математики, 3, №1, С.66-90, 1996.

17. Кузнецов С.О., Объедков С.А. Алгоритмы построения множества всехпонятий формального контекста и его диаграммы Хассе // Известия Академии Наук, Теория и системы управления, №1, С. 120-129, 2001.

18. Кузнецов С.О. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика, №10, С.3-27, 2001.

19. Мейер Д. Теория реляционных баз данных // Москва, Мир, 1987.

20. Финн В.К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф.Бэкона Д.С.Милля. // Семиотика и информатика, Вып. 20, С.35-101, 1983.

21. Финн В.К. Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техн., Сер. Теория вероятностей Мат. стат. Теор. кибернет. М.:ВИНИТИ, Вып. 28, С.3-84, 1988.

22. Финн В.К. Об обобщенном ДСМ-методе автоматического порождения гипотез // Семиотика и информатика, Вып.29, С.93-123, 1989.

23. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ // Итоги науки и техники, Сер. Информатика, М.: ВИНИТИ, №15, С.54-101, 1991.

24. Финн В.К., Михеенкова М.А. О ситуационном расширении ДСМ-мстода автоматического порождения гипотез // НТИ, Сер.2, №11, С.20-30, 2000.

25. Anshakov О.М., Firm V.K., Skvortsov D.P. On axiomatization of many-valued logics associated with the formalization of plausible reasonings // Stud. Log., vol. 25, No. 4, p.23-47, 1989.

26. Agrawal R., Imielinski T., Swami A. N. Mining Association Rules between Sets of Items in Large Databases // SIGMOD Conference, p.207-216, 1993.

27. Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules in Large Databases // Journal of Computer Science and Technology, vol. 15, Issue 6, p.487-499, 1994.

28. Angluin D., Frazier M., Pitt L. Learning Conjunctions of Horn Clauses // Machine Learning, vol. 9, p. 147-164, 1992.

29. Armstrong W.W. Dependency structure of data base relationships // Proc. IFIP Congress, Geneva, p.580-583, 1974.

30. Babin M.A., Kuznetsov S.O. On Links between Concept Lattices and Related Complexity Problems // Proc. 8th Int. Conf. on Formal Concept Analysis (ICFCA'10), Lecture Notes in Artificial Intelligence, Springer, vol. 5986, p.138-144, 2010.

31. Babin M.A., Kuznetsov S.O. Recognizing Pseudo-intents is coNP-complete // Proc. CLA 2010, p.294-301, 2010.

32. Babin M.A., Kuznetsov S.O. Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices // Proc. 9th Int. Conf. on Formal Concept Analysis (ICFCA'll), Lecture Notes in Artificial Intelligence, Springer, vol. 6628, p.42-48, 2011.

33. Babin M.A., Kuznetsov S.O. Approximating Concept Stability // Proc. 10th Int. Conf. on Formal Concept Analysis (ICFCA'12), Lecture Notes in Artificial Intelligence, Springer, vol. 7278, p.7-15, 2012.

34. Babiri M.A., Kuznetsov S.O. Computing Premises of a Minimal Cover of Functional Dependencies is Intractable // Discrete Applied Mathematics, принята к публикации, 2012.

35. Bastide Y., Lakhal L., Pasquier N., Taouil R. Efficient Mining of Association Rules Based on Using Closed Itemset Lattices // J. Inf. Systems, vol. 24, p.25-46, 1999.

36. Bishop C.M. Pattern Recognition and Machine Learning // Information Science and Statistics, Springer, 2006.

37. Borchmann D., Distel F., Ryssel U. Fast Computation of Proper Premises // Proc. International Conference on Concept Lattices and Their Applications(CLA'2011), Nancy (France), 2011.

38. Distel F. Hardness of enumerating pseudo-intents in the lectic order // Proc. ICFCA 2010, Lecture Notes in Artificial Intelligence, vol. 5986, p. 124-137, Springer, 2010.

39. Distel F., Sertkaya В. On the complexity of enumerating pseudo-intents // Discrete Applied Mathematics, vol. 159, no.6, p.450-466, 2011.

40. Dyer M., Goldberg L.A., Greenhill C., Jerrum C. On the relative complexity of approximate counting problems, Proc. APPROX 2000, p.108-119, 2000.

41. Duquenne V., Guigues J. L. Families minimales d'implications informatives resultant d'un tableau de données binaries / / Mathématiques, Informatique et Sciences Humaines, 95, p.5-18, 1986.

42. Duquenne V., Obicdkov S.A. Attribute-incremental construction of the canonical implication basis // Annals of Mathematics and Artificial Intelligence, 49(l-4):7799, 2007.

43. Egho E., Jay N., Raissi C., Napoli A. A FCA-based Analysis of Sequential Care Trajectories // Proc. 8th of the International Conference on Concept Lattices and Their Applications (CLA'2011), Nancy (France), p.362-376, 2011.

44. Eiter T., Ibaraki T., Makino K. Computing Intersections of Horn Theories for Reasoning with Models // Proc. National Conference on Artificial Intelligence (AAAI'98), Madison, Wisconsin, July 26-30, p.292-297, 1998.

45. Falk I., Gardent C. Combining Formal Concept Analysis and Translation to Assign Frames and Thematic Role Sets to French Verbs // Proc. International Conference Concept Lattices and Their Applications (CLA'2011), Nancy (France), 2011.

46. Falk I., Gardent C. Bootstrapping a Classification of French Verbs Using Formal Concept Analysis // Proc. Interdisciplinary Workshop on Verbs, Pisa (Italy), 2011.

47. Falk I., Gardent C., Lorenzo A. Using Formal Concept Analysis to Acquire Knowledge about Verbs // Proc. 7th of the International Conference on Concept Lattices and Their Applications (CLA'2010), p. 151-162, 2010.

48. Feldman R., Sanger J. The text mining handbook: advanced approaches in analyzing unstructured data // Cambridge University Press, 2007.

49. Fredman M.L., Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // Journal of Algorithms, vol. 21, p.618-628, 1996.

50. Ganter B. Two Basic Algorithms in Concept Analysis // FB4-Preprint No. 831, TH Darmstadt, 1984.

51. Ganter B. Lattices of Rough Set Abstractions as P-Products // Proc. ICFCA 2008, Lecture Notes in Computer Science, vol. 4933, p. 199-216, 2008.

52. Ganter B., Kuznetsov S. Formalizing Hypotheses with Concepts, Proc. 8th Int. Conf. on Conceptual Structures, ICCS'00, Lecture Notes in Artificial Intelligence, vol. 1867, p.342-356, 2000.

53. Ganter B., Kuznetsov S.O. Hypotheses and Version Spaces // Proc. 10th Int. Conf. on Conceptual Structures, ICCS'03, Lecture Notes in Artificial Intelligence, vol. 2746, p.83-95, 2003.

54. Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations // Springer, Berlin, 1999.

55. Garcy M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness // W. H. Freeman, 1979.

56. Gold E.M. Language identification in the limit // Information and Control, vol. 10, p.447-474, 1967.

57. Jay N., Kohler F., Napoli A. Analysis of Social Communities with Iceberg and Stability-Based Concept Lattices // Proc. 6th International Conference on Formal Concept Analysis (ICFCA'2008), p.258-272, 2008.

58. Jerrum M. R., Valiant L.G., Vazirani V.V. Random generation of combinatorial structures from a uniform distribution // Theoretical Computer Science, vol. 43, no. 2-3, p. 169-188, 1986.

59. Jiawei H., Jian P., Yiwen Y., Runying M. Mining frequent patterns without candidate generation // Data Mining and Knowledge Discovery, vol. 8, p.53-87, 2004.

60. Johnson D.S., Papadimitriou C.H., Yannakakis M. On Generating All Maximal Independent Sets // Informaion Processing Letters, vol. 27, no. 3, p.119-123, 1988.

61. Kavvadias D. J., Sideri M., Stavropoulos E. C. Generating All Maximal Models of a Boolean Expression, 1999.

62. Kavvadias D.J., Stavropoulos E.C. An Efficient Algorithm for the Transversal Hypergraph Generation //J. Graph Algorithms Appl., vol. 9(2), p.239-264, 2005.

63. Khardon R. Translating between Horn Representations and their Characteristic Models //J. Artificial Intelligence, vol. 3, p.349-372, 1995.

64. Kivinen J., Mannila H. Approximate Inference of Functional Dependenciesfrom Relations // Theoretical Computer Science, vol. 149, no. 1, p. 129149, 1995.

65. Klimushkin M., Obiedkov S.A., Roth C. Approaches to the Selection of Relevant Concepts in the Case of Noisy Data // Proc. 8th International Conference on Formal Concept Analysis (ICFCA'2010), p.255-266, 2010.

66. Kourie D.G., Obiedkov S.A., Roth C. Towards Concise Representation for Taxonomies of Epistemic Communities // Proc. International Conference Concept Lattices and Their Applications (CLA'2006), Tunis (Tunisia), p.240-255, 2006.

67. Kuznetsov S.O. Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity // Nauchn. Tekh. Inf., ser 2., №12, p.21-29, 1990.

68. Kuznetsov S.O. On Computing the Size of a Lattice and Related Decision Problems // Order, 18(4), p.313-321, 2001.

69. Kuznetsov S.O. Machine Learning on the Basis of Formal Concept Analysis // Automation and Remote Control, vol. 62, no. 10, 2001.

70. Kuznetsov S.O., Obiedkov S.A. Comparing performance of algorithms for generating concept lattices //J. Exp. Theor. Artif. Intell., 14, 2-3, p.189-216, 2002.

71. Kuznetsov S.O. Stability of a Formal Concept // Proc. 4th Journee d'Informatique Messine (JIM'03), Metz, 2003.

72. Kuznetsov S.O. On the intractability of computing Duquenne-Guigues base //J. Universal Computer Sciencc, vol. 10, no. 8, p.927-933, 2004.

73. Kuznetsov S.O. Complexity of Learning in Concept Lattices from Positive and Negative Examples // Discrete Applied Mathematics, 110. 142, p. 111125, 2004.

74. Kuznetsov S.O. On Stability of a Formal Concept // Annals of Mathematics and Artificial Intelligence, vol. 49, p. 101-115, 2007.

75. Kuznetsov S.O., Obiedkov S.A. Counting pseudo-intents and #P-completeness // Proc. ICFCA 2006, Lecture Notes in Computer Science, vol. 3874, p.306—308, Springer, 2006.

76. Kuznetsov S.O., Obiedkov S.A. Some decision and counting problems of the Duquenne-Guigues basis of implications // Discrete Applied Mathematics, 156(11), p. 1994-2003, 2008.

77. Krôtzsch M. and Malik G. The Tensor Product as a Lattice of Regular Galois Connections // Proc. 4th Inernational Conference on Formal Concept Analysis (ICFCA'2006), Lecture Notes in Artificial Intelligence (LNAI), vol. 3874, p.89-104, Springer 2006.

78. Loshin D. Master Data Management // Morgan Kaufmann Publishers, 2009.

79. Mannila H., Râihâ K. The design of relational databases // Addison Wesley, 1992.

80. Mohammed Z.J. Scalable algorithms for association mining // IEEE Transactions on Knowledge and Data Engineering, vol. 12(3), p.372-390, 2000.

81. Motwani R., Raghavan P. Randomized Algorithms // Cambridge University Press, 1995.

82. Nienhuys-Cheng S.-H., Wolf R. Foundations of Inductive Logic Programming, // Lecture Notes in Artificial Intelligence, vol. 1228, 1997.

83. Obiedkov S.A., Roth C., Kourie D.G. On Succinct Representation of Knowledge Community Taxonomies with Formal Concept, Analysis // Int. J. Found. Comput. Sci., 19(2), p.383-404, 2008.

84. Obiedkov S.A., Roth C., Kourie D.G. Towards Concise Representation for Taxonomies of Epistemic Communities // Proc. 4th International Conference Concept Lattices and Their Applications (CLA'2006), p.240-255, 2008.

85. Piatetsky-Shapiro G. Discovery, Analysis, and Presentation of Strong Rules // Knowledge Discovery in Databases, p.229-248, 1991.

86. Poelmans J., Elzinga P., Neznanov A., Dedene G., Viaene S., Kuznetsov S.O. Human-Centered Text Mining: A New Software System // ICDM 2012, p.258-272, 2012.

87. Priss U. Some open problems in Formal Concept Analysis // Proc. ICFCA 2006, 2006.

88. Rudolph S. Some notes on pseudo-closed sets // Proc. ICFCA 2007, Lecture Notes in Computer Science, vol. 4390, p.151-165, Springer, 2007.

89. Sertkaya B. Towards the complexity of recognizing pseudo-intents // Proc. ICCS 2009, Lecture Notes in Computer Science, vol. 5662, p.284-292, Springer, 2009.

90. Sertkaya B. Some computational problems related to pseudo-intents // Proc. ICFCA 2009, Lecture Notes in Computer Science, vol. 5662, p.284-292, Springer, 2009.

91. Singh K., Singh R. A Descriptive Classification of Causes of Data Quality Problems in Data Warehousing // International Journal of Computer Science Issue, vol. 7, Issue 3, No. 2, 2010.

92. Solomonoff R.J. A formal theory of inductive inference // Information and Control, vol. 7, p. 224-254, 1964.

93. Valiant L.G. The complexity of computing the permanent // Theoretical Computer Science, 8, No. 2, p. 189-201, 1979.

94. Valiant L.G. The Complexity of Enumeration and Reliability Problems // SIAM J. Comput., 8, no. 3, p.410-421, 1979.

95. Valiant L.G. A theory of the learnable // Coinmun. ACM, 27, no. 11, p.1134-1142, 1984.

96. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets, Reidel, p.445-470, Dordrecht-Boston, 1982.

97. Wille R. Conceptual Structure of Multicontexts // Proc. 4th International Conference on Conceptual Structures, Lecture Notes in Artificial Intelligence (LNAI), vol. 1115, p.23-39, Springer, 1996.

98. Сайт репозитория машинного обучения UCI http://archive.ics.uci.edu/ml/