Интеллектуальный анализ выполнения бизнес-процессов в системе электронного документооборота. Матвейкин В.Г - 41 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

4.4.1. Алгоритм поиска частых подпоследовательностей "f-поиск"
Определим необходимые в дальнейшем понятия. Допустим у нас есть WF-модель
P
и множество экземпляров
}...,,{
1 n
IIF =
. Граф
PEAp
pp
>⊆=< ,
называется F-шаблоном, если существует
FEAI
II
>∈=< ,
такое, что
Ip
AA ⊆
и
p
подграф
I
, включенный посредством узлов в
P
A
.
Допустим
||/|}||{|)(
FpIFIpfreq
=∈=
поддержка F-шаблона
p
. Тогда мы можем дать следующее определение:
Определение 6 (Математическая формулировка задачи).
)(σFCPD
: задача поиска всех связанных шаблонов, под-
держка которых больше чем
σ
.
Если подходить к решению этой задачи прямолинейно, то напрашивается алгоритм поиска шаблонов на основе простой
генерации прямо связанных подграфов, а затем тестирование в полиномиальном времени является ли этот шаблон экземпля-
ром для
P
. Другое предложение основано на идее ослабления количества шаблонов, подлежащих генерации. Для того что-
бы добиться этой цели, мы можем рассматривать только графы, которые "закрыты" (с учетом глобальных и локальных огра-
ничений), т.е. таких, что
cp =|
для всех
. Будем называть такие графы ослабленными шаблонами или просто w-
шаблоны. Формализуем приведенные выше рассуждения:
Определение 7. Дана WF-модель
>=<
′
′′
pp
EAp ,
, детерменестическое закрытие
p
(
)(_ pзакрытиеws
) определяется,
как граф
>=<
′
′′
pp
EAp ,
такой, что: (1)
pp
AA
′
⊆
, и
pp
EE
′
⊆
, (2)
p
Aa
′
∈
– and-join подразумевает, что для каждого
Eab ∈),(
,
p
Eab
′
∈),(
и
p
Ab
′
∈
, (3)
p
Aa
′
∈
– deterministic fork подразумевает, что для каждого
Eba ∈),(
с
b
– or-join,
p
Eba
′
∈),(
и
p
Ab
′
∈
. Более того граф
p
такой, что
)(_ pзакрытиеwsp =
называется
закрытымws _
.
Определение 8. Ослабленный шаблон, или просто w-шаблон, это
закрытыйws _
граф
p
, такой что для каждого узла
a
, )(|}),(|),{(|
max
aOUTEbaba
p
≤∈ .
Определение 9. Пусть дана WF-модель
>=< EAWS ,
, тогда для каждого
Aa ∈
граф
){}},{(_ ><= aзакрытиеwsp
на-
зывается элементарным w-паттерном.
Для поиска решения задачи используется алгоритм, который инкрементально строит частые w-шаблоны, стартуя с
"элементарных"
w-шаблонов (описанных ниже) и расширяя каждый частый шаблон max посредством использования двух базовых операций:
добавление частой дуги и слияние с другим частым элементарным w-шаблоном.
Элементарные w-шаблоны, с которых начинается построение частых шаблонов, получаются как детерменестическое
закрытие отдельных узлов. Шаблон является элементарным w-шаблоном (обозначим через ew-шаблон) для узла
a
, если это
минимальный w-шаблон содержащий
a
. Множество всех ew-шаблонов обозначается как
EW
. Более того, пусть
p
w-шаблон,
тогда
p
EW
обозначает множество элементарных w-шаблонов содержащихся в
p
. Заметим, что если дан ew-шаблон
e
,
e
EW
не
обязательно содержит только один элемент, может содержать другие ew-шаблоны. Кроме того, данное множество
EWE ⊆
′
,
Ee
e
EWEWECompl
′
∈
−=
′
)(
содержит все элементарные шаблоны, которые не содержатся ни в
E
′
ни в одном элементе
E
′
.
Теперь введем операцию отношения
между связанными w-шаблонами. Определим через
⊆
E
множество всех дуг в
P
, источники которых не являются and-split, т.е.
)}()(|),{(
min
aOutDegreeaOUTEbaE <∈=
⊆
. Даны два соединенных w-
шаблона
>=<
pp
EAp ,
и
>=<
′
′′
pp
EAp ,
, мы говорим что
pp
′
тогда и только тогда, когда:
1.
pp
AA
′
=
и
)},{( baEE
pp
∪=
′
, где
p
EEba −∈
⊆
),(
и
)()(
max
aOutDegreeaOUT
p
>
(т.е.
p
′
может быть получила из
p
посредством добавления дуги).
2. Существует
)(
p
EWComplp ∈
′′
такая, что
Xppp ∪
′′
∪=
′
, где
X
либо пустое множество, если
p
и
p
′′
связанные
или содержит дугу в
⊆
E
с конечными точками в
p
и
p
′′
(т.е.
p
′
получено из
p
путем добавления элементарного w-
шаблона и возможно соединяющей дуги.)
При работе алгоритма инкрементально строятся частые w-шаблоны с использованием двух базовых операций: добавле-
ние частой дуги и слияние с другим частым w-шаблоном.
Элементарные шаблоны с которых начинается алгоритм получаются как
)(_ pзакрытиеws
для каждого из узлов. Далее
идет вычисления в главном цикле алгоритма, где каждое новое значение для
1+k
L
получается путем расширения любого
шаблона
p
сгенерированного на предыдущем шаге (
k
Lp ∈
) двумя способами: 1) добавлением частой дуги из
⊆
E
(посред-
ством функции
tArcaddFrequen
) и 2) добавлением элементарного w-шаблона (функция
tEWPatternAddFrequen
). Каждый
шаблон
p
′
, генерируемый функциями, указанными выше, – допустимый подграф для
WS
, т.е. для каждой
p
Aa
′
∈
,
)()(
max
aOUTaOutDegree
p
≤
′
.
Приведем псевдокод алгоритма:

Страницы