基于行為向量的在線事件流預(yù)測(cè)

盧 可，方賢文,2+，方 娜

(1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.同濟(jì)大學(xué) 嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，上海 201804)

0 引言

業(yè)務(wù)流程監(jiān)控在運(yùn)行時(shí)分析系統(tǒng)執(zhí)行信息，以了解系統(tǒng)的性能和與目標(biāo)的偏差。預(yù)測(cè)能夠提前感知異常情況，在業(yè)務(wù)流程監(jiān)控中發(fā)揮著重要的作用[1]。常見(jiàn)的預(yù)測(cè)目標(biāo)包括預(yù)測(cè)案例完成之前的剩余時(shí)間[2-4]、下一個(gè)活動(dòng)[5-7]、下一個(gè)時(shí)間戳[8-9]、所使用的資源[10]等。其中，預(yù)測(cè)下一個(gè)活動(dòng)能夠使業(yè)務(wù)流程的相關(guān)人員預(yù)先對(duì)系統(tǒng)中的風(fēng)險(xiǎn)采取應(yīng)對(duì)措施，預(yù)防系統(tǒng)出現(xiàn)問(wèn)題[11]。為了能對(duì)逐年驟增的業(yè)務(wù)流程及時(shí)做出反應(yīng)，近年很多學(xué)者開(kāi)始關(guān)注在線過(guò)程分析[12]，而正在運(yùn)行的實(shí)例信息通常以事件流的形式記錄，因此研究基于在線事件流愈發(fā)重要。

早期研究通常關(guān)注存儲(chǔ)于數(shù)據(jù)庫(kù)的離線數(shù)據(jù)[13]，通過(guò)隱馬爾科夫模型等統(tǒng)計(jì)方法分析信息系統(tǒng)生成的日志信息，獲得對(duì)企業(yè)面臨的相關(guān)問(wèn)題的深入思考[14]。還有一些研究采用推薦系統(tǒng)中的方法分析日志，以推薦下一個(gè)活動(dòng)的形式進(jìn)行預(yù)測(cè)分析[15]。

近些年，隨著計(jì)算機(jī)硬件和人工智能的發(fā)展，一些研究受到自然語(yǔ)言處理(Natural Language Processing, NLP)的啟發(fā)，將事件日志視為文本，引入深度學(xué)習(xí)的思想，將預(yù)測(cè)下一個(gè)事件轉(zhuǎn)為預(yù)測(cè)句子中下一個(gè)單詞的問(wèn)題來(lái)處理[16]。在此背景下，循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network, RNN)[17]、長(zhǎng)—短期記憶網(wǎng)絡(luò)(Long Short Term Memory, LSTM)[9,18]、卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks, CNN)[11,19]、堆疊式自動(dòng)編碼器[20]等各種先進(jìn)的神經(jīng)網(wǎng)絡(luò)被應(yīng)用于預(yù)測(cè)下一個(gè)事件場(chǎng)景。EVERMANN等[17]描述了具有遞歸神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)在預(yù)測(cè)下一個(gè)過(guò)程事件上的初步應(yīng)用；CAMARGO等[9]提出一種采用LSTM架構(gòu)訓(xùn)練遞歸神經(jīng)網(wǎng)絡(luò)的方法，以預(yù)測(cè)下一個(gè)事件的剩余序列、運(yùn)行周期時(shí)間及相關(guān)資源；LIN等[18]采用LSTM網(wǎng)絡(luò)對(duì)事件信息及其屬性分別編碼，然后將其組合在一起作為給定序列歷史信息的隱藏表示，再用另一個(gè)LSTM層作為解碼器，同時(shí)對(duì)下一個(gè)事件及其屬性進(jìn)行預(yù)測(cè)。受到前期深度學(xué)習(xí)算法在預(yù)測(cè)性過(guò)程挖掘領(lǐng)域的啟發(fā)，AL-JEBRNI等[11]采用五層一維卷積神經(jīng)網(wǎng)絡(luò)(one-Dimensional Convolution Neural Network, 1D CNN)預(yù)測(cè)下一個(gè)過(guò)程事件，并在所提供的數(shù)據(jù)集上取得當(dāng)時(shí)同領(lǐng)域最佳的表現(xiàn)；PASQUADIBISCEGLIE等[19]同樣采用CNN將業(yè)務(wù)流程歷史事件日志中包含的時(shí)間數(shù)據(jù)轉(zhuǎn)換為空間數(shù)據(jù)，然后用空間數(shù)據(jù)訓(xùn)練CNN，以預(yù)測(cè)下一個(gè)活動(dòng)；MEHDIYEV等[20]則采用一種多階段的深度學(xué)習(xí)算法，包括無(wú)監(jiān)督的預(yù)訓(xùn)練組件與堆疊的自動(dòng)編碼器和有監(jiān)督的微調(diào)組件，并在各種業(yè)務(wù)流程日志數(shù)據(jù)集上得到了較好的結(jié)果。

雖然深度學(xué)習(xí)領(lǐng)域的方法均已成功用于真實(shí)案例，但是仍然存在一些缺陷。目前關(guān)于預(yù)測(cè)下一個(gè)事件的方法以事件流為研究起點(diǎn)，采用One-Hot編碼[2,7,10,21]或者基于事件的頻率[19]表示事件流。One-Hot編碼具有以下特點(diǎn)：①假設(shè)對(duì)象之間相互獨(dú)立；②不考慮對(duì)象之間的順序。

然而事件流之間不僅相互影響，還有特定的行為關(guān)系，因此采用One-Hot編碼會(huì)導(dǎo)致研究過(guò)程中缺少對(duì)事件流行為的分析。因此，本文提出基于行為編碼的預(yù)測(cè)方法，主要貢獻(xiàn)如下：

(1)定義了基于實(shí)時(shí)數(shù)據(jù)的事件流行為輪廓。通過(guò)細(xì)化事件流之間的行為關(guān)系，捕獲活動(dòng)之間的順序、循環(huán)、并發(fā)及排他關(guān)系。

(2)提出一種新的事件編碼方式——行為編碼，對(duì)活動(dòng)進(jìn)行編碼，從而衡量活動(dòng)之間的行為距離、內(nèi)在聯(lián)系和活動(dòng)順序。

(3)采用協(xié)同過(guò)濾的思想對(duì)當(dāng)前事件流進(jìn)行推薦，從而預(yù)測(cè)下一個(gè)可能發(fā)生的事件流。

1 基本概念

本章介紹了本文所需的背景知識(shí)，包括活動(dòng)、跡、事件日志(如表1)、事件流和傳統(tǒng)的模型行為輪廓。

表1 事件日志片段

1.1 日志和事件流

事件是活動(dòng)的一次執(zhí)行，可以由各種屬性表征。例如，事件可以具有時(shí)間戳、與活動(dòng)相對(duì)應(yīng)的名稱、特定的執(zhí)行人員和執(zhí)行的相關(guān)成本等屬性。事件日志由多組事件序列構(gòu)成，其與事件流的區(qū)別在于，事件日志是存儲(chǔ)于數(shù)據(jù)庫(kù)或本地文檔的有限、離線數(shù)據(jù)，事件流是系統(tǒng)運(yùn)行時(shí)的無(wú)限、實(shí)時(shí)數(shù)據(jù)。

定義2事件流[23]。A為一組活動(dòng)集，C為所有可能的案例標(biāo)識(shí)符的集合。事件流S=(c,a)為C×A上的序列，即S∈(C×A)*，其中c∈C,a∈A。

Si=(c,a)表示i時(shí)刻，案例標(biāo)識(shí)符為c，發(fā)生了活動(dòng)a。兩個(gè)事件流之間的距離記為D(Si,Sj)。Si的下一個(gè)事件流Sj需同時(shí)滿足兩個(gè)條件：①與Si具有相同的案例標(biāo)識(shí)符；②與Si距離最小。

1.2 模型的行為輪廓

為了捕獲過(guò)程模型的基本行為約束，本節(jié)引入模型行為輪廓的概念(簡(jiǎn)稱行為輪廓)。

定義3行為輪廓[24]。假設(shè)(N,M0)為一個(gè)網(wǎng)，對(duì)于任意變遷對(duì)(t1,t2)∈(T×T)：

(1)若t1?t2且t2t1，則t1和t2為嚴(yán)格序關(guān)系，記作t1→t2。

(2)若t1t2且t2?t1，則t1和t2為嚴(yán)格逆序關(guān)系，記作t1←-1t2。

(3)若t1t2且t2t1，則t1和t2為排他關(guān)系，記作t1+t2。

(4)若t1?t2且t2?t1，則t1和t2為交叉序關(guān)系，記作t1||t2。

將所有關(guān)系的集合稱為網(wǎng)系統(tǒng)的行為輪廓，記作BP={→,←-1,+,||}。

1.3 協(xié)同過(guò)濾

作為推薦系統(tǒng)中的重要技術(shù)，協(xié)同過(guò)濾[25]廣泛應(yīng)用于電子商務(wù)，根據(jù)用戶或項(xiàng)目之間的關(guān)系，其能夠從候選集中推薦出最相似的選擇。本文將預(yù)測(cè)系統(tǒng)運(yùn)行的事件流問(wèn)題預(yù)測(cè)視為一種推薦問(wèn)題，采用推薦系統(tǒng)領(lǐng)域的方法分析系統(tǒng)的運(yùn)行情況，實(shí)時(shí)預(yù)測(cè)事件流的發(fā)生。傳統(tǒng)的協(xié)同過(guò)濾算法分為基于用戶的協(xié)同過(guò)濾、基于項(xiàng)目的協(xié)同過(guò)濾、基于模型的協(xié)同過(guò)濾3種類型，其中前兩種屬于基于記憶的協(xié)同過(guò)濾算法，因此具有相似的分析步驟[26]：

(1)計(jì)算用戶或項(xiàng)目之間的相似度 通過(guò)分析數(shù)據(jù)之間的關(guān)系比較數(shù)據(jù)中間的相似性。傳統(tǒng)的相似度度量方法有皮爾遜相關(guān)系數(shù)法、向量余弦法等[27]。

(2)尋找相似近鄰 經(jīng)過(guò)(1)計(jì)算后，需要選擇所需的相似的數(shù)據(jù)。尋找相似近鄰的方法主要有使用設(shè)定閾值和k近鄰搜索算法。

(3)TopN推薦[28]協(xié)同過(guò)濾算法根據(jù)近鄰信息為用戶返回候選的推薦列表。本文采用協(xié)同過(guò)濾的基本思想，將其應(yīng)用到實(shí)時(shí)預(yù)測(cè)的事件流情景中。

2 基于事件流行為向量的預(yù)測(cè)

當(dāng)前研究工作已經(jīng)對(duì)各種預(yù)測(cè)方法進(jìn)行了探索，如基于Markov等統(tǒng)計(jì)模型的預(yù)測(cè)方法、基于自動(dòng)機(jī)的預(yù)測(cè)方法和基于Petri網(wǎng)的預(yù)測(cè)方法等(關(guān)于這幾類方法的對(duì)比可參閱文獻(xiàn)[6])，這些方法在分析事件日志或事件流時(shí)，有些只考慮活動(dòng)與前驅(qū)和后繼的關(guān)系，有些只考慮活動(dòng)本身的狀態(tài)，有些甚至沒(méi)有體現(xiàn)活動(dòng)之間的關(guān)系。為了在預(yù)測(cè)分析過(guò)程中考慮事件流以及所有事件流之間的行為關(guān)系，需要一種新的事件流編碼方式將事件流輸入到算法中。因此，本章提出一種協(xié)同過(guò)濾算法，基于事件流的行為向量實(shí)時(shí)預(yù)測(cè)系統(tǒng)中即將發(fā)生的下一個(gè)事件流。

2.1 定義事件流行為輪廓

傳統(tǒng)的行為輪廓旨在分析模型中活動(dòng)之間的序列關(guān)系，捕獲過(guò)程模型中存在的基本行為約束[24]。本文需要對(duì)事件流進(jìn)行分析，而傳統(tǒng)的行為輪廓無(wú)法直接滿足需求，因此本節(jié)基于傳統(tǒng)的行為輪廓重新定義一組行為輪廓關(guān)系概念來(lái)描述在線事件流之間的關(guān)系。

對(duì)于事件流S，尋找與其具有相同案例標(biāo)識(shí)符的事件流S′，基于這兩個(gè)事件流，給出事件流嚴(yán)格序的定義。為了便于體現(xiàn)事件發(fā)生的順序，在事件流的定義中考慮事件的發(fā)生時(shí)間t。

圖1所示為嚴(yán)格序的簡(jiǎn)單示例，其中S1=(1001,a)和S3=(1001,b)是一對(duì)嚴(yán)格序關(guān)系的事件流。因?yàn)镾1和S3的案例標(biāo)識(shí)符均為1001，S2=(1002,e)的案例標(biāo)識(shí)符為1002，不滿足定義的第一個(gè)條件，而S6=(1001,c)的案例標(biāo)識(shí)符雖然也是1001，但是D(S1,S6)=5>D(S1,S3)=2,所以S6并不是與S1距離最近的下一個(gè)事件流。

嚴(yán)格序反映了事件之間的順序關(guān)系，其前件事件流的發(fā)生時(shí)間在前，后件事件流的發(fā)生時(shí)間在后，后面發(fā)生的事件總是在前面發(fā)生的事件之后，因此容易推導(dǎo)出嚴(yán)格序具有傳遞性，將此傳遞性形式化為性質(zhì)1：

定義5事件流間接嚴(yán)格序。事件流間接嚴(yán)格序簡(jiǎn)稱為間接嚴(yán)格序，記為，事件流和Si之間的間接嚴(yán)格序表示為

基于模型結(jié)構(gòu)的行為輪廓可以快速獲取行為之間的各種關(guān)系，然而在源源不斷的實(shí)時(shí)數(shù)據(jù)流中，能直接獲取的只有前后密切相關(guān)的嚴(yán)格序。因此，欲分析事件流中的所有事件，只關(guān)注某一時(shí)刻的運(yùn)行狀態(tài)遠(yuǎn)遠(yuǎn)不夠。這里將觀察的范圍擴(kuò)大，使用輸入流的滑動(dòng)窗口[29]對(duì)接收的數(shù)據(jù)進(jìn)行分析。

如果對(duì)于任意c∈C，滑動(dòng)窗口w中的事件流Si和Sj都不存在i和j，使得Si→Sj或者Sj→Si，則Si和Sj為事件流排他序。如圖2所示，Si=(1001,b)和Sj=(1002,c)在窗口w中為排他序。

定義6事件流排他序。事件流排他序簡(jiǎn)稱為排他序，記為+，Si和Sj之間的排他序表示為Si+Sj，if ?i,j∈[0,∞],c∈C?SiSj∨SjSi。

從傳統(tǒng)行為輪廓的定義可知，出現(xiàn)交叉序的情況分為兩種：①并發(fā)結(jié)構(gòu)導(dǎo)致的事件發(fā)生順序不確定，而且事件不處于任何一個(gè)循環(huán)結(jié)構(gòu)中；②由于循環(huán)結(jié)構(gòu)導(dǎo)致一組事件重復(fù)發(fā)生，從而使同一活動(dòng)在執(zhí)行時(shí)呈現(xiàn)交叉序。這兩種情況增大了分析模型的難度，因此將交叉序細(xì)化，分為并發(fā)交叉序和循環(huán)交叉序兩種情況分別討論。

如果在窗口w中，對(duì)于Si和Sj既有Si→Sj，又有Sj→Si，則Si和Sj為交叉序。

定義7事件流并發(fā)交叉序。事件流并發(fā)交叉序簡(jiǎn)稱為交叉序，記為||，Si和Sj之間的交叉序表示為Si||Sj，if ?i,j∈[0,∞],?c1∈C?Si→Sj∧?c2∈C?Sj→Si。

如果在窗口w中一組事件流重復(fù)出現(xiàn)，則這組事件流中的每個(gè)事件與其自身為循環(huán)交叉序(如圖3)，循環(huán)體的不同事件之間是嚴(yán)格序。

定義8事件流循環(huán)交叉序。事件流循環(huán)交叉序簡(jiǎn)稱為循環(huán)交叉序，Si和Sj之間的循環(huán)交叉序表示為Si||○Sj,if …SiSi+1Si+2S…Sj…,?i,j∈[0,∞]?Si=Sj。

定義9事件流循環(huán)內(nèi)嚴(yán)格序。簡(jiǎn)稱為循環(huán)內(nèi)嚴(yán)格序(如圖4)，Si和Sj之間的循環(huán)內(nèi)嚴(yán)格序表示為Si○→Sj，如果存在一個(gè)案例c，使Si和Sj處于一個(gè)循環(huán)序列中，且Si→Sj。

以上定義的6種事件流之間的關(guān)系形成了事件流的行為輪廓，而事件發(fā)生的頻率在一定程度上能夠體現(xiàn)其在系統(tǒng)中的重要性，因此將頻率作為事件流行為輪廓的一部分。

定義10事件流行為輪廓EBP。EBPR={…,(Si,Sj)N,…},i,j∈(1,∞)，其中R={→,,||,||○,○→,+}為行為關(guān)系，N為R在窗口w內(nèi)發(fā)生的次數(shù)，記作∏(SiRSj)=N。

2.2 在線識(shí)別事件流行為輪廓

本節(jié)通過(guò)在線事件流行為輪廓，從正在運(yùn)行的系統(tǒng)中學(xué)習(xí)事件流之間的行為關(guān)系。因?yàn)槭录魇腔顒?dòng)在某一時(shí)刻的運(yùn)行狀態(tài)，數(shù)據(jù)項(xiàng)的順序已經(jīng)由每個(gè)項(xiàng)到達(dá)的時(shí)間戳決定[25]，所以在特定時(shí)刻只能觀察到某個(gè)事件及其前一個(gè)事件。而事件流行為輪廓的后3種關(guān)系均建立在嚴(yán)格序的基礎(chǔ)上，因此首先需要從事件流中獲取嚴(yán)格序關(guān)系。

首先假設(shè)事件流為單線程，這樣系統(tǒng)中每次只有一個(gè)案例c1在發(fā)生，當(dāng)c1結(jié)束后，c2才可以發(fā)生。采用一個(gè)集合EBP→存儲(chǔ)獲取的所有嚴(yán)格序。在時(shí)刻i，觀察到事件流Si及其上一個(gè)事件Si-1，根據(jù)定義2判斷Si-1和Si之間的關(guān)系為嚴(yán)格序，即Si-1→Si，將其加入集合EBP→，此時(shí)EBP→={(Si-1,Si)}。同樣，在時(shí)刻j對(duì)其進(jìn)行同樣操作，可得Sj-1→Sj。以此類推，每個(gè)新到達(dá)的事件流均被立即處理。如果該嚴(yán)格序是第一次出現(xiàn)，即Si-1≠Sj-1或Si≠Sj，則直接加入集合，此時(shí)EBP→={(Si-1,Si),(Sj-1,Sj)}；如果已經(jīng)在集合中出現(xiàn)了至少一次，如Si-1=Sj-1且Si=Sj，則更新該項(xiàng)的次數(shù)，記為EBP→={(Si-1,Si)2}。

上述分析只適用于理想情況，即連續(xù)的事件流都屬于同一個(gè)案例c，且事件發(fā)生時(shí)必須是連續(xù)、不可中斷的，然而這種理想狀況在實(shí)際中出現(xiàn)的概率非常低，而且因?yàn)橛布目焖侔l(fā)展，絕大多數(shù)系統(tǒng)都支持多線程同時(shí)進(jìn)行，只著眼于某一時(shí)刻無(wú)法洞悉整個(gè)系統(tǒng)的結(jié)構(gòu)，所以引入滑動(dòng)窗口來(lái)擴(kuò)大事件流的檢測(cè)視圖，構(gòu)造滑動(dòng)窗口中所有活動(dòng)之間的行為關(guān)系矩陣。

滑動(dòng)窗口分為基于時(shí)間定義的滑窗和基于元組個(gè)數(shù)定義的計(jì)數(shù)滑窗兩類，本文基于滑動(dòng)窗口觀察運(yùn)行的事件流，將事件流按照發(fā)生的時(shí)間戳重新定義單位時(shí)間，只考慮事件流的到達(dá)順序而不關(guān)注具體的時(shí)間點(diǎn)，即采用基于元組個(gè)數(shù)定義的滑動(dòng)窗口。

為了同時(shí)分析滑動(dòng)窗口中的多個(gè)案例，需要設(shè)置一個(gè)緩存機(jī)制。首先將滑動(dòng)窗口內(nèi)各個(gè)案例的第1個(gè)事件Si=(ci,xi)，Sj=(cj,xj)，Sk=(ck,xk)等保存到緩存機(jī)制中，當(dāng)下一時(shí)刻匹配到擁有相同案例標(biāo)識(shí)符的第2個(gè)事件時(shí)，如出現(xiàn)Si+1=(ci,xi+1)，將該案例的第1個(gè)Si=(ci,xi)從緩存機(jī)制中取出，采用本節(jié)開(kāi)始的方法對(duì)Si和Si+1進(jìn)行分析。重復(fù)以上步驟，直到事件流結(jié)束，可以獲得一個(gè)當(dāng)前滑動(dòng)窗口范圍內(nèi)觀測(cè)到的所有事件流的一個(gè)完整嚴(yán)格序集EBP→={(S1,S2)m,…,(Si,Sj)n,…}。

由于滑動(dòng)窗口視圖擴(kuò)大了分析的范圍，此時(shí)可以觀察到事件流中包含的循環(huán)結(jié)構(gòu)。對(duì)于其中的循環(huán)結(jié)構(gòu)，通過(guò)循環(huán)交叉序的定義可以識(shí)別出符合循環(huán)交叉序的事件流，將其加入循環(huán)交叉序集EBP||○。若Si=(ci,xi)||○Si=(ci,xi)，則Si中的xi為循環(huán)體的起始事件，將其作為循環(huán)的開(kāi)始標(biāo)志。對(duì)循環(huán)體只分析一次，以避免重復(fù)分析，循環(huán)體內(nèi)部的嚴(yán)格序加入循環(huán)嚴(yán)格序集EBP||→中。

隨后通過(guò)嚴(yán)格序集，根據(jù)定義推導(dǎo)其他行為關(guān)系。如果不包含循環(huán)結(jié)構(gòu)，而且在嚴(yán)格序集EBP→中，既有(Si,Sj)n也有(Sj,Si)m，則Si和Sj為并發(fā)交叉序關(guān)系，將其加入并發(fā)交叉序集EBP||中。為了全面探索活動(dòng)之間的行為關(guān)系，用行為關(guān)系矩陣表示已經(jīng)獲得的行為關(guān)系。

定義11行為關(guān)系矩陣

EBP→∪EBP∪EBP○→∪EBP||∪EBP||○

∪EBP+,Rij∈{→,,○→,||,||○,+}。

行為關(guān)系矩陣的行和列分別表示事件流中的活動(dòng)集，矩陣中的元素表示活動(dòng)對(duì)之間的行為關(guān)系及發(fā)生頻率。將嚴(yán)格序集和循環(huán)交叉序的元素存儲(chǔ)在行為關(guān)系矩陣的對(duì)應(yīng)位置，很容易推導(dǎo)出間接嚴(yán)格序，將其存入間接嚴(yán)格序集EBP中。此時(shí)矩陣中仍然存在空值，表示對(duì)應(yīng)的兩個(gè)活動(dòng)x，y之間沒(méi)有前面所述的4種行為關(guān)系，即x，y為排他序，將對(duì)應(yīng)事件存入排他序集EBP+中。最后將4個(gè)集合中的元素按照對(duì)應(yīng)關(guān)系存入行為關(guān)系矩陣，將推導(dǎo)事件流之間行為關(guān)系的步驟形式化為算法1。

算法1推導(dǎo)事件流行為關(guān)系。

輸入:事件流S。

輸出:事件流行為矩陣M。

1 Initialization Slide Window w,Event Stream Behavioural MatrixM, EBP→,EBP,EBP‖,EBP,EBP,EBP+;

2 for S in w do

3 if (Si,Sj) in EBP→then

4 ∏(Si,Sj)=N+1

5 else

6 EBP→←(Si,Sj)

7 end

8 if Sj=Skin Sito Si+wthen

9 EBP←(Sj,Sj);

10 EBP←other event stream between Siand Si+w

11 end

12 end

13 for i,j inMdo

14 if Mijis null then

15 if (Si,Sj)nand (Sj,Si)min EBP→then EBP‖→←(Si,Sj)n,(Sj,Si)m;

16 if (Sx,Sx+1),…,(Sx+y-1,Sx+y) in EBP→then EBP←(Sx,Sx+y);

17 else EBP+←(Si,Sj);

18 end

19 end

20M←EBP→∪EBP∪EBP‖∪EBP∪EBP∪EBP+

輸出：M

算法1第1～11行通過(guò)緩存事件流直接獲取一部分事件流行為輪廓關(guān)系。其中第3～7行分析一對(duì)事件流的嚴(yán)格序關(guān)系，如果該關(guān)系已經(jīng)存在于事件流行為矩陣M中，則計(jì)數(shù)加1，否則將其存入事件流嚴(yán)格序集EBP→中。如果該關(guān)系的逆已經(jīng)存在于M中，則將其關(guān)系替換為循環(huán)交叉序集EBP||○，并將該關(guān)系及其逆序從嚴(yán)格序集中刪除。

當(dāng)對(duì)事件流的分析結(jié)束時(shí)，再基于行為關(guān)系矩陣M推導(dǎo)其他行為關(guān)系(第12～19行)，關(guān)于推導(dǎo)循環(huán)內(nèi)嚴(yán)格序、間接嚴(yán)格序和排他序的關(guān)系的具體步驟在上文已經(jīng)給出。第20行獲得一個(gè)關(guān)于事件流中所有活動(dòng)之間的行為輪廓關(guān)系矩陣。

2.3 預(yù)測(cè)下一個(gè)事件

本節(jié)以協(xié)同過(guò)濾算法為基礎(chǔ)，對(duì)其每一步進(jìn)行調(diào)整以適應(yīng)事件流場(chǎng)景。首先將事件流序列與事件流之間的行為特征結(jié)合，構(gòu)造一個(gè)既能體現(xiàn)行為關(guān)系，又能用于協(xié)同過(guò)濾的事件流向量，然后將其應(yīng)用于系統(tǒng)的事件流分析，對(duì)每個(gè)運(yùn)行中的事件流進(jìn)行實(shí)時(shí)預(yù)測(cè)。

2.3.1 構(gòu)造行為向量

在描述算法之前，先定義一些新概念。為了便于計(jì)算事件流之間的相似度，即具有相同案例標(biāo)識(shí)符的事件構(gòu)成的序列，需要將向量作為輸入。首先定義一個(gè)映射函數(shù)，將行為輪廓矩陣中的關(guān)系映射成為特定的數(shù)值。

定義12行為輪廓映射函數(shù)。使用行為輪廓映射函數(shù)F(R)=N,N∈[-3,3]，將行為輪廓矩陣轉(zhuǎn)換為一個(gè)整數(shù)型行為關(guān)系矩陣M′，其每個(gè)元素均為特定范圍間的整數(shù)。

通過(guò)定義12將事件流對(duì)應(yīng)的符號(hào)轉(zhuǎn)變?yōu)閿?shù)值型數(shù)據(jù)，這樣矩陣中的每一行就可以轉(zhuǎn)變?yōu)橐粋€(gè)數(shù)值型的行向量，將該行向量稱為事件流向量。

定義13事件流編碼

vi=[F(Ri1),F(Ri2),…,F(Rin)]=Mi,

n=count(Sd)。

式中：vi為第i個(gè)事件流的向量形式，n為不相同的事件流Sd的總數(shù)。事件流序列是由擁有相同案例標(biāo)識(shí)符的事件流構(gòu)成的序列。因此，將事件流序列向量表示為事件流向量的連接。

定義14事件流序列編碼

V=[…vi·vj…]=[…F(Ri1),F(Ri2),…,

F(Rin)，…，F(xiàn)(Rj1),F(Rj2),…,F(Rjn)，…]。

2.3.2 預(yù)測(cè)事件流

事件流的向量表達(dá)形式不僅可以用來(lái)反映事件流之間的順序、循環(huán)等結(jié)構(gòu)的相似性，還可以量化事件流在空間上的相似性。

定義15相似度

將預(yù)測(cè)事件流的步驟形式化為算法2，算法思想是基于已經(jīng)發(fā)生的m個(gè)事件流，預(yù)測(cè)第(m+1)個(gè)事件流。

算法2預(yù)測(cè)下一個(gè)事件流。

輸入:事件流關(guān)系矩陣M。

輸出:預(yù)測(cè)結(jié)果cond。

1 Initialization Event stream vertor V, similarity event stream squences matrix SimMatrix, Next event stream matrix Vnext;

2 begin

3 v['end']=|Set(events)|

4 M′=F(M)

5 for event,index in Set(events) do

6 v[event]=M′[index]

7 end

8 while event do

//kenel of algorithm

9 V=V.conc(v[event])

10 Vtemp=V.pad(v['end'])

11 foreach event′ in Set(events) do

12 add V.conc(v[event′]) to Vnext

13 end

14 SimMatrix=Sim(Vtemp,Vnext)

15 cond=KNN(SimMatrix,k)

16 end

17 end

構(gòu)造的事件流序列向量長(zhǎng)度為m×|Set(events)|，候選集的長(zhǎng)度為(m+1)×|Set(events)|，需要將向量擴(kuò)充至相同長(zhǎng)度。因此，算法2第3行先初始化一個(gè)空事件流向量，用于補(bǔ)齊事件流向量；第4行將行為輪廓矩陣中的符號(hào)轉(zhuǎn)換為數(shù)值型數(shù)據(jù)，得到對(duì)應(yīng)的整數(shù)型關(guān)系矩陣；第5～7行將矩陣的每一行賦值給每個(gè)事件流，即用事件流行為輪廓定義事件流編碼。

算法2第8～17行分析運(yùn)行中的事件流，每個(gè)事件流發(fā)生時(shí)(第8行)，將其轉(zhuǎn)換為對(duì)應(yīng)的事件流編碼(第9行)。此時(shí)的事件流序列中包含m個(gè)事件流，將其擴(kuò)充到m+1個(gè)事件流的長(zhǎng)度(第10行)。將候選事件流序列集用Vnext表示，在第11～13行將所有長(zhǎng)度為m+1的事件流列入候選集，然后通過(guò)Sim函數(shù)計(jì)算當(dāng)前事件流序列與候選事件流序列之間的相似度(第14行)。最后，采用k近鄰搜索算法得到最終預(yù)測(cè)結(jié)果(第15行)。

3 評(píng)估

本文基于Python實(shí)現(xiàn)了第2章所提算法。使用開(kāi)源的過(guò)程挖掘項(xiàng)目pm4py[30]將XES[31]格式的日志轉(zhuǎn)換為由事件流構(gòu)成的CSV格式，然后將其以數(shù)據(jù)流的形式傳入算法中模擬系統(tǒng)實(shí)時(shí)運(yùn)行的狀態(tài)。

3.1 推導(dǎo)行為關(guān)系

為便于掌握算法的運(yùn)行特點(diǎn)，首先采用結(jié)構(gòu)較簡(jiǎn)單的合成數(shù)據(jù)測(cè)試，然后用真實(shí)數(shù)據(jù)驗(yàn)證結(jié)果。

3.1.1 合成數(shù)據(jù)

首先使用合成事件日志“Artificial-Loan Process-Partial”作為測(cè)試數(shù)據(jù)。為了直觀查看日志的流程結(jié)構(gòu)，采用IM(inductive miner)挖掘算法[32]對(duì)該日志(包括98個(gè)案例、7個(gè)活動(dòng)、372個(gè)事件)進(jìn)行分析，得到一個(gè)Petri網(wǎng)形式的過(guò)程模型(如圖5)，然后將事件日志轉(zhuǎn)換為事件流數(shù)據(jù)。為了確定滑動(dòng)窗口的視圖尺寸，需要了解案例之間的時(shí)間跨度(具有相同案例的各個(gè)事件流與其第1個(gè)事件流之間的距離)，圖6所示的抖動(dòng)圖(可以將相同位置的點(diǎn)上下分散顯示)反映了轉(zhuǎn)儲(chǔ)后案例之間的跨度，可見(jiàn)案例之間的距離集中在0～43之間，因此將緩存大小設(shè)置為45，舍棄時(shí)間跨度過(guò)大的案例，獲取事件流之間的行為關(guān)系。

算法1挖掘合成日志的結(jié)果如表2所示。對(duì)照?qǐng)D5所示的模型結(jié)構(gòu)可見(jiàn)，事件流之間的各種關(guān)系均已正確地呈現(xiàn)在表2中。

表2 合成日志中各個(gè)事件之間的行為關(guān)系

3.1.2 真實(shí)數(shù)據(jù)

本節(jié)采用荷蘭金融機(jī)構(gòu)的貸款申請(qǐng)過(guò)程相關(guān)的日志“BPI Challenge 2017-Offer log”(簡(jiǎn)稱BPI 2017,https://data.4tu.nl/articles/dataset/BPI_Challenge_2017_-_Offer_log/12705737)進(jìn)行分析。數(shù)據(jù)包括2016年通過(guò)在線系統(tǒng)提交的所有申請(qǐng)及其后續(xù)事件，直到2017年2月1日15:11，共計(jì)193 849個(gè)事件，42 994個(gè)案例，8個(gè)活動(dòng)。由于事件發(fā)生的時(shí)間跨度較大，采用密度圖觀察時(shí)間間隔情況。如圖7所示，時(shí)間跨度集中在20 000個(gè)單位時(shí)間內(nèi)，舍棄該范圍之外的數(shù)據(jù)。

圖8所示為采用IM算法從真實(shí)日志中挖掘的過(guò)程模型，表3所示為采用算法1從事件流中捕獲的事件流之間的行為關(guān)系矩陣，表4所示為活動(dòng)名及其縮寫。對(duì)比之后發(fā)現(xiàn)，該日志雖然數(shù)量比較龐大，但是事件流之間的行為關(guān)系并不復(fù)雜，模型與行為關(guān)系之間差異較小。

表3 日志BPI2017中活動(dòng)間的行為關(guān)系

表4 日志BPI2017中的活動(dòng)名及其縮寫

3.2 度量行為距離

因?yàn)楹铣扇罩镜男袨殛P(guān)系比較簡(jiǎn)單，所以本節(jié)只分析真實(shí)日志BPI2017對(duì)應(yīng)的事件流在行為輪廓矩陣與One-Hot編碼下的行為距離。

首先比較兩種編碼下的數(shù)值分布。為便于觀察，將日志中的活動(dòng)對(duì)應(yīng)的行為向量編碼和One-Hot編碼繪制成熱圖(如圖9和圖10)，x軸和y軸分別為活動(dòng)的名稱和編碼。如圖9所示，行為向量編碼中的數(shù)值分布范圍較大，活動(dòng)之間差異明顯，更具標(biāo)識(shí)度。在圖10所示的One-Hot編碼中，數(shù)值比較稀疏，只有對(duì)角線上的數(shù)值為1，其他數(shù)值均為0。

采用常用的余弦相似度和Hamming相似度比較每?jī)蓚€(gè)活動(dòng)之間的相似性，如圖11和圖12所示。相似度與兩種編碼的數(shù)值規(guī)律相似，行為向量編碼下的活動(dòng)之間的相似度差異較明顯，能夠更好地區(qū)別不同活動(dòng)的關(guān)系。而One-Hot編碼下只有對(duì)角線上的活動(dòng)之間存在關(guān)系，其余活動(dòng)之間無(wú)論是順序、循環(huán)序，還是交叉序，都具有相同的相似性，與實(shí)際情況不符。

3.3 預(yù)測(cè)下一個(gè)事件流

本節(jié)比較使用行為編碼和One-Hot編碼對(duì)預(yù)測(cè)結(jié)果的影響。將事件流序列視為協(xié)同過(guò)濾中的項(xiàng)目，首先截取部分時(shí)間段內(nèi)的事件流序列進(jìn)行訓(xùn)練，然后用k近鄰搜索算法從候選集中以最佳推薦的形式獲得預(yù)測(cè)值。本文基于scikit-learn(Python實(shí)現(xiàn)的機(jī)器學(xué)習(xí)庫(kù))進(jìn)行預(yù)測(cè)分析，并采用以下度量標(biāo)準(zhǔn)：

(1)預(yù)測(cè)分?jǐn)?shù) 返回給定測(cè)試數(shù)據(jù)和標(biāo)簽上的平均準(zhǔn)確度，預(yù)測(cè)分?jǐn)?shù)越高，預(yù)測(cè)效果越好。

(2)Hamming損失 反映預(yù)測(cè)值和實(shí)際值差異程度，數(shù)值越小，預(yù)測(cè)結(jié)果越精確。

首先用合成日志進(jìn)行測(cè)試。分別對(duì)事件流序列使用以下方式進(jìn)行處理：①用行為向量編碼；②用行為向量編碼，同時(shí)將數(shù)據(jù)歸一化(sta_enc)；③用One-Hot編碼(onehot)。

分別選擇k(k∈[1,8])個(gè)最近鄰進(jìn)行預(yù)測(cè)，結(jié)果如圖13所示。隨著k的增長(zhǎng)，兩種編碼下的預(yù)測(cè)結(jié)果趨于相同值。這是由于KNN預(yù)測(cè)模型基于k個(gè)臨近點(diǎn)的投票機(jī)制進(jìn)行選擇，而近鄰數(shù)達(dá)到一定值后，投票的影響超過(guò)了編碼本身的影響?？傮w上基于①的預(yù)測(cè)結(jié)果最好，②次之，③的結(jié)果總體低于①和②，表明結(jié)合了事件之間的聯(lián)系后，采用行為向量編碼具有優(yōu)勢(shì)。

用網(wǎng)絡(luò)4個(gè)真實(shí)的公共日志“BPI Challenge 2017-Offer log”“Receipt”“Roadtraffic100traces”“Reviewing”(https://github.com/pm4py/pm4py-core/tree/release/tests/input_data)繼續(xù)驗(yàn)證，結(jié)果如表5所示，說(shuō)明相比One-Hot編碼，行為向量編碼能在一定程度上提升預(yù)測(cè)結(jié)果。

表5 使用事件流編碼對(duì)真實(shí)日志中事件流預(yù)測(cè)的結(jié)果

4 結(jié)束語(yǔ)

本文關(guān)注事件流之間的行為關(guān)系，提出一種新的事件流編碼形式來(lái)預(yù)測(cè)下一個(gè)事件流，通過(guò)使用少量緩存空間，能夠捕獲事件流之間的各種行為關(guān)系。為了捕獲事件流活動(dòng)之間的關(guān)聯(lián)性，定義了事件流行為輪廓矩陣，在此基礎(chǔ)上構(gòu)建了行為向量編碼。相比已有工作中的One-Hot編碼，行為向量編碼不僅將日志數(shù)據(jù)轉(zhuǎn)換為深度學(xué)習(xí)方法的輸入，還包含有事件流之間的行為關(guān)系。另外，調(diào)整后的協(xié)同過(guò)濾推薦算法能夠根據(jù)事件流之間的行為相似性更好地進(jìn)行預(yù)測(cè)。實(shí)驗(yàn)通過(guò)合成日志和真實(shí)日志證明了本文所提行為向量的優(yōu)勢(shì)，以及對(duì)協(xié)同過(guò)濾算法預(yù)測(cè)結(jié)果的提升效果。

本文算法僅考慮了事件流中的行為信息，并未考慮事件流的其他屬性，如所用的資源、事件的角色等，未來(lái)將根據(jù)屬性信息細(xì)化推薦結(jié)果，從而提高預(yù)測(cè)能力。另外，對(duì)于文中的部分參數(shù)設(shè)置，將采用有監(jiān)督的機(jī)器學(xué)習(xí)方法進(jìn)行優(yōu)化。