birmaga.ru
добавить свой файл

1
МИНИМИЗАЦИЯ ОДНОЗНАЧНОГО КОНТЕКСТА


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

Будем говорить, что задан формальный полиатрибутный контекст K = (G, (), ), если заданы G — непустое конечное множество объектов, () — семейство непустых конечных множеств атрибутов с множеством индексов 1  i  n, — некоторое (n1)-арное отношение. При n = 1 получаем контекст K = (GM), где бинарное отношение. Этот случай формального контекста был введён в первой половине 80-х годов прошлого столетия представителями немецкой математической школы Вилле Р., Гантером Б., Бурмейстером П., Стумме Г. и др. [1]. Формальный концептуальный анализ с бинарным отношением за эти годы был всесторонне развит представителями разных математических школ и получил многочисленные приложения в социологии, медицине, биологии, и др. областях исследований, связанных с обработкой баз данных. Главным инструментом перевода этой теории к случаю (n1)-арному отношению является аппарат алгебры отношений, разработанный Вагнером В.В. в [2]. При этом в разработке основного инструмента используются хорошо известные методы теории реляционных баз данных [3]. Далее под словом «контекст» всюду будем понимать «полиатрибутный контекст».

Восстановим основные определения концептуального анализа. Пусть n-арное отношение. Обозначим  = (1, 2, …, n), , и , , для произвольных . Для удобства введём обозначения для результатов булевых операций над данными множествами: , , . Например, при = (1, 3, 4), = (3, 5, 6) имеем = (1, 3, 4, 5, 6), = 3, = (1, 4). При этом также обозначаем . Говорим, что k-система входит в отношение , если существует n-система , для которой элементы являются её соответствующими компонентами. Для , , обозначим:


:= ,

, ,

:=, .

В случае (n + 1)-арного отношения множеству G будет соответствовать нулевой индекс:  = , ,  = .

Пусть задан контекст K = (G, (), ). Если для некоторого существует , такое что выполняется


,

то X называется концептом по системе атрибутов . Любое подмножество для которого выполняется равенство называется -генератором концепта X, элементы множества объектами, элементы множества Y-атрибутами или атрибутами концепта X, индекс индексом генератора или индексом атрибута. Концепты, отличные от и G, называются собственными.

Будем говорить, что в отношении имеет место F-зависимость , , если , , определяет отображение . F-зависимость , , будем называть B-зависимостью , если определяемое им отображение: является взаимно однозначным.


В [4] было показано, что если атрибуты и в отношении связаны B-зависимостью, то множество концептов по и по совпадают. Там же на основе B-зависимостей было предложен один из способов минимизации арности контекста с сохранением структуры концептов.

Будем говорим, что контекст K = (G, (), ) однозначен относительно множества объектов, или просто однозначен, если отношение имеет F-зависимость . В частности однозначный контекст моделируется любой реляционной базой данных, в которой множество объектов является одним из ключей этой базы.

В [5] была представлена следующая теорема.

Теорема 1. Пусть K = (G, (), ) — однозначный контекст. Тогда справедливы следующие утверждения:


  1. множество собственных концептов по любому образует разбиение множества , которое обозначаем ;
  2. если (), то , т.е. является измельчением разбиения ;


  3. если и , то ;

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

  5. высота решётки концептов этого контекста не превосходит значения min{n + 1, }, а её ширина не превосходит значения .

Заметим, что если отношение является полным относительно G, то  = G. Если это не так, то всегда можно перейти к контексту K = (G, (), ), где G G и G = . Поэтому далее будем полагать, что однозначный контекст K = (G, (), ) обладает отношением полным относительно множества объектов G. Обозначим , — это эквивалентность, соответствующая разбиению , и Lp(K) = {P0, | }, где P0 — это разбиение множества G, состоящее из одного блока G. По утверждению 1 теоремы 1 получаем, что любой собственный концепт по любому является одним из блоков разбиения множества G.


Пусть Lp(G) — решётка разбиений множества G

Теорема 2. Для любого однозначного контекста K = (G, (), ) множество Lp(K) является подрешёткой решётки разбиений Lp(G). И для любой подрешётки L  Lp(G), содержащей P0, существует однозначный контекст K(L) такой, что L Lp(K(L)).

Доказательство. Рассмотрим множество Lp(K). Для любых j1j2  {1, 2, 3, …, n} по определению  = (j1j2), т.е. j1j2  , и по утверждению 2 теоремы 1    и   . Таким образом,  = . И для любого  = (j1j2, …, jk) =…, где  операция пересечения в решётке разбиений множества объектов G. Следовательно, множество Lp(K) является подрешёткой решётки Lp(G). При этом P0 является единицей в решётках Lp(K) и Lp(G), является нулём решётки Lp(K). Разбиения Pj, где j  {1, 2, 3, …, n}, являются коатомами решётки Lp(K).


Обратно, пусть дана некоторая подрешётка L  Lp(G), содержащая P0, где G конечное множество. Пусть P1, P2, …, Pn — все коатомы этой решётки, и 1, 2, …, n — соответствующие эквивалентности на множестве G. Построим контекст K(L) = (G, (),  ), где  = {(g1(g), 2(g), …, n(g)) | g  G}. Построенный контекст является однозначным, поскольку любой g  G попадает только в один блок j(g) разбиения Pj, j  {1, 2, 3, …, n}. Любой собственный концепт контекста K(L) по любому является одним из блоков разбиения множества G. И поскольку =… (является пересечением соответствующих коатомов решётки L), то решётки L и Lp(K(L)) состоят из одних и тех же элементов, т.е. L Lp(K(L)). 

Теорема 3. Для любого однозначного контекста K = (G, (), ) и для любых существует B-зависимость тогда и только тогда, когда =.


Доказательство. Допустим, существует B-зависимость . По определению это значит, что : является взаимно однозначным. Пусть = , по предложению 2 в [6] имеем . А поскольку это отображение является биекцией, то, аналогично, и . Откуда . Это значит, что и состоят из одних и тех же блоков разбиения, т.е. =.

Обратно, пусть =. Для произвольного концепт  =  является блоком разбиения . Пусть ему соответствует также концепт  =  = , где . В силу однозначности контекста получаем  =  и  = . Таким образом, = , и в силу симметричности всех рассуждений относительно и отображение : является взаимно однозначным. 

Теоремы 2 и 3 позволяют построить простой алгоритм минимизации не только арности контекста с сохранением структуры концептов, но одновременно и минимизации мощности множества объектов. Пусть задан произвольный однозначный контекст K = (G, (), ), где — (n1)-арное отношение, и Lp(K) = {P0, | } — соответствующая решётка разбиений множества G. В ней разбиения P1, P2, …, Pn являются коатомами. По теореме 3 если существует B-зависимость Mi   Mj, где i, j  {1, 2, 3, …, n}, то Pi  = Pj. Выпишем теперь все различные коатомы решётки Lp(K): , , …, , где t  n. Напомним, что является нулём решётки Lp(K) и ||  |G |. Обозначим , , , …, — соответствующие эквивалентности. Построим теперь контекст K(Lp(K)) = (, (),  ), где  = {((g), (g), (g), …, (g)) | g  G}.


Теорема 4. Для любого однозначного контекста K = (G, (), ) контекст K(Lp(K)) является минимальным по арности входящего в него отношения и по мощности множества объектов из однозначных контекстов, имеющих с точностью до изоморфизма ту же самую решётку концептов.

Доказательство. Действительно, поскольку , , …, все различные коатомы решётки Lp(K), то невозможно уменьшить арность t, не потеряв хотя бы один из этих коатомов, а значит не потеряв соответствующую антицепь в решётке концептов. С другой стороны, поскольку является нулём решётки Lp(K), то все её блоки являются атомами решётки концептов, и не возможно сократить число этих блоков, не потеряв хотя бы один из соответствующих атомов решётки концептов. 
СПИСОК ЛИТЕРАТУРЫ
1. Ganter B., Wille R. Formal Concept Analysis. Mathematical Foundatoins. Springer Verlag, 1999.

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

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

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

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

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