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

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИФедеральное государственное автономное образовательное учреждениевысшего профессионального образованияНАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»На правах рукописиБАБИНМихаил АлександровичМОДЕЛИ, МЕТОДЫ И КОМПЛЕКСЫ ПРОГРАММПОСТРОЕНИЯ ЗАВИСИМОСТЕЙ, ОСНОВАННЫЕ НАРЕШЕТКАХ ЗАМКНУТЫХ МНОЖЕСТВСпециальность 05.13.18Математическое моделирование, численные методы икомплексы программДиссертация на соискание учёной степеникандидата физико-математических наукНаучный руководительдоктор физико-математических наукC. О. КузнецовМосква 20122ОглавлениеВведение15Построение зависимостей в данных с помощью решетокзамкнутых множеств: основные понятия и состояние пред­метной области101.1 Основные определения . .

. . . . . . . . . . . . . . . . . . . .101.1.1Частично упорядоченные множества и решетки . . .101.1.2Анализ формальных понятий . . . . . . . . . . . . . .141.1.3Теория алгоритмов и вычислительная сложность . . .181.2 Модели зависимостей и их вычисление . . . . . . . . . . . .271.3 Минимальная модель знаний о предметной области: минимальный базис импликаций . . . .

. . . . . . . . . . . . . . .321.4 Задачи и алгоритмы построения гипотез . . . . . . . . . . .362 Базисы импликаций и функциональных зависимостей422.1 Квазизамкнутые множества и псевдосодержания . . . . . . .422.2 Структура минимальных базисов импликаций . . . . . . . .432.3 Функциональные зависимости и импликации .

. . . . . . . .452.4 Распознавание псевдосодержаний . . . . . . . . . . . . . . . .462.5 Лектически максимальные псевдосодержания и перечисление максимальных псевдосодержаний . . . . . . . . . . . . .5432.6 Распознавание существенных содержаний . . . . . . . . . . .2.6.156Посылка импликации из минимального базиса . . . .572.7 Базис импликаций с двухэлементными посылками . .

. . . .602.8 Приближенный базис импликаций . . . . . . . . . . . . . . .622.8.1Результаты экспериментов . . . . . . . . . . . . . . . .3 Базисы импликаций и общие содержания3.1 Связь базиса импликаций с общими содержаниями . . . . .6567673.2 Общий метод поиска минимального базиса импликаций черезобщие содержания . . . . . . . .

. . . . . . . . . . . . . . . .683.2.1Поиск собственных посылок через общие содержания683.3 Интенсионально связанные понятия . . . . . . . . . . . . . .693.4 Понятия с общими содержаниями . . . . . . . . . . . . . . .713.5 Сцепления и общие содержания . . .

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

. . . . . . . . . . . . . . . . . . . . .904.3 Распределенное обучение гипотезам . . . . . . . . . . . . . .994.4 Устойчивость понятий и гипотез . . . . . . . . . . . . . . . . 1014.5 Приближенный подсчет числа замкнутых и незамкнутыхмножеств . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . 1034.6 Индекс вероятностной устойчивости . . . . . . . . . . . . . . 10644.7 Анализ результатов вычислений индекса вероятностнойустойчивости . . . . . . . . . . . . . . . . . . . . . . . . . . . 1094.8 Устойчивые гипотезы: Результаты экспериментов с даннымипо токсичности химических соединений . . . . .

. . . . . . . 1115 Комплекс программ5.1 Программный комплекс Cordiet114. . . . . . . . . . . . . . . . 1145.2 Программная реализация построения базисов импликаций . 1145.3 Программная реализация алгоритма вычисления операторазамыкания общих содержаний . . . . . . . . . . .

. . . . . . 1165.4 Программная реализация распределенного обучения гипотезам117Заключение118Литература121Приложения1345.5 Приложение 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.6 Приложение 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 1405.7 Приложение 1.3 . . . . . . .

. . . . . . . . . . . . . . . . . . . 1485.8 Приложение 1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . 1525.9 Приложение 1.5 . . . . . . . . . . . . . . . . . . . . . . . . . . 1645.10 Приложение 1.6 . . . . . . . . . . . . . . . . . . . . . . . . . . 1665.11 Приложение 2.1 . . . . . .

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

Примерами актуальных задач являются:∙ Модели импликативных зависимостей, позволяющие более сжатоепредставление и эффективную алгоритмическую реализацию∙ Эффективные алгоритмы порождения приближенных базисов им-6пликаций, множества минимальных ДСМ-гипотез∙ Эффективные алгоритмы распознавания псевдосодержаний, задающих оптимальный базис импликаций∙ Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостейТак например, сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей (импликаций) была одной из основных открытых задач АФП на протяжении многих лет (список открытыхзадач АФП [89] задачи 2,8,9).Объектом исследования является модель импликативных зависимостей данных и ее эффективная алгоритмическая реализация.Целью исследования является разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, а также решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.Методы исследования.

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

Предложена новая модель приближенного базиса импликаций фор-7мального контекста, алгоритм его вычисления и эффективная программная реализация.3. Доказана трудноразрешимость вычисления минимальных гипотез встандартной постановке4. Предложена и экспериментально проверена модель распределенногообучения гипотезам – импликативным зависимостям для задачи машинного обучения.5. Предложен линейный по времени алгоритм поиска всех гипотез пораспределенной обучающей выборке и его программная реализация.6. Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий – вероятностный индекс устойчивости.7. Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективныйалгоритм и его программная реализация.8.

Решены давно сформулированные и остававшиеся открытыми задачисоздания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний.9. Показана полиномиальная эквивалентность задачи перечисления минимальных гипотез и задачи дуализации монотонной булевой функции на решетке.10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в От-8делении прикладной математики и информатики НИУ ВШЭ комплекс программ.Теоретическая значимость подтверждается тем, что были предложены новые модели импликативных зависимостей, а также средства ихоценивания, показана их адекватность практическим задачам и возможность эффективной алгоритмической реализации.

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

Основные результаты работыдокладывались и обсуждались на следующих научных конференциях:1. 8-ой международной конференции по анализу формальных понятий(8th International Conference on Formal Concept Analysis), Агадир, Марокко, 2010.2. 7-ой международной конференции по решеткам понятий и их приложениям (7th International Confere6nce on Concept Lattices and Their9Applications), Севилья, Испания, 2010. [Награда за лучшую ста­тью]3. 9-ой международной конференции по анализу формальных понятий(9th International Conference on Formal Concept Analysis), Никосия,Кипр, 2011.4. 10-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Лёвен,Бельгия, 2012.Публикации.

Основные результаты работы изложены в 6 научныхстатьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и2 опубликованы в журналах из списка ВАК. Также 1 статья принята кпубликации в международный рецензируемый журнал.101. Построение зависимостей в данных с помощьюрешеток замкнутых множеств: основные понятия исостояние предметной области1.1.Основные определения1.1.1.Частично упорядоченные множества и решеткиОпределение 1.1. Бинарное отношение ≤ на некотором множестве называется отношением (нестрогого) частичного порядка, если для , , ∈:1. ≤ (рефлексивность);2. Если ≤ и ≤ , то = (антисимметричность);3. Если ≤ и ≤ , то ≤ (транзитивность).Множество S с определённым на нем отношением частичного порядка≤ (частично упорядоченное множество) обозначается (, ≤).