Разработка метода и средств фрагментации и дефрагментации формальных контекстов

Монгуш, Чодураа Михайловна

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Глава 1 Объектно-признаковые модели коллекций текстов и методы их
анализа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1 Модели и методы анализа естественно-языковых текстов . . . . . . 12
1.2 Теоретические основы анализа формальных понятий . . . . . . . . . 18
1.3 Постановка задачи нахождения всех формальных понятий . . . . . . 25
1.4 Выводы по главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Глава 2 Снижение размерности формального контекста без потери иско-
мых формальных понятий . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.1 Метод декомпозиции контекста без потери формальных понятий . . 31
2.2 Алгоритм формирования системы фрагментов контекста . . . . . . . 41
2.3 Алгоритм восстановления решетки формальных понятий . . . . . . . 51
2.4 Алгоритмы реализации запросов на извлечение знаний из решетки
формальных понятий . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5 Процедуры предобработки формального контекста . . . . . . . . . . 59
2.6 Анализ результативности разработанных алгоритмов . . . . . . . . . 61
2.7 Выводы по главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Глава 3 Программные средства и результаты их применения при исследо-
вании коллекции «Тувинские героические сказания» . . . . . . . . . . . 72
3.1 Описание программных средств . . . . . . . . . . . . . . . . . . . . . 72
3.2 Структура базы данных, описание информационного интерфейса . . 77
3.3 Установление авторского стиля сказителей . . . . . . . . . . . . . . . 80
3.4 Выводы по главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Cписок литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Актуальность темы исследования. Во многих задачах интеллектуально-
го анализа данных, в том числе в анализе естественно-языковых текстов, изуча-
емая предметная область часто описывается в виде объектно-признаковой таб-
лицы, в которой каждый столбец соответствует некоторому признаку, а каждая
строка определяет признаковое описание отдельного объекта [1, 5, 6, 29–32, 39].
Появление размеченных корпусов естественных языков как элементов ин-
формационных систем позволяет получать структурированную информацию и
представлять ее в виде объектно-признаковой таблицы. Разметка — главная ха-
рактеристика корпуса, отличающая корпус от простых электронных коллекций
текстов [33, 72]. Она отражает лингвистическую и экстралингвистическую ин-
формацию хранимых текстов в корпусе. Чем больше набор признаков, характе-
ризующий каждый текст, тем шире возможности корпуса по поиску текстов для
решения различных филологических и лингвистических задач. В рамках кор-
пусов решаются различные прикладные задачи, учитывающие семантическую
составляющую анализируемых текстов [23, 74]. Эти задачи в основном сводятся
к задачам концептуального моделирования коллекции текстов [43].
Существует формализованный подход, известный в литературе как анализ
формальных понятий (АФП, англ. Formal Concept Analysis), который позволяет
построить концептуальную модель исходя из объектно-признаковой таблицы на
основе алгебраической теории решеток Г. Биркгофа [9,10]. Построенная концеп-
туальная модель позволяет решать различные прикладные задачи, связанные с
анализом текстов на естественном языке. В рамках АФП объектно-признаковая
таблица представляется формальным контекстом и моделируется 0,1-матрицей,
отражающей отсутствие или наличие признаков, характерных для исследуемо-
го множества текстов. Основные идеи АФП были сформулированы в работах
Р. Вилле и Б. Гантера в начале 80-х годов XX века и развиты в исследова-
ниях российских ученых С. О. Кузнецова, К. А. Найденовой, С. А. Объедкова,
С. И. Гурова, Д. И. Игнатова [20, 34, 35, 91–93, 110]. Каждое формальное поня-
тие в АФП определяется с использованием соответствий Галуа и представляет
собой пары замкнутых множеств, интерпретируемых как объем и содержание
этого понятия. В матричной форме формальному понятию соответствует некото-
рая максимально полная подматрица 0,1-матрицы, представляющей формальный
контекст. Главным достоинством этого определения является полное совпадение
традиционной трактовке термина «понятие», применяемого в гуманитарных на-
уках [125]. С применением методов АФП решаются типовые задачи анализа
данных, связанные с классификацией и кластеризацией данных, выявлением за-
висимостей между данными [7, 8, 11, 21, 35, 46, 88, 113, 117]. В них формальные
понятия трактуются как перекрестные ассоциации, кластеры или бикластеры. В
рамках АФП решение указанных задач сводится к нахождению всех формаль-
ных понятий исходного формального контекста с последующим связыванием их
в решетку. Полученная решетка служит концептуальной моделью исследуемой
предметной области и основой для решения прикладных задач.
При всей привлекательности методов АФП их практическое применение
ограничивается высокой трудоемкостью процесса извлечения всех формальных
понятий из исходного контекста. В задаче нахождения всех формальных понятий
требуется найти множество всех формальных понятий для заданного формаль-
ного контекста. Данная задача относится к комбинаторным перечислительным
задачам и является #P -полной [103]. Высокая вычислительная сложность за-
дачи состоит в том, что число формальных понятий в общем случае экспонен-
циально зависит от размера исходного формального контекста. Рассматриваемая
задача эквивалентна задаче определения всех максимально полных подматриц
0,1-матрицы и может встречаться в различных задачах комбинаторной оптими-
зации [24–26, 79, 82, 97, 105, 109, 115, 118, 124, 127].
Степень разработанности темы исследования.
На сегодняшний день для нахождения множества всех формальных по-
нятий и построения решетки разработано много алгоритмов и программных
средств [45, 80, 84, 89, 94, 95, 99–101, 106, 107, 112]. Традиционно данные алгорит-
мы разделяют на две группы: пакетные алгоритмы (Bordat [84], NextClosure [94],
Close-by-One [101], Lindig [106]), которые строят решетку понятий из ранее най-
денных формальных понятий; инкрементные алгоритмы (Nourine [112], Godin
[95], Dowling [89], Norris [99]), которые достраивают решетку посредством по-
степенного добавления объектов и пересечения с имеющимися формальными
понятиями. Подробное описание и сравнение практической производительно-
сти этих алгоритмов представлено в работе [101]. Известно, что время выполне-
ния указанных алгоритмов в худшем случае составляет O(|F C| · |G|2 · |M |), где
|F C| — число найденных формальных понятий, |G| — количество объектов, |M |
— количество признаков исходного формального контекста. Поскольку величи-
на |F C| экспоненциально зависит от |G| и |M |, то время выполнения данных
алгоритмов также может быть экспоненциальным.
Наиболее известными программными системами являются Concept Exp-
lorer, ToscanaJ, Galicia, Lattice Minner, OpenFCA, FCART [27, 81, 86, 104, 111,
116, 123]. Многие из них находятся в открытом доступе. Программа Concept
Explorer позволяет обрабатывать формальные контексты, шкалировать много-
значные признаки формального контекста и визуализировать решетки формаль-
ных понятий [27]. Автоматическое формирование исходного контекста на осно-
ве реляционных баз данных реализовано в системе ToscanaJ [81]. Программа
Galicia имеет широкие возможности по визуализации решеток формальных по-
нятий в трехмерном пространстве, а основная цель OpenFCA — отображение
решеток через веб-приложения [86,123]. Все эти программные средства являют-
ся специализированными продуктами, т. е. направлены на решение конкретной
задачи. Создатели программы FCART объединили полный цикл исследований
на основе методов АФП в одну универсальную интегрированную среду [111].
Однако, вычислительная сложность задачи нахождения всех формальных поня-
тий формального контекста большой размерности и связывание их в решетку
остается открытой.
В настоящее время актуальны исследования по снижению вычислительной
сложности задачи нахождения всех формальных понятий. Первое направление
исследований связано с разработкой новых алгоритмов отбора информативных,
релевантных формальных понятий при построении решетки [25, 35, 76–78]. Та-
кой подход к решению рассматриваемой задачи позволяет уменьшить ее вы-
ход. Второе направление исследований рассматривает уменьшение размерно-
сти входа, а значит, повышение производительности существующих алгорит-
мов нахождения множества всех формальных понятий и родственных с ней
задач, путем «неискажающего» разложения формального контекста — деком-
позиции исходного контекста с сохранением всех искомых формальных поня-
тий [83,90,91,119,121]. Такое направление исследований является более универ-
сальным и рассматривается в настоящей диссертационной работе.
Цель и задачи исследования. Целью диссертационной работы является
повышение производительности существующих алгоритмов решения задачи на-
хождения всех формальных понятий путем декомпозиции формального контек-
ста на фрагменты без потери искомых формальных понятий и разработка на их
основе математического и программного обеспечения.
Для достижения цели были поставлены и решены следующие задачи.
1. Разработать и теоретически обосновать метод «неискажающего» разло-
жения формального контекста на фрагменты. Исследовать структуру фрагментов
и найти оценку числа фрагментов, получаемых на каждой итерации разложения,
определить правила остановки процесса разложения формального контекста на
фрагменты без потери формальных понятий.
2. Разработать алгоритмы формирования для заданного формального кон-
текста системы фрагментов, восстановления искомого решения исходя из реше-
ний, полученных для подзадач, и реализации возможных запросов на извлечение
знаний из решетки формальных понятий.
3. Разработать алгоритмы предобработки формального контекста без поте-
ри формальных понятий путем удаления единичных, нулевых и кратных строк
и столбцов этого контекста.
4. Создать комплекс программ, реализующий разработанные метод и алго-
ритмы, для проверки их результативности на случайных формальных контекстах
и на реальных данных применительно к корпусу тувинского языка.
Научная новизна.
1. Разработан новый метод декомпозиции формального контекста на фраг-
менты без потери формальных понятий. В отличие от существующих методов
АФП, предложенный метод позволяет уменьшить размерность формального кон-
текста с сохранением всех искомых формальных понятий и тем самым повысить
производительность известных алгоритмов нахождения всех формальных поня-
тий формального контекста.
2. Впервые разработан алгоритм реализации предложенного метода «неис-
кажающей» декомпозиции формального контекста. Алгоритм отличается от ра-
нее существующих алгоритмов тем, что разлагает исходный формальный кон-
текст без потери формальных понятий и восстанавливает решение поставленной
задачи исходя из решений, полученных для подзадач.
Методы исследования. Для решения поставленных в диссертационной
работе задач использовались современные методы АФП, теории графов и мето-
ды объектно-ориентированного программирования.
Теоретическая значимость работы. Предложенный в работе метод «неис-
кажающей» декомпозиции формального контекста может быть использован для
развития АФП и комбинаторной оптимизации при решении задач определения
всех максимально полных подматриц 0,1-матрицы.
Практическая значимость работы. Применение результатов диссертаци-
онной работы при исследовании объектно-признаковых описаний предметных
областей позволяет на семантическом уровне решать различные задачи анали-
за данных, включая классификацию, кластеризацию, обнаружение закономерно-
стей в данных и извлечение знаний из решетки формальных понятий. Исследо-
вание естественно-языковых текстов тувинского фольклора в научно-образова-
тельном центре «Тюркология» Тувинского государственного университета с при-
менением предложенных в работе метода и алгоритмов позволяет эффективно
решать филологические и лингвистические задачи в рамках корпуса тувинского
языка.
Соответствие паспорту специальности. Диссертационная работа соот-
ветствует области исследования специальности 05.13.17 — Теоретические ос-
новы информатики по п. 5 «Разработка и исследование моделей и алгоритмов
анализа данных, обнаружения закономерностей в данных и их извлечениях, раз-
работка и исследование методов и алгоритмов анализа текста, устной речи и
изображений» (пункты 1, 2 научной новизны).
Положения, выносимые на защиту.
1. Доказательство корректности метода декомпозиции формального кон-
текста на фрагменты без потери формальных понятий, позволяющего умень-
шить размерность формального контекста и тем самым повысить производи-
тельность известных алгоритмов нахождения всех формальных понятий фор-
мального контекста.
2. Алгоритм реализации предложенного метода «неискажающей» деком-
позиции формального контекста и оценки его сложности, а также рекомендации
по практическому применению этого алгоритма при анализе данных.
3. Комплекс программ для проверки результативности предложенных ме-
тода и алгоритмов на случайных формальных контекстах и на реальных данных
применительно к корпусу тувинского языка.
Степень достоверности и апробация результатов работы. Достоверность
результатов работы подтверждается строгими математическими доказательства-
ми основных положений, экспериментальной проверкой результатов, численных
расчетов на реальных текстовых данных и практической эффективности про-
граммных реализаций.
Основные результаты работы докладывались и обсуждались на III Меж-
дународной научно-практической конференции молодых ученых, аспирантов и
студентов «Актуальные проблемы исследования этноэкологических и этнокуль-
турных традиций народов Саяно-Алтая» (Кызыл, 2015), Международной кон-
ференции студентов, аспирантов и молодых ученых «Молодежь и наука: Про-

1. Разработан и теоретически обоснован метод «неискажающего» разложе-
ния формального контекста на фрагменты (теорема 2.1). Исследована структура
фрагментов и найдена оценка числа фрагментов, получаемых на каждой итера-
ции разложения, определены правила остановки процесса разложения формаль-
ного контекста на фрагменты без потери формальных понятий (предложения 2.1
– 2.6).
2. Разработаны алгоритмы формирования для заданного формального кон-
текста системы фрагментов, восстановления искомого решения исходя из реше-
ний, полученных для подзадач, и реализации возможных запросов на извлечение
знаний из решетки формальных понятий.
3. Разработаны алгоритмы предобработки формального контекста без по-
тери формальных понятий путем удаления единичных, нулевых и кратных строк
и столбцов этого контекста.
4. Создан комплекс программ, реализующий разработанные метод и алго-
ритмы, для проверки их результативности на случайных формальных контекстах
и на реальных данных применительно к корпусу тувинского языка. Эксперимен-
ты показали, что все разработанные в диссертации алгоритмы имеют высокую
вычислительную сложность. Однако на практике при удачном задании значений
k и σ0 возможно построение полиномиального числа |Ω| = p (|G| , |M |) фраг-
ментов. Эксперименты подтверждают, что увеличение числа итераций приводит
к увеличению числа фрагментов, подлежащих дальнейшему разложению, и в
свою очередь к увеличению времени выполнения алгоритмов. Поэтому количе-
ство итераций разложения k рекомендуется задавать значительно меньше, чем
k n/2, где n = |G|, а пороговое значение выбрать из интервала σK < σ0 < 1.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

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

    Читать «Разработка метода и средств фрагментации и дефрагментации формальных контекстов»

    Помогаем с подготовкой сопроводительных документов

    Совместно разработаем индивидуальный план и выберем тему работы Подробнее
    Помощь в подготовке к кандидатскому экзамену и допуске к нему Подробнее
    Поможем в написании научных статей для публикации в журналах ВАК Подробнее
    Структурируем работу и напишем автореферат Подробнее

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Анна Александровна Б. Воронежский государственный университет инженерных технол...
    4.8 (30 отзывов)
    Окончила магистратуру Воронежского государственного университета в 2009 г. В 2014 г. защитила кандидатскую диссертацию. С 2010 г. преподаю в Воронежском государственно... Читать все
    Окончила магистратуру Воронежского государственного университета в 2009 г. В 2014 г. защитила кандидатскую диссертацию. С 2010 г. преподаю в Воронежском государственном университете инженерных технологий.
    #Кандидатские #Магистерские
    66 Выполненных работ
    Анастасия Л. аспирант
    5 (8 отзывов)
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибост... Читать все
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибостроение, управление качеством
    #Кандидатские #Магистерские
    10 Выполненных работ
    Александр Р. ВоГТУ 2003, Экономический, преподаватель, кандидат наук
    4.5 (80 отзывов)
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфин... Читать все
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфинансы (Казначейство). Работаю в финансовой сфере более 10 лет. Банки,риски
    #Кандидатские #Магистерские
    123 Выполненных работы
    Татьяна Б.
    4.6 (92 отзыва)
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские ди... Читать все
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские диссертации, курсовые работы средний балл - 4,5). Всегда на связи!
    #Кандидатские #Магистерские
    138 Выполненных работ
    Александра С.
    5 (91 отзыв)
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повы... Читать все
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повышении уникальности текста и оформлении библиографических ссылок по ГОСТу.
    #Кандидатские #Магистерские
    132 Выполненных работы
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ
    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ
    Олег Н. Томский политехнический университет 2000, Инженерно-эконо...
    4.7 (96 отзывов)
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Явл... Читать все
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Являюсь действующим преподавателем одного из ВУЗов.
    #Кандидатские #Магистерские
    177 Выполненных работ
    Дмитрий К. преподаватель, кандидат наук
    5 (1241 отзыв)
    Окончил КазГУ с красным дипломом в 1985 г., после окончания работал в Институте Ядерной Физики, защитил кандидатскую диссертацию в 1991 г. Работы для студентов выполня... Читать все
    Окончил КазГУ с красным дипломом в 1985 г., после окончания работал в Институте Ядерной Физики, защитил кандидатскую диссертацию в 1991 г. Работы для студентов выполняю уже 30 лет.
    #Кандидатские #Магистерские
    2271 Выполненная работа

    Последние выполненные заказы

    Другие учебные работы по предмету

    Расширенное суперпиксельное представление изображений для их обработки и анализа
    📅 2022 год
    🏢 ФГАОУ ВО «Самарский национальный исследовательский университет имени академика С.П. Королева»
    Метод восстановления динамических изображений на основе оптимальной интерполяции
    📅 2022 год
    🏢 ФГАОУ ВО «Самарский национальный исследовательский университет имени академика С.П. Королева»
    Метод конверсационного анализа неструктурированных текстов социальных сетей
    📅 2021 год
    🏢 ФГАОУ ВО «Самарский национальный исследовательский университет имени академика С.П. Королева»