Содержание к диссертации
Введение
1 Возможные подходы к моделированию процессов с состояниями сложной структурой 13
1.1 Введение 13
1.2 Процессы с состояниями сложной структуры 14
1.3 Плоские модели 15
1.4 Модели последовательностей 18
1.5 Графовые модели 23
1.6 Методы оценки качества моделей 27
1.7 Заключение 29
2 Модель процессов с состояниями сложной структуры на основе узорных структур 30
2.1 Введение 30
2.2 Базовые понятия
2.2.1 Элементы теории решёток 31
2.2.2 Анализ формальных понятий (АФП) 34
2.2.3 Узорные структуры
2.3 Проекции как средство приближенного анализа 39
2.4 Узорные структуры для процессов 44
2.4.1 Рабочий пример 45
2.4.2 Частичный порядок на последовательностях и соответствующая полурешётка 46
2.4.3 Проекции узорных структур на последовательностях 49
2.4.4 Алгоритм расчёта решёточной операции на
сплошных последовательностях 52
2.5 Заключение 54
3 Меры качества моделей и их применение 55
3.1 Введение 55
3.2 Устойчивость формальных понятий 56
3.2.1 Определение устойчивости 56
3.2.2 Оценки устойчивости 603.3 Особенности расчёта устойчивости и её оценок 64
3.4 Исследование поведения меры устойчивости формального понятия и её оценок 65
3.4.1 Схема эксперимента 66
3.4.2 Общее поведение устойчивости 69
3.4.3 Порог устойчивых понятий 71
3.4.4 Ранжирование понятий по устойчивости 74
3.4.5 Ограничения данной схемы экспериментов 77
3.5 Сравнение меры устойчивости и её оценок с другими мерами качества моделей 78
3.5.1 Рабочий пример 80
3.5.2 Мера рычага 81
3.5.3 Схема эксперимента 83
3.5.4 Результаты эксперимента 86
3.6 Эффективность оценок устойчивости 87
3.6.1 Точность оценки устойчивости 89
3.6.2 Оценка устойчивости и ранжирование 91
3.6.3 Устойчивость и интервал оценки 92
3.7 Заключение 93
4 Алгоритмы и комплексы программ, реализующие модели на основе решёток замкнутых описаний 95
4.1 Введение 95
4.2 Адаптация существующих АФП алгоритмов для работы с узорными структурами 96
4.3 Программный комплекс для моделирования на основе узорных структур 97
4.3.1 Форматы передачи данных 99
4.3.2 Архитектура подхода 101
4.3.3 Менеджер узоров 104
4.3.4 Подсистемы хранения объёмов и содержаний 106
4.3.5 Подсистема построения узорной решётки 108
4.3.6 Моделирование процессов с состояниями сложной структуры 109
4.3.7 Интеграция с программным комплексом FCART 110
4.3.8 Комплексы программ для работы с узорными структурам и АФП 112
4.4 Заключение 114
5 Построение и использование моделей процессов с состояниями сложной структуры на реальных данных 116
5.1 Введение 116
5.2 Моделирование посещения новостных ресурсов пользователями 117
5.3 Моделирование процесса госпитализации пациентов 1205.3.1 Наивный подход моделирования процессов госпитализации 123
5.3.2 Моделирование процессов госпитализации с учётом сложного описания состояний 125
5.3.3 Использование других подходов для моделирования процесса госпитализации пациентов 129
5.4 Заключение 132
Заключение 134
Литература
- Модели последовательностей
- Проекции как средство приближенного анализа
- Исследование поведения меры устойчивости формального понятия и её оценок
- Подсистема построения узорной решётки
Модели последовательностей
В этой главе мы задаемся вопросом какие подходы могут быть использованы для анализа процессов с состояниями сложной структуры? Прежде всего необходимо определить какие процессы мы исследуем и затем посмотреть, какие существуют подходы к моделированию процессов как таковых. К таким подходам следует отнести плоские и иерархические модели. К плоским моделям относят сети Петри, системы переходов и другие классы общих схем процессов, то есть таких схем, на которых показано общее поведение процесса, и по которым можно смоделировать большую часть реализаций процессов.
Иерархические модели включают упорядоченное множество простых моделей. Это может быть как иерархия сетей Петри, так и упорядоченные множества закономерностей, называемых также элементарными моделями, получаемые методами анализа данных. В этом случае, как правило, используются методы анализа последовательностей. Количество найденных таким образом элементарных моделей может быть существенно и необходима последующая фильтрация для возможности экспертного анализа такой модели. Соответствен но меры качества элементарных моделей имеют важное значения для значимых иерархических моделей.
Однако, большинство таких моделей не всегда могут передать сложную структуру состояний. Тогда естественным подходом к моделированию процессов с состояниям сложной структуры является графовое представление процесса, которое также будет рассмотрено.
Таким образом, в этой главе мы сначала рассмотрим подробнее процесс с состояниями сложной структуры, а затем будут рассмотрены плоские и иерархические модели, за которым последует обсуждение подходов к обработке графов для анализа процессов с состояниями сложной структуры. В самом конце мы рассмотрим различные меры качества элементарных моделей, позволяющие редуцировать иерархические модели без потери качества.
В реальной жизни процессом называется некоторое скрытое явление, которое в реальной жизни проявляется как последовательности однотипных взаимосвязанных (предполагаемых взаимосвязанными) фактов. Каждая такая последовательность взаимосвязанных фактов называется реализацией этого процесса, а каждый факт называется его состоянием. Процесс порождает множество своих реализаций.
Например, процесс госпитализации пациентов связан с многими скрытыми факторами, такими как реакции организма на патологии и медикаментозное лечение, различные поведенческие установки индивидуума, методология лечения и многое другое. Каждая реализация этого процесса представлена историей госпитализации отдельного пациента. Состоянием этого процесса является одна госпитализация. Такие состояния в одной реализации процесса взаимосвязаны через реакции организма конкретного пациента и методы его лечения.
В данной работе мы говорим о процессах с состояниями сложной структуры, что означает, что о каждом состоянии нам известно не только его название, такое как “госпитализация для прохождения химиотерапии” или “госпитализация для диагностики рака”, но и другая информация, отражающая взаимозависимости между состояниями. Эти взаимосвязи позволяют нам говорить об обобщённых состояниях и обобщённых реализациях процесса. В таких состояниях часть из доступной информации не рассматривается, но они чаще встречаются в реализациях процесса. Например, состояние “госпитализация территориально расположенная в московской области” является обобщённым состояниям для “госпитализация территориально расположенная в Москве”, так как последнее состояние предполагает, что оно также является и первым состояниям, но не наоборот.
Таким образом, реализации процессов с состояниями сложной структуры описываются последовательностями элементов некоторого частично-упорядоченного множества состояний. Этот частичный порядок на множестве состояний представляет отношение типа "быть более общим чем"или "быть частью". Таким образом, реализация процесса с состояниями сложной структуры – это элемент (слово в алфавите ), где (,) – некоторое частично-упорядоченное множество.
Существует несколько плоских моделей, которые могут быть созданы методами анализа процессов. К таким моделям относятся: системы переходов и Петри-сети [3], WF-сети (частный случай Петри-ситей, используемый для моделирования бизнес процессов) [4], YAWL [111], BPMN [124], EPC [104]. Эти модели обладают разной степенью выразительности, в частности, системы переходов не могут выразить конкурентных состояний в процессе. Большинство этих моделей может быть достаточно просто преобразовано друг в друга, когда это допускают средства выразительности. Например, сети Петри могут быть легко преобразованы в BPMN [6].
Проекции как средство приближенного анализа
С точки зрения дополнительных ограничений часто используется особое поведение закономерностей для задач классификации, то есть такие закономерности, которые могут быть использованы для отличия положительной от отрицательной выборок [15; 29; 40; 47; 57; 72; 76; 78; 80; 86; 98; 101]. Также часто накладывается ограничения замкнутости подграфов [40; 55; 71; 72; 76; 127; 136] или его максимальности [51; 112]. Особый интерес представляют подходы для заданий ограничений, определяемых пользователем [94; 107; 108].
Большинство методов по анализу данных, представленных графами, решают задачу поиска частых подграфов или их множеств (то есть подграфов с ограничением по поддержке) с дополнительными ограничениями на тип подграфов. Одним из первых методов по поиску частых подграфов является WARMR [62], основанный на индуктивном логическом программировании. За счёт большого числа скрытых проверок изоморфизма подграфов, данные метод является неэффективным и на практике редко используется. Наиболее часто используемыми методами являются FSG [67], MoFa [17], gSpan [128] и GASTON [90]. На различных выборках графовых данных было показано, что gSpan и GASTON, основанные на каноническом порождении следующего подграфа, являются наиболее эффективными, но выделить явного победителя среди них нельзя, и их производительность существенно зависит от выборки графов [125].
gSpan начинают свою работу с одной вершины и затем последовательно расширяет уже найденные подграфы рёбрами, полагаясь на канонический код получаемых графов. GASTON также использует канонический код подграфов при проверке допустимости расширения, но он состоит из трёх стадий. Задачей первой стадии является поиск всех частых путей выборки графов, на второй стадии находятся все частые деревья и, наконец на третей – все частые подграфы, содержащие циклы.
Как правило, существует большое количество частых подграфов. Поэтому разработан ряд подходов, переформулирующих задачу для уменьшения множества получаемых закономерностей. Алгоритм
CloseGraph [127] является расширением gSpan. Этот подход ищет только замкнутые графы, то есть такие графы, к которым невозможно добавить ребро или вершины без изменения поддержки этого графа в выборке. Подход FOGGER [137] является антиподом CloseGraph и ищет минимальные генераторы – подграфы из которых нельзя убрать ребро или вершину без изменения поддержки.
Другим возможным путём для ограничения множества результатов являются подходы по поиску максимальных подграфов, то есть таких подграфов, любое расширение которых не является частыми. Примерами являются MARGIN [112] и SPIN [51].
Существует другая возможность уменьшить множество результирующих закономерностей, тем самым увеличив производительность системы и, возможно, снизив число ненужных закономерностей. Пользователю можно предоставить возможность выбора ограничений, которые могут быть найдены методом. Несколько подходов были разработаны для того, чтобы напрямую вводить такие ограничения в процесс вычислений, а также для того, чтобы упростить пользователю саму процедуру подбора этих ограничений [94; 139].
Из-за большой вычислительной сложности подходов, получающих полный список всех частых подграфов даже с дополнительными ограничениями, возникло множество методов, получающих либо приблизительный результат, либо, так называемый, представительный результат, то есть некоторое подмножество всех возможных закономерностей, дающих общую картину возможных подграфов. Так один из первых подходов к анализу данных был именно таким (SUBDUE [26]). В нём авторы используют принцип минимальной длины описания и приблизительной проверкой изоморфизма подграфов. Это даёт существенный вычислительный выигрыш, но тем не менее авторы утверждают, что подграфы получаемые таким образом, являются важными для исследуемых предметных областей.
Другим эвристическим методом является подход Leap Search [130], в котором авторы используют эвристическое отсечение ветвей пространства поиска. Другим возможным подходом к уменьшению множества закономерностей является поиск представительного множества. Так в работе [49] описывается подход, в которым получаются все подграфы, удовлетворяющие некоторому критерию. В частности, требуется, чтобы они были частыми и чтобы они были достаточно различными. Авторы предлагают метод случайных блужданий для решения этой задачи. В своих следующих работах они делают равномерной вероятность получения подграфов различного вида [47; 48] на основе марковских цепей.
Ещё одним интересным неполным методом, является алгоритм GAIA [56], основанный на генетических алгоритмах. Алгоритм выделяет определённое количество мест под результирующие подграфы. И затем задаёт функцию выживаемости подграфов от их классифицирующей способности. Это позволяет найти достаточно большие подграфы, классифицирующие данную выборку.
Общим недостатком всех методов анализа графов является их низкая производительность, что связано с необходимостью решения #P-полной задачи проверки изоморфизма графа подграфу. Даже при использовании приближённых методов вычисления, подходы к анализу графов имеют высокую вычислительную сложность, и не могут быть использованы для процессов с состояниями сложной структуры.
Исследование поведения меры устойчивости формального понятия и её оценок
Предположим, что ЗА с Ext (С), такое что А = Int(C), но при этом А ф Int(Q). Тогда существует Сф - наследник Сф (Ext(C ) С Ext(Q)) такой, что А = Int(Q), то есть А С Ext(Q). В таком случае, согласно утверждению 5, существует понятия С в (С,(ДП),), такое что Ext (С) = Ext{Сф). Следовательно, А С Ext(C ) = Ext (С) С Ext (Сф) = Ext (С). Но тогда А ф Int(C). Полу чили противоречие, что и завершает доказательство.
Таким образом, если среди понятий спроецированной узорной структуры, найти устойчивые по некоторому уровню в, то есть такие, что Stab(C) в. То среди них будут все понятия исходной узорной структуры, устойчивые по этому же уровню в и присутствующие в спроецированной узорной структуре.
Стоит также отметить, что, как было показано ранее, нахождение устойчивости для данного понятия является #P-полной задачей [74; 75]. Один из лучших алгоритмов [103] для нахождения устойчивости может её находить только для всей решётки и имеет алгоритмическую сложность, в худшем случае квадратичную от размера решётки, 0(2). Напомним, что размер решётки может быть экспоненциальным от количества объектов, \\ - 0(2lGl). Данная теоретическая оценка является более сложной для вычисления, чем теоретическая оценка построения решётки формальных (узорных) понятий. Более того как показывают вычислительные эксперименты, нахождение меры устойчивости может требовать существенно большего времени, чем вычисление самой решётки [21]. Кроме того, известные алгоритмы нахождение точного значения устойчивости требуют построения диаграммы решётки формальных понятий, и, таким образом, предъявляют высокие требования к памяти и вычислительной мощности ЭВМ. Значит, эффективная оценка этой меры является необходимой для её применения. 3.2.2 Оценки устойчивости
Для понятия С и его соседа снизу С (Ext (С) С Ext (С)), верно следующее (Vs С Ext(C))(s" С Ext (С) As Int(C) D Int(C)), то есть s т Int(C). Следовательно, подмножество объёма любого соседа снизу С не может входить в числитель формулы (3.1) при вычислении устойчивости для понятия С. С другой стороны, все подмножества объёма понятия С, которые не являются подмножествами какого-либо соседа снизу данного понятия, будут описываться признаками из Int(C). Соответственно, такие подмножества должны включаться в числитель формулы 3.1. Следовательно, если исключить из числителя все подмножества объёмов всех соседей снизу понятия С, мы получим оценку снизу, так как некоторые подмножества могут быть исключены дважды. С другой стороны, исключение подмножеств только одного соседа снизу, исключает лишние подмножества Ext (С) единожды, но часть лишних подмножеств не будет исключена. Таким образом, мы получаем утверждение 11 для оценки устойчивости формального понятия. где DD(C) - это множество всех соседей снизу данного понятия в решётке, а Д(С,Р) := Ext(C) \ Ext(D) -разница в количестве объектов между объёмами понятий С и V.
Нахождение данной оценки может быть реализовано с помощью алгоритма 1. Теоретическая сложность данного подхода совпадает со сложностью нахождения всех соседей снизу для данного понятия, то есть 0(\G\ \М\2), для простого формального контекста (G,M,I). Данная оценка может быть применена для одного понятия и не требует нахождения всего множества понятий, что особенно важно для больших решёток, в которых нахождение всех понятий не представляется возможным. Назовём этот подход методом оценивания.
Пример 5. Согласно формуле (3.3) для нахождения всех понятий с устойчивостью не меньше 0.97 следует выбрать только понятия С, для которых Amin(C) = min А(С,Т ) превышает 5 (Ат[П(С) Алгоритм, вычисляющий устойчивость формального понятия согласно (3.3) . Известно, что для данного контекста, количество наследников у формального понятия не может превышать количество признаков в контексте (,,). Каждое слагаемое нижней оценки в формуле (3.3) не превышает 2 А С\ Тогда:
Таким образом, эта оценка и верхняя оценка формулы (3.3) подсказывают, что устойчивость может иметь полезное на практике поведение в логарифмической шкале. Так, например, авторы работы [53] замечают, что на достаточно больших контекстах, большая часть понятий имеет устойчивость близкую к единице, что не позволяет выбирать наиболее релевантные понятия. Позже будет показано на различных больших контектсах, что такое поведение свойственно всем выборкам данных. Таким образом, необходимо рассмотреть устойчивость также и в логарифмической шкале:
Данная оценка позволяет эффективно оценивать устойчивость в том числе в удобной логарифмической шкале. Однако точность данной оценки (разность между верхней и нижней оценками) не может быть задана заранее. Здесь метод оценивания устойчивости методом Монте-Карло, предложенный в работе [11], оказывается полезным. Идея данного метода состоит в том, чтобы для понятия С случайным выбором оценить количество подмножеств его объёма s С Ext (С) таких, что описание этих подмножеств совпадает с содержанием понятия С, то есть, что s = Int(C). Затем, зная количество случайно выбранных подмножеств N и количество искомых подмножеств среди них Ngood можно оценить устойчивость как Stab (С) = % . Далее, авторы этой работы приводят следующую оценку количества требуемых итераций:
Подсистема построения узорной решётки
Для построения узорной решётки понятий достаточно лишь немного изменить существующие алгоритмы построения решёток формальных понятий. Теоретико-множественная операция пересечения должна быть заменена на полурешёточную операцию сходства, а операция проверки того, что одно множество является подмножеством другого, должна быть заменена на проверку поглощения одного элемента полурешётки другим. Так Алгоритм 3 показывает псевдокод алгоритма Замыкай по Одному (ЗО) [70; 73], модифицированного для работы с узорными структурами. Этот алгоритм для понятия, задаваемого объёмом и содержанием, находит всех канонических соседей сверху. Алгоритм ЗО пробегается по всем допустимым расширениям объёма начального понятия и проверяет, что замыкание этого расширения также является допустимым. Допустимость объёма не требует изменений для работы с узорными структурами и, таким образом, проверяется в точности по [70].
Аналогичным образом могут быть модифицированы другие классические алгоритмы, строящие решётки формальных понятий. В качестве следующего примера рассмотрим алгоритм AddIntent [87], который позволяет находить не только множество формальных понятий, но и вычислять диаграмму покрытия отношения частичного порядка на понятиях. Алгоритм 4 показывает каким образом должны быть изменены строки с 8 по 24 изначального алгоритма AddIntent для обработки узорных понятий. Function CloseByOne(Ext, Int)
Математический формализм узорных структур позволяет работать с любыми типами полурёшеток описаний. Но как возможно передать программе структуру этой полурешётки? Один из возможных подходов - заранее ограничить количество типов узорных структур, научив программную систему обрабатывать узорные структуры, основанные, например, на интервалах, графах и последовательностях. Но такой подход существенно ограничивает возможности пользователей системы по использованию узорных структур. Другим подходом может быть система, которая позволяет передавать пользователю любую полурешётку описаний. Но напрямую передавать всю полурешётку во многих случаях невозможно, так как размер этой решётки может быть очень большим, либо даже бесконечным. Более того, это может привести пользователя к необходимости расчёта foreach Candidate Є Generator Parents do
Algorithm 4: Изменёные строки с 8 по 24 алгоритма AddIntent для работы с узорными структурами. всей полурешётки, что, в силу её большого размера, может серьёзно понизить производительность системы. Альтернативным способом передачи полурешётки описаний является неявное задание полурешётки. Другими словами, можно просить пользователя определять операцию сходства между любыми двумя узорами, интересующего его вида. Этот подход с одной стороны эффективно решает проблемы предыдущих двух подходов, с другой стороны возникает необходимость для пользователя программировать с использованием API программного обеспечения для обработки нужных ему узорных структур, что также может ограничить применяемость системы. Мы остановились на последнем варианте, с тем дополнением, что все написанные узорные структуры могут быть сохранены в системе как библиотеки для последующего переиспользования. Таким образом мы позволяем пользователям использовать узорные структуры известных типов, что существенно может сохранить время на разработку своей узорной структуры. С другой стороны мы позволяем пользователю разрабатывать узорные структуры любой сложностью, переиспользуя стандартные части системы. Так, например, пользователь может выбрать любой из доступных алгоритмов построения решётки формальных понятий, задав только решёточную операцию сходства для интересующих его описаний.
Таким образом, для использования полурешётки (D, П) достаточно для любых двух описаний из ж, у Є D определить операцию сходства z = х П у, где z Є D. Как было отмечено для модификации любого классического алгоритма для работы с узорными структурами необходимо так же уметь сравнивать два описания согласно частичному порядку поглощения описаний, которая может быть выражена через решёточную операцию сходства: х Ц у х П у = х. Значит любая узорная структура на полурешётке, заданной операцией сходства, может быть рассчитана многими классическими алгоритмами, такими как Noris [92], NextClosure [39], Bordat [16], CbO [70], Addlntent [87] и другие.
В качестве форматов передачи данных был выбран стандарт JSON 1. Данный стандарт позволяет представить практически любой тип данных и имеет при этом небольшую сложность обработки и невысокий объём памяти, требуемый для хранения элементов самого JSON. В частности, JSON является более компактным универсальным представление данных, чем XML. Следующие форматы данных являются частоиспользуемыми и поэтому их необходимо зафиксировать для более простого взаимодействия между отдельными модулями: примитивные типы (числа, строка), множества, упорядоченные множества или вектора, корневые деревья, решётки формальных понятий и общие структуры или графы.
Выбор формата JSON позволяет также облегчить импорт из внешних источников данных. В частности, существует множество программных средств, умеющих работать с JSON. В случае программных средств по работе с узорными структурами, внешняя выборка данных должна быть сконвертирована в JSON представление.
Похожие диссертации на Моделирование процессов с состояниями сложной структуры на основе решеток замкнутых описаний
