對(duì)工作流網(wǎng)的過(guò)程挖掘算法研究

摘要：過(guò)程挖掘主要是發(fā)現(xiàn)事件日志的有價(jià)值的客觀信息，對(duì)于它的研究為實(shí)施新的業(yè)務(wù)過(guò)程和對(duì)已實(shí)施的業(yè)務(wù)過(guò)程進(jìn)行分析改進(jìn)具有重要的作用，本文主要是基于工作流網(wǎng)，對(duì)于多事件類(lèi)型挖掘、間接依賴關(guān)系挖掘以及不可見(jiàn)任務(wù)挖掘及算法進(jìn)行的探討研究。

關(guān)鍵詞：工作流網(wǎng)；過(guò)程挖掘；算法

中圖分類(lèi)號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007—9599 （2012） 14—0000—02

一、過(guò)程挖掘

（一）過(guò)程挖掘算法

過(guò)程挖掘的主要思路是最早是新墨西哥州立大學(xué)的Cook教授等人提出的，他認(rèn)為：過(guò)程挖掘主要根據(jù)日志記錄中的過(guò)程實(shí)例來(lái)發(fā)現(xiàn)和執(zhí)行信息重構(gòu)工作流的過(guò)程模型。過(guò)程挖掘算法即過(guò)程挖掘是根據(jù)得到的執(zhí)行日志進(jìn)行工作的，過(guò)程日志是對(duì)一個(gè)個(gè)完整的事件的記錄，因此如果能夠找到一種算法對(duì)日志進(jìn)行分析，在軟件設(shè)計(jì)時(shí)就能夠直接依據(jù)過(guò)程運(yùn)行的記錄，客觀而真實(shí)地重現(xiàn)整個(gè)事件的過(guò)程，以此避免因管理者或者業(yè)務(wù)顧問(wèn)的主觀原因而造成軟件設(shè)計(jì)的失敗。他提出了根據(jù)記錄的活動(dòng)屬性自動(dòng)地發(fā)現(xiàn)事件活動(dòng)中的相互關(guān)聯(lián)，并提出了使用的方法，既通過(guò)純理論、純算法和理論和算法相結(jié)合的方法，以此對(duì)軟件的運(yùn)行過(guò)程進(jìn)行分析。其目標(biāo)是過(guò)程模型通過(guò)通過(guò)大量的后繼工作，在軟件過(guò)程的事件日志中國(guó)自動(dòng)的發(fā)現(xiàn)；算法是采用有限狀態(tài)自動(dòng)機(jī)來(lái)對(duì)過(guò)程模型進(jìn)行表達(dá)，并對(duì)并行結(jié)構(gòu)和噪聲進(jìn)行處理。

（二）過(guò)程挖掘工具

當(dāng)前存在很多的挖掘工具，有代表性的主要是挖掘工具Little Thumb，它是由荷蘭埃因霍溫理工大學(xué)的Van der Aalst教授等人提出的，這種工具能夠從不完全的工作流日志中以及包含噪聲的工作流日志中誘導(dǎo)出WF—net；還有后來(lái)提出的挖掘工具EMiT，該工具用α算法[44，45]的擴(kuò)展版本挖掘，對(duì)挖掘出的WF—net可以自動(dòng)布局；德國(guó)奧爾登堡大學(xué)的Schimm教授提出的能夠輸出塊結(jié)構(gòu)的過(guò)程模型的挖掘工具Process Miner；德國(guó)烏爾姆大學(xué)的Herbst等人提出的支持帶重名任務(wù)的過(guò)程模型挖掘的挖掘工具InWoLvE，以及以后出現(xiàn)的方便過(guò)程挖掘?qū)＜遗c挖掘算法進(jìn)行交互的挖掘工具ProTo。

二、多事件類(lèi)型挖掘

事件類(lèi)型在目前的過(guò)程挖掘技術(shù)中幾乎沒(méi)有被注意，普遍的將任務(wù)認(rèn)為是原子，或者僅僅關(guān)注兩種事件類(lèi)型開(kāi)始START、完成COMPLETE，然而對(duì)于這兩種事件的關(guān)系現(xiàn)有的算法也沒(méi)有給出解釋?zhuān)蚨鴮?duì)包含多事件類(lèi)型的日志進(jìn)行挖掘是很有必要的。

（一）日志分析

過(guò)程挖掘的主要內(nèi)容就是對(duì)任務(wù)間的次序關(guān)系進(jìn)行確定，因此對(duì)于多事件類(lèi)型的事件日志，就應(yīng)當(dāng)將同任務(wù)一次全部執(zhí)行的有關(guān)事件整體進(jìn)行考慮，即事件類(lèi)型STARTCOMPLETE。任務(wù)間的次序關(guān)系主要有兩種形式：一種是基本次序關(guān)系。對(duì)于一次任務(wù)的發(fā)生一般用帶有時(shí)刻的線段進(jìn)行表示，線段的左端點(diǎn)是事件類(lèi)型開(kāi)始START，其右端點(diǎn)是事件類(lèi)型完成COMPLETE，左右端點(diǎn)之間的部分代表正在執(zhí)行的任務(wù)，而線段的長(zhǎng)度表示任務(wù)的持續(xù)時(shí)間，以此就可以定義任務(wù)之間的相繼和相交等次序關(guān)系；第二種就是派生次序關(guān)系，其是用來(lái)產(chǎn)生模型中的如AND—join、AND—split、OR—join、OR—split和其各種組合等形成的典型路由結(jié)構(gòu)的。

（二）挖掘算法

首先對(duì)于事件日志中任務(wù)間的次序關(guān)系以及其與過(guò)程模型中連接庫(kù)所的對(duì)應(yīng)關(guān)系，主要通過(guò)運(yùn)用相關(guān)的定義和定理以及對(duì)其證明來(lái)進(jìn)行考察；再提出以WF—net表示的從日志構(gòu)造的過(guò)程模型的具體算法，稱(chēng)之為為β算法。β算法是通過(guò)某具體事件日志（W）來(lái)構(gòu)造一個(gè)WF—net，其表示形式為：NW = （PW，TW，F(xiàn)W）。在該算法中是比較簡(jiǎn)單的獲得TW、TI以及TO的，算法的前三步表明了日志大小或事件總數(shù)與時(shí)間復(fù)雜度是一種線性關(guān)系，步驟4和步驟5可以表示為O（kn3），即算法復(fù)雜度是任務(wù)數(shù)的指數(shù)次方，n代表的任務(wù)的個(gè)數(shù)，k表示庫(kù)所平均的輸入、輸出的總的任務(wù)個(gè)數(shù)，最壞情況為n，實(shí)際過(guò)程中的任務(wù)個(gè)數(shù)n一般不會(huì)超過(guò)100。最后三個(gè)步驟表明時(shí)間復(fù)雜度與結(jié)果模型的大小成正比。

（三）實(shí)驗(yàn)評(píng)估

β算法已經(jīng)實(shí)現(xiàn)在開(kāi)源過(guò)程挖掘框架ProM的挖掘插件Tsinghua—α中，其輸入以MXML格式的日志為標(biāo)準(zhǔn)，用戶能夠自行選擇同事件類(lèi)型相對(duì)應(yīng)的事件日志。對(duì)算法進(jìn)行評(píng)估的日志主要有三種來(lái)源：真實(shí)日志即從事務(wù)操作系統(tǒng)獲取的日志、根據(jù)給定的模型借助于仿真工具創(chuàng)建的日志以及手工創(chuàng)建的日志；返回的結(jié)果是WF—net表示的過(guò)程模型。

三、間接依賴關(guān)系的挖掘

在目前的過(guò)程挖掘領(lǐng)域中，從日志中發(fā)現(xiàn)任務(wù)間的間接依賴關(guān)系還是挑戰(zhàn)性的，間接依賴關(guān)系問(wèn)題同其他的過(guò)程建模語(yǔ)言存在差異，落實(shí)到WF—net上具體就體現(xiàn)為選擇與同步相混合的情況，即非自由選擇結(jié)構(gòu)，然而現(xiàn)有的方法仍然不能對(duì)類(lèi)似結(jié)構(gòu)進(jìn)行正確處理。

（一）對(duì)于間接依賴關(guān)系的檢測(cè)

為了能夠正確挖掘選擇與同步相混合情況下的WF—net，對(duì)于間接依賴關(guān)系的檢測(cè)是很重要的，為了從日志中檢測(cè)任務(wù)間的間接依賴關(guān)系，我們可以通過(guò)α算法對(duì)于如何發(fā)現(xiàn)間接依賴關(guān)系進(jìn)行研究。α算法以任務(wù)間的基本的次序關(guān)系和派生次序關(guān)系等作為其依據(jù)，只是依靠這兩種次序關(guān)系是很難發(fā)現(xiàn)間接依賴關(guān)系的，所以就有必要借助于比較復(fù)雜的次序關(guān)系來(lái)進(jìn)行檢測(cè)。為了使挖掘的準(zhǔn)確性得以提高，還必須保證對(duì)應(yīng)事件日志的質(zhì)量，盡管存在很多的次序關(guān)系，都可以從任務(wù)間的基本次序關(guān)系中>W派生出來(lái)，如→W、#W、║W等，其中║W具有特殊性，其體現(xiàn)了一切可能的間接依賴關(guān)系。

（二）挖掘算法

本部分將提出構(gòu)造最終WF—net的算法α++。該算法處理長(zhǎng)度為1的短循環(huán)，其過(guò)程模型較為復(fù)雜，它具有巨大的完備事件日志。α++算法主要由基本次序關(guān)系以及派生次序關(guān)系如→W、#W、║W來(lái)驅(qū)動(dòng)，影響這些關(guān)系構(gòu)建時(shí)間的主要因素是日志大小，它們之間是線性關(guān)系。另外α++算法所要求的完備性也是在要求這三種關(guān)系的完備性基礎(chǔ)上建立的，在事件日志中并不可能出現(xiàn)所有的事件軌跡；任務(wù)數(shù)也是影響α++算法的各個(gè)步驟所需時(shí)間的關(guān)鍵因素，一般情況下任務(wù)數(shù)的數(shù)量不會(huì)超過(guò)100，日志的大小不會(huì)影響該數(shù)量的大小，總的來(lái)說(shuō)該算法的復(fù)雜度不會(huì)對(duì)大規(guī)模應(yīng)用造成瓶頸，且現(xiàn)有的應(yīng)用領(lǐng)域?qū)τ谶^(guò)程挖掘算法的運(yùn)行時(shí)間并沒(méi)有提出相關(guān)的要求，相較于建模的時(shí)間耗費(fèi)，對(duì)日志進(jìn)行挖掘的時(shí)間要少的很多。

（三）算法實(shí)驗(yàn)評(píng)估

評(píng)估挖掘結(jié)果時(shí)主要使用兩個(gè)維度的符合性：合理性和合適性。合理性是對(duì)于過(guò)程行為與控制流是否相符合進(jìn)行的考察，合適性則是用來(lái)考察過(guò)程模型能否對(duì)被觀察過(guò)程進(jìn)行合適的描述。對(duì)于挖掘結(jié)果的評(píng)估可以采用可視的方式通過(guò)模型對(duì)比的方式來(lái)進(jìn)行考察，以此用于直觀的理解α++算法的正確性。

四、不可見(jiàn)任務(wù)的挖掘

對(duì)于不可見(jiàn)任務(wù)從事件日志中挖掘的問(wèn)題最早由van der Aalst等人指出，在任何日志軌跡中不出現(xiàn)不可見(jiàn)任務(wù)，所以其不能被直接的發(fā)現(xiàn)。不可見(jiàn)任務(wù)挖掘也是是過(guò)程挖掘領(lǐng)域中具有挑戰(zhàn)性問(wèn)題之一，對(duì)其研究在理論和實(shí)踐上具有重要的價(jià)值。

（一）分類(lèi)與檢測(cè)

不可見(jiàn)任務(wù)可以定義為其是過(guò)程模型的任務(wù)的集合，但不可見(jiàn)任務(wù)并不限定在某個(gè)特指的的建模語(yǔ)言所體現(xiàn)的過(guò)程模型中，其主要分為SKIP型、REDO型以及SWITCH型，它們具有類(lèi)似的結(jié)構(gòu)和行為，三者的檢測(cè)方法具有很大的相似性。

（二）挖掘算法

挖掘算法首先要明確不可任務(wù)的檢測(cè)順序，這些檢測(cè)方法的使用順序并不是任意的；其次構(gòu)造不可見(jiàn)任務(wù)，對(duì)于僅僅存在順序關(guān)系的過(guò)程模型，不可見(jiàn)任務(wù)與從虛假依賴構(gòu)造之間是相對(duì)應(yīng)的，然而實(shí)際的業(yè)務(wù)中都不可或缺的會(huì)包含選擇、并行等結(jié)構(gòu)，再者要構(gòu)造SIDE類(lèi)型和SKIP、REDO、SWITCH類(lèi)型，最后構(gòu)造最終模型的α#算法，其步驟是首先對(duì)于各種類(lèi)型的不可見(jiàn)任務(wù)通過(guò)ConIT算法來(lái)構(gòu)造，修正并確定他們的因果及并行的關(guān)系；其次要考慮長(zhǎng)為1的短循環(huán)任務(wù)以及不可見(jiàn)任務(wù)的前提下，構(gòu)造同所有可能庫(kù)所相對(duì)應(yīng)的任務(wù)集合；最后構(gòu)造相對(duì)應(yīng)的連接弧和相對(duì)應(yīng)的庫(kù)所，返回工作流網(wǎng)后，挖掘結(jié)果就是工作流網(wǎng)所體現(xiàn)的過(guò)程模型。

（三）實(shí)驗(yàn)評(píng)估

α#算法已經(jīng)作為插件實(shí)現(xiàn)在開(kāi)源的過(guò)程挖掘框架ProM中，ProM已是一個(gè)應(yīng)用普遍的的過(guò)程挖掘框架，其輸入以MXML格式的事件日志為標(biāo)準(zhǔn)，用戶能夠自行選擇過(guò)程挖掘插件，結(jié)合事件日志中挖掘出的過(guò)程模型，能夠以圖形的形式體現(xiàn)最終的結(jié)果，其具備了從完備的事件日志中檢測(cè)出包涵不可見(jiàn)任務(wù)的合理的WF—net的能力。

參考文獻(xiàn)：

[1]聞立杰.基于工作流網(wǎng)的過(guò)程挖掘算法研究[D].清華大學(xué)，2007

[2]劉新瑜，朱衛(wèi)東.基于過(guò)程挖掘的工作流性能分析[J].計(jì)算機(jī)應(yīng)用，2005，04

[3]馬輝，張凱.基于Petri網(wǎng)的工作流挖掘技術(shù)分析[J].計(jì)算機(jī)與現(xiàn)代化，2005，07