支持業(yè)務(wù)流程建模的塊結(jié)構(gòu)流程挖掘技術(shù)的研究.pdf

1、隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展,企業(yè)、機(jī)構(gòu)需要順應(yīng)市場(chǎng)需求的變化,隨時(shí)快速調(diào)整業(yè)務(wù),提高應(yīng)對(duì)市場(chǎng)變化的快速反應(yīng)能力。因此企業(yè)的信息系統(tǒng)中支持業(yè)務(wù)運(yùn)行的業(yè)務(wù)流程部分需要再造或優(yōu)化,而流程的再造或優(yōu)化首先需要理解當(dāng)前業(yè)務(wù)流程運(yùn)行的模式。目前,業(yè)務(wù)流程運(yùn)行模式的提煉主要依賴(lài)技術(shù)人員與業(yè)務(wù)人員的溝通,其所得結(jié)果有很強(qiáng)的主觀性,缺乏整體、完善性,且時(shí)間成本高、效率低。目前,大多數(shù)企業(yè)的信息系統(tǒng)管理應(yīng)用軟件,無(wú)論提供或不提供顯式的流程,這些軟件都提供企業(yè)實(shí)際業(yè)

2、務(wù)執(zhí)行的記錄,即流程日志。如何分析這些日志數(shù)據(jù),從中找出業(yè)務(wù)流程運(yùn)行的模式,用于快速的流程再造和柔性管理是迫切需要解決的問(wèn)題,而流程日志中抽取的業(yè)務(wù)流程模型,可以真實(shí)反映企業(yè)業(yè)務(wù)流程的執(zhí)行,支持業(yè)務(wù)流程再造或優(yōu)化的快速建模。
　　 本文研究的基礎(chǔ)--簡(jiǎn)單格式的流程日志并不是僅僅局限于工作流管理系統(tǒng)所提供,目前公司、機(jī)構(gòu)的信息系統(tǒng),它們的事務(wù)系統(tǒng),如ERP、CRM、B2B、SCM等都提供本文研究所需的簡(jiǎn)單格式的日志信息。也就是說(shuō),

3、只需要收集記錄了業(yè)務(wù)流程中各個(gè)任務(wù)活動(dòng)發(fā)生的順序序列,即流程日志。流程日志記錄了業(yè)務(wù)流程執(zhí)行的真實(shí)情況,從中挖掘出業(yè)務(wù)流程模式更加可信易讀。
　　 因?yàn)榱鞒棠Ｐ偷慕Y(jié)構(gòu)往往比較復(fù)雜,存在循環(huán)、并行、選擇、非自由選擇等難以表述清楚的塊結(jié)構(gòu),現(xiàn)有文獻(xiàn)的挖掘方法對(duì)這些結(jié)果的處理不理想,如循環(huán)結(jié)構(gòu)、非自由選擇結(jié)構(gòu)等,目前沒(méi)有普適的處理方法解決這些問(wèn)題。
　　 此外,利用流程日志中的時(shí)間信息可以挖掘到更精確的活動(dòng)邏輯關(guān)系并計(jì)算流程工

4、作的性能,但是大多數(shù)的流程挖掘方法并沒(méi)有充分利用日志中的時(shí)間信息。
　　 本文主要是深入研究并提煉給出了流程挖掘概念、流程日志的數(shù)學(xué)表示、流程模型的Petri網(wǎng)表示及結(jié)構(gòu)化工作流網(wǎng)概念,并給出相關(guān)的數(shù)學(xué)描述以及定義。在此基礎(chǔ)上的研究工作主要有以下三個(gè)方面的貢獻(xiàn):
　　 第一,目前,企業(yè)應(yīng)用系統(tǒng)軟件沒(méi)有統(tǒng)一的流程日志規(guī)范標(biāo)準(zhǔn),日志格式分為兩類(lèi):無(wú)時(shí)間標(biāo)志型日志和有時(shí)間標(biāo)志型日志且一般原始日志帶有噪音。針對(duì)無(wú)時(shí)間標(biāo)志型日志,

5、采用多步抽取模型方法,提出了一種基于簡(jiǎn)單流程日志格式的塊結(jié)構(gòu)挖掘方法BRC(Block_Structure Replace Compression:BRC),挖掘任務(wù)之間的邏輯關(guān)系,用于構(gòu)建日志所反映的業(yè)務(wù)流程模型。
　　 基本塊結(jié)構(gòu)對(duì)應(yīng)于四種結(jié)構(gòu)即順序、并行、選擇和循環(huán)結(jié)構(gòu)。方法首先定義了能夠被挖掘的流程的基本要求,即結(jié)構(gòu)化流程模型。方法的基本思想是在對(duì)四種基本結(jié)構(gòu)進(jìn)行分析的基礎(chǔ)上,從日志中找出具有這些結(jié)構(gòu)的模塊,并用結(jié)點(diǎn)來(lái)替

6、換每個(gè)模塊。通過(guò)循環(huán)使用四種模塊挖掘算法從日志中挖掘和替換,使得日志不斷收縮。如果最后得到的日志是一個(gè)點(diǎn),則只需進(jìn)行一次逆變換,即將前面得到的模塊按照相反的順序依次代入到流程模型中,這樣得到一個(gè)容易理解的基于工作流網(wǎng)的WF網(wǎng)模型。同時(shí),證明用該種方法得到的工作流網(wǎng)是合理的,安全的。在對(duì)順序任務(wù)和選擇任務(wù)進(jìn)行挖掘的過(guò)程中,考慮到來(lái)自其他并行任務(wù)的干擾,BRC提出并采用了并行任務(wù)等價(jià)類(lèi)概念,即首先從日志中劃分出并行任務(wù)等價(jià)類(lèi),再依次搜索各等

7、價(jià)類(lèi),挖掘出其中的順序和選擇任務(wù),從而很好地解決了并行任務(wù)對(duì)結(jié)構(gòu)化挖掘的干擾問(wèn)題。通過(guò)生成和運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù),對(duì)BRC方法的挖掘質(zhì)量進(jìn)行了檢驗(yàn)分析,證明該方法在復(fù)雜流程的挖掘方面具有明顯優(yōu)勢(shì)。討論了帶噪音的因果關(guān)系挖掘、帶噪音的并行關(guān)系挖掘、帶噪音的選擇結(jié)構(gòu)的挖掘,并給出了帶噪音處理的改進(jìn)型結(jié)構(gòu)化挖掘算法。
　　 第二,無(wú)時(shí)間標(biāo)志型日志中并行關(guān)系的挖掘是相對(duì)困難且計(jì)算量較大,針對(duì)有時(shí)間標(biāo)志型日志,提出了一種基于時(shí)間間隔的簡(jiǎn)

8、單流程日志格式的挖掘方法,用于構(gòu)建日志所反映的業(yè)務(wù)流程模型。
　　 方法的基本思想不同于事件模型類(lèi)思想,在事件挖掘類(lèi)中,把一個(gè)任務(wù)的執(zhí)行看作是不可分割的,是一個(gè)原子性事件。而從基于時(shí)間間隔日志的流程挖掘方法解決方案看,每一個(gè)任務(wù)的執(zhí)行都具有一個(gè)時(shí)間間隔,即任務(wù)的開(kāi)始事件和任務(wù)的結(jié)束事件?？梢栽偻卣惯@個(gè)模型成為捕獲更精確的模型視圖,在其中,執(zhí)行活動(dòng)是一個(gè)沿著時(shí)間軸的時(shí)間間隔,并且兩個(gè)間隔可以互相交叉。間隔方法分為兩大步驟:(1):

9、產(chǎn)生流程執(zhí)行圖。針對(duì)每一執(zhí)行產(chǎn)生一個(gè)DAG圖。在單個(gè)執(zhí)行中的間隔交叉使得此DAG圖易于對(duì)并行關(guān)系的挖掘,對(duì)具有同樣活動(dòng)集合的執(zhí)行圖進(jìn)行合并產(chǎn)生單個(gè)DAG圖；(2)合并流程執(zhí)行圖。對(duì)于流程圖的一個(gè)子圖,各個(gè)運(yùn)行于其上的執(zhí)行覆蓋相同的活動(dòng)集合,也就是業(yè)務(wù)流程中使用不同的參數(shù)來(lái)選擇合作伙伴的有向邊是一樣的。因此合并結(jié)果所產(chǎn)生的DAG圖就是流程的控制流圖。方法通過(guò)合并各個(gè)依賴(lài)于日志的DAG圖,產(chǎn)生現(xiàn)實(shí)意義上的流程模型圖。驗(yàn)證對(duì)比了兩類(lèi)算法:間隔

10、算法和非間隔算法。得出了有意義的一些結(jié)論,如丟失邊或多余邊與流程日志規(guī)模之間的關(guān)系等。
　　 第三,針對(duì)一般情況下,流程日志帶有噪音且是不完備的,探討分析了噪音情況,給出了日志中任務(wù)邏輯關(guān)系挖掘方法。方法中定義了一個(gè)概念:順序關(guān)系。該關(guān)系是基于START和COMPLETE這兩種事件類(lèi)型和它們的時(shí)間戳的。隨后給出順序關(guān)系的度量方法。提出了一個(gè)挖掘流程模型圖的方法,源流程模型可以包括所有的基本塊結(jié)構(gòu)和非自由選擇結(jié)構(gòu)。
　　

11、提出的方法使用具有時(shí)間戳的任務(wù)狀態(tài)流程日志,利用時(shí)間信息,比如活動(dòng)的平均等待時(shí)間、平均執(zhí)行時(shí)間去挖掘流程模型。在挖掘流程模型時(shí),首先通過(guò)掃描一次日志,為每一個(gè)任務(wù)構(gòu)建平均值表:然后在平均值表的基礎(chǔ)上分兩步執(zhí)行:第一步是挖掘基本的結(jié)構(gòu),比如順序路由、并行路由、選擇和循環(huán)路由；第二步是分析流程模型的高級(jí)結(jié)構(gòu),如或連接結(jié)構(gòu)。通過(guò)以上兩步,能挖掘出預(yù)期的流程模型。另外使用算法進(jìn)行挖掘的時(shí)候,去除噪音問(wèn)題通過(guò)觀測(cè)起始值來(lái)決定。最后對(duì)提出的挖掘算法

12、和文獻(xiàn)中已經(jīng)提到的算法做了比較,得出的結(jié)論是:TWM能挖掘α算法所挖掘的所有流程,然而,α算法不能挖掘TWM能挖掘的所有的流程,TWM和α算法在時(shí)間復(fù)雜度方面是等同的。另外,提出的算法對(duì)解決隱藏任務(wù)挖掘提供了有用的信息。
　　 此外,研究工作中,實(shí)現(xiàn)了一個(gè)支持流程挖掘算法的原型系統(tǒng)。設(shè)計(jì)此系統(tǒng)的目的主要是:(1)驗(yàn)證α算法的有效性:(2)以此和我們所提方法算法進(jìn)行有意義的比較,獲得有效的可信度；(3)驗(yàn)證針對(duì)復(fù)雜變異結(jié)構(gòu)流程,α