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

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

2、法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ù)過(guò)程做出適當(dāng)?shù)恼{(diào)整以適應(yīng)新的需要。這不但需要管理者能夠掌握外部環(huán)境的變化，也需要管理者能夠?qū)ζ髽I(yè)業(yè)務(wù)過(guò)程的實(shí)際情況有清晰的了解。傳統(tǒng)的過(guò)程分析手段，如調(diào)查、訪談、建模分析和模擬等，費(fèi)時(shí)費(fèi)力，而且受用戶的主觀性影響很大，容易出現(xiàn)偏差，因此越來(lái)越難以滿足用戶的需要。過(guò)程挖掘是一種自動(dòng)化的過(guò)程分析技術(shù)，

3、通過(guò)對(duì)業(yè)務(wù)過(guò)程日志的挖掘，自動(dòng)生成業(yè)務(wù)過(guò)程的執(zhí)行流模型，從而幫助用戶更好地理解業(yè)務(wù)過(guò)程的在執(zhí)行邏輯。由于其分析的依據(jù)業(yè)務(wù)過(guò)程日志是企業(yè)在實(shí)際業(yè)務(wù)運(yùn)行過(guò)程中生成的客觀記錄，因此該技術(shù)客觀性強(qiáng)、費(fèi)用低、速度快，有效地彌補(bǔ)了傳統(tǒng)過(guò)程分析手段的各種缺陷，并已經(jīng)在政府公共工程、醫(yī)院和供應(yīng)鏈管理等實(shí)際領(lǐng)域中取得了一定的成功應(yīng)用。對(duì)包含錯(cuò)誤、隱含任務(wù)等的不完整日志的挖掘是過(guò)程挖掘面臨的難題之一。因?yàn)閷?shí)際中用于挖掘的日志主要來(lái)源于企業(yè)的信息系統(tǒng)的自動(dòng)生成，因此日志中包含錯(cuò)誤的情況并不常見(jiàn)，不完整日志問(wèn)題基本上都是由于包含隱含任務(wù)造成的?，F(xiàn)有的大多數(shù)過(guò)程挖掘算法在處理包含隱含任務(wù)的日志時(shí)都無(wú)法得到正確的結(jié)果。少

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

5、每個(gè)字母代表一個(gè)任務(wù)，每個(gè)逗號(hào)隔開(kāi)的字母序列代表一條日志實(shí)例。對(duì)該日志實(shí)例用算法進(jìn)行過(guò)程挖掘，就可以得到如圖（）所示的結(jié)構(gòu)化工作流網(wǎng)過(guò)程模型。在現(xiàn)實(shí)中，由于很多信息系統(tǒng)只對(duì)進(jìn)行實(shí)際業(yè)務(wù)操作的業(yè)務(wù)單元活動(dòng)進(jìn)行記錄，以與系統(tǒng)采用的過(guò)程建模工具本身的特性等各種原因，一些過(guò)程任務(wù)往往沒(méi)有被記錄在日志中。這種過(guò)程任務(wù)就是所謂的“隱含任務(wù)”?，F(xiàn)有的大多數(shù)算法無(wú)確處理包含隱含任務(wù)的日志。例如，假設(shè)圖（）中過(guò)程的任務(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ù)。但它無(wú)法挖掘圖（）類型的隱含任務(wù)。因此，本文在綜合現(xiàn)有各種隱含任務(wù)挖掘方法的基礎(chǔ)上，結(jié)合結(jié)構(gòu)化工作流網(wǎng)本身的特性，提出了一種基于算法和結(jié)構(gòu)化工作流網(wǎng)的過(guò)程挖掘算法，該算法能夠比較全面地挖掘結(jié)構(gòu)化工作流網(wǎng)模型中的各類隱含任務(wù)。 結(jié)構(gòu)化工作流網(wǎng)中的隱含任務(wù) 結(jié)構(gòu)化工作流網(wǎng)過(guò)程挖掘通過(guò)深入分析過(guò)程日志來(lái)構(gòu)造出過(guò)程模型。顯然，算法所使用的建模語(yǔ)言決定了算法能夠成功挖掘的過(guò)程與其日志的特性。目前，絕大多數(shù)過(guò)程挖掘算法都采用工作流網(wǎng)或者其子集作為建模語(yǔ)言，它是網(wǎng)的一個(gè)子集，具體定義如下：定義（工作流網(wǎng)

7、） 工作流網(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，有：tp；（）p中不存在隱含庫(kù)所。 隱含任務(wù)定義隱含任務(wù)就是在過(guò)程中存在并且被執(zhí)行，但是始終不會(huì)被記錄在過(guò)程日志中的任務(wù)。定義（隱含任務(wù)） 已知結(jié)構(gòu)化工作流網(wǎng)n（，），w=t*是其對(duì)應(yīng)的日志

8、。則稱tt是隱含任務(wù)，當(dāng)且僅當(dāng)不存在日志實(shí)例lw，使tl。n的全部隱含任務(wù)的集合記為h。隱含任務(wù)問(wèn)題的本質(zhì)是日志中的信息缺失。顯然，只有那些導(dǎo)致模型結(jié)構(gòu)出現(xiàn)缺陷的隱含任務(wù)才有可能被發(fā)現(xiàn)，其他隱含任務(wù)在不引入其他知識(shí)的條件下是無(wú)法通過(guò)日志分析的方法來(lái)發(fā)現(xiàn)的。例如，圖中的幾種隱含任務(wù)都不會(huì)導(dǎo)致挖掘模型出現(xiàn)結(jié)構(gòu)缺陷，都是無(wú)法被發(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)和

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ù)：隱含路徑型對(duì)應(yīng)于 算法中的和類型，是單獨(dú)組成過(guò)程中的某條執(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ù)的幾種情況，其中左邊是原始過(guò)程，右邊是用算法挖掘?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)的幾種情況，其中左邊是原始過(guò)程，右邊是用算法挖掘?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)缺陷。因此，通過(guò)檢測(cè)挖掘模型中的結(jié)構(gòu)缺陷，就能夠發(fā)現(xiàn)這些隱含任務(wù)的存在，并加以彌補(bǔ)。本文采用算法中次序關(guān)系作為檢測(cè)模型結(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)系，就可以針對(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)（，）

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ù)的檢測(cè)順序由于過(guò)程可能同時(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)的

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

18、提出了一種基于結(jié)構(gòu)化工作流網(wǎng)的挖掘算法，可以較好地挖掘包含隱含任務(wù)的結(jié)構(gòu)化工作流網(wǎng)過(guò)程日志，因此能夠更好地幫助用戶分析和理解過(guò)程執(zhí)行流結(jié)構(gòu)。作為一種自動(dòng)化的建模工具，該算法適用于需要應(yīng)用過(guò)程分析和建模的各類場(chǎng)合。本文通過(guò)實(shí)驗(yàn)評(píng)估驗(yàn)證了算法的可行性和有效性。接下來(lái)的研究方向是在現(xiàn)有算法的基礎(chǔ)上繼續(xù)深入擴(kuò)展其適用的建模語(yǔ)言圍，從而進(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