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

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

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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.6 (30 отзывов)
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации... Читать все
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации. Опыт работы 7 лет. Всегда на связи и готова прийти на помощь. Вместе удовлетворим самого требовательного научного руководителя. Возможно полное сопровождение: от статуса студента до получения научной степени.
    #Кандидатские #Магистерские
    47 Выполненных работ
    AleksandrAvdiev Южный федеральный университет, 2010, преподаватель, канд...
    4.1 (20 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    28 Выполненных работ
    Петр П. кандидат наук
    4.2 (25 отзывов)
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт напис... Читать все
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт написания магистерских диссертаций. Направление - связь, телекоммуникации, информационная безопасность, информационные технологии, экономика. Пишу научные статьи уровня ВАК и РИНЦ. Работаю техническим директором интернет-провайдера, имею опыт работы ведущим сотрудником отдела информационной безопасности филиала одного из крупнейших банков. Образование - высшее профессиональное (в 2006 году окончил военную Академию связи в г. Санкт-Петербурге), послевузовское профессиональное (в 2018 году окончил аспирантуру Уральского федерального университета). Защитил диссертацию на соискание степени "кандидат технических наук" в 2020 году. В качестве хобби преподаю. Дисциплины - сети ЭВМ и телекоммуникации, информационная безопасность объектов критической информационной инфраструктуры.
    #Кандидатские #Магистерские
    33 Выполненных работы
    Анна К. ТГПУ им.ЛН.Толстого 2010, ФИСиГН, выпускник
    4.6 (30 отзывов)
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помог... Читать все
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помогала студентам, вышедшим на меня по рекомендации.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Анна Н. Государственный университет управления 2021, Экономика и ...
    0 (13 отзывов)
    Закончила ГУУ с отличием "Бухгалтерский учет, анализ и аудит". Выполнить разные работы: от рефератов до диссертаций. Также пишу доклады, делаю презентации, повышаю уни... Читать все
    Закончила ГУУ с отличием "Бухгалтерский учет, анализ и аудит". Выполнить разные работы: от рефератов до диссертаций. Также пишу доклады, делаю презентации, повышаю уникальности с нуля. Все работы оформляю в соответствии с ГОСТ.
    #Кандидатские #Магистерские
    0 Выполненных работ
    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ
    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы
    Антон П. преподаватель, доцент
    4.8 (1033 отзыва)
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публик... Читать все
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публикуюсь, имею высокий индекс цитирования. Спикер.
    #Кандидатские #Магистерские
    1386 Выполненных работ
    Вирсавия А. медицинский 1981, стоматологический, преподаватель, канди...
    4.5 (9 отзывов)
    руководитель успешно защищенных диссертаций, автор около 150 работ, в активе - оппонирование, рецензирование, написание и подготовка диссертационных работ; интересы - ... Читать все
    руководитель успешно защищенных диссертаций, автор около 150 работ, в активе - оппонирование, рецензирование, написание и подготовка диссертационных работ; интересы - медицина, биология, антропология, биогидродинамика
    #Кандидатские #Магистерские
    12 Выполненных работ

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

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