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

1、. . . . 基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)挖掘方法摘 要 過程挖掘是一種客觀、自動(dòng)化的過程分析技術(shù)，它通過挖掘過程日志來得到業(yè)務(wù)過程的結(jié)構(gòu)模型，是傳統(tǒng)過程分析手段的重要補(bǔ)充。如何正確挖掘包含隱含任務(wù)的不完整過程日志，是過程挖掘需要解決的難題之一?，F(xiàn)有的一些算法如基因算法、#算法等解決了部分類型隱含任務(wù)的挖掘問題，但仍有許多類型的隱含任務(wù)無法被正確挖掘。針對這一問題，本文在#算法的基礎(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)算

2、法doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 07. 025中圖分類號 tp391 文獻(xiàn)標(biāo)識碼 a 文章編號 1673 - 0194（2012）07- 0048- 04 引 言面對激烈的市場競爭和市場環(huán)境的快速變化，現(xiàn)代企業(yè)必須能夠隨時(shí)對核心業(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ù)，

3、通過對業(yè)務(wù)過程日志的挖掘，自動(dòng)生成業(yè)務(wù)過程的執(zhí)行流模型，從而幫助用戶更好地理解業(yè)務(wù)過程的在執(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)用。對包含錯(cuò)誤、隱含任務(wù)等的不完整日志的挖掘是過程挖掘面臨的難題之一。因?yàn)閷?shí)際中用于挖掘的日志主要來源于企業(yè)的信息系統(tǒng)的自動(dòng)生成，因此日志中包含錯(cuò)誤的情況并不常見，不完整日志問題基本上都是由于包含隱含任務(wù)造成的?，F(xiàn)有的大多數(shù)過程挖掘算法在處理包含隱含任務(wù)的日志時(shí)都無法得到正確的結(jié)果。少

4、數(shù)幾種能夠處理隱含任務(wù)的算法，如基因算法、算法等，但只能挖掘部分類型的隱含任務(wù)，未能完全解決隱含任務(wù)的挖掘問題。針對這一問題，本文嘗試提出一種基于算法和結(jié)構(gòu)化工作流網(wǎng)的過程挖掘算法，該算法能夠比較全面地挖掘結(jié)構(gòu)化工作流網(wǎng)模型中的各類隱含任務(wù)。通過理論分析和實(shí)驗(yàn)驗(yàn)證，該算法的正確性得到了證明。 問題說明過程挖掘通過對日志信息的分析來構(gòu)造過程模型。為了保證挖掘算法能夠最大限度地適用于各種形式的日志，絕大多數(shù)挖掘算法僅要求日志中包含下列3項(xiàng)容：事件所屬的工作實(shí)例；執(zhí)行事件的業(yè)務(wù)單元（任務(wù)標(biāo)識）；事件發(fā)生的順序（處理時(shí)間）。因此，在分析過程挖掘算法時(shí)，為了簡便起見，通常直接將日志寫成諸如，的形式，其中

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

6、但都無法完全挖掘所有類型的隱含任務(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)

7、） 工作流網(wǎng)為五元組（，）。其中，為全體庫所集合，t為全體變遷集合，為全體邊集合，為輸入庫所，為輸出庫所。 為工作流網(wǎng)的初始配置。結(jié)構(gòu)化工作流網(wǎng)是工作流網(wǎng)的各類子集中研究最多最深入的一種，其特點(diǎn)是不包含非自由選擇結(jié)構(gòu)，結(jié)構(gòu)相對簡單，但仍能滿足大多數(shù)實(shí)際應(yīng)用的需要。其定義如下：定義（結(jié)構(gòu)化工作流網(wǎng)） 工作流網(wǎng)（，）是一個(gè)結(jié)構(gòu)化工作流網(wǎng)，當(dāng)且僅當(dāng)：（）對任意滿足（，）的和，有：；（2）對任意滿足（，）的p和t，有：tp；（）p中不存在隱含庫所。 隱含任務(wù)定義隱含任務(wù)就是在過程中存在并且被執(zhí)行，但是始終不會(huì)被記錄在過程日志中的任務(wù)。定義（隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)n（，），w=t*是其對應(yīng)的日志

8、。則稱tt是隱含任務(wù)，當(dāng)且僅當(dāng)不存在日志實(shí)例lw，使tl。n的全部隱含任務(wù)的集合記為h。隱含任務(wù)問題的本質(zhì)是日志中的信息缺失。顯然，只有那些導(dǎo)致模型結(jié)構(gòu)出現(xiàn)缺陷的隱含任務(wù)才有可能被發(fā)現(xiàn)，其他隱含任務(wù)在不引入其他知識的條件下是無法通過日志分析的方法來發(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)型對應(yīng)于 算法中的類型，是由出現(xiàn)在模型起始位置的與分支點(diǎn)和

9、出現(xiàn)在模型結(jié)束位置的與匯合點(diǎn)形成的隱含任務(wù)，如圖（）和（）所示。其定義如下：定義（起始結(jié)束點(diǎn)型隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)（，）。當(dāng)隱含任務(wù)th滿足下列條件之一時(shí)，稱其為起始結(jié)束點(diǎn)型隱含任務(wù)：隱含路徑型對應(yīng)于 算法中的和類型，是單獨(dú)組成過程中的某條執(zhí)行路徑分支的隱藏任務(wù)，如圖（）和（）所示。其定義如下：定義（隱含路徑型隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)（，）。稱隱含任務(wù)th為隱含路徑型隱含任務(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)

10、換點(diǎn)型隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)（，）。當(dāng)隱含任務(wù)th滿足下列條件之一時(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ù)th為子分支點(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)缺陷。因此，通過檢測挖掘模型中的結(jié)構(gòu)缺陷，就能夠發(fā)現(xiàn)這些隱含任務(wù)的存在，并加以彌補(bǔ)。本文采用算法中次序關(guān)系作為檢測模型結(jié)構(gòu)缺陷的工具，其定義如

11、下：定義（次序關(guān)系） （，）是合理工作流網(wǎng)，w是n的一個(gè)日志，即wt*，則有： 當(dāng)且僅當(dāng)?堝，：wti=ati+1=b；awb 當(dāng)且僅當(dāng)?堝t1t2tn，i1，：wti=ti+2a=ati+1=b；awb 當(dāng)且僅當(dāng)awbbwa；awb 當(dāng)且僅當(dāng)a（）；a#wb 當(dāng)且僅當(dāng)awbbwa；根據(jù)次序關(guān)系，就可以針對各類隱含任務(wù)的不同特點(diǎn)，分別找出它們的發(fā)現(xiàn)方法。因?yàn)?算法中已經(jīng)給出了起始結(jié)束型和隱含路徑型的隱含任務(wù)的檢測方法，因此本文只討論結(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)（，）

12、，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)的定義和圖，很容易證明該定理的正確

13、性。詳細(xì)證明從略。 隱含任務(wù)的檢測順序由于過程可能同時(shí)存在多種類型的隱含任務(wù)，一種隱含任務(wù)的存在可能會(huì)對另一種隱含的發(fā)現(xiàn)造成影響。因此各隱含任務(wù)的檢測必須符合一定的順序。由于起始結(jié)束點(diǎn)型隱含任務(wù)存在于模型的兩端，其他類型隱含任務(wù)的發(fā)現(xiàn)可能會(huì)依賴于它的正確發(fā)現(xiàn)，因此應(yīng)該先進(jìn)行起始結(jié)束點(diǎn)型隱含任務(wù)的檢測。結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型的隱含任務(wù)本身是選擇結(jié)構(gòu)或者并行結(jié)構(gòu)的起始點(diǎn)或者結(jié)束點(diǎn)，而子分支點(diǎn)型隱含任務(wù)的檢測依賴于選擇結(jié)構(gòu)的起始點(diǎn)或結(jié)束點(diǎn)的存在。因此，結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的檢測必須先于子分支點(diǎn)型隱含任務(wù)。隱含路徑型隱含任務(wù)的正確檢測依賴于選擇結(jié)構(gòu)或者并行結(jié)構(gòu)的正確結(jié)束，因此應(yīng)該最后進(jìn)行。 基于結(jié)構(gòu)化工作流網(wǎng)的

14、挖掘算法 子分支點(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)算法是：（）?堝，（）（，）|ab?奐tw（?坌bba）（?坌， ）（?堝（?坌）（）2（，b|a?奐twbtw（?坌aa a）（?坌a1，a2aa1|w a2）（?堝cb（?坌aa a）（）x=x1x2（）ty=ty|?堝yy（）r1=awty|?堝，（，），（）r2=tywb|?堝，（，），bb（）ry=r1r2（）tw=twty（）rw=rwry 結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)

15、發(fā)現(xiàn)算法根據(jù)前面的討論，結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)算法 如下：定義（ 算法） 已知結(jié)構(gòu)化工作流網(wǎng)n （p，t，f，i，0），w是其滿足和關(guān)系完備性的日志，rw是從得到的所有次序關(guān)系集合。則結(jié)構(gòu)轉(zhuǎn)換點(diǎn)型隱含任務(wù)的發(fā)現(xiàn)算法是：（）?堝，（）（a，）|ab?奐（?坌，）（?坌， ）（?坌，2b1|2）（）2（，b）a?奐twbtw（?坌aa，bbawb）（?坌a1，a2aa1|w a2）（?坌b1，b2bb1b2）（4）3（，b）a?奐twbtw（?坌aa，bbawb）（?坌a1，a2aa1|w a2）（?坌b1，b2bb1b2）（5）x=x1x2x3（7）ty=ty|?堝yy（8）r1=awty|

16、?堝，（，），（9）r2=tywb|?堝，（，），bb（10）ry=r1r2（1）tw=twty（2）rw=rwry3 基于結(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)算法，（，）是使用算法

17、構(gòu)造過程模型。 實(shí)驗(yàn)評估本文使用語言在平臺(tái)上實(shí)現(xiàn)了提出的基于結(jié)構(gòu)化工作流網(wǎng)的隱含任務(wù)發(fā)現(xiàn)算法，并對其進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)使用了個(gè)手工構(gòu)造的過程實(shí)例進(jìn)行。圖顯示了實(shí)驗(yàn)中所使用的一個(gè)實(shí)例，其中，圖（）是原始模型，圖（）是使用算法挖掘的結(jié)果。使用本文提出的算法，挖掘出的模型與圖（）中的模型完全一樣。對其他實(shí)例的實(shí)驗(yàn)也得到了類似的結(jié)果，從而證明了算法的正確性。 結(jié) 論現(xiàn)有的過程挖掘算法大多無確挖掘包含隱含任務(wù)的過程日志，少數(shù)幾種能夠挖掘隱含任務(wù)的算法也不夠完善，往往導(dǎo)致挖掘出來的過程模型過分復(fù)雜，難以分析和理解。針對這一缺陷，本文通過深入分析研究結(jié)構(gòu)化工作流網(wǎng)過程模型中可能出現(xiàn)的各類隱含任務(wù)與其特點(diǎn)，

18、提出了一種基于結(jié)構(gòu)化工作流網(wǎng)的挖掘算法，可以較好地挖掘包含隱含任務(wù)的結(jié)構(gòu)化工作流網(wǎng)過程日志，因此能夠更好地幫助用戶分析和理解過程執(zhí)行流結(jié)構(gòu)。作為一種自動(dòng)化的建模工具，該算法適用于需要應(yīng)用過程分析和建模的各類場合。本文通過實(shí)驗(yàn)評估驗(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