Главная » Просмотр файлов » Диссертация

Диссертация (1137435)

Файл №1137435 Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств)Диссертация (1137435)2019-05-20СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИФедеральное государственное автономное образовательное учреждениевысшего профессионального образованияНАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»На правах рукописиБАБИНМихаил АлександровичМОДЕЛИ, МЕТОДЫ И КОМПЛЕКСЫ ПРОГРАММПОСТРОЕНИЯ ЗАВИСИМОСТЕЙ, ОСНОВАННЫЕ НАРЕШЕТКАХ ЗАМКНУТЫХ МНОЖЕСТВСпециальность 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 с определённым на нем отношением частичного порядка≤ (частично упорядоченное множество) обозначается (, ≤).

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации

Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6310
Авторов
на СтудИзбе
312
Средний доход
с одного платного файла
Обучение Подробнее