李 莉

(安徽理工大學數(shù)學與大數(shù)據(jù)學院，安徽 淮南 232001)

0 引 言

過程挖掘是工作流管理的一個子領域[1]。它在數(shù)據(jù)挖掘與業(yè)務流程管理的協(xié)同方面發(fā)揮著非常重要的作用，并極大地增強了商業(yè)智能技術(shù)。目前主要分為三種類型[2](1)發(fā)現(xiàn)：將事件日志作為輸入，并在不使用任何先驗信息的情況下生成模型，這是最突出的過程挖掘技術(shù)；(2)一致性檢查識別事件日志中記錄的現(xiàn)實是否符合模型，反之亦然；(3)增強：利用事件日志中記錄的實際過程執(zhí)行信息來擴展或改進現(xiàn)有的過程模型。

業(yè)務流程旨在實現(xiàn)某些目標，即流程目標。目標通常通過一些基本特征[3](例如它們的類型和屬性)以及它們與其他目標和需求模型的其他元素的鏈接來建模。Fani Sani[4]等人提出在過程發(fā)現(xiàn)中應用子組發(fā)現(xiàn)，并將案例的屬性作為子組分類的主要依據(jù)。Yukun Cao提出了一個屬性驅(qū)動的層次聚類框架[5]，可以在用戶指定的案例屬性的基礎上比較案例集之間的行為差異，結(jié)果表明從聚類的案例組中發(fā)現(xiàn)的模型比基于完整日志發(fā)現(xiàn)的模型具有更好的質(zhì)量。

本文的研究就是將過程發(fā)現(xiàn)和目標相結(jié)合，發(fā)現(xiàn)具有不同屬性案例的子目標。其余部分如下，第1節(jié)是相關的概念;第2節(jié)提出了子目標發(fā)現(xiàn)算法，并進行了詳細闡述;第3節(jié)是實驗部分;第4節(jié)是文章的總結(jié)和展望。

1 基本概念

定義1(事件日志)：A是活動的集合，一個事件日志是A上的序列的一個多集，即L∈M(A*)。σ∈A*是L中的一條跡。

定義2(跡和案例)C代表案例的集合，對于c∈C，存在一個映射函數(shù)πa:C→V,將案例的屬性值映射到案例上，πa(c)=v代表案例c中屬性a的值為v。

一個事件是一個活動的執(zhí)行，可以被定義為ε=I×C×E×R×T,其中I是事件標識符的集合，C是案例標識符的集合，E是活動的集合，R是資源的集合，T是時間戳的集合。

2 基于案例屬性和時間相關性發(fā)現(xiàn)子目標

2.1 基于案例屬性對案例進行分組

在許多案例中，一些案例子集存在偏差，這些偏差可能是由具有特定人群產(chǎn)生。比如在手機購票過程中，由于操作失誤而產(chǎn)生購票過程中斷現(xiàn)象的人群大多數(shù)都是比較年長的群體，導致購票失敗結(jié)果的各種操作則是需要改進的地方。在對不完整的案例進行研究時，首先將案例基于屬性分類，得到具有特定類別標簽的的子集。

子日志是基于所選案例的案例屬性值的分組，是一個非重疊的案例集，只包含一個案例屬性值。給定一個事件日志L，案例屬性a∈A，對于所有的子日志Lv∈P(L,a)?P(L)φ，ULv∈P(L,a)Lv=L,Lv是完整事件日志中屬性值為v的子日志，v∈V是案例屬性a的一組案例屬性值且?Lv≠Lv′∈P(L,a)，Lv∩Lv′=φ。

算法1實現(xiàn)了案例基于屬性的分組，首先將案例的屬性映射到集合中，選擇需要參照分組的的屬性，將屬性的取值范圍進行劃分，根據(jù)所選的屬性范圍劃分出不同的子組，具體的算法思想如下：

算法1 基于案例屬性的分類算法

Input:L,CBOutput:L1,…Li1 Function π∈(A→(C→UV))2 for all L ,c∈Cdo 3 πa(c)=v4 vi∈V5 ai∈A6 if πai(C)=vi and vi∈V then7 return Li8 i=i+19 endif10 repeat 11 return L1,…Li

在對案例進行基于屬性的分組后，得到具有特定屬性的子日志。對于分類后的子日志，可以應用各種過程挖掘算法發(fā)現(xiàn)子日志的主要流程模型，與原流程模型可能存在不同，存在原模型中缺失的活動。針對這些具有特定屬性的流程模型，無法確定模型中的子目標，就需要明確目標與子目標之間的時間相關性，從而確定子目標。

2.2 時間相關性

在事件日志挖掘過程中，目標和子目標之間存在時間相關性，我們可以從多層事件日志中挖掘目標的細化模式-子目標。通過時間戳屬性，可以看出在一系列的事件中，目標的實現(xiàn)在其子目標實現(xiàn)之后發(fā)生。

目標間的時間相關性模式：時間相關模式對子目標實現(xiàn)和父目標的實現(xiàn)施加時間約束，D為目標，d1…dn為子目標，d1…dn→D代表目標在所有子目標完成之后發(fā)生，目標和子目標之間存在順序相關性，要求每個子目標實現(xiàn)的時間間隔完全包含在父目標實現(xiàn)的時間間隔中。

2.2.1 事件發(fā)生的時間間隔

一個案例中有多條日志，對于案例中的每條日志，每個事件發(fā)生的時間間隔不是一個固定值，定義一條日志中事件發(fā)生的時間間隔為：

hk=sk+1-sk

其中，sk+1為日志中第(k+1)個活動發(fā)生的時間，sk為日志中第(k)個活動發(fā)生的時間。

2.2.2 事件持續(xù)時間

對于每個事件都有開始時間和結(jié)束時間，這種情況稱為事件持續(xù)時間，定義每個事件的持續(xù)時間為：

φk=fk-sk

其中，fk為日志中第(k)個活動結(jié)束的時間。

在一個活動周期中，假設正常情況下事件發(fā)生的時間間隔、事件持續(xù)時間、和該活動的截止時間戳分別用表示，可能的取值范圍為：

hk∈{hmin,…,hmax}

2.2.3 基于時間相關性判定子目標算法

在算法2中的輸入是基于屬性分類后的子日志，對于從子日志中挖掘出的過程模型，相比完整日志挖掘出的模型有相同點和不同點，導致子目標無法確定。需要保證子目標事件的發(fā)生是包含在一個完整的跡中的一部分，由此提出了算法2。

算法2 基于目標與子目標的時間相關性判定子目標

Input: L1,…LiOutput :ξ={d1…dn} 1 Function Time ( L,ξ)2 for ?Ek∈Li do3 if hk=sk+1-sk∈{hmin,…,hmax} then4 if φk=fk-sk<φd then5 if fk

算法2主要是應用了子目標與目標之間的時間相關性來判斷子目標，由于子目標的發(fā)生要滿足時間間隔在父目標實現(xiàn)的時間間隔中以及最終的活動時間戳之前兩個條件，符合這個區(qū)間的活動視為子目標。

3 實 驗

為了驗證提出的子目標的概念對過程挖掘模型精度的影響，在PROM框架中采用真實數(shù)據(jù)進行實驗對比。

3.1 實驗設置

采用事件日志集(receipt phase of an environmental permit application process)進行實驗，下表1是案例的詳細情況，每個案例的事件數(shù)(min=1,max=25),每個案例的事件類別(min=1,max=15)。選取案例的一個屬性(跡長度)作為研究的對象，將不同日志長度的案例進行分類，然后進行流程樹挖掘。

表1 receipt phase of an environmental permit application process

3.2 對比分析

由流程樹的結(jié)構(gòu)性質(zhì)，從圖1中可以看出流程主要分為7個部分，活動(T07-1 Draft intern advice aspect 1)是基于屬性進行過濾后的最后一個活動，根據(jù)子目標與目標發(fā)生的時間相關性，活動(T07-1 Draft intern advice aspect 1)可以作為案例的一個子目標進行研究。對完整的案例進行過濾操作，將活動(T07-1)作為最終的目標進行過程挖掘，挖掘出的結(jié)果如下圖3所示，可以看出與圖2中的流程樹具有不同的結(jié)構(gòu)層次。

圖1 折疊流程樹(1-5)

圖2 折疊流程樹(6-10)

圖3 以活動(T07-1)為結(jié)束活動的流程樹挖掘結(jié)果

對比圖3中挖掘出的流程樹模型與完整真實案例間的F-measure，通過計算得出F-measuresub≈0.99，F(xiàn)-measure=0.92

3.3 實驗總結(jié)

為了便于對比和分析，將合成數(shù)據(jù)以及真實案例中子目標對應的流程樹和原模型通過上述方法計算適合度、精確度以及F1-measure，具體的值如下圖4所示。

圖4 完整日志和子日志的F1-measure

通過對案例原始模型和對應子目標群體計算F-measure，完整的日志被分成多個子日志，從這些子日志中發(fā)現(xiàn)的模型只能捕獲完整日志的部分行為，因此圖4中子日志的流程樹模型的適合度降低，由于附加行為的減少，精確度提升。但是提出的基于屬性對日志進行劃分的方法提高了過程模型的質(zhì)量，得到的F-measure(sublog)大于原模型的值。

4 結(jié) 語

因為事件日志中可能包含不同特征的案例信息，將這些不同的案例放在一起分析可能會導致某些重要現(xiàn)象的丟失。為了解決這個問題，將案例中事件的屬性以及目標和子目標之間的時間相關性應用到過程發(fā)現(xiàn)中，提高了過程發(fā)現(xiàn)模型的整體質(zhì)量。

實驗是基于于跡的長度屬性進行分類，后續(xù)可以將事件類型和資源屬性添加進去考慮，可以使得案例分析更具有針對性，得出的優(yōu)化方案更加專業(yè)。