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

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

(山東理工大學 計算機科學與技術學院，山東 淄博 255000)

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

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

1 相關工作

1.1 漂移檢測

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

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

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

1.2 流程變體差異分析

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

1.3 現存挑戰

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

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

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

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

2.2 漂移檢測

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

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

圖2 漂移檢測方法

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

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

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

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

1) 總是存在，Dij=1；

2) 從不存在，Dij=0；

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

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

表1 L={abcd,acbd,abdc,adbc,acdb}的關系矩陣

具體檢測過程如圖3所示。設置間隔長度為4，第一行為矩陣中的列號(軌跡ID)，第二行為活動關系的變化情況。區間[1,15]以5為單位劃分為3個區間，區間內活動關系經歷了有時存在、總是存在、從不存在3個階段。區間[1,2)和區間[3,5)距離長度小于4，不認為兩個區間關系的過渡會產生漂移；區間[1,5)和區間[6,10)距離長度大于4，關系從有時存在變為總是存在，認為兩個區間關系的過渡產生漂移；區間[6,10)和區間[11,15)距離長度大于4，關系從總是存在變為從不存在，認為兩個區間關系的過渡產生漂移，故可能的候選漂移點為6和11。

圖3 候選漂移點檢測

圖4 候選漂移點合并

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

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

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

算法1 漂移檢測 輸入:事件日志L,關系長度d,最小時間間隔s,聚類半徑r; 輸出:模型漂移點集合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 流程變體差異分析

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

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

圖6 差異分析示例

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

算法2 漂移檢測 輸入:模型漂移點集合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 實驗分析

3.1 數據集及實驗設置

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

利用文獻[6]中已公開發表的數據集進行測試，圖7為用于測試漂移的一個貸款申請業務流程[6]模型，共包括15個活動、1個開始事件和3個結束事件，并展示了循環、并發和選擇等控制流結構。數據集中共包含72個與貸款申請業務流程不同變體相關的合成日志。

圖7 貸款申請業務流程的參考模型

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

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

圖8 日志仿真過程

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

3.2 評價指標

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

(1)

(2)

(3)

其中：TP表示正確檢測到的漂移點數量，FP表示誤檢的漂移點數量，FN表示漏檢的漂移點數量。

為了對檢測到的具有顯著差異的行為進行準確評估，設計一個基于矩陣相似性的方法來預判相鄰變體的差異：

(4)

(5)

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

3.3 實驗結果

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

圖9 不同鄰域半徑對結果的影響

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

此外，本算法是在文獻[14]的基礎上改進得到的，在保證漂移檢測準確性的前提下，對本算法和文獻[14]在時間效率上進行對比，見圖11。可見，本算法的時間效率優于文獻[14]，進一步驗證了二者在時間復雜度上的差異。

圖11 時間效率對比

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

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

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

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

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

根據上述實驗可知，從淺層的檢測漂移點到更深層次的定位及可視化描述能夠揭露業務動態演化過程，可以幫助業務分析人員更好地進行流程配置和維護。

4 結論

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