基于案例屬性的子目標(biāo)挖掘方法①

李 莉

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

0 引 言

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

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

本文的研究就是將過程發(fā)現(xiàn)和目標(biāo)相結(jié)合，發(fā)現(xiàn)具有不同屬性案例的子目標(biāo)。其余部分如下，第1節(jié)是相關(guān)的概念;第2節(jié)提出了子目標(biāo)發(fā)現(xiàn)算法，并進(jìn)行了詳細(xì)闡述;第3節(jié)是實(shí)驗(yàn)部分;第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是事件標(biāo)識符的集合，C是案例標(biāo)識符的集合，E是活動的集合，R是資源的集合，T是時間戳的集合。

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

2.1 基于案例屬性對案例進(jìn)行分組

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

子日志是基于所選案例的案例屬性值的分組，是一個非重疊的案例集，只包含一個案例屬性值。給定一個事件日志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實(shí)現(xiàn)了案例基于屬性的分組，首先將案例的屬性映射到集合中，選擇需要參照分組的的屬性，將屬性的取值范圍進(jì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

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

2.2 時間相關(guān)性

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

目標(biāo)間的時間相關(guān)性模式：時間相關(guān)模式對子目標(biāo)實(shí)現(xiàn)和父目標(biāo)的實(shí)現(xiàn)施加時間約束，D為目標(biāo)，d1…dn為子目標(biāo)，d1…dn→D代表目標(biāo)在所有子目標(biāo)完成之后發(fā)生，目標(biāo)和子目標(biāo)之間存在順序相關(guān)性，要求每個子目標(biāo)實(shí)現(xiàn)的時間間隔完全包含在父目標(biāo)實(shí)現(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é)束的時間。

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

hk∈{hmin,…,hmax}

2.2.3 基于時間相關(guān)性判定子目標(biāo)算法

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

算法2 基于目標(biāo)與子目標(biāo)的時間相關(guān)性判定子目標(biāo)

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主要是應(yīng)用了子目標(biāo)與目標(biāo)之間的時間相關(guān)性來判斷子目標(biāo)，由于子目標(biāo)的發(fā)生要滿足時間間隔在父目標(biāo)實(shí)現(xiàn)的時間間隔中以及最終的活動時間戳之前兩個條件，符合這個區(qū)間的活動視為子目標(biāo)。

3 實(shí) 驗(yàn)

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

3.1 實(shí)驗(yàn)設(shè)置

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

表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ìn)行過濾后的最后一個活動，根據(jù)子目標(biāo)與目標(biāo)發(fā)生的時間相關(guān)性，活動(T07-1 Draft intern advice aspect 1)可以作為案例的一個子目標(biāo)進(jìn)行研究。對完整的案例進(jìn)行過濾操作，將活動(T07-1)作為最終的目標(biāo)進(jìn)行過程挖掘，挖掘出的結(jié)果如下圖3所示，可以看出與圖2中的流程樹具有不同的結(jié)構(gòu)層次。

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

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

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

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

3.3 實(shí)驗(yàn)總結(jié)

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

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

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

4 結(jié) 語

因?yàn)槭录罩局锌赡馨煌卣鞯陌咐畔ⅲ瑢⑦@些不同的案例放在一起分析可能會導(dǎo)致某些重要現(xiàn)象的丟失。為了解決這個問題，將案例中事件的屬性以及目標(biāo)和子目標(biāo)之間的時間相關(guān)性應(yīng)用到過程發(fā)現(xiàn)中，提高了過程發(fā)現(xiàn)模型的整體質(zhì)量。

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