王燊

摘 要：文章首先分析工作流網(wǎng)中隱含任務(wù)可能出現(xiàn)的情況，基于α算法，提出在噪聲環(huán)境下能發(fā)現(xiàn)隱含任務(wù)的改進(jìn)α算法。該算法利用依賴/頻率表確定日志中任務(wù)間依賴關(guān)系并判斷是否存在隱含任務(wù)，向工作流網(wǎng)中添加隱含任務(wù)，通過對(duì)隱含任務(wù)合并、去冗操作完善工作流網(wǎng)。最后，用一個(gè)案例對(duì)改進(jìn)算法進(jìn)行驗(yàn)證。

關(guān)鍵詞：工作流網(wǎng)；依賴/頻率表；工作流日志；隱含任務(wù)

工作流是一類能夠完全或是部分自動(dòng)執(zhí)行的經(jīng)營(yíng)過程，它定義任務(wù)間相互關(guān)系來完成業(yè)務(wù)流程的自動(dòng)化執(zhí)行和管理。工作流挖掘是一種自動(dòng)化的過程分析技術(shù)，從流程日志中自動(dòng)獲得有價(jià)值的信息，建立工作流模型，使得所建模型可以重現(xiàn)原始工作流網(wǎng)。

對(duì)含有隱含任務(wù)、噪音數(shù)據(jù)等不完整日志的挖掘是當(dāng)今面臨的難題之一。大部分不完整日志都是由于含有隱含任務(wù)造成的，現(xiàn)有的大多掘算法在挖掘隱含任務(wù)時(shí)都不能得到正確的模型。少數(shù)幾個(gè)能解決隱含任務(wù)的算法，如算法、基因算法都只是能挖掘部分結(jié)構(gòu)的隱含任務(wù)，并不能解決全部的隱含任務(wù)問題。

1 研究現(xiàn)狀

在文獻(xiàn)[1]中，Agrawal等人最早提出利用工作流管理系統(tǒng)日志挖掘工作流模型。Herbest提出一種基于ADONIS模型的算法，該算法可以挖掘并行結(jié)構(gòu)、選擇結(jié)構(gòu)，但是該算法不能檢測(cè)隱含的結(jié)構(gòu)，而且對(duì)循環(huán)結(jié)構(gòu)的發(fā)現(xiàn)能力也是非常有限的。

隱含任務(wù)是指存在于業(yè)務(wù)流程中但不存在于流程日志中的任務(wù)，因?yàn)樗鼈儾淮嬖谟诹鞒倘罩局?，所以非常難被挖掘。國(guó)外學(xué)者Aalst對(duì)隱含任務(wù)的挖掘作了大量研究工作，他提出一種#α算法，可以在DIWF-nets中很好的發(fā)現(xiàn)隱含任務(wù)，但是該算法仍然存在問題，例如算法的挖掘效率不高等。

2 相關(guān)技術(shù)

Petri網(wǎng)為工作流建模提供了形式化的方法和分析技術(shù)。由Aalst引入工作流建模的Petri網(wǎng)稱工作流網(wǎng)，它是Petri網(wǎng)的一個(gè)子集。

定義6（隱含任務(wù)）隱含任務(wù)是指存在于業(yè)務(wù)流程中但不存在于流程日志中的任務(wù)，在流程中僅僅起到路由作用的任務(wù)，目的是為了真實(shí)任務(wù)的并行執(zhí)行。

工作流挖掘中一般認(rèn)為所有信息都會(huì)記錄在日志中，其實(shí)不然，隱含任務(wù)就沒有在日志中出現(xiàn)。導(dǎo)致隱含任務(wù)產(chǎn)生的情況有2種：（1）日志記錄的過程中有噪聲或信息的錯(cuò)誤丟失。（2）任務(wù)在日志中沒有被記錄，比如只作為路由的任務(wù)，如圖1所示（陰影是隱含任務(wù)）。圖中隱含任務(wù)的加入僅是因?yàn)槁酚蛇x擇的需要，并不對(duì)應(yīng)具體的工作。其作用是為了B和D，E和F并行執(zhí)行。

如果不考慮流程中隱含任務(wù)的作用，那么挖掘出來的結(jié)果模型可能不會(huì)符合日志所記錄的流程行為，導(dǎo)致挖掘結(jié)果不正確。

[參考文獻(xiàn)]

[1]Agrawal R，Gunopulos D，Leymann F.Mining process models from workflow logs[C]//Proceedings of the 16th.International Conference of Extending Database Technology.Valencia，Spain，1998.

[2]馬慧，湯庸，吳凌坤.α_H算法：工作流挖掘中一種能挖掘隱含任務(wù)的擴(kuò)展α算法[J].計(jì)算機(jī)科學(xué)，2011（4）：221-225.

[3]吳建強(qiáng).噪聲環(huán)境下工作流挖掘算法研究[D].廣州：華南理工大學(xué)，2012.

Exploration on Implicit Task in the Workflow Mining

Wang Shen

（Beifang University of Nationalities， Yinchuan 750021， China）

Abstract： First， by analyzing the situations where a hidden task may appear in the WF-Net，a new α#-algorithm- based om αalgorithmis proposed to find the hidden tasks under the noise environment.Using the dependence-frequency table，It ascertains the dependencies between tasks in logs and determines if there are hidden tasks ，then inserts hidden tasks in the WF-Net. To perfect the WF-Net，it merges and removes the hidden tasks. Last，a case is presented to verify theα#-algorithm.

Key words： WF-Net； dependence-frequency table；logs of workflow； hidden tasks