Приложения алгебры отношений к формальному концептуальному анализу тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Новиков Валерий Евгеньевич

ПРИЛОЖЕНИЯ АЛГЕБРЫ ОТНОШЕНИЙ К ФОРМАЛЬНОМУ КОНЦЕПТУАЛЬНОМУ АНАЛИЗУ

01.01.09-дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

1 2 МАЙ 2011

Саратов - 2011

Г2к

4845243

Работа выполнена на кафедре геометрии Саратовского государственного университета им. Чернышевского.

Научный руководитель: доктор физико-математических наук,

профессор Молчанов Владимир Александрович

Официальные оппоненты: доктор физико-математических наук,

профессор Кожухов Игорь Борисович

кандидат физико-математических наук, профессор Салий Вячеслав Николаевич

Ведущая организация: Институт проблем точной механики и

управления РАН

Защита состоится "19" мая 2011 г. в 15 час. 30 мин. на заседании диссертационного совета ДМ 212.243.15 при Саратовском государственном университете имени Н.Г.Чернышевского по адресу: 410012, Саратов, ул. Астраханская, 83, СГУ, IX корпус.

С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета им. Н.Г. Чернышевского.

Автореферат разослан ё " апреля 2011 г.

Учёный секретарь диссертационного совета кандидат физико-математических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В общем виде содержательная постановка задачи распознавания образов возникла в конце 50-х годов прошлого века в связи с исследованиями проблем искусственного интеллекта. Суть этой задачи заключается в необходимости построения машины, способной обучаться классификации ситуаций так же, как это делают живые существа [I]. Такая общая трактовка проблемы привела к возникновению в математической кибернетике следующих направлений: 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, М, Г), где G, М— произвольные множества и / cGxM — бинарное отношение между элементами множеств СиМ Элементы из множеств G и М называются объектами и атрибутами соответственно. В случае, когда (g, т)е/ говорят, что объект g имеет атрибут т, или атрибут т присущ объекту g.

Формальный концепт контекста К = (G, М, I) определяется как пара множеств (А, В), где AcG — множество объектов с общим множеством

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

{Ах,Вх)<{А1,В1)<*АхсАг.

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

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

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

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

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

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

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

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

Научная новизна и выносимые на защиту положения.

Основные результаты диссертации:

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

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

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

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

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

Все вышеназванные результаты являются новыми.

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

Апробация работы. Результаты диссертационного исследования докладывались и обсуждались на 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 гг.

Публикации. Основные результаты диссертации опубликованы в работах [AI] - [А17]. Работа [AI] опубликована в издании, содержащемся в Перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК.

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка литературы, включающего 29 наименований. Общий объём диссертации составляет 117 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Формальный контекст — это структура К = (G, (Л/,), р), где G называется множеством объектов, (Л/,) — семейство множеств атрибутов с множеством индексов 1 < i < п, pcGxM|X...xM„ — некоторое («+ 1)-арное отношение. Под словом «контекст» далее будем понимать «полиатрибутный контекст», если нет специального уточнения. В случае, когда (g, т\, тг,..., тп) е р говорят, что объект g имеет систему атрибутов (иь тг,..., т„), или система атрибутов (т(, т2, ..., т„) присуща объекту g.

Для приведения выражений с «-арными отношениям к более компактному виду введём ряд обозначений. Пусть р с М\ х • • • х Л/„ — и-арное отношение. Обозначим п = (1,2, ...,п), Mjj = М\х.---х М п и для произвольных 1 </]<■•■< is < п is ~ (/] ,...JS), x]s - (лг(| ), Mj - M,] x • • • x Mis. В этом случае также записываем is с п. Будем гово-

рить, что ^-система х^ входит в отношение р, если существует «-система хл ер, для которой элементы х^ ,х12,...,луу являются её соответствующими компонентами, что обозначаем х[ с х^. Основные операторы баз данных, такие как проекция, выборка и другие, естественно приводят к следующим обозначениям. Для ¡5, }к с п, а- е М-, X с М^ положим:

Л]к 0)= {У]к е Л/^ | У]к входитв р}, °Н} =е ¿'К £ } > Р]к } = } С/7))>

X] еХ

В случае (и + 1)-арного отношения рсСх Му х...х Л/„ множеству О будет соответствовать нулевой индекс: яо(р) = {хеС | х входитвр},

РО {х1, ) = *0 (°~{х} } (/>)) . Л) (Л = П РО (х1, ) ■

1 х; еХ

'г

Пусть задан контекст К = (С, (Л/,), р). Если для некоторого X ей существует ей, такое что выполняется

Х = р0]к(Х),

то X называется концептом по системе атрибутов ]к. Любое подмножество УсМу для которого выполняется равенство Ро(У) = X будем называть -генератором концепта X, элементы множества X будем называть объектами, элементы множества У—]к -атрибутами или атрибутами концепта X, индекс ]к — индексом генератора или индексом атрибута. Концепты, отличные от 0 и С, будем называть собственными.

В разделе 1.4 установлено, что для контекста К = (С, (М,), р) множество всех концептов по одному и тому же индексу атрибутов с п относительно теоретико-множественного включения образует полную решётку, которая обозначается Ljk (К). Основной результат раздела 1.4 описывает строение упорядоченного множество концептов полиатрибутного контекста.

Теорема 1.6. Для любого контекста К = (С, (МД р) множество концептов, упорядоченное отношением теоретико-множественного включения, является объединением решёток £у (К) (где у* ей) с наибольшим элементом С и наименьшим элементом 0.

Будем говорим, что отношение р с М-р, имеет Г-зависимость для индексов атрибутов , у^ с п и обозначать М/ -» М д , если операция

взятия элементарного среза р^ ^лу ^ определяет отображение проекции

(р) на проекцию (р). Будем говорим, что контекст

К = (С, (А/(), р) однозначен относительно множества объектов, или просто однозначен, если отношение р имеет ^-зависимость С -> . Описание строения упорядоченного множества концептов однозначно го полиатрибутного контекста представлено в разделе 1.3.

Теорема 1.8. Пусть задан однозначный контекст К = (С, (М;), ). Множество всех его концептов относительно упорядоченности по включению образует полную решётку.

В разделе 1.5 установлен характер связи между моноатрибутным и полиатрибутным контекстами. Обозначим С/Р преобразование полиатрибутного контекста К.1 = (б, р) в моноатрибутный контекст К2 = (С,

л л

М, /), определённое правилом: М = иА/;,/= и/Т(0;)^-

¡=1 ;=1

Теорема 1.11. Пусть К] = (<?,'(А/Д /?) — однозначный полиатрибутный контекст и Ь\ — его концептуальная решётка. Пусть Кг = (С, М, I) — моноатрибутный контекст, полученный из К, преобразованием Ь'Р, и Ц — соответствующая концептуальная решётка. Тогда ¿2 £ ¿1, причём в общем случае включение может быть собственным.

Вторая глава посвящена исследованию строения генераторов отдельно взятого концепта полиатрибутного контекста. Пусть задан контекст К = (С, (Л/,), р) и Л"является концептом по атрибуту сп. Множество р^к (X) = Г является наибольшим -генератором концепта X относительно теоретико-множественного включения. Множество всех У'сУ, для которых ро(У') = Х, является множеством всех ]/(-генераторов концепта X. Для исследования задачи распознавания образа особый интерес представляет описание минимальных по включению элементов множества генераторов.

Основной результат раздела 2.4 даёт описание множества генераторов концепта полиатрибутного контекста. Обозначим ?{М) — булева алгебра всех подмножеств множества М.

Теорема 2.26. Пусть задан контекст К = (С, (А/, ), р) и X— концепт по системе атрибутов дсп, Тогда справедливы следующие утверждения:

1) множество всех уд -генераторов концепта X совпадает с объединением фильтров [26] булевой алгебры ^(р]к (X)), содержащих минимальные

-генераторы этого концепта;

2) множество Г° с У является минимальным /д -генератором концепта

X тогда и только тогда, когда для любого у' е У0 выполняется условие

Ро(У°\ {/})**

и для любых у',у" е К0, у' * у", справедливо равенство

ро^Ч/НПРОС^Ь'"})^;

3) если Х\ и Х2 — два концепта, с минимальными у'д -генераторами У]0

и >2° соответственно, то из У® с У;0 следует ^ с , причём обратное включение в общем случае не выполняется.

С целью описания строения системы минимальных генераторов вводится следующее понятие. Множество минимальных у^ -генераторов {У/}/е7* концепта X называется насыщенным, если объединение и У, не

/еГ

включает минимального Уд -генератора, не присутствующего в множестве КЬеТ-

Описание структуры насыщенных множеств минимальных генераторов концепта полиатрибутного контекста даёт следующий результат раздела 2.4.

Теорема 2.25. Пусть задан контекст К = ((7, (А/; ), р) и X— концепт по системе атрибутов уд ей. Тогда справедливы следующие утверждения:

1) множество минимальных -генераторов {У, концепта X является насыщенным тогда и только тогда, когда для любого семейства {уА/еТ элементов у; е У( выполняется условие

2) множество всех насыщенных множеств минимальных уд -генераторов концепта X с элементом 0 относительно теоретико-множественного включения образует решётку;

3) насыщенное множество минимальных -генераторов {У, концепта X является максимальным тогда и только тогда когда для любого семейства {д^ЬеГ элементов ус е У, выполняется условие

Про^Ч^})**.

/еГ

Третья глава работы посвящена задаче минимизации полиатрибутного контекста. В разделе 3.3 установлена связь между функциональными зависимостями в полиатрибутном контексте и структурой его концептов. Теорема 3.25. Пусть задан контекст К = (С, (Л/,), р) и отношениеримеет ^-зависимость Л/у- —> М ^, си. Тогда каждый концепт по 1Ц со-

держится в некотором концепте по ]к, и каждый концепт по }к является объединением некоторых концептов по 1д.

Для отношения р с M-tl F-зависимость Mj -^М^ , lq,jk с:п, будем называть В-зависгшостью, если определяемое этой зависимостью отображение pjk({xj }): щ (р) -» n-jk (р) является взаимно однозначным.

Связь между В-зависимостью и структурой концептов полиатрибутного контекста установлена в основном результате раздела 3.4. Теорема 3.26. Пусть задан контекст К = (С, (А/,), р) и отношение римеет ^-зависимость Mj —> М jk (lq,jk с«). Тогда множество концептов по jf.

совпадает с множеством концептов по 1д.

Если \xj (р) | =! 7zjk (р) то существование В-зависимости А/г —> М 7 можно проверить модифицированным алгоритмом satisfies

^ у л

[25]. Другие S-зависимости можно вывести с помощью следующих свойств:

1. Для любого /¿с Я имеет место В-зависимость Л/ ^ -> Л/у (рефлексивность).

2. Для любых ]к, Igcfi, из существования .В-зависимости Mj Л/у^ следует существование В-зависимости А/;, —> Л/г (симметричность).

3. Для любых ¡7/,~jk,lq с из существования В-зависимостей Mj Мjk

и Mjk—>M„t следует существование В-зависимости Mj —> Л/^

(транзитивность).

Таким образом, В-зависимость определяет абстрактное отношение эквивалентности на множестве индексов атрибутов с Я, которое разбивает это множество на классы индексов атрибутов с одинаковыми множествами концептов. Это разбиение является главным инструментом в алгоритме минимизации полиатрибутного контекста, который описан в разделе

Четвёртая глава посвящена описанию структуры концептов однозначного контекста. Основной результат раздела 4.1 устанавливает основные характеристики решётки концептов однозначного контекста и описывает её антицепи [26].

Теорема 4.4. Пусть задан однозначный контекст К = (С, Л/;-, /?) и

,}р с п. Тогда справедливы следующие утверждения: 1) множество собственных концептов по ур образует разбиение множест-

3.4.

ва я"о(/с), которое обозначается 7Tq 2) если с jр, то подразбиение разбиения jtq

3) если ХР,Х<! сС —два собственных концепта по )р, 1д соответственно, и у 7 ,ут — их одноэлементные генераторы максимального индек-

■> Р с/

са, то условие >у с у^ равносильно включению Хр с Xя;

4) если концепт X в решётке концептов не является атомом, то X покрывает не менее двух концептов;

5) высота решётки концептов ¿(К) не превосходит значения тт{« + 1, \71(){р)\и ширина этой решётки не превосходит значения

Автор выражает глубокую благодарность научному руководителю профессору Молчанову Владимиру Александровичу за постановку задач и поддержку в исследованиях.

СПИСОК ЛИТЕРАТУРЫ

1. Бонгард М.М., Проблема узнавания. М.: Наука, 1967.

2. Вапник В.Н., Червоненкис А.Я., Теория распознавания образов. М.: Наука, 1974.

3. Лосев И.С., Максимов В.В. О задаче обобщения начальных ситуаций // Моделирование обучения и поведения/ Под ред. М.С. Смирнова. - М.: Наука, 1975.

4. Бенерджи Р. Теория решения задач. - М.: Мир, 1972. - 224с.

5. Кочен М. (Kochen М.) An experimental program for the selection of "disjunctive hypothesis"// Proceedings of Western Joint Computer Conference. -1961.

6. Кочен M. (Kochen M.) Experimental study of "hypothesis - formation" by computer // Information Theory, IY London Symposium. - London; Washington, 1961.

7. Вагин B.H. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988.-383с.

8. Болдырев Н.Г., Чебоксарова Т.Н. Алгебраический подход к проблеме классификации // Изв. АН СССР Техническая кибернетика. - М. -1977. №2.-С. 207-212.

9. Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир, 1980.-411с.

10. Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир,

1976.-511с.

11. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. - 1978. - Вып. 33.-С.4-68.

12. Гуревич Ю.Б., Журавлёв Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика. - 1974. Вып. 3. -С. 16-20.

13. Фу К.С. Структурные методы в распознавании образов. - М.: Мир,

1977.-319с.

14. Вагнер В. В. Теория отношений и алгебра частичных отображений И Теория полугрупп и её приложения. Саратов: Изд-во Сарат. ун-та, 1965. Вып.1. С. 3 - 178.

15. Харалик P.M. (Haralick R.M.) Structural Pattern Recognition, Homomor-phisms and Arrangements // Pattern Recognition. - 1978. - V. 10, №3.

16. Харалик P.M. (Haralick R.M.) Structural Pattern Recognition, Arrangements and Theory of Covers // Proc IEEE Comput. Soc. Conf. "Pattern Recognition and Image Process". - Tray, N.Y. - 1977.

17. Wille R. Introduction to Formal Concept Analysis. Darmstadt, Technische Hochschule, 1996.

18. Wille R. Contextual Logic Summery. Darmstadt, Technische Universität, FB04, Preprint, 2000.

19. Ganter В., Wille R. Formal Coneept Analysis. Mathematical Foundations. Springer Verlag, 1999.

20. Ganter B. Algorithmen zur Begriffsanalyse. In: B. Ganter, R. Wille, K.E. Wolff (eds.): Beiträge zur Begriffsanalyse. B.I. - Wissenschaftsverlag, Mannheim, Wien, Zürich 1987, 241-254.

21. Burmeistcr P. Comlmp - Ein Programm zur Formalen Begriffsanalyse. In G. Stumme and R. Wille (eds.) Begriffliche Wissensverarbeitung. Methoden und Anwendungen, Springer Verlag, 2000, 25-56.

22. Wille R. Boolean Coneept Logic. Darmstadt, Technische Universität, Preprint, 2000.

23. Herrmann C., Luksch Р., Skorsky M., Wille R. Algebras of Semiconcepts and Double Boolean Algebras. Darmstadt, Technische Universität, 2000.

24. Säcärea C. Towards a Theory of Contextual Topology. Shaker Verlag Aachen 2001.

25. Maier, D. The Theory of Relation Databases. Oregon Graduate Center,

1983 Computer Science Press, Inc. Рус. перевод: Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.

26. Биркгоф Г. Теория решёток. Пер. с англ. - М.: Наука. Главная редакция физико-математической литературы, 1984. - 568 с.

Публикации автора по теме диссертации

AI. Новиков В.Е. Теоретико-множественный подход к структуре генераторов концепта // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2009. Т. 9, вып. 3. С. 50 - 56. А2. Новиков В.Е. Формальный концептуальный анализ на контексте с парным отношением// Вестник Саратовского государственного технического университета. №3(15) 2006.Вып. 2. С. 17 - 22. A3. Новиков В.Е. Решётки понятий «-арных отношений// Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2002. Вып. 4. С. 111 -113.

A4. Новиков В.Е. О системах замыкания на и-арных отношениях. Гос. ун-т. - Саратов, 2002. -12с. - Библиогр.: 4 назв. - Рус. - Деп. в ВИНИТИ 17.04.02, № 717-В2002. А5. Новиков В.Е. Спектр понятий на и-арных отношениях // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2003. Вып. 5. С. 81-84.

А6. Новиков В.Е. Спектральный анализ понятий на и-арных отношениях. Гос. ун-т. - Саратов, 2003. -21с. - Библиогр.: 5 назв. - Рус. - Деп. в ВИНИТИ 07.10.03, № 1772-В2003. А7. Новиков В.Е. Определения понятий на и-арных отношениях. Гос. ун-т. - Саратов, 2004. -15с. - Библиогр.: 8 назв. - Рус. - Деп. в ВИНИТИ 17.02.04, № 266-В2004.

А8. Novikov V.E. Ordered set of concepts in n-ary relation // Summaries of talks, AAA68 Workshop on General Algebra, Dresden, Dresden University of Technology, Germany, 2004, P.37-38.

A9. Новиков B.E. О решётке понятий частично однозначных отношений // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. С. 102 - 105.

А10. Новиков В.Е. Генераторы концептов в проблеме распознавания образов// Проблемы теоретической кибернетики: тезисы докладов XIV Международной конференции. Москва: Изд-во мех.-мат. фак-та МГУ, 2005, С. 107.

All. Новиков В.Е. О концептуальном анализе на контексте с многомерными атрибутами // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2005. Вып. 7. С. 82 - 85.

А12. Новиков В.Е. Насыщенные семейства минимальных генераторов концепта // Математика. Механика: Сб. науч.тр. - Саратов: Изд-во Сарат. ун-та, 2006. - Вып.8. - С.99-102. - ISSN 1609-4751.

А13. Новиков В.Е. Концепты и функциональные зависимости // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2007. Вып. 9. С. 68 - 70.

А14. Новиков В.Е. Семейства минимальные по пересечению // Современные проблемы дифференциальной геометрии и общей алгебры: тезисы докладов международной научной конференции, посвященной 100-летию В.В. Вагнера. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 10. С. 124- 127.

Al5. Новиков В.Е. Функциональные зависимости в формальном контексте // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2008. Вып. 10. С. 53 -55.

Al 6. Новиков В.Е. Связь между решётками контекстов с бинарным и парным отношениями // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2009. Вып. 11. С. 38 - 41.

Al 7. Новиков В.Е. Решётки концептов в однозначном контексте // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2010. Вып. 12. С. 52-55.

Подписано в печсть 15.04.2011. Формат 60x84 1/16. Бумага Офсетная. Печать офсетная. Усл. п.л. 0,93 Тираж 100 экз. Заказ № 258.

Отпечатано в типографии «Новый ветер», г. Саратов, ул. Б.Казачья, 113.

Введение.

1. Полиатрибутный контекст.

1.1. Основные понятия алгебры отношений.

1.2. Полиатрибутный контекст.

1.3. Однозначный полиатрибутный контекст.

1.4. Структура множества всех концептов полиатрибутного контекста.

1.5. Связь между моноатрибутным и полиатрибутным контекстами.

2. Генераторы концептов.

2.1. Семейства минимальные по пересечению.

2.2. Насыщенные множества минимальных семейств.

2.3. ^-минимальные семейства.

2.4. Генераторы концепта.

2.5. Задача диагностики и принятия решения.

3. Анализ и минимизация контекста.

3.1. Спектральный анализ контекста с унарным отношением.

3.2. Спектральный анализ контекста с бинарным отношением.

3.3. Функциональные зависимости в формальном контексте.

3.4. ^-зависимости и минимизация контекста.

4. Генераторы в однозначном контексте.

4.1. Анализ решётки концептов однозначного контекста.

4.2. Генераторы концептов в однозначном контексте.

4.3. Соответствие Галуа в однозначном контексте.

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

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

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

1. Бенерджи Р. Теория решения задач. М.: Мир, 1972. - 224с.

2. Биркгоф Г. Теория решёток. Пер. с англ. М.: Наука. Главная редакция физико-математической литературы, 1984. - 568 с.

3. Болдырев Н.Г., Чебоксарова Т.Н. Алгебраический подход к проблеме классификации // Изв. АН СССР Техническая кибернетика. М. - 1977. -№2. - С. 207-212.

4. Бонгард М.М., Проблема узнавания. М.: Наука, 1967.

5. Вагин В.Н. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988.-383с.

6. Вагнер В. В. Теория отношений и алгебра частичных отображений // Теория полугрупп и её приложения. Саратов: Изд-во Сарат. ун-та, 1965. ВыпЛ.С. 3-178.

7. Вапник В.Н., Червоненкис А .Я., Теория распознавания образов. М:: Наука, 1974.

8. Гмурман. В.Е. Введение в теорию вероятностей и математическую статистику. М.: Высшая школа, 1966.

9. Гретцер Г. Общая теория решёток. Пер. с англ./ Под редакцией Д.М. Смирнова. М.: Мир, 1981. - 456 с.

10. Ю.Гуревич Ю.Б., Журавлёв Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика. 1974. Вып. 3. - С. 1620.

11. П.Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. -511с.

12. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. - Вып. 33. - С. 4-68.

13. Лосев И.С., Максимов B.Bl О задаче обобщения начальных ситуаций // Моделирование обучения и поведения/ Под ред. М.С. Смирнова. М.: Наука, 1975.

14. Н.Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.

15. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. М.: Наука, 1991.

16. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1980. -411с.

17. Фу К.С. Структурные методы в распознавании образов. -М.: Мир, 1977. -319с.

18. Burmeister Р. Comlmp Ein Programm zur Formalen Begriffsanalyse. In G. Stumme and R. Wille (eds.) Begriffliche Wissensverarbeitung. Methoden und Anwendungen, Springer Verlag, 2000,25-56.

19. Ganter B. Algorithmen zur Begriffsanalyse. In: B. Ganter, R. Wille, K.E. Wolff (eds.):.Beiträge zur Begriffsanalyse. B.I. Wissenschaftsverlag, Mannheim, Wien, Zürich 1987, 241-254.

20. Ganter В., Wille R. Formal Concept Analysis. Mathematical Foundations. Springer Verlag, 1999.

21. Haralick R.M. Structural' Pattern Recognition, Arrangements and Theory of Covers И Proc IEEE Comput. Soc. Conf. "Pattern Recognition and.Image Process".-Tray, N.Y.- 1977.

22. Haralick R.M. Structural Pattern Recognition, Homomorphisms and Arrangements // Pattern Recognition. 1978. - V.10, №3.

23. Herrmann C., Luksch P., Skorsky M., Wille R. Algebras of Semiconcepts and-Double Boolean Algebras. Darmstadt, Technische Universität, 2000.

24. Kochen M. An experimental program for the selection of "disjunctive hypothesis"// Proceedings of Western Joint Computer Conference. -1961.

25. Kochen M. Experimental study of "hypothesis formation" by computer // Information Theory, IY London Symposium. — London; Washington, 1961.

26. Säcärea С. Towards a Theory of Contextual Topology. Shaker Verlag Aachen 2001.

27. Wille R. Boolean Concept Logic. Darmstadt, Technische Universität, Preprint, 2000.

28. Wille R. Contextual Logic Summery. Darmstadt, Technische Universität, FB04, Preprint, 2000.

29. Wille R. Introduction to Formal Concept Analysis. Darmstadt, Technische Hochschule, 1996.

30. Публикации автора по теме диссертации

31. А6. Новиков В.Е. Спектральный анализ понятий на «-арных отношениях. Гос. ун-т. Саратов, 2003. -21с. - Библиогр.: 5 назв. - Рус. — Деп. в ВИНИТИ 07.10.03, № 1772-В2003.

32. А10. Новиков В.Е. Генераторы концептов в проблеме распознавания образов// Проблемы теоретической кибернетики: тезисы докладов XIV Международной конференции. Москва: Изд-во мех.-мат. фак-та МГУ,2005, С. 107.