基于行為包含的日志變化挖掘

詹 悅，王麗麗

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，業(yè)務(wù)管理系統(tǒng)需要設(shè)計(jì)高效的模型以滿足需求.但在實(shí)際操作過程中，當(dāng)一個(gè)小的細(xì)節(jié)被以錯(cuò)誤的方式運(yùn)行時(shí)，或者外部的變化（例如新的立法或公司）強(qiáng)加在這個(gè)過程上，系統(tǒng)都將被迫偏離指定的流程模型.然而，考慮到系統(tǒng)重設(shè)計(jì)是昂貴并且耗時(shí)的，所以如何發(fā)現(xiàn)運(yùn)行系統(tǒng)的實(shí)際模型與原設(shè)計(jì)模型之間的偏差并修復(fù)是目前工作的核心.過程挖掘技術(shù)［1］能夠從當(dāng)今信息系統(tǒng)記錄事件的日志中提取有價(jià)值的信息，這些技術(shù)為發(fā)現(xiàn)、監(jiān)控和改進(jìn)各種應(yīng)用領(lǐng)域的流程模型提供了新的手段.而變化挖掘是過程挖掘的一個(gè)重要分支，旨在發(fā)現(xiàn)實(shí)際模型或者運(yùn)行日志變化片段，修復(fù)系統(tǒng)漏洞并完善模型構(gòu)建.

已有的關(guān)于變化挖掘方面的文獻(xiàn)比較匱乏，大多數(shù)是針對(duì)日志挖掘模型或者模型間的變化傳播問題.一般地，適應(yīng)性過程提供了關(guān)于過程變化的附加信息（例如單個(gè)過程實(shí)例的臨時(shí)變化）可被用于管理系統(tǒng)組織.文獻(xiàn)［2］介紹了自適應(yīng)過程管理系統(tǒng)中挖掘變化日志的方法，通過過程挖掘匯總所有發(fā)生的變化過程.反過來，這可以作為各種過程改進(jìn)措施的基礎(chǔ)，例如觸發(fā)過程重設(shè)計(jì)或更好地控制機(jī)制.系統(tǒng)的適應(yīng)性導(dǎo)致了同一個(gè)流程模型可以產(chǎn)生多個(gè)結(jié)構(gòu)存在差異的變體.一般地，對(duì)此類模型變體的配置與維護(hù)成本極高.文獻(xiàn)［3］介紹了一個(gè)挖掘由配置變體而影響的參考模型，當(dāng)原始參考模型不可知的情況下，利用過程變體的聚合技術(shù)構(gòu)建一個(gè)完整的參考模型.文獻(xiàn)［4］利用行為輪廓挖掘多個(gè)對(duì)應(yīng)流程模型間的變化域，并利用變化傳播原則改進(jìn)模型以提高模型的可適應(yīng)性.文獻(xiàn)［5］根據(jù)模型結(jié)構(gòu)保質(zhì)性挖掘模型的動(dòng)態(tài)變化，但較少考慮到活動(dòng)的行為語義.文獻(xiàn)［6］提出了一種基于嵌套深度的測試，探索變化模式的使用對(duì)認(rèn)知復(fù)雜度的影響，有效地改進(jìn)了基于挖掘變化模式的建模設(shè)計(jì)工具.文獻(xiàn)［7］利用形態(tài)學(xué)片段提取事件日志中存在微量變化的可變片段，提高了過程片段的重用性和靈活性.文獻(xiàn)［8］根據(jù)一致性準(zhǔn)則對(duì)真實(shí)模型的動(dòng)態(tài)變化作出分類比較；文獻(xiàn)［9］在PAIS中提出了17個(gè)變化模式及6個(gè)變化支持特征，解決了特定變化系統(tǒng)框架的變化問題.以上的變化挖掘方法主要是針對(duì)變化的流程模型，或者先通過變化日志挖掘出實(shí)際模型，極少有直接作用于變化的事件日志.一個(gè)變化流程的誘導(dǎo)原因包括變化操作和因果關(guān)系，而這些變化將被記錄在實(shí)際事件日志中，所以對(duì)事件日志中隱藏的變化挖掘顯得尤為重要.

本文以行為包含［10］為基礎(chǔ)，提出了基于完備日志的后繼關(guān)系.通過比較日志中活動(dòng)間后繼關(guān)系與預(yù)先定義的模型間后繼關(guān)系，分析活動(dòng)所對(duì)應(yīng)的實(shí)際模型是否行為包含與原模型檢查一致性，并結(jié)合模型與日志的行為輪廓利用變化挖掘技術(shù)發(fā)現(xiàn)變化域［11］.

1 基本概念

定義 1［12］（流 程 模 型）一個(gè)六元組PM=(A,G,F,s,e,t)是一個(gè)流程模型，滿足下列幾條件：

A為有限的非空活動(dòng)集；

①G={and,xor}為有限的網(wǎng)關(guān)集；

②N=A?B為有限節(jié)點(diǎn)集，當(dāng)A?B=φ；

③F?N×N為流關(guān)系；

④ ·n={n′∈N|(n′,n)∈F}和為節(jié)點(diǎn) n 的前集；n·={n′∈N|(n,n′)∈F}為節(jié)點(diǎn) n 的后繼；

⑤ ?a∈A:|·a |≤1∧|a·|≤1；

⑥s∈A為唯一的開始活動(dòng)，即·s=φ；

⑦e∈A為唯一的結(jié)束活動(dòng)，即e·=φ；

變化挖掘的目的是提取出日志中活動(dòng)行為關(guān)系與模型存在變化的片段，所以下面定義關(guān)于活動(dòng)間關(guān)系的一些定義.

定義2［10］（k-后繼關(guān)系）S=(N,Mi)為一個(gè)網(wǎng)系統(tǒng)，其中N=(P,T,F).k∈N.則對(duì)于一條

跡 σ∈Τ(N,Mi)可定義 k- 后繼關(guān)系

定義3［10］（mink- 后繼關(guān)系）對(duì)于跡 σ定義mink-后繼關(guān)系：

同理對(duì)于系統(tǒng)S和日志L分別存在：

對(duì)于任意一個(gè)網(wǎng)系統(tǒng)為S=(N,Mi)，其中N=(P,T,F)中，都存在一個(gè)確定的后繼界bs，使得所有的mink-后繼系都滿足k≤bs；同理對(duì)于完備日志L，也存在一個(gè)確定的后繼界bL，使得所有的mink-后繼關(guān)系都滿足k≤bL.

定義 4［13］（基 于 日 志 的 弱 序 關(guān) 系）Lp=n1,...,nm為過程模型PM=(A,G,F,s,e,t)的一組日志.則弱序關(guān)系為?L?(AL×AL)，當(dāng)對(duì)于所有的活動(dòng)對(duì)(x,y)，存在兩個(gè)下標(biāo) j,k∈{1,...,m-1}且 j＜k≤m滿足nj=x,nk=y.

定義 5［13］（基于日志的行為輪廓）L={l1,l2,...,ln}為過程模型 PM=(A,G,F,s,e,t)的一組日志，li(1≤i≤n)為日志中的一條跡.一組活動(dòng)對(duì)(x,y)∈(AL×AL)至多滿足一下關(guān)系之一，集合 BL={→L′||L′×L}為日志 L 的行為輪廓.

①如果x?Ly且y?Lx，則為嚴(yán)格序關(guān)系→L；

②如果x?Ly且y?Lx，則為交叉序關(guān)系||L；

③如果x與y不在同一條有重復(fù)活動(dòng)的跡中出現(xiàn)，則為排他序關(guān)系×L.

此外，當(dāng)且僅當(dāng)滿足y→Lx的活動(dòng)對(duì)(x,y)為逆嚴(yán)格序關(guān)系，記為x→-1Ly.

2 基于行為包含的日志變化挖掘方法

系統(tǒng)開發(fā)之前都需要需求分析，即設(shè)計(jì)一個(gè)完整的預(yù)定義模型.如何測試實(shí)際開發(fā)的系統(tǒng)是否符合要求，必須對(duì)系統(tǒng)的結(jié)構(gòu)進(jìn)行分析.由于運(yùn)行系統(tǒng)的內(nèi)部架構(gòu)是不可視的，已有的方法是通過系統(tǒng)產(chǎn)生的大量事件日志重構(gòu)模型，再與原設(shè)計(jì)模型一致性比較，如圖1所示.但重構(gòu)模型并不能保證其質(zhì)量，此過程可能產(chǎn)生不一致的二次變化問題.

圖1 系統(tǒng)評(píng)估

為了有效提高系統(tǒng)測試結(jié)果，本文提出了基于行為包含的日志變化挖掘方法，直接對(duì)事件日志進(jìn)行分析（圖1中加粗箭頭），主要包括日志和模型后繼關(guān)系的計(jì)算，行為包含的具體誘導(dǎo)規(guī)則，以及如何利用行為包含與行為輪廓關(guān)系對(duì)完備日志進(jìn)行變化挖掘.

2.1 計(jì)算日志的行為包含

通過直接分析處理實(shí)際系統(tǒng)運(yùn)行產(chǎn)生的事件日志，可以挖掘出系統(tǒng)對(duì)應(yīng)仿真模型的變化片段.如果該日志所有活動(dòng)的行為關(guān)系都包含于預(yù)定義模型中，則說明實(shí)際系統(tǒng)符合設(shè)計(jì)規(guī)范與要求，否則存在變化.下文給出計(jì)算日志的活動(dòng)行為是否包含于預(yù)定義模型的具體方法.

定義 6［10］（行 為 包含）已知 網(wǎng) 系統(tǒng) 為S=(N,Mi)，其中N=(P,T,F)；實(shí)際日志為L.如果所有屬于日志L的投影跡σˉL∈Τˉ(L)，存在一條跡σ∈Τ(N,Mi)且滿足σˉL∈σ，則L抽象跡包含于S，即日志L行為包含于網(wǎng)系統(tǒng)S，記為L?S.

定義 7［10］（后 繼 包含）已知 網(wǎng) 系統(tǒng) 為S=(N,Mi)，其中N=(P,T,F)；實(shí)際日志為L.分別為他們的后繼關(guān)系.如果，則系統(tǒng)S后繼包含L記為L?S.

后續(xù)包含僅僅需要比較日志與預(yù)定義模型的所有后繼關(guān)系，如果后繼關(guān)系已知，則可在日志活動(dòng)個(gè)數(shù)的二次時(shí)間內(nèi)計(jì)算出結(jié)果，這種方法對(duì)比直接計(jì)算抽象跡包含更加高效.因此，如果某日志并不被包含于此后繼關(guān)系中，則該日志對(duì)應(yīng)的實(shí)際模型存在變化，可以進(jìn)一步研究其變化域或異常情況.

推論1：對(duì)于完備日志L和合理的自由選擇網(wǎng)S，后繼關(guān)系是抽象跡包含的充分必要條件，證明過程參照文獻(xiàn)［10］推論2和推論3.

2.2 基于日志行為輪廓的基本結(jié)構(gòu)

根據(jù)上文提出的后繼包含關(guān)系，可以判斷日志活動(dòng)行為是否包含于預(yù)定義模型，對(duì)于不滿足行為包含的活動(dòng)集合，利用基于日志的行為輪廓方法挖掘其對(duì)應(yīng)的變化片段.

要想準(zhǔn)確挖掘出變化活動(dòng)對(duì)應(yīng)的模型片段，必須明確基于日志行為輪廓的基本結(jié)構(gòu)，一些常見的結(jié)構(gòu)如下，活動(dòng)下標(biāo)代表滿足該結(jié)構(gòu)的活動(dòng)至少在跡中發(fā)生的次數(shù).

①如果日志L={...xy...}，即x→Ly，則對(duì)應(yīng)的基本結(jié)構(gòu)如圖2a；

② 如 果 日 志L={...xy...；...yx...}，即x1||Ly1，則對(duì)應(yīng)的基本結(jié)構(gòu)如圖2b；

③如果日志L={...xyx...}，即x2||Ly1，則對(duì)應(yīng)的基本結(jié)構(gòu)如果2c；

④如果日志L={...x...;...y...}，即x×Ly，則對(duì)應(yīng)的基本結(jié)構(gòu)如圖2d.

圖2 基本結(jié)構(gòu)

2.3 變化片段的挖掘方法

對(duì)于給定的一組事件日志，根據(jù)活動(dòng)間的行為包含關(guān)系可判斷日志對(duì)應(yīng)的模型是否存在變化.通過后繼包含關(guān)系找到其存在變化的活動(dòng)集合，然后結(jié)合日志的行為輪廓挖掘這些變化活動(dòng)對(duì)應(yīng)的局部模型片段.具體的算法如下.

基于行為包含的變化挖掘算法：

輸入：完備日志L，預(yù)定義模型S.

輸出：日志L對(duì)應(yīng)的變化片段FCT.

步驟1：初始化，設(shè)潛在的變化活動(dòng)組CT=φ.

步驟2：找出L與S中滿足對(duì)應(yīng)關(guān)系的活動(dòng)組T={t1,t2,...,tn}.

步驟3：根據(jù)定義7的后繼關(guān)系，遍歷日志的所有跡，建立具有對(duì)應(yīng)關(guān)系的活動(dòng)對(duì)間的mink-后繼關(guān)系表ti≥Lktj(1≤i,j≤n)，記長度為Length.

步驟4：遍歷模型，建立活動(dòng)對(duì)之間的mink-后繼關(guān)系表.

步驟5：比較一組日志活動(dòng)與模型活動(dòng)關(guān)系，當(dāng)前Length=Length-1.

步驟6：如果日志所有的活動(dòng)對(duì)均滿足后繼包含關(guān)系，則日志包含于模型即L?S，即FCT=φ.

步驟7：將不滿足后繼包含關(guān)系的日志活動(dòng)組并入潛在變化活動(dòng)組即CT?(ti,tj)，如果Length≠0，則返回步驟5.

步驟8：根據(jù)日志行為輪廓BL={→L,||L,×L}，計(jì)算CT的行為輪廓關(guān)系BLCT.

步驟9：根據(jù)BLCT的基本結(jié)構(gòu)構(gòu)建BLCT的模塊結(jié)構(gòu)，即為日志對(duì)應(yīng)的變化片段FCT.

Case 1：x→Ly，則為順序結(jié)構(gòu)；

Case 2：x||Ly，則為并發(fā)結(jié)構(gòu)；

Case 3：x2||Ly，則為循環(huán)結(jié)構(gòu)；

Case 4：x×Ly，則為選擇結(jié)構(gòu).

算法的核心思想就是判斷日志與預(yù)定義模型間的后繼包含關(guān)系.特別地，當(dāng)事件日志單條跡中存在重復(fù)活動(dòng)（或者模型存在循環(huán)結(jié)構(gòu)），k-后繼關(guān)系的k取值可無限增大.所以在實(shí)際應(yīng)用時(shí)，給定一個(gè)后繼界b，分別計(jì)算滿足k≤b下的所有日志與模型活動(dòng)后繼關(guān)系，有利于降低因循環(huán)結(jié)構(gòu)而帶來的計(jì)算復(fù)雜度.

3 實(shí)例分析

近年來網(wǎng)上購物十分火爆，但在實(shí)行過程中容易受到黑客或者木馬程序的攻擊，造成系統(tǒng)紊亂，商家和買家利益也因此受損.找出系統(tǒng)存在的變化區(qū)域或者異常點(diǎn)是解決系統(tǒng)故障的重要途徑，利用上述的方法可以明顯提高查找效率.圖3給出了系統(tǒng)預(yù)定義的模型包含以下活動(dòng)（用大寫字母表示）.表1為收集的該系統(tǒng)事件日志.

圖3 預(yù)定義模型

表1 事件日志L

表2 日志L的min1-后繼關(guān)系

表3 預(yù)定義模型S的min1-后繼關(guān)系

首先根據(jù)后繼關(guān)系的定義，遍歷預(yù)定義模型S和日志L，計(jì)算出對(duì)應(yīng)的mink-后繼關(guān)系，分別如表2、表3所示.從表中可以發(fā)現(xiàn)，活動(dòng)對(duì)(D,E)、(D,E)、(G,I)、(I,L)、(K,I)、(L,K)及(L,M)（表中陰影部分）均滿足min1-后繼關(guān)系≥L1，但不屬于≥S1.根據(jù)行為包含關(guān)系定義，不滿足后繼包含的活動(dòng)均存在變化或異常，所以可將包含{D,E}的變化活動(dòng)集合記為CT1，包含{G,I,K,L,M}的變化活動(dòng)集記為CT2.

然后，提取這些存在變化的活動(dòng)并根據(jù)基于日志的弱序關(guān)系計(jì)算它們之間的行為輪廓關(guān)系.由于在日志中，D?LE∧E?LD，可知D||LE形成CT1的行為輪廓關(guān)系BLCT1；

G?LI∧I?LG，可知G→LI，同理可得I→LL、K→LI、L→LK、L→LM形成CT2的行為輪廓關(guān)系BCT2.

最后，基于日志行為輪廓的基本結(jié)構(gòu)，構(gòu)建變化活動(dòng)集CT1與CT2的模塊結(jié)構(gòu)，記為變化片段FCT1與FCT2.由于存在變化的活動(dòng)對(duì)(D,E)屬于交叉關(guān)系，且在無重復(fù)活動(dòng)中僅發(fā)生一次，則對(duì)應(yīng)結(jié)構(gòu)片段如圖4a所示，后者(G,I)為嚴(yán)格序則對(duì)應(yīng)結(jié)構(gòu)為順序塊，由于I→LL→LK→LI，則存在循環(huán)結(jié)構(gòu)如圖4b所示.

圖4 日志L的變化片段

通過上述方法挖掘出的變化片段，與預(yù)定義模型的對(duì)應(yīng)片段（圖3的虛線框所示）可以發(fā)現(xiàn)在該網(wǎng)上購物系統(tǒng)中出現(xiàn)的異常情況，（D）在線支付與（E）到付只能選擇一種，而日志中隱含的為兩種支付方式都采用的異常狀況.其次是商家由于缺貨等原因選擇（G）拒絕接單，而系統(tǒng)可能自動(dòng)跳轉(zhuǎn)到其他仿冒商家繼續(xù)發(fā)貨（I），導(dǎo)致買家所購商品存在仿冒、質(zhì)量等問題.所以接下來對(duì)系統(tǒng)的修復(fù)問題只需針對(duì)支付系統(tǒng)與商家處理訂單及發(fā)貨的局部系統(tǒng)，大大地提高了系統(tǒng)變化檢測的效率.

4 結(jié)束語

針對(duì)系統(tǒng)內(nèi)部出現(xiàn)的不可視變化問題，提出了基于日志行為包含的概念并結(jié)合行為輪廓挖掘其變化域的方法，然后通過日志對(duì)應(yīng)的基本結(jié)構(gòu)構(gòu)建變化域的具體變化結(jié)構(gòu)［14］.與現(xiàn)有通過日志挖掘出實(shí)際模型再與預(yù)定義模型比較的方法，有效避免了重構(gòu)模型而引起的二次變化問題的產(chǎn)生，也為系統(tǒng)修復(fù)與優(yōu)化提供更可靠的基礎(chǔ).但由于實(shí)際系統(tǒng)運(yùn)行產(chǎn)生的日志質(zhì)量問題，針對(duì)不完備日志的行為包含變化挖掘技術(shù)與一致性分析，將在以后的工作中解決.