基于時間差約束的事件日志合并
2022-12-31 00:00:00李欣歌趙海燕陳慶奎曹健
計算機應用研究 2022年11期
摘 要：在跨企業、跨系統的環境中，流程數據通常記錄在單獨的事件日志中，這使得無法挖掘完整的端到端的執行流程，因此提出的算法僅使用事件名稱以及時間戳屬性對日志進行合并。首先分別獲取兩個系統的過程模型以及根據活動的跨系統跟隨依賴關系獲得的合并模型，接著將兩個系統的流程一對一進行合并并按照時間戳排序，留下與合并模型路徑一致的合并流程，然后從這些流程中獲得一對一的實例對，即唯一主流程僅與唯一子流程可以合并，再從這些實例對中挖掘活動間的時間約束用于剩余日志的合并，重復最后兩步直到所有日志均合并或無法一對一合并日志。該算法在真實的事件日志上進行了實驗，達到了滿意的合并效果并獲得較高的準確率與召回率。
關鍵詞：業務過程；事件日志；過程挖掘；日志合并
中圖分類號：TP319 文獻標志碼：A
文章編號：1001-3695（2022）11-032-3402-08
doi：10.19734/j.issn.1001-3695.2022.04.0195
Event log merging based on time difference constraints
Li Xinge1，Zhao Haiyan1，Chen Qingkui1，Cao Jian2
（1.Shanghai Key Lab of Modern Optical System，and Engineering Research Center of Optical Instrument amp; System，Ministry of Education，University of Shanghai for Science amp; Technology，Shanghai 200093，China；2.Dept. of Computer Science amp; Technology，Shanghai Jiao Tong University，Shanghai 200030，China）
Abstract：In the cross enterprise or cross system environment，the process data is usually recorded in a separate event log，which makes it impossible to mine the complete end-to-end execution process.Therefore，this algorithm proposed to merge the logs only by using the event name and timestamp attributes.Firstly，it obtained the process models of the two systems and the merge model according to the cross system followed dependency of activities，then merged the processes of the two systems one-to-one and sorted them according to the timestamp and left the merge processes consistent with the merge model path.Then it obtained one-to-one instance pairs from these processes，that was，the only main process could be merged with the only sub process.Then，it mined time constraints between activities from these instance pairs for consolidation of remaining logs，and repeated the last two steps until all logs were merged or couldn’t be merged one-to-one.The algorithm is tested on the real event log，and achieves satisfactory merging effect and high precision and recall.
Key words：business process；event log；process mining；log merge
基金項目：國家自然科學基金資助項目（62072301）
作者簡介：李欣歌（1997-），女（通信作者），河南鄭州人，碩士研究生，主要研究方向為過程挖掘、機器學習、數據挖掘（L1113027@163.com）；趙海燕（1975-），女，河南人，副教授，碩導，博士，主要研究方向為服務計算、數據挖掘、推薦系統；陳慶奎（1967-），男，黑龍江人，教授，博導，博士，主要研究方向為計算機集群、并行數據庫、并行理論、物聯網等；曹?。?972-），男，江蘇人，教授，博導，博士，主要研究方向為協同計算、服務計算、網絡計算、智能數據分析等.
0 引言
為了使企業工作流程越來越高效化、標準化，20世紀90年代提出了工作流管理的觀念并得到了廣泛關注，文獻［1］提出了關于工作流管理的模型、方法與系統。之后，信息系統與它們所支持的業務流程越來越緊密地結合在一起，因此，信息系統中記錄了數量龐大的數據，這些數據以事件日志的形式進行保存。然而，企業很難從這些事件數據中提取有價值的信息。由此，Van Der Aalst［2］提出了過程挖掘的概念，其旨在通過對事件日志的采集、處理和分析，從而對業務過程進行挖掘、監控和優化。文獻［3］提出真實的業務流程產生的日志數據會存在各種質量問題，這些問題的存在會降低分析結果的正確性。文獻［4］提出了當前過程挖掘面臨的難點，其中第一個難點就是發現、合并和清洗事件日志數據。因此文獻［5］提出在過程挖掘之前需要對日志數據作預處理，從而保證事件日志數據的質量。其中的一個日志問題在于日志的不完整性，即真實的業務流程通常涉及到多個信息系統，文獻［6］提出從某一系統提取出的事件日志并不反映完整的業務執行過程，而目前所存在的過程模型挖掘算法都是針對單個事件日志。為了挖掘完整的端到端的業務過程，需要將不同源上的日志作合并處理，從而揭示完整的端到端的流程。日志合并主要由兩步組成，首先發現不同事件日志中屬于同一流程實例的日志，然后將其合并且按照時間戳對事件進行排序構成完整的流程。其中，第一步發現流程間的實例匹配是日志合并的基礎與核心。
當前關于日志合并的方法主要包含基于智能算法的合并［7～10］、基于可合并的時間關系和屬性值相似［11，12］、基于規則以及規則建議算法［13，14］。其中基于智能算法包含Claes等人［7］提出的基于人工免疫算法、文獻［8，9］提出的基于混合免疫算法以及Claes等人［10］提出的基于遺傳算法。前兩種智能算法將日志合并問題轉換成抗原和抗體的親和力判斷問題，而基于遺傳算法［10］將問題轉換為隨機解的匹配度問題?；诳珊喜⒌臅r間關系和屬性值相似［11，12］則以日志軌跡之間的時間關系作為第一判斷條件，然后以屬性值相似性分數作為第二合并條件。最后基于規則以及規則建議算法［13，14］是指程序通過發現日志特點向用戶建議合并的規則。
以上方法都適用于事件日志文件中事件包含多個屬性值，以及兩個流程的時間線有重疊部分。而在真實的事件日志中也存在幾種特殊情況：a）事件屬性僅包含事件名稱和時間戳這兩種屬性；b）事件的其他屬性對日志合并無太大幫助；c）要合并的兩個流程在時間線上并未有重疊的部分。采用以上方法對于這幾種情況的日志合并效果并不好。因此針對這幾種情況的日志提出另外的日志合并方法，僅考慮使用事件名稱和時間戳屬性對日志進行合并。
1 相關工作
目前，面向過程挖掘的關于日志合并的方法主要分為基于智能算法的日志合并［7～10］、基于可合并的時間關系和屬性值相似［11，12］、基于規則以及規則建議算法［13，14］。其中，基于智能算法主要包含文獻［7］提出的基于人工免疫算法、文獻［8，9］提出的混合免疫算法和文獻［10］提出的基于遺傳算法，前兩種算法是將不同日志之間的過程實例匹配問題轉換為抗原和抗體的親和力判斷問題，為解決人工免疫算法得到的實例匹配解容易陷入局部最優的陷阱，混合免疫算法在人工免疫算法的基礎上添加了模擬退火算法，在保證合并質量的前提下提高了合并效率，同時也解決了人工免疫算法容易陷入局部最優的問題?；谶z傳算法將不同日志中的過程實例進行隨機合并形成總的鏈接集，然后在每一步中對鏈接集進行隨機突變，保留比原來鏈接集中匹配度更高的解。文獻［11，12］提出的基于可合并的時間關系和屬性值相似是指為滿足時間關系的實例映射使用Rajaraman等人［15］提出的詞頻—逆文檔（TF-IDF）技術計算屬性值相似性分數然后進行合并。時間關系是指兩個流程在時間線上包含重疊的部分，然后對每個主流程實例選擇屬性值相似性分數最大的子流程實例與之合并。文獻［13，14］提出的基于規則以及規則建議算法需要對日志的領域知識有一定的了解，從而根據日志的特點選擇特定的規則對實例進行匹配，建立實例間的映射關系。
以上方法適合于要合并的日志中包含較多的屬性值，且在涉及時間關系的要求上都認為子流程在事件結束后會給予主流程反饋，從而在時間方面認為兩段流程在時間上有重疊的部分。而當事件日志中僅包含事件名稱和時間戳，或剩余的屬性值對合并意義不大時，以上方法則顯得能力不足。另外，真實的事件日志中也包含一種情況，即主流程的最后一個事件發生后，由于流程特性或系統延遲，子流程不會立即給予反饋或有事件的發生，從而導致兩者不具備重疊的時間線。所以對于該類日志的合并，采用上述方法的合并效果也不是很好。
2 相關概念
事件日志由多條過程實例組成，而每條過程實例由一個或多個事件組成，每個事件包含自身的屬性值，如實例標志符、時間戳、耗費資源、發起人等，其中實例標志符和時間戳屬性值必須包含，前者表示擁有相同實例標志符的事件歸屬于同一過程實例，而時間戳用來確定過程實例中活動的執行順序。
定義1 事件日志。設Γ是活動的有限集合，Γ上定義的日志為L=（ε，δ，α，β，θ，lt;），其中，ε是事件集，δ是實例標志符集，α：ε→δ是將事件鏈接到實例的滿射函數，β：ε→Γ是將事件鏈接到活動的滿射函數，θ：ε→Τ 是將事件鏈接到時間戳的滿射函數，lt;ε × ε是事件按照時間戳排序。
定義2 過程實例。給定一個事件日志L，將包含同一實例標志符δ的所有事件ε按照時間戳排序得到的執行序列s。
定義3 主流程，子流程。給定兩個事件日志L1、L2。若L1中的軌跡s1和L2中的軌跡S2屬于同一流程，給出軌跡s1的第一個事件的時間戳Τ1，s2的第一個事件的時間戳Τ2，當Τ1lt;Τ2時，則L1 先執行的是主流程，L2由L1觸發執行的是子流程。
定義4 時間差。歸屬于同一流程實例的兩個軌跡合并后按照時間戳排序，存在系統A的事件x結束后執行系統B的事件y，則y跨系統直接跟隨依賴于x，表示為x→y，由x到y所需的時間稱為時間差Τx→y。
定義5 時間差約束。由時間差的最小值與最大值構成的區間，即［min（Tx→y），max（Tx→y）］。
3 基于時間差約束的日志合并算法
3.1 算法概述
Weske［16］認為業務流程是一組跨越時間和空間的相關活動的集合，它們實現了特定的服務或業務目標，因此時間是分析業務流程的一個重要方面［17，18］。根據業務流程中活動的時間信息對分散在多個系統的日志進行合并，為在兩個日志中尋找實例映射關系，假設：a）事件屬性必須包含事件名稱、時間戳這兩種屬性；b）兩個系統記錄的事件的時間戳準確且精確。
本文假設僅合并兩個日志，一個與主流程有關，一個與子流程有關。用M表示主流程，S表示子流程。p、q分別表示主流程、子流程包含過程實例的個數。M中包含同一過程實例標志符的執行序列表示為〈m1，m2，…，mx，mx-1〉，時間順序為〈Tm1，Tm2，…，Tmx，Tmx-1〉。S中包含同一過程實例標志符的執行序列表示為〈s1，s2，…，sy-1，sy〉，時間順序為〈Ts1，Ts2，…，Tsy-1，Tsy〉。
以下為具體的合并步驟：
a）通過Prom獲得兩個日志的過程模型。文獻［19］介紹了Prom軟件中集合了大量與過程挖掘相關的插件，其中包括關于挖掘過程模型的插件。
b）根據領域知識區分主流程與子流程，再由流程間事件的跨系統跟隨依賴關系得到合并模型，從而確定流程間的時間關系。
關于時間關系，應用Allen［19］提出的區間代數。根據Allen的區間代數，任意兩個流程之間可能存在13種時間關系，如表1所示。根據定義3，將完整且正確執行的端到端的流程視為主流程與子流程應遵循以下順序：a）主流程先執行，然后觸發子流程；b）子流程與主流程重疊且子流程的開始時間介于主流程的開始時間到結束時間；c）主流程可在子流程啟動后的任何時間結束，同樣子流程也可在啟動后的任何時間點結束，其與主流程的結束時間無關；d）當子流程可以不向主流程提供反饋或系統之間未同步時，主流程和子流程在時間線上可以有未重疊的部分。
從時間關系表中看到，序號1表示的是主流程結束后不久子流程開始執行，序號3、5、8、12表示的是主流程在執行過程中觸發子流程，這滿足上文中提到的主流程與子流程應遵循的順序。因此本文算法認為兩個軌跡之間滿足序號1、3、5、8和12的時間關系是合并的先決條件。
實際上，大多數真實的流程是在時間約束下完成的，文獻［20］提出流程中活動的持續時間或兩個相接活動的執行時間的差值在一定范圍內。例如，銀行從客戶處收到的房屋抵押申請必須在規定的時間內完成信用檢查、財產評估、產權查詢等步驟，每個階段都有明確的截止日期。同樣地，就醫過程中的一些治療步驟也有明確的時間規定，如放射科醫生需要在CT掃描后24小時內提交報告，患者需要在康復兩天后才能出院等。根據此理論以及定義4，滿足先決條件的主流程與子流程在合并后，跨系統相接的活動的執行時間差值要落在定義5所給出的區間。這是合并的第二條件，也是本文算法的核心思想：基于時間差約束對日志進行合并。假設根據領域知識s1在ma之后發生，sy在md之前發生，子流程包含于主流程，則活動間的跨系統跟隨依賴關系為ma→s1，sy→md，則合并后的流程應為〈m1，…，ma，s1，…，sy-1，sy，md，…，mx-1，mx〉。
c）將Mi（i（1，p））與sj（j（1，q））進行一對一合并，并將每一個合并結果RMi×Sj按照時間戳順序排列，然后將與上述得到的合并模型路徑一致的合并結果放在集合set1中。對于set1中的合并結果RMi×Sj，若對于Mi僅有唯一的Sj與之合并和對于Sj僅有唯一的Mi與之合并，則將該RMi×Sj放入集合set2中，set2中的所有RMi×Sj即為第一次合并的日志，然后在set1中刪除已經合并過的Mi與Sj。
d）在沒有掌握時間約束的領域知識時，根據已經合并的日志推斷時間差約束。因此，對于set2或set4（步驟e）提及）中的所有RMi×Sj，得到ma→s1的時間差約束TDCma→s1=［min（Tma→s1），max（Tma→s1）］以及sy→md的時間差約束TDCsy→md=［min（Tsy→md），max（Tsy→md）］，并以這兩個時間差約束對剩余日志進行合并。
e）對于set1中剩余的每一個RMi×Sj，計算Ts1-Tma、Tmd-Tsy是否分別落在TDCma→s1和TDCsy→md的區間內。若均落在區間內，將該RMi×Sj放入集合set3中。對于set3中的每一個合并結果RMi×Sj，若對于Mi僅有唯一的Sj與之合并和對于Sj僅有唯一的Mi與之合并，則將該RMi×Sj放入集合set4中。set4中的所有RMi×Sj即為第二次合并的日志，然后在set1中刪除已經合并過的Mi與Sj。
重復以上最后兩步，直到所有日志均合并或根據時間差約束無法對日志進行一對一合并。對于多日志的合并，假設其中一個為主流程，剩余日志為子流程，然后將主流程與其中一個子流程按照上述步驟進行合并，合并完成后繼續將其與剩余的子流程繼續合并，直到所有流程均已合并。
3.2 算法示例
為了說明本文提出的合并方法，考慮一個簡單的示例流程。每一個信貸過程中用戶都可提交其信貸申請，然后銀行將會選擇是否接受其信貸請求登記。若通過，則用戶需提交相應的文件以供審查，最后銀行通過多次審查從而決定是否通過信貸請求。用戶流程作為主流程，銀行流程作為子流程。表2顯示了主流程的簡化日志，而子流程的簡化日志M在表3中給出。
b）確定活動間的跨系統跟隨依賴關系register（M）→refusal of requests（S），register（M）→acceptance of requests（S）→submit documents（M）→check（S），然后得到用戶流程和銀行流程之間需滿足表1中的序號1和5所列的時間關系。而合并后的模型如圖3所示，（M）表示用戶流程的活動，（S）表示銀行流程的活動。
c）將用戶流程的五個軌跡和銀行流程的五個軌跡進行一一合并得到25條合并軌跡，并將軌跡中的活動按照時間戳排序；然后將合并軌跡與合并模型進行一致性檢查，即在模型上重放合并軌跡，留下與合并模型中路徑一致的合并軌跡，共七條；最后從這七條合并軌跡中得到一對一的實例對，即唯一主流程軌跡與唯一子流程軌跡可以合并，共三條，則這三條軌跡為第一次合并的日志。
d）從上個步驟合并的三條日志中得到時間差約束，如表4所示。橫向表示該條合并軌跡中所有跨系統相接的活動對的執行時間的差值，縱向表示所有合并軌跡中給定的跨系統相接的活動對的執行時間的差值。對于一對多的實例對，計算每一個合并軌跡中跨系統相接的活動對之間的時間差是否滿足對應的時間差約束，然后從滿足所有時間差約束的實例對中繼續挖掘一對一的實例對。
根據表5顯示，主流程軌跡ID10001與子流程軌跡ID30001合并以及主流程軌跡ID10002與子流程軌跡ID30002合并之后滿足所有時間差約束且為一對一的實例對。以主流程軌跡ID10001與子流程軌跡ID30001合并為例，其register→accept＼refuse的時間差24h29m落在［23h17m，45h22m］內，accept→submit的時間差24h49m落在［24h12m，28h22m］內，submit→agree＼disagree的時間差97h5m落在［96h23m，98h11m］內，所有時間差均滿足約束。主流程軌跡ID10002與子流程軌跡ID30002合并后同理。由此這兩條合并軌跡即為第二次合并的日志。到此所有日志均已合并完畢。合并過程如圖4所示。
3.3 算法偽代碼
根據上述內容，該算法合并兩個日志，一個是主流程，一個是子流程，最后生成一個單一的日志文件。算法主要使用的變量與函數如下：
*model（log）：日志生成的模型。
**match_time_window（case1，case2）：檢查case1（main log）和case2（sub log）合并后是否與合并模型路徑一致。
**merge_trace（case1，case2）：合并與模型路徑一致的case1（main log）和case2（sub log），并將活動按照時間戳排序。
**log_time_difference（log）：若在merge_trace中對于case1只有唯一的case2與之合并且對于case2僅有唯一的case1與之合并，則將所有一對一的日志進行合并得到merge_log，然后得到其所有時間差約束log_time_diff。
**case_time_difference（case1，case2）：計算case1（main log）和case2（sub log）合并之后的所有時間差case_time_diff。
**satisfy_time_difference（case1，case2）：對于case1（main log），若有多條case2（sub log）與之合并后的match_time_window為true，則根據case_time_diff判斷是否滿足log_time_diff。若對于case1（main log），存在唯一的case2（sub log）與之合并后滿足所有時間差約束，則將它們進行合并。
算法1 合并事件日志
輸入：主流程日志；子流程日志。
輸出：合并日志。
1）得到與合并模型路徑一致的合并軌跡
for all case_id∈main log do：
for all case_id∈sub log do：
if match_time_window{case1（main log），case2（sub log）}：
merged_trace=merge_trace（case1（main log），case2（sub log））
end if
end for
end for
return merged_trace
2）合并 merged_trace 中一對一的日志
for case1，case2 in merged_trace：
if num（case2）=1 and num（case1）=1：
merge_log=merge_trace（case1（main log），case2（sub log））
end if
end for
return merge_log
3）計算merge_log的所有時間差約束
log_time_diff=log_time_difference（merge_log）
4）計算 merged_trace中無法一對一合并的日志的時間差
for case1 in merged_trace：
if num（case2）gt;1：
case_time_diff=case_time_difference（case1，case2））
end if
end for
return case_time_diff
5）合并滿足時間差約束且為一對一的日志
for case1 in case_time_diff：
if satisfy_time_difference（case1，case2） and num（case2）=1：
merge_log=merge_trace（case1（main log），case2（sub log））
end if
end for
return merge_log
算法復雜度分析：該算法涉及到多個函數，其中match_time_window（case1，case2）復雜度最高，由兩層for循環組成，其時間復雜度為p×q。其中p為主流程的軌跡個數，q為子流程的軌跡個數。
3.4 軌跡分類
事件的跨系統跟隨依賴關系基于特定事件之間的順序關系或流程片段之間的包含關系。對于簡單的順序模型，發現確切的事件跨系統跟隨依賴關系相對來說比較簡單。而對于復雜模型，軌跡的種類繁多，若想找到確切的事件跨系統跟隨依賴關系具有困難。因此可以將各自系統內的軌跡進行分類或聚類，使得同類型的軌跡聚集在一起，然后挖掘同類型軌跡的模型，從而使得模型變得簡單，事件的跨系統跟隨依賴關系也更為確切。而將各自系統內的軌跡進行分類的方法主要包含事件個數、事件順序、聚類算法等，對于實際日志要進行實際分析。
3.5 軌跡分割
為提高日志的合并速度，可以在合并前將日志進行分割。例如，若主流程的事件x和y之間穿插了子流程，則計算主流程的事件x傳遞到事件y所需時間的最小值與最大值，然后構成時間差區間［min（Tx→y），max（Tx→y）］。將主流程的事件日志按照時間單位小時、天或月將其分割，對應地將子流程的事件日志也根據時間差區間進行分割，這樣使得相對應的事件日志文件中的主流程的軌跡和子流程的軌跡合并后的時間差必須落在區間之內，再從中選擇一對一的實例對進行合并。由此減少了合并范圍，再通過并行化合并分割日志，日志合并速度可以得到明顯提升。
3.6 評價指標
將真實的事件日志進行分離得到兩個事件日志，運用合并算法得到的結果與真實結果可以比較，使用精確率（precision）和召回率（recall）作為評價指標。
1）精確率 又稱查準率，指出合并的過程實例中有多少樣本是正確的合并，強調準確性。其計算公式如式（1）所示。
其中：correct number表示正確合并的實例對個數；number of cases merged表示合并的實例對個數。
2）召回率 又稱查全率，指出待合并的樣本中有多少實例被正確合并，強調覆蓋度。其計算公式如式（2）所示。
其中：correct number表示正確合并的實例對個數；number of cases to be merged表示需要合并的實例對個數。
4 實驗結果與分析
4.1 實驗數據
在4tu網站（https：//data.4tu.nl/）中下載了一些數據集，選用了electronic invoicing和sepsis cases兩個具有代表性的數據集。前者包含的活動數量較少且流程較為簡單，而后者包含的數量較多且流程較為復雜，這兩個數據集中的一些活動的執行時間都是在一定的范圍內。針對需要合并的事件日志，若其系統中的活動在具有明確的時間約束時，該方法具有普適性。
實驗所采用的兩個數據集中的事件日志都是完整的執行序列，為驗證本文算法，事件日志被拆分為兩部分。electronic invoicing事件日志拆分為處理過程和批準過程，sepsis cases事件日志拆分為處理過程和治療過程。每個過程包含的活動個數以及過程實例個數如表6所示，而拆分后的部分過程實例樣本分別如圖5～8所示，其中第一列代表軌跡的ID，第二列代表活動名稱，第三列代表活動發生的時間戳。
4.2 electronic invoicing數據集
首先挖掘兩個事件日志的過程模型，模型如圖9、10所示。
在合并前，發現兩個事件日志軌跡中的事件個數均可分類成三種情況：處理系統中軌跡包含事件的個數有4、6和7個，與之對應的批準系統中軌跡包含事件的個數有1、3和4個。由此將軌跡按照包含事件個數進行分類得到三個小的合并過程模型，而從各自模型中挖掘確切的跨系統跟隨依賴關系也更為簡單、直接。圖11～13分別表示流程合并后的模型1～3。
屬于合并模型1的日志共包含4 230條日志，其合并過程以及評價指標如表7所示。
屬于合并模型2的日志共包含10 726條日志，其合并過程以及評價指標如表8所示。
屬于合并模型3的日志共包含5 179條日志，其合并過程以及評價指標如表9所示。
對于該數據集的模型1添加了日志分割實驗。由于處理系統中的invoice scanning和end兩個事件之間穿插了子流程的approve invoice事件，而invoice scanning到end會在一天之內完成。由此合并日志前，以天為基本單位對主流程的日志文件進行分割，使得分割后的日志文件中所有軌跡的第一個事件——register同屬于一天。相對應地，將子流程的日志同樣按照天為單位進行分割使得與主流程分割后的日志文件相對應。由此總的日志被分割成了以天為單位的25個事件日志文件，這一步驟既減少了主流程合并的范圍，并且25個事件日志同時合并加快了合并速度。相比于直接進行日志合并，按照事件日志特點對文件進行分割后再進行日志合并，使得總的合并性能提升。
4.3 sepsis cases數據集
首先挖掘處理過程和批準過程各自的過程模型，模型分別如圖14、15所示。
根據現實中治療過程總是包含在處理過程中這一常識作為日志第一次合并的時間關系，即Tm1lt;Ts1。根據該時間關系合并一對一的實例映射對，然后從已經合并過的日志中挖掘更深層次的時間關系。在合并過程中，逐漸發現事件日志的特點。在處理系統中，軌跡包含的事件個數分為等于3和大于3，而治療過程作為一個整體步驟無法分割。由此將處理系統中的事件日志分成兩部分：a）軌跡包含的事件個數為3個；b）軌跡大于3個。將已經合并過的日志分為以上兩種情況，得到兩個小的模型，然后對模型再次進行細分。治療過程可包含在處理過程的位置也分為三種情況：a）在ER registration之后；b）在ER triage之后；c）在ER sepsis triage之后，由此小的模型再細分成三種類型。圖16、17分別表示模型1、2。
屬于模型1的日志共包含326條日志，其合并過程以及評價指標如表10所示。
屬于模型2的日志共包含682條日志，其合并過程以及評價指標如表11所示。
4.4 對比實驗
將上述兩個數據集使用基于人工免疫算法、基于恰當的時間關系和屬性值相似進行合并，但合并的效果非常不好，原因是由于數據集中兩個日志流程之間沒有重疊的時間關系，所以對本文方法進行修改。在上述算法中，取事件之間時間差的最小值和最大值構成時間差范圍，但是在實際的日志中可能會存在某個合并軌跡的時間差和其他軌跡的時間差相差較大，于是對時間差進行處理：首先，刪除離群點，從所有合并軌跡中得出事件間的時間差并畫出散點圖，找到離群點對其進行刪除；其次，根據過濾后的時間差按照時間差的頻數畫出時間差累計頻率分布直方圖；然后將時間差范圍取在時間差累計頻率落在0.05～0.95，從而縮小時間差范圍。以electronic invoicing數據集的模型1為例說明對比實驗的步驟。
首先對于第一次合并的日志，時間差的散點圖如圖18、19所示。
該模型中存在兩個跨系統的活動跟隨依賴關系，圖中方格內的點所對應的時間差明顯大于“正?！钡臅r間差，由此將其視為時間差的離群點，然后刪除所有離群點，得到scanning of extral documention到approve invoice的時間差為［48，94］ （單位為s，下同），approve invoice到end的時間差為［87，153］。將時間差按照出現頻數畫出累計頻率直方圖，如圖20、21所示。
將時間差范圍取在時間差累計頻率落在0.05～0.95，則scanning of extral documention到approve invoice的時間差范圍變成［50，91］，approve invoice到end的時間差范圍變成［97，143］。依據該時間差范圍對剩余日志進行合并。對于每一次得出的時間差都要經過上述兩個步驟處理再運用到下一次日志的合并。將修改后的算法應用到以上兩個數據集，兩個實驗的評價指標分別在表12、13中給出。
觀察圖22、23兩個算法的評價指標發現，若縮小時間差范圍則合并的條數將會減少，由此合并的覆蓋度減小，使得召回率下降。而由于時間差范圍的縮小，合并的正確條數會增加，所以精確率將會提升。
5 結束語
真實的業務流程可能由多個信息系統支持，而過程挖掘技術需要應用在一個單一的、統一的日志文件上，因此需要將分散在不同系統上的日志文件進行合并處理從而應用過程挖掘技術。本文方法僅考慮事件的名稱和時間戳兩種屬性，然后基于時間差約束對日志進行合并。該方法適合于事件日志中活動的執行具有明確的時間約束以及事件日志中僅包含活動名稱和時間戳這兩種屬性或其他屬性對合并日志無太大意義的日志，或者兩個流程間沒有重疊的時間線。而本文方法的不足在于，對于時間跨度較大的日志合并效果并不是很好，由于時間跨度較大的日志中的時間差約束的范圍也必將跨度很大，而這不利于軌跡間的一對一合并，從而使得該方法的合并效果并不好。未來的研究還包括許多方向，例如將本文算法應用到復雜關系日志的合并中。除此之外，在實際生活中，事件日志的數據量是龐大的，因此如何提高日志合并速度也是日志合并的關鍵要素，應用大數據處理技術和并行計算可以有效提高日志合并效率。因此，如何利用這兩種技術對日志進行并行合并也是以后的研究方向。
參考文獻：
［1］Van Der Aalst W，Van Hee K.工作流管理：模型、方法和系統 ［M］.王建民，聞立杰，譯.北京：清華大學出版社，2004.（Van Der Aalst W，Van Hee K.Workflow management：models，methods，and systems［M］.Wang Jianmin，Wen Lijie，trans.Beijing：Tsinghua University Press，2004.）
［2］Van Der Aalst W.業務過程的發現、合規和改進 ［M］.王建民，聞立杰，譯.北京：清華大學出版社，2011.（Van Der Aalst W.Process mining discovery，conformance and enhancement of business processes ［M］.Wang Jianmin，Wen Lijie，trans.Beijing：Tsinghua University Press，2011.）
［3］趙海燕，李欣歌，陳慶奎，等.面向業務過程挖掘和分析的事件日志預處理技術 ［J］.小型微型計算機系統，2022，43（1）：1-9.（Zhao Haiyan，Li Xinge，Chen Qingkui，et al.Event log preprocessing technology for business process mining and analysis［J］.Journal of Chinese Computer Systems，2022，43（1）：1-9.）
［4］Van Der Aalst W，Adriansyah A，De Medeiros A K A，et al. Process mining manifesto［C］//Proc of International Conference on Business Process Management.Berlin：Springer，2011：169-194.
［5］Marin-Castro H M，Tello-Leal E.Event log preprocessing for process mining：a review［J］.Applied Sciences，2021，11（22）：10556.
［6］Goel S，Bhat J M，Weber B.End-to-end process extraction in process unaware systems［C］//Proc of International Conference on Business Process Management.Berlin：Springer，2012：162-173.
［7］Claes J，Poels G.Merging computer log files for process mining：an artificial immune system technique［C］//Proc of International Confe-rence on Business Process Management.Berlin：Springer，2011：99-110.
［8］Xu Yang，Lin Qi，Zhao M Q.Merging event logs for process mining with hybrid artificial immune algorithm［C］//Proc of International Conference on Data Science.［S.l.］：Steering Committee of World Congress in Computer Science，Computer Engineering and Applied Computing，2016：10.
［9］徐楊，袁峰，林琪，等.基于混合人工免疫算法的流程挖掘事件日志融合方法 ［J］.軟件學報，2018，29（2）：396-416.（Xu Yang，Yuan Feng，Lin Qi，et al.Merging evet logs for process mining with a hybrid artificial immune algorithm［J］.Journal of Software，2018，29（2）：396-416.）
［10］Claes J，Poels G.Integrating computer log files for process mining：a genetic algorithm inspired technique［C］//Proc of International Confe-rence on Advanced Information Systems Engineering.Berlin：Springer，2011：282-293.
［11］Raichelson L，Soffer P.Merging event logs with many to many relationships ［C］//Proc of International Conference on Business Process Management.Cham：Springer，2014：330-341.
［12］Raichelson L，Soffer P，Verbeek E.Merging event logs：combining levels for process flow analysis ［J］.Information Systems，2017，71：211-227.
［13］Claes J，Poels G.Merging event logs for process mining：a rule based merging method and rule suggestion algorithm［J］.Expert Systems with Applications，2014，41（16）：7291-7306.
［14］Djedovic′ A，Karabegovic′ A，?unic′" E，et al.A rule based events correlation algorithm for process mining ［C］//Proc of International Symposium on Innovative and Interdisciplinary Applications of Advanced Technologies.Cham：Springer，2019：587-605.
［15］Rajaraman A，Ullman J D.Mining of massive datasets［M］.Cambridge：Cambridge University Press，2011.
［16］Weske M.Business process management architectures ［J］.Business Process Management，2012，5：333-371.
［17］Eder J，Panagos E，Rabinovich M.Workflow time management revisited ［M］//Business Process Management：Concepts，Languages，Architectures.Berlin：Springer，2013：207-213.
［18］Eder J，Panagos E，Rabinovich M，Time constraints in workflow systems ［M］//Seminal Contributions to Information Systems Enginee-ring.Berlin：Springer，1999：286-300.
［19］Allen J F.Maintaining knowledge about temporal intervals ［J］.Communications of the ACM，1983，26（11）：832-843.
［20］Kumar A，Barton R R.Controlled violation of temporal process constraints-models，algorithms and results［J］.Information Systems，2016，64：410-424.
［21］Van Dongen B V，De Medeiros A，Verbeek H，et al.The ProM framework：a new era in process mining tool support［C］//Proc of International Conference on Application and Theory of Petri Nets.Berlin：Springer，2005：444-454.
