基于漂移檢測的流程變體差異分析方法

李 婷，鞏秀鋼，徐興榮，李會玲，牛慧敏，劉 聰

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255000)

過程挖掘技術(shù)提供了一種從事件日志中自動抽取過程知識的方法，其典型的應(yīng)用場景之一是過程發(fā)現(xiàn)[1]，即從事件日志中挖掘出潛在的過程模型。過程發(fā)現(xiàn)算法能夠從穩(wěn)定行為的事件日志中生成過程模型，但由于多方面的因素，過程模型在真實(shí)的業(yè)務(wù)環(huán)境中是動態(tài)調(diào)整的[2]，這種業(yè)務(wù)流程在執(zhí)行過程中的動態(tài)變化稱為漂移。如果將傳統(tǒng)的過程發(fā)現(xiàn)技術(shù)應(yīng)用于含有漂移的事件日志中，挖掘出來的過程模型由于混雜了多個模型的行為變得復(fù)雜且無法解釋。如何通過漂移檢測來定位漂移前后流程內(nèi)容的變化顯得尤為重要。

在實(shí)踐中，業(yè)務(wù)流程中漂移的存在是事先不知道的，分析人員需要隨著時間的推移區(qū)分哪些流程發(fā)生了變化，哪些沒有變化，從而做出決策來減輕其影響[3]?，F(xiàn)有的過程挖掘研究僅側(cè)重于漂移檢測，對漂移前后流程變化的分析和解釋略顯不足。本研究通過抽取日志中軌跡的活動關(guān)系來檢測和定位漂移，對漂移前后的流程進(jìn)行可視化分析，揭示具有顯著差異的流程行為，幫助企業(yè)管理者適應(yīng)或改進(jìn)其業(yè)務(wù)流程。實(shí)驗(yàn)結(jié)果表明，所提方法能夠有效檢測到漂移，并對檢測到的漂移提供準(zhǔn)確描述。

1 相關(guān)工作

1.1 漂移檢測

業(yè)務(wù)流程中事件日志的可用性激發(fā)了各種流程挖掘技術(shù)，這些技術(shù)主要支持過程監(jiān)控和分析。經(jīng)典的過程挖掘技術(shù)通常假設(shè)日志對時間不敏感，即在產(chǎn)生事件日志的執(zhí)行過程中從未發(fā)生版本演化[4]。在過程挖掘中引入漂移的挑戰(zhàn)是如何以時間依賴的方式表示行為變化。

早期的方法大多基于假設(shè)檢驗(yàn)和統(tǒng)計(jì)測試，不僅需要巨大的特征空間，還需要人為選擇合適的特征，同時還不易擴(kuò)展。如Bose等[5]將軌跡表征為特征向量進(jìn)行統(tǒng)計(jì)測試，Maaradji等[6]直接對兩個連續(xù)窗口之間的軌跡頻率進(jìn)行統(tǒng)計(jì)測試。這類方法保留了有損統(tǒng)計(jì)檢驗(yàn)可靠性的低頻行為，因此存在局限性。

基于相似性的漂移檢測方法依賴于事件日志和提取的行為特征，如活動頻率或活動之間的關(guān)系。Carmona等[7]從早期的數(shù)據(jù)中建立一個凸多面體來抽象表示包含多條軌跡的事件日志，并檢查此多面體與最近軌跡的交點(diǎn)，但在檢測到漂移后需要重新啟動，擴(kuò)展性不強(qiáng)。劉娜等[8]使用流程一致性技術(shù)來檢查從軌跡中提取的活動與發(fā)現(xiàn)的流程模型之間關(guān)系的相似性。該類方法在考慮不屬于實(shí)際業(yè)務(wù)流程的行為時，可能會檢測到虛假的漂移。

1.2 流程變體差異分析

從過程挖掘的角度來看，比較流程變體的方法可以用在概念漂移中來描述業(yè)務(wù)流程行為方面的差異。Adriansya等[9]基于對齊的方法將每個流程模型與相應(yīng)事件日志進(jìn)行比較來顯示模型和流程執(zhí)行之間的差異。Beest等[10]從對應(yīng)的事件日志中計(jì)算行為的相關(guān)頻率來識別兩個事件日志之間的差異，但此方法只考慮了相對頻率，存在局限性。Perner等[11]利用決策樹來比較變體差異，由于只對其分支規(guī)則進(jìn)行結(jié)構(gòu)比較，容易造成高度過擬合的現(xiàn)象。Bolt等[12]對從子日志中提取的流程指標(biāo)執(zhí)行統(tǒng)計(jì)測試，但不能識別某些變化，也無法對有差異的流程行為進(jìn)行可視化表示。Nguyen等[13]通過抽取日志中實(shí)體間的關(guān)系來構(gòu)造關(guān)系圖，并根據(jù)權(quán)重、公共節(jié)點(diǎn)和邊進(jìn)行比較，生成一個可視化的矩陣來突出顯示兩個過程變體之間的變化。

1.3 現(xiàn)存挑戰(zhàn)

現(xiàn)有工作只強(qiáng)調(diào)漂移檢測和變體差異分析這兩個孤立任務(wù)而缺乏全局觀念，漂移檢測僅能單純地定位發(fā)生變化的關(guān)鍵點(diǎn)，并不能對漂移點(diǎn)前后的流程行為變化進(jìn)行詳實(shí)描述，無法有效解決漂移定位與變體分析孤立存在的問題。因此，本研究提出一種基于漂移檢測和流程變體差異分析的綜合方法，在不需要額外的數(shù)據(jù)結(jié)構(gòu)或過程模型的情況下，能夠有效檢測變化并解釋變化的具體內(nèi)容，幫助業(yè)務(wù)分析人員更好地理解流程行為并做出決策。

2 基于漂移檢測的流程變體差異分析方法

2.1 基于漂移檢測的流程變體差異分析方法

本研究提出的基于漂移檢測的流程變體差異分析方法，整體框架如圖1所示。首先在鄭燦彬等[14]所提方法的基礎(chǔ)上進(jìn)行改進(jìn)，以事件日志為輸入進(jìn)行漂移檢測；然后根據(jù)漂移檢測的結(jié)果對事件日志進(jìn)行分割，采用可視化方法將分割后的兩個連續(xù)子日志的流程呈現(xiàn)出來；最后比較兩個流程圖中活動的發(fā)生順序，標(biāo)記并輸出具有顯著差異的活動結(jié)點(diǎn)和邊。

2.2 漂移檢測

過程挖掘領(lǐng)域的核心數(shù)據(jù)是事件日志，需要從事件日志中提取流程的相關(guān)信息，完成對漂移的檢測和對流程差異行為的描述。本研究對文獻(xiàn)[14]進(jìn)行改進(jìn)，提出一種通過抽取日志中活動間行為上下文關(guān)系來檢測漂移的方法，整體架構(gòu)如圖2所示。

圖1 基于漂移檢測的流程變體差異分析方法框架

圖2 漂移檢測方法

定義1(行為上下文關(guān)系) 行為上下文關(guān)系[15]是一對活動序列，事件日志L中的一組行為上下文關(guān)系表示為：βL∈ρ(A*×A*)，βL={(σl,σr)∈A*×A*|?σ∈L,σ′∈A*(σl·σ′·σr∈σ)}，其中，A為一組活動，A*為A上所有可能活動序列的集合，σl和σr為2個活動序列，σ′為則軌跡σ的子序列。

例如，在軌跡σ=中，和是圍繞著活動的兩個子序列，因此，活動序列對(,)是活動的行為上下文關(guān)系。此處可設(shè)置關(guān)系長度，若關(guān)系長度設(shè)置為1，則活動的行為上下文關(guān)系為(,)。在確定了活動間的關(guān)系之后，可以通過抽取活動間的行為上下文關(guān)系來構(gòu)造關(guān)系矩陣，進(jìn)而表示事件日志中所有關(guān)系的變化情況。

定義2(關(guān)系矩陣) 設(shè)L是一個包含n條軌跡的事件日志，即L={σ1,…,σn}。D為一個關(guān)系矩陣，Dij表示矩陣D中第i行第j列的元素，i為日志中所包含的活動關(guān)系的有限集合，j為軌跡的ID。若關(guān)系i在軌跡σj上存在，則Dij=1，否則Dij=0。

定義3(頻率變化) 給定一種活動關(guān)系i和一個整數(shù)時間間隔[x,y)，i在[x,y)上的頻率變化情況為：

1) 總是存在，Dij=1；

2) 從不存在，Dij=0；

3) 有時存在，Dij={0∪1}。

以事件日志L={abcd,acbd,abdc,adbc,acdb}為例，表1為關(guān)系長度為1的行為上下文關(guān)系矩陣。根據(jù)關(guān)系矩陣的定義，矩陣的每一行代表日志中一種活動的變化情況，每一列代表每條軌跡中存在的所有活動關(guān)系。若活動關(guān)系i在時間間隔[x,y]上總是存在或者從不存在，表明關(guān)系i在此間隔內(nèi)具有不變性，將間隔長度預(yù)先設(shè)置為某個閾值。若在相鄰兩個時間間隔上的同一活動關(guān)系有變化，即在給定的時間間隔內(nèi)從一個值變?yōu)榱硪粋€值，則說明流程可能在兩個時間間隔的交點(diǎn)處發(fā)生了漂移，此處的交點(diǎn)即為可能的漂移點(diǎn)。

表1 L={abcd,acbd,abdc,adbc,acdb}的關(guān)系矩陣

具體檢測過程如圖3所示。設(shè)置間隔長度為4，第一行為矩陣中的列號(軌跡ID)，第二行為活動關(guān)系的變化情況。區(qū)間[1,15]以5為單位劃分為3個區(qū)間，區(qū)間內(nèi)活動關(guān)系經(jīng)歷了有時存在、總是存在、從不存在3個階段。區(qū)間[1,2)和區(qū)間[3,5)距離長度小于4，不認(rèn)為兩個區(qū)間關(guān)系的過渡會產(chǎn)生漂移；區(qū)間[1,5)和區(qū)間[6,10)距離長度大于4，關(guān)系從有時存在變?yōu)榭偸谴嬖?，認(rèn)為兩個區(qū)間關(guān)系的過渡產(chǎn)生漂移；區(qū)間[6,10)和區(qū)間[11,15)距離長度大于4，關(guān)系從總是存在變?yōu)閺牟淮嬖?，認(rèn)為兩個區(qū)間關(guān)系的過渡產(chǎn)生漂移，故可能的候選漂移點(diǎn)為6和11。

圖3 候選漂移點(diǎn)檢測

圖4 候選漂移點(diǎn)合并

在每個給定的活動關(guān)系上進(jìn)行檢測得到的候選漂移點(diǎn)不一定是真正意義上的漂移點(diǎn)，需要對候選漂移點(diǎn)進(jìn)行聚類，以獲得大概率事件下整個流程的漂移點(diǎn)。該聚類方法依賴于密度聚類算法，通過密度聚類將檢測到的漂移點(diǎn)聚成若干點(diǎn)簇，按照簇中點(diǎn)的數(shù)量由大到小排序，簇中點(diǎn)的數(shù)量越多，該點(diǎn)簇越有可能代表最終的流程漂移點(diǎn)。通過對簇內(nèi)所有漂移點(diǎn)進(jìn)行聚合平均，獲得表示流程漂移點(diǎn)的單一值，可用質(zhì)心來表示。

示例過程如圖4所示，基于密度聚類算法對候選漂移點(diǎn)進(jìn)行合并，合并后的點(diǎn)簇C3比點(diǎn)簇C2包含更多的候選漂移點(diǎn)，說明點(diǎn)簇C3更有可能代表一個真正的流程漂移點(diǎn)，此處點(diǎn)簇C3用質(zhì)心來表示。下面給出漂移檢測的算法。

設(shè)事件日志中包含的軌跡有n條，活動關(guān)系數(shù)有m個，軌跡的平均長度為k。算法1中抽取行為上下文關(guān)系并轉(zhuǎn)換成關(guān)系矩陣的復(fù)雜度為Ο(nk)。由于候選漂移點(diǎn)的數(shù)量不會超過mn/s，因此，檢測候選漂移點(diǎn)并對候選漂移點(diǎn)進(jìn)行合并生成模型漂移點(diǎn)的復(fù)雜度為O(mn)+O(mn/s)=Ο(mn)。綜合來看，整個漂移檢測算法的時間復(fù)雜度為O(nk)+O(mn)，稍低于文獻(xiàn)[14]中的時間復(fù)雜度O(nk2)+O(mn)。

算法1 漂移檢測 輸入:事件日志L,關(guān)系長度d,最小時間間隔s,聚類半徑r; 輸出:模型漂移點(diǎn)集合Drift. 1)Drift←0, List←?, C←0, res←?, D←? 2)For i←1 to len(trace)-1 do 3) For key to res, key() then 4) if [key[i]∈key[i-1], key[i+1]] then 5) D←{D∪res[i]} 6)return D 7)For j←0 to D[i][n] do (i≤n) 8) if [D[i][j], D[i][j+1]]∈d and [D[i][j], D[i][j+1]]>s then 9) List←{List∪D[i][j]} 10) return List 11) For k←0 to clusters[list, r] do 12) C← clusters[k] then 13) sort(C)max→min then 14) Drift←{Drift∪C} then 15) return Drift

圖5 變體差異分析算法

2.3 流程變體差異分析

基于上述工作，在漂移檢測的基礎(chǔ)上，給出定位相鄰變體間流程行為變化的算法，算法的整體架構(gòu)如圖5所示。①將原始事件日志按照檢測到的流程漂移點(diǎn)切割成多個連續(xù)的子日志；②通過比較子日志間關(guān)系矩陣的相似性來預(yù)判相鄰變體間的差異；③通過繪制有向圖的方式來描述每個流程漂移點(diǎn)前后子日志中活動間的發(fā)生順序；④根據(jù)有向圖中對應(yīng)活動和活動順序的一致性來判定變體間具有顯著差異的行為并對其進(jìn)行可視化。

將分割后的兩個連續(xù)子日志依據(jù)活動發(fā)生的順序生成有向圖，再對有向圖中的活動順序進(jìn)行比較，若無法匹配，則在有向圖中對活動結(jié)點(diǎn)和活動順序進(jìn)行標(biāo)記。其中，活動的發(fā)生順序是指活動的跟隨關(guān)系，在有向圖中用箭頭來表示，箭頭的始端表示先發(fā)生的活動，箭頭的尾端表示隨后發(fā)生的活動。圖6為兩個變體間活動片段出現(xiàn)差異的場景示例。

圖6 差異分析示例

算法2展示了流程變體差異分析的核心部分。設(shè)事件日志中包含的軌跡有n條，活動關(guān)系數(shù)有m個，則算法2的時間復(fù)雜度為Ο(mn)。本研究方法的整體復(fù)雜度為Ο(nk)+Ο(mn)。

算法2 漂移檢測 輸入:模型漂移點(diǎn)集合Drift; 輸出:變體間的矩陣相似度δ, 變體間具有顯著差異的行為Diff. 1)δ←0, Diff←?, D←?, count←0, 2)For i←0 to len(Drift)-1 do 3) basic on Drift[i] split L to L0, L1, L2,…,Ln-1 then 4) D0～n-1←{L0～n-1} compare [δ0～n-1, δ1-n] 5) count++ 6)For j←0 to count do 7) found activity and D[j] then 8) if activity!=D[j] then 9) Diff←{Diff∪D[j] } 10) return Diff

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

3.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置

為了模擬概念漂移的存在，使用ProM工具對Petri網(wǎng)模型生成仿真日志。實(shí)驗(yàn)基于PC Intel Core i5-4210 M 2-60 GHz CPU，12 GB RAM環(huán)境，使用Python語言實(shí)現(xiàn)。

利用文獻(xiàn)[6]中已公開發(fā)表的數(shù)據(jù)集進(jìn)行測試，圖7為用于測試漂移的一個貸款申請業(yè)務(wù)流程[6]模型，共包括15個活動、1個開始事件和3個結(jié)束事件，并展示了循環(huán)、并發(fā)和選擇等控制流結(jié)構(gòu)。數(shù)據(jù)集中共包含72個與貸款申請業(yè)務(wù)流程不同變體相關(guān)的合成日志。

圖7 貸款申請業(yè)務(wù)流程的參考模型

表2為12種簡單的控制流變更模式，為了進(jìn)一步模擬更復(fù)雜的情況，將簡單的變更模式分為插入(I)、重排序(R)和選擇(O)3個類別，通過從每個類別中隨機(jī)應(yīng)用一個模式相互嵌套產(chǎn)生6個可能的綜合變化模式：IOR、IRO、OIR、ORI、RIO、ROI。例如，綜合模式IOR是通過插入(I)一個新活動，然后選擇(O)該活動或現(xiàn)有活動，最后將整個模塊放入重排序(R)結(jié)構(gòu)中來獲得。

表2 12種簡單的控制流變更模式

圖8 日志仿真過程

在日志仿真過程中，先通過應(yīng)用以上變更模式對基礎(chǔ)模型進(jìn)行修改得到新的模型，然后為每個修改后的新模型和基礎(chǔ)模型仿真生成5組同等規(guī)模的事件日志，每組日志規(guī)模分別為250、500、750、1 000，最后將每組日志按順序交叉拼接得到混合事件日志。圖8以250條軌跡的日志規(guī)模為例進(jìn)行仿真，該事件日志混合了兩個模型的日志，每個模型分別生成5組250條軌跡的日志，得到10組250條軌跡規(guī)模的日志，即最后的混合事件日志為L10,250。

3.2 評價指標(biāo)

以日志拼接的方式生成混合日志，說明日志中發(fā)生漂移的位置是事先已知的。如果檢測到的漂移點(diǎn)位于實(shí)際漂移點(diǎn)的某個較小鄰域半徑R內(nèi)，則認(rèn)為該檢測結(jié)果正確，R越小，檢測的精度越高。為了評估檢測的準(zhǔn)確性，使用數(shù)據(jù)挖掘[16]中針對漂移檢測建立的既定指標(biāo)，即以召回率和精確度的調(diào)和平均值衡量的F-Score來度量方法性能：

(1)

(2)

(3)

其中：TP表示正確檢測到的漂移點(diǎn)數(shù)量，F(xiàn)P表示誤檢的漂移點(diǎn)數(shù)量，F(xiàn)N表示漏檢的漂移點(diǎn)數(shù)量。

為了對檢測到的具有顯著差異的行為進(jìn)行準(zhǔn)確評估，設(shè)計(jì)一個基于矩陣相似性的方法來預(yù)判相鄰變體的差異：

(4)

(5)

其中：α為矩陣相似度，j為第j個矩陣，xi為矩陣中的某一活動關(guān)系，xi,j為活動關(guān)系xi在矩陣j中的成立情況。若活動關(guān)系xi在相鄰兩個矩陣中成立情況不一致，則標(biāo)記為1，反之為0。然后，統(tǒng)計(jì)成立情況不一致的活動關(guān)系在全部活動關(guān)系中所占比例，進(jìn)而得到兩個矩陣的相似度。

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

為測試算法的效果，在不同規(guī)模的混合日志上(L10,250，L10,500，L10,750，L10,1000)進(jìn)行測試。圖9為本研究算法在不同鄰域半徑R下對12種基本變化模式進(jìn)行漂移檢測的平均效果。由圖9可以看出，本研究算法(簡稱本算法)的檢測效果隨著鄰域半徑R的增大而明顯提升。聚類半徑對檢測效果的影響如圖10所示，當(dāng)聚類半徑增大到超過每組日志的規(guī)模時，本該分開的點(diǎn)簇可能會聚合在一起，導(dǎo)致漂移點(diǎn)被漏檢，從而影響召回率和準(zhǔn)確率，故本算法在聚類半徑較小時會取得好的效果。

圖9 不同鄰域半徑對結(jié)果的影響

圖10 不同聚類半徑對結(jié)果的影響Fig. 10 The influence of clustering radius on the results

此外，本算法是在文獻(xiàn)[14]的基礎(chǔ)上改進(jìn)得到的，在保證漂移檢測準(zhǔn)確性的前提下，對本算法和文獻(xiàn)[14]在時間效率上進(jìn)行對比，見圖11?？梢?，本算法的時間效率優(yōu)于文獻(xiàn)[14]，進(jìn)一步驗(yàn)證了二者在時間復(fù)雜度上的差異。

圖11 時間效率對比

漂移前后相鄰變體間行為的差異能夠體現(xiàn)流程的演變，故利用漂移前后相鄰變體的相似度進(jìn)行預(yù)判，能大概率的度量流程變體之間行為程度的差異。將聚類半徑R固定為10，在ORI模式下得到的混合日志L10,1 000中檢測出來的流程變體矩陣之間的相似程度見表3。

表3 L10,1 000中相鄰流程變體矩陣的相似度

對漂移前后流程變體間的差異行為進(jìn)行檢測和標(biāo)注，能夠更準(zhǔn)確地把握流程行為的演變。圖12為綜合變化模式ORI下，混合日志L10,1 000中檢測出來的變體1和變體2的有向圖，圖13為兩者具有顯著差異行為的可視化示意圖。

圖12 變體1與變體2的有向圖

圖13 變體1與變體2差異行為的可視化

根據(jù)上述實(shí)驗(yàn)可知，從淺層的檢測漂移點(diǎn)到更深層次的定位及可視化描述能夠揭露業(yè)務(wù)動態(tài)演化過程，可以幫助業(yè)務(wù)分析人員更好地進(jìn)行流程配置和維護(hù)。

4 結(jié)論

通過抽取事件日志中活動間行為上下文關(guān)系的方法來檢測漂移，不僅可以降低算法的時間復(fù)雜度，還能通過結(jié)果對漂移前后的變體流程進(jìn)行差異檢測。此外，根據(jù)所提評估方法對變體間行為差異的檢測結(jié)果進(jìn)行質(zhì)量評估，間接證明了本算法的有效性。本算法主要針對離線場景下的概念漂移，未來可以從在線場景入手對漂移以及漂移后的流程演變進(jìn)行分析或者預(yù)測。此外，針對更復(fù)雜的業(yè)務(wù)流程場景，如跨組織交互過程，嘗試給出針對性的漂移檢測算法。