摘 要：低頻行為識(shí)別是揭示業(yè)務(wù)流程重要信息和優(yōu)化流程模型的方法之一，現(xiàn)有流程發(fā)現(xiàn)方法忽略了數(shù)據(jù)影響鏈對低頻行為產(chǎn)生的影響，導(dǎo)致了一些低頻行為被視為噪聲直接過濾掉。針對這一問題，提出了一種基于活動(dòng)恢復(fù)集的有效低頻行為分析方法。首先根據(jù)事件日志中的行為重要性過濾日志，并構(gòu)建初始流程模型；其次從事務(wù)日志中提取活動(dòng)的輸入輸出數(shù)據(jù)項(xiàng)，并根據(jù)這些數(shù)據(jù)項(xiàng)構(gòu)造活動(dòng)影響鏈圖，在此基礎(chǔ)上獲取每個(gè)活動(dòng)基于跡的活動(dòng)恢復(fù)集；最后根據(jù)活動(dòng)恢復(fù)集來計(jì)算每條跡的行為容忍度以區(qū)分有效低頻行為和噪聲。實(shí)驗(yàn)結(jié)果表明，與其他方法相比，該方法能夠有效區(qū)分有效低頻行為與噪聲，并且從擬合度、精度以及簡單性方面提高了流程模型的質(zhì)量。該方法考慮了由活動(dòng)恢復(fù)集而導(dǎo)致的偏差情況，可以成功識(shí)別事件日志中的有效低頻行為，從而優(yōu)化了流程模型。

關(guān)鍵詞：行為重要性； 有效低頻行為； 數(shù)據(jù)影響鏈； 恢復(fù)集； 行為容忍度

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）07-012-2005-07

doi：10.19734/j.issn.1001-3695.2023.11.0567

Effective infrequent behaviors analysis method based on activity recovery sets

Abstract：Infrequent behavior recognition is one of the methods to reveal important information about business processes and optimize process models. Existing process discovery methods have overlooked the impact of data influence chains on infrequent behavior， resulting in some infrequent behavior being considered as noise and filtered out directly. To address this issue， this paper proposed a novel infrequent behavior analysis method based on activity recovery sets. Firstly， it filtered the event logs based on the importance of behavior and constructed an initial process model. Secondly，it extracted input and output data items of activities from transaction logs， and constructed an activity influence chain graph based on these data items. It obtained activity recovery sets based on these graphs. Finally， it calculated the behavior tolerance of each trace using the activity recovery sets to distinguish effective infrequent behavior from noise. The experimental results indicate that， compared to other methods， this study effectively distinguishes valid infrequent behaviors from noise and improves the quality of the process model in terms of fitness， precision， and simplicity. This method considers the biases caused by the activity recovery set and successfully identifies valid infrequent behaviors in event logs， thereby optimizing the process model.

Key words：behavioral importance; effective infrequent behavior; data impact chain; recovery sets; behavioral tolerance

0 引言

隨著工業(yè)互聯(lián)網(wǎng)時(shí)代的到來，業(yè)務(wù)流程復(fù)雜性也隨之增加，現(xiàn)在很多企業(yè)都開始通過業(yè)務(wù)流程管理來改進(jìn)傳統(tǒng)以人為中心的信息系統(tǒng)，從而提高企業(yè)工作效率。流程挖掘是業(yè)務(wù)流程管理的核心技術(shù)之一，主要是從復(fù)雜的事件日志中提取有用的信息，進(jìn)而構(gòu)建業(yè)務(wù)流程模型來促進(jìn)企業(yè)發(fā)展。流程挖掘主要包含三個(gè)部分：流程發(fā)現(xiàn)，主要通過事件日志自動(dòng)構(gòu)建一個(gè)流程模型；一致性檢查，主要分析已構(gòu)建的流程模型與事件日志之間的差異；模型增強(qiáng)，主要通過事件日志來改進(jìn)和增強(qiáng)流程模型。目前事件日志數(shù)據(jù)呈指數(shù)級(jí)增長，業(yè)務(wù)流程變得越來越復(fù)雜，事件日志隨之也變得越來越復(fù)雜，生產(chǎn)制造中的突發(fā)情況、多場景業(yè)務(wù)融合等都會(huì)造成更多低頻行為的出現(xiàn)，其中有些低頻行為（如飛機(jī)的逃逸行為，保險(xiǎn)賠付中的騙保行為）是由于某些難以滿足的條件而導(dǎo)致其出現(xiàn)頻次很低，但它們在現(xiàn)實(shí)系統(tǒng)的運(yùn)行中往往起著至關(guān)重要的作用，這類低頻行為是有效低頻行為，正確識(shí)別有效低頻行為對提高業(yè)務(wù)流程的建模質(zhì)量尤為重要。近年來的研究考慮了低頻行為，文獻(xiàn)［1］提出一種基于全局事件日志構(gòu)建日志自動(dòng)機(jī)，根據(jù)給定閾值刪除不頻繁弧，從而過濾事件日志中不頻繁的行為。文獻(xiàn)［2］提出了一種基于最大概率路徑的算法來分析活動(dòng)的分布狀態(tài)和行為之間的強(qiáng)轉(zhuǎn)移關(guān)系。首先使用條件概率熵對不頻繁的日志進(jìn)行預(yù)處理，以去除軌跡中分布極不規(guī)則的單個(gè)噪聲活動(dòng)，然后基于活動(dòng)的狀態(tài)轉(zhuǎn)移信息從日志中提取有效序列。文獻(xiàn)［3］通過抽象低頻行為來簡化流程模型，即使用存儲(chǔ)在事件日志中的靜態(tài)歷史數(shù)據(jù)無差別過濾低頻行為。文獻(xiàn)［4］進(jìn)一步提出了一個(gè)事件處理器，能夠從實(shí)時(shí)事件流中過濾掉低頻行為，從而改善在線流程挖掘結(jié)果。文獻(xiàn)［1～4］雖然研究了低頻行為，但是他們都將這些低頻行為直接識(shí)別為噪聲刪除，忽略了低頻行為中的有效低頻行為對業(yè)務(wù)流程產(chǎn)生的影響。

基于此，文獻(xiàn)［5］提出了一個(gè)從流程模型中檢索非頻繁行為模式的算法—WoMine-I，該算法可以檢測流程模型的不頻繁子結(jié)構(gòu)，進(jìn)而通過這些不頻繁子結(jié)構(gòu)執(zhí)行優(yōu)化流程模型。文獻(xiàn)［6］通過用流程樹切的直接流圖表示日志的行為關(guān)系，并與初始模型作匹配，發(fā)現(xiàn)所有的低頻序列，計(jì)算日志與模型的行為距離向量，基于行為緊密度區(qū)分有效低頻日志和噪聲日志，優(yōu)化事件日志。文獻(xiàn)［7］提出了基于Petri網(wǎng)行為緊密度的有效低頻模式分析方法，先根據(jù)事件日志建立流程模型，然后通過迭代擴(kuò)展初始模式來發(fā)現(xiàn)流程模型中的所有低頻日志序列，并在此基礎(chǔ)上計(jì)算日志與模型的行為距離向量，最后利用日志與模型的行為緊密度找出有效的低頻行為模式。

由于文獻(xiàn)［5～7］主要是基于控制流視角考慮有效低頻行為，但是忽略了數(shù)據(jù)流視角，數(shù)據(jù)流對有效低頻行為的識(shí)別也尤為重要。文獻(xiàn)［8］進(jìn)一步提出了一種基于數(shù)據(jù)感知啟發(fā)式挖掘算法（DHM），該方法利用數(shù)據(jù)屬性通過分類技術(shù)將非頻繁路徑與隨機(jī)噪聲區(qū)分開來。文獻(xiàn)［9］從控制流和數(shù)據(jù)流結(jié)合的視角來進(jìn)行有效低頻行為分析，利用頻繁模式和交互行為配置文件找出低頻行為，然后通過條件依賴概率分析了數(shù)據(jù)流信息對非頻繁行為的影響強(qiáng)度，從而提出了一種基于數(shù)據(jù)感知的頻繁模式的有效低頻行為識(shí)別方法。

綜上所述，現(xiàn)有研究雖然采用了數(shù)據(jù)流和控制流結(jié)合的視角進(jìn)行有效低頻行為分析，但忽略了由于數(shù)據(jù)變化引起的數(shù)據(jù)影響鏈產(chǎn)生的系列行為變化，進(jìn)而產(chǎn)生低頻行為，這些低頻行為對有效低頻行為識(shí)別與優(yōu)化流程模型至關(guān)重要。因此，本文重點(diǎn)基于數(shù)據(jù)變化對流程活動(dòng)執(zhí)行產(chǎn)生的聯(lián)動(dòng)影響來分析有效低頻行為，提出了一種基于活動(dòng)恢復(fù)集的有效低頻行為分析方法。第一步首先根據(jù)給定的事件日志計(jì)算跡變體直接跟隨關(guān)系分?jǐn)?shù)來篩選包含更多重要直接跟隨關(guān)系的跡，然后通過篩選出的跡構(gòu)建初始流程模型。第二步根據(jù)事件日志中跡的頻率篩選出低頻行為，然后根據(jù)事件日志的活動(dòng)影響鏈圖找出低頻行為中每個(gè)活動(dòng)基于跡的恢復(fù)集，最后計(jì)算每條跡的行為容忍度來區(qū)分有效低頻行為與噪聲。本文在業(yè)務(wù)流程執(zhí)行中引入多視角一致性檢查和有效低頻行為識(shí)別，該方法將低頻事件日志數(shù)據(jù)化，通過行為容忍度這一衡量標(biāo)準(zhǔn)來區(qū)分有效低頻行為與噪聲，并通過服裝生產(chǎn)的數(shù)據(jù)集和公開數(shù)據(jù)集BPI Challenge 2017對其適用性進(jìn)行了評(píng)估。實(shí)驗(yàn)表明本文方法不僅可以識(shí)別其他方法不能識(shí)別的有效低頻行為，還可以在不顯著降低精度的基礎(chǔ)上提高流程模型的擬合度。其主要貢獻(xiàn)如下：a）不同于基于頻率過濾事件日志的方法，提出了通過計(jì)算事件日志中跡變體直接跟隨關(guān)系得分以判斷其行為重要性的方法，從而更好地獲得初始流程模型；b）通過分析活動(dòng)的輸入和輸出數(shù)據(jù)，提出了采用活動(dòng)影響鏈圖以分析數(shù)據(jù)流和控制流間的相互影響關(guān)系，為有效低頻行為的識(shí)別提供了理論基礎(chǔ)；c）基于活動(dòng)影響鏈圖，進(jìn)一步提出了基于活動(dòng)恢復(fù)集的行為容忍度計(jì)算方法，以實(shí)現(xiàn)有效低頻行為的識(shí)別。

1 動(dòng)機(jī)例子

當(dāng)今，工業(yè)互聯(lián)網(wǎng)迅速發(fā)展，與各個(gè)生產(chǎn)制造相結(jié)合促進(jìn)生產(chǎn)業(yè)快速發(fā)展［10］。在智能制造的過程中，特定情況下的數(shù)據(jù)修改會(huì)對業(yè)務(wù)流程產(chǎn)生一系列影響，導(dǎo)致活動(dòng)序列發(fā)生頻次很低，進(jìn)而在流程挖掘中被忽略。為了研究這些低頻行為也會(huì)對流程挖掘產(chǎn)生影響，下面將用一個(gè)例子來進(jìn)行說明。如表1所示，給出了一個(gè)服裝生產(chǎn)的部分事件案例。其中A為訂單開始，B為樣品預(yù)生產(chǎn)，C為客戶審核，D為輸入訂單規(guī)模，E為計(jì)算報(bào)價(jià)，F(xiàn)為制定生產(chǎn)計(jì)劃，G為分配庫存，H為請求采購， I為儲(chǔ)備庫存，J為開始生產(chǎn)，K為抽樣檢查產(chǎn)品，L為生產(chǎn)完成，M為輸入交貨地址，N為選擇運(yùn)輸方式，O為計(jì)算運(yùn)輸成本，P為開始配送，Q為結(jié)束訂單。

現(xiàn)實(shí)生活的生產(chǎn)制造過程中，客戶可能會(huì)在工廠已經(jīng)準(zhǔn)備發(fā)貨后由于一些突發(fā)原因修改訂單的數(shù)量。雖然這種突發(fā)情況比較少見，但從現(xiàn)實(shí)角度思考它是非常合理的。如跡σ15表示這個(gè)訂單在已經(jīng)準(zhǔn)備好庫存后進(jìn)行了訂單數(shù)量的修改，因此在開始準(zhǔn)備庫存后重新執(zhí)行計(jì)算報(bào)價(jià)和修改生產(chǎn)計(jì)劃是合理的。即σ15雖然是一個(gè)低頻行為，但是從實(shí)際角度出發(fā)它是一個(gè)有效的低頻跡。表1中存在一些類似的低頻行為，如σ11～σ16，如果僅考慮控制流視角來挖掘流程模型，這些低頻跡會(huì)被當(dāng)成噪聲直接過濾掉以獲得簡單的業(yè)務(wù)流程模型，但這些低頻跡中可能存在對業(yè)務(wù)流程有意義的有效低頻行為。如果從控制流和數(shù)據(jù)流相結(jié)合的視角考慮，即在考慮控制流的基礎(chǔ)上考慮活動(dòng)之間的數(shù)據(jù)影響，這些低頻行為可能會(huì)為業(yè)務(wù)流程提供更多有價(jià)值的信息。在服裝生產(chǎn)銷售實(shí)際流程中，會(huì)存在一些由于突然事件而造成的低頻行為，如跡σ15，通過分析發(fā)現(xiàn)，這條跡在執(zhí)行儲(chǔ)備庫存活動(dòng)I之后又重新執(zhí)行輸入訂單規(guī)模活動(dòng)D，由于輸入訂單規(guī)模D的再次執(zhí)行，導(dǎo)致執(zhí)行計(jì)算報(bào)價(jià)活動(dòng)E和制定生產(chǎn)計(jì)劃活動(dòng)F相繼重復(fù)發(fā)生。后續(xù)重復(fù)執(zhí)行的活動(dòng)子序列〈E，F(xiàn)〉是導(dǎo)致跡σ15低頻出現(xiàn)的關(guān)鍵子序列?，F(xiàn)有的流程模型挖掘算法未深入分析由一個(gè)活動(dòng)的偏差執(zhí)行導(dǎo)致一系列活動(dòng)相繼偏差執(zhí)行的原因，從而導(dǎo)致類似σ15這樣的低頻跡直接識(shí)別為噪聲過濾，使構(gòu)建的流程模型不能真實(shí)地描述系統(tǒng)運(yùn)行的實(shí)際操作。圖1是基于頻次的歸納式挖掘算法［11］挖掘出的流程模型，可以發(fā)現(xiàn)σ15等一些低頻跡無法在圖1所示的流程模型上重演。

在實(shí)際業(yè)務(wù)流程中可以發(fā)現(xiàn)，σ15這條跡是具有現(xiàn)實(shí)意義的，對于σ15，當(dāng)?shù)诙螆?zhí)行輸入訂單規(guī)模D后會(huì)改變訂單的數(shù)量，而訂單數(shù)量這個(gè)數(shù)據(jù)項(xiàng)會(huì)影響后續(xù)以它作為輸入的多個(gè)活動(dòng)的發(fā)生，如〈E，F(xiàn)〉。因此一個(gè)活動(dòng)發(fā)生偏差后可能會(huì)導(dǎo)致一系列活動(dòng)受影響，如σ15中由于活動(dòng)D的偏差執(zhí)行，導(dǎo)致了活動(dòng)子序列〈D，E，F(xiàn)〉重復(fù)發(fā)生，從而使得σ15低頻出現(xiàn)。因此，針對這種由于某一個(gè)活動(dòng)的偏差發(fā)生而引起一系列后續(xù)活動(dòng)相繼重復(fù)發(fā)生而導(dǎo)致的低頻行為開展研究，并提出了活動(dòng)恢復(fù)集的低頻行為識(shí)別方法。

2 基本概念

Petri網(wǎng)是分布式系統(tǒng)的建模和分析工具，它可以描述系統(tǒng)中進(jìn)程或部件的順序、并發(fā)、沖突以及同步關(guān)系等，本文將使用Petri網(wǎng)對流程進(jìn)行建模，本章給出了本文中使用的幾個(gè)術(shù)語的基本定義。

可見，網(wǎng)PN=（P，T，F(xiàn)，C）的基本元素集合是P和T，在Petri網(wǎng)中，分別使用圓圈和方框表示。

在本文中，使用多重集DL表示事件日志L中的所有直接跟隨關(guān)系。

3 基于恢復(fù)集的有效低頻行為分析

本章主要介紹了基于活動(dòng)恢復(fù)集來發(fā)現(xiàn)有效低頻行為的方法，并給出相應(yīng)的算法。該方法不僅可以解決現(xiàn)存流程挖掘技術(shù)只注重發(fā)現(xiàn)頻繁行為而忽略低頻行為的問題，而且通過將控制流和數(shù)據(jù)流相結(jié)合的視角來發(fā)現(xiàn)有效低頻行為，實(shí)現(xiàn)了流程模型增強(qiáng)的目的。首先通過跡變體直接跟隨關(guān)系分?jǐn)?shù)篩選包含更多重要直接跟隨關(guān)系的跡，并利用這些跡構(gòu)建初始流程模型；其次通過判斷事件日志中跡的頻率是否小于閾值來發(fā)現(xiàn)低頻行為；進(jìn)而通過數(shù)據(jù)影響分析從事務(wù)日志中獲取活動(dòng)恢復(fù)集以分析低頻行為，并從中識(shí)別有效低頻行為，最后通過有效低頻行為進(jìn)行模型增強(qiáng)。該方法的研究框架如圖2所示。3.1節(jié)給出了通過捕獲事件日志中的重要行為來發(fā)現(xiàn)初始流程模型的算法，3.2節(jié)給出了一些相關(guān)定義和一個(gè)基于恢復(fù)集的有效低頻行為識(shí)別的算法。

3.1 基于行為重要性過濾事件日志

流程發(fā)現(xiàn)是流程挖掘的主要分支之一，旨在發(fā)現(xiàn)一個(gè)流程模型，該模型能準(zhǔn)確描述事件日志中的數(shù)據(jù)所捕獲的底層流程［15］。本節(jié)通過捕獲事件日志中的重要行為來發(fā)現(xiàn)流程模型［16］，該方法可以在減少挖掘時(shí)間的同時(shí)，保證挖掘出的模型質(zhì)量。

首先遍歷事件日志L找到流程變體LT，然后遍歷LT找到所有直接跟隨關(guān)系，并將它們放入多重集DL。直接跟隨關(guān)系a>Lb的頻率F（a>Lb） 的計(jì)算方法如式（1）所示。本文將F（a>Lb）作為直接跟隨關(guān)系a>Lb行為重要性的判別標(biāo)準(zhǔn)。

其中：|a>Lb|表示a>Lb這個(gè)直接跟隨關(guān)系的數(shù)量；|DL|表示事件日志LT中包含的所有直接跟隨關(guān)系個(gè)數(shù)之和。計(jì)算出每個(gè)直接跟隨關(guān)系的頻率后，遍歷DL去除多重集DL中重復(fù)的跟隨關(guān)系得到Dl，并按照每個(gè)直接跟隨關(guān)系的頻率從小到大進(jìn)行排序。設(shè)置一個(gè)閾值θ，選出F（a>Lb）的直接跟隨關(guān)系多重集集合P，其中P∈Dl。當(dāng)閾值θ選擇過大時(shí)，可能體現(xiàn)不出篩選重要跟隨關(guān)系的作用，當(dāng)閾值θ選擇過小時(shí)，可能會(huì)丟失一些重要的直接跟隨關(guān)系，從而導(dǎo)致發(fā)現(xiàn)的流程模型質(zhì)量較差。本文主要通過實(shí)驗(yàn)對比挖掘過程模型的質(zhì)量來選擇一個(gè)相對最優(yōu)的閾值θ作為基準(zhǔn)閾值，具體步驟見第4章節(jié)實(shí)驗(yàn)部分。

例如：有一個(gè)事件日志L=［ADB3，ACDB2，EF，CADB4］，LT=［ADB，ACDB，EF，CADB］，DL=［A>LD，D>LB，A>LC，C>LD，D>LB，E>LF，C>LA，A>LD，D>LB］，F(xiàn)（D>LB）≈0.33，Dl=［A>LD，D>LB，A>LC，C>LD，E>LF，C>LA］。

本文通過選擇包含P中更多直接跟隨關(guān)系的跡來挖掘初始流程模型。首先將每個(gè)跡變體直接跟隨關(guān)系分?jǐn)?shù)Sγi的初始值設(shè)置為0。如果跡變體包含P中的一個(gè)直接跟隨關(guān)系，則將Sγi加1來增加其重要性。否則，如果跡變體包含不屬于P的直接跟隨關(guān)系，則將Sγi減1來降低其重要性。例如，對于跡變體γ=〈e1，e2，…，en〉，如果任意i∈{1，2，…，n-1}，ei>L ei+1∈P，Sγ+1，否則為Sγ-1。算法1主要通過行為重要性過濾事件日志。其實(shí)現(xiàn)思想是根據(jù)日志L中所有跡變體的直接跟隨關(guān)系分?jǐn)?shù)從高到低對跡變體進(jìn)行排序，然后從高到低選擇跡變體添加到日志L′中，最后通過篩選后的事件日志L′得到一個(gè)初始流程模型，具體如算法1所示。

算法1 根據(jù)行為重要性篩選事件日志

第1、2行首先遍歷事件日志L，得到流程變體LT，然后遍歷LT得到所有的直接跟隨關(guān)系的多重集DL；第3、4行計(jì)算多重集DL中每個(gè)直接跟隨關(guān)系的頻率F（a>Lb），在第5行遍歷DL，去除多重集DL中重復(fù)的元素得到Dl;第6、7行按照每個(gè)直接跟隨關(guān)系的頻率從大到小進(jìn)行排序，然后選擇直接跟隨關(guān)系頻率大于θ的直接跟隨關(guān)系多重集集合P；第8、9行初始化跡變體分?jǐn)?shù)Sγi的初始值為0；第10～15行遍歷所有跡變體，判斷是否包含P中直接跟隨關(guān)系，如果包含則令Sγi加上1來增加其狀態(tài)，否則減1；第16～19行根據(jù)它們在LT中的分?jǐn)?shù)從高到低對所有跡變體進(jìn)行排序，然后從高到低選擇跡變體， 并將選定的跡變體附加到子日志。通過對事件日志中的跡重要性進(jìn)行判斷，進(jìn)而得出一個(gè)初始的模型，方便后文的有效低頻行為分析。

3.2 基于數(shù)據(jù)影響分析有效低頻行為

為了區(qū)分事件日志中的低頻行為是有效低頻還是噪聲，本節(jié)基于數(shù)據(jù)影響分析提出識(shí)別有效低頻行為的算法。

定義4 輸入-活動(dòng)-輸出IAO［17］。IAO是一組三元組（in，Act，out），其中in，out∈Data_I∪{null}，Data_I是一組數(shù)據(jù)項(xiàng)，即輸入數(shù)據(jù)項(xiàng)in經(jīng)過活動(dòng)Act，輸出對應(yīng)的輸出數(shù)據(jù)項(xiàng)out。

表2是本文第1章節(jié)中示例的部分IAO集。例如，訂單ID是樣品預(yù)生產(chǎn)（B）的輸入數(shù)據(jù)，樣品審核結(jié)果是樣品預(yù)生產(chǎn)（B）的輸出數(shù)據(jù)。

在日志移動(dòng)時(shí)，檢索由給定活動(dòng)更改的所有數(shù)據(jù)項(xiàng)，通過數(shù)據(jù)影響分析識(shí)別可能受到這些數(shù)據(jù)項(xiàng)影響的所有活動(dòng)［18］。為了方便對活動(dòng)進(jìn)行數(shù)據(jù)影響分析，通過表2畫出部分事件日志的活動(dòng)影響鏈圖，如圖3所示，每個(gè)灰色虛線框里面的活動(dòng)表示受其對應(yīng)活動(dòng)更改的所有數(shù)據(jù)項(xiàng)的活動(dòng)。例如〈客戶審核、結(jié)束訂單〉這兩個(gè)活動(dòng)會(huì)受到〈樣品預(yù)生產(chǎn)〉這個(gè)活動(dòng)影響。給定一個(gè)事件日志L，A表示事件日志L中所有的活動(dòng)集合，給定一個(gè)活動(dòng)e，用RS（e）表示受活動(dòng)e影響的所有活動(dòng)集合，本文稱RS（e）為活動(dòng)e的影響集。例如，從圖3中可以看出RS（D）={E，F(xiàn)，G，H，I，N，O}。

根據(jù)事件日志的IAO集檢索活動(dòng)e更改的所有數(shù)據(jù)項(xiàng)，應(yīng)用數(shù)據(jù)影響分析識(shí)別可能受到這些數(shù)據(jù)項(xiàng)影響的所有已經(jīng)執(zhí)行的活動(dòng)。由于事件日志L中活動(dòng)不會(huì)同時(shí)出現(xiàn)在同一條跡中，所以進(jìn)一步給出了恢復(fù)集的概念。

定義6 恢復(fù)集［17］。給定一條跡σ，e是對齊γ中發(fā)生日志移動(dòng)的事件。Aff（e）是受e影響的所有數(shù)據(jù)項(xiàng)的集合，e關(guān)于σ的恢復(fù)集定義為RC（e， σ）=∪d∈Aff（e）DI（d，σ）。

假設(shè)給定一條跡σ=〈A，B，C，D，E，F(xiàn)，G，J，K，Q〉，由于活動(dòng)D的影響集為RS（D）={E，F(xiàn)，G，H，I，N，O}，則活動(dòng)D基于σ的恢復(fù)集為RC（D，σ）=〈E，F(xiàn)，G〉。定義6的恢復(fù)集表示，在跡σ中，由活動(dòng)e的輸出數(shù)據(jù)改變導(dǎo)致的后續(xù)受影響的發(fā)生活動(dòng)集合。后續(xù)章節(jié)將采用活動(dòng)恢復(fù)集來識(shí)別有效低頻行為。

當(dāng)檢測到日志移動(dòng)時(shí)，首先判斷發(fā)生日志移動(dòng)的活動(dòng)a是否是由某個(gè)前驅(qū)活動(dòng)b的數(shù)據(jù)影響而導(dǎo)致的移動(dòng)，即判斷活動(dòng)a是否屬于發(fā)生日志移動(dòng)的前驅(qū)活動(dòng)b的恢復(fù)集a∈RC（b， σ）。若是，說明活動(dòng)b的偏差執(zhí)行是由活動(dòng)a導(dǎo)致的，因此活動(dòng)b產(chǎn)生的日志移動(dòng)成本代價(jià)將被忽略。引入活動(dòng)恢復(fù)集的概念后，傳統(tǒng)的流程模型于跡的偏差對齊計(jì)算方法將不再適用，定義7將進(jìn)一步給出行為容忍度的概念，該定義在計(jì)算模型和跡的偏差對齊成本時(shí)考慮了由活動(dòng)恢復(fù)集而導(dǎo)致的偏差情況。

定義7 行為容忍度。給定一個(gè)事件日志L={σ1，…，σm}，σi表示事件日志L中的一條跡，則這條跡σi的行為感容忍度為

其中：Clog、Cmod、Crec、Cre分別表示這條跡對應(yīng)的日志移動(dòng)、模型移動(dòng)、恢復(fù)移動(dòng)，恢復(fù)集中未執(zhí)行預(yù)期活動(dòng)的成本代價(jià)；|Mlog|、|Mmod|、|Mrec|分別表示發(fā)生日志移動(dòng)、模型移動(dòng)、恢復(fù)移動(dòng)的次數(shù)；|Mre|表示在回溯完整條跡后，尚未執(zhí)行的預(yù)期活動(dòng)RE列表中剩余所有活動(dòng)的個(gè)數(shù)。日志移動(dòng)表示流程模型中發(fā)生的活動(dòng)在事件日志中沒有發(fā)生而產(chǎn)生的移動(dòng)；模型移動(dòng)表示跡中發(fā)生的事件在流程模型中沒有發(fā)生而產(chǎn)生的移動(dòng)；恢復(fù)移動(dòng)表示屬于某個(gè)前驅(qū)活動(dòng)的恢復(fù)集中的活動(dòng)產(chǎn)生的日志移動(dòng)；未執(zhí)行的預(yù)期活動(dòng)表示當(dāng)整條跡已經(jīng)分析完成，所有活動(dòng)基于跡的恢復(fù)集中本該執(zhí)行實(shí)際卻未執(zhí)行的活動(dòng)。

以第1章動(dòng)機(jī)例子的σ15〈A，B，C，D，E，F(xiàn)，H，I，J，D，E，F(xiàn)，K，M，N，O，P，Q〉為例，與圖1所示的模型進(jìn)行一致性檢查，構(gòu)建一條對齊［19］，如表3所示，其中（D，>>）為日志移動(dòng)、（>>，L）模型移動(dòng)、{（E，>>），（F，>>）}為恢復(fù)移動(dòng)、{ H，I }為未執(zhí)行預(yù)期活動(dòng)。

本文中將Clog和Cmod的大小設(shè)置為1。Crec為恢復(fù)移動(dòng)的成本，恢復(fù)移動(dòng)是基于某個(gè)前驅(qū)活動(dòng)的恢復(fù)集而產(chǎn)出的移動(dòng)，即此活動(dòng)發(fā)生的移動(dòng)是由前驅(qū)活動(dòng)導(dǎo)致的偏差，因此，在計(jì)算偏差代價(jià)時(shí)，可以將其忽略不計(jì)，本文將其成本設(shè)為0。Cre為恢復(fù)集中未執(zhí)行預(yù)期活動(dòng)的成本，其表示在恢復(fù)集中本該執(zhí)行實(shí)際上沒有發(fā)生的活動(dòng)成本，因此本文將其設(shè)置為1。設(shè)置閾值φ，如果一條跡的行為容忍度大于閾值φ，則認(rèn)為這條跡是有效的。當(dāng)閾值φ選擇過大時(shí)，會(huì)將一些有效低頻行為識(shí)別為噪聲，當(dāng)閾值φ選擇過小時(shí)，可能會(huì)將一些噪聲識(shí)別成有效低頻行為。本文φ主要是基于實(shí)驗(yàn)數(shù)據(jù)，通過實(shí)驗(yàn)驗(yàn)證來進(jìn)行選擇，具體步驟見第4章節(jié)實(shí)驗(yàn)部分。算法2主要通過計(jì)算跡的行為容忍度來區(qū)分有效低頻行為。該算法首先通過事務(wù)日志獲取每個(gè)活動(dòng)的輸入數(shù)據(jù)項(xiàng)和輸出數(shù)據(jù)項(xiàng)，然后通過數(shù)據(jù)影響分析識(shí)別和檢查數(shù)據(jù)項(xiàng)對其他業(yè)務(wù)流程元素的影響，通過遍歷事件日志，得到每個(gè)活動(dòng)的恢復(fù)集，從而計(jì)算每條跡基于模型的行為容忍度，以實(shí)現(xiàn)有效低頻行為的識(shí)別。

算法2 基于恢復(fù)集分析有效低頻行為

第1～3行根據(jù)事件日志L中跡的頻率選出低頻日志L_inf；第4～13行將這些低頻日志L_inf結(jié)合過程模型進(jìn)行一致性檢查，構(gòu)造一個(gè)一致性對齊列表M，并根據(jù)規(guī)則求出每個(gè)活動(dòng)的恢復(fù)集;第14行初始化RE為空集，其表示為一條跡上尚未執(zhí)行的預(yù)期活動(dòng)的集合;第16～29行表示在對齊M的基礎(chǔ)上，動(dòng)態(tài)更新尚未執(zhí)行的預(yù)期活動(dòng)的RE列表；第30～34行通過定義7求出每條跡的行為容忍度，將日志L_inf中的低頻行為識(shí)別為有效低頻和噪聲。

4 實(shí)例分析

本章針對第1章中服裝生產(chǎn)制造的案例和BPI Challenge 2017的公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，并將本文方法與現(xiàn)有方法進(jìn)行對比分析，并對結(jié)果進(jìn)行討論。首先將本文方法在區(qū)分有效低頻行為方面與其他方法［7，20］進(jìn)行比較，然后通過將不同級(jí)別的罕見行為注入到現(xiàn)實(shí)日志中時(shí)，評(píng)估發(fā)現(xiàn)流程模型的質(zhì)量。實(shí)驗(yàn)運(yùn)行環(huán)境是Intel i7-6500處理器和8 GB RAM。

4.1 服裝生產(chǎn)案例實(shí)驗(yàn)分析

4.1.1 根據(jù)行為重要性構(gòu)建流程模型

首先遍歷表1中事件日志L，找到流程變體LT，然后遍歷LT找到所有直接跟隨關(guān)系的對象，計(jì)算直接跟隨關(guān)系a>Lb在整個(gè)多重集中的頻率F（a>Lb）作為選擇標(biāo)準(zhǔn)，如表4所示。本文給定選擇F（a>Lb）的閾值θ，從而選出符合閾值要求的直接跟隨關(guān)系多重集集合P。閾值θ的選取會(huì)影響流程模型的擬合度以及發(fā)現(xiàn)此流程模型的時(shí)間，為了選擇相對合適的θ值，本文設(shè)計(jì)一個(gè)實(shí)驗(yàn)來進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果如圖4所示。從圖4中發(fā)現(xiàn)擬合度和時(shí)間是隨著θ增長而逐漸增加的，當(dāng)閾值θ從0.9調(diào)整到0.95時(shí)，挖掘模型的擬合度只增加了0.005，然而挖掘模型所用的時(shí)間同比增加了31.78%，因此通過對比本文選擇θ=0.9時(shí)的直接跟隨關(guān)系多重集集合P更合適。

通過3.1節(jié)中的方法計(jì)算所有跡變體的分?jǐn)?shù)之后，根據(jù)它們在LT中的分?jǐn)?shù)從高到低對所有跡變體進(jìn)行排序。最后，從高到低選擇跡變體，并將選定的跡變體添加到日志L′。最后通過日志L′得到一個(gè)相對合理的流程模型，如圖5所示，并計(jì)算出其流程模型的擬合度fitness（M）=0.953。與現(xiàn)有的流程挖掘算法相比，雖然構(gòu)建的流程模型的擬合度不是最高的，但是在考慮時(shí)間因素的基礎(chǔ)上，通過實(shí)驗(yàn)驗(yàn)證本文方法是相對最優(yōu)的，實(shí)驗(yàn)結(jié)果如表5所示。

4.1.2 有效低頻行為識(shí)別

首先，從表1的事件日志中選擇頻率低于閾值τ的低頻行為，本文設(shè)置τ=0.2，因此將頻率低于0.2的跡認(rèn)定為低頻行為，進(jìn)而選出的低頻事件日志{σ11，σ12，σ13，σ14，σ15，σ16}，并按照實(shí)例數(shù)從多到少進(jìn)行排序，結(jié)果如下：{〈ABCDEFGJKMNONOPQ〉13，〈ABCDEFHIJKLMNOMNOPQ〉11，〈ABCDEFHIDEFJKLMNOPQ〉10，〈ABCDEFHIJDEFKLMNOPQ〉8，〈ABCDEFHIHIJKMNOPQ〉6，〈ABCCEGMOQ〉3}。下面將低頻跡與圖5所示的流程模型進(jìn)行控制流對齊，其中σ11的對齊結(jié)果如表6所示。

根據(jù)活動(dòng)影響鏈圖求出每個(gè)活動(dòng)基于這條跡的恢復(fù)集，同樣以σ11為例，通過圖2得到活動(dòng)N基于σ11的恢復(fù)集為RE（N，σ11）=〈O〉。根據(jù)每個(gè)活動(dòng)的恢復(fù)集動(dòng)態(tài)更新表5中的對齊，如果這個(gè)日志移動(dòng)屬于前面活動(dòng)的恢復(fù)集中的活動(dòng)，則將>>改為Ω，更新后的對齊如表7所示。

然后基于恢復(fù)集在構(gòu)建的對齊表上進(jìn)行重放，計(jì)算出跡σ11的行為容忍度DF（σ11）=0.941，同理計(jì)算出其他所有低頻案例的行為容忍度分別為DF（σ12）=0.944，DF（σ13）=0.556，DF（σ14）=0.944，DF（σ15）=0.895，DF（σ16）=0.895。根據(jù)行為容忍的閾值判斷出哪些低頻行為是有效低頻行為，閾值φ的選擇會(huì)對模型優(yōu)化的結(jié)果產(chǎn)生影響，根據(jù)上文計(jì)算的行為容忍度來觀察，當(dāng)φ的取值在0.6～0.9時(shí)均不影響優(yōu)化結(jié)果。當(dāng)φ取值大于0.9時(shí)，優(yōu)化后模型的擬合度會(huì)低于當(dāng)φ=0.85時(shí)優(yōu)化后模型的擬合度，因?yàn)楸疚脑O(shè)置行為容忍度的閾值為0.85，從而判斷出σ11，σ12，σ14，σ15，σ16為有效低頻行為，而σ13可能是因?yàn)闃I(yè)務(wù)流程或系統(tǒng)原因而產(chǎn)生的噪聲。利用σ11，σ12，σ14，σ15，σ16這些有效低頻行為對圖5所示的模型進(jìn)行優(yōu)化，優(yōu)化后的模型如圖6所示。

4.1.3 方法評(píng)估

針對第1章動(dòng)機(jī)例子的數(shù)據(jù)，本節(jié)通過將本文方法（DAR）與LFB［7］、MP算法［20］ 對比，來評(píng)估本文方法識(shí)別有效的低頻行為的能力。對比結(jié)果如表8所示，從表8可以看出本文方法在識(shí)別有效低頻行為上優(yōu)于其他方法，而MP可能將不正確的低頻行為（噪聲）識(shí)別為有效的低頻行為，并且通過實(shí)驗(yàn)驗(yàn)證了采用本文方法（DRA）進(jìn)行優(yōu)化后的模型質(zhì)量優(yōu)于其他兩種方法。為了更全面地研究使用該方法對有效低頻行為分析的影響，本文向服裝生產(chǎn)事件日志注入5%、10%、15%的噪聲，考慮在跡中的隨機(jī)位置添加隨機(jī)活動(dòng)、隨機(jī)刪除活動(dòng)以及在跡中交換活動(dòng)這三種方式來添加噪聲，然后分析不同閾值大小下擬合度、精度、簡單性角度不同方法對比的結(jié)果，實(shí)驗(yàn)結(jié)果如圖7～9所示。

從圖7、8發(fā)現(xiàn)，在擬合度方和精確度方面，本文方法優(yōu)于另外兩種方法，首先因?yàn)檫@兩種方法均沒有考慮到數(shù)據(jù)視角，導(dǎo)致會(huì)把一些有效低頻行為誤認(rèn)為噪聲，進(jìn)而使優(yōu)化后的模型擬合度和精度相對較低。本文方法在注入5%、10%、15%噪聲下的事件日志挖掘出的模型質(zhì)量雖然有所下降，但對比另外兩種方法仍然具有一定優(yōu)勢。在簡單性方面，如圖9所示，本文方法優(yōu)于MP，與LFP相差不多。因?yàn)镸P主要基于最大概率路徑分析活動(dòng)分布狀態(tài)和行為間強(qiáng)傳遞關(guān)系來區(qū)分噪聲活動(dòng)和有效序列，導(dǎo)致一些噪聲被識(shí)別成有效行為，進(jìn)而導(dǎo)致挖掘的流程模型相對復(fù)雜。

實(shí)驗(yàn)結(jié)果表明，在對本文實(shí)驗(yàn)事件日志添加噪聲之后，本文方法仍然表現(xiàn)出較好的有效低頻行為識(shí)別能力，降低了假陽性的出現(xiàn)。所以利用本文方法識(shí)別出的有效低頻行為對流程模型進(jìn)行優(yōu)化，在大部分情況下都是優(yōu)于其他兩種方法的。

4.2 公開數(shù)據(jù)集實(shí)驗(yàn)分析

為了證明本文方法具有一定的泛化能力，本節(jié)使用BPI Challenge 2017公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析。該數(shù)據(jù)集與荷蘭金融機(jī)構(gòu)的貸款申請流程有關(guān)，包含2016年通過在線系統(tǒng)提交的所有申請及其后續(xù)事件，具有31 509條跡，1 202 267個(gè)事件，26個(gè)活動(dòng)。實(shí)驗(yàn)結(jié)果如圖10所示。

通過圖10可以發(fā)現(xiàn)，針對BPI Challenge 2017的事件日志，本文方法具有一定的優(yōu)勢。在擬合度方面，本文方法明顯優(yōu)于另外兩個(gè)方法，這是因?yàn)長FB只是基于控制流考慮了子序列間的行為緊密度來進(jìn)行識(shí)別有效低頻行為，而MP方法同樣只考慮了控制流，主要根據(jù)最大概率路徑分析活動(dòng)分布狀態(tài)和行為間強(qiáng)傳遞關(guān)系和區(qū)分有效低頻行為。在簡單性方面比LFB這個(gè)方法差一點(diǎn)，可能是因?yàn)楸疚姆椒紤]的數(shù)據(jù)過于細(xì)致，導(dǎo)致挖掘出的流程模型相較于LFB方法復(fù)雜。

綜上所述，本文方法在大部分的情況下都是優(yōu)于其他兩個(gè)方法，從而驗(yàn)證了其有效性。通過本文方法優(yōu)化的模型具有較高的模型質(zhì)量，說明基于活動(dòng)恢復(fù)集來區(qū)分有效低頻行為具有較高的準(zhǔn)確性， 主要因?yàn)楸疚目紤]活動(dòng)輸入輸出數(shù)據(jù)的改變對此活動(dòng)以及其后繼活動(dòng)產(chǎn)出的影響鏈，進(jìn)而增加了有效低頻行為的識(shí)別質(zhì)量，然后通過計(jì)算跡的行為容忍度來區(qū)分有效低頻行為和噪聲，同時(shí)降低了噪聲被識(shí)別為低頻行為的可能性。

5 結(jié)束語

為了更好地區(qū)分有效低頻行為與噪聲，本文提出基于活動(dòng)恢復(fù)集的有效低頻行為識(shí)別方法。首先從事務(wù)日志中提取每個(gè)活動(dòng)的輸入輸出數(shù)據(jù)項(xiàng)，其次根據(jù)活動(dòng)輸入輸出數(shù)據(jù)項(xiàng)表構(gòu)造活動(dòng)影響鏈圖，再從活動(dòng)影響鏈圖中得到每個(gè)活動(dòng)的影響集，然后在考慮活動(dòng)恢復(fù)集的基礎(chǔ)上構(gòu)建對齊，從而計(jì)算每一條跡的行為容忍度來區(qū)分有效低頻行為和噪聲，并且通過識(shí)別出的有效低頻行為對初始模型進(jìn)行優(yōu)化。最后，本文使用合成和真實(shí)的事件日志進(jìn)行評(píng)估，結(jié)果驗(yàn)證了本文方法可以識(shí)別其他方法不能識(shí)別的有效低頻行為。同時(shí)本文方法可以在不顯著降低精度的基礎(chǔ)上提高發(fā)現(xiàn)流程模型的擬合度。在未來的工作中，考慮將本文方法應(yīng)用到更多的工業(yè)互聯(lián)網(wǎng)領(lǐng)域，以更好地驗(yàn)證提出方法的泛化能力，同時(shí)可以進(jìn)一步結(jié)合機(jī)器學(xué)習(xí)等方法來優(yōu)化數(shù)據(jù)影響鏈圖。

參考文獻(xiàn)：

［1］Conforti R， Rosa M L， Ter Hofstede A H M. Filtering out infrequent behavior from business process event logs［J］. IEEE Trans on Knowledge and Data Engineering， 2017， 29（2）： 300-314.

［2］Sani M F， Van Zelst S J， Van der Aalst W M P. Improving process discovery results by filtering outliers using conditional behavioural probabilities［C］//Proc of International Conference on Business Process Management. Cham： Springer， 2018： 216-229.

［3］Chapela-Campa D， Mucientes M， Lama M. Understanding complex process models by abstracting infrequent behavior［J］. Future Gene-ration Computer Systems， 2020， 113： 428-440.

［4］Van Zelst S J， Sani M F， Ostovar A， et al. Detection and removal of infrequent behavior from event streams of business processes［J］. Information Systems， 2020，90： 101451.

［5］Chapela-Campa D， Mucientes M， Lama M. Discovering infrequent behavioral patterns in process models［C］//Proc of International Conference on Business Process Management. Cham： Springer， 2017： 324-340.

［6］郝惠晶， 方賢文， 方娜， 等. 基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘與優(yōu)化分析［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2020，26（6）： 1660-1667. （Hao Huijing， Fang Xianwen， Fang Na， et al. Low-frequency behavior mining and optimization of business process base on Petri net［J］. Computer Integrated Manufacturing Systems， 2020，26（6）： 1660-1667.）

［7］郝惠晶， 方賢文， 王麗麗， 等. 基于Petri網(wǎng)行為緊密度的有效低頻行為模式分析［J］. 計(jì)算機(jī)科學(xué)， 2019，46（2）： 321-326. （Hao Huijing， Fang Xianwen， Wang Lili， et al. Analysis of effective low frequency behavior patterns based on Petri net behavior choseness［J］. Computer Science， 2019，46（2）： 321-326.）

［8］Mannhardt F， De Leoni M， Reijers H A， et al. Data-driven process discovery—revealing conditional infrequent behavior from event logs［C］//Proc of International Conference on Advanced Information Systems Engineering. Cham： Springer， 2017： 545-560.

［9］Wang Lili， Fang Xianwen， Asare E， et al. An optimization approach for mining of process models with infrequent behaviors integrating data flow and control flow［J］. Scientific Programming， 2021， 2021： e8874316.

［10］Li Jianqiang， Yu F R， Deng Genqiang， et al. Industrial Internet： a survey on the enabling technologies， applications， and challenges［J］. IEEE Communications Surveys & Tutorials， 2017， 19（3）： 1504-1526.

［11］Leemans S J J， Fahland D， van der Aalst W M P. Discovering block-structured process models from event logs containing infrequent beha-viour［C］//Proc of International Conference on Business Process Management. Cham： Springer， 2014： 66-78.

［12］Smirnov S， Weidlich M， Mendling J. Business process model abstraction based on behavioral profiles［C］//Proc of International Confe-rence on Service-Oriented Computing. Berlin： Springer， 2010： 1-16.

［13］Taymouri F， Rosa M L， Dumas M， et al. Business process variant analysis： survey and classification［J］. Knowledge-Based Systems， 2021， 211： 106557.

［14］Fani Sani M，Van Zelst S J，Van der Aalst W M P. The impact of biased sampling of event logs on the performance of process discovery［J］. Computing， 2021，103（6）： 1085-1104.

［15］Pasquadibisceglie V， Appice A， Castellano G， et al. PROMISE： coupling predictive process mining to process discovery［J］. Information Sciences， 2022， 606： 250-271.

［16］Wang Mimi， He Xudong， Zhao Peihai. Process model enhancement through capturing important behaviors and rating trace variants［J］. IEEE Access， 2021， 9： 1zsdjK2vpPAr15BR51DgnmQ==43634-143660.

［17］Tsoury A， Soffer P， Reinhartz-Berger I. How well did it recover？ Impact-aware conformance checking［J］. Computing， 2021， 103（1）： 3-27.

［18］白少康， 方賢文， 錢陳婧. 基于數(shù)據(jù)影響的業(yè)務(wù)流程一致性檢查方法［J］. 計(jì)算機(jī)應(yīng)用研究， 2024， 41（2）： 540-547. （Bai Shaokang， Fang Xianwen， Qian Chenjing. Business process conformance checking method based on data impact［J］. Application Research of Computers， 2024， 41（2）： 540-547.）

［19］王麗麗， 向小陽， 方賢文. 基于日志聚類構(gòu)造行為子集的近似一致性方法［J］. 計(jì)算機(jī)應(yīng)用研究， 2022， 39（6）： 1872-1878. （Wang Lili， Xiang Xiaoyang， Fang Xianwen. Approximate consistency method for constructing behavior subsets based on log clustering［J］. Application Research of Computers， 2022， 39（6）： 1872-1878.）

［20］Lu Ke， Fang Xianwen， Fang Na， et al. Discovery of effective infrequent sequences based on maximum probability path［J］. Connection Science， Taylor & Francis， 2022， 34（1）： 63-82.