Диссертация (1137259), страница 3
Текст из файла (страница 3)
Эти взаимосвязи позволяют нам говорить об обобщённыхсостояниях и обобщённых реализациях процесса. В таких состояниях часть из доступной информации не рассматривается, но они чащевстречаются в реализациях процесса. Например, состояние “госпитализация территориально расположенная в московской области” является обобщённым состояниям для “госпитализация территориальнорасположенная в Москве”, так как последнее состояние предполагает, что оно также является и первым состояниям, но не наоборот.Таким образом, реализации процессов с состояниями сложнойструктуры описываются последовательностями элементов некоторого частично-упорядоченного множества состояний.
Этот частичный порядок на множестве состояний представляет отношение типа "быть более общим чем"или "быть частью". Таким образом, реализация процесса с состояниями сложной структуры – это элемент * (слово в алфавите ), где (, ≤) – некоторое частичноупорядоченное множество.1.3Плоские моделиСуществует несколько плоских моделей, которые могут бытьсозданы методами анализа процессов. К таким моделям относятся: системы переходов и Петри-сети [3], WF-сети (частный случай Петри-ситей, используемый для моделирования бизнес процессов) [4], YAWL [111], BPMN [124], EPC [104]. Эти модели обладают разной степенью выразительности, в частности, системы переходов не могут выразить конкурентных состояний в процессе.
Большинство этих моделей может быть достаточно просто преобразованодруг в друга, когда это допускают средства выразительности. Например, сети Петри могут быть легко преобразованы в BPMN [6].15На данный момент существует несколько обзорных статей,описывающих анализ процессов [3; 32]. Они выделяют альфаалгоритм [6], как один из первых подходов к построению моделей,который может обрабатывать конкурентные состояния. Данный алгоритм анализирует отношение предшествования между любыми двумя элементами в реализациях процесса. Так может быть найдено,что один элемент всегда следует за другим, они оба следуют друг задругом, либо никогда не встречаются в одной реализации процесса.На основании чего создаются исключающие события, параллельныесобытия или ветвление.
Этот алгоритм строит сеть Петри. Существует несколько его расширений, которые позволяют получить WFсеть, т.е. Петри-сеть, в которых в частности отсутствуют дубликатыи подвешенные состояния [6]. Альфа-алгоритм строит достовернуюмодель процесса в случае, когда содержаться все возможные реализации процесса, и не содержится шумов.Среди всех алгоритмов построения моделей процессов можновыделить подходы, которые выделяют некоторые “отпечатки” реализаций процессов [14; 22; 122; 121; 123]. Также в эту группу следует отнести подходы [119; 120], которые в отличие от предыдущихиспользуют поддержку (количество реализаций процесса, описываемых той или иной частью модели), что позволяет им бороться сшумами в данных, описывающих процесс. Именно к таким алгоритмам относится альфа-алгоритм.
В частности для него “отпечатком”является отношение следования для разных состояний процесса.К другой группе алгоритмов относятся двух-проходные алгоритмы, которые сначала строят простую модуль процесса, а затем используют её для создания более сложной модели, с большей выразительностью. Примерами простых моделей могут служить марковскиецепи и системы переходов.
Так, например, алгоритм [7] строит сначала систему переходов, которую затем преобразует в Петри-сеть, вкоторой уже возможно выразить конкурентные состояния.Третью группу подходов образуют алгоритмы, основанные на методах искусственного интеллекта, в том числе на генетическом про16граммировании, нейроных сетях, размытых и грубых множествах итак далее.
Например, в подходе [85] авторы используют генетическоепрограммирование для получения модели процесса. Каждая модельсоответствует одному индивиду. Жизнеспособность индивида задаётся через его возможность моделирования всех реализаций процесса. На каждой итерации лучшие индивиды скрещиваются, с введением случайных мутаций. Таким образом качество модели от популяции к популяции возрастает. Процесс останавливается, когда будетполучена модель с хорошими характеристиками.Для алгоритмов построения плоских моделей процесса выделяют4 критерия качества, которые оптимизируются в разных пропорцияхразличными алгоритмами∙ вписывание – это критерий, согласно которому, чем больше известных реализаций процесса могут быть промоделированы,тем лучше;∙ точность – критерий, согласно которому, реализации, существенно отличающиеся от известных, не должны описыватьсямоделью;∙ простота – критерий, согласно которому, количество вершин ирёбер в схеме процесса должно быть минимально.∙ обобщение – критерий, соответствующий обобщающей способности модели, по сути является композицией предыдущихкритериев.Общим недостатком всех рассмотренных в этом подразделе подходов является возможность обработки только простых состояний,то есть когда у каждого состояния есть только имя, но нет никакихвнутренних связей между состояниями, что приводит к невозможности использования таких подходов для исследования процессов ссостояниями сложной структуры.
Более того, нет понимания того,как состояния сложной структуры могут быть переданы в рамкахплоских моделей без существенного увеличения модели.171.4Модели последовательностейРеализации многих процессов могут быть представлены последовательностями состояний. Соответственно в данном разделе представлены подходы к анализу данных, описываемых последовательностями.
Такие методы получают множества подпоследовательностейпо множеству последовательностей, называемых также выборкой.Каждое такое множество последовательностей является элементарной моделью процесса разной степени общности. Здесь такие элементарные модели мы также называем закономерностями.Одним из первых таких подходов является работа [9].
Высокийинтерес к анализу последовательностей, вызванный данными порождаемых процессами или периодическими явлениями, повлёк за собойбольшое количество работ по анализу таких данных. Эти подходычасто создавались, исходя из конкретной задачи, что может объяснить большой объём таких работ, но в то же время высокую практическую значимость. Большинство подходов к анализу данных, представленных последовательностями могут быть найдены в различныхобзорах [38; 46; 81; 88; 95; 126; 138]. Сравнение эффективностинекоторых методов по поиску частых подпоследовательностей может быть найдено в [66].Первая работа анализа последовательностей, вводит три алгоритма: AprioryAll, ApriorySome и DynamicSome [9]. Авторы описывают пятишаговый алгоритм.
Сначала они модифицируют реляционные таблицы базы данных в последовательности, затем находятчастые множества признаков, описывающих одно состояние, послечего каждая последовательность описывается только частыми множествами признаков. Далее ищутся частые множества множеств признаков, соответствующие последовательностям. В заключительномэтапе выбираются только максимальные последовательности. Различия между этими алгоритмами состоят в различном способе подсчёта результирующих последовательностей. Следующий подход GSP ванализе последовательностей был введён теми же авторами [109], в18котором они обобщают предыдущий подход и добавляют ограничения на возможные последовательности.
Алгоритм состоит из двухэтапов:Порождение. Порождаются все последовательности длины +1, где – это длина последовательности на данной итерации.Отсечение. Дубликаты порождённых последовательностей удаляются из рассмотрения.Следующим был алгоритм PSP [84], использовавший древеснуюструктуру для хранение последовательностей.
Для того чтобы иметьвозможность учитывать пользовательские ограничение, разрабатывается поход, который позволяет устанавливать ограничения на допустимые последовательности регулярными выражениями [43]. Наряду с [109], эта работа одна из первых, которая вводит ограниченияна получаемые закономерности. Наряду с полными методами, были введены неполные, порождающие лишь подмножество всех искомых последовательностей.
К таким методам относятся [79; 113], вкоторых авторы используют отсечение ветвей поиска на основаниистатистических методов.До сих пор мы рассматривали методы, имеющие горизонтальный формат хранения последовательностей. Горизонтальное представление – это такой способ представления последовательностей,для которого в выборке нужно сначала задать идентификатор объекта, а затем по идентификатору объекта можно получить его описание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
