胡玉倩 方賢文

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

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

1 問(wèn)題的描述

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

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

2 基本理論

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

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

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

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

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

Petri網(wǎng)的變遷可以用出自字母表Σ的字母名稱來(lái)標(biāo)記，如假設(shè)標(biāo)簽τ∈Σ代表一個(gè)不可見(jiàn)的動(dòng)作。標(biāo)簽Petri網(wǎng)(P，T，F(xiàn)，l)，是一個(gè)標(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)，是一個(gè)初始標(biāo)識(shí)為m0、終止標(biāo)識(shí)為mf的標(biāo)簽網(wǎng)(P，T，F(xiàn)，l)。

定義3[4](可行跡)設(shè)一個(gè)流程模型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

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

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

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

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

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

例如，(a，t1)表示日志和模型都產(chǎn)生了一個(gè)“a移動(dòng)”，并且模型中的移動(dòng)是由變遷t1(因?yàn)閠1的標(biāo)簽是a的發(fā)生造成的，“>>”表明在日志或者模型跡中“無(wú)移動(dòng)”)。定義對(duì)齊如下：

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

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

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

ⅣγSN∈A*→A*是為最優(yōu)對(duì)齊模型跡的可見(jiàn)活動(dòng)分配任意日志跡σL的一個(gè)映射。

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

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

(1)

3 隱變遷的挖掘

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

3.1 事件日志活動(dòng)間的捆綁集

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

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

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

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

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

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

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

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

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

使用MB，即可見(jiàn)模型跡的子集，以獲得近似的適合度值。采用候選選擇的方法構(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) 對(duì)于每個(gè)σL∈LC，找到最優(yōu)對(duì)齊并將λSN(σL)插入到MB。對(duì)照表1所示日志，分別將〈a，b，d，e，f〉和〈a，c，e，f〉置于初始模型中重放，即可得到與模型對(duì)齊的最優(yōu)對(duì)齊所對(duì)應(yīng)的模型跡，組成行為子集(MB)。

表1 示例日志

3.2.2 計(jì)算近似適合度

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

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

3.3 利用直接輸入和輸出捆綁活動(dòng)集挖掘隱變遷

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

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

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

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

4 實(shí)際案例分析

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

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

表2 示例日志

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

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

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

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

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

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

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

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

根據(jù)表4所示數(shù)據(jù)，去掉4種低頻跡，得到模型的松弛近似適合度為0.801，適合度的下界、上界分別為0.786、1.000，因此，日志與模型的適合度區(qū)間為[0.786，1.000]。運(yùn)用此方法計(jì)算出剩余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〉為噪聲。接著，可利用跡中活動(dòng)的輸入輸出捆綁活動(dòng)集挖掘初始模型中被忽略的隱變遷。

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

表5 輸入輸出捆綁活動(dòng)集

表6 N1的直接前集與后集

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

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

5 結(jié) 語(yǔ)

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