Приложения алгебры отношений к формальному концептуальному анализу

Актуальность темы

исследования. Работа посвящена формальному концептуальному анализу. Во второй половине XX века в совершенно разных и независимых областях исследований возникла необходимость формализации понятий и их связей. В результате исследований было установлено, что нерешённость одной понятийной проблемы порождает сотни методных проблем, а нерешенность одной методной проблемы порождает сотни ресурсных проблем. Данный факт указывает на особую важность исследования свойств системы понятий той или иной предметной области с целью организации эффективной деятельности человека (или автоматического устройства) в соответствие с этой системой понятий. Задача классификации понятий тесно взаимосвязана с задачей принятия решений, проблемой управления сложными системами, и системного управления в частности. Эти исследования являются основным направлением кафедры концептуального анализа и проектирования (КАиП) факультета инноваций и высоких технологий Московского физико-технического института, которая занимается задачей проектирования организаций инновационного типа.

Исследование кибернетических задач обобщения понятий (так называемая задача классификации) и распознавания, образов послужило началом математизации логики понятий. Известные решения этих задач успешно применяются в вопросах прогнозирования и классификации в химии, астрономии, экономике, геологии и др., а также в системах оперативно-диспетчерского управления энергообъединением, воздушным движением, речными портами и т. п.

В общем виде содержательная постановка задачи распознавания образов возникла в конце 50-х годов прошлого века в связи с исследованиями проблем искусственного интеллекта. Суть этой задачи заключается в необходимости построения машины, способной обучаться классификации, ситуаций так же, как это делают живые существа [4]. Такая общая трактовка проблемы привела к возникновению в математической кибернетике следующих направлений: 1) разработка различных подходов к построению моделей процесса восприятия- 2) разработка и анализ алгоритмов обучения распознаванию образов- 3) поиск новых теоретических методов решения задачи распознавания образов.

Первые результаты исследований, полученные в 60-х годах, показали, что усложнение первоначальных общих моделей не позволяет прояснить тонкие эффекты восприятия и построить эффективные алгоритмы распознавания образов. Для развития этой теории необходимо было найти формальную схему задачи обучения распознаванию образов.

Исчерпывающего ответа на вопрос существования единых принципов распознавания образов до сих пор не получено. Поэтому большинство исследователей занимается конструированием языка описания образов в конкретных областях знаний. Такой подход быстрее даёт результаты, применимые к практике, и под теорией распознавания образов чаще всего понимается1 теория минимизации риска принятия решениям специальном классе решающих правил [7]. В этом направлении можно выделить три составляющих части. Первая связана с постановкой задачи (так называемая элементарная теория). Вторая отражает влияние задач обучения распознаванию образов на развитие аппарата математической статистики (статистические основы теории). Третья отражает развитие конструктивных идей построения алгоритмов, (методы разделяющих поверхностей или метод обобщенного портрета).

Задача построения моделей процесса восприятия делиться на две подзадачи. Суть первой подзадачи заключается в формировании понятий-— это так называемая задача обобщения понятий или задача классификации. Суть второй подзадачи заключается в разработке алгоритмов нахождения понятий (классов), к которым принадлежат рассматриваемые объекты (ситуации) — это так называемая задача распознавания образов. В основу многих алгоритмов обобщения по признакам положены идеи, впервые изложенные Бонгар-дом М.М. и его учениками [4, 13]. Например, Бенерджи Р. в [1] описал алгоритмы формирования конъюнктивных и простых понятий. Кочен М. в [24, 25] разработал алгоритмы формирования дизъюнктивно-конъюнктивных понятий. Дедуктивные способы построения классификации рассмотрены Ваги-ным В.Н. в [5]. Подход к задаче классификации на основе теории алгебраических решёток был разработан Болдыревым Н. Г. и Чебоксаровой Т. Н. в [3]. Ту Дж., ГонсалесР. в [16] и Дуда Р., Харт П. в [11] представили результаты исследования основных принципов распознавания. В работах Журавлёва Ю. И. и Гуревич Ю. Б [12, 10] разработаны основные модели распознавания, базирующиеся на алгебраическом подходе. Структурные методы распознавания изложили Харалик P.M. и Фу К. С. в работах [17, 21, 22].

Формальный концептуальный анализ. Принципиально новый алгебраический подход к задаче классификации понятий разработан на основе теории формального концептуального анализа. Формальный концептуальный анализ был основан в первой половине 80-х годов прошлого столетия представителями немецкой математической школы Вилле Р., ГантеромБ., Бур-мейстером П., Стумме Г. и др.

Введение

в формальный концептуальный анализ представлено в работе Вилле Р. [29]. Изложение математических основ формального концептуального анализа наиболее полно представлено в работе Вилле Р. и Гантера Б. [20]:

Согласно [20] формальный контекст — это структура К = (G, М, Г), где G, М — произвольные множества и / с: GxM — бинарное отношение между элементами множеств G и М. Элементы из множеств G и М называются объектами и атрибутами соответственно. В случае, когда (g, m) е I говорят, что объект g имеет атрибут т, или атрибут т присущ объекту g.

Формальный концепт контекста К = (G, M, I) определяется как пара множеств (А, В), где AczG — множество объектов с общим множеством атрибутов В сМ, и каждый атрибут из В присущ всем объектам из множества А. Множества, А я В называются соответственно объёмом и содержанием формального концепта (А, В). Теоретико-множественное включение множеств объектов естественно определяет отношение порядка < на множестве концептов по формуле:

АЪВ{) <(Л2,В2) <*Ах с А2.

Следующие производные операторы определены для произвольных и 7сМ:

X —> X' = {т е М^, т) е.1 для всех geX}, У —" V = е <7|^, т) е/ для всех те Г}. Таким образом, формальный концепт формального контекста К = ((?, М, /) это пара (А, В), где^сб, В^М, А = В', и? = .4';

Основные результаты [20] показывают, что множество 9?(К) всех формальных концептов контекста К вместе с определённым на нём отношением порядка является полной решёткой.

В настоящее время формальный концептуальный анализ развивается как в направлении его практических приложений, так и в направление дальнейших теоретических исследований. С одной стороны, многочисленные работы по формальному концептуальному анализу посвящены таким его приложениям, как разработка способов построения решётки формальных концептов (например, работы ГантераБ. [19] и Бурмайстера П. [18]) и приложение формального концептуального анализа, к социологии, медицине, биологии и другим областям знаний, так или иначе связанным" с обработкой баз данных.

С другой стороны, результатом развития теоретических основ концептуального анализа является создание Вилле Р. в 1990;х концептуальной логики [28] как способа математизации традиционной* философской логики средствами концептуального анализа и теории концептуальных графов. В [27] Вилле Р. рассматривает алгебры протоконцептов и концептов, которые положили начало развития булевой концептуальной логики. Геррманн С., ЛукшП., СкорскиМ. и Вилле Р. в [23] построили алгебру полуконцептов, исследования которой проводятся с помощью введения подходящих булевых алгебр. Интересное исследование топологических свойств метрических контекстов представляет Закареа С. в работе [26].

В основу классического формального концептуального анализа положен одноатрибутный контекст — контекст с множеством атрибутов одного вида. Такой контекст называется моноатрибутным контекстом. Однако математическое моделирование многих прикладных задач приводит к формальным контекстам К =(Сг М, М2,., Мп р) с множеством объектов <7 и несколькими множествами атрибутов М^, М2,., Мп, связь между которыми определяется (п + 1)-арным отношением рсСх М х М^ х. х Мп. Такой контекст называется полиатрибутным контекстом.

Так как классический формальный концептуальный анализ рассматривает только моноатрибутные контексты, то для исследования баз данных с несколькими видами атрибутов в классическом формальном концептуальном анализе разработаны стандартные преобразования, переводящие базу данных с несколькими разнотипными множествами атрибутов в базу данных с одним множеством атрибутов. Однако эти стандартные преобразования аннулируют связи между атрибутами исходной базы данных, сохраняя связи только между объектом и каждым из видов атрибутом. Это приводит к потере важной информации об объектах и концептах. Поэтому естественно возникает задача переноса идей формального концептуального анализа моноатрибутного контекста на случай полиатрибутного контекста.

Развитию теории формального концептуального анализа полиатрибутных контекстов посвящена настоящая работа. Главным инструментом исследований этой теории является аппарат алгебры отношений, разработанный Вагнером В. В. в [6]. При этом в качестве основного инструмента настоящей работы используются хорошо известные методы теории реляционных баз данных [14].

В начале первой главы работы приводятся основные понятия алгебры отношений, необходимые для последовательного развития теории формального концептуального анализа полиатрибутных контекстов. В первом разделе главы исследуются основные свойства операторов на «-арных отношениях, используемые в дальнейшем изложении. Центральное место этого раздела занимает исследование свойств дуального среза.

В разделе 1.2 проведено исследование структуры концептов произвольного полиатрибутного контекста. Показано, что множество концептов такого контекста представляет собой упорядоченное множество, являющееся объединением решёток концептов по фиксированным индексам атрибутов. В разделе 1.3 доказано, что это упорядоченное множество концептов полиатрибутного контекста является решёткой, если контекст однозначен относительно множества объектов.

В последнем разделе первой главы проведено исследование взаимосвязи классического формального концептуального анализа с концептуальным анализом полиатрибутного контекста.

Вторая глава посвящена исследованию структуры генераторов концепта. Для этого в разделах 2.1, 2.2. и 2.3 разрабатывается вспомогательный математический аппарат конечных семейств минимальных по пересечению. Результаты этих разделов являются главным инструментов в разделе 2.4 при описании структуры генераторов концепта полиатрибутного контекста. Последний раздел этой главы посвящен краткому обзору возможных приложений исследуемых понятий в задаче диагностики и принятия решения.

Третья глава посвящена поиску способов минимизации полиатрибутного контекста. В разделах 3.1 и 3.2 исследуется концептуальный спектр семейства контекстов с одним и тем же отношением. В частности для случая унарного и бинарного отношений установлен критерий совпадения концептуальных спектров двух семейств контекстов с одним и тем же отношением.

В разделах 3.3 и 3.4 проведено исследование взаимосвязи функциональных зависимостей атрибутов контекста и структуры его концептов. Установленные в этом исследовании результаты стали главным инструментом в решении задачи минимизации арности отношения в контексте при сохранении структуры его концептов. На основе полученных результатов в конце раздела 3.4 приведено описание способа минимизации контекста.

Последняя глава посвящена исследованию решётки концептов однозначного контекста. Установлены основные характеристики этой решётки. Проведено исследование структуры индексов генераторов концепта однозначного контекста. Установлена связь Галуа между структурой’индексов генераторов и структурой концептов однозначного контекста.

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

Сделаем несколько замечаний технического характера. Основная информация о понятиях и обозначениях, систематически используемых в диссертации, даётся в разделе «Основные понятия алгебры отношений». Нумерация теорем, лемм и предложений в диссертации сквозная с учётом главы, нумерация рисунков сквозная, нумерация формул по главам. Например, ссылка «предложение 2.12» означает предложение 2.12 из главы 2.

Результаты диссертационного исследования докладывались и обсуждались на IV Международной научно-технической конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов», Ульяновск, 2001; международной конференции ААА68 (Arbeitstagung Allgemeine Algebra) Workshop on General Algebra, Dresden, Dresden University of Technology, Germany, 2004; межвузовской научной конференции «Компьютерные науки и информационные технологии», Саратов, 2004; XIV Международной конференции «Проблемы Теоретической кибернетики» посвященной 80-летию со дня рождения С. В. Яблонского, Пенза, 2005; международной научной конференции «Современные проблемы дифференциальной геометрии и общей алгебры», посвященной 100-летию со дня рождения профессора В. В. Вагнера, Саратов, 2008; ежегодных конференциях мех.-мат. факультета СГУ «Актуальные проблемы математики и механики» в 2002 — 2010 гг.

Заключение

.

Проведённые в диссертации исследования показывают, что полиатрибутный контекст несёт достаточно полную информацию о концептуальных свойствах множества объектов и позволяет использовать эффективный инструментарий реляционных баз данных для построения и описания структуры концептов. Это подтверждается следующими основными результатами диссертационной работы:

1) получено решение задачи описания упорядоченных множеств концептов полиатрибутного контекста;

2) описана структура упорядоченного множества концептов однозначного полиатрибутного контекста;

3) описана взаимосвязь классического формального концептуального анализа с формальным концептуальным анализом полиатрибутных контекстов;

4) решена задача описания множества генераторов концепта полиатрибутного контекста;

5) описан способ минимизации полиатрибутного контекста, при котором-сохраняется" с точностью до изоморфизма упорядоченное множество концептов исходного контекста.

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

Диссертация имеет теоретический характер, её результаты могут быть использованы в алгебраической теории формального концептуального анализа и теории управления сложными системами, а также в теории распознавания образов и в других задачах, связанных с приложениями теории реляционных баз данных.