基于多視角關聯規則的事件日志異常分析及過濾方法
2023-06-22 16:14:46胡偉
現代信息科技 2023年2期
摘? 要：事件日志的預處理是過程挖掘的第一步，事件日志中存在的大量噪音、低頻行為對過程挖掘造成了極大的困擾。以往的研究大多是從控制流角度出發，只考慮了活動之間的發生順序，較少涉及活動所包含的數據屬性。由此提出了在控制流關聯規則的基礎上進行數據流關聯規則的挖掘方法，首先基于Apriori算法挖掘出具有高度依賴關系的活動集合，再從數據流角度對事件日志進行過濾。具體的實例分析和仿真實驗驗證了方法的有效性。
關鍵詞：過程挖掘；關聯規則；Apriori
中圖分類號：TP391.9? ? 文獻標識碼：A? 文章編號：2096-4706（2023）02-0069-05
Event Log Anomaly Analysis and Filtering Method Based on Multi-View Association Rules
HU Wei
（School of Computer Science and Engineering， Anhui University of Science and Technology， Huainan? 232001， China）
Abstract： The preprocessing of event log is the first step of process mining. A lot of noise and low-frequency behavior in event log cause great trouble to process mining. From the perspective of control flow， most of the previous studies only consider the sequence of occurrence among activities， and rarely involve the data attributes contained in activities. Thus this paper puts forward the mining method of data flow association rules based on control flow association rules. Firstly， based on Apriori algorithm， it mines the set of activities with high degree of dependency relationship. Then it filters the event log from the perspective of the data flow. The effectiveness of the method is verified by the actual example analysis and simulation experiments.
Keywords： process mining; association rule; Apriori
0? 引? 言
關聯規則（Association Rules）反映了多個數據項之間的相互關系和依賴性，如最著名的“啤酒和尿布”營銷案例，就是利用了兩件商品之間的相互依賴關系，時至今日，關聯規則已成為數據挖掘領域的一個重要技術。而過程挖掘就是對事件日志中的知識進行提取、挖掘，從而去發現、監控、優化實際流程。在實際應用中，過程挖掘所用到的事件日志往往不是完備的，常常包含大量的低頻行為、噪音、異常，這對發現過程模型造成了嚴重的困擾，如何過濾掉事件日志中的噪音、無效低頻行為是過程挖掘研究的熱點。文獻[1]提出一種名為“日志自動機”的技術來自動過濾低頻行為。文獻[2]提出了一種利用關聯規則和模糊關聯規則的方法對異常行為進行檢測，判斷其是欺詐行為的可能性。文獻[3]則是從三個不同的視角控制流（活動）、時間（時間戳）、資源（活動執行資源）出發，檢測事件日志中的異常行為。文獻[4]重點從醫療領域的一系列實際流程出發，從數據流和控制流兩個角度將事件日志與模型進行對齊，分析和分類了數據預期目的和數據使用環境相關的偏差，并提供了一種新的算法來識別不一致的用戶行為。文獻[5]采用了一種將過程挖掘和關聯規則挖掘相結合的混合方法，通過關聯規則算法產生的正負規則與事件日志進行一致性檢查來判斷異常行為，與單純的過程挖掘方法相比，混合方法具有更低的錯誤發現率和更高的準確度，在該方法中，最佳的準確度取決于一定的置信閾值。
本文將活動的名稱、資源、時間戳視為活動自帶的內部屬性，通過探索屬性之間的關聯規則篩選出合法活動與異常活動。本文不僅考慮單個活動是否符合流程規則，更進一步地考慮活動與活動之間的關聯規則，并通過根據Apriori算法計算出的關聯規則區分出合法行為和異常行為，并以此對事件日志進行過濾。
1? 基本概念
定義1（事件日志）：業務流程的執行以事件日志的形式記錄下來，設一個事件日志L是一組執行跡的集合，日志跡t=
（1）ea：事件的執行活動，這里用活動名稱表示。
（2）er：事件的執行資源，表示活動是由特定角色或系統執行。
（3）et：事件執行所需的時間，由活動的開始時間戳、結束時間戳以及相關的隸屬度函數確定。
（4）es：活動執行的開始時間戳，任意eies＞0∩
eies∈R。
（5）ec：活動執行的結束時間戳，任意eiec＞0∩
eiec∈R。
例如表一中的跡t1中的事件e1=（A，Tom，0，5，Low），A代表e1執行的活動，Tom表示A活動是由Tom執行，0、5表示A活動的開始時間戳與結束時間戳，因為時間屬性屬于模糊數，為了方便定義與后續的計算，本文將時間分為三個等級，通過相關的隸屬度函數確定其等級，Low表示該活動執行所需的時間等級為低。
圖1中橫坐標表示活動的執行所需的總時間，由ec-es計算所得。縱坐標表示隸屬度。
根據圖1的隸屬度函數可以確定活動執行時間的等級，使用三種不同顏色的曲線表示三種不同的等級（Low，Middle，High），通過隸屬度的不同確定其歸屬的等級。如表1中事件e1es=0，e1ec=5，事件e1的活動執行所需時間為5，通過隸屬度函數可知e1et=Low，其隸屬度為0.25。
定義2（規則）：設R=（rc，rd）為關聯規則的集合，其中rc=（rcea1，rcea2，…，rcean）代表控制流的關聯規則，即只涉及活動與活動之間的關聯規則。rd=（rdea，rder，rdet）代表數據流（包含資源er、時間et）的關聯規則，用rdet∈{Tom，Eve，…，Mike，Alan}表示數據流規則包含的資源屬性et，用rdet∈{Low，Middle，High}表示數據流規則包含的時間屬性et。其中rc滿足以下條件：
（1）rcea1是rcea2的前繼活動，如對于跡L1={A，B，C}，rcea1=A，則rcea2=B。
（2）對于一個規則rc，當且僅當n≥2是成立。
對于數據流規則rd，滿足以下條件：
（1）rdea≠?且唯一。
（2）同一規則的資源和時間屬性都歸屬于同一活動。
即單個數據流規則只考慮單個活動的內部屬性之間的關聯，而控制流規則更多是考慮多個活動（至少兩個活動）之間的關聯。
2? 基于關聯規則的異常分析
流程挖掘是一個新興領域，專門用于從事件日志中記錄的實際數據中獲取知識[6]。但是事件日志中往往存在異常或者偏差，即噪音，噪音的存在會影響業務流程的結構。事件日志存儲有關流程的重要信息。反過來，對這些信息的分析可以讓公司追蹤其系統中記錄的實際數據和事件[7]。本文通過對控制流和數據流兩個不同角度的關聯規則分析活動與活動之間以及活動與資源、時間等屬性的特定關系，首先在控制流角度挖掘出滿足最小支持度（最小支持度根據實際結果人為設置）的頻繁項集，計算其置信度是否達到設置的閾值（最小置信度）。對于達到最小置信度的規則將其稱為合規規則[8]，而對于只包含合規規則的事件日志還需對日志進行數據流的關聯規則挖掘，從而將事件日志中的噪音進行過濾。
關聯規則學習是一種無監督的數據挖掘方法，旨在發現大量數據中項與項之間相關關系[9]。在這里，本文將關聯規則學習應用于過程挖掘領域，將多個相關聯的事件中的活動集合視作一個項集，利用先驗算法[10]滿足閾值（最小置信度）的頻繁項集，具體方法流程通過一個實際案例展示。
2.1? 控制流關聯規則挖掘
控制流描述了流程的執行順序，是判斷流程是否合規的第一步，首先給出支持度與置信度的相關定義。
定義3（支持度）：支持度表示事件日志中該項集所占的比例，X代表一組活動集合（項集）中的前繼活動，Y代表X的后繼活動。對于項集（A，B）其支持度表示活動A、B共同在事件日志中出現的比例。
Support（X，Y）=P（X∪Y）
定義4（置信度）：置信度表示前繼活動出現后期后繼活動出現的概率，項集（A，B）的置信度表示在A活動發生之后B活動發生的概率。
算法1 控制流關聯規則挖掘方法：
輸入：事件日志L={t1，t2，t3，…，tn}，最小支持度Min_Supt和最小置信度Min_Conf；
輸出：控制流關聯規則；
步驟1：對事件日志L={t1，t2，t3，…，tn}進行預處理，計算日志中所有活動的出現次數，將活動出現的次數除以日志所包含的跡的總數，得到每個活動的支持度，大于等于最小支持度的活動作為初始的頻繁一項集。
步驟2：將步驟1中得到的頻繁一項集進行兩兩組合，組成不相同的二項集，再分別計算每個二項集的支持度，保留大于或等于最小支持度的二項集作為頻繁二項集。
步驟3：不斷重復步驟2的操作，將上個步驟得到的頻繁K項集兩兩組合得到頻繁K+1項集，如果頻繁K+1項集為空則算法返回頻繁K項集，如果頻繁K+1項集只有一項，直接返回頻繁K+1項集，計算其置信度，大于等于最小置信度的頻繁K+1項集作為算法結果返回，算法結束。
下面是其偽代碼：
Algorithm 1 控制流關聯規則挖掘算法
Input：事件日志L={t1，t2，t3，…，tn}，最小支持度Minsupport，最小置信度Minconfidence
Output：控制流關聯規則集合Rc={rc1，rc2，…，rcn}
1：for m = 1 → M do //m 表示迭代次數
2：? ? C ? Findfrequentitem //初始化項集
3：? ? for i = 1 → n do //循環遍歷項集
4：? ? supportCi ? Support（Ci） //計算當前項集的支持度
5：? ? if then supportCi ≤ Minsupport
6：? ? ? ? ? ?Item1 ? Item1 ∪ {Ci} //將低于最小支持度的項集劃分到相應的集合
7：? ? else
8：? ? ? ? ? ? ?Item2 ? Item2 ∪ {Ci}
9：? ? end if
10：? end for
11：? ? ? ? ?Cditem = cd1，cd2，…，cdn ? CandidateItem（） ? RanAssort（Item2） //將頻繁項集隨機組合成頻繁候選集
12：? for i = 1 → n do
13：? Confidcdi ? Confidence（cdi）//計算其置信度
14：? if then? Confidcdi ≤ Minconfidence //判斷是否小于最小置信度
15：? break? Rc ? Rc ∪ {cdi}
16：? return Rc //輸出結果
2.2? 數據流關聯規則挖掘
由算法1得到的控制流規則從事件日志中提取出了相互關聯、相互依賴的活動集合，在實際的應用流程中，如信貸申請流程中接受申請活動往往與核實申請人信息活動綁定在一起，又比如在醫療領域流程中病人在接受檢查之后醫生才能為其指定治療方案。但控制流關聯規則只能挖掘活動與活動之間的依賴關系，而對于流程中出現的數據流異常卻無能為力，如在信貸申請流程中，大額貸款的申請需要經理同意才能得到批準，這就對活動的執行資源進行了限制，數據流關聯規則針對活動與資源、時間等屬性的依賴關系進行挖掘，有效解決了事件日志中數據流的異常行為。
算法 2 數據流關聯規則挖掘方法：
輸入：算法1得到的控制流關聯規則，事件所包含的所有屬性（資源er，活動ea，時間et）；
輸出：數據流關聯規則；
步驟1：將控制流關聯規則所包含的事件的所有屬性作為初始的三項集，即包含活動ea、資源er、事件et的三項集。
步驟2：分別計算由不同資源和時間執行同一活動的事件的支持度，與算法1類似，保留大于等于最小支持度的三項集作為頻繁項集。
步驟3：再通過計算頻繁項集的置信度得到數據流關聯規則，作為算法結果返回，算法結束。
下面是其偽代碼：
Algorithm 2 數據流關聯規則挖掘算法
Input：事件日志L={t1，t2，t3，…，tn}，最小支持度Minsupport，最小置信度Minconfidence，活動ea，資源er，開始時間es，結束時間ec，數據流項集，df
Output：數據流關聯規則集合Rd={rd1，rd2，…，rdn}
1：for m = 1 → M do //m 表示迭代次數
2：? ? C ? Findfrequentitem //初始化項集
3：? ? for i = 1 → n do //循環遍歷項集
4：? ? ? et ? Membership（es，ec） //通過隸屬度函數確定執行時間 et 的級別
5：? ? ? supportdf ? Support（ea，er，et） //計算當前項集的支持度
6：? ? if then supportdf ≤ Minsupport
7：? ? ? ? Item1 ? Item1 ∪ {df } //將低于最小支持度的項集劃分到相應的集合
8：? ? else
9：? ? ? ? Item2 ? Item2 ∪ {df }
10：? end if
11：? end for
12：? Df Cditem = cd1，cd2，…，cdn ? CandidateItem（） ? RanAssort（Item2） //將頻繁項集隨機組合成頻繁候選集
13：? for i = 1 → n do
14：? Confidcdi? ? Confidence（cdi）//計算其置信度
15：? if? ?thenConfidcdi? ≤ Minconfidence //判斷是否小于最小置信度
16：? break Rd ? Rd ∪ {cdi}
17：? return Rd //輸出結果
3? 實例分析及仿真實驗
為驗證上述方法的可行性，以銀行信貸申請流程為例，首先客戶提交貸款申請，銀行在收到貸款申請之后會核實客戶的個人信息，檢查其申請資料是否完整合格，申請通過之后客戶需辦理擔保手續，將抵押物抵押給銀行，銀行會根據抵押物品類、價值的不同決定貸款金額的大小，而大額貸款的同意往往需要經理同意才能簽訂貸款合同，合同簽訂完銀行才會發放貸款資金到客戶的賬號上。表2是給出的一個事件日志實例，其中e1表示提交貸款申請，e2表示核實客戶信息，e3表示檢查申請資料，e4表示根據貸款金額選擇抵押品類，e5表示房屋抵押貸款，e6表示車輛抵押貸款，e7表示股權抵押貸款，e8表示評估抵押品的價值，e9表示辦理擔保手續，e10表示檢查手續是否合規，e11表示貸款交由經理處理，e12表示貸款交由職員處理，e13表示簽訂貸款合同，e14表示檢查貸款合同是否合規，e15發放貸款金額，e16表示拒絕貸款請求。
表2中的事件日志已按頻數從大到小進行排序，首先對事件日志應用算法1進行控制流關聯規則的挖掘，對于事件日志中所有的事件{e1，…，e16}，將單個事件作為一項集，由定義3計算支持度，如二項集{e1，e4}的支持度為：
這里最小支持度設為0.15，大于等于最小支持度的予以保留，得到頻繁一項集。再根據算法1將得到的頻繁一項集兩兩組合成二項集，通過定義3計算二項集的支持度，剔除小于最小支持度的二項集得到頻繁二項集。不斷重復以上操作，可以得到頻繁K項集，直到算法終止如圖2所示。由于篇幅原因，這里只計算到頻繁三項集，對于頻繁三項集，通過定義4計算三項集{e7，e9，e10}的置信度，此處將e7視作X，（e9，e10）視作Y
同樣的，此處將最小置信度設為0.2，關聯規則（e7，（e9，e10））的置信度為0.55，即在事件e7發生之后（e9，e10）發生的概率為0.55，大于最小置信度，說明兩者之間關聯度較高，在控制流上具有很強的相互依賴性。
在對事件日志應用完算法1之后，對得到的控制流關聯規則應用算法2，為了方便計算演示，只對關聯規則（e7，（e9，e10））應用算法二，而包含該關聯規則只有t3，表3給出了部分事件日志所包含的數據流屬性。
表3還給出了規則中的事件在不同的執行資源和執行時間下所對應的支持度，最小支持度設為0.15，由表3可知，（e7，Eve，Hgih）的支持度遠遠小于最小支持度，這在實際應用中表現為往常股權抵押貸款是由Tom負責，而某次股權抵押貸款負責人不是Tom，變成了由Eve負責，這種異常行為控制流無法檢測，因為在控制流角度其事件的執行順序并無異常，只是事件的執行資源出現異常，而通過對數據流規則的挖掘，能夠在控制流正常的情況下發現其屬性異常。對于（e10，Alan，High），其執行時間出現了異常，因此其支持度也不滿足條件。
為了驗證本文提出的方法的有效性，將本文提出的方法與啟發式挖掘方法的適合度進行了比較，適合度指的是流程模型重現事件日志所包含的流程行為的能力，適合度測量值為0表示無法重現日志中記錄的任何行為，而值為1表示能夠重現所有記錄的行為。由圖3的一致性度分析結果可知，本文提出的方法在事件日志實例數較多的情況下有著更好的表現。
由以上可知，通過對事件日志中控制流和數據流兩個角度關聯規則的挖掘，在基于發生頻率的基礎上計算不同規則（項集）的支持度以及置信度，通過對閾值（最小支持度、最小置信度）的設置，可以篩選出符合要求的事件日志。
4? 結? 論
本文在基于以往的研究基礎上，給出了從控制流以及數據流兩個角度進行關聯規則挖掘對事件日志進行過濾和異常分析的方法，首先基于流程中活動的發生順序以及頻率挖掘事件日志中具有緊密關聯的活動集合（項集），通過計算其支持度，也就是在事件日志中發生的概率，找出在事件日志中一起頻繁發生的活動集合，即控制流關聯規則。再對控制流關聯規則中所包含的單個事件的活動、資源、時間等屬性進行數據流關聯規則的挖掘，這里的時間通過時間戳以及隸屬度函數確定，從而解決了單一控制流規則無法發現屬性異常的缺陷，有效減少了事件日志中的噪音對過程挖掘的影響。
本文是從兩個不同角度對事件日志進行過濾，未來還要對過濾后的事件日志應用過程挖掘算法挖掘過程模型，再對挖掘出的過程模型與事件日志進行控制流與數據流兩種角度對齊操作，從而更好的驗證對模型精度的提升。
參考文獻：
[1] CONFORTI R，LA ROSA M，HOFSTEDE A H M. Filtering out infrequent behavior from business process event logs [J].IEEE Transactions on Knowledge and Data Engineering，2016，29（2）：300-314.
[2] SARNO R，SINAGA F，SUNGKONO K R. Anomaly detection in business processes using process mining and fuzzy association rule learning [J].Journal of Big Data，2020，7（1）：1-19.
[3] B?HMER K，RINDERLE-MA S. Association rules for anomaly detection and root cause analysis in process executions [C]//International Conference on Advanced Information Systems Engineering.Cham：Springer，2018：3-18.
[4] ALIZADEH M，Lu X，FAHLAND D，et al. Linking data and process perspectives for conformance analysis [J].Computers & Security，2018，73：172-193.
[5] SARNO R，DEWANDONO R D，AHMAD T，et al. Hybrid Association Rule Learning and Process Mining for Fraud Detection [J].IAENG International Journal of Computer Science，2015，42（2）：59-72.
[6] LEE C K H，TSE Y K，HO G T S，et al. Fuzzy association rule mining for fashion product development [J].Industrial Management & Data Systems，2015，115（2）：383-399.
[7] DENISOV V，FAHLAND D，VAN DER AALST W M P. Repairing event logs with missing events to support performance analysis of systems with shared resources [C]//International Conference on Applications and Theory of Petri Nets and Concurrency. Cham：Springer，2020：239-259.
[8] NOLLE T，LUETTGEN S，SEELIGER A，et al. Binet：Multi-perspective business process anomaly classification [J/OL].Information Systems，2022，103：1-12[2022-06-20].https：//arxiv.org/pdf/1902.03155.pdf.
[9] FANI SANI M，ZELST S J，VAN DER AALST W M P. Repairing outlier behaviour in event logs [C]//International Conference on Business Information Systems.Cham：Springer，2018：115-131.
[10] TAGHIABADI E R，GROMOV V，FAHLAND D，et al. Compliance checking of data-aware and resource-aware compliance requirements [C]//OTM Confederated International Conferences" On the Move to Meaningful Internet Systems". Berlin：Springer，2014：237-257.
作者簡介：胡偉（1997—），男，漢族，安徽安慶人，碩士在讀，研究方向：過程挖掘。
收稿日期：2022-07-26
基金項目：國家自然科學基金項目（61572035，61402011）
