ВУЗ:
Составители:
4.4. РАЗРАБОТКА АЛГОРИТМА ПОЛУЧЕНИЯ
ЧАСТЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ
Рассмотрим проблему поиска наиболее повторяющихся шаблонов (т.е. подграфов в нашей терминологии) в экземпля-
рах бизнес-процессов, заключающейся в нахождении наиболее повторяющихся фрагментов в бизнес-процессе при его вы-
полнении.
Одной из разновидностей задачи поиска частых подпоследовательностей является задача ответа на вопрос: какие зада-
чи из модели бизнес-процесса, представленного на рис. 10, выполняются в наиболее часто при выполнении задачи h? В каче-
стве примера рассмотрим экземпляры:
b
a
c
f i
d g
h
b
a
c
i
d g
h
Рис. 11. Экземпляры для бизнес-процесса "Обработка заказа от клиента"
Отметим, что оба графа с рис. 11 являются подграфами первоначальной модели бизнес-процесса, показанного на рис.
10, и удовлетворяет ограничениям там указанным. Кроме того, оба подграфа соответствуют требованию на содержание узла
h.
Рассмотрим подграф с рис. 12.
a
dc g h
Рис. 12. Подграф для экземпляров с рис. 10
Часто выпадает при выполнении обоих экземпляров, и характеризуется выполнением задач c, d, g. В таком случае это
может означать, что отказ от обслуживания часто характеризуется недостатком материалов на предприятии. С точки зрения
анализа бизнеса становится очевидным необходимость внесения изменений в стратегию управления хранением комплек-
тующих. Сложность решения задачи поиска наиболее частых шаблонов заключается в выборе алгоритма генерации желае-
мых паттернов путем "умного" изучения области поиска, на которые накладываются ограничения схемы.
При поиске частых подпоследовательностей WF-модель выступает в качестве стартовой точки исследования, а не ре-
зультата: некоторое количество исполнений бизнес-процесса анализируется контекстуально и базируется на этой WF-модели
с целью найти частые шаблоны выполняемых задач, таким образом исследуя полезную информацию для поддержки приня-
тия решений в организации. С учетом этой перспективы исследование следует сопоставить с другими попытками анализа
частых подпоследовательностей. Наиболее известны из этого класса исследований базирующиеся на свойстве антимоно-
тонности. В этой работе представляется алгоритм "Apriori": общая идея заключается в генерации множества кандидатов
k + 1, комбинируя в подходящем случае размер k множества частых шаблонов, и проверяя их частоту.
Совершенно иное исследование проблемы было предложено в [6], которое использует метод "FP-growth". По существу
идея анализа частых шаблонов совпадает с вышеописанным, посредством рекурсивного проецирования базы данных на час-
тые шаблоны уже найденные и затем комбинирование результатов исследования с проецированной базой данных. Расшире-
ние этой идеи для последовательных шаблонов предложено в [7]. Недавняя попытка комбинирования такого метода с алго-
ритмом Apriori была предпринята в [8].
Как и проблема интеллектуального анализа шаблонов в сложных предметных областях, исследование частых деревьев
была произведена в [9] (алгоритм "AGM"), в то время, как первый алгоритм в этом направлении, базирующийся на свойстве
антимонотонности, был предложен в [10]. Отметим, что эта задача все еще обещает интересные задачи в различных пред-
метных областях, таких как биоинформатика и анализ web-документов.
Например, поиск используемый в "AGM" был адаптирован и улучшен в алгоритме "FSG" [11], в котором используется
умная стратегия для маркировки сгенерированных графов с целью уменьшить вычислительные расходы на проверку изо-
морфности графов. Более того, в настоящее время появляются новые алгоритмы, основанные на методе проекции: "gSpan"
[12] исследует все подграфы без генерации кандидатов и использует позитивное усечение, в то время как "CloseGraph" [13]
сокращает количество шаблонов, подлежащих генерации за счет использования понятия закрытых шаблонов, т.е. шаблонов,
которые не являются подграфами для других шаблонов с той же поддержкой.
Понятно, что подобные подходы могут быть использованы для решения проблемы поиска наиболее частых последова-
тельностей для WF-моделей, после адаптации этих алгоритмов с учетом специфики данного прикладной области примене-
ния.
Тем ни менее адаптация вышеописанных методов к поиску частых подпоследовательностей в автоматизированных биз-
нес-процессах – сложная задача. Действительно, генерация шаблонов посредством таких традиционных подходов не учиты-
вает тех ограничений, которые накладывает сама схема, таких как взаимоотношения между задачами, синхронизация и па-
раллельное выполнение задач (см. [14] – [16]). В противоположность этому алгоритмы, представленные ниже, учитывает эти
ограничения, накладываемые структурой WF-модели. А экспериментальные результаты представленные далее показывают,
что они превосходят традиционные подходы к восстановлению частых подпоследовательностей.
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
