特殊循環(huán)結(jié)構(gòu)的過程挖掘算法

賀朝陽(yáng)，杜玉越，王 路

山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590

1 引言

過程挖掘在數(shù)據(jù)挖掘和過程建模與分析兩個(gè)領(lǐng)域的知識(shí)之間搭建橋梁，從事件日志中提取知識(shí)，進(jìn)而發(fā)現(xiàn)、監(jiān)控和改進(jìn)實(shí)際過程。有三種類型的過程挖掘場(chǎng)景使用了事件日志，分別為過程發(fā)現(xiàn)、一致性檢測(cè)和過程增強(qiáng)[1]。過程發(fā)現(xiàn)是使用不包含先驗(yàn)信息的日志挖掘得到模型；一致性檢測(cè)是比較日志實(shí)際情況和挖掘的過程模型是否吻合，或者比較已知模型與其產(chǎn)生的日志的情況是否吻合；過程增強(qiáng)是對(duì)于一個(gè)已存在的過程，利用實(shí)際過程產(chǎn)生的日志對(duì)其進(jìn)行改進(jìn)或擴(kuò)展。

在過程挖掘中，日志完備性至關(guān)重要。完備性與噪聲類似，噪聲表示日志中含有過多數(shù)據(jù)問題，而完備性表示日志中含有數(shù)據(jù)過少問題。缺少特殊日志行為的非完備事件日志將會(huì)對(duì)挖掘算法的實(shí)際工作產(chǎn)生影響，導(dǎo)致無法挖掘正確模型。噪聲和完備性描述了關(guān)于事件日志的質(zhì)量問題，而模型質(zhì)量的度量需要從不同維度來描述。過程模型有擬合度、精確度、泛化度和簡(jiǎn)潔度這四個(gè)主要度量維度。模型的擬合度表示事件日志中的跡在過程模型中的重演能力，擬合度高的模型說明其允許事件日志中所反映的行為發(fā)生。模型的精確度決定模型是否允許日志以外的行為出現(xiàn)，模型精確度高說明其不允許過多日志以外的行為發(fā)生。模型的泛化度代表模型不僅僅局限于日志中的行為，允許更多額外行為。簡(jiǎn)潔度好的模型說明是能夠解釋日志中所見行為并且最簡(jiǎn)單的模型。

目前，國(guó)內(nèi)外學(xué)者提出了許多過程挖掘算法。文獻(xiàn)[2]提出了挖掘工作流模型的α算法，并證明了能準(zhǔn)確挖掘出的模型種類。從實(shí)踐日志中挖掘過程模型時(shí)，很多實(shí)際業(yè)務(wù)流程對(duì)應(yīng)的工作流模型中存在復(fù)雜結(jié)構(gòu)，如非自由選擇結(jié)構(gòu)（non-free-choices）、不可見任務(wù)（invisible tasks）、重名任務(wù)（duplicate tasks）以及長(zhǎng)短不一的循環(huán)結(jié)構(gòu)（loop）。α算法通過分析日志中活動(dòng)之間的依賴關(guān)系來挖掘模型。這些依賴關(guān)系的定義基于局部日志行為，對(duì)于短循環(huán)和非自由選擇結(jié)構(gòu)等復(fù)雜結(jié)構(gòu)無法處理。文獻(xiàn)[3]提出的α+算法擴(kuò)展了α算法，針對(duì)長(zhǎng)度為1和2的短循環(huán)進(jìn)行挖掘。文獻(xiàn)[4]在此基礎(chǔ)上提出了能夠處理非自由選擇結(jié)構(gòu)的α++算法。文獻(xiàn)[5]利用啟發(fā)式規(guī)則發(fā)現(xiàn)日志中的循環(huán)任務(wù)和重復(fù)任務(wù)，提出了τ算法。文獻(xiàn)[6]基于啟發(fā)式挖掘算法，擴(kuò)展了長(zhǎng)距離依賴關(guān)系的度量，對(duì)多個(gè)模型進(jìn)行并行挖掘，提升了針對(duì)短循環(huán)以及長(zhǎng)距離依賴的挖掘效果。文獻(xiàn)[7]和[8]將遺傳算法應(yīng)用于過程挖掘，解決了非自由選擇結(jié)構(gòu)、不可見任務(wù)以及重名任務(wù)等復(fù)雜結(jié)構(gòu)的挖掘問題。文獻(xiàn)[9]提出了一種層次化擬合功能，結(jié)合了遺傳算法和啟發(fā)式算法，能夠處理包含不可見任務(wù)和循環(huán)結(jié)構(gòu)等多種復(fù)雜結(jié)構(gòu)?；谡Z(yǔ)言的區(qū)域挖掘[10-11]、基于狀態(tài)的區(qū)域挖掘[12]以及ILP挖掘算法[13]對(duì)模型的擬合度有很好的保證。在現(xiàn)有的挖掘算法中，大多基于完備事件日志進(jìn)行過程挖掘，然而實(shí)際業(yè)務(wù)過程中存在非完備日志的情況。文獻(xiàn)[14]針對(duì)塊狀結(jié)構(gòu)過程模型的挖掘，提出了IM算法，可以對(duì)非完備的日志進(jìn)行挖掘，并且挖掘得到的模型具有極高的擬合度。文獻(xiàn)[15]定義了因果完備日志，基于這種非完備日志，提出了針對(duì)塊狀并發(fā)結(jié)構(gòu)進(jìn)行挖掘的α||算法。

在不考慮重名活動(dòng)的情況下，對(duì)于存在循環(huán)結(jié)構(gòu)的事件日志，同一條跡中一定存在出現(xiàn)次數(shù)大于2的活動(dòng)。對(duì)于α系列算法，當(dāng)循環(huán)結(jié)構(gòu)與其他結(jié)構(gòu)處于并發(fā)關(guān)系時(shí)，其定義的活動(dòng)間依賴關(guān)系存在局限。對(duì)于同一循環(huán)結(jié)構(gòu)中的活動(dòng)在日志的跡中沒有連續(xù)出現(xiàn)時(shí)，α系列算法將不能正確地發(fā)現(xiàn)嵌套在并發(fā)結(jié)構(gòu)中的循環(huán)結(jié)構(gòu)。本文針對(duì)存在循環(huán)結(jié)構(gòu)的日志完備性進(jìn)行了探討，給出了新的定義，并針對(duì)一種特殊循環(huán)結(jié)構(gòu)的挖掘提出了αfsl算法。該算法主要通過預(yù)處理日志以及后處理添加結(jié)構(gòu)實(shí)現(xiàn)，主要目標(biāo)為在重新定義的循環(huán)完備日志中挖掘存在于并發(fā)結(jié)構(gòu)中的特殊循環(huán)結(jié)構(gòu)。

2 基本概念

本章描述了多重集合[16]、序列、跡[17]、事件日志、Petri網(wǎng)[18-19]、工作流網(wǎng)[20]、α算法[2]等基本概念。在本文中，N代表一個(gè)自然數(shù)集合，N={ }0,1,2,…。

定義1（多重集合）設(shè)S是一個(gè)集合，一個(gè)S上的多重集合定義為一個(gè)函數(shù)Z:S→N。Β()S代表了S上的所有多重集合組成的集合。

定義2（序列）設(shè)S是一個(gè)集合，S*是S上所有有限序列組成的集合。是一個(gè)序列，σ[i]表示序列σ中第i個(gè)元素，|σ|表示序列σ的長(zhǎng)度。

σ是一個(gè)序列，對(duì)于?a∈σ，σ(a)表示a在σ中出現(xiàn)的次數(shù)。例如

定義3（跡）設(shè)A是活動(dòng)集合，一條跡σ∈A*是一個(gè)活動(dòng)的隊(duì)列。

定義4（事件日志）事件日志L是跡σ的多重集合，記為L(zhǎng)∈Β( )A*。

Petri網(wǎng)是由庫(kù)所（place）和變遷（transition）組成的有向二分圖。

定義5（Petri網(wǎng)）三元組 PN=(P ,T;F)稱為一個(gè)Petri網(wǎng)，其中P是一個(gè)有限庫(kù)所集，T是一個(gè)有限變遷集，是一個(gè)有限弧集。對(duì)于變遷t∈T ，?t表示t的輸入集，t?表示t的輸出集。

在本文中，模型中的變遷和日志中的活動(dòng)一一對(duì)應(yīng)，在一些情況下不進(jìn)行區(qū)分。工作流網(wǎng)是一個(gè)有著唯一初始庫(kù)所和終止庫(kù)所的Petri網(wǎng)。

定義6（工作流網(wǎng)）五元組WFN=( )P,T;F,i,o稱為一個(gè)工作流網(wǎng)當(dāng)且僅當(dāng)：

（1）PN=( )P,T;F 為一個(gè)Petri網(wǎng)；

（4）對(duì)于?x∈P?T，x在一條從i到o的路徑上。

定義7（基本活動(dòng)次序關(guān)系）令W是一個(gè)覆蓋T工作流日志，i.e.,W∈Β( )T*。令a,b∈T：

跟隨關(guān)系a＞W(wǎng)b：當(dāng)且僅當(dāng)存在一條跡使得 σ∈W,ti=a并且ti+1=b；

因果關(guān)系a→Wb：當(dāng)且僅當(dāng)a＞W(wǎng)b并且b≯Wa；

定義8（α算法）[2]令W代表覆蓋T的工作流日志。α(W)定義如下：

3 自由單循環(huán)結(jié)構(gòu)

本章說明了α算法及其衍生算法挖掘特殊循環(huán)結(jié)構(gòu)時(shí)的局限，并給出了自由單循環(huán)結(jié)構(gòu)及自由單循環(huán)完備日志的定義。

在挖掘并發(fā)結(jié)構(gòu)中嵌套的循環(huán)結(jié)構(gòu)時(shí)，α算法及其衍生算法都存在一定的局限性。

首先，針對(duì)不同長(zhǎng)度循環(huán)結(jié)構(gòu)進(jìn)行挖掘時(shí)，α算法存在以下局限：對(duì)于長(zhǎng)度為1的循環(huán)結(jié)構(gòu)（即自環(huán)結(jié)構(gòu)），α算法會(huì)將循環(huán)結(jié)構(gòu)中的活動(dòng)識(shí)別為與模型其他部分獨(dú)立的一個(gè)活動(dòng)；對(duì)于長(zhǎng)度為2的循環(huán)結(jié)構(gòu)，結(jié)構(gòu)中的兩個(gè)活動(dòng)互相存在跟隨關(guān)系，與并發(fā)關(guān)系的定義完全一致，即α算法無法區(qū)分長(zhǎng)度為2的循環(huán)結(jié)構(gòu)和由兩個(gè)活動(dòng)組成的并發(fā)結(jié)構(gòu)；對(duì)于長(zhǎng)度為3以及更長(zhǎng)的循環(huán)結(jié)構(gòu)，α算法能夠正確挖掘。因?yàn)檠h(huán)中包含3個(gè)及以上活動(dòng)時(shí)，采用跟隨關(guān)系即(＞W(wǎng))能夠清楚地表達(dá)并且區(qū)分并發(fā)結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

在日志完備的前提下，對(duì)于α算法的衍生算法，包括α+算法等，通過后處理等方法添加了長(zhǎng)度為1的循環(huán)結(jié)構(gòu)；通過預(yù)處理重新定義并發(fā)關(guān)系等方法，解決了長(zhǎng)度為2的循環(huán)結(jié)構(gòu)和并發(fā)結(jié)構(gòu)的區(qū)分問題。

當(dāng)并發(fā)結(jié)構(gòu)中存在循環(huán)結(jié)構(gòu)時(shí)，如果日志中沒有包含明確的循環(huán)結(jié)構(gòu)的特征（即循環(huán)結(jié)構(gòu)中包含的活動(dòng)連續(xù)多次出現(xiàn)），現(xiàn)有的α算法及其部分衍生算法便不能正確地發(fā)現(xiàn)存在于并發(fā)結(jié)構(gòu)中的循環(huán)結(jié)構(gòu)。圖1展示了兩種并發(fā)結(jié)構(gòu)中嵌套循環(huán)結(jié)構(gòu)的情況。圖（a）中WFN1表示了長(zhǎng)度為1的循環(huán)結(jié)構(gòu)與單個(gè)活動(dòng)處于并發(fā)結(jié)構(gòu)的情況，圖（b）中WFN2表示了三種不同長(zhǎng)度的循環(huán)結(jié)構(gòu)處于并發(fā)結(jié)構(gòu)的情況。

本文僅針對(duì)如圖1（a）、（b）中的這類循環(huán)結(jié)構(gòu)嵌套在并發(fā)結(jié)構(gòu)的情況進(jìn)行挖掘，但循環(huán)結(jié)構(gòu)的長(zhǎng)度和數(shù)量不局限于圖中情況。

圖1 兩種并發(fā)結(jié)構(gòu)嵌套循環(huán)結(jié)構(gòu)情況

當(dāng)日志中任何一條跡中不包含連續(xù)多次出現(xiàn)的活動(dòng)或者活動(dòng)集，例如等情況，使用α算法及其部分衍生算法不能有效挖掘并發(fā)結(jié)構(gòu)中嵌套的此類循環(huán)結(jié)構(gòu)。

對(duì)于圖1（a）、（b）中的這類循環(huán)結(jié)構(gòu)，其起始庫(kù)所和終止庫(kù)所為同一個(gè)庫(kù)所，本文中稱為自由單循環(huán)結(jié)構(gòu)。此類循環(huán)結(jié)構(gòu)自由的特點(diǎn)表現(xiàn)為日志中至少存在一條跡不包含該循環(huán)結(jié)構(gòu)中的活動(dòng)，而且該循環(huán)結(jié)構(gòu)是一個(gè)單循環(huán)，即循環(huán)內(nèi)部是順序結(jié)構(gòu)，沒有其他的分支結(jié)構(gòu)。圖2展示了不同長(zhǎng)度的自由單循環(huán)結(jié)構(gòu)的例子。圖（a）中WFN3含有長(zhǎng)度為1的自由單循環(huán)結(jié)構(gòu)，圖（b）中WFN4含有長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)，圖（c）中WFN5含有長(zhǎng)度為3的自由單循環(huán)結(jié)構(gòu)。

圖2 三種長(zhǎng)度的自由單循環(huán)結(jié)構(gòu)

定義9（自由單循環(huán)結(jié)構(gòu)）設(shè)WFN=(P ,T;F,i,o)為一個(gè)工作流網(wǎng)，F(xiàn)SL是WFN的一個(gè)自由單循環(huán)結(jié)構(gòu)當(dāng)且僅當(dāng)FSL=(P ′,T′;F′,i′,o′)，其中T且表示組成 FSL中變遷的個(gè)數(shù)，i′=o′。T′中的變遷組成的序列 TS∈T′*，對(duì)于 TS ，有其中TS[1]為 FSL的初始變遷為FSL的終止變遷tend。

對(duì)于圖2（c）中WFN5所表示的長(zhǎng)度為3的自由單循環(huán)結(jié)構(gòu)，其tstart為B，tend為D，自由單循環(huán)序列TS為

在不考慮表示偏好的情況下，日志的一條跡中如果多次出現(xiàn)同樣活動(dòng)，即說明存在循環(huán)結(jié)構(gòu)。對(duì)于α算法，存在活動(dòng)a和b，根據(jù)跟隨關(guān)系＞W(wǎng)定義，如果有a＞W(wǎng)b以及b＞W(wǎng)a，便不能判斷活動(dòng)a與活動(dòng)b是存在于長(zhǎng)度為2的循環(huán)結(jié)構(gòu)的兩個(gè)活動(dòng)，還是存在于并發(fā)結(jié)構(gòu)中的兩個(gè)活動(dòng)。在α算法的衍生算法α+算法中，通過重新定義并發(fā)關(guān)系和因果關(guān)系來對(duì)長(zhǎng)度為2的循環(huán)進(jìn)行處理。其定義的并發(fā)關(guān)系中不存在一條跡中有的情況，對(duì)于這種情況，當(dāng)作因果關(guān)系a→Wb處理。

對(duì)于一個(gè)自由單循環(huán)結(jié)構(gòu)，tstart表示結(jié)構(gòu)中的第一個(gè)變遷，即該結(jié)構(gòu)在日志中的起始活動(dòng)對(duì)應(yīng)的變遷；tend表示結(jié)構(gòu)中的最后一個(gè)變遷，即該結(jié)構(gòu)在日志中的終止活動(dòng)對(duì)應(yīng)的變遷；TS表示該結(jié)構(gòu)中所有的變遷對(duì)應(yīng)的日志中的活動(dòng)按順序組成的序列，即自由單循環(huán)序列。該序列的順序?yàn)樵撗h(huán)結(jié)構(gòu)在日志的跡中出現(xiàn)第一遍時(shí)各活動(dòng)的順序。

對(duì)于并發(fā)結(jié)構(gòu)中嵌套循環(huán)結(jié)構(gòu)的情況，如果日志是非完備的，即日志的任何一條跡中的重復(fù)活動(dòng)沒有連續(xù)出現(xiàn)，而是穿插了與其并發(fā)的其他活動(dòng)，例如σ=這類情況，α算法及其衍生算法不能正確挖掘。這些算法將嵌套在并發(fā)結(jié)構(gòu)中的循環(huán)結(jié)構(gòu)識(shí)別為普通順序結(jié)構(gòu)或者錯(cuò)誤結(jié)構(gòu)，不能表現(xiàn)存在重復(fù)活動(dòng)的情況。對(duì)于包含循環(huán)結(jié)構(gòu)的模型對(duì)應(yīng)的日志，存在某一條跡中有活動(dòng)出現(xiàn)次數(shù)不小于兩次，即循環(huán)結(jié)構(gòu)中的活動(dòng)在一條跡中出現(xiàn)至少兩次，但不需要一定連續(xù)出現(xiàn)。因此，對(duì)于包含自由單循環(huán)結(jié)構(gòu)的日志定義如下。

定義10（自由單循環(huán)完備日志）設(shè)WFN=(P,T;F,i,o)為一個(gè)工作流網(wǎng)，，日志W(wǎng)fsl為WFN的自由單循環(huán)完備日志當(dāng)且僅當(dāng)：（1）對(duì)于?ti,tj∈T ，有且不存在，其中＞W(wǎng)fsl表示自由單循環(huán)完備日志中的跟隨關(guān)系，＞N表示模型中的跟隨關(guān)系；（2）對(duì)于自由單循環(huán)完備日志W(wǎng)fsl中的任意一條跡σ，當(dāng)時(shí)，不存在一條長(zhǎng)度為k(k＞0)的子序列，使得

自由單循環(huán)完備日志是一種針對(duì)并發(fā)結(jié)構(gòu)中嵌套循環(huán)結(jié)構(gòu)情況存在的非完備日志，日志中的跟隨關(guān)系在模型中都存在，但日志中任何一條跡中不包含連續(xù)多次出現(xiàn)的活動(dòng)或者活動(dòng)集，例如或 σ=等情況。

對(duì)于圖1（a）中的WFN1，其自由單循環(huán)完備日志可以是Wfsl1={ACD,ABCD,ACBD,ABCBD}。對(duì)于該日志中的每一條跡，都不存在連續(xù)重復(fù)的活動(dòng)，但存在重復(fù)活動(dòng)B。

4 自由單循環(huán)結(jié)構(gòu)挖掘算法

對(duì)于如何發(fā)現(xiàn)自由單循環(huán)結(jié)構(gòu)，本文主要提出三個(gè)階段的工作。

（1）尋找日志中存在的重復(fù)活動(dòng)。

（2）通過日志中重復(fù)活動(dòng)與前后活動(dòng)之間的關(guān)系區(qū)分不同自由單循環(huán)結(jié)構(gòu)中的活動(dòng)。

（3）挖掘每個(gè)自由單循環(huán)結(jié)構(gòu)，得到其自由單循環(huán)序列TS，根據(jù)TS得到結(jié)構(gòu)內(nèi)部活動(dòng)之間的關(guān)系。

4.1 尋找重復(fù)活動(dòng)

在不考慮表示偏好的前提下，針對(duì)并發(fā)結(jié)構(gòu)中嵌套的自由單循環(huán)結(jié)構(gòu)挖掘，根據(jù)自由單循環(huán)完備日志的定義，在日志的一條跡中所有出現(xiàn)次數(shù)大于1的活動(dòng)，都屬于自由單循環(huán)結(jié)構(gòu)中的活動(dòng)。對(duì)于這些活動(dòng)，給出重復(fù)活動(dòng)的定義。

定義11（重復(fù)活動(dòng)）設(shè)A為活動(dòng)集合，為自由單循環(huán)完備日志，若?a∈A，σ∈Wfsl，有a∈σ，且，稱a是一個(gè)重復(fù)活動(dòng)。

對(duì)于所有的重復(fù)活動(dòng)，這些活動(dòng)是在日志的某一條跡中重復(fù)出現(xiàn)，即自由單循環(huán)結(jié)構(gòu)中的活動(dòng)，但并沒有劃分到具體的自由單循環(huán)結(jié)構(gòu)中。例如圖1（b）中的WFN2，對(duì)于它的一個(gè)自由單循環(huán)完備日志：

根據(jù)定義得到的重復(fù)活動(dòng)為{ }B,C,D,E,F,G ，包含了所有在日志的某一條跡中重復(fù)出現(xiàn)的活動(dòng)。

4.2 發(fā)現(xiàn)重復(fù)活動(dòng)的前驅(qū)活動(dòng)和后繼活動(dòng)

定義12（跡前驅(qū)活動(dòng)和跡后繼活動(dòng)）設(shè)A為活動(dòng)集合，Wfsl∈Β(A*)為一個(gè)自由單循環(huán)完備日志。對(duì)于任意重復(fù)活動(dòng)a，存在跡，使得a∈σ，有 ai=a(1 ＜i＜n )，稱ai-1為a的跡前驅(qū)活動(dòng)，ai+1為a的跡后繼活動(dòng)。

對(duì)于任意重復(fù)活動(dòng)，日志的每一條跡中所有該活動(dòng)的跡前驅(qū)活動(dòng)組成其跡活動(dòng)前集TracePreSet，所有該活動(dòng)的跡后繼活動(dòng)組成其跡活動(dòng)后集TracePostSet。例如圖1（b）中的WFN2及其日志W(wǎng)fsl2，可以得到活動(dòng)

通過給出跡前驅(qū)活動(dòng)和跡后繼活動(dòng)的定義，對(duì)已發(fā)現(xiàn)的重復(fù)活動(dòng)存在于具體的自由單循環(huán)結(jié)構(gòu)進(jìn)行區(qū)分。

B的TracePreSet為{A,C,D,E,F,G},TracePostSet為{C,D,E,F,G,H}?；顒?dòng)C的TracePreSet為{A,B,D,E,F,G}，TracePostSet為{B,D,E,F,G}。活動(dòng)D的TracePreSet為 {B,C,E,F,G}，TracePostSet為 {B,C,E,F,G,H}?；顒?dòng)E的TracePreSet為{A,B,C,D,G},TracePostSet為{B,C,D,F}?；顒?dòng)F的TracePreSet為{B,C,D,E}，TracePostSet為{B,C,D,G}?；顒?dòng)G的TracePreSet為 {B,C,D,F}，TracePostSet為 {B,C,D,E,H}。

4.3 獲取自由單循環(huán)序列

對(duì)于不同長(zhǎng)度的自由單循環(huán)結(jié)構(gòu)中的活動(dòng)，其跡活動(dòng)前集和跡活動(dòng)后集存在一定關(guān)聯(lián)。關(guān)聯(lián)的具體情形主要有兩種：一種是長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)中內(nèi)部的活動(dòng)自身的跡活動(dòng)前集和跡活動(dòng)后集之間存在關(guān)聯(lián)；另一種是多個(gè)長(zhǎng)度不為2的自由單循環(huán)結(jié)構(gòu)之間的活動(dòng)的跡活動(dòng)前集和跡活動(dòng)后集存在關(guān)聯(lián)。首先是發(fā)現(xiàn)并區(qū)分出長(zhǎng)度為2的自由單循環(huán)中的活動(dòng)，由以下定理判斷。

定理1設(shè)WFN=( )P,T;F,i,o為一個(gè)工作流網(wǎng)，Wfsl為WFN的自由單循環(huán)完備日志，F(xiàn)SL標(biāo)識(shí)WFN的自由單循環(huán)結(jié)構(gòu)。對(duì)任意重復(fù)活動(dòng)a：

證明假設(shè) a為 FSL中的活動(dòng)，對(duì)于 ?b∈a.TracePreSet,有b＞W(wǎng)a或；對(duì)于?c∈TracePostSet,有a＞W(wǎng)c或a→Wc。

且對(duì)于?c∈TracePostSet有a→Wc,所以a為FSL.tstart且

（2）與（1）的證明類似。

由定理1可知，當(dāng)一個(gè)活動(dòng)的跡活動(dòng)后集是前集的真子集，說明該活動(dòng)是一個(gè)長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)中的tstart對(duì)應(yīng)的日志中的起始活動(dòng)，將此類活動(dòng)加入到長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)的tstart組成的集合L2TstartSet；當(dāng)該活動(dòng)的跡活動(dòng)前集是后集的真子集，說明該活動(dòng)是一個(gè)長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)中的tend對(duì)應(yīng)的日志中的終止活動(dòng)，將此類活動(dòng)加入到長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)的tend組成的集合L2Tend Set；當(dāng)一個(gè)活動(dòng)的跡活動(dòng)前后集合不互為真子集，說明該活動(dòng)存在于長(zhǎng)度不為2的自由單循環(huán)結(jié)構(gòu)中，將這些活動(dòng)加入長(zhǎng)度不為2的重復(fù)活動(dòng)集合NoL2ASet。

對(duì)于L2TstartSet中每一個(gè)起始活動(dòng)，遍歷日志中的每一條跡，在集合L2Tend Set中必定存在一個(gè)終止活動(dòng)在每一條跡中都與該起始活動(dòng)出現(xiàn)次數(shù)相同。該起始活動(dòng)與該終止活動(dòng)存在于同一個(gè)長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)，因此得到該結(jié)構(gòu)有序的自由單循環(huán)序列TS。對(duì)于區(qū)分其他長(zhǎng)度不為2的自由單循環(huán)結(jié)構(gòu)中的活動(dòng)，即NoL2ASet中的活動(dòng)，通過以下定理判斷。

定理2設(shè)WFN=( )P,T;F,i,o為一個(gè)工作流網(wǎng)，A為活動(dòng)集合，Wfsl∈Β( )A*為WFN的自由單循環(huán)完備日志，NoL2ASet是Wfsl的長(zhǎng)度不為2的重復(fù)活動(dòng)集合，F(xiàn)SL標(biāo)識(shí)WFN的自由單循環(huán)結(jié)構(gòu)。對(duì)?a,b∈NoL2ASet,且,若,則a、b屬于同一個(gè)FSL。

證明用反證法。假設(shè)活動(dòng)a、b不屬于同一個(gè)FSL,即，可知 ?p∈A ，有因?yàn)?，所?/p>

根據(jù)定理2，對(duì)于集合NoL2ASet中的活動(dòng)，如果存在兩個(gè)活動(dòng)處于同一自由單循環(huán)結(jié)構(gòu)中，這兩個(gè)活動(dòng)的跡活動(dòng)前集交集與后集交集應(yīng)該相同，即包含其他所有與該自由單循環(huán)結(jié)構(gòu)并發(fā)的活動(dòng)。對(duì)于每個(gè)長(zhǎng)度為1的自由單循環(huán)結(jié)構(gòu)，其自由短循環(huán)序列TS為單個(gè)活動(dòng)；對(duì)于每個(gè)長(zhǎng)度大于2的自由單循環(huán)結(jié)構(gòu)，通過遍歷日志，當(dāng)存在一條跡出現(xiàn)該結(jié)構(gòu)中的活動(dòng)時(shí)，按照活動(dòng)第一遍出現(xiàn)的順序排序，得到該結(jié)構(gòu)的自由單循環(huán)序列TS。

根據(jù)上述兩種情況，下面給出獲取所有自由單循環(huán)序列的算法。

算法1自由單循環(huán)序列獲取算法

輸入：自由單循環(huán)完備日志W(wǎng)fsl、重復(fù)活動(dòng)集合RASet、每個(gè)重復(fù)活動(dòng)的跡活動(dòng)的前集TracePreSet和后集TracePostSet。

輸出：自由單循環(huán)序列集合FSLSet。

照跡中出現(xiàn)的順序排序

算法1所有重復(fù)活動(dòng)根據(jù)不同情況劃分到各自的自由單循環(huán)結(jié)構(gòu)中，得到其自由單循環(huán)序列TS。第2行到第8行根據(jù)定理1區(qū)分不同長(zhǎng)度的自由單循環(huán)結(jié)構(gòu)中的活動(dòng)，并加入相應(yīng)的集合中。第9行到第15行，對(duì)于長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)中的tstart和tend進(jìn)行匹配。遍歷日志中的每一條跡，對(duì)每一個(gè)起始活動(dòng)tstart，找到與之對(duì)應(yīng)的終止活動(dòng)tend，得到自由單循環(huán)序列TS。第16行到第22行根據(jù)定理2對(duì)長(zhǎng)度不為2的自由單循環(huán)結(jié)構(gòu)中的活動(dòng)進(jìn)行匹配，得到無序集合S。對(duì)于每一個(gè)S中的活動(dòng)，日志中存在一條跡含有這些活動(dòng)。按照這條跡中這些活動(dòng)首次出現(xiàn)的順序?qū)中的活動(dòng)按序添加到有序的自由單循環(huán)序列TS中。所有的自由單循環(huán)序列TS組成自由單循環(huán)序列集合FSLSet。

對(duì)于圖1（b）中的WFN2及其日志W(wǎng)fsl2，首先挖掘其中長(zhǎng)度為2自由單循環(huán)結(jié)構(gòu)。對(duì)于活動(dòng)C，根據(jù)算法2，C.TracePostSet?C.TracePreSet，因此C 為某一個(gè)長(zhǎng)度為2的循環(huán)結(jié)構(gòu)中tstart對(duì)應(yīng)的起始活動(dòng)，加入 集合 L2TstartSet。對(duì)于活動(dòng) D,D.TracePreSet?D.TracePostSet,因此D屬于某一個(gè)長(zhǎng)度為2的循環(huán)結(jié)構(gòu)的tend對(duì)應(yīng)的終止活動(dòng)，加入集合L2Tend Set。遍歷日志中的每一條，發(fā)現(xiàn)活動(dòng)C和活動(dòng)D在每條跡中出現(xiàn)的次數(shù)相同，可知活動(dòng)C與活動(dòng)D屬于同一個(gè)長(zhǎng)度為2的自由單循環(huán)結(jié)構(gòu)，將加入所有自由單循環(huán)序列集合FSLSet。對(duì)于其他的重復(fù)活動(dòng)B、E、F、G，加入長(zhǎng)度不為2的重復(fù)活動(dòng)集合NoL2ASet。根據(jù)算法1，通過判斷每?jī)蓚€(gè)活動(dòng)的跡活動(dòng)前集交集和后集交集，可以發(fā)現(xiàn)活動(dòng)B與其他活動(dòng)的前集交集和后集交集都不相同，可知活動(dòng)B屬于一個(gè)長(zhǎng)度為1的自由單循環(huán)結(jié)構(gòu)，將加入所有自由單循環(huán)序列集合FSLSet。其他三個(gè)活動(dòng)E、F、G兩兩之間的跡活動(dòng)前集交集和后集交集都是{B ,C,D} ，可知活動(dòng)E、F、G屬于同一個(gè)自由單循環(huán)結(jié)構(gòu)，得到包含活動(dòng)E、F、G的無序集合S。根據(jù)日志中的任意一條包含活動(dòng)E、F以及G的跡，例如，可以得到包含這些活動(dòng)的自由單循環(huán)結(jié)構(gòu)的，并將其加入自由單循環(huán)序列集合FSLSet。至此，日志W(wǎng)fsl2中所有自由單循環(huán)結(jié)構(gòu)已經(jīng)全部發(fā)現(xiàn)，自由單循環(huán)序列集合FSLSet為

4.4 日志活動(dòng)的次序關(guān)系

定義13（自由單循環(huán)關(guān)系）令Wfsl是一個(gè)自由單循環(huán)完備日志，i.e.,Wfsl∈Β(T*)。令a,b∈T：

根據(jù)圖1（b）中的WFN2及其日志W(wǎng)fsl2，以及其自由單循環(huán)序列集合FSLSet，對(duì)于每個(gè)自由單循環(huán)結(jié)構(gòu)中的活動(dòng)，前后相繼的活動(dòng)之間的關(guān)系變?yōu)椋春?/p>

根據(jù)自由單循環(huán)關(guān)系，能夠正確發(fā)現(xiàn)自由單循環(huán)結(jié)構(gòu)中各活動(dòng)之間的關(guān)系，而α算法及其衍生算法對(duì)自由單循環(huán)結(jié)構(gòu)內(nèi)部活動(dòng)關(guān)系不能正確發(fā)現(xiàn)，會(huì)錯(cuò)誤地識(shí)別為并發(fā)關(guān)系或者跟隨關(guān)系。

對(duì)于自由單循環(huán)序列集合FSLSet中每一個(gè)自由單循環(huán)結(jié)構(gòu)，其中活動(dòng)之間的基本次序關(guān)系重新定義為自由單循環(huán)關(guān)系。

4.5 αfsl算法

根據(jù)日志預(yù)處理工作得到的不同自由單循環(huán)結(jié)構(gòu)對(duì)應(yīng)的自由單循環(huán)序列，發(fā)現(xiàn)各個(gè)結(jié)構(gòu)內(nèi)部活動(dòng)之間的自由單循環(huán)關(guān)系，為αfsl算法的模型挖掘工作提供支持。

αfsl算法是針對(duì)并發(fā)結(jié)構(gòu)中嵌套的自由單循環(huán)結(jié)構(gòu)進(jìn)行挖掘，基于α算法實(shí)現(xiàn)。在預(yù)處理階段，通過對(duì)日志的處理，發(fā)現(xiàn)其中存在的重復(fù)活動(dòng)，進(jìn)而獲得所有自由單循環(huán)序列。通過對(duì)自由單循環(huán)結(jié)構(gòu)內(nèi)部活動(dòng)之間次序的重新定義，正確發(fā)現(xiàn)自由單循環(huán)結(jié)構(gòu)中各活動(dòng)之間的關(guān)系，進(jìn)而挖掘出合理的模型。下面給出αfsl算法的定義。

定義14（αfsl算法）令W代表覆蓋T的自由單循環(huán)完備工作流日志。αfsl( )W 定義如下：

αfsl算法針對(duì)并發(fā)結(jié)構(gòu)中嵌套的自由單循環(huán)結(jié)構(gòu)進(jìn)行挖掘。在該算法中，擴(kuò)展了α算法定義的日志中不同活動(dòng)之間的關(guān)系，加入了第四步過程。在第四步中，根據(jù)算法1獲得所有FSL的TS，發(fā)現(xiàn)FSL內(nèi)部活動(dòng)之間的自由單循環(huán)關(guān)系并加入到α算法中。具體實(shí)現(xiàn)時(shí)，利用α算法挖掘不包含F(xiàn)SL的部分模型，并在α算法挖掘到部分模型的基礎(chǔ)上通過后處理的方式插入所有FSL，最終得到正確模型。

5 仿真實(shí)驗(yàn)

本文通過實(shí)驗(yàn)驗(yàn)證算法的可行性以及分析結(jié)果。αfsl算法已經(jīng)作為插件（https：//pan.baidu.com/s/1pK7zSuR）在開源過程挖掘框架ProM中實(shí)現(xiàn)，它以XES格式的日志作為輸入，以工作流網(wǎng)表示的過程模型為輸出。實(shí)驗(yàn)使用Java語(yǔ)言編寫插件，硬件環(huán)境為Windows7 SP1操作系統(tǒng)、Intel?CoreTM2.50 GHz處理器以及10.0 GB內(nèi)存。

以某電腦維修公司網(wǎng)上維修的業(yè)務(wù)流程為例，客戶的電腦出現(xiàn)故障，從申請(qǐng)維修業(yè)務(wù)到維修成功包含一系列活動(dòng)。首先客戶需要申請(qǐng)維修（Application），然后在網(wǎng)上進(jìn)行維修登記（Register）。登記成功后，客戶要將自己的設(shè)備通過郵寄的形式發(fā)送到電腦維修公司（Delivery）。電腦維修公司收到客戶的設(shè)備后要進(jìn)行故障檢測(cè)（Malfunction Detection），設(shè)備故障一般包含硬件故障（Hardware Malfunction）和軟件故障（Software Malfunction）。兩種故障可以都存在，也可以只存在其一，甚至存在無故障的情況，即客戶使用環(huán)境的問題而非設(shè)備本身的問題。對(duì)于檢測(cè)到的設(shè)備硬件故障，維修人員要進(jìn)行硬件維修（Hardware Fix），同樣的對(duì)于軟件故障也要進(jìn)行軟件維修（Software Fix），檢測(cè)出故障并維修的過程可能多次發(fā)生，也可能不發(fā)生。所有故障維修200條跡的日志L3，如表1所示。在這些日志中，不包含任意重復(fù)活動(dòng)連續(xù)出現(xiàn)的情況，即或這類情況。完畢，有關(guān)人員對(duì)維修費(fèi)用進(jìn)行統(tǒng)計(jì)（Expense Statistics），并將客戶的設(shè)備打包發(fā)回給客戶（Return）?？蛻粼谑盏椒祷氐脑O(shè)備后，要進(jìn)行驗(yàn)收（Check），驗(yàn)收完成后需繳納維修費(fèi)用（Pay）。最后電腦維修公司要對(duì)客戶進(jìn)行定期回訪，短期內(nèi)跟蹤客戶的設(shè)備使用情況（Follow Up）。

針對(duì)該業(yè)務(wù)流程實(shí)例，依據(jù)自由單循環(huán)完備日志定義，模擬了三組符合自由單循環(huán)完備的日志，分別為包含50條跡的日志L1、包含100條跡的日志L2以及包含

表1 三組自由單循環(huán)完備日志

根據(jù)αfsl算法對(duì)表1中的日志進(jìn)行挖掘得到模型，見圖3。由于α算法不支持對(duì)短循環(huán)結(jié)構(gòu)的挖掘，因此作為對(duì)比，分別選取了能夠挖掘短循環(huán)的α+算法[3]、ILP算法[13]以及IM算法[14]對(duì)相同日志進(jìn)行挖掘，挖掘模型的結(jié)果見圖4、圖5和圖6。

圖3 αfsl算法挖掘的模型

圖5 ILP算法挖掘的模型

圖6 IM算法挖掘的模型

依據(jù)電腦維修公司的業(yè)務(wù)流程，可以發(fā)現(xiàn)硬件檢測(cè)出故障與硬件維修同時(shí)存在，同樣軟件檢測(cè)出故障與硬件維修也同時(shí)存在。由于一臺(tái)設(shè)備由多個(gè)硬件組成，硬件出現(xiàn)故障的情況有很多，要逐一檢測(cè)和維修。因此，硬件檢測(cè)出故障以及硬件維修這兩個(gè)活動(dòng)可能多次出現(xiàn)，同樣軟件檢測(cè)出故障以及軟件維修也會(huì)多次出現(xiàn)。對(duì)于一臺(tái)設(shè)備，甚至?xí)霈F(xiàn)沒有故障即客戶判斷失誤的情況，這種情況不會(huì)出現(xiàn)軟硬件故障以及軟硬件維修活動(dòng)。

對(duì)于這幾種情況，αfsl算法能挖掘出符合這些情況的工作流模型。根據(jù)圖3可以看出，硬件檢測(cè)出故障（Hardware Malfunction）與硬件維修（Hardware Fix）存在于同一個(gè)自由單循環(huán)結(jié)構(gòu)中，說明每次發(fā)現(xiàn)一種硬件的故障，要對(duì)其進(jìn)行維修。對(duì)于軟件出現(xiàn)故障（Software Malfunction）以及軟件維修（Software Fix）同樣適用。硬件故障以及硬件維修組成的自由單循環(huán)結(jié)構(gòu)與軟件故障以及軟件維修組成的自由單循環(huán)結(jié)構(gòu)處于并發(fā)結(jié)構(gòu)中，說明了軟硬件的檢測(cè)和維修能夠同時(shí)發(fā)生，也可以只發(fā)生其中一種，甚至可以都不發(fā)生。

對(duì)于α+算法、ILP算法和IM算法，這三種算法不能正確地挖掘出該業(yè)務(wù)流程對(duì)應(yīng)的模型。根據(jù)圖4和圖5可以看出，α+算法以及ILP算法挖掘到的模型本身存在錯(cuò)誤，硬件檢測(cè)出故障（Hardware Malfunction）和軟件出現(xiàn)故障（Software Malfunction）這兩個(gè)變遷沒有后繼庫(kù)所，硬件維修（Hardware Fix）和軟件維修（Software Fix）這兩個(gè)變遷沒有前驅(qū)庫(kù)所，也沒有表現(xiàn)出自由單循環(huán)結(jié)構(gòu)。根據(jù)圖6可以看出，對(duì)于IM算法挖掘到的模型，硬件故障和硬件維修沒有滿足必然同時(shí)出現(xiàn)的情況，軟件故障和軟件維修也沒有滿足該情況，并且沒有表現(xiàn)出自由單循環(huán)結(jié)構(gòu)。圖7和圖8分別從各算法在不同日志下挖掘模型的擬合度和精確度的表現(xiàn)給出了實(shí)驗(yàn)結(jié)果，擬合度檢測(cè)使用ProM插件Replay a Log on Petri Net for Conformance Analysis，精確度檢測(cè)使用ProM插件Check Precision based on Align-ETConformance。

圖7展示了對(duì)于不同日志各算法挖掘模型的擬合度比較。從圖中可以發(fā)現(xiàn)，對(duì)于每個(gè)日志，αfsl算法和IM算法挖掘的模型擬合度相同而且很高，而α+算法和ILP算法得到的模型的擬合度較低。

圖7 擬合度比較

圖8 展示了對(duì)于不同日志各算法挖掘模型的精確度比較。從圖中可以發(fā)現(xiàn)，雖然αfsl算法挖掘的模型隨著日志中跡條數(shù)的增多精確度略有降低，但仍舊處于較高水平。相比之下，IM算法挖掘的模型精確度較低，而α+算法和ILP算法得到的模型的精確度效果不佳。

圖8 精確度比較

6 結(jié)束語(yǔ)

為了挖掘存在于并發(fā)結(jié)構(gòu)中的特殊循環(huán)結(jié)構(gòu)（自由單循環(huán)結(jié)構(gòu)），本文重新定義了存在自由單循環(huán)結(jié)構(gòu)的日志完備性，并且基于α算法提出了αfsl算法，針對(duì)這種結(jié)構(gòu)進(jìn)行挖掘。通過實(shí)驗(yàn)例證了αfsl算法挖掘的模型具有較高的擬合度和精確度。本文算法僅針對(duì)文中定義的自由單循環(huán)結(jié)構(gòu)嵌套在并發(fā)結(jié)構(gòu)中的情況進(jìn)行挖掘，對(duì)于其他類型的結(jié)構(gòu)，甚至更加復(fù)雜的情況，將來會(huì)有更進(jìn)一步的討論和研究。