基于日志活動捆綁挖掘隱變遷

胡玉倩 方賢文

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

流程挖掘是指利用過程挖掘技術(shù)將事件數(shù)據(jù)轉(zhuǎn)化為有價值的可操作知識，主要以流程模型的形式重構(gòu)業(yè)務(wù)流程的基礎(chǔ)結(jié)構(gòu)。隱變遷是指在模型中能夠看到但在日志中看不到的活動，對隱變遷的挖掘有利于增強(qiáng)流程模型的描述性。流程增強(qiáng)是指通過挖掘隱變遷來增強(qiáng)流程模型，從而能夠更好地描述流程執(zhí)行期間得到的事件日志跡集。本次研究將討論一種通過流程來挖掘隱變遷的方法，該方法主要分為2個階段：第一階段，利用事件日志中的高頻日志生成初始流程模型；第二階段，采用松弛的思路，基于高頻日志與初始模型行為子集的整體近似適合度及其上下界過濾掉最可能是噪聲的低頻日志，再利用余下的低頻日志來修復(fù)模型，最后挖掘出初始模型未曾包含的隱變遷路徑。

1 問題的描述

通過流程挖掘得到的流程模型可能會誤將有效的低頻信息忽略掉，導(dǎo)致日志信息不準(zhǔn)確，因此需要對日志進(jìn)行預(yù)處理或?qū)α鞒棠Ｐ瓦M(jìn)行增強(qiáng)。日志預(yù)處理中，一般直接對日志進(jìn)行過濾。模型增強(qiáng)，一般通過日志對模型進(jìn)行修復(fù)。隱變遷的挖掘，實質(zhì)上就是利用日志活動間的依賴關(guān)系將合理的隱變遷挖掘出來，以增強(qiáng)模型的描述性。

傳統(tǒng)的挖掘方法，通常是完全將低頻日志視為噪聲，或者根據(jù)挖掘需要去過濾可能存在的噪聲。這些傳統(tǒng)方法并不能完全適用于所有場景。文獻(xiàn)[1]中，將事件標(biāo)簽之間的不頻繁直接依賴關(guān)系作為不頻繁行為的代理，從事件日志構(gòu)建的自動機(jī)中檢測并刪除這些依賴項，然后通過基于對齊的重放刪除單個事件更新原始日志。此方法不能用于處理缺少事件的日志，并且直接刪除的只是不頻繁行為，而這些不頻繁行為不一定都是無效的。文獻(xiàn)[2]中，提出了一種新的令牌重放方法，改進(jìn)了基于令牌重放的操作執(zhí)行時間，提高了基于令牌重放和對齊的性能，能夠管理令牌泛濫的問題。但是，此方法并不能解決活動終止的問題，也不能保證較高的適合度。

2 基本理論

事件日志是過程挖掘的起點。過程模型可描述特定的事件類型，例如保險索賠、客戶訂單或患者的生命周期等。一個事件可以是一個案例，也可以是一類活動，與特定情況的所有事件序列相對應(yīng)[3]。

事件日志是跡的多重集，其中可以包含多個具有相同跡的案例。如果跡的頻率無關(guān)緊要，則將日志引用為一組跡：L={l1，…，ln}。在事件日志的簡單定義中，如果一個事件完全通過活動來描述，則無法區(qū)分具有相同跡的不同案例。

在本次研究中，系統(tǒng)網(wǎng)使用標(biāo)簽Petri網(wǎng)描述流程，然后將這些概念提升到有標(biāo)簽的變體中[4]。

定義2 (Petri網(wǎng))一個Petri網(wǎng)(P，T，F(xiàn))由庫所集P，與P不相交的變遷集T，以及一組流弧F?(P×T)∪(T×P)組成。系統(tǒng)網(wǎng)N的標(biāo)識m給每個庫所p∈P分配一個托肯自然數(shù)m(p)。系統(tǒng)網(wǎng)N=(P，T，F(xiàn)，m0，mf),是一個初始標(biāo)識為m0、終止標(biāo)識為mf的Petri網(wǎng)(P，T，F(xiàn))。

在此，將y的前集和后集分別寫作?y：={x|(x，y)∈F}和y?：={x|(y，x)∈F}。 初始標(biāo)識為[p0]，終止標(biāo)識為[p6]的簡單網(wǎng)系統(tǒng)N1，將N1作為運行示例。

Petri網(wǎng)的變遷可以用出自字母表Σ的字母名稱來標(biāo)記，如假設(shè)標(biāo)簽τ∈Σ代表一個不可見的動作。標(biāo)簽Petri網(wǎng)(P，T，F(xiàn)，l)，是一個標(biāo)簽函數(shù)為l：T→Σ的Petri網(wǎng)(P，T，F(xiàn))。標(biāo)簽網(wǎng)系統(tǒng)N=(P，T，F(xiàn)，l，m0，mf)，是一個初始標(biāo)識為m0、終止標(biāo)識為mf的標(biāo)簽網(wǎng)(P，T，F(xiàn)，l)。

定義3[4](可行跡)設(shè)一個流程模型Petri網(wǎng)為N=(P，T，F(xiàn)，C)，發(fā)生序列集合為TN，σ=n1，n2，…，nk。若(x，y)?(N∪F)×(F∪N)，在σ中存在j∈(1，2，…，k-1)，j

給定一個系統(tǒng)網(wǎng)SN，φf(SN)是SN的所有完整發(fā)生序列的集合，φv(SN)是可見跡的集合，即從其初始標(biāo)識開始并于其終止標(biāo)識結(jié)束的完整發(fā)生序列投影到可見活動的集合(無靜默變遷)。

定義4[5](合法移動)設(shè)L∈B(A*)是一個事件日志，其中A是活動集，T是模型中的變遷集。此外，設(shè)l是返回每個變遷的標(biāo)簽函數(shù)。其中ALM是合法移動的集合：

ALM={(x，(x，t))|x∈Α∧t∈T∧l(t)=x}∪

{(>>，(x，t))|t∈Τ∧l(t)=x}∪

{(x，>>)|x∈A}

例如，(a，t1)表示日志和模型都產(chǎn)生了一個“a移動”，并且模型中的移動是由變遷t1(因為t1的標(biāo)簽是a的發(fā)生造成的，“>>”表明在日志或者模型跡中“無移動”)。定義對齊如下：

使用分配單位成本的標(biāo)準(zhǔn)成本函數(shù)δS：如果l(t)≠τ，δS(>>，t)=δS(x，>>)=1。給定日志跡和系統(tǒng)網(wǎng)，其中有可能產(chǎn)生許多對齊記錄，為了尋找最優(yōu)對齊，在此選擇總成本最低的對齊。

定義7[5](最優(yōu)對齊)設(shè)L∈B(A*)是一個事件日志，SN是一個φv(SN)≠0的系統(tǒng)網(wǎng)。

Ⅱ 一個對齊γ∈ΓσL，SN，對于跡σL∈L和系統(tǒng)網(wǎng)SN為最優(yōu)，且對于任意的對齊有γ′∈ΓσL，SN：δ(γ′)≥δ(γ)。

ⅣγSN∈A*→A*是為最優(yōu)對齊模型跡的可見活動分配任意日志跡σL的一個映射。

定義8(隱變遷)設(shè)T′是Petri網(wǎng)業(yè)務(wù)流程模型中的變遷集，L′是記錄日志事件集。l：T′→L′是標(biāo)簽映射，變遷t′稱為隱變遷，當(dāng)且僅當(dāng)t′?dom(l)，即變遷t′不在l的定義域內(nèi)。

文獻(xiàn)[6]中的Levenshtein距離為常用的距離函數(shù)，本次研究用到的編輯距離函數(shù)為該距離函數(shù)的調(diào)整版。

定義9[7](編輯距離函數(shù))設(shè)σ，σ′∈A*均為可行跡，編輯距離函數(shù)Δ(σ，σ′)→N，返回將σ轉(zhuǎn)換為σ′的最小編輯次數(shù)。

進(jìn)行編輯操作時，允許在跡中刪除和插入活動(或變遷標(biāo)簽)。例如，Δ(〈a，c，f，e〉，〈a，f，c，a〉)=4，對應(yīng)2個刪除和2個插入。這個度量具有對稱性，即Δ(σ，σ′)=Δ(σ′，σ)，其中使用Δ函數(shù)而不是標(biāo)準(zhǔn)成本函數(shù)。因此，Δ和δS返回相同的距離值。Δ函數(shù)按照給定的不同權(quán)重插入和刪除不同的活動，將單位成本(δS)擴(kuò)展成另一種成本。

運用式(1)，可以將未對齊成本轉(zhuǎn)換為適合度。它通過針對跡中每個活動的一次刪除和模型最短路徑(SPM)中每個可見變遷的一個插入來規(guī)范最優(yōu)對齊的成本。事件日志L和系統(tǒng)網(wǎng)SN之間的適合度Fitness(L，SN)為跡的加權(quán)平均值。

(1)

3 隱變遷的挖掘

根據(jù)事件日志中不同活動間的綁定關(guān)系進(jìn)行隱變遷挖掘。首先，從完整的事件日志中提取出高頻日志，基于高頻日志生成初始模型M0；然后，基于行為緊密度來識別有效低頻行為的序列；最后，利用有效低頻序列中活動間的綁定關(guān)系，挖掘行為模型中的隱變遷。

3.1 事件日志活動間的捆綁集

事件日志由跡的多重集構(gòu)成，活動集的集合為事件日志，各種活動間的行為關(guān)系一般由行為輪廓來描述。在此，基于捆綁的概念簡單描述日志中各活動間的行為關(guān)系：捆綁由六元組(A，ai，ao，D，I，O)組成，其中A為一個有限的活動集，ai∈A表示開始活動，ao∈A表示結(jié)束活動；D?A×A表示依賴關(guān)系，而AS={X?P(A)|X={φ}∨φ?X}；I∈A→AS為輸入捆綁活動集，O∈A→AS為輸出捆綁活動集，DI∈A→AS為直接輸入捆綁活動，DO∈A→AS為直接輸出捆綁活動，則有：

{ai}={a∈A|(a)={φ}}

{ao}={a∈A|O(a)={φ}}

對于日志〈a，b，c，e〉、〈a，c，e〉和〈a，b，e〉可得到活動c，其直接輸入捆綁活動集為Ic={a，b}，直接輸出捆綁活動集為Oc={e}。

根據(jù)日志活動間捆綁的定義，可以得到每個活動的輸入捆綁活動集、輸出捆綁活動集，開始或結(jié)束活動。同時，根據(jù)有效低頻信息中的多條日志得到活動的輸入、輸出捆綁活動集，發(fā)現(xiàn)模型的不直接相連活動，從而挖掘出模型中的隱變遷，完成流程模型的修復(fù)。

3.2 噪聲與有效低頻的松弛區(qū)分

在此，根據(jù)日志與初始模型的行為子集MB?φv(SN)的近似適合度及其區(qū)間值確認(rèn)有效低頻和噪音。當(dāng)日志與MB的近似適合度值未超出區(qū)間范圍時，該低頻日志被認(rèn)定為有效低頻；否則，該低頻日志被認(rèn)定為噪聲。使用編輯距離函數(shù)Δ，獲得對齊成本的上界，即適合度的下界。

引理1(對齊成本上界)。設(shè)σL∈A*是一個日志跡，σM∈φv(SN)是SN的課件發(fā)生序列，則有δS(γSN(σL))≤Δ(σL，σM)，其中γSN(σL)為最優(yōu)對齊[7]。

3.2.1 構(gòu)建模型行為子集

使用MB，即可見模型跡的子集，以獲得近似的適合度值。采用候選選擇的方法構(gòu)建MB，主要步驟如下[7]：

(1) 在事件日志L中任意選擇2條跡(即候選者)放入LC。按照松弛的思想，應(yīng)選擇高頻跡中頻次較低的跡。在表1所示日志中，越符合流程模型的跡，其產(chǎn)生的可能性就越高。若是考慮頻次最高的2條跡〈a，b，c，e，f〉和〈a，b，d，e，f〉，產(chǎn)生的適合度甚至?xí)哌_(dá)1，這樣便達(dá)不到松弛的目的；若是選擇頻次最低的2條跡，則最低頻的跡最可能為噪聲。故，可選擇〈a，b，d，e，f〉和〈a，c，e，f〉。

(2) 對于每個σL∈LC，找到最優(yōu)對齊并將λSN(σL)插入到MB。對照表1所示日志，分別將〈a，b，d，e，f〉和〈a，c，e，f〉置于初始模型中重放，即可得到與模型對齊的最優(yōu)對齊所對應(yīng)的模型跡，組成行為子集(MB)。

表1 示例日志

3.2.2 計算近似適合度

(3) 對于高頻部分，根據(jù)加權(quán)平均法得到高頻日志跡與初始模型總體的近似適合度ΦA(chǔ)F總，以及總體上下界[ΦLP，ΦUP]。

通過上述步驟得到每條日志跡與模型跡，以及高頻日志跡與初始模型整體的近似適合度ΦA(chǔ)F總及其上下界[ΦLP，ΦUP]。比較低頻日志跡的近似適合度值ΦA(chǔ)F與[ΦLP，ΦUP]：若ΦA(chǔ)F?[ΦLP，ΦUP]，則該日志跡為松弛后的有效低頻日志跡，可用于修復(fù)初始模型；若ΦA(chǔ)F?[ΦLP，ΦUP]，則該日志跡為噪聲。據(jù)此得到的有效低頻日志跡即松弛后的日志跡，利用這些日志跡活動的直接輸入和輸出捆綁活動集即可挖掘隱變遷，并添加合理的發(fā)生路徑。

3.3 利用直接輸入和輸出捆綁活動集挖掘隱變遷

挖掘初始模型中缺少的隱變遷，進(jìn)而修復(fù)模型。

(1) 日志跡。列出日志跡中所有活動的直接輸入和輸出捆綁活動集。

(2) 初始模型。根據(jù)Petri網(wǎng)前集與后集概念列出每個變遷的直接輸入前集與直接輸出后集。

比較日志跡與初始模型的挖掘結(jié)果，若松弛得到的有效低頻日志跡中活動集與該活動在模型中變遷所得直接前集中的元素不同，則可以確定其中存在合理的隱變遷。在其他情況下，皆無須添加合理路徑。

4 實際案例分析

醫(yī)院日?；顒油ǔ．a(chǎn)生龐大的流水日志。其中有些相對低頻的日志不完全與高頻日志挖掘到的模型相符，但是卻屬于正確流程。這些日志在大多流程挖掘過程中都被視為噪聲而過濾掉，或者直接被認(rèn)為是正確的日志而用于挖掘。當(dāng)這些日志被濾掉時，會使模型缺失極少發(fā)生的一部分正確流程；而當(dāng)這些日志全部被視為正確流程時，又會使模型復(fù)雜化，影響其精度。

在此，以某精神病院家屬接病人出院時的行為日志為例(見表2 )進(jìn)行挖掘分析?；谠撊罩镜那?種高頻跡，生成初始模型N1。雖然N1可以代表出院的正確流程，然而并不能解釋某些特殊情況下未完成路徑或已完成特殊路徑的正確出院流程。例如，申請人在確認(rèn)費用時，出現(xiàn)了不能及時支付的情況。 表3所示為醫(yī)院病人出院活動名稱。

表2 示例日志

表3 醫(yī)院病人出院活動名稱

根據(jù)上述事件日志，應(yīng)用挖掘算法得到圖1所示Petri網(wǎng)初始模型N1，該模型符合精神病院患者家屬申請出院的一般流程。

圖1 Petri網(wǎng)初始模型N1

圖1中的活動發(fā)生路徑基本涵蓋了辦理出院的一系列流程，然而對于一些特殊情況并未描述出來。有些低頻日志實際上對流程的完善是有益的，利用這些有用的低頻日志來挖掘隱變遷，可以改善模型的合理發(fā)生路徑。

選擇所有可能日志跡中相對低頻的部分，可以降低適合度的下界，從而達(dá)到松弛的目的，故將 〈a，b，d，e，f，g，h〉和〈a，b，d，e，f，h〉放入LC，然后將這2條跡放入初始模型N1中進(jìn)行重放。可以看出跡本身即為其相應(yīng)的最優(yōu)對齊的模型跡，針對表2構(gòu)造的模型行為子集為：

MB={〈a，b，d，e，f，g，h〉，〈a，b，d，e，f，h〉}

利用表2中日志與MB計算近似適合度，結(jié)果見表4。

表4 模型適合度計算數(shù)據(jù)

根據(jù)表4所示數(shù)據(jù)，去掉4種低頻跡，得到模型的松弛近似適合度為0.801，適合度的下界、上界分別為0.786、1.000，因此，日志與模型的適合度區(qū)間為[0.786，1.000]。運用此方法計算出剩余3條低頻跡的近似適合度，其值分別為0.818、0.800、0.769。前兩條跡的近似適合度值落在區(qū)間范圍內(nèi)，可知跡〈a，c，e，f，g，h〉、〈a，b，e，f，g，h〉和〈a，b，d，e〉為有效低頻跡，跡〈a，h〉為噪聲。接著，可利用跡中活動的輸入輸出捆綁活動集挖掘初始模型中被忽略的隱變遷。

對于跡〈a，c，e，f，g，h〉、〈a，b，e，f，g，h〉和〈a，b，d，e〉，列出其活動的輸入輸出捆綁集(見表5)。為了使對比更明顯，列出初始模型N1中變遷的直接前集與后集(見表6)。

表5 輸入輸出捆綁活動集

表6 N1的直接前集與后集

由表5和表6可以看出，事件日志中活動e的輸入輸出捆綁活動集分別為{a，b，d}和{f}∪{φ}，而N1中變遷e的直接前集和后集分別為{c，d}和{f}。由此可推斷出，變遷a與變遷e之間、變遷b與變遷e之間各自有一個隱變遷，變遷e與終止標(biāo)識p7之間應(yīng)該也存在一個隱變遷。其他剩余活動的輸入與輸出捆綁活動集均處于N1的變遷直接前集與后集的集合內(nèi)。最終得到的模型為N2，如圖2所示。

圖2 挖掘隱變遷后的模型N2

5 結(jié) 語

現(xiàn)有的挖掘方法大多默認(rèn)事件日志完全無噪聲，或者將所有可能的低頻日志都視為噪聲，這是與事實不符的。本次研究提出的增強(qiáng)挖掘流程方法，主要挖掘流程中的隱變遷分支，以增強(qiáng)模型的適合度。同時，提出了日志中活動的輸入捆綁及輸出捆綁的概念，用于識別存在于日志中而流程模型中沒有的活動捆綁關(guān)系來確定隱變遷的存在位置，增強(qiáng)了模型的描述性與適用性。其次，運用松弛思想，在選擇低頻日志中的有效低頻時，過濾掉最可能是噪聲的低頻日志。最后，利用剩余低頻近似適合度與初始模型行為子集適合度上下界區(qū)間范圍對初始模型進(jìn)行修復(fù)?；谒沙谒枷?，所得模型更符合日志的實際情況。