基于最優(yōu)近似跡的增量日志過程挖掘優(yōu)化方法

周衍志

（安徽理工大學，安徽 淮南 232001）

0 引言

過程挖掘是介于計算智能與數據挖掘、過程建模與分析之間的一門新興的學科［1］。過程挖掘的起點是事件日志。所有過程挖掘技術都假設可以順序記錄事件，使得每個事件都指向一個活動（即流程中定義良好的步驟），并且與特定情況（即流程實例）相關。事件日志可以存儲額外的信息，例如執(zhí)行或發(fā)起活動的資源（即人或設備）、事件的時間戳或與事件一起記錄的數據元素（例如命令的大?。?。事件日志可用于發(fā)現、監(jiān)視和改進基于事實而不是虛構的流程。過程挖掘主要有三種類型：獲取事件日志并生成模型而不使用任何其他先驗信息；將現有流程模型與同一流程的事件日志進行比較；采用事件日志和過程模型并使用觀察到的事件擴展或改進模型。

業(yè)務過程挖掘是實現業(yè)務過程自動化管理的途徑之一，用于實現業(yè)務過程的發(fā)現、監(jiān)控和改進。由于外部環(huán)境的影響和用戶的個性化需求，業(yè)務過程需要不斷變化，過程模型需要不斷地改進和更新，基于先前歷史事件日志的過程模型很難滿足更新后的業(yè)務過程。以目的指導作為每個特定流程模型創(chuàng)建的決定因素，這種建模方式的結果是，公司需要為同一過程創(chuàng)建不同的模型。這些模型駐留在不同的抽象層次上，并根據建模目標的適當程度，假設不同的建模視角，例如這些差異導致了眾所周知的“業(yè)務-IT差距”［2-3］。文獻［4］描述一個組織的運作過程和實際實施的模型之間的關系。調整業(yè)務流程以適應不斷變化的業(yè)務需求的靈活性是業(yè)務流程的核心。因此，變化在幾個相關的過程模型之間的傳播是模型對齊的主要用例［5］。Gartner 認為，變更與業(yè)務流程的關鍵要素高度相關，業(yè)務流程的關鍵要素是“使業(yè)務流程模型與流程執(zhí)行保持同步，使流程和底層系統(tǒng)能夠快速迭代以進行持續(xù)的流程改進和優(yōu)化”［6］。Logica 咨詢公司在最近的白皮書中公布的令人印象深刻的數字也說明了業(yè)務流程變化的重要性：“大多數歐洲公司將10%至55%的平均利潤率用于業(yè)務流程的改變”［7］。文獻［8］中提出了過程發(fā)現的α 算法。α是第一個過程發(fā)現算法，給定一個事件日志，通過算法可以發(fā)現一個過程模型，該過程模型只能夠重演給定的事件日志。基于這樣的局限性，文獻［9］提出了α+算法用于解決算法無法處理短循環(huán)的問題。文獻［10］中提出了一種具有完備性、精確性和簡單性的適應度函數的遺傳算法來發(fā)現模型中的頻繁行為，用以解決過去幾年中沒有算法能夠保證為所給定的日志找到完整、精確和簡單模型的問題。文獻［11］提出了一種啟發(fā)式的挖掘方法，該方法在構建過程模型時僅使用了因果網的結構，而且考慮到了事件和序列的頻率，該方法的目標是從一個事件日志中提取出一個因果網：首先，通過事件日志中活動之間的相互依賴關系與設定的閾值，構建相對應的依賴圖，從而得到不包含非頻繁行為的因果網。上述算法能夠很好地處理日志的挖掘問題，但是對于增量日志或所生成的模型具有很大的缺陷，原日志不能在生成的模型中重演，不能很好地在實際中運用。

為保證原系統(tǒng)主要行為在特征不變的前提下，盡可能根據增量日志更新業(yè)務流程，本文提出了基于最優(yōu)近似跡的增量日志過程挖掘優(yōu)化方法。首先基于串比較的思想在原日志中尋找與增量跡差異最小的最優(yōu)近似的初始跡，然后通過比對增量跡和最優(yōu)近似跡之間的差異確定最優(yōu)近似跡的變化位置，再根據最優(yōu)近似跡尋找原模型中對應的變化域，最后根據不同的變化類型分別采取不同的優(yōu)化方案，從而得到優(yōu)化之后的過程模型。實驗結果表明，該方法得到的過程模型能保持原系統(tǒng)的主要行為不發(fā)生改變，和初始過程模型具有較好的一致性度，有效地提高了模型的適合度，避免了重復挖掘問題。

1 研究背景

現實中由于用戶需求的不斷變化及各種外界因素的影響，業(yè)務流程常常會發(fā)生變化，因此可能會出現增加、刪除或者修改某些活動現象。下面給出初始日志和增量日志，初始事件日志為：

L1=［163，155，172，176，156，159，161，151，144，142，170，161］。增量日志為：

L2=［4，5］。

利用Alpha Miner+（α+挖掘）算法對日志L1進行挖掘得到模型M1，如圖1所示。

圖1 初始過程模型M1

顯然，此時L2中的跡無法在模型M1中進行重演，傳統(tǒng)的做法是合并日志L1和增量日志L2，然后利用過程挖掘算法對合并后的日志進行重新挖掘。再次利用α+挖掘算法對合并后的日志進行重新挖掘得到模型，如圖2所示。

圖2 合并日志L1 和L2 得到的模型M2

本文采用文獻［12］中的適合度計算方法，

其中，k 為給定日志的不同軌跡數，n 為日志軌跡中所含的數目，m 為日志軌跡中缺少的標識數，r為日志軌跡中遺留的標識數，c 為日志軌跡中消耗的標識數，p 為日志軌跡中產生的標識數。分別計算模型M1和模型M2的fitness，得到結果為過程模型M1的fitness=0.9945，過程模型M2的fitness=0.8723。通過M1和M2模型的適合度的對比發(fā)現，盡管僅在日志L1中添加了兩條不同的增量跡，但是挖掘得到的過程模型M2適合度顯然低于模型M1的適合度，而且模型M1和模型M2的一致性度很低，導致了原日志L1中很多跡不能再次在模型M2中重演，如，，等。此時繼續(xù)使用圖2 挖掘得到的模型作為最終的業(yè)務過程模型顯然是不合理的。

通過上述實例不難發(fā)現，在原有日志的基礎上添加新的變化日志（即使只包含很少的幾條變化跡），通過現有的挖掘算法對合并后的日志進行重新挖掘，會導致挖掘以后的更新模型和原模型的差異度很大、甚至會丟失原模型中的一些主要行為，更新后的模型適合度可能會大幅度降低。為了解決這樣的問題，本文提出了基于最優(yōu)近似跡的增量日志過程挖掘優(yōu)化方法，該方法能在盡可能保持原模型行為結構不變的情況下拓展新功能，使得優(yōu)化后的模型能更好地重演原日志和增量日志。

2 基礎知識

定義1［13］（過程模型）過程模型是一個元組P=(A,I,C,F,T)，其中：

A 作為活動節(jié)點的非空集，C 作為控制節(jié)點的集，A 和C 是不相交的，I ?A 作為一組初始活動，F ?(A ?C)×(AI ?C) 作 為 流 關 系，T:C →{and,or,xor}作為為控制節(jié)點分配類型的函數。

定義2［14］（行為輪廓）設(N,M0) 是一個網，初始狀態(tài)為M0，對任意的變遷對( t1,t2)∈(T×T )滿足下面關系：

1）若t1>t2且t2≯ t1，則稱變遷對(t1,t2)中的t1與t2為嚴格序關系，記作t1→t2；

2）若t1≯ t2且t2>t1，則稱變遷對(t1,t2)中的t1與t2為逆嚴格序關系，記作t1→-1t2；

3）若t1≯ t2且t2≯ t1，則稱變遷對(t1,t2)中的t1與t2為排他關系，記作t1+t2；

4）若t1>t2且t2>t1，則稱變遷對(t1,t2)中的t1與t2為交叉序關系，記作 t1‖t2；

5）將所有的關系集合稱為網系統(tǒng)的行為輪廓，記作BP={→,→-1,+,||}。

定義3［15］（日志跡、業(yè)務流程日志，L）A 是一組活動。 A* 表示A 上一組有限序列集，并且σ=a1a2…an∈ A*是一條日志跡。 L ∈( A*) 是一業(yè)務流程日志。‖ L‖ 表示一條日志跡中的活動數量。

定義4［16］（完整的業(yè)務流程日志）完整的業(yè)務流程日志是包含所有已執(zhí)行跡的日志。完整的業(yè)務流程日志用L*來表示，L*∈ *(A*) 。L ?L*。

定義5［17］（帶標簽的Peri 網）一個帶標簽的Petri網是一個4-元組N:=(P,T,F,λ)，其中(P,T,F)是一個Petri網，λ:T →A ?{τ} 是一個將標簽分配給變遷的函數。如果λ(t)≠ τ，則t 是可見的，否則，t 是不可見的或沉默的。

定義6［17］（活動對齊）一個網系統(tǒng)S:=(N,Nini,Mfin)一條跡υ ∈ A*與另一條跡υ′∈ A*′執(zhí)行活動σ 的對齊，其中N:=(P,T,F,λ) ，是S 上滿足π1(γ)|A=υ 和π2(γ)|T=σ 合法移動的有限序列

3 基于最優(yōu)近似跡的增量日志過程挖掘優(yōu)化方法

3.1 查找最優(yōu)近似跡

基于串首尾比較的思想，首先將原日志中的跡與增量日志中的跡分別從每條跡的開始活動逐個向后對齊以及從每條跡的結束活動逐個向前對齊，分別計算增量日志中的跡和原日志中的跡不對齊活動的數量所占比例，然后通過計算兩個情況的平均值得到兩條跡差異度。其中與增量日志中跡差異度最小的原日志中跡，即為最優(yōu)近似跡。算法實現如下：首先將原日志（Original Log）中每一條跡分別與增量日志（Incremental Log）中每條跡的初始變遷對齊，當增量日志中跡的活動與原日志中跡的活動tj相同，則對比差異值取0；若兩跡中活動不相同，則對比差異值取1。由于增量日志中的跡有對活動的增加或刪除等操作，使得原日志單條跡的活動數量||Original Log||與增量日志單條跡的活動數量||Incremental Log||存在差異，上述方法計算差異度時，沒有考慮跡長度不相等時的對比規(guī)則。基于此，對計算步驟進一步優(yōu)化，令Lo=||Original Log||，Li=||Incremental Log||，SSFromHead 函數用上述方式處理日志之后，獲取增量日志與原日志順序對齊之后的差異度。

函數SSFromHead 將原日志中跡與增量日志中跡從開始活動逐個向后對齊，計算原日志與增量日志的差異度DDS′。其中Original Log 表示原日志，Incremental Log 表示增量日志，函數執(zhí)行時，將原日志中每條跡分別與增量日志的初始變遷對齊，依次向后，當原跡的變遷與增量日志跡的變遷相同時，返回值0；若變遷不相同，返回值1；兩條跡中任意一條跡中出現無活動比較時，比較操作終止。此時兩條跡活動數量求差的絕對值，與所有對比返回的值求和，然后除以增量日志跡的長度，得到的結果即為該原日志跡與增量日志跡的差異度。

同時，基于數據結構串比對的思想，將原日志中的跡序與增量日志中的跡結束活動對齊，對齊之后序列使用SSFromEnd 函數處理對齊日志，獲取增量日志跡與原日志跡結束活動對齊的差異度DDS″。

function SSFromEnd(Lo,Li,Original Log,Incremental Log)

OLi?Original Log∧

ILi?Incremental Log∧

tj∈OLi∧t′

j∈ILi∧

m=min{Li,Lo}∧

ML=|Li-Lo|}

return…,

end function

求得原日志與增量日志所有跡對比差異度之后，將起始活動對齊求得的差異度與結束活動對齊求得的差異度取平均值，作為最終原日志跡與增量日志跡的差異度。從最終的差異度中找到最小的值，即可獲得原日志中與增量日志差異度最小的日志。

functionFLSe arch(

Lo,Li,Original Log,Incremental Log

)

FinalLog←{OringalLogt|t∈(1,n)∧

DDSt?min{DDS1,…,DDSn}

returnFinalLog

end function

3.2 基于增量日志的變化類型優(yōu)化過程模型

上文算法1求得了在原日志中與增量日志差異度最小的跡。在此基礎上，首先通過比對增量跡和最優(yōu)近似跡之間的差異確定最優(yōu)近似跡的變化位置，再根據最優(yōu)近似跡尋找原模型中對應的變化域，最后，根據不同的變化類型分別采取不同的優(yōu)化方案，從而得到了優(yōu)化之后的過程模型。

下面給出常見的變化類型，并針對不同的變化類型提出了不同的優(yōu)化方案，這些優(yōu)化方案保證了變化域的原行為不變。

圖3 修復操作規(guī)則

圖3 中的修復操作在保證源模型中活動行為不變的前提下，進一步拓展了新的業(yè)務流程，達到了對源模型修復的目的，有效地避免了重復挖掘增量日志的低效問題，保證了源模型的主要行為不會丟失。

算法:String Comparison Algorithm

輸入：原日志，增量日志

輸出：可重演原日志以及增量日志的模型

Step1 根據給定的所有原事件日志L1，使用prom 工具的α+插件分析各個變遷的行為輪廓關系，建立初始的Petri網過程模型M1。

Step2 將原日志L1與增量日志L2輸入算法l（Find the optimal approximation trace algorithm），求得原日志L1中與增量日志L2中相似度最高的跡τx。

Step3 從Step1 已建立的初始過程模型M1中取出跡τx的子模塊M2。根據τx模塊中的變遷表現得到行為關系，建立增量日志L2的過程模型M3。

Step4 對比模型M2與模型M3，引入靜默變遷，基于約定的模型修復規(guī)則，使得模型M2優(yōu)化后的日志L2可以在優(yōu)化后的模型M4中重演。

Step5 用模型M4替換子模塊M2，得到最終的過程模型M5。

Step6 輸出最后的過程模型M5，即為優(yōu)化后的過程模型，算法結束。

4 實例分析

以上述增量日志為例來驗證所提算法String Comparison Algorithm的可行性。。如圖4 所示，圖中Ⅰ為日志L2中跡τ′1，Ⅱ、Ⅲ、Ⅳ分別為日志L1中跡τ2、跡τ3和跡τ4。算法String Comparison Algorithm運行時，將跡如圖所示依次頭尾對齊，如果對齊跡的活動相同，權值取0；如果對齊跡的活動不相同，權值取1。將對比所得到的跡的權值進行求和，得到L1中跡τ2、跡τ3和跡τ4與L2中跡τ′1對比的權值。計算圖4中（a）（b）（c）的差異度：

圖4 求差異度過程圖

根據求出的差異度，繼而求出差異值最小的跡。得到跡和為所求跡，從圖1的模型中將跡和的模型取出，如圖5 中Ⅱ所示，對比該模型，對跡建?？梢缘玫饺鐖D5中Ⅲ所示模型，基于圖3的模型變化方法，得到如圖5所示的模型變化。

圖5 模型變化執(zhí)行過程

圖5中，模型Ⅰ為傳統(tǒng)α+算法將原日志與增量日志合并后挖掘的模型中增量日志的子模塊。模型Ⅲ與模型Ⅰ對比，不僅增量日志可以在模型Ⅰ中重演，原日志中的跡也可以在模型中重演。將該變化帶入源模型，得到如圖6 所示的變化后模型M3。

圖6 變化后模型M3

相較于圖2所示的Prom插件挖掘模型，使用算法String Comparison Algorithm 求得原日志與增量日志差異度最小的跡，并基于約定的修復規(guī)則修復模型，加入靜默變遷的使用，使得原日志L1中的跡可以在圖6 模型中重演。經計算得該模型Fitness=0.9947，此模型能極大程度上表達日志L1與日志L2中的過程，可作為當前項目實施過程模型。

5 總結

本文在已有研究的基礎上，給出了基于日志變化的模型變化的方法。在Prom 軟件中使用Alpha Miner+插件獲得當前日志序列過程模型。經分析發(fā)現，使用上述插件當日志發(fā)生變化時無法產生與變化后日志相符合的模型，由此提出算法String Comparison Algorithm，先求出原日志跡與增量日志跡起始活動對齊時的差異值，再求出原日志跡與增量日志跡結束活動對齊時差異值，繼而獲得與增量日志差異值最小的原日志跡。基于約定的模型修復規(guī)則，對所求日志模型進行修復，最后將該模型發(fā)生的變化映射到原日志模型，確定變化后的過程模型。經檢驗，原日志的跡可以在得到的過程模型中進行重演。