Примеры применения алгебры кортежей в интеллектуальном анализе данных

Размещено на http://www.allbest.ru

ПРИМЕРЫ ПРИМЕНЕНИЯ АЛГЕБРЫ КОРТЕЖЕЙ В ИНТЕЛЛЕКТУАЛЬНОМ АНАЛИЗЕ ДАННЫХ

А.А. Зуенко (zuenko@iimm.kolasc.net.ru)

А.Я. Фридман (fridman@iimm.kolasc.net.ru)

Институт информатики и

математического моделирования

КНЦ РАН, Апатиты

Б.А. Кулик (ba-kulik@yandex.ru)

Институт проблем машиноведения РАН,

Санкт-Петербург

Ключевые слова и выражения: алгебра кортежей, интеллектуальный анализ данных, неоднородная семантическая сеть, формальный анализ понятий алгебра кортеж интеллектуальный сеть семантический

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

Введение

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

Фактическим стандартом обработки данных являются реляционные отношения (реляционная алгебра), с другой стороны, установлено, что предикаты и другие основные объекты интеллектуальных систем (правила, семантические сети и т.д.), традиционно описываемые с помощью формальных систем, также представимы в виде отношений [Russel, 2003]. В связи с этим авторы полагают, что единый математический аппарат для обработки данных и знаний следует разрабатывать на основе теории многоместных отношений, то есть в рамках алгебраического подхода. Однако существующие модели и методы теории отношений (реляционная алгебра, графы и т.д.) малопригодны для задач логического анализа, поскольку не позволяют проводить количественную оценку параметров систем.

Разработанная авторами алгебра кортежей (АК) [Кулик, 2007], [Kulik et al., 2010] реализует общую теорию многоместных отношений, ориентированную на решение задач логического анализа (проверка правильности следствия, анализ гипотез и т.д.). За счет введения простых операций с атрибутами отношений удалось существенно расширить область применения этой алгебры.

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

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

В-третьих, исследованы матричные свойства структур АК. Анализ этих свойств предоставляет дополнительные резервы уменьшения трудоемкости процедур логического вывода. В частности, в D-системах, которые в математической логике соответствуют конъюнктивным нормальным формам (КНФ), выделены специфические подструктуры - бесконфликтные и монотонные блоки, с использованием которых выявлены новые структурные и статистические классы КНФ с полиномиально распознаваемым свойством выполнимости.

Таким образом, АК создает единую методологическую основу для обработки данных и знаний, представленных в виде многоместных отношений. Подробное описание основ АК и ее приложений можно найти в [Kulik et al., 2010], [Зуенко, 2009]. Далее в работе приводятся некоторые сведения из АК и рассматриваются возможности применения АК при решении задач формального анализа понятий (ФАП), а также моделирования неоднородных семантических сетей, поскольку эти способы представления и структурирования знаний опираются на понятие многоместного отношения.

1. Основные понятия алгебры кортежей

В АК определены 4 структуры (C-кортеж, C-система, D-кортеж, D-система) табличного или матрицеподобного типа. Эти структуры носят обобщенное название АК-объекты. Каждая из этих структур компактно представляет некоторое множество элементарных кортежей. Например, рассмотрим структуру С-кортежа. Запись R₁[XYZ] = [A B C] означает, что С-кортеж [A B C] соотносится со схемой отношения [XYZ], при этом AX; BY; CZ и R₁[XYZ] = ABC. Если атрибут в схеме отношения выделен жирным шрифтом, то он трактуется не как отдельный атрибут, а как множество атрибутов. Компоненты АК-объектов являются подмножествами домена соответствующего атрибута. Среди компонент особую роль играют две фиктивные компоненты: - полная компонента, т.е. множество, равное домену некоторого атрибута; используется в C-кортежах и C-системах; - пустое множество используется в D-кортежах и D-системах.

С-система - это таблица, строками которой являются однотипные С-кортежи, которая представляет отношение, равное объединению соответствующих декартовых произведений. Например, С-система

R₂[YZ] = = ({a, d}{a, b})({d}{b, c}).

D-кортежи и D-системы - это дополнения соответственно C-кортежей и С-систем. Они записываются в виде матриц, ограниченных перевернутыми скобками. Дополнением C-системы (С-кортежа) является D-система (D-кортеж) той же размерности, в которой каждая компонента равна дополнению соответствующей компоненты в исходной C-системе (С-кортеже).

С АК-объектами, заданными в одной схеме, можно выполнять любые операции алгебры множеств. Для выполнения операций с АК-объектами, имеющими разные схемы отношений, требуются операции с атрибутами. К ним относятся: 1) переименование атрибутов; 2) перестановка атрибутов; 3) обращение отношений; 4) добавление фиктивного атрибута (+Atr); 5) элиминация атрибута (-Atr). Подробно остановимся на двух последних операциях.

При добавлении фиктивного атрибута в схему отношения добавляется имя нового атрибута, а в АК-объект добавляется новый столбец с фиктивными компонентами (в C-кортежи и в C-системы - фиктивные компоненты “”, а в D-кортежи и D-системы - фиктивные компоненты “”). Это соответствует в логике правилу обобщения.

При элиминации атрибута из АК-объекта удаляется столбец, а из его схемы отношения - соответствующий атрибут. Доказано, что элиминация атрибута X из C-кортежей и C-систем соответствует навешиванию квантора x в соответствующую логическую формулу, а элиминация того же атрибута из D-кортежей и D-систем - навешиванию квантора x.

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

2. АК и неоднородные семантические сети

Понятие неоднородной семантической сети введено Г.С. Осиповым для описания плохо структурированных предметных областей, где знания об индивидах и их взаимосвязях не имеют завершенного вида [Осипов, 2009]. Неоднородной интенсиональной семантической сетью называют алгебраическую систему H = <D, N, R, F>, где D = {D₁, D₂, …, D_n} - семейство непустых множеств; N N - подмножество слов конечной длины над заданным алфавитом; R = {R₁, R₂, …, R_q} - семейство бинарных отношений на N², F = {f₁, f₂, …, f_m} - семейство типизированных функций. Функция f_i имеет тип <, >, где = <k1, k2, …, km>, если она определена на декартовом произведении D_k1 Ч D_k2 Ч … Ч D_km.

Если каждому nN приписать тип , а также e - некоторое подмножество декартова произведения D_k1 Ч D_k2 Ч … Ч D_km (экстенсионал, множество примеров), а затем определить на множестве экстенсионалов E = {e_i} отношения R_i⁺ вместо отношений R_i на N², то полученная конструкция H = <D, E, R⁺, F> называется экстенсиональной неоднородной семантической сетью (ЭНС). ЭНС применяются при организации правдоподобных рассуждений, в частности, в задачах аргументации рассуждений [Осипов, 2009]. Процедуры вывода основаны на том, что элементы в парах из R_i⁺ (элементы множества E) сами имеют некоторую внутреннюю структуру, то есть, по существу, тоже являются отношениями, определенными на множествах из D. Это позволяет выразить отношения R_i⁺ через внутреннюю структуру элементов из E, а также выделить следующие классы отношений: a) отношения структурного сходства, b) ассоциативные и каузальные отношения. Далее приведем определения отношений структурного сходства, а затем перепишем условия этих определений на языке АК.

Пусть e₁, e₂ E, , - примеры e₁, e₂ соответственно.

Определение 1. Отношением R₁ на E называется такое X E², что для всякой пары (e₁, e₂) X имеет место e₁, e₂, что .

Определение 2. Отношением R₂ на E называется такое X E², что для всякой пары (e₁, e₂) X имеет место e₁, e₂ что ?Ш и и .

Определение 3. Отношением R₃ на E называется такое X E², что для всякой пары (e₁, e₂) X имеет место e₁, e₂, что =.

Определение 4. Отношением R₄ на E называется такое X E², что для всякой пары (e₁, e₂) X имеет место e₁, e₂, что ?Ш и ()\? Ш.

Определение 5. Отношением R₅ на E называется такое X E², что для всякой пары (e₁, e₂) X имеет место e₁, e₂, что .

Определение 6. Отношением R₆ на E называется такое X E², что для всякой пары (e₁, e₂) X имеет место e₁, e₂, что .

В [Осипов, 2009] дано естественно-языковое описание этих отношений. Так, например, принадлежность пары событий отношению R₁ означает, что событие e₁ всегда сопровождается событием e₂.

В определениях 1-6 , - это, по сути, элементарные кортежи отношений e₁ и e₂. Результатом пересечения будет общий фрагмент слов и , а под записью понимается, что слово включено в слово (здесь кортежи рассматриваются как слова некоторого языка).

В АК обобщенное отношение включения _G для двух кортежей трактуется иначе: проверка включения кортежа в кортеж производится путем приведения кортежей к одной схеме и проверки вхождения компонент кортежа в соответствующие компоненты кортежа (см. [Kulik et al., 2010]). В связи с этим, на языке АК условия, соответствующие введенным определениям, примут следующий вид:

1. Пусть отношения e₁ и e₂ записаны в виде C-систем E1[XYZ] и E2[Y]. Тогда E1[XYZ]_GE2[Y], причем как атрибуты X, так и атрибуты Z могут отсутствовать.

2. Пусть отношения e₁ и e₂ записаны в виде C-систем E1[XY] и E2[YZ], причем E1[XY] ={E1_i[XY]}, где E1_i[XY] - C-кортежи, составляющие E1[XY]. Тогда для каждого E1_i[XY] должно выполняться условие E1_i[XY] _G E2[YZ] ? Ш, причем атрибуты X и атрибуты Z должны обязательно присутствовать в схемах отношений.

3. Пусть отношения e₁ и e₂ записаны в виде C-систем E1[X] и E2[X]. Тогда E1[X]_GE2[X]? Ш;

4. Пусть отношения e₁ и e₂ записаны в виде C-систем E1[XY] и E2[YZ]. Тогда E1[XY]_GE2[YZ] ? Ш, причем либо атрибут X, либо атрибут Z могут отсутствовать.

5. Пусть отношения e₁ и e₂ записаны в виде C-систем E1[Y]={E1_i[Y]} и E2[XYZ]={E2_j[XYZ]}, где E1_i и E2_j - элементарные кортежи, а в схеме E2 либо атрибуты X, либо атрибуты Y могут отсутствовать. Тогда для каждого E1_i должно существовать E2_j, такое что E2_j[XYZ]_GE1_i[Y].

6. Пусть отношения e₁ и e₂ записаны в виде C-систем E1[XYZ]={E1_i[XYZ]} и E2[Y]={E2_j[Y]}, где E1_i и E2_j - элементарные кортежи, а в схеме E1 либо атрибуты X, либо атрибуты Y могут отсутствовать. Тогда в E1[XYZ] должны существовать элементарные кортежи, которым в E2[Y] соответствуют кортежи E2_j такие, что E1_i[XYZ]_GE2_j[Y].

При проверке условий 1-4 представление отношений e₁ и e₂ в виде множеств С-кортежей позволяет, как показано ниже, существенно снизить трудоемкость операций, производимых над этими отношениями. Для проверки условий 5 и 6 отношения e₁ и e₂ также можно использовать структуры АК - С-системы, разложенные в элементарные кортежи.

3. АК и формальный анализ понятий

В отличие от статистических методов, ФАП позволяет описывать отношения между объектами изучаемых предметных областей в виде решеток формальных понятий [Кузнецов, 2002].

Формальный контекст - это тройка K=(G, M, I), где G - множество объектов, M - множество признаков, I G Ч M - отношение обладания признаком. Пара ?g_i, m_j?? I показывает, что объект g_i обладает признаком m_j. Часто формальный контекст представляют в виде бинарной матрицы, например, такой, как в табл.1.

Табл. 1. Пример формального контекста

При определении формального понятия используются операторы Галуа A' и B'.

Для AG и BM: A' = {m ? M | ?g ? A: gIm}, B'= {g ? G | ?m ? B: gIm}.

Другими словами, A' - множество признаков, которыми обладают все объекты из множества A, B' - множество объектов, которые обладают всеми признаками из множества B.

Определение 7. Формальное понятие (A, B) состоит из множества объектов AG и множества признаков BM, таких что B'=A и A'=B. A называется объемом, а B - содержанием понятия. В матрице контекста формальное понятие представляет собой подматрицу, состоящую из единиц. Например, в табл.1 есть формальное понятие - ([g2, g4], [m2, m3]).

Множество понятий контекста K образуют решетку формальных понятий ?(K), так как создают частичный порядок по вложению объемов понятий и всегда имеют наименьшее и наибольшее по вложению понятия. Находятся такие формальные понятия алгоритмом «замыкай по одному». Функция начинает работать с самого общего формального понятия, которое содержит все объекты и чаще всего ни одного признака. Затем находятся все остальные понятия рекурсивным добавлением признаков.

При помощи алгебры кортежей также можно генерировать понятия, удовлетворяющие определению 7. Для этого необходимо выполнить следующие шаги: 1) выписать в виде С-системы дополнение исходного отношения, заданного бинарной матрицей; 2) обратить эту С-систему (получить соответствующую D-систему); 3) преобразовать полученную D-систему в эквивалентную ей С-систему; 4) исключить дублирование С-кортежей в С-системе. Рассмотрим процесс генерации понятий на основе табл. 1.

После выполнения первого шага получим следующую C-систему К[XY] (X - множество объектов, Y - множество признаков этих объектов):

К[XY]=.

Тогда

[XY] = ,

где каждая компонента есть дополнение соответствующей компоненты С-системы К[XY]. Третий шаг алгоритма, реализуется в соответствии с методами, подробно описанными в [Kulik et al., 2010]:

[XY]=.

После исключения дублирования из результирующей С-системы получаются такие С-кортежи:

[{g₁, g₂, g₄}, {m₃}], [{g₁, g₃}, {m₄}], [{g₃, g₄}, {m₁}], [{g₂, g₄}, {m₂, m₃}], [{g₁}, {m₃, m₄}], [{g₃}, {m₁, m₄}], [{g₄}, {m₁, m₂, m₃}].

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

Далее рассмотрим способы снижения трудоемкости операций над отношениями при их представлении в виде АК-объектов.

4. Преимущества реализации алгоритмов средствами АК

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

При рассмотрении неоднородных семантических сетей в качестве основных операций над отношениями использовались _G (обобщенное пересечение) и _G (обобщенное включение). Из них наиболее трудоемкой является вторая операция.

В табл. 2 приведены различные сочетания АК-объектов и знаком «+» помечены сочетания, для которых алгоритмы выполнения соответствующих операций являются полиномиальными. Пустые клетки соответствуют операциям, имеющим экспоненциальную сложность.

Табл.2. Вычислительная сложность операций

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

Кроме того, как при проверке включения одного АК объекта в другой, в частности, С-кортежа в С-систему, так и при выполнении других трудоемких операций (например, преобразование АК-объекта в альтернативный класс) активно используются матричные свойства АК-объектов. Большинство таких операций сводятся в определению непустоты/пустоты D-систем. Для этого в D-системах выявляются специфические подструктуры - бесконфликтные и монотонные блоки. Если D-система содержит монотонный блок, то она непуста. Если в D-системе выявлен бесконфликтный блок, то значительно снижается размерность задачи определения непустоты D-системы.

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

Заключение

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

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

Благодарности

Работа выполнена при финансовой поддержке РФФИ (проект № 09-07-00066), ОНИТ РАН (проект 2.3 Программы фундаментальных научных исследований) и Президиума РАН (проект 4.3 Программы №3).

Список литературы

[Зуенко, 2009] Зуенко А.А., Фридман А.Я. Развитие алгебры кортежей для логического анализа баз данных с использованием двуместных предикатов // Известия РАН. Теория и системы управления. 2009. №2.

[Кулик, 2007] Кулик Б.А. Обобщенный подход к моделированию и анализу интеллектуальных систем на основе алгебры кортежей // Труды VI Международной конференции «Идентификация систем и задачи управления» SICPRO'07 (Москва, 29 января - 1 февраля 2007 г.). 2007.

[Осипов, 2009] Осипов Г.С. Лекции по искусственному интеллекту. - М.: КРАСАНД, 2009.

[Kulik et al., 2010] Kulik B., Fridman A., Zuenko A., Logical Analysis of Intelligence Systems by Algebraic Method // Sybernetics and Systems 2010: Proceedings of Twentieth European Meeting on Cybernetics and Systems Research (EMCSR 2010), Vienna, Austria, 2010.

[Kuznetsov, 2002] Kuznetsov S. and Obiedkov S. Comparing Performance of Algorithms for Generating Concept Lattices // Journal of Experimental and Theoretical Artificial Intelligence, vol. 14, 2002.

[Russel, 2003] Russel S. and Norvig P. Artificial Intelligence: A Modern Approach. Second edition. - Prentice Hall, 2003.

Размещено на Allbest.ru