薛洋婷 王麗麗

摘 要：增量挖掘是在已有挖掘結(jié)果的基礎(chǔ)上，僅挖掘增量數(shù)據(jù)庫，更新已有的挖掘結(jié)果.傳統(tǒng)過程挖掘算法大多是批量式挖掘，模型精確度隨著日志不斷新增逐漸降低，獲得精確度高的模型需要從頭開始重新挖掘.因此，本文提出了一種增量挖掘優(yōu)化流程模型方法.首先，根據(jù)頻數(shù)高的事件日志的行為輪廓，構(gòu)建初始模型，頻數(shù)較低的日志，創(chuàng)建依賴關(guān)系樹;其次，通過部分新增日志來不斷更新依賴關(guān)系樹，進(jìn)而優(yōu)化模型;最后，通過具體的實(shí)例分析驗證了該方法有效.

關(guān)鍵詞：petri網(wǎng);行為輪廓;過程挖掘;增量挖掘

中圖分類號：TP391.9? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2019）10-0057-04

隨著信息技術(shù)的快速發(fā)展，業(yè)務(wù)流程管理發(fā)揮著越來越重要的作用.業(yè)務(wù)流程模型是業(yè)務(wù)流程管理的關(guān)鍵，挖掘出當(dāng)前業(yè)務(wù)流程模型至關(guān)重要.隨著事件日志不斷更新，傳統(tǒng)挖掘算法著重于從頭開始重新挖掘，這使得成本增加且效率低.因此，本文提出了增量挖掘優(yōu)化流程模型，在已挖掘出流程模型的基礎(chǔ)上，挖掘增量日志信息來更新模型.

目前，增量挖掘在數(shù)據(jù)挖掘中應(yīng)用比較廣泛.增量式的數(shù)據(jù)挖掘主要是指僅挖掘增量數(shù)據(jù)庫，更新已有的挖掘結(jié)果，得到最新的規(guī)則.文獻(xiàn)[1]一種靈活的聲明性框架，用于對流數(shù)據(jù)的物化視圖（即連續(xù)查詢的結(jié)果）進(jìn)行增量維護(hù).擬議框架的主要組成部分是View Delta函數(shù)（ViewDF），它聲明性地指定了在新批數(shù)據(jù)到達(dá)時如何更新物化視圖.文獻(xiàn)[2]提出了一種新的流量數(shù)據(jù)增量半監(jiān)督學(xué)習(xí)框架.每層模型都包含生成網(wǎng)絡(luò)，判別結(jié)構(gòu)和橋.生成網(wǎng)絡(luò)使用基于自動編碼器的動態(tài)特征學(xué)習(xí)來學(xué)習(xí)流數(shù)據(jù)的生成特征.文獻(xiàn)[3]提出了一種從增量數(shù)據(jù)庫中挖掘高效用模式的有效算法，其中一個數(shù)據(jù)庫掃描基于列表的數(shù)據(jù)結(jié)構(gòu)而沒有候選生成.該算法優(yōu)于先前的一階段構(gòu)造方法和候選生成.文獻(xiàn)[4]提出了IncGM+，一種用于在單個大型演化圖上進(jìn)行連續(xù)頻繁子圖挖掘的快速增量方法.將“邊緣”的概念適應(yīng)于圖形上下文，IncGM+維護(hù)邊緣子圖并利用它們來修剪搜索空間.文獻(xiàn)[5]提出了一種稱為IMU2P-Miner的增量算法，用于從單變量不確定數(shù)據(jù)中進(jìn)行增量最大頻繁模式挖掘.文獻(xiàn)[6]提出了一種新的增量關(guān)系關(guān)聯(lián)規(guī)則挖掘（IRARM）方法，旨在逐步調(diào)整數(shù)據(jù)集中標(biāo)識的有趣關(guān)系關(guān)聯(lián)規(guī)則.文獻(xiàn)[7]提出了一種通過處理子圖來檢測社區(qū)的增量方法.首先進(jìn)行綜合分析，并提出四種增量元素.然后建議不同更新策略.文獻(xiàn)[8]專注于增量更新，以選擇具有多個對象變體的新特征子集.首先，以遞增方式更新依賴性函數(shù)以評估候選特征的質(zhì)量.然后，當(dāng)在決策系統(tǒng)中添加或刪除多個對象時，會開發(fā)兩個增量特征選擇算法.文獻(xiàn)[9]提出了增量挖掘首先提取部分模型，然后在最后將它們集成到完整的模型中，新增日志能夠更新、擴(kuò)展和改進(jìn)部分流程模型.而本文則是先挖掘出初始模型，再對部分進(jìn)行改進(jìn)，從而優(yōu)化模型.

本文的其他部分內(nèi)容安排如下：第1節(jié)給出一個動機(jī)例子，第2節(jié)介紹基本概念，第3節(jié)介紹了一種增量挖掘優(yōu)化模型分析方法，第4節(jié)通過實(shí)例分析來驗證算法的可行性.最后，總結(jié)全文并展望未來的工作.

1 動機(jī)例子

現(xiàn)如今，網(wǎng)上購物已成為人們生活必需，本文只考慮買家中心其網(wǎng)上購物大致步驟：A，…，R分別表示登錄，選擇商品，加入購物車，購買商品，選擇支付方式，銀行卡支付，支付寶支付，支付成功，確認(rèn)收貨地址，修改收貨地址，訂單生成，取消訂單，交易關(guān)閉，確認(rèn)收貨，評價訂單，僅退貨，再收貨，退貨退款.表1記錄買家系統(tǒng)的事件日志序列及其實(shí)例數(shù)，根據(jù)表1的發(fā)生頻數(shù)高的事件日志信息構(gòu)建了圖1所示的初始模型M.該模型符合購物的一般流程，但通過分析發(fā)現(xiàn)，日志有的活動并未出現(xiàn)在流程模型M中.僅通過部分日志挖掘出的模型，精確度隨著日志更新而降低.因此，本文是針對不斷新增的日志進(jìn)行研究，利用日志活動之間的直接依賴關(guān)系創(chuàng)建依賴關(guān)系樹，通過更新依賴關(guān)系樹進(jìn)而優(yōu)化已得到的模型.

2 基本概念

定義1[10] （流程Petri網(wǎng)）一個流程模型Petri網(wǎng)PM=（P，T，F(xiàn)，C，s，e）是一個六元組，滿足以下條件：

其中，k為給定日志中的不同軌跡數(shù)，n為日志軌跡中所含的數(shù)目，x表示日志軌跡重放時就緒變遷的平均數(shù)目，m表示模型中可見任務(wù)的數(shù).

3 一種增量挖掘優(yōu)化模型分析方法

本節(jié)主要介紹增量挖掘更新流程模型，它是啟發(fā)式挖掘的擴(kuò)展.首先，給出啟發(fā)式挖掘相關(guān)定義;然后，給出增量挖掘優(yōu)化模型算法，它是利用現(xiàn)有挖掘方法挖掘出初始模型，頻數(shù)低的日志建立依賴關(guān)系樹，本文的依賴關(guān)系樹出自文獻(xiàn)[9]，它是AVL樹，它包含了候選關(guān)系，支持度和置信度值.通過重放適合度低的高頻數(shù)新增日志以及低頻數(shù)的新增日志來更新依賴關(guān)系樹，新增或刪除樹的結(jié)點(diǎn)，得到最終的依賴關(guān)系樹，確定依賴關(guān)系是否添加到模型，起到優(yōu)化模型的作用.

3.1 相關(guān)啟發(fā)式挖掘知識

3.2 增量挖掘優(yōu)化模型算法

輸入：初始日志L，新增日志InL，閾值σ

輸出：更新后的流程模型

步驟1.預(yù)處理事件日志，按事件日志發(fā)生頻數(shù)從大到小排列;

步驟2.根據(jù)頻數(shù)高的日志的行為輪廓，建立初始模型M;

步驟3.頻數(shù)低的日志組成日志L”;

步驟4.活動e1，e2，e3…∈L”，根據(jù)L”創(chuàng)建活動之間的依賴關(guān)系rel（e1，e2），rel（e1，e3），…，得到相應(yīng)活動下存在的依賴關(guān)系，如rel（e1，e2），rel（e1，e3）是活動e1下的依賴關(guān)系，對應(yīng)生成結(jié)點(diǎn)e2，e3;

步驟5.根據(jù)定義5，依次計算rel（e1，e2）支持度和置信度，同一活動的不同依賴關(guān)系之間添加有向弧，如第4步中活動e1下有兩個結(jié)點(diǎn)e2，e3，在e2和e3結(jié)點(diǎn)間添加有向弧;

步驟6.根據(jù)步驟4和5，創(chuàng)建不同活動下的依賴關(guān)系樹，如果活動e暫時沒有依賴關(guān)系，即沒有產(chǎn)生結(jié)點(diǎn)，也在依賴關(guān)系樹中保留該活動;

步驟7.每條新增日志，計算頻數(shù)高的日志與模型M的適合度aLP，低于給定值的日志InL和頻數(shù)低的新增日志，組成日志InL”;

步驟8.計算日志InL”中活動對的支持度和置信度;

步驟9.如果rel（e1，e2）置信度大于依賴關(guān)系樹中對應(yīng)活動對的置信度，更新e1活動下的依賴關(guān)系樹中rel（e1，e2）的置信度，如若小于，則刪除依賴關(guān)系樹中該結(jié)點(diǎn);

步驟10.依賴關(guān)系rel（e1，e2）在新增日志未再出現(xiàn)，繼續(xù)保留依賴關(guān)系樹中相應(yīng)的結(jié)點(diǎn);

步驟11.如果InL”出現(xiàn)新的活動對，在依賴關(guān)系樹添加結(jié)點(diǎn)，重復(fù)步驟8，9，10，直到得到最新的依賴關(guān)系樹;

步驟12.更新的依賴關(guān)系樹中的結(jié)點(diǎn)置信度在不斷增加越來越接近1，則認(rèn)為這一依賴關(guān)系存在，在流程模型中找到相應(yīng)活動，增加庫所和變遷，使得在模型中也存在這關(guān)系;

步驟13.更新后的流程模型.

4 實(shí)例分析

本節(jié)以上述提出的買家系統(tǒng)購物（動機(jī)例子）來驗證提出算法的可行性.頻數(shù)低的日志如表2所示，根據(jù)算法建立依賴關(guān)系樹如圖2，發(fā)現(xiàn)新的關(guān)系rel（K，E），rel（R，M），rel（N，R），rel（D，K）和rel（J，N）未在流程模型中出現(xiàn)，因此，通過新增日志更新依賴關(guān)系樹判斷是否更新模型，新增日志如表3所示，計算每個新增日志，得到適合度大于給定值0.95，即InL”只包含了頻數(shù)低的日志，如表4所示，用來更新的依賴關(guān)系樹，得到新的依賴關(guān)系樹，如圖3所示，圖2的活動關(guān)系對在新增日志未出現(xiàn)則保留這些依賴關(guān)系，也不更新流程模型，A，B，C，D，G，H，I，J，L，M，N，O，P，Q，R這些活動沒有增加或刪除新的關(guān)系，它們的支持度和置信度在增加或保持不變，因此，不更新流程模型.E，F(xiàn)這兩個活動出現(xiàn)新的關(guān)系rel（E，K），rel（F，I），活動K有刪除rel（K，E）=0.615小于0.992.

流程模型發(fā)生變化是活動未在流程模型中出現(xiàn)且隨著新增日志的增加其置信度在增加，則考慮在流程模型中添加該活動，如活動R可以在模型中添加，其置信度在增加從0.998到0.999;或者是有的活動刪除或新增關(guān)系結(jié)點(diǎn)也會引起流程模型的改變，如rel（K，E）就不在模型中更新;再者有依賴關(guān)系沒有在模型中出現(xiàn)，并且在新增日志中也為再出現(xiàn)這一關(guān)系，保留此關(guān)系并不更新流程模型，如rel（D，K），rel（J，N）.因此，得到新的流程模型如圖4.經(jīng)過行為適當(dāng)性計算aB（M）=0.419，aB（M1）=0.451，aB（M1）>aB（M），說明優(yōu)化后模型的行為適當(dāng)性得到了提高.

5 結(jié)束語

本文提出了一種增量挖掘優(yōu)化流程模型方法，首先，通過頻數(shù)高的日志建立初始模型，由于不是全部日志，因此需要對初步建立的模型進(jìn)行優(yōu)化分析.本文通過擴(kuò)展的啟發(fā)式挖掘，重新構(gòu)造了使用的數(shù)據(jù)結(jié)構(gòu)，以支持模型的增量更新，通過依賴關(guān)系樹的更新來優(yōu)化流程模型，最后，通過一個實(shí)例說明業(yè)務(wù)流程優(yōu)化方法的可行性.未來需要對復(fù)雜模型進(jìn)行優(yōu)化，且文章僅考慮了控制流方面對于數(shù)據(jù)流，資源等方面沒有考慮，將是下一步工作重點(diǎn).

參考文獻(xiàn)：

〔1〕Yuke Yang， Lukasz Golab ， M. Tamer Ozsu. ViewDF： Declarative incremental view maintenance for streaming data[J]. Information Systems，2017，（71）：55-67.

〔2〕Yanchao Li， Yongli Wang， Qi Liu，etal.Incremental semi-supervised learning on streaming data[J]. Pattern Recognition，2019，（88）：383-396.

〔3〕Unil Yun a ， Heungmo Ryang a ， Gangin Lee a ， Hamido Fujita An efficient algorithm for mining high utility patterns from incremental databases with one database scan[J]. Knowledge-Based Systems，2017：124：188–206.

〔4〕Ehab Abdelhamid， Mustafa Canim，etal. Incremental Frequent Subgraph Mining on Large EvolvingGraphs[C].IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING， 2017：2710-2723.

〔5〕Hanieh Fasihy ， MohammadHosseinNadimi Shahraki Incremental mining maximal frequent patterns from univariate uncertain data[J] Knowledge-Based Systems，2018，152： 40–50.

〔6〕Diana-Lucia Miholcaa， Gabriela Czibulaa， A new incremental relational association rules mining approach[J]. ScienceDirect nce，2018，126：126–135.

〔7〕Zhongying Zhao， Chao Li，etal. An incremental method to detect communities in dynamic evolving social networks[J]. Knowledge-Based Systems，2019，163：404–415.

〔8〕Wenhao Shu， Wenbin Qian b， Yonghong Xie Incremental approaches for feature selection from dynamic data with the variation of multiple objects[J]. Knowledge-Based Systems ，2019，163：320–331.

〔9〕Kalsing A C，Thom L H，Iochpe C， et al. AN INCREMENTAL PROCESS MINING ALGORITHM[C]. international conference on enterprise information systems， 2010： 263-268.

〔10〕Smirnov S， Weidlich M， Mendling J. Business Process Model Abstraction based on Behaviroural Profiles[C]. In 8th International Conference， San Francisco， December 7-10， 2010. Heidelberg： Springer Berlin Heidelberg， 2010， 6470：1-16.

〔11〕Weidlich M，Polyvyanyy A，Desai N，et al.Process compliance measurement based on behavioural profiles[C]. Advanced Information Systems Engineering.Berlin Heidelberg：Springer，2010：499-514.

〔12〕Van der Aalst W， Weijters T， Maruster L.Workflow mining： Discovering process models from event logs[J]. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（9）：1128-1142.

〔13〕Li S ， Li T ， Liu D . Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set[J]. Knowledge-Based Systems， 2013， 40：17-26.

〔14〕Li Y ， Liu X Q ， Hou J J . Maintaining Dynamic Information Systems Using Incremental Dominance-Based Rough Set Approach[J]. Applied Mechanics and Materials， 2014， 631-632：53-56.

〔15〕Shu W， Qian W. An incremental approach to attribute reduction from dynamic incomplete decision systems in rough set theory[J]. Data & Knowledge Engineering， 2015， 100：116-132.

〔16〕Jing Y ， Li T ， Luo C ， et al. An incremental approach for attribute reduction based on knowledge granularity[J]. Knowledge-Based Systems， 2016， 104：24-38.