摘? 要：事件日志的預處理是過程挖掘的第一步，事件日志中存在的大量噪音、低頻行為對過程挖掘造成了極大的困擾。以往的研究大多是從控制流角度出發(fā)，只考慮了活動之間的發(fā)生順序，較少涉及活動所包含的數(shù)據(jù)屬性。由此提出了在控制流關(guān)聯(lián)規(guī)則的基礎(chǔ)上進行數(shù)據(jù)流關(guān)聯(lián)規(guī)則的挖掘方法，首先基于Apriori算法挖掘出具有高度依賴關(guān)系的活動集合，再從數(shù)據(jù)流角度對事件日志進行過濾。具體的實例分析和仿真實驗驗證了方法的有效性。

關(guān)鍵詞：過程挖掘；關(guān)聯(lián)規(guī)則；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? 引? 言

關(guān)聯(lián)規(guī)則（Association Rules）反映了多個數(shù)據(jù)項之間的相互關(guān)系和依賴性，如最著名的“啤酒和尿布”營銷案例，就是利用了兩件商品之間的相互依賴關(guān)系，時至今日，關(guān)聯(lián)規(guī)則已成為數(shù)據(jù)挖掘領(lǐng)域的一個重要技術(shù)。而過程挖掘就是對事件日志中的知識進行提取、挖掘，從而去發(fā)現(xiàn)、監(jiān)控、優(yōu)化實際流程。在實際應用中，過程挖掘所用到的事件日志往往不是完備的，常常包含大量的低頻行為、噪音、異常，這對發(fā)現(xiàn)過程模型造成了嚴重的困擾，如何過濾掉事件日志中的噪音、無效低頻行為是過程挖掘研究的熱點。文獻[1]提出一種名為“日志自動機”的技術(shù)來自動過濾低頻行為。文獻[2]提出了一種利用關(guān)聯(lián)規(guī)則和模糊關(guān)聯(lián)規(guī)則的方法對異常行為進行檢測，判斷其是欺詐行為的可能性。文獻[3]則是從三個不同的視角控制流（活動）、時間（時間戳）、資源（活動執(zhí)行資源）出發(fā)，檢測事件日志中的異常行為。文獻[4]重點從醫(yī)療領(lǐng)域的一系列實際流程出發(fā)，從數(shù)據(jù)流和控制流兩個角度將事件日志與模型進行對齊，分析和分類了數(shù)據(jù)預期目的和數(shù)據(jù)使用環(huán)境相關(guān)的偏差，并提供了一種新的算法來識別不一致的用戶行為。文獻[5]采用了一種將過程挖掘和關(guān)聯(lián)規(guī)則挖掘相結(jié)合的混合方法，通過關(guān)聯(lián)規(guī)則算法產(chǎn)生的正負規(guī)則與事件日志進行一致性檢查來判斷異常行為，與單純的過程挖掘方法相比，混合方法具有更低的錯誤發(fā)現(xiàn)率和更高的準確度，在該方法中，最佳的準確度取決于一定的置信閾值。

本文將活動的名稱、資源、時間戳視為活動自帶的內(nèi)部屬性，通過探索屬性之間的關(guān)聯(lián)規(guī)則篩選出合法活動與異?；顒印１疚牟粌H考慮單個活動是否符合流程規(guī)則，更進一步地考慮活動與活動之間的關(guān)聯(lián)規(guī)則，并通過根據(jù)Apriori算法計算出的關(guān)聯(lián)規(guī)則區(qū)分出合法行為和異常行為，并以此對事件日志進行過濾。

1? 基本概念

定義1（事件日志）：業(yè)務(wù)流程的執(zhí)行以事件日志的形式記錄下來，設(shè)一個事件日志L是一組執(zhí)行跡的集合，日志跡t=∈L將特定流程執(zhí)行描述為一系列的事件，一個事件e指的是一個活動的執(zhí)行，它是一個包含三個不同屬性元組；ei=（ea，er，et，es，ec），具體定義如下：

（1）ea：事件的執(zhí)行活動，這里用活動名稱表示。

（2）er：事件的執(zhí)行資源，表示活動是由特定角色或系統(tǒng)執(zhí)行。

（3）et：事件執(zhí)行所需的時間，由活動的開始時間戳、結(jié)束時間戳以及相關(guān)的隸屬度函數(shù)確定。

（4）es：活動執(zhí)行的開始時間戳，任意eies＞0∩

eies∈R。

（5）ec：活動執(zhí)行的結(jié)束時間戳，任意eiec＞0∩

eiec∈R。

例如表一中的跡t1中的事件e1=（A，Tom，0，5，Low），A代表e1執(zhí)行的活動，Tom表示A活動是由Tom執(zhí)行，0、5表示A活動的開始時間戳與結(jié)束時間戳，因為時間屬性屬于模糊數(shù)，為了方便定義與后續(xù)的計算，本文將時間分為三個等級，通過相關(guān)的隸屬度函數(shù)確定其等級，Low表示該活動執(zhí)行所需的時間等級為低。

圖1中橫坐標表示活動的執(zhí)行所需的總時間，由ec-es計算所得?？v坐標表示隸屬度。

根據(jù)圖1的隸屬度函數(shù)可以確定活動執(zhí)行時間的等級，使用三種不同顏色的曲線表示三種不同的等級（Low，Middle，High），通過隸屬度的不同確定其歸屬的等級。如表1中事件e1es=0，e1ec=5，事件e1的活動執(zhí)行所需時間為5，通過隸屬度函數(shù)可知e1et=Low，其隸屬度為0.25。

定義2（規(guī)則）：設(shè)R=（rc，rd）為關(guān)聯(lián)規(guī)則的集合，其中rc=（rcea1，rcea2，…，rcean）代表控制流的關(guān)聯(lián)規(guī)則，即只涉及活動與活動之間的關(guān)聯(lián)規(guī)則。rd=（rdea，rder，rdet）代表數(shù)據(jù)流（包含資源er、時間et）的關(guān)聯(lián)規(guī)則，用rdet∈{Tom，Eve，…，Mike，Alan}表示數(shù)據(jù)流規(guī)則包含的資源屬性et，用rdet∈{Low，Middle，High}表示數(shù)據(jù)流規(guī)則包含的時間屬性et。其中rc滿足以下條件：

（1）rcea1是rcea2的前繼活動，如對于跡L1={A，B，C}，rcea1=A，則rcea2=B。

（2）對于一個規(guī)則rc，當且僅當n≥2是成立。

對于數(shù)據(jù)流規(guī)則rd，滿足以下條件：

（1）rdea≠?且唯一。

（2）同一規(guī)則的資源和時間屬性都歸屬于同一活動。

即單個數(shù)據(jù)流規(guī)則只考慮單個活動的內(nèi)部屬性之間的關(guān)聯(lián)，而控制流規(guī)則更多是考慮多個活動（至少兩個活動）之間的關(guān)聯(lián)。

2? 基于關(guān)聯(lián)規(guī)則的異常分析

流程挖掘是一個新興領(lǐng)域，專門用于從事件日志中記錄的實際數(shù)據(jù)中獲取知識[6]。但是事件日志中往往存在異?；蛘咂?，即噪音，噪音的存在會影響業(yè)務(wù)流程的結(jié)構(gòu)。事件日志存儲有關(guān)流程的重要信息。反過來，對這些信息的分析可以讓公司追蹤其系統(tǒng)中記錄的實際數(shù)據(jù)和事件[7]。本文通過對控制流和數(shù)據(jù)流兩個不同角度的關(guān)聯(lián)規(guī)則分析活動與活動之間以及活動與資源、時間等屬性的特定關(guān)系，首先在控制流角度挖掘出滿足最小支持度（最小支持度根據(jù)實際結(jié)果人為設(shè)置）的頻繁項集，計算其置信度是否達到設(shè)置的閾值（最小置信度）。對于達到最小置信度的規(guī)則將其稱為合規(guī)規(guī)則[8]，而對于只包含合規(guī)規(guī)則的事件日志還需對日志進行數(shù)據(jù)流的關(guān)聯(lián)規(guī)則挖掘，從而將事件日志中的噪音進行過濾。

關(guān)聯(lián)規(guī)則學習是一種無監(jiān)督的數(shù)據(jù)挖掘方法，旨在發(fā)現(xiàn)大量數(shù)據(jù)中項與項之間相關(guān)關(guān)系[9]。在這里，本文將關(guān)聯(lián)規(guī)則學習應用于過程挖掘領(lǐng)域，將多個相關(guān)聯(lián)的事件中的活動集合視作一個項集，利用先驗算法[10]滿足閾值（最小置信度）的頻繁項集，具體方法流程通過一個實際案例展示。

2.1? 控制流關(guān)聯(lián)規(guī)則挖掘

控制流描述了流程的執(zhí)行順序，是判斷流程是否合規(guī)的第一步，首先給出支持度與置信度的相關(guān)定義。

定義3（支持度）：支持度表示事件日志中該項集所占的比例，X代表一組活動集合（項集）中的前繼活動，Y代表X的后繼活動。對于項集（A，B）其支持度表示活動A、B共同在事件日志中出現(xiàn)的比例。

Support（X，Y）=P（X∪Y）

定義4（置信度）：置信度表示前繼活動出現(xiàn)后期后繼活動出現(xiàn)的概率，項集（A，B）的置信度表示在A活動發(fā)生之后B活動發(fā)生的概率。

算法1 控制流關(guān)聯(lián)規(guī)則挖掘方法：

輸入：事件日志L={t1，t2，t3，…，tn}，最小支持度Min_Supt和最小置信度Min_Conf；

輸出：控制流關(guān)聯(lián)規(guī)則；

步驟1：對事件日志L={t1，t2，t3，…，tn}進行預處理，計算日志中所有活動的出現(xiàn)次數(shù)，將活動出現(xiàn)的次數(shù)除以日志所包含的跡的總數(shù)，得到每個活動的支持度，大于等于最小支持度的活動作為初始的頻繁一項集。

步驟2：將步驟1中得到的頻繁一項集進行兩兩組合，組成不相同的二項集，再分別計算每個二項集的支持度，保留大于或等于最小支持度的二項集作為頻繁二項集。

步驟3：不斷重復步驟2的操作，將上個步驟得到的頻繁K項集兩兩組合得到頻繁K+1項集，如果頻繁K+1項集為空則算法返回頻繁K項集，如果頻繁K+1項集只有一項，直接返回頻繁K+1項集，計算其置信度，大于等于最小置信度的頻繁K+1項集作為算法結(jié)果返回，算法結(jié)束。

下面是其偽代碼：

Algorithm 1 控制流關(guān)聯(lián)規(guī)則挖掘算法

Input：事件日志L={t1，t2，t3，…，tn}，最小支持度Minsupport，最小置信度Minconfidence

Output：控制流關(guān)聯(lián)規(guī)則集合Rc={rc1，rc2，…，rcn}

1：for m = 1 → M do //m 表示迭代次數(shù)

2：? ? C ? Findfrequentitem //初始化項集

3：? ? for i = 1 → n do //循環(huán)遍歷項集

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 //輸出結(jié)果

2.2? 數(shù)據(jù)流關(guān)聯(lián)規(guī)則挖掘

由算法1得到的控制流規(guī)則從事件日志中提取出了相互關(guān)聯(lián)、相互依賴的活動集合，在實際的應用流程中，如信貸申請流程中接受申請活動往往與核實申請人信息活動綁定在一起，又比如在醫(yī)療領(lǐng)域流程中病人在接受檢查之后醫(yī)生才能為其指定治療方案。但控制流關(guān)聯(lián)規(guī)則只能挖掘活動與活動之間的依賴關(guān)系，而對于流程中出現(xiàn)的數(shù)據(jù)流異常卻無能為力，如在信貸申請流程中，大額貸款的申請需要經(jīng)理同意才能得到批準，這就對活動的執(zhí)行資源進行了限制，數(shù)據(jù)流關(guān)聯(lián)規(guī)則針對活動與資源、時間等屬性的依賴關(guān)系進行挖掘，有效解決了事件日志中數(shù)據(jù)流的異常行為。

算法 2 數(shù)據(jù)流關(guān)聯(lián)規(guī)則挖掘方法：

輸入：算法1得到的控制流關(guān)聯(lián)規(guī)則，事件所包含的所有屬性（資源er，活動ea，時間et）；

輸出：數(shù)據(jù)流關(guān)聯(lián)規(guī)則；

步驟1：將控制流關(guān)聯(lián)規(guī)則所包含的事件的所有屬性作為初始的三項集，即包含活動ea、資源er、事件et的三項集。

步驟2：分別計算由不同資源和時間執(zhí)行同一活動的事件的支持度，與算法1類似，保留大于等于最小支持度的三項集作為頻繁項集。

步驟3：再通過計算頻繁項集的置信度得到數(shù)據(jù)流關(guān)聯(lián)規(guī)則，作為算法結(jié)果返回，算法結(jié)束。

下面是其偽代碼：

Algorithm 2 數(shù)據(jù)流關(guān)聯(lián)規(guī)則挖掘算法

Input：事件日志L={t1，t2，t3，…，tn}，最小支持度Minsupport，最小置信度Minconfidence，活動ea，資源er，開始時間es，結(jié)束時間ec，數(shù)據(jù)流項集，df

Output：數(shù)據(jù)流關(guān)聯(lián)規(guī)則集合Rd={rd1，rd2，…，rdn}

1：for m = 1 → M do //m 表示迭代次數(shù)

2：? ? C ? Findfrequentitem //初始化項集

3：? ? for i = 1 → n do //循環(huán)遍歷項集

4：? ? ? et ? Membership（es，ec） //通過隸屬度函數(shù)確定執(zhí)行時間 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 //輸出結(jié)果

3? 實例分析及仿真實驗

為驗證上述方法的可行性，以銀行信貸申請流程為例，首先客戶提交貸款申請，銀行在收到貸款申請之后會核實客戶的個人信息，檢查其申請資料是否完整合格，申請通過之后客戶需辦理擔保手續(xù)，將抵押物抵押給銀行，銀行會根據(jù)抵押物品類、價值的不同決定貸款金額的大小，而大額貸款的同意往往需要經(jīng)理同意才能簽訂貸款合同，合同簽訂完銀行才會發(fā)放貸款資金到客戶的賬號上。表2是給出的一個事件日志實例，其中e1表示提交貸款申請，e2表示核實客戶信息，e3表示檢查申請資料，e4表示根據(jù)貸款金額選擇抵押品類，e5表示房屋抵押貸款，e6表示車輛抵押貸款，e7表示股權(quán)抵押貸款，e8表示評估抵押品的價值，e9表示辦理擔保手續(xù)，e10表示檢查手續(xù)是否合規(guī)，e11表示貸款交由經(jīng)理處理，e12表示貸款交由職員處理，e13表示簽訂貸款合同，e14表示檢查貸款合同是否合規(guī)，e15發(fā)放貸款金額，e16表示拒絕貸款請求。

表2中的事件日志已按頻數(shù)從大到小進行排序，首先對事件日志應用算法1進行控制流關(guān)聯(lián)規(guī)則的挖掘，對于事件日志中所有的事件{e1，…，e16}，將單個事件作為一項集，由定義3計算支持度，如二項集{e1，e4}的支持度為：

這里最小支持度設(shè)為0.15，大于等于最小支持度的予以保留，得到頻繁一項集。再根據(jù)算法1將得到的頻繁一項集兩兩組合成二項集，通過定義3計算二項集的支持度，剔除小于最小支持度的二項集得到頻繁二項集。不斷重復以上操作，可以得到頻繁K項集，直到算法終止如圖2所示。由于篇幅原因，這里只計算到頻繁三項集，對于頻繁三項集，通過定義4計算三項集{e7，e9，e10}的置信度，此處將e7視作X，（e9，e10）視作Y

同樣的，此處將最小置信度設(shè)為0.2，關(guān)聯(lián)規(guī)則（e7，（e9，e10））的置信度為0.55，即在事件e7發(fā)生之后（e9，e10）發(fā)生的概率為0.55，大于最小置信度，說明兩者之間關(guān)聯(lián)度較高，在控制流上具有很強的相互依賴性。

在對事件日志應用完算法1之后，對得到的控制流關(guān)聯(lián)規(guī)則應用算法2，為了方便計算演示，只對關(guān)聯(lián)規(guī)則（e7，（e9，e10））應用算法二，而包含該關(guān)聯(lián)規(guī)則只有t3，表3給出了部分事件日志所包含的數(shù)據(jù)流屬性。

表3還給出了規(guī)則中的事件在不同的執(zhí)行資源和執(zhí)行時間下所對應的支持度，最小支持度設(shè)為0.15，由表3可知，（e7，Eve，Hgih）的支持度遠遠小于最小支持度，這在實際應用中表現(xiàn)為往常股權(quán)抵押貸款是由Tom負責，而某次股權(quán)抵押貸款負責人不是Tom，變成了由Eve負責，這種異常行為控制流無法檢測，因為在控制流角度其事件的執(zhí)行順序并無異常，只是事件的執(zhí)行資源出現(xiàn)異常，而通過對數(shù)據(jù)流規(guī)則的挖掘，能夠在控制流正常的情況下發(fā)現(xiàn)其屬性異常。對于（e10，Alan，High），其執(zhí)行時間出現(xiàn)了異常，因此其支持度也不滿足條件。

為了驗證本文提出的方法的有效性，將本文提出的方法與啟發(fā)式挖掘方法的適合度進行了比較，適合度指的是流程模型重現(xiàn)事件日志所包含的流程行為的能力，適合度測量值為0表示無法重現(xiàn)日志中記錄的任何行為，而值為1表示能夠重現(xiàn)所有記錄的行為。由圖3的一致性度分析結(jié)果可知，本文提出的方法在事件日志實例數(shù)較多的情況下有著更好的表現(xiàn)。

由以上可知，通過對事件日志中控制流和數(shù)據(jù)流兩個角度關(guān)聯(lián)規(guī)則的挖掘，在基于發(fā)生頻率的基礎(chǔ)上計算不同規(guī)則（項集）的支持度以及置信度，通過對閾值（最小支持度、最小置信度）的設(shè)置，可以篩選出符合要求的事件日志。

4? 結(jié)? 論

本文在基于以往的研究基礎(chǔ)上，給出了從控制流以及數(shù)據(jù)流兩個角度進行關(guān)聯(lián)規(guī)則挖掘?qū)κ录罩具M行過濾和異常分析的方法，首先基于流程中活動的發(fā)生順序以及頻率挖掘事件日志中具有緊密關(guān)聯(lián)的活動集合（項集），通過計算其支持度，也就是在事件日志中發(fā)生的概率，找出在事件日志中一起頻繁發(fā)生的活動集合，即控制流關(guān)聯(lián)規(guī)則。再對控制流關(guān)聯(lián)規(guī)則中所包含的單個事件的活動、資源、時間等屬性進行數(shù)據(jù)流關(guān)聯(lián)規(guī)則的挖掘，這里的時間通過時間戳以及隸屬度函數(shù)確定，從而解決了單一控制流規(guī)則無法發(fā)現(xiàn)屬性異常的缺陷，有效減少了事件日志中的噪音對過程挖掘的影響。

本文是從兩個不同角度對事件日志進行過濾，未來還要對過濾后的事件日志應用過程挖掘算法挖掘過程模型，再對挖掘出的過程模型與事件日志進行控制流與數(shù)據(jù)流兩種角度對齊操作，從而更好的驗證對模型精度的提升。

參考文獻：

[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，F(xiàn)AHLAND 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，F(xiàn)AHLAND 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，F(xiàn)AHLAND 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）