Введение к работе
Актуальность темы исследования. Работа посвящена формальному концептуальному анализу. Во второй половине XX века в совершенно разных и независимых областях исследований возникла необходимость формализации понятий и их связей. В результате исследований было установлено, что нерешённость одной понятийной проблемы порождает сотни ме-тодных проблем, а нерешенность одной методной проблемы порождает сотни ресурсных проблем. Данный факт указывает на особую важность исследования свойств системы понятий той или иной предметной области с целью организации эффективной деятельности человека (или автоматического устройства) в соответствие с этой системой понятий. Задача классификации понятий тесно взаимосвязана с задачей принятия решений, проблемой управления сложными системами, и системного управления в частности. Эти исследования являются основным направлением кафедры концептуального анализа и проектирования (КАиП) факультета инноваций и высоких технологий Московского физико-технического института, которая занимается задачей проектирования организаций инновационного типа. Исследование кибернетических задач обобщения понятий (задача классификации) и распознавания образов послужило началом математизации логики понятий. Известные решения этих задач успешно применяются в вопросах прогнозирования и классификации в химии, астрономии, экономике, геологии и др., а также в системах оперативно-диспетчерского управления энергообъединением, воздушным движением, речными портами и т.п.
В общем виде содержательная постановка задачи распознавания образов возникла в конце 50-х годов прошлого века в связи с исследованиями проблем искусственного интеллекта. Суть этой задачи заключается в необходимости построения машины, способной обучаться классификации ситуаций так же, как это делают живые существа [1]. Такая общая трактовка проблемы привела к возникновению в математической кибернетике следующих направлений: 1) разработка различных подходов к построению моделей процесса восприятия; 2) разработка и анализ алгоритмов обучения распознаванию образов; 3) поиск новых теоретических методов решения задачи распознавания образов.
Первые результаты исследований, полученные в 60-х годах, показали, что усложнение первоначальных общих моделей не позволяет прояснить тонкие эффекты восприятия и построить эффективные алгоритмы распознавания образов. Для развития этой теории необходимо было найти формальную схему задачи обучения распознаванию образов.
Исчерпывающего ответа на вопрос существования единых принципов распознавания образов до сих пор не получено. Поэтому большинство исследователей занимаются конструированием языка описания образов в конкретных областях знаний. Такой подход быстрее даёт результаты, применимые к практике, и под теорией распознавания образов чаще
всего понимается теория минимизации риска в специальном классе решающих правил [2]. В этом направлении можно выделить три составляющих компоненты. Первая связана с постановкой задачи (так называемая элементарная теория). Вторая отражает влияние задач обучения распознаванию образов на развитие аппарата математической статистики (статистические основы теории). Третья отражает развитие конструктивных идей построения алгоритмов (методы разделяющих поверхностей или метод обобщенного портрета).
Задача построения моделей процесса восприятия делиться на две подзадачи. Суть первой подзадачи заключается в формировании понятий, так называемая задача обобщения понятий или задача классификации. Суть второй подзадачи заключается в разработке алгоритмов нахождения понятий (классов), к которым принадлежат рассматриваемые объекты (ситуации), так называемая задача распознавания образов. В основу многих алгоритмов обобщения по признакам положены идеи, впервые высказанные и обоснованные Бонгардом М.М. и его учениками [1, 3]. Например, Бенерджи Р. в [4] описал алгоритмы формирования конъюнктивных и простых понятий. Кочен М. в [5, 6] разрабатал алгоритмы формирования дизъюнктивно-конъюнктивных понятий. Дедуктивные способы построения классификации рассмотрены Вагиным В.Н. в [7]. Подход к задаче классификации на основе теории алгебраических решёток был развит Болдыревым Н.Г. и Чебоксаровой Т.Н. в [8]. Ту Дж., Гонсалес Р. в [9] и Дуда Р., Харт П. в [10] представили одни из первых исследований основных принципов распознавания. В работах Журавлёва Ю.И. и Гуревич Ю.Б [11, 12] разработаны основные модели распознавания, базирующиеся на алгебраическом подходе. Структурные методы распознавания изложили Харалик P.M. и Фу К.С. в работах [13, 15, 16].
Принципиально новый алгебраический подход к задаче классификации понятий разработан на основе теории формального концептуального анализа. Формальный концептуальный анализ был основан в первой половине 80-х годов прошлого столетия представителями немецкой математической школы Вилле Р., Гантером Б., Бурмейстером П., Стумме Г. и др. Введение в формальный концептуальный анализ представлено в работе Вилле Р. [17]. Изложение математических основ формального концептуального анализа наиболее полно представлено в работе Вилле Р. и Ганте-раБ. [19].
Согласно [19] формальный контекст — это структура К = (G,M,I), где G,М — произвольные множества и I <^GxM — бинарное отношение между элементами множеств G и М. Элементы из множеств G и М называются объектами и атрибутами соответственно. В случае, когда (g,m) є I говорят, что объект g имеет атрибут т, или атрибут т присущ объекту g.
Формальный концепт контекста К = (G, М, I) определяется как пара множеств (А, В), где Ac^G — множество объектов с общим множеством
атрибутов йсМ,и каждый атрибут из В присущ всем объектам из множества А. Множества А и В называются соответственно объёмом и содержанием формального концепта (А, В). Теоретико-множественное включение множеств объектов естественно определяет отношение порядка < на множестве концептов по формуле:
(АЪВ1)<(А2,В2)<^А1^А2.
Основные результаты [19] показывают, что множество 9(К) всех формальных концептов контекста К вместе с определённым на нём отношением порядка является полной решёткой.
С одной стороны, многочисленные работы по формальному концептуальному анализу посвящены таким его приложениям, как разработка способов построения решётки формальных концептов (например, работы ГантераБ. [20] и Бурмайстера П. [21]), и приложение формального концептуального анализа к социологии, медицине, биологии и другим областям знаний, так или иначе связанным с обработкой баз данных.
С другой стороны, результатом развития теоретических основ концептуального анализа является создание Вилле Р. в 1990-х концептуальной логики [18] как способа математизации традиционной философской логики средствами концептуального анализа и теории концептуальных графов. В [22] Вилле Р. рассматривает алгебры протоконцептов и концептов, которые положили начало развития булевой концептуальной логики. Геррманн С. Лукш П. Скорски М. и Вилле Р. в [23] осуществляют построение алгебры полу концептов, исследования которой проводятся с помощью введения подходящих булевых алгебр. Интересное исследование топологических свойств метрических контекстов представляет Закареа С. в работе [24].
В основу классического формального концептуального анализа положен одноатрибутный контекст — контекст с множеством атрибутов одного вида. Такой контекст называется моноатрибутным контекстом. Однако математическое моделирование многих прикладных задач приводит к формальным контекстам К =(G;Mi,M2,...,Mn; р) с множеством объектов
G и несколькими множествами атрибутов М\,М2,--;Мп, связь между ко
торыми определяется (п + 1)-арным отношением
p<^GxM\xM2x...xMn. Такой контекст называется полиатрибутным
контекстом.
Классический формальный концептуальный анализ рассматривает только моноатрибутные контексты, поэтому для исследования баз данных с несколькими видами атрибутов в классическом формальном концептуальном анализе разработано преобразование, переводящее базу данных с несколькими разнотипными множествами атрибутов в базу данных с одним множеством атрибутов. Однако это преобразование аннулирует связи между атрибутами исходной базы данных, сохраняя связи только между объектом и каждым из видов атрибутом. Это приводит к потере важной информации об объектах. Поэтому естественно возникает задача переноса
идей формального концептуального анализа моноатрибутного контекста на случай полиатрибутного контекста.
Развитию теории формального концептуального анализа полиатрибутных контекстов посвящена настоящая работа. Главным инструментом исследований этой теории является аппарат алгебры отношений, разработанный Вагнером В.В. в [14]. При этом в качестве основного инструмента настоящей работы используются хорошо известные методы теории реляционных баз данных [25].
Цель работы. Разработать алгебраические методы исследования полиатрибутных контекстов. Исследовать структуру формальных концептов полиатрибутного контекста. Исследовать структуры генераторов формальных концептов полиатрибутного контекста. Изучить связь между структурой концептов и функциональными зависимостями между компонентами полиатрибутного контекста. Исследовать задачу минимизации полиатрибутного контекста при условии абстрактной инвариантности упорядоченного множества его концептов.
Научная новизна и выносимые на защиту положения.
Основные результаты диссертации:
получено решение задачи описания упорядоченных множеств концептов полиатрибутного контекста;
описана структура упорядоченного множества концептов однозначного полиатрибутного контекста;
описана взаимосвязь классического формального концептуального анализа с формальным концептуальным анализом полиатрибутных контекстов;
решена задача описания множества генераторов концепта полиатрибутного контекста;
описан способ минимизации полиатрибутного контекста, при котором сохраняется с точностью до изоморфизма упорядоченное множество концептов исходного контекста.
Все вышеназванные результаты являются новыми.
Научная и практическая ценность работы. Диссертация имеет теоретический характер, её результаты могут быть использованы в алгебраической теории формального концептуального анализа и теории управления сложными системами, а также в теории распознавания образов и в других задачах, связанных с приложениями теории реляционных баз данных.
Апробация работы. Результаты диссертационного исследования докладывались и обсуждались на 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] - [А17]. Работа [А1] опубликована в издании, содержащемся в Перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК.
Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка литературы, включающего 29 наименований. Общий объём диссертации составляет 117 страниц.
