Алгоритм «безопасной» декомпозиции формального контекста | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/62

Алгоритм «безопасной» декомпозиции формального контекста

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

Algorithm for "safety" decomposition of the formal context.pdf Введение Объектно-признаковая таблица - модель представления данных некоторой предметной области, в которой каждый столбец соответствует некоторому признаку, а каждая строка определяет признаковое описание отдельного объекта. Такая модель часто используется при решении прикладных задач в интеллектуальном анализе данных, в том числе в анализе формальных понятий. Анализ формальныйх понятий (АФП) - прикладная ветвь алгебраической теории решёток Г. Биркгофа [1]. Основные идеи АФП были сформулированы в начале 80-х годов XX века в работах Р. Вилле и Б. Гантера и развиты в исследованиях С. О. Кузнецова, С. А. Объедкова, Д. И. Игнатова [2-4]. В рамках АФП объектно-признаковая таблица представляется формальным контекстом, отражающим наличие или отсутствие признаков, характерных для изучаемого множества объектов, и моделируется 0,1-матрицей. В АФП формальные понятия определяются с помощью соответствий Галуа и представляют собой пары множеств вида (объём, содержание). В настоящее время применение методов АФП ограничивается высокой трудоёмкостью процесса нахождения всех формальных понятий заданного формального контекста. В данной работе предлагается алгоритм, который на практике позволяет разложить данную задачу на подзадачи (уменьшенные копии исходной задачи) за полиномиальное время. 1. Основные положения анализа формальных понятий Приведём основные положения и обозначения АФП [2, 3]. Пусть для предметной области определены два непустых конечных множества G и M объектов и признаков (или свойств) и задано непустое отношение инцидентности I С G х M. Данное отношение содержит информацию о выполнимости свойств из M на объектах из G, т.е. (g,m) Е I означает, что объект g обладает признаком m, и наоборот - признак m присущ объекту g. Тройку K = (G, M, I) принято называть формальным контекстом. Будем полагать, что множества G и M линейно упорядочены (например, лексикографически). В этом случае формальный контекст K = (G, M, I) однозначно задается 0,1-матрицей T = (tj): tij = 0 при (gj, mj) EI и tij = 1 при (gj ,mj) Е I (i = 1, 2,... , |G|; j = 1, 2,..., |M |). Выберем в K = (G, M, I) два произвольных подмножества A С G и B С M и определим для них отображения (•)' Галуа: A = П g', B' = П m', где g' = {m Е M : geA m£B (g,m) E I}; m' = {g E G : (g,m) E I}. Согласно этому определению, множество A - набор признаков, присущих объектам из A, а множество B' задаёт семейство объектов, обладающих признаками из B. Двойное применение (■)' определяет оператор замыкания (■)'' на 2м в алгебраическом смысле. Множество (B)'' можно трактовать как набор признаков, которые неизменно появляются в объектах формального контекста K = (G,M,I) вместе с признаками из B, причём это множество является наибольшим по включению в пределах этого формального контекста. Если B = B'', то B называется замкнутым множеством относительно оператора (■)''. Пара множеств (A,B), таких, что A С G, B С M, A' = B и B' = A, называется формальным понятием формального контекста K = (G, M, I) с объёмом A и содержанием B. Далее для краткости в ряде случаев определение «формальный» перед словами «контекст» или «понятие» будем опускать. Пара множеств (A,B) является формальным понятием тогда и только тогда, когда A = A'' и B = B''. Очевидно, что всякое формальное понятие уникально в заданном контексте, т. е. отличается от других формальных понятий объёмом и/или содержанием. Если формальный контекст представлен 0,1-матрицей T, то при A = 0 и B = 0 формальному понятию (A,B) отвечает максимальная полная подматрица матрицы T. Обозначим через FC множество всех формальных понятий формального контекста K = (G,M,I). Пусть (Ai,Bi) , (A2,B2) Е FC. Множество FC частично упорядочено отношением (A1,B1) □ (A2,B2) ^ A1 С A2. Отметим, что последнее эквивалентно условию B2 С B1. Каждое формальное понятие (A,B) Е FC определяет для исследуемой предметной области совокупность однородных объектов A со своим специфичным набором признаков B. Если (G, 0) Е FC, (0,M) Е FC, то формальные понятия (G, 0) , (0, M) называются тривиальными. Определим на FC операции пересечения П и объединения U через одноимённые теоретико-множественные операции П и U следующим образом: (A1, B1) П (A2, B2) = (A1 П A2, (A1 П A2)'), (A1, B1) U (A2, B2) = ((B1 П B2)', B1 П B2). Тогда (FC, □) образует полную решётку L = (FC, П, U), называемую в АФП решёткой формальных понятий контекста K = (G, M, I). 2. Постановка задачи и метод «безопасной» декомпозиции В рамках АФП задача нахождения всех формальных понятий формулируется следующим образом. Задан формальный контекста K = (G, M, I). Требуется для K найти множество FC. На сегодняшний день для определения множества FC разработано много алгоритмов, в их числе NextClosure, Close-by-One, Norris [3, 4]. Время их выполнения в худшем случае составляет O(|FC| ■ |G|2 ■ |M|). Поскольку величина | FC| может экспоненциально зависеть от |G| и |M|, время выполнения данных алгоритмов также может быть экспоненциальным. Повысить производительность можно путём применения метода «безопасной» декомпозиции формального контекста на боксы [5]. Пусть g £ G и m £ M - произвольные элементы контекста K = (G,M,I). Пары множеств (g", g') и (m!, m") образуют формальные понятия, первое из которых назовём объектным, а второе - признаковым формальным понятием контекста K = (G, M, I). Обозначим через O = {(g'',g') : g £ G} С FC множество всех объектных формальных понятий и через S = {(m',m'') : m £ M} С FC - множество всех признаковых формальных понятий контекста K = (G, M, I). Пара формальных понятий (g'', g') £ O, (m', m'') £ S определяет бокс ш = (m', g', J) контекста K = (G,M,I), если (g'',g') E (m',m'') , что эквивалентно g'' С m' (или m'' С g'). Про такой бокс будем говорить, что он образован элементами g £ G и m £ M. Далее вместо ш = (m',g', J) будем кратко писать ш = (m',g') или (m', g'). Утверждение 1 [6]. Для всякого формального контекста K = (G, M, I) и любых (g'',g') £ O, (m',m'') £ S отношение порядка (g'',g') Е (m', m'') выполняется тогда и только тогда, когда (g,m) £ I. Утверждение 1 устанавливает оценку числа боксов, получаемых на каждой итерации разложения: число различных боксов, порождаемых всевозможными элементами контекста K = (G, M, I), не превышает веса 0,1-матрицы T, т. е. величины ||T|| -числа единичных элементов этой матрицы. Очевидно, что 1 ^ ||T|| ^ |G| ■ |M|. Будем говорить, что формальное понятие (A,B) £ FC вложено в бокс (m',g') контекста K = (G, M, I), и записывать (A, B) ^ (m',g'), если A С m', B С g'. Всякий бокс (m',g') не является пустым, поскольку, согласно определению бокса, он всегда содержит формальные понятия (g'',g') £ O и (m',m'') £ S. Утверждение 2 [6]. Всякое нетривиальное формальное понятие (A,B) контекста K = (G, M, I), которое вложено в бокс (m', g'), образованный элементами g £ G и m £ M, содержит эти элементы и их замыкания, т. е. если (A, B) ^ (m', g'), то g £ A и m £ B; g'' С A и m'' С B. Согласно утверждению 2, пару (g'',m'') можно рассматривать в качестве типичного представителя не только бокса (m',g'), но и всех формальных понятий контекста K = (G, M, I), вложенных в этот бокс. Переход от боксов к их типичным представителям в большинстве случаев уменьшает на практике время выполнения алгоритмов нахождения всех формальных понятий для заданного формального контекста. Соответствие между боксами и формальными понятиями контекста устанавливает следующая теорема. Теорема 1 [6]. Для всякого формального контекста K = (G, M, I), множества FC всех его формальных понятий и любой пары множеств (A,B), 0 = A С G, 0 = B С M, справедливо: 1) если (A, B) £ FC, то в K существует бокс ш = (m',g'), g £ G и m £ M, возможно, не единственный, в который это формальное понятие вложено; 2) если (A, B) - формальное понятие некоторого бокса ш = (m',g') формального контекста K, то оно также принадлежит FC. Согласно теореме 1, разложение контекста K = (G, M,I) на боксы является «безопасным» для любого формального понятия из FC [5]. Очевидно, что процесс разложения заданного контекста на боксы может быть организован итерационно, поскольку каждый выявленный на первой итерации бокс можно рассматривать в качестве исходного контекста и вновь подвергать декомпозиции. Определим сложность процесса разложения и правила его остановки. Пусть |m'| ■ |g'| -размер бокса (m',g'), а ||(m',g')|| -число его единичных элементов. Плотностью бокса (m',g') назовём величину a (m',g') = ||(m',g')||/(|m'| ■ |g'|). Верны естественные границы 0 < a (m',g') ^ 1. Утверждение 3 [6]. Всякий бокс (m',g') с плотностью a (m',g') = 1 содержит ровно одно нетривиальное формальное понятие (A, B) контекста K = (G, M, I), совпадающее с ним, т. е. A = m' и B = g'. Из утверждения 3 следует, что бокс (m',g') с плотностью 1 вырождается в нетривиальное формальное понятие и не подлежит дальнейшему разложению. Заметим, что время формирования одного бокса для формального контекста K = (G, M, I) составляет O(|G| ■ |M|). В целом, время, необходимое на однократное разложение этого контекста на боксы, в худшем случае составляет O (a (G, M) |G|2 ■ |MП. 3. Алгоритм «безопасной» декомпозиции формального контекста на боксы Алгоритм FindBoxes (алгоритм 1) реализует метод «безопасной» декомпозиции формального контекста на боксы. Теоретическим обоснованием этого алгоритма являются теорема 1 и утверждения 1-3, входными данными служат исходный контекст K = (G, M, I) и целое положительное число k - число итераций. Результат работы алгоритма FindBoxes: П - множество боксов и H - множество типичных представителей боксов, входящих в П. Алгоритм FindBoxes включает следующие основные процедуры: Boxes, Delete, SearchChains. Процедура Boxes разлагает заданный бокс ш, плотность которого отлична от 1, на более мелкие боксы и находит для них типичных представителей. Процедура Delete удаляет кратные боксы и боксы, совпадающие с исходным. Процедура SearchChains выявляет вложенные боксы, выполняет построение взаимно непересекающихся цепей частично упорядоченного множества боксов П1 и находит для этих цепей максимальные элементы. Данная процедура позволяет уменьшать число боксов, получаемых на каждой итерации разложения. Если число итераций процесса декомпозиции равно k, то разложение можно осуществить за время о(|G|2k ■ |M|2fc) ; при k =1 алгоритм FindBoxes выполняется за время 0(|G|2 ■ |M|2). Для дополнительного ограничения числа частей, получаемых на каждой итерации, можно устанавливать пороговое значение на плотность боксов, подлежащих дальнейшему разложению. Это достигается заменой на шаге 8 алгоритма FindBoxes условия a (ш) = 1 условием a (ш) < ao, где a0 - пороговое значение плотности боксов, которые подлежит дальнейшему разложению. Для оценки результативности алгоритма FindBoxes проведены вычислительные эксперименты при k = 1 и без задания ограничения на плотность боксов. Эксперименты проводились с помощью программы FCACorpus [7], осуществляющей нахождение всех формальных понятий. Использовались контексты, сгенерированные случайным образом. Для каждого контекста K = (G, M, I) осуществлялось нахождение множества FC всех формальных понятий без разбиения на боксы и с итеративным разбиением на боксы. Анализировались два случая при проверке вложенности боксов: случай 1 - проверка производится без типичных представителей боксов, случай 2 - Алгоритм 1. FindBoxes Вход: исходный контекст K = (G, M, I), k - количество итераций. Выход: П - множество боксов, H - множество типичных представителей боксов из П. 1: Hi := (G, M, I) // множество боксов, подлежащих дальнейшему разложению 2: П2 := 0 // множество боксов, не подлежащих дальнейшему разложению 3: H1 := (G", M") // множество типичных представителей боксов, входящих в П1 4: H2 := 0 // множество типичных представителей боксов, входящих в П2 5: Пока (k = 0 & Hi = 0) 6: Q := 0, V := 0. 7: Для всех ш £ П1 8: Если а(ш) = 1, то 9: Boxes(w,X,Y); Q := Q U 10: иначе 11: П2 := П2 U ш; H2 := H2 U 12: W1 := Q; H1 := R; Delete (П1 13: Если П1 = 0 то 14: SearchChains(n1, H1). 15: k := k - 1. 16: П := П1 U П2; H := H1 U H2. с помощью типичных представителей. Результаты эксперимента приведены в таблице, где N - количество образованных боксов; |FC| -число найденных формальных понятий; t - время выполнения программы. Эксперименты выполнялись на компьютере с процессором Intel Core i7-720QM Processor (6M Cache, 1,60 ГГц) и ОЗУ размером 4 Гбайт. Оценка эффективности процесса декомпозиции формального контекста Случаи Характеристика исходного контекста Результаты |G| |M | l|T || a (G, M) N IFC | t, мс Без разложения на боксы С разложением на боксы (случай 1) С разложением на боксы (случай 2) 100 20 1000 0,5 883 883 4962 4962 4962 145125 2878 2200 Без разложения на боксы С разложением на боксы (случай 1) С разложением на боксы (случай 2) 200 30 2940 0,49 2895 2895 10567 10567 10567 794520 97906 90908 Из таблицы видно, что значения |FC| в случаях без разложения и с разложением на боксы полностью совпадают; число боксов, образованных при разложении контекста, не превышает величины ||T||; алгоритм FindBoxes даёт значительный выигрыш по времени: время выполнения программы FCACorpus при разложении контекста на боксы уменьшается в несколько раз. Заключение Представленный алгоритм FindBoxes реализует метод «безопасной» декомпозиции формального контекста и на практике позволяет разложить задачу нахождения всех формальных понятий на подзадачи за полиномиальное время. Алгоритм также применим для ускорения существующих алгоритмов решения родственных задач, связанных с нахождением максимальных полных подматриц 0,1-матрицы. X; R := R U Y, H1. U П2, H1 U H2).

Ключевые слова

формальный контекст, формальное понятие, декомпозиция формального контекста, алгоритм декомпозиции, formal context, formal concept, decomposition of formal context, algorithm of decomposition

Авторы

ФИООрганизацияДополнительноE-mail
Монгуш Чодураа МихайловнаСибирский федеральный университет ; Тувинский государственный университетаспирантка; преподавательmongushchod91@yandex.ru
Всего: 1

Ссылки

Биркгоф Г. Теория решеток. М.: Наука, 1984. 568с.
Ganter B. and Wille R. Formal Concept Analyses: Mathematical Foundations. Springer Science and Business Media, 2012. 314 p.
Ganter B. and Obiedkov S. A. Conceptual Exploration. Berlin; Heidelberg: Springer, 2016. 315 p.
Kuznetsov S. O. and Obiedkov S. A. Comparing performance of algorithms for generating concept lattices // J. Exper. Theor. Artificial Intelligence. 2002. V. 14. No. 2. P. 189-216.
Mongush Ch. M. and Bykova V. V. On decomposition of a binary context without losing formal concepts // J. Siberian Federal University. Mathematics and Physics. 2019. No. 3. P. 323-330.
Быкова В. В., Монгуш Ч. М. Декомпозиционный подход к исследованию формальных контекстов // Прикладная дискретная математика. 2019. №.44. С. 111-124.
Монгуш Ч. М., Быкова В. В. Программа FCACorpus концептуального моделирования тувинских текстов методами анализа формальных понятий. Свид. о гос. регистрации программы для ЭВМ № 2018618907, выдано Федеральной службой по интеллектуальной собственности РФ, 2018.
 Алгоритм «безопасной» декомпозиции формального контекста | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/62

Алгоритм «безопасной» декомпозиции формального контекста | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/62