賀朝陽，杜玉越，王 路

山東科技大學 計算機科學與工程學院，山東 青島 266590

1 引言

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

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

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

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

2 基本概念

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

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

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

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

定義3（跡）設A是活動集合，一條跡σ∈A*是一個活動的隊列。

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

Petri網是由庫所（place）和變遷（transition）組成的有向二分圖。

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

在本文中，模型中的變遷和日志中的活動一一對應，在一些情況下不進行區(qū)分。工作流網是一個有著唯一初始庫所和終止庫所的Petri網。

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

（1）PN=( )P,T;F 為一個Petri網；

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

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

跟隨關系a＞Wb：當且僅當存在一條跡使得 σ∈W,ti=a并且ti+1=b；

因果關系a→Wb：當且僅當a＞Wb并且b≯Wa；

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

3 自由單循環(huán)結構

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

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

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

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

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

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

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

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

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

圖2 三種長度的自由單循環(huán)結構

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

對于圖2（c）中WFN5所表示的長度為3的自由單循環(huán)結構，其tstart為B，tend為D，自由單循環(huán)序列TS為

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

對于一個自由單循環(huán)結構，tstart表示結構中的第一個變遷，即該結構在日志中的起始活動對應的變遷；tend表示結構中的最后一個變遷，即該結構在日志中的終止活動對應的變遷；TS表示該結構中所有的變遷對應的日志中的活動按順序組成的序列，即自由單循環(huán)序列。該序列的順序為該循環(huán)結構在日志的跡中出現(xiàn)第一遍時各活動的順序。

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

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

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

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

4 自由單循環(huán)結構挖掘算法

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

（1）尋找日志中存在的重復活動。

（2）通過日志中重復活動與前后活動之間的關系區(qū)分不同自由單循環(huán)結構中的活動。

（3）挖掘每個自由單循環(huán)結構，得到其自由單循環(huán)序列TS，根據(jù)TS得到結構內部活動之間的關系。

4.1 尋找重復活動

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

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

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

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

4.2 發(fā)現(xiàn)重復活動的前驅活動和后繼活動

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

對于任意重復活動，日志的每一條跡中所有該活動的跡前驅活動組成其跡活動前集TracePreSet，所有該活動的跡后繼活動組成其跡活動后集TracePostSet。例如圖1（b）中的WFN2及其日志Wfsl2，可以得到活動

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

B的TracePreSet為{A,C,D,E,F,G},TracePostSet為{C,D,E,F,G,H}?；顒覥的TracePreSet為{A,B,D,E,F,G}，TracePostSet為{B,D,E,F,G}?；顒覦的TracePreSet為 {B,C,E,F,G}，TracePostSet為 {B,C,E,F,G,H}?；顒覧的TracePreSet為{A,B,C,D,G},TracePostSet為{B,C,D,F}?；顒覨的TracePreSet為{B,C,D,E}，TracePostSet為{B,C,D,G}?；顒覩的TracePreSet為 {B,C,D,F}，TracePostSet為 {B,C,D,E,H}。

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

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

定理1設WFN=( )P,T;F,i,o為一個工作流網，Wfsl為WFN的自由單循環(huán)完備日志，F(xiàn)SL標識WFN的自由單循環(huán)結構。對任意重復活動a：

證明假設 a為 FSL中的活動，對于 ?b∈a.TracePreSet,有b＞Wa或；對于?c∈TracePostSet,有a＞Wc或a→Wc。

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

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

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

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

定理2設WFN=( )P,T;F,i,o為一個工作流網，A為活動集合，Wfsl∈Β( )A*為WFN的自由單循環(huán)完備日志，NoL2ASet是Wfsl的長度不為2的重復活動集合，F(xiàn)SL標識WFN的自由單循環(huán)結構。對?a,b∈NoL2ASet,且,若,則a、b屬于同一個FSL。

證明用反證法。假設活動a、b不屬于同一個FSL,即，可知 ?p∈A ，有因為，所以

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

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

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

輸入：自由單循環(huán)完備日志Wfsl、重復活動集合RASet、每個重復活動的跡活動的前集TracePreSet和后集TracePostSet。

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

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

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

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

4.4 日志活動的次序關系

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

根據(jù)圖1（b）中的WFN2及其日志Wfsl2，以及其自由單循環(huán)序列集合FSLSet，對于每個自由單循環(huán)結構中的活動，前后相繼的活動之間的關系變?yōu)?，即?/p>

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

對于自由單循環(huán)序列集合FSLSet中每一個自由單循環(huán)結構，其中活動之間的基本次序關系重新定義為自由單循環(huán)關系。

4.5 αfsl算法

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

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

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

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

5 仿真實驗

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

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

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

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

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

圖3 αfsl算法挖掘的模型

圖5 ILP算法挖掘的模型

圖6 IM算法挖掘的模型

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

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

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

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

圖7 擬合度比較

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

圖8 精確度比較

6 結束語

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