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

Актуальность темы исследования. Во многих задачах интеллектуально-
го анализа данных, в том числе в анализе естественно-языковых текстов, изуча-
емая предметная область часто описывается в виде объектно-признаковой таб-
лицы, в которой каждый столбец соответствует некоторому признаку, а каждая
строка определяет признаковое описание отдельного объекта [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), Международной кон-
ференции студентов, аспирантов и молодых ученых «Молодежь и наука: Про-