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

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

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 экспертов уже готовы начать работу над твоим проектом!

    Шагали Е. УрГЭУ 2007, Экономика, преподаватель
    4.4 (59 отзывов)
    Серьезно отношусь к тренировке собственного интеллекта, поэтому постоянно учусь сама и с удовольствием пишу для других. За 15 лет работы выполнила более 600 дипломов и... Читать все
    Серьезно отношусь к тренировке собственного интеллекта, поэтому постоянно учусь сама и с удовольствием пишу для других. За 15 лет работы выполнила более 600 дипломов и диссертаций, Есть любимые темы - они дешевле обойдутся, ибо в радость)
    #Кандидатские #Магистерские
    76 Выполненных работ
    Дмитрий Л. КНЭУ 2015, Экономики и управления, выпускник
    4.8 (2878 отзывов)
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    #Кандидатские #Магистерские
    5125 Выполненных работ
    Сергей Е. МГУ 2012, физический, выпускник, кандидат наук
    4.9 (5 отзывов)
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым напра... Читать все
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым направлениям физики, математики, химии и других естественных наук.
    #Кандидатские #Магистерские
    5 Выполненных работ
    Анна Н. Государственный университет управления 2021, Экономика и ...
    0 (13 отзывов)
    Закончила ГУУ с отличием "Бухгалтерский учет, анализ и аудит". Выполнить разные работы: от рефератов до диссертаций. Также пишу доклады, делаю презентации, повышаю уни... Читать все
    Закончила ГУУ с отличием "Бухгалтерский учет, анализ и аудит". Выполнить разные работы: от рефератов до диссертаций. Также пишу доклады, делаю презентации, повышаю уникальности с нуля. Все работы оформляю в соответствии с ГОСТ.
    #Кандидатские #Магистерские
    0 Выполненных работ
    Анна В. Инжэкон, студент, кандидат наук
    5 (21 отзыв)
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссе... Читать все
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссертаций. Работала в маркетинге. Практикующий бизнес-консультант.
    #Кандидатские #Магистерские
    31 Выполненная работа
    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Сергей Н.
    4.8 (40 отзывов)
    Практический стаж работы в финансово - банковской сфере составил более 30 лет. За последние 13 лет, мной написано 7 диссертаций и более 450 дипломных работ и научных с... Читать все
    Практический стаж работы в финансово - банковской сфере составил более 30 лет. За последние 13 лет, мной написано 7 диссертаций и более 450 дипломных работ и научных статей в области экономики.
    #Кандидатские #Магистерские
    56 Выполненных работ
    Анастасия Л. аспирант
    5 (8 отзывов)
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибост... Читать все
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибостроение, управление качеством
    #Кандидатские #Магистерские
    10 Выполненных работ
    Мария А. кандидат наук
    4.7 (18 отзывов)
    Мне нравится изучать все новое, постоянно развиваюсь. Могу написать и диссертацию и кандидатскую. Есть опыт в различных сфера деятельности (туризм, экономика, бухучет... Читать все
    Мне нравится изучать все новое, постоянно развиваюсь. Могу написать и диссертацию и кандидатскую. Есть опыт в различных сфера деятельности (туризм, экономика, бухучет, реклама, журналистика, педагогика, право)
    #Кандидатские #Магистерские
    39 Выполненных работ

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

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