０ 引 言
面對激烈的市場競爭和市場環(huán)境的快速變化，現代企業(yè)必須能夠隨時對核心業(yè)務過程做出適當的調整以適應新的需要。這不但需要管理者能夠掌握外部環(huán)境的變化，也需要管理者能夠對企業(yè)業(yè)務過程的實際情況有清晰的了解。傳統(tǒng)的過程分析手段，如調查、訪談、建模分析和模擬等，費時費力，而且受用戶的主觀性影響很大，容易出現偏差，因此越來越難以滿足用戶的需要。
過程挖掘是一種自動化的過程分析技術，通過對業(yè)務過程日志的挖掘，自動生成業(yè)務過程的執(zhí)行流模型，從而幫助用戶更好地理解業(yè)務過程的內在執(zhí)行邏輯［１］。由于其分析的依據――業(yè)務過程日志是企業(yè)在實際業(yè)務運行過程中生成的客觀記錄，因此該技術客觀性強、費用低、速度快，有效地彌補了傳統(tǒng)過程分析手段的各種缺陷，并已經在政府公共工程、醫(yī)院和供應鏈管理等實際領域中取得了一定的成功應用［２－４］。
對包含錯誤、隱含任務［５］等的不完整日志的挖掘是過程挖掘面臨的難題之一。因為實際中用于挖掘的日志主要來源于企業(yè)的信息系統(tǒng)的自動生成，因此日志中包含錯誤的情況并不常見，不完整日志問題基本上都是由于包含隱含任務造成的?，F有的大多數過程挖掘算法在處理包含隱含任務的日志時都無法得到正確的結果。少數幾種能夠處理隱含任務的算法，如基因算法［６］、α＃算法［７］等，但只能挖掘部分類型的隱含任務，未能完全解決隱含任務的挖掘問題。
針對這一問題，本文嘗試提出一種基于α算法［８］和結構化工作流網［９］的過程挖掘算法，該算法能夠比較全面地挖掘結構化工作流網模型中的各類隱含任務。通過理論分析和實驗驗證，該算法的正確性得到了證明。
?。?問題說明
過程挖掘通過對日志信息的分析來構造過程模型。為了保證挖掘算法能夠最大限度地適用于各種形式的日志，絕大多數挖掘算法僅要求日志中包含下列3項內容：①事件所屬的工作實例；②執(zhí)行事件的業(yè)務單元（任務標識）；③事件發(fā)生的順序（處理時間）。因此，在分析過程挖掘算法時，為了簡便起見，通常直接將日志寫成諸如ＡＢＣＤＥ，ＡＢＣＤＦ，ＡＣＢＤＥ，ＡＣＢＤＦ的形式，其中每個字母代表一個任務，每個逗號隔開的字母序列代表一條日志實例。對該日志實例用算法進行過程挖掘，就可以得到如圖１（ａ）所示的結構化工作流網過程模型。
在現實中，由于很多信息系統(tǒng)只對進行實際業(yè)務操作的業(yè)務單元活動進行記錄，以及系統(tǒng)采用的過程建模工具本身的特性等各種原因，一些過程任務往往沒有被記錄在日志中。這種過程任務就是所謂的“隱含任務”?，F有的大多數算法無法正確處理包含隱含任務的日志。例如，假設圖１（ａ）中過程的任務Ｄ是一個隱含任務，則得到的日志是ＡＢＣＥ，ＡＢＣＦ，ＡＣＢＥ，ＡＣＢＦ。用α算法挖掘將得到如圖１（ｂ）所示的模型，它不是一個合法的結構化工作流網模型，而且相比原始模型，其結構復雜，不容易為用戶所理解。
現有少數算法能夠挖掘部分類型的隱含任務，但都無法完全挖掘所有類型的隱含任務。例如，圖２給出了α ＃算法能夠挖掘的幾種隱含任務，其中黑色方塊表示隱含任務。但它無法挖掘圖１（ａ）類型的隱含任務。
因此，本文在綜合現有各種隱含任務挖掘方法的基礎上，結合結構化工作流網本身的特性，提出了一種基于算法和結構化工作流網的過程挖掘算法，該算法能夠比較全面地挖掘結構化工作流網模型中的各類隱含任務。
?。?結構化工作流網中的隱含任務
２．１ 結構化工作流網
過程挖掘通過深入分析過程日志來構造出過程模型。顯然，算法所使用的建模語言決定了算法能夠成功挖掘的過程及其日志的特性。目前，絕大多數過程挖掘算法都采用工作流網［１０］或者其子集作為建模語言，它是Ｐｅｔｒｉ網的一個子集，具體定義如下：
定義１（工作流網） 工作流網Ｎ為五元組（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。其中，Ｐ為全體庫所集合，T為全體變遷集合，Ｆ為全體邊集合，ｉ為輸入庫所，ｏ為輸出庫所。Ｍｏ ＝｛ｉ｝為工作流網的初始配置。
結構化工作流網是工作流網的各類子集中研究最多最深入的一種，其特點是不包含非自由選擇結構，結構相對簡單，但仍能滿足大多數實際應用的需要。其定義如下：
定義２（結構化工作流網） 工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）是一個結構化工作流網，當且僅當：
（１）對任意滿足（ｐ，ｔ）∈Ｆ的ｐ和ｔ，有：｜ｐ・｜＞１→｜・ｔ｜＝１；
?。?）對任意滿足（ｐ，ｔ）∈Ｆ的p和t，有：｜・t｜＞１→｜p・｜＝１；
?。ǎ常㏄中不存在隱含庫所［９］。
?。玻?隱含任務定義
隱含任務就是在過程中存在并且被執(zhí)行，但是始終不會被記錄在過程日志中的任務。
定義３（隱含任務） 已知結構化工作流網N＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W=T*是其對應的日志。則稱t∈T是隱含任務，當且僅當不存在日志實例L∈W，使t∈L。N的全部隱含任務的集合記為H。
隱含任務問題的本質是日志中的信息缺失。顯然，只有那些導致模型結構出現缺陷的隱含任務才有可能被發(fā)現，其他隱含任務在不引入其他知識的條件下是無法通過日志分析的方法來發(fā)現的。例如，圖４中的幾種隱含任務都不會導致挖掘模型出現結構缺陷，都是無法被發(fā)現的。因此，本文只討論會導致結構化工作流網的結構出現缺陷的那些隱含任務。
?。玻?隱含任務分類
按照在模型中的位置及其特點，可以將結構化工作流網中的隱含任務分成起始／結束點型、隱含路徑型、結構轉換點型和子分支點型四大類。
起始／結束點型對應于α ＃算法中的ＳＩＤＥ類型［７］，是由出現在模型起始位置的與－分支點和出現在模型結束位置的與－匯合點形成的隱含任務，如圖２（ａ）和（ｂ）所示。其定義如下：
定義４（起始／結束點型隱含任務） 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。當隱含任務t∈H滿足下列條件之一時，稱其為起始／結束點型隱含任務：
隱含路徑型對應于α ＃算法中的ＳＫＩＰ和ＲＥＤＯ類型，是單獨組成過程中的某條執(zhí)行路徑分支的隱藏任務，如圖２（ｃ）和（ｄ）所示。其定義如下：
定義５（隱含路徑型隱含任務） 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。稱隱含任務t∈H為隱含路徑型隱含任務，當?堝ａ，ｂ∈Ｔ－Ｈ，a・?勱・t，ｔ・?奐・ｂ。
結構轉換點型是由選擇結構和并行結構之間的轉換點形成的隱含任務。圖５是結構轉換點型隱含任務的幾種情況，其中左邊是原始過程，右邊是用α算法挖掘對應的日志得到的模型。其定義如下：
定義６（結構轉換點型隱含任務） 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。當隱含任務t∈H滿足下列條件之一時，稱其為結構轉換點型隱含任務：
子分支點型是由選擇分支里的并行分支點形成的隱含任務。圖６是結構轉換點的幾種情況，其中左邊是原始過程，右邊是用α算法挖掘對應的日志得到的模型。其定義如下：
定義７（子分支點型隱含任務） 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。稱隱含任務t∈H為子分支點型隱含任務，當其滿足下列條件之一：
３ 隱含任務的發(fā)現
在上一節(jié)中定義了幾種隱含任務，它們的共同特點是會導致結構化工作流網的結構出現缺陷。因此，通過檢測挖掘模型中的結構缺陷，就能夠發(fā)現這些隱含任務的存在，并加以彌補。本文采用α＋［９］算法中次序關系作為檢測模型結構缺陷的工具，其定義如下：
定義８（次序關系） Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）是合理工作流網，W是N的一個日志，即W∈T*，ａ，ｂ∈Ｔ，則有：
－ａ＞Ｗｂ 當且僅當?堝σ＝ｔ１ｔ２…ｔｎ，ｉ∈｛１，…，ｎ－１｝：σ∈W∧ti=a∧ti+1=b；
?。璦ΔWb 當且僅當?堝σ＝t1t2…tn，i∈｛1，…，ｎ－２｝：σ∈W∧ti=ti+2a=a∧ti+1=b；；
?。璦◇Wb 當且僅當aΔWb∨bΔWa；
?。璦→Wb 當且僅當a>Ｗｂ∧（ｂ≯Ｗａ∨ａ◇Ｗｂ）；
?。璦#Wb 當且僅當aW≯b∧b≮Wa；
根據次序關系，就可以針對各類隱含任務的不同特點，分別找出它們的發(fā)現方法。因為α ＃算法中已經給出了起始／結束型和隱含路徑型的隱含任務的檢測方法，因此本文只討論結構轉換點型和子分支點型隱含任務的發(fā)現方法。
?。常?結構轉換點型隱含任務的發(fā)現
結構化工作流網中的結構轉換點型隱含任務可以根據下面的定理發(fā)現：
定理１ 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→W和ΔW關系完備性的日志。則N中存在結構轉換點型隱含任務，當且僅當下列條件之一被滿足：
?。ǎ保?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ＃Ｗ ｂ，ｄ｜｜Ｗ ｃ，ａ→Ｗ ｃ，ａ→Ｗ ｄ，ｂ→Ｗ ｃ，ａ→Ｗ ｄ；
?。ǎ玻?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ＃Ｗ ｂ，ｄ｜｜Ｗ ｃ，ａ→Ｗ ｃ，ａ→Ｗ ｄ，ｂ→Ｗ ｃ，ａ→Ｗ ｄ；
?。ǎ常?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ＃Ｗ ｂ，ｄ｜｜Ｗ ｃ，ａ→Ｗ ｃ，ａ→Ｗ ｄ，ｂ→Ｗ ｃ，ａ→Ｗ ｄ。
根據結構化工作流網的定義和圖５，很容易證明該定理的正確性。詳細證明從略。
?。常?子分支點型隱含任務的發(fā)現
結構化工作流網中的子分支點型隱含任務可以根據下面的定理發(fā)現：
定理２ 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→Ｗ 和ΔＷ 關系完備性的日志。則N中存在子分支點型隱含任務，當且僅當下列條件之一被滿足：
?。ǎ保?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ→Ｗ ｂ，ａ→Ｗ ｃ，ａ→Ｗ ｂ，ｂ＃Ｗ ｄ，ｃ＃Ｗ ｄ，ｂ｜｜Ｗｃ；
（2）?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ→Ｗ ｄ，ｂ→Ｗ ｄ，ｃ→Ｗ ｄ，ａ＃Ｗ ｃ，ｂ＃Ｗ ｃ，ａ｜｜Ｗ b。
根據結構化工作流網的定義和圖６，很容易證明該定理的正確性。詳細證明從略。
?。常?隱含任務的檢測順序
由于過程可能同時存在多種類型的隱含任務，一種隱含任務的存在可能會對另一種隱含的發(fā)現造成影響。因此各隱含任務的檢測必須符合一定的順序。
由于起始／結束點型隱含任務存在于模型的兩端，其他類型隱含任務的發(fā)現可能會依賴于它的正確發(fā)現，因此應該先進行起始／結束點型隱含任務的檢測。
結構轉換點型的隱含任務本身是選擇結構或者并行結構的起始點或者結束點，而子分支點型隱含任務的檢測依賴于選擇結構的起始點或結束點的存在。因此，結構轉換點型隱含任務的檢測必須先于子分支點型隱含任務。
隱含路徑型隱含任務的正確檢測依賴于選擇結構或者并行結構的正確結束，因此應該最后進行。
?。?基于結構化工作流網的挖掘算法
?。矗?子分支點型隱含任務發(fā)現算法
根據前面的討論，子分支點型隱含任務的發(fā)現算法Ｆｉｎｄ Ｓｕｂ Ｂｒａｎｃｈ ＩＴ如下：
定義９（Ｆｉｎｄ Ｓｕｂ Ｂｒａｎｃｈ ＩＴ算法） 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→W和ΔW關系完備性的日志，RW是從W得到的所有次序關系集合。則子分支點型隱含任務的發(fā)現算法是：
（１）ＴＷ＝｛ｔ｜?堝σ∈Ｗ，ｔ∈σ｝
（２）Ｘ１＝｛（｛ａ｝，Ｂ）|a∈ＴＷ∧B?奐TW∧（?坌b∈B∶a→Ｗｂ）∧（?坌ｂ１，ｂ２∈Ｂ∶ｂ１｜｜Ｗ ｂ２）∧（?堝ｃ∈ＴＷ∶ａ→Ｗｃ∧（?坌ｂ∈Ｂ∶ｃ＃Ｗｂ））｝
?。ǎ常?＝｛（Ａ，｛b｝|A?奐TW∧b∈TW∧（?坌a∈A∶ ｃ＃Ｗa）∧（?坌a1，a2∈A∶a1||W a2）∧（?堝ｃ∈ＴＷ∶c→Ｗb∧（?坌a∈A∶ ｃ＃Ｗa））｝
（４）X=X1∪X2
?。ǎ叮㏕Y=｛ty|?堝y∈Y｝
（７）R1=｛a→Wty|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），ａ∈Ａ｝
?。ǎ福㏑2=｛ty→Wb|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），b∈B｝
?。ǎ梗㏑Y=R1∪R2
?。ǎ保埃㏕W=TW∪TY
?。ǎ保保㏑W=RW∪RY
?。矗?結構轉換點型隱含任務發(fā)現算法
根據前面的討論，結構轉換點型隱含任務的發(fā)現算法Ｆｉｎｄ Ｂｒａｎｃｈ Ｃｏｎｎｅｃｔｏｒ ＩＴ如下：
定義９（Ｆｉｎｄ Ｂｒａｎｃｈ Ｃｏｎｎｅｃｔｏｒ ＩＴ算法） 已知結構化工作流網N ＝ （P，T，F，i，0），W是其滿足和關系完備性的日志，RW是從得到的所有次序關系集合。則結構轉換點型隱含任務的發(fā)現算法是：
（１）ＴＷ＝｛ｔ｜?堝σ∈Ｗ，ｔ∈σ｝
?。ǎ玻兀保剑ˋ，Ｂ）|A∈ＴＷ∧B?奐ＴＷ∧（?坌ａ∈Ａ，ｂ∈Ｂ∶ａ→Ｗｂ）∧（?坌ａ１，ａ２∈Ａ∶ａ１｜｜Ｗ ａ２）∧（?坌ｂ１，ｂ2∈Ｂ∶b1||Ｗｂ2）｝
（３）Ｘ2＝｛（Ａ，B）｜A?奐TW∧B∈TW∧（?坌a∈A，b∈B∶a→Wb）∧（?坌a1，a2∈A∶a1||W a2）∧（?坌b1，b2∈B∶b1＃Ｗb2）｝
?。?）Ｘ3＝｛（Ａ，B）｜A?奐TW∧B∈TW∧（?坌a∈A，b∈B∶a→Wb）∧（?坌a1，a2∈A∶a1||W a2）∧（?坌b1，b2∈B∶b1＃Ｗb2）｝
?。?）X=X1∪X2∪X3
（7）TY=｛ty|?堝y∈Y｝
?。?）R1=｛a→Wty|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），ａ∈Ａ｝
?。?）R2=｛ty→Wb|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），b∈B｝
?。?0）RY=R1∪R2
（１1）TW=TW∪TY
?。ǎ?）RW=RW∪RY
?。矗? 基于結構化工作流網的隱含任務挖掘算法
最終得到的基于結構化工作流網的隱含任務發(fā)現算法如下：
定義１０（基于結構化工作流網的隱含任務發(fā)現算法） 已知結構化工作流網Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→Ｗ和ΔW關系完備性的日志。則基于結構化工作流網的隱含任務發(fā)現算法是：
?。ǎ保裕祝剑簦?堝σ∈Ｗ，ｔ∈σ｝
（２）構造RW
?。ǎ常ǎ裕祝遥祝剑茫铮睿樱椋洌澹桑裕ǎ裕?，ＲＷ）
（４）（ＴＷ，ＲＷ）＝ＦｉｎｄＳｕｂＢｒａｎｃｈＩＴ（ＴＷ，ＲＷ）
?。ǎ担ǎ裕?，ＲＷ）＝ＦｉｎｄＢｒａｎｃｈＣｏｎｎｅｃｔｏｒＩＴ（ＴＷ，ＲＷ）
（６）（ＴＷ，ＲＷ）＝ＣｏｎＩＴ（ＴＷ，ＲＷ）
?。ǎ罚㎞＝α（ＴＷ，ＲＷ）
其中，Ｆｉｎｄ Ｓｕｂ Ｂｒａｎｃｈ ＩＴ和Ｆｉｎｄ Ｂｒａｎｃｈ Ｃｏｎｎｅｃｔｏｒ ＩＴ分別是前面定義的子分支點型和結構轉換點型隱含任務發(fā)現算法，ＣｏｎＳｉｄｅＩＴ和ＣｏｎＩＴ分別是α＃算法中定義的起始／結束點型和隱含路徑型隱含任務發(fā)現算法，α（ＴＷ，ＲＷ）是使用α算法構造過程模型。
５ 實驗評估
本文使用Ｊａｖａ語言在ＰｒｏＭ平臺［１１］上實現了提出的基于結構化工作流網的隱含任務發(fā)現算法，并對其進行了實驗驗證。實驗使用了１８個手工構造的過程實例進行。圖７顯示了實驗中所使用的一個實例，其中，圖７（ａ）是原始模型，圖７（ｂ）是使用α＃算法挖掘的結果。使用本文提出的算法，挖掘出的模型與圖７（ａ）中的模型完全相同。對其他實例的實驗也得到了類似的結果，從而證明了算法的正確性。
６ 結 論
現有的過程挖掘算法大多無法正確挖掘包含隱含任務的過程日志，少數幾種能夠挖掘隱含任務的算法也不夠完善，往往導致挖掘出來的過程模型過分復雜，難以分析和理解。針對這一缺陷，本文通過深入分析研究結構化工作流網過程模型中可能出現的各類隱含任務及其特點，提出了一種基于結構化工作流網的挖掘算法，可以較好地挖掘包含隱含任務的結構化工作流網過程日志，因此能夠更好地幫助用戶分析和理解過程執(zhí)行流結構。作為一種自動化的建模工具，該算法適用于需要應用過程分析和建模的各類場合。本文通過實驗評估驗證了算法的可行性和有效性。接下來的研究方向是在現有算法的基礎上繼續(xù)深入擴展其適用的建模語言范圍，從而進一步提高算法的實用性。
