Автореферат (1137434)
Текст из файла
На правах рукописиБабин Михаил АлександровичМодели, методы и комплексы программ построения зависимостей,основанные на решетках замкнутых множествСпециальность 05.13.18Математическое моделирование, численные методы и комплексы программАВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата физико-математических наукМосква — 2012Работа выполнена в Национальном исследовательском университете «Высшая школа экономики» (НИУ ВШЭ).Научный руководитель:доктор физико-математических наукКузнецов Сергей ОлеговичОфициальные оппоненты:доктор физико-математических наук, профессор,профессор кафедры математики, логики и интеллектуальных систем Института лингвистики РГГУАншаков Олег Михайловичкандидат физико-математических наук,старший научный сотрудник отдела теоретических и прикладных проблем информатикиВИНИТИ РАНВиноградов Дмитрий ВячеславовичВедущая организация:Институт проблем передачи информации им.
А.А. Харкевича(ИППИ) РАНЗащита состоится “29” октября 2012 г. в 14.00 на заседании диссертационного совета Д 212.048.09 в Национальном исследовательском университете«Высшая школа экономики» (НИУ ВШЭ) по адресу: 105187, Москва, ул. Кирпичная, д. 33., ауд. 505С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики».Автореферат разослан “Учёный секретарьдиссертационного советадоктор технических наук” сентября 2012 г.В.А. Фомичев3ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность работы.
Стремительный рост объема данных разной природы, наблюдающийся в последние десятилетия, приводит к необходимостиразработки эффективных методов их автоматического и интерактивного анализа. Одной из распространенных математических моделей, позволяющихописывать методы и алгоритмы анализа данных, является анализ формальных понятий.Анализ формальных понятий (АФП) является ветвью прикладной алгебраической теории решеток, широко используемой для описания методованализа данных.
АФП предлагает средства моделирования онтологий и таксономий предметных областей на основе решеток понятий, а также моделиточных и приближенных зависимостей в данных.Для многих ключевых задач анализа формальных понятий до сих порнеизвестны эффективные алгоритмы и какие-либо теоретические оценки ихсложности. Основной целью большинства существующих исследований является анализ данных на основе методов АФП, в то время как эффективныеалгоритмы и вычислительная сложность этих методов уходит на второй план.Примерами актуальных задач являются:∙ Модели импликативных зависимостей, позволяющие более сжатое представление и эффективную алгоритмическую реализацию∙ Эффективные алгоритмы порождения приближенных базисов импликаций, множества минимальных ДСМ-гипотез∙ Эффективные алгоритмы распознавания псевдосодержаний, задающихоптимальный базис импликаций∙ Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостейТак например, эффективные алгоритмы порождения и сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей(импликаций) была одной из основных открытых задач АФП на протяжениимногих лет (список открытых задач АФП [U.
Priss 2006] задачи 2,8,9).Объектом исследования являются модели импликативных зависимостейв данных и их эффективная алгоритмическая реализация.Целью исследования является разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, атакже решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.Методы исследования. В диссертации применяются методы анализаформальных понятий, дискретной оптимизации, вероятностных алгоритмови теории вычислительной сложности алгоритмов.Научная новизна.
В диссертации получены следующие основные новыенаучные результаты, которые выносятся на защиту:41. Доказана трудноразрешимость задач, связанных с вычислением классического минимального базиса импликаций.2. Предложена новая модель приближенного базиса импликаций формального контекста, алгоритм его вычисления и эффективная программнаяреализация.3. Доказана трудноразрешимость вычисления минимальных гипотез встандартной постановке4. Предложена и экспериментально проверена модель распределенногообучения гипотезам – импликативным зависимостям для задачи машинного обучения.5. Предложен линейный по времени алгоритм поиска всех гипотез по распределенной обучающей выборке и его программная реализация.6.
Предложена и экспериментально проверена модель оценивания гипотези формальных понятий – вероятностный индекс устойчивости.7. Теоретически и экспериментально исследована сложность вычислениявероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация.8. Решены давно сформулированные и остававшиеся открытыми задачисоздания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний.9.
Показана полиномиальная эквивалентность задачи перечисления минимальных гипотез и задачи дуализации монотонной булевой функции нарешетке.10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделенииприкладной математики и информатики НИУ ВШЭ комплекс программ.Теоретическая значимость подтверждается тем, что были предложеныновые модели импликативных зависимостей, а также средства их оценивания,показана их адекватность практическим задачам и возможность эффективнойалгоритмической реализации.
Были решены открытые теоретические задачиприкладной теории решеток и анализа данных.Практическая значимость подтверждена экспериментами по построениюприближенного базиса импликаций, распределенному обучению гипотезам ивычислению вероятностной устойчивости. Эти эксперименты показали значительные улучшения во времени вычисления и в качестве полученных результатов. Был разработан комплекс программ, в который вошли алгоритмы,опубликованные в данной работе.Достоверность результатов подтверждена строгими математическимидоказательствами теоретических утверждений, экспериментальной проверкой5результатов численных расчетов и практической эффективности программных реализаций.АПРОБАЦИЯ РАБОТЫОсновные результаты работы докладывались и обсуждались на следующих научных конференциях:1. 8-ой международной конференции по анализу формальных понятий (8thInternational Conference on Formal Concept Analysis), Агадир, Марокко,2010.2.
7-ой международной конференции по решеткам понятий и их приложениям (7th International Confere6nce on Concept Lattices and TheirApplications), Севилья, Испания, 2010. [Награда за лучшую статью]3. 9-ой международной конференции по анализу формальных понятий (9thInternational Conference on Formal Concept Analysis), Никосия, Кипр,2011.4.
10-ой международной конференции по анализу формальных понятий(8th International Conference on Formal Concept Analysis), Лёвен, Бельгия,2012.Публикации. Основные результаты работы изложены в 6 научных статьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК.Структура и объем диссертации. Диссертация состоит из пяти глав, заключения, списка литературы и приложений. Общий объем основного текстаработы — 133 страницы. Список литературы включает 100 наименований.КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫВо введении обоснована актуальность темы, сформулированы цели изадачи исследования, научная новизна, теоретическая и практическая значимость полученных результатов, основные положения, выносимые на защиту,а также приведены данные о структуре и объеме диссертации.В первой главе описываются основные результаты и определения используемые в диссертации.Ниже приводятся основные определения анализа формальных понятий,используемые в диссертационной работе.Пусть и - конечные множества, называющиеся множествами объектов и признаков соответственно.
Пусть - бинарное отношение ⊆ × между объектами и признаками: для ∈ , ∈ , выполнено тогда итолько тогда, когда объект обладает признаком . Тройка K = (, , )6называется (формальным) контекстом. Если ⊆ , ⊆ - произвольные подмножества, то следующая пара операторов, называемых операторамиГалуа,′ = { ∈ | ∀ ∈ } ′ = { ∈ | ∀ ∈ }задает соответствие Галуа между частично упорядоченными множествами(2 , ⊆) и (2 , ⊆).Пара (, ), где ⊆ , ⊆ , ′ = , и ′ = (следовательно,′′ = и ′′ = ), называется (формальным) понятием (контекста K) собъемом и содержанием .Оператор (·)′′ является оператором замыкания, т.е.
он идемпотентен( ′′′′ = ′′ ), экстенсивен ( ⊆ ′′ ) и монотонен ( ⊆ ⇒ ′′ ⊆ ′′ ).Множества ⊆ , ⊆ называются замкнутыми если ′′ = и ′′ = .Очевидно, объемы и содержания (и только они) замкнуты. Множество всехзамкнутых множеств относительно данного оператора замыкания называетсясистемой замыканий.Основная теорема анализа формальных понятий (см.
[Ganter B., WilleR., 1999]) говорит, что множество понятий контекста K = (, , ) образуетполную решетку со следующими операциями инфинума (inf) и супремума(sup) соответственно:(︃(︃)︃′′ )︃⋀︁⋂︁⋃︁( , ) = ,∈∈∈)︃′′(︃(︃⋁︁∈( , ) =⋃︁∈)︃,⋂︁∈Понятие (, ) называется супремум-неразложимым, если оно не можетбыть представлено как супремум каких-то других понятий.Множество признаков следует из множества признаков , или выполнена импликация → , если все объекты из , которые обладают всемипризнаками из , также обладают всеми признаками из , т.е.
′ ⊆ ′ .Импликации подчиняются правилам Армстронга:→ → , ∪ → ,.→∪ →∪ →Во второй главе приводятся основные результаты диссертации, связанные с оптимальными базисами импликаций формального контекста.В разделе 2.1 приводятся основные определения, связанные с минимальными базисами импликаций, такие как определения псевдосодержаний, существенных содержаний и квазизамкнутых множеств.Подмножество ⊆ удовлетворяет импликации → , если из ⊆ следует ⊆ . Любое множество импликаций J на множестве определяет оператор замыкания (·)J на , где подмножество замкнуто,7тогда и только тогда, когда это множество удовлетворяет всем импликациям из J. Набор импликаций, из которого все остальные импликации могутбыть выведены по правилам Армстронга, называется базисом импликаций.Другое, эквивалентное определение базиса импликаций это совпадение операторов замыкания (·)′′ и (·)J .
Одним из минимальных базисов импликацийявляется базис Дюкена-Гига (канонический базис). Множество посылок импликаций в каноническом базисе является в точности множеством псевдосодержаний. Множество ⊆ называется псевдосодержанием, если ̸= ′′и ′′ ⊂ для любого псевдосодержания ⊂ . Подмножество ⊆ квазизамкнуто, если его пересечение с любым замкнутым множеством замкнуто.Множество квазизамкнутых множеств образует систему замыканий. Множество ⊆ называется существенным содержанием (существенно замкнутоеподмножество признаков), если существует псевдосодержание ⊆ такое, что ′′ = .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
