Диссертация (1137259), страница 16
Текст из файла (страница 16)
При этом они также не являют95ся легко доступными научному сообществу [27; 60]. Таким образом,данная глава является первой попыткой предоставления общего алгоритмического и программного аппарата узорных структур широкомукругу пользователей.4.2Адаптация существующих АФП алгоритмов дляработы с узорными структурамиДля построения узорной решётки понятий достаточно лишьнемного изменить существующие алгоритмы построения решётокформальных понятий. Теоретико-множественная операция пересечения должна быть заменена на полурешёточную операцию сходства,а операция проверки того, что одно множество является подмножеством другого, должна быть заменена на проверку поглощения одного элемента полурешётки другим. Так Алгоритм 3 показывает псевдокод алгоритма Замыкай по Одному (ЗО) [70; 73], модифицированного для работы с узорными структурами.
Этот алгоритм для понятия, задаваемого объёмом и содержанием, находит всех канонических соседей сверху. Алгоритм ЗО пробегается по всем допустимымрасширениям объёма начального понятия и проверяет, что замыкание этого расширения также является допустимым. Допустимостьобъёма не требует изменений для работы с узорными структурами и,таким образом, проверяется в точности по [70].Аналогичным образом могут быть модифицированы другие классические алгоритмы, строящие решётки формальных понятий. В качестве следующего примера рассмотрим алгоритм AddIntent [87],который позволяет находить не только множество формальных понятий, но и вычислять диаграмму покрытия отношения частичного порядка на понятиях. Алгоритм 4 показывает каким образомдолжны быть изменены строки с 8 по 24 изначального алгоритмаAddIntent для обработки узорных понятий.96Function CloseByOne(, )Data: (, (, ⊓), ), объем и содержание некоторого понятия.Result: Все канонические предки (, ) в решёткепонятий.foreach ⊆ , ≻ do;/* ⊓ - пересечение */d ←−();∈;/* ⊑ - поглощение */ ←− { ∈ | ⊑ ()};if IsCanonicExtension(, ) thenSaveConcept(( , ));CloseByOne(NewExt,NewInt);;/* Находим все понятия решётки */CloseByOne(∅, ⊤);Algorithm 3: Версия ЗО, вычисляющая решётку узорных понятий.4.3Программный комплекс для моделирования наоснове узорных структурМатематический формализм узорных структур позволяет работать с любыми типами полурёшеток описаний.
Но как возможно передать программе структуру этой полурешётки? Один из возможных подходов – заранее ограничить количество типов узорных структур, научив программную систему обрабатывать узорные структуры, основанные, например, на интервалах, графах и последовательностях. Но такой подход существенно ограничивает возможностипользователей системы по использованию узорных структур. Другимподходом может быть система, которая позволяет передавать пользователю любую полурешётку описаний.
Но напрямую передавать всюполурешётку во многих случаях невозможно, так как размер этойрешётки может быть очень большим, либо даже бесконечным. Более того, это может привести пользователя к необходимости расчёта97foreach ∈ doif . ̸< then :=AddIntent(. ⊓ , , ) := ;foreach ∈ doif . ⊑ . then := ;else if . < .
thenRemove from ;if thenAdd to ;Algorithm 4: Изменёные строки с 8 по 24 алгоритмаAddIntent для работы с узорными структурами.всей полурешётки, что, в силу её большого размера, может серьёзнопонизить производительность системы.Альтернативным способом передачи полурешётки описаний является неявное задание полурешётки. Другими словами, можно просить пользователя определять операцию сходства между любымидвумя узорами, интересующего его вида. Этот подход с одной стороны эффективно решает проблемы предыдущих двух подходов, сдругой стороны возникает необходимость для пользователя программировать с использованием API программного обеспечения для обработки нужных ему узорных структур, что также может ограничитьприменяемость системы.
Мы остановились на последнем варианте,с тем дополнением, что все написанные узорные структуры могутбыть сохранены в системе как библиотеки для последующего переиспользования. Таким образом мы позволяем пользователям использовать узорные структуры известных типов, что существенно можетсохранить время на разработку своей узорной структуры.
С другойстороны мы позволяем пользователю разрабатывать узорные структуры любой сложностью, переиспользуя стандартные части системы. Так, например, пользователь может выбрать любой из доступных98алгоритмов построения решётки формальных понятий, задав толькорешёточную операцию сходства для интересующих его описаний.Таким образом, для использования полурешётки (, ⊓) достаточно для любых двух описаний из , ∈ определить операцию сходства = ⊓ , где ∈ . Как было отмечено для модификации любого классического алгоритма для работы с узорными структураминеобходимо так же уметь сравнивать два описания согласно частичному порядку поглощения описаний, которая может быть выраженачерез решёточную операцию сходства: ⊑ ⇔ ⊓ = .
Значитлюбая узорная структура на полурешётке, заданной операцией сходства, может быть рассчитана многими классическими алгоритмами,такими как Noris [92], NextClosure [39], Bordat [16], CbO [70],AddIntent [87] и другие.4.3.1Форматы передачи данныхВ качестве форматов передачи данных был выбран стандартJSON 1 . Данный стандарт позволяет представить практически любой тип данных и имеет при этом небольшую сложность обработки и невысокий объём памяти, требуемый для хранения элементовсамого JSON. В частности, JSON является более компактным универсальным представление данных, чем XML. Следующие форматыданных являются частоиспользуемыми и поэтому их необходимо зафиксировать для более простого взаимодействия между отдельнымимодулями: примитивные типы (числа, строка), множества, упорядоченные множества или вектора, корневые деревья, решётки формальных понятий и общие структуры или графы.Выбор формата JSON позволяет также облегчить импорт извнешних источников данных.
В частности, существует множествопрограммных средств, умеющих работать с JSON. В случае программных средств по работе с узорными структурами, внешняя выборка данных должна быть сконвертирована в JSON представление.1http://www.json.org99{[{ “NodesCount” : 2 },{ “Nodes” : [{ “Int” : 0, “Ext” : 0 },{ “Int” : 1, “Ext” : 1 }]},{ “ArcsCount” : 1 },{ “Arcs” : [{ “S” : 0, “D” : 1 },]},{“Count”: 3,“Inds":[2, 5, 8]}(a) Вектор индексов{“Count”: 3,“Inds"::[2.3, 5.5, 8.1]}]}(b) Вектор действительных чисел(c) Решётка понятийРисунок 4.1: Примеры форматов JSON для представления элементовданных, объектов и элементов узорных структурПосле чего внутреннее представление этой выборки может быть загружена той или иной узорной структурой. Само по себе это внутреннее представление соответствует -функции узорных структур.Сама же узорная структура может преобразовать это представлениив другое JSON представление с целью оптимизации вычислительных ресурсов и затрат памяти.
В частности, спроецированная узорная структура может хранить граф как множество путей, и в этомслучае ей больше не нужно хранить каждый путь как отдельныйграф.Рисунок 4.1 приводит примеры различных данных, сохраненныхв формате JSON. В частности рисунки 4.1a и 4.1b показывают вектора чисел. Вектор целых чисел может быть использован для представления бинарных данных, в которых каждое целое число соответствует номеру признака в бинарных данных, а вектор действительных чисел может быть использован для представления любыхчисленных данных. На рисунке 4.1c показан пример решётки двухформальных понятий, который в дальнейшем может быть использован любым другим пользователем.1004.3.2Архитектура подходаАрхитектурное решение подбиралось из следующих требований:Моделирование процессов.
Программный комплекс должен позволять моделировать процессы с состояниями сложной структуры.Гибкость. Программный комплекс должен позволять с минимальными усилиями создавать любые модели на основе узорныхструктур. В частности необходимо:∙ Любая узорная структура должна иметь возможностьбыть представленной в проектируемом программномобеспечении.∙ Любой алгоритм по построению решётки формальных понятий, который можно адаптировать для построения узорных структур должен иметь возможность для добавленияв систему.Эффективность.
Накладные расходы должны быть минимизированы для уменьшения времени расчёт узорной решётки.Кроссплатформенность. Необходимо избежать зависимости отокружения программного комплекса, так как научное сообщество, которому может быть интересен этот комплекс представлен такими системами как Windows, Linux и MacOS.Напомним, что моделирование процессов с состояниями сложной структуры происходит согласно диаграмме, показанной на рисунке 4.2.
В частности необходимо преобразовать данные в узорныеструктуры, построить решётку узорных понятий, посчитать меры качества на них и отфильтровать решётку согласно этим мерам качества.Построение различных моделей на основе узорных структур имеют много общих черт. В частности, диаграмма моделирования на ри101Рисунок 4.2: Диаграмма выполнения при моделировании процессовс состояниями сложной структуры на основе узорных структур.сунке 4.2 будет иметь тот же вид и для других типов моделей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
