瞿華

［摘要］ 過程挖掘是一種客觀、自動(dòng)化的過程分析技術(shù)，它通過挖掘過程日志來得到業(yè)務(wù)過程的結(jié)構(gòu)模型，是傳統(tǒng)過程分析手段的重要補(bǔ)充。如何正確挖掘包含隱含任務(wù)的不完整過程日志，是過程挖掘需要解決的難題之一。現(xiàn)有的一些算法如基因算法、α#算法等解決了部分類型隱含任務(wù)的挖掘問題，但仍有許多類型的隱含任務(wù)無法被正確挖掘。針對(duì)這一問題，本文在α#算法的基礎(chǔ)上提出了一種基于結(jié)構(gòu)化工作流網(wǎng)的挖掘算法，該算法能夠較為完整地挖掘各類包含隱含任務(wù)的結(jié)構(gòu)化工作流網(wǎng)模型。通過理論分析和實(shí)驗(yàn)驗(yàn)證，該算法的正確性和有效性得到了證明。

［關(guān)鍵詞］ 過程挖掘；結(jié)構(gòu)化工作流網(wǎng)；隱含任務(wù)；改進(jìn)α算法

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 07. 025

［中圖分類號(hào)］TP391［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673 - 0194（2012）07- 0048- 04

０引言

面對(duì)激烈的市場(chǎng)競(jìng)爭(zhēng)和市場(chǎng)環(huán)境的快速變化，現(xiàn)代企業(yè)必須能夠隨時(shí)對(duì)核心業(yè)務(wù)過程做出適當(dāng)?shù)恼{(diào)整以適應(yīng)新的需要。這不但需要管理者能夠掌握外部環(huán)境的變化，也需要管理者能夠?qū)ζ髽I(yè)業(yè)務(wù)過程的實(shí)際情況有清晰的了解。傳統(tǒng)的過程分析手段，如調(diào)查、訪談、建模分析和模擬等，費(fèi)時(shí)費(fèi)力，而且受用戶的主觀性影響很大，容易出現(xiàn)偏差，因此越來越難以滿足用戶的需要。

過程挖掘是一種自動(dòng)化的過程分析技術(shù)，通過對(duì)業(yè)務(wù)過程日志的挖掘，自動(dòng)生成業(yè)務(wù)過程的執(zhí)行流模型，從而幫助用戶更好地理解業(yè)務(wù)過程的內(nèi)在執(zhí)行邏輯［１］。由于其分析的依據(jù)——業(yè)務(wù)過程日志是企業(yè)在實(shí)際業(yè)務(wù)運(yùn)行過程中生成的客觀記錄，因此該技術(shù)客觀性強(qiáng)、費(fèi)用低、速度快，有效地彌補(bǔ)了傳統(tǒng)過程分析手段的各種缺陷，并已經(jīng)在政府公共工程、醫(yī)院和供應(yīng)鏈管理等實(shí)際領(lǐng)域中取得了一定的成功應(yīng)用［２－４］。

對(duì)包含錯(cuò)誤、隱含任務(wù)［５］等的不完整日志的挖掘是過程挖掘面臨的難題之一。因?yàn)閷?shí)際中用于挖掘的日志主要來源于企業(yè)的信息系統(tǒng)的自動(dòng)生成，因此日志中包含錯(cuò)誤的情況并不常見，不完整日志問題基本上都是由于包含隱含任務(wù)造成的?，F(xiàn)有的大多數(shù)過程挖掘算法在處理包含隱含任務(wù)的日志時(shí)都無法得到正確的結(jié)果。少數(shù)幾種能夠處理隱含任務(wù)的算法，如基因算法［６］、α＃算法［７］等，但只能挖掘部分類型的隱含任務(wù)，未能完全解決隱含任務(wù)的挖掘問題。

針對(duì)這一問題，本文嘗試提出一種基于α算法［８］和結(jié)構(gòu)化工作流網(wǎng)［９］的過程挖掘算法，該算法能夠比較全面地挖掘結(jié)構(gòu)化工作流網(wǎng)模型中的各類隱含任務(wù)。通過理論分析和實(shí)驗(yàn)驗(yàn)證，該算法的正確性得到了證明。

１問題說明

過程挖掘通過對(duì)日志信息的分析來構(gòu)造過程模型。為了保證挖掘算法能夠最大限度地適用于各種形式的日志，絕大多數(shù)挖掘算法僅要求日志中包含下列3項(xiàng)內(nèi)容：①事件所屬的工作實(shí)例；②執(zhí)行事件的業(yè)務(wù)單元（任務(wù)標(biāo)識(shí)）；③事件發(fā)生的順序（處理時(shí)間）。因此，在分析過程挖掘算法時(shí)，為了簡(jiǎn)便起見，通常直接將日志寫成諸如ＡＢＣＤＥ，ＡＢＣＤＦ，ＡＣＢＤＥ，ＡＣＢＤＦ的形式，其中每個(gè)字母代表一個(gè)任務(wù)，每個(gè)逗號(hào)隔開的字母序列代表一條日志實(shí)例。對(duì)該日志實(shí)例用算法進(jìn)行過程挖掘，就可以得到如圖１（ａ）所示的結(jié)構(gòu)化工作流網(wǎng)過程模型。

在現(xiàn)實(shí)中，由于很多信息系統(tǒng)只對(duì)進(jìn)行實(shí)際業(yè)務(wù)操作的業(yè)務(wù)單元活動(dòng)進(jìn)行記錄，以及系統(tǒng)采用的過程建模工具本身的特性等各種原因，一些過程任務(wù)往往沒有被記錄在日志中。這種過程任務(wù)就是所謂的“隱含任務(wù)”?，F(xiàn)有的大多數(shù)算法無法正確處理包含隱含任務(wù)的日志。例如，假設(shè)圖１（ａ）中過程的任務(wù)Ｄ是一個(gè)隱含任務(wù)，則得到的日志是ＡＢＣＥ，ＡＢＣＦ，ＡＣＢＥ，ＡＣＢＦ。用α算法挖掘?qū)⒌玫饺鐖D１（ｂ）所示的模型，它不是一個(gè)合法的結(jié)構(gòu)化工作流網(wǎng)模型，而且相比原始模型，其結(jié)構(gòu)復(fù)雜，不容易為用戶所理解。

現(xiàn)有少數(shù)算法能夠挖掘部分類型的隱含任務(wù)，但都無法完全挖掘所有類型的隱含任務(wù)。例如，圖２給出了α ＃算法能夠挖掘的幾種隱含任務(wù)，其中黑色方塊表示隱含任務(wù)。但它無法挖掘圖１（ａ）類型的隱含任務(wù)。

因此，本文在綜合現(xiàn)有各種隱含任務(wù)挖掘方法的基礎(chǔ)上，結(jié)合結(jié)構(gòu)化工作流網(wǎng)本身的特性，提出了一種基于算法和結(jié)構(gòu)化工作流網(wǎng)的過程挖掘算法，該算法能夠比較全面地挖掘結(jié)構(gòu)化工作流網(wǎng)模型中的各類隱含任務(wù)。

２ 結(jié)構(gòu)化工作流網(wǎng)中的隱含任務(wù)

２．１ 結(jié)構(gòu)化工作流網(wǎng)

過程挖掘通過深入分析過程日志來構(gòu)造出過程模型。顯然，算法所使用的建模語言決定了算法能夠成功挖掘的過程及其日志的特性。目前，絕大多數(shù)過程挖掘算法都采用工作流網(wǎng)［１０］或者其子集作為建模語言，它是Ｐｅｔｒｉ網(wǎng)的一個(gè)子集，具體定義如下：

定義１（工作流網(wǎng)） 工作流網(wǎng)Ｎ為五元組（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。其中，Ｐ為全體庫(kù)所集合，T為全體變遷集合，Ｆ為全體邊集合，ｉ為輸入庫(kù)所，ｏ為輸出庫(kù)所。Ｍｏ ＝｛ｉ｝為工作流網(wǎng)的初始配置。

結(jié)構(gòu)化工作流網(wǎng)是工作流網(wǎng)的各類子集中研究最多最深入的一種，其特點(diǎn)是不包含非自由選擇結(jié)構(gòu)，結(jié)構(gòu)相對(duì)簡(jiǎn)單，但仍能滿足大多數(shù)實(shí)際應(yīng)用的需要。其定義如下：

定義２（結(jié)構(gòu)化工作流網(wǎng)） 工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）是一個(gè)結(jié)構(gòu)化工作流網(wǎng)，當(dāng)且僅當(dāng)：

（１）對(duì)任意滿足（ｐ，ｔ）∈Ｆ的ｐ和ｔ，有：｜ｐ·｜＞１→｜·ｔ｜＝１；

（2）對(duì)任意滿足（ｐ，ｔ）∈Ｆ的p和t，有：｜·t｜＞１→｜p·｜＝１；

（３）P中不存在隱含庫(kù)所［９］。

２．２ 隱含任務(wù)定義

隱含任務(wù)就是在過程中存在并且被執(zhí)行，但是始終不會(huì)被記錄在過程日志中的任務(wù)。

定義３（隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)N＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W=T*是其對(duì)應(yīng)的日志。則稱t∈T是隱含任務(wù)，當(dāng)且僅當(dāng)不存在日志實(shí)例L∈W，使t∈L。N的全部隱含任務(wù)的集合記為H。

隱含任務(wù)問題的本質(zhì)是日志中的信息缺失。顯然，只有那些導(dǎo)致模型結(jié)構(gòu)出現(xiàn)缺陷的隱含任務(wù)才有可能被發(fā)現(xiàn)，其他隱含任務(wù)在不引入其他知識(shí)的條件下是無法通過日志分析的方法來發(fā)現(xiàn)的。例如，圖４中的幾種隱含任務(wù)都不會(huì)導(dǎo)致挖掘模型出現(xiàn)結(jié)構(gòu)缺陷，都是無法被發(fā)現(xiàn)的。因此，本文只討論會(huì)導(dǎo)致結(jié)構(gòu)化工作流網(wǎng)的結(jié)構(gòu)出現(xiàn)缺陷的那些隱含任務(wù)。

２．３ 隱含任務(wù)分類

按照在模型中的位置及其特點(diǎn)，可以將結(jié)構(gòu)化工作流網(wǎng)中的隱含任務(wù)分成起始／結(jié)束點(diǎn)型、隱含路徑型、結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型和子分支點(diǎn)型四大類。

起始／結(jié)束點(diǎn)型對(duì)應(yīng)于α ＃算法中的ＳＩＤＥ類型［７］，是由出現(xiàn)在模型起始位置的與－分支點(diǎn)和出現(xiàn)在模型結(jié)束位置的與－匯合點(diǎn)形成的隱含任務(wù)，如圖２（ａ）和（ｂ）所示。其定義如下：

定義４（起始／結(jié)束點(diǎn)型隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。當(dāng)隱含任務(wù)t∈H滿足下列條件之一時(shí)，稱其為起始／結(jié)束點(diǎn)型隱含任務(wù)：

隱含路徑型對(duì)應(yīng)于α ＃算法中的ＳＫＩＰ和ＲＥＤＯ類型，是單獨(dú)組成過程中的某條執(zhí)行路徑分支的隱藏任務(wù)，如圖２（ｃ）和（ｄ）所示。其定義如下：

定義５（隱含路徑型隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。稱隱含任務(wù)t∈H為隱含路徑型隱含任務(wù)，當(dāng)?堝ａ，ｂ∈Ｔ－Ｈ，a·?勱·t，ｔ·?奐·ｂ。

結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型是由選擇結(jié)構(gòu)和并行結(jié)構(gòu)之間的轉(zhuǎn)換點(diǎn)形成的隱含任務(wù)。圖５是結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的幾種情況，其中左邊是原始過程，右邊是用α算法挖掘?qū)?yīng)的日志得到的模型。其定義如下：

定義６（結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。當(dāng)隱含任務(wù)t∈H滿足下列條件之一時(shí)，稱其為結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)：

子分支點(diǎn)型是由選擇分支里的并行分支點(diǎn)形成的隱含任務(wù)。圖６是結(jié)構(gòu)轉(zhuǎn)換點(diǎn)的幾種情況，其中左邊是原始過程，右邊是用α算法挖掘?qū)?yīng)的日志得到的模型。其定義如下：

定義７（子分支點(diǎn)型隱含任務(wù)）已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。稱隱含任務(wù)t∈H為子分支點(diǎn)型隱含任務(wù)，當(dāng)其滿足下列條件之一：

３隱含任務(wù)的發(fā)現(xiàn)

在上一節(jié)中定義了幾種隱含任務(wù)，它們的共同特點(diǎn)是會(huì)導(dǎo)致結(jié)構(gòu)化工作流網(wǎng)的結(jié)構(gòu)出現(xiàn)缺陷。因此，通過檢測(cè)挖掘模型中的結(jié)構(gòu)缺陷，就能夠發(fā)現(xiàn)這些隱含任務(wù)的存在，并加以彌補(bǔ)。本文采用α＋［９］算法中次序關(guān)系作為檢測(cè)模型結(jié)構(gòu)缺陷的工具，其定義如下：

定義８（次序關(guān)系）Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）是合理工作流網(wǎng)，W是N的一個(gè)日志，即W∈T*，ａ，ｂ∈Ｔ，則有：

－ａ＞Ｗｂ當(dāng)且僅當(dāng)?堝σ＝ｔ１ｔ２…ｔｎ，ｉ∈｛１，…，ｎ－１｝：σ∈W∧ti=a∧ti+1=b；

－aΔWb當(dāng)且僅當(dāng)?堝σ＝t1t2…tn，i∈｛1，…，ｎ－２｝：σ∈W∧ti=ti+2a=a∧ti+1=b；；

－a◇Wb當(dāng)且僅當(dāng)aΔWb∨bΔWa；

－a→Wb 當(dāng)且僅當(dāng)a>Ｗｂ∧（ｂ≯Ｗａ∨ａ◇Ｗｂ）；

－a#Wb當(dāng)且僅當(dāng)aW≯b∧b≮Wa；

根據(jù)次序關(guān)系，就可以針對(duì)各類隱含任務(wù)的不同特點(diǎn)，分別找出它們的發(fā)現(xiàn)方法。因?yàn)棣?＃算法中已經(jīng)給出了起始／結(jié)束型和隱含路徑型的隱含任務(wù)的檢測(cè)方法，因此本文只討論結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型和子分支點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)方法。

３．１ 結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)

結(jié)構(gòu)化工作流網(wǎng)中的結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)可以根據(jù)下面的定理發(fā)現(xiàn)：

定理１已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→W和ΔW關(guān)系完備性的日志。則N中存在結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)，當(dāng)且僅當(dāng)下列條件之一被滿足：

（１）?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ＃Ｗ ｂ，ｄ｜｜Ｗ ｃ，ａ→Ｗ ｃ，ａ→Ｗ ｄ，ｂ→Ｗ ｃ，ａ→Ｗ ｄ；

（２）?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ＃Ｗ ｂ，ｄ｜｜Ｗ ｃ，ａ→Ｗ ｃ，ａ→Ｗ ｄ，ｂ→Ｗ ｃ，ａ→Ｗ ｄ；

（３）?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ＃Ｗ ｂ，ｄ｜｜Ｗ ｃ，ａ→Ｗ ｃ，ａ→Ｗ ｄ，ｂ→Ｗ ｃ，ａ→Ｗ ｄ。

根據(jù)結(jié)構(gòu)化工作流網(wǎng)的定義和圖５，很容易證明該定理的正確性。詳細(xì)證明從略。

３．２ 子分支點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)

結(jié)構(gòu)化工作流網(wǎng)中的子分支點(diǎn)型隱含任務(wù)可以根據(jù)下面的定理發(fā)現(xiàn)：

定理２已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→Ｗ 和ΔＷ 關(guān)系完備性的日志。則N中存在子分支點(diǎn)型隱含任務(wù)，當(dāng)且僅當(dāng)下列條件之一被滿足：

（１）?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ→Ｗ ｂ，ａ→Ｗ ｃ，ａ→Ｗ ｂ，ｂ＃Ｗ ｄ，ｃ＃Ｗ ｄ，ｂ｜｜Ｗｃ；

（2）?堝ａ，ｂ，ｃ，ｄ∈Ｔ，ａ→Ｗ ｄ，ｂ→Ｗ ｄ，ｃ→Ｗ ｄ，ａ＃Ｗ ｃ，ｂ＃Ｗ ｃ，ａ｜｜Ｗ b。

根據(jù)結(jié)構(gòu)化工作流網(wǎng)的定義和圖６，很容易證明該定理的正確性。詳細(xì)證明從略。

３．３ 隱含任務(wù)的檢測(cè)順序

由于過程可能同時(shí)存在多種類型的隱含任務(wù)，一種隱含任務(wù)的存在可能會(huì)對(duì)另一種隱含的發(fā)現(xiàn)造成影響。因此各隱含任務(wù)的檢測(cè)必須符合一定的順序。

由于起始／結(jié)束點(diǎn)型隱含任務(wù)存在于模型的兩端，其他類型隱含任務(wù)的發(fā)現(xiàn)可能會(huì)依賴于它的正確發(fā)現(xiàn)，因此應(yīng)該先進(jìn)行起始／結(jié)束點(diǎn)型隱含任務(wù)的檢測(cè)。

結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型的隱含任務(wù)本身是選擇結(jié)構(gòu)或者并行結(jié)構(gòu)的起始點(diǎn)或者結(jié)束點(diǎn)，而子分支點(diǎn)型隱含任務(wù)的檢測(cè)依賴于選擇結(jié)構(gòu)的起始點(diǎn)或結(jié)束點(diǎn)的存在。因此，結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的檢測(cè)必須先于子分支點(diǎn)型隱含任務(wù)。

隱含路徑型隱含任務(wù)的正確檢測(cè)依賴于選擇結(jié)構(gòu)或者并行結(jié)構(gòu)的正確結(jié)束，因此應(yīng)該最后進(jìn)行。

４基于結(jié)構(gòu)化工作流網(wǎng)的挖掘算法

４．１ 子分支點(diǎn)型隱含任務(wù)發(fā)現(xiàn)算法

根據(jù)前面的討論，子分支點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)算法Ｆｉｎｄ Ｓｕｂ Ｂｒａｎｃｈ ＩＴ如下：

定義９（Ｆｉｎｄ Ｓｕｂ Ｂｒａｎｃｈ ＩＴ算法）已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→W和ΔW關(guān)系完備性的日志，RW是從W得到的所有次序關(guān)系集合。則子分支點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)算法是：

（１）ＴＷ＝｛ｔ｜?堝σ∈Ｗ，ｔ∈σ｝

（２）Ｘ１＝｛（｛ａ｝，Ｂ）|a∈ＴＷ∧B?奐TW∧（?坌b∈B∶a→Ｗｂ）∧（?坌ｂ１，ｂ２∈Ｂ∶ｂ１｜｜Ｗ ｂ２）∧（?堝ｃ∈ＴＷ∶ａ→Ｗｃ∧（?坌ｂ∈Ｂ∶ｃ＃Ｗｂ））｝

（３）Ｘ2＝｛（Ａ，｛b｝|A?奐TW∧b∈TW∧（?坌a∈A∶ ｃ＃Ｗa）∧（?坌a1，a2∈A∶a1||W a2）∧（?堝ｃ∈ＴＷ∶c→Ｗb∧（?坌a∈A∶ ｃ＃Ｗa））｝

（４）X=X1∪X2

（６）TY=｛ty|?堝y∈Y｝

（７）R1=｛a→Wty|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），ａ∈Ａ｝

（８）R2=｛ty→Wb|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），b∈B｝

（９）RY=R1∪R2

（１０）TW=TW∪TY

（１１）RW=RW∪RY

４．２ 結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)發(fā)現(xiàn)算法

根據(jù)前面的討論，結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)算法Ｆｉｎｄ Ｂｒａｎｃｈ Ｃｏｎｎｅｃｔｏｒ ＩＴ如下：

定義９（Ｆｉｎｄ Ｂｒａｎｃｈ Ｃｏｎｎｅｃｔｏｒ ＩＴ算法）已知結(jié)構(gòu)化工作流網(wǎng)N ＝ （P，T，F(xiàn)，i，0），W是其滿足和關(guān)系完備性的日志，RW是從得到的所有次序關(guān)系集合。則結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)算法是：

（１）ＴＷ＝｛ｔ｜?堝σ∈Ｗ，ｔ∈σ｝

（２）Ｘ１＝｛（A，Ｂ）|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）｝

（4）Ｘ3＝｛（Ａ，B）｜A?奐TW∧B∈TW∧（?坌a∈A，b∈B∶a→Wb）∧（?坌a1，a2∈A∶a1||W a2）∧（?坌b1，b2∈B∶b1＃Ｗb2）｝

（5）X=X1∪X2∪X3

（7）TY=｛ty|?堝y∈Y｝

（8）R1=｛a→Wty|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），ａ∈Ａ｝

（9）R2=｛ty→Wb|?堝ｙ∈Ｙ，ｙ＝（Ａ，Ｂ），b∈B｝

（10）RY=R1∪R2

（１1）TW=TW∪TY

（１2）RW=RW∪RY

４．3 基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)挖掘算法

最終得到的基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)發(fā)現(xiàn)算法如下：

定義１０（基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)發(fā)現(xiàn)算法）已知結(jié)構(gòu)化工作流網(wǎng)Ｎ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W是其滿足→Ｗ和ΔW關(guān)系完備性的日志。則基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)發(fā)現(xiàn)算法是：

（１）ＴＷ＝｛ｔ｜?堝σ∈Ｗ，ｔ∈σ｝

（２）構(gòu)造RW

（３）（ＴＷ，ＲＷ）＝ＣｏｎＳｉｄｅＩＴ（ＴＷ，ＲＷ）

（４）（ＴＷ，ＲＷ）＝ＦｉｎｄＳｕｂＢｒａｎｃｈＩＴ（ＴＷ，ＲＷ）

（５）（ＴＷ，ＲＷ）＝ＦｉｎｄＢｒａｎｃｈＣｏｎｎｅｃｔｏｒＩＴ（ＴＷ，ＲＷ）

（６）（ＴＷ，ＲＷ）＝ＣｏｎＩＴ（ＴＷ，ＲＷ）

（７）N＝α（ＴＷ，ＲＷ）

其中，Ｆｉｎｄ Ｓｕｂ Ｂｒａｎｃｈ ＩＴ和Ｆｉｎｄ Ｂｒａｎｃｈ Ｃｏｎｎｅｃｔｏｒ ＩＴ分別是前面定義的子分支點(diǎn)型和結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)發(fā)現(xiàn)算法，ＣｏｎＳｉｄｅＩＴ和ＣｏｎＩＴ分別是α＃算法中定義的起始／結(jié)束點(diǎn)型和隱含路徑型隱含任務(wù)發(fā)現(xiàn)算法，α（ＴＷ，ＲＷ）是使用α算法構(gòu)造過程模型。

５ 實(shí)驗(yàn)評(píng)估

本文使用Ｊａｖａ語言在ＰｒｏＭ平臺(tái)［１１］上實(shí)現(xiàn)了提出的基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)發(fā)現(xiàn)算法，并對(duì)其進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)使用了１８?jìng)€(gè)手工構(gòu)造的過程實(shí)例進(jìn)行。圖７顯示了實(shí)驗(yàn)中所使用的一個(gè)實(shí)例，其中，圖７（ａ）是原始模型，圖７（ｂ）是使用α＃算法挖掘的結(jié)果。使用本文提出的算法，挖掘出的模型與圖７（ａ）中的模型完全相同。對(duì)其他實(shí)例的實(shí)驗(yàn)也得到了類似的結(jié)果，從而證明了算法的正確性。

６結(jié)論

現(xiàn)有的過程挖掘算法大多無法正確挖掘包含隱含任務(wù)的過程日志，少數(shù)幾種能夠挖掘隱含任務(wù)的算法也不夠完善，往往導(dǎo)致挖掘出來的過程模型過分復(fù)雜，難以分析和理解。針對(duì)這一缺陷，本文通過深入分析研究結(jié)構(gòu)化工作流網(wǎng)過程模型中可能出現(xiàn)的各類隱含任務(wù)及其特點(diǎn)，提出了一種基于結(jié)構(gòu)化工作流網(wǎng)的挖掘算法，可以較好地挖掘包含隱含任務(wù)的結(jié)構(gòu)化工作流網(wǎng)過程日志，因此能夠更好地幫助用戶分析和理解過程執(zhí)行流結(jié)構(gòu)。作為一種自動(dòng)化的建模工具，該算法適用于需要應(yīng)用過程分析和建模的各類場(chǎng)合。本文通過實(shí)驗(yàn)評(píng)估驗(yàn)證了算法的可行性和有效性。接下來的研究方向是在現(xiàn)有算法的基礎(chǔ)上繼續(xù)深入擴(kuò)展其適用的建模語言范圍，從而進(jìn)一步提高算法的實(shí)用性。

主要參考文獻(xiàn)

［１］B F ｖａｎ Ｄｏｎｇｅｎ，A K Ａｌｖｅｓ ｄｅ Ｍｅｄｅｉｒｏｓ，ｅｔｃ． Ｐｒｏｃｅｓｓ Ｍｉｎｉｎｇ： Ｏｖｅｒｖｉｅｗ ａｎｄ Ｏｕｔｌｏｏｋ ｏｆ Ｐｅｔｒｉ Ｎｅｔ Ｄｉｓｃｏｖｅｒｙ Ａｌｇｏｒｉｔｈｍｓ［M］//K Jensen, W M P van der Aalst（Ｅｄｓ）. Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐｅｔｒｉ Ｎｅｔｓ ａｎｄ Ｏｔｈｅｒ Ｍｏｄｅｌｓ ｏｆ Ｃｏｎｃｕｒｒｅｎｃｙ ＩＩ，Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ，２００９：２２５－２４２．

［２］W M P ｖａｎ ｄｅｒ Ａａｌｓｔ，Ｒｅｉｊｅｒｓ Ｈ Ａ， ｅｔｃ． Ｂｕｓｉｎｅｓｓ Pｒｏｃｅｓｓ Mｉｎｉｎｇ： Ａｎ Iｎｄｕｓｔｒｉａｌ Aｐｐｌｉｃａｔｉｏｎ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， ２００７， ３２（５）： ７１３－７３２．

［３］T Ｂｌｕｍ，N Ｐａｄｏｙ，ｅｔｃ． Ｗｏｒｋｆｌｏｗ Mｉｎｉｎｇ ｆｏｒ Vｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Aｎａｌｙｓｉｓ ｏｆ Sｕｒｇｅｒｉｅｓ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｓｓｉｓｔｅｄ Ｒａｄｉｏｌｏｇｙ ａｎｄ Ｓｕｒｇｅｒｙ， ２００８， ３（５）： ３７９－３８６．

［４］H C W Ｌａｕ，G T SＨｏ， ｅｔｃ． Ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ａ Pｒｏｃｅｓｓ Mｉｎｉｎｇ Sｙｓｔｅｍ ｆｏｒ Sｕｐｐｏｒｔｉｎｇ Kｎｏｗｌｅｄｇｅ Dｉｓｃｏｖｅｒｙ ｉｎ ａ Sｕｐｐｌｙ Cｈａｉｎ Nｅｔｗｏｒｋ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐｒｏｄｕｃｔｉｏｎ Ｅｃｏｎｏｍｉｃｓ， ２００９， １２２（１）： １７６－１８７．

［５］ W M P ｖａｎ ｄｅｒ Ａａｌｓｔ，B F ｖａｎ Ｄｏｎｇｅｎ，ｅｔｃ． Ｗｏｒｋｆｌｏｗ Mｉｎｉｎｇ： Ａ Sｕｒｖｅｙ ｏｆ Iｓｓｕｅｓ ａｎｄ Aｐｐｒｏａｃｈｅｓ［Ｊ］． Ｄａｔａ ＆ Ｋｎｏｗｌｅｄｇｅ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００３， ４７（２）： ２３７－２６７．

［６］A ｄｅ Ｍｅｄｅｉｒｏｓ， Ａ Ｗｅｉｊｔｅｒｓ，ｅｔｃ． Ｇｅｎｅｔｉｃ Pｒｏｃｅｓｓ Mｉｎｉｎｇ： Aｎ Eｘｐｅｒｉｍｅｎｔａｌ Eｖａｌｕａｔｉｏｎ［Ｊ］． Ｄａｔａ Ｍｉｎｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ， ２００７， １４（２）： ２４５－３０４．

［７］Ｗｅｎ Ｌ，Ｗａｎｇ Ｊ， ｅｔｃ． Ｍｉｎｉｎｇ Ｉｎｖｉｓｉｂｌｅ Ｔａｓｋｓ ｆｒｏｍ Ｅｖｅｎｔ Ｌｏｇｓ［Ｍ］//Ｇ Ｄｏｎｇ，ｅｔ ａｌ （Ｅｄｓ）. ＡＰＷｅｂ／ＷＡＩＭ ２００７． Ｓｐｒｉｎｇｅｒ-Verlag，Berlin Ｈｅｉｄｅｌｂｅｒｇ， ２００７:358-365．

［８］W M P ｖａｎ ｄｅｒ Ａａｌｓｔ，A J M M Ｗｅｉｊｔｅｒｓ，ｅｔｃ． Ｗｏｒｋｆｌｏｗ Ｍｉｎｉｎｇ： Ｄｉｓｃｏｖｅｒｉｎｇ Ｐｒｏｃｅｓｓ Ｍｏｄｅｌｓ ｆｒｏｍ Ｅｖｅｎｔ Ｌｏｇｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００４， １６（９）： １１２８－１１４２．

［９］A K A ｄｅ Ｍｅｄｅｉｒｏｓ，B F ｖａｎ Ｄｏｎｇｅｎ，ｅｔｃ． Ｐｒｏｃｅｓｓ Ｍｉｎｉｎｇ ｆｏｒ Ｕｂｉｑｕｉｔｏｕｓ Ｍｏｂｉｌｅ Ｓｙｓｔｅｍｓ： Ａｎ Ｏｖｅｒｖｉｅｗ ａｎｄ ａ Ｃｏｎｃｒｅｔｅ Ａｌｇｏｒｉｔｈｍ［M］//Ｌ Ｂａｒｅｓｉ， ＳＤｕｓｔｄａｒ， Ｈ Ｃ Ｇａｌｌ， ａｎｄ Ｍ Ｍａｔｅｒａ（Eds）． ＵＭＩＣＳ ２００４． Ｓｐｒｉｎｇｅｒ-Verlag， Berlin Ｈｅｉｄｅｌｂｅｒｇ， ２００４：１５１－１６５．

［１０］W M P ｖａｎ ｄｅｒ Ａａｌｓｔ. Ｔｈｅ Aｐｐｌｉｃａｔｉｏｎ ｏｆ Ｐｅｔｒｉ Nｅｔｓ ｔｏ Wｏｒｋｆｌｏｗ Mａｎａｇｅｍｅｎｔ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｉｒｃｕｉｔｓ，Ｓｙｓｔｅｍｓ ａｎｄ Ｃｏｍｐｕｔｅｒｓ，１９９８，８（１）：２１－６６．

［１１］B F ｖａｎ Ｄｏｎｇｅｎ，A K A ｄｅ Ｍｅｄｅｉｒｏｓ，ｅｔｃ． Ｔｈｅ ＰｒｏＭ Ｆｒａｍｅｗｏｒｋ： Ａ Ｎｅｗ Ｅｒａ ｉｎ Ｐｒｏｃｅｓｓ Ｍｉｎｉｎｇ Ｔｏｏｌ Ｓｕｐｐｏｒｔ［Ｍ］// G Ciardo，Ｐ Darondeau（Eds）. ICATPN 2005. Springer-Verlag,Berlin Heidelberg,2005:444-454.