單觸發(fā)序列突發(fā)漂移檢測算法

原佳怡，朱 銳，林雷蕾，李 彤，鄭 明

(1.云南大學(xué) 軟件學(xué)院，云南 昆明 650091；2.云南省軟件工程重點實驗室，云南 昆明 650091；3.清華大學(xué) 軟件學(xué)院，北京 100084；4.云南農(nóng)業(yè)大學(xué) 大數(shù)據(jù)學(xué)院，云南 昆明 650201；5.云南大學(xué) 信息學(xué)院，云南 昆明 650500；6.山西師范大學(xué) 教師教育學(xué)院，山西 太原 030092)

0 引言

過程挖掘往往假設(shè)模型是穩(wěn)態(tài)的，而在真實的系統(tǒng)執(zhí)行過程中，過程模型往往是動態(tài)變更的[1]。這種在系統(tǒng)實際執(zhí)行過程中過程模型發(fā)生動態(tài)變更的現(xiàn)象稱為概念漂移。為了挖掘出更加符合真實變更的過程模型，有必要解決概念漂移現(xiàn)象帶來的模型演化問題。概念漂移檢測算法通過特征抽取等一系列檢測方法判斷出過程模型在實際執(zhí)行過程中發(fā)生了幾次演化，分別是如何演化的，從而更好地服務(wù)于過程發(fā)現(xiàn)，挖掘出更加符合實際過程的過程模型。過程在不斷執(zhí)行的進程中發(fā)生演化(或稱漂移點)是常有的事情，從過程的執(zhí)行日志中進行挖掘與定位漂移點可以用于尋找過程執(zhí)行中變化的區(qū)域。概念漂移是一種由于軟件系統(tǒng)的演化或行為的變化而引起的數(shù)據(jù)分布顯著變化的現(xiàn)象[2]。過程的概念漂移分為4個類型：突發(fā)漂移、漸變漂移、周期漂移和增量漂移[1]。其中：突發(fā)漂移是指過程模型在某一時間點前后不一致而發(fā)生演化的現(xiàn)象[3]。漸變漂移是指在某一時間段前后，模型發(fā)生了演化；而在這一時間段內(nèi)模型是從一個模型逐步演化到另一個模型的，同時也可能出現(xiàn)多個模型混合變更的現(xiàn)象[4]。周期漂移是指一段時間過后，總是重復(fù)之前的過程模型，且與現(xiàn)在的過程模型來回替換，這種重復(fù)可能是定期的，也可能是非定期的[1]。增量漂移是指原過程模型遵循某種較小的增量變化被不斷替換為新的過程模型，新的過程模型往往是更新迭代的功能更為齊全的過程模型，常出現(xiàn)在敏捷過程挖掘技術(shù)領(lǐng)域或全面質(zhì)量管理與改進領(lǐng)域[1]。周期漂移和增量漂移都有可能是突發(fā)漂移或漸變漂移[1]。本文重點研究單觸發(fā)序列的突發(fā)漂移檢測方法(Single-firing sequence Sudden Drift Detection, SSDD)，通過檢測單觸發(fā)序列中的漂移點來發(fā)現(xiàn)模型演化，從而更好地分析模型、挖掘出更合理的過程模型。

過程挖掘中認(rèn)為，過程是由案例組成的，案例是由事件組成的，事件日志的案例信息不可或缺[5]，即對事件日志L而言，L中元素的個數(shù)至少要大于等于1；但不是所有的實際系統(tǒng)中記錄的事件日志都具有案例屬性，實際系統(tǒng)中往往因為案例屬性的缺失或者系統(tǒng)本身不提供案例屬性而使得需要分析與挖掘的事件日志具有單實例性，即事件日志是一條只含有一個案例的軌跡，同時這個軌跡的長度往往大于活動集合的個數(shù)，形式化表示如下：設(shè)挖掘出的活動集為A，則事件日志L=[σ](|L|=1)，其中軌跡σ∈A*，A*為A上所有有限序列的集合。這種軌跡其實就是一組活動的序列(如σ=，其中對于1≤i≤n有ai=σ(i)，表示在軌跡σ中，位置i的活動為ai，|σ|=n表示軌跡的長度)，當(dāng)|σ|>|A|時，將這種軌跡稱為單觸發(fā)序列[6]。

現(xiàn)有的漂移檢測方法所分析的日志具有案例屬性，是多實例的、是同一個模型多次執(zhí)行產(chǎn)生的結(jié)果[7-12]。而現(xiàn)實生活中大多數(shù)軟件系統(tǒng)記錄的日志雖然也會有多次執(zhí)行，但用工具直接獲得的原始數(shù)據(jù)往往是一條沒有案例編號的單觸發(fā)序列形式的日志[13](如github上記錄軟件開發(fā)活動的日志)，做漂移檢測時不能得到輸出為案例編號的漂移點，需要先使用算法進行合理的劃分，得到具有案例屬性的多案例形式的事件日志，然后才能進行漂移檢測。單觸發(fā)序列是一條活動不斷增長的事件流，從軌跡的定義層面來說，這個事件流是只含有一條軌跡的事件流；原始的模型是未知的，能看到的只是活動與關(guān)系的變化。換句話說，在單觸發(fā)序列的日志中，只有一條案例數(shù)據(jù)，漂移檢測的最小單元必須是活動級別，而非案例級別。因此，直接尋找單觸發(fā)序列中活動漂移點的問題有待解決。由此，本文提出一種基于活動距離的突發(fā)漂移檢測算法。本文的創(chuàng)新點在于：

(1)對單觸發(fā)序列的突發(fā)漂移進行研究，解決現(xiàn)有漂移檢測算法不適用于單觸發(fā)序列日志形式的問題。

(2)提出一種通過兩次計算活動距離檢測漂移的算法，第一次使用杰卡德距離降維零一關(guān)系矩陣，第二次使用KL(Kullback-Leiber)散度判定距離分布的變化來定位漂移區(qū)間。

(3)最后，以循環(huán)關(guān)系的位置為窗口大小依次遍歷并合并漂移區(qū)間互求交集來定位活動漂移點的位置。

1 問題描述

如圖1所示，單觸發(fā)序列形成一條活動動態(tài)增長的事件流，而傳統(tǒng)的突發(fā)漂移檢測算法是基于活動靜態(tài)完整的軌跡集合。數(shù)據(jù)結(jié)構(gòu)的不同導(dǎo)致不能直接使用傳統(tǒng)的突發(fā)漂移檢測算法。本文假設(shè)活動的執(zhí)行是原子性的，并且是從數(shù)據(jù)屬性中抽象出來的。事件流形式的事件日志表示一個有限的或者無限的隨著時間而發(fā)生的事件序列[14]，它沒有案例屬性，在本文中被稱為單觸發(fā)序列。具有案例屬性的多案例形式的事件日志是在一組活動集合上的多組有限的事件序列，本文稱為多實例日志。

漂移的本質(zhì)就是隨著時間的推移模型發(fā)生演化的現(xiàn)象，單觸發(fā)序列與多實例日志的本質(zhì)區(qū)別是研究對象的最小單位不同，前者是活動或者事件，后者是軌跡。另一個區(qū)別是，數(shù)據(jù)的增長方式不同，前者是一條軌跡的長度增長，后者是多條軌跡的數(shù)量增長，而每條軌跡的長度不變。圖1左半部分展示了一條單觸發(fā)序列形式的事件流，隨著時間的推移模型在第i個活動處發(fā)生了演化；圖1的右半部分展示了多軌跡事件日志，隨著時間的推移模型在第j條軌跡處發(fā)生了演化，漂移點的位置就是軌跡編號。在圖1的左半部分，只有一條無限增長的軌跡和不斷增加的活動，它就是本文要研究的數(shù)據(jù)形式，其中，n是不斷增長的未知量；當(dāng)概念漂移發(fā)生時，需要在活動點之間檢測到漂移。在圖1的右半部分，是軌跡數(shù)量的不斷增長和同一活動集合未知數(shù)量的組合，且每條軌跡的長度有限，比如一個活動集合有m個活動，m個活動以未知數(shù)量(m以內(nèi)的數(shù)量)組合成多條長度有限、數(shù)量不斷增長的軌跡；當(dāng)概念漂移發(fā)生時，將在軌跡編號，即案例號，或者軌跡對應(yīng)的時間點處檢測到漂移。如果想使用現(xiàn)有的漂移檢測技術(shù)來解決單觸發(fā)序列的漂移問題，需要先對如圖1左半部分所示的單觸發(fā)序列進行合理劃分，使其成為如圖1右半部分所示的多實例事件日志的形式，才能輸入具有案例編號形式的數(shù)據(jù)，繼而使用現(xiàn)有的漂移檢測技術(shù)得到輸出為案例編號位置的漂移點。然而，圖1右半部分所采用的方法只能解決多實例日志的漂移檢測，本文重點研究如何直接在單觸發(fā)序列上滑動窗口去檢測引起過程模型變更的活動點的位置，即漂移點的位置，而不是先劃分單觸發(fā)序列為多軌跡形式的日志，再在軌跡上滑動窗口去檢測軌跡變化的位置。

2 相關(guān)工作

概念漂移最早出現(xiàn)在機器學(xué)習(xí)領(lǐng)域[15]，用于解決隨著時間的推移和數(shù)據(jù)量的增大，分類器不能很好地進行分類的問題。在過程挖掘領(lǐng)域，概念漂移還是一個比較新的研究方向，現(xiàn)有的過程突發(fā)漂移檢測算法的相關(guān)工作如下。

BOSE等[1]提出了在過程挖掘領(lǐng)域存在概念漂移的現(xiàn)象。他們分析了100多個組織的實際過程，結(jié)果表明：過程挖掘?qū)τ谀Ｐ头€(wěn)態(tài)不變的假設(shè)是不現(xiàn)實的，在過程實施中模型往往會發(fā)生變化，而這些在過程實施中模型的變化卻很少被直接記錄在日志中。為此，BOSE等[7]又提出一種通過提取特征和假設(shè)檢驗來檢測漂移的框架，這是目前主流的漂移檢測算法，但特征提取較為復(fù)雜。隨后，MARTJUSHEV等[8]在此基礎(chǔ)上提出了自適應(yīng)滑動窗口，解決了特征提取時一次只能移動一步窗口的問題。MAARADJI等[9]提出一種run特征和卡方檢驗的方法，其中，run的特點是利用并發(fā)關(guān)系壓縮日志，降低了提取復(fù)雜特征的難度；但是，缺點是并發(fā)關(guān)系很難快速確定。KUMAR等[10]使用事件類和假設(shè)檢驗的方法來檢測概念漂移，其缺點是在某些變化模式和某些長度的日志中得到的檢測效果不是很好。ZHENG等[11]使用活動關(guān)系矩陣和密度聚類算法(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)檢測日志中的漂移點。LIN等[12]使用直接后繼關(guān)系的局部完備性，以及新關(guān)系的增加和舊關(guān)系的消失再加上窗口的跳躍性遺忘機制來檢測漂移。二者的方法能快速準(zhǔn)確地檢測出漂移，并且只提取直接后繼關(guān)系，大大降低了特征提取的復(fù)雜度。但是，上述方法大多只適用于多實例的事件日志，對于缺少用于標(biāo)記過程挖掘的過程實例的案例編號的日志數(shù)據(jù)，則需要在預(yù)處理中進行分割[16]。本文提出一種基于活動距離的單觸發(fā)序列突發(fā)漂移檢測算法，該算法無需討論單觸發(fā)序列的合理劃分問題，可以直接對其進行漂移檢測。

3 預(yù)備知識

過程模型的表示形式很多，本文使用Petri網(wǎng)[17-18]來表示過程模型。下面給出Petri網(wǎng)的基本定義：

定義1Petri網(wǎng)[12]。一個四元組N=(P,T;F,M0)代表一個Petri網(wǎng)，其中：

(1)P∪T≠?且P∩T=?，一般將P稱為有窮庫所集，T視為有窮變遷集。

(2)F?(P×T)∪(T×P)，其中F表示流關(guān)系。

(3)dom(F)∪cod(F)=P∪T,且dom(F)={x∈P∪T|?y∈P∪T:(x,y)∈F},cod(F)={y∈P∪T|?x∈P∪T: (x,y)∈F}。

(4)M:P→{0,1,2,…}，習(xí)慣稱M為N的一個標(biāo)識，且用M0代表N的初始標(biāo)識。

本文基于單觸發(fā)序列形式的事件日志進行研究，下面給出與事件日志相關(guān)的定義：

定義2事件日志與軌跡[12]。假設(shè)T為所有任務(wù)集合，σ∈T*是一條事件軌跡，L?P(T*)是一個事件日志。

由定義2可知,事件日志是軌跡的集合，每條軌跡是由有限的任務(wù)T(也稱活動A)按照發(fā)生的先后次序排列而成。

定義3直接后繼關(guān)系，>[12]。假設(shè)T是任務(wù)集合，L?P(T*)代表事件日志。對于?a,b∈T,a>b，當(dāng)且僅當(dāng)：存在一條軌跡σ=t1t2t3…tn-1tn,而i∈{1,…,n-1}，其中滿足σ∈W且ti=a，ti+1=b。

由定義3可知直接后繼關(guān)系即為緊鄰關(guān)系。

定義4單觸發(fā)序列[6]。設(shè)事件日志為L，一個軌跡σ∈L被稱為單觸發(fā)序列，當(dāng)且僅當(dāng)L=[σ1]。

由定義4可知單觸發(fā)序列是只含有一條軌跡的事件日志，與文獻[14]提到的事件流定義形式不同，但含義相同。

定義5概念漂移[3]。設(shè)M0，M1，…，Mk，為k個不同模型，T0

本文研究的突發(fā)漂移是認(rèn)為，當(dāng)模型在Ti時刻從Mi演變成Mi+1時，假定這一演變是瞬時完成的，即從Ti時刻起所有記錄的軌跡均屬于Mi+1，直到再次發(fā)生演變?yōu)橹?。另外，需要指出的是，本文只考慮過程模型的控制流變化，不考慮數(shù)據(jù)、資源等因素。

4 單觸發(fā)序列突發(fā)漂移檢測方法

本章將討論如何通過兩次計算窗口間活動距離的差異來定位漂移點，本文算法檢測漂移點的原理是相鄰窗口間活動距離的概率分布差異越大，越容易發(fā)生漂移。依據(jù)文獻[3]和文獻[12]可以發(fā)現(xiàn)，漂移發(fā)生的本質(zhì)是關(guān)系，不是軌跡。對于單觸發(fā)序列形式的日志直接可以獲得的便是活動之間的關(guān)系，其中直接后繼關(guān)系最為重要。為此，本文基于直接后繼關(guān)系提出了單觸發(fā)序列突發(fā)漂移檢測框架。如圖2所示，圖2a是單觸發(fā)序列突發(fā)漂移檢測框架流程圖，圖2b是介紹如何設(shè)置滑動窗口的移動。圖2c是本文提出的SSDD算法原理圖的詳細(xì)介紹。

(1)提取直接后繼關(guān)系矩陣 從事件日志的一條軌跡中，要找到模型的變化，并且只有無限增長的活動數(shù)據(jù)，沒有其他形式的數(shù)據(jù)?；顒邮且粋€接一個排序的，且一組一組地反映過程模型。在這類數(shù)據(jù)中，相鄰活動之間的關(guān)系尤為重要。因此，要提取直接后繼關(guān)系矩陣，使活動數(shù)據(jù)轉(zhuǎn)化為數(shù)值數(shù)據(jù)來獲取活動的特征。

事件日志可以通過滑動窗口進行分析。當(dāng)滑動窗口時，因為最后一個活動的直接后繼關(guān)系在前一個窗口中不存在，所以選擇前一個窗口的尾活動作為下一個窗口的首活動，即一次挪動窗口大小減1步，既保證活動關(guān)系不丟失，又避免一次挪動一個活動的重復(fù)遍歷，如圖2b所示。用一個較小的事件日志作為例子，如事件日志L=[][11]。得到活動的直接后繼關(guān)系后將日志L轉(zhuǎn)換成活動的關(guān)系矩陣，如圖2c關(guān)系矩陣一列所示。在同一窗口內(nèi)，如果一個活動與另一個活動具有直接后繼關(guān)系記為1，否則記為0。

(2)計算活動的杰卡德距離 為了反映窗口之間活動關(guān)系的變化情況，并對關(guān)系矩陣做降維處理，選擇能夠反映集合相似性的杰卡德距離公式來計算相鄰兩個窗口之間同一活動直接后繼關(guān)系矩陣的距離。杰卡德距離公式來自于杰卡德系數(shù)[19]，它是用來度量兩個有限集A和B重疊的相對大小，杰卡德系數(shù)

(1)

與其相關(guān)的杰卡德距離

(2)

算法1展示了如何使用杰卡德距離公式計算相鄰窗口之間活動的直接后繼關(guān)系矩陣的距離分布的核心部分。在算法1中，輸入的是同一活動在相鄰兩個窗口上的直接后繼關(guān)系矩陣M[i]、M[j];輸出的是杰卡德距離矩陣。通過滑動窗口依次計算相鄰窗口之間同一活動之間的杰卡德距離，最后得到所有活動的杰卡德距離，即杰卡德距離分布矩陣，如圖2c第2列所示。算法1采用雙指針的計算方式實現(xiàn)杰卡德距離公式的計算，portion指針指向分子，total指針指向分母，不同則分子分母都加1；同為1，分母在原來不同的基礎(chǔ)上繼續(xù)加1；其他情況均不計算(如，同為0)。

算法1計算活動關(guān)系的杰卡德距離矩陣。

輸入：the relation vector M[i], M[j]of adjacent windows；

輸出：distance D。

1. begin

2. D←?, portion, total, d ←0, k ←0,n ←length of M[i]

3. for k ← 0 to n do

4. if M[i][k] ≠M[j][k] then

5. portion←portion+1

6. total←total+1

7. else if M[i][k]=1 and M[j][k]=1 then

8. total ← total + 1

9. if total=0 then

10. d←0

11. else d←portion/total

12. D←j5i0abt0b

13.end

算法2計算距離分布的KL散度值。

輸入：distance matrix D, minimum value eps；

輸出：the set of KL values KL。

1. begin

2. sample←?, sum1, sum2, d←0, n ←length of sample

3. sample← normalize(D)

4. m←length of sample[i]

5. for i←0 to n do

6. for j←0 to m do

7. if sample[i][j]=0 then

8. sample[i][j]← eps

9. for k←0 to n do

10. for l←0 to n do

11. sum1←asymmetricKL(sample[k],sample[l])

12. sum2←asymmetricKL(sample[l],sample[k])

13. d←(sum1+sum2)/2

14. KL← j5i0abt0b

15. end

(3)定位漂移區(qū)間 得到杰卡德距離分布矩陣后，可以觀測到距離分布的差異越大，相鄰兩個窗口的活動關(guān)系差異就越大，越容易發(fā)生漂移。因此，引入KL散度[20]來衡量距離分布的差異。首先標(biāo)記要比較的分布并對每一個分布進行歸一化處理，以適應(yīng)KL散度公式概率和為1的要求；其次，使用KL散度來計算分布中的差異；最后，用KL散度變化的極大值來定位漂移區(qū)間。

KL散度[20]也稱為相對熵，用來衡量兩個隨機分布之間的差異。如果分布相同，相對熵為0，如果兩個隨機分布之間的差異很大，相對熵也會增大。相對熵的定義是：假設(shè)在相同的事件空間中，兩個概率分布分別是P和Q，隨機分布P中第i個事件變量的概率可以表示為p(xi)，隨機分布Q中第i個事件的概率表示為q(xi)，則P和Q的相對熵D(P||Q)可以表示為：

(3)

相對熵有非負(fù)性和非對稱性兩個基本性質(zhì)。非負(fù)性表示D(P||Q)≥0，非對稱性表示D(P||Q)不一定等于D(Q||P)。因此，如果想測量兩個分布之間的距離，可以用平均值來轉(zhuǎn)換。這就是為什么KL散度不叫KL距離。設(shè)D(P,Q)為分布之間的距離，則

(4)

算法2展示了如何使用KL散度來計算相鄰標(biāo)簽之間的杰卡德距離矩陣的變化。如圖2c第3列和第4列所示，標(biāo)記了杰卡德距離矩陣，label0表示從窗口1到窗口2的杰卡德距離變化的分布，label1依次表示從窗口2到窗口3的杰卡德距離變化的分布。使用KL散度來計算label0和label1之間分布的差值，即計算隨著窗口的增加相鄰標(biāo)簽之間距離分布的變化。同時，算法的時間復(fù)雜度從O(n)變?yōu)镺(n2)。

在算法2中，由于距離的某些值為0，在對數(shù)的真數(shù)中，分子和分母又都不能為0。因此，當(dāng)距離值為0時，取一個盡可能接近0的最小值eps，但不是0(第5～第8行)，本文eps=1×10-8。首先將距離矩陣歸一化，使每個標(biāo)簽的概率分布之和為1(第3行)，然后計算相鄰標(biāo)簽兩兩之間的KL散度值，并取平均值(第9～第13行)。在得到KL散度值的集合后，極大值對應(yīng)的窗口值是所求漂移區(qū)間。如圖2c最后結(jié)果所示，KL0、KL1、KL2、KL3、KL4分別為{0.2,5.5,3.1,0.1,14.8}，極大值分別為5.5與14.8，對應(yīng)的漂移區(qū)間為活動16～活動21，活動31～活動32，窗口內(nèi)活動的數(shù)量小于窗口大小的一半，影響結(jié)果可以舍去，檢測到漂移的區(qū)間為[16,21]。

(4)定位漂移點 漂移區(qū)間的定位受窗口大小的影響較大。窗口粒度大，不容易檢測到漂移；窗口粒度小，容易檢測到不是因為漂移引起的變化，如循環(huán)與并發(fā)結(jié)構(gòu)引起的變化。因此，本文提出以循環(huán)關(guān)系的位置為窗口大小依次遍歷并求得漂移區(qū)間的交集來定位漂移點。依然是前面的例子，記錄第一次出現(xiàn)的循環(huán)關(guān)系的位置分別為d→a,a→c,c→b,b→d,a→b,b→c,c→d：9,10,11,12,14,15,16，以此為窗口大小依次遍歷算法求得漂移區(qū)間分別為：[17,25]，[28,32]，[21,31]，[23,32]，[23,32]，?，?，?，互求交集后得到漂移點為活動[23,25]和活動[28,31]。漂移點的位置為活動關(guān)系a→d(28-29)的增加，故求得結(jié)果有效。

5 實驗評估

5.1 評估數(shù)據(jù)

漂移檢測需要事先知道漂移點的位置，直接用真實的數(shù)據(jù)集來驗證漂移檢測的結(jié)果有一定的難度，這是因為構(gòu)造的數(shù)據(jù)集中真實漂移點的位置已知，而真實數(shù)據(jù)集中真實漂移點位置未知。因此，本文使用PIPE工具，參考文獻[21]繪制了一個軟件過程的Petri網(wǎng)模型。如圖3a所示，該模型圖包含了順序、選擇、并發(fā)、循環(huán)4種基本結(jié)構(gòu)，還包含了循環(huán)中嵌套并發(fā)、并發(fā)中嵌套二度循環(huán)等復(fù)雜結(jié)構(gòu)。在使用PIPE工具生成日志的過程中，根據(jù)文獻[9]提供的12種基本變化模式(分別為：CB, CD, CF, CM, CP, FR, LP, PL, PM, RE, RP, SW)，對該模型進行了12種變換，并記錄變換時漂移點的位置，其中：FR改變頻率這種變換PIPE工具做不到，因此本文增加了一種基本變化模式的混合模式ORI，總共也是12種變換模式。同時，考慮到日志數(shù)據(jù)長度對檢測結(jié)果的影響，還設(shè)置了5種不同的日志長度(800、2 400、4 000、6 400、8 000)，每條日志均含有7個漂移點。這些長度都是800的倍數(shù)，相當(dāng)于把日志都劃分成8份。最終，本文使用這12種變更模式(CB, CD, CF, CM, CP, ORI, LP, PL, PM, RE, RP, SW)來改變原始模型，并用PIPE工具生成合成日志。這樣就生成了包含12個變更模式和5種長度的60條單觸發(fā)序列。

圖3a是基準(zhǔn)模型，以此基準(zhǔn)模型本文進行了12種變換?！癛E”模式是刪除了“Review”活動；“CF”模式是使“By Virtual Machine”活動與“Porting”活動由原來的選擇變換為順序；“LP”模式使“Review”活動至“Integration”活動的并發(fā)塊結(jié)構(gòu)加入一個循環(huán)體變成可循環(huán)的；“PL”模式是使活動“Kernel Code Design”、活動“User Interface Design”和活動“Other Important Design”由原來的并發(fā)結(jié)構(gòu)變?yōu)轫樞蚪Y(jié)構(gòu)；“CB”模式是跳過了“Abstract”活動；“CM”模式是使“Abstract”活動與“Feedback”活動從順序結(jié)構(gòu)加入到選擇結(jié)構(gòu)；“CD”模式是使活動“Kernel Code Design”和活動“User Interface Design”同步發(fā)生；“CP”模式是重復(fù)了“Kernel Algorithm Test”活動；“PM”模式是使活動“User Interface Implementation”移出并發(fā)塊；“RP”模式是將活動“Review”替換為新活動“Document Design”；“SW”模式是將“Review”活動與“Validation”活動交換位置；“ORI”模式包含了類型O中的“CB”模式，類型R中的“PL”模式和類型I中的“SW”，先是跳過了“Abstract”活動，再將活動“Risk Analysis”和活動“Re-Design”由原來的順序結(jié)構(gòu)變?yōu)椴l(fā)結(jié)構(gòu)，最后是將“Review”活動與“Validation”活動交換了位置；PIPE中可用黑色方塊表示活動沒有意義且是瞬間執(zhí)行的，相當(dāng)于一條直線，用它來跳過‘CB’模式中的活動，其他模式同理。

同時，選取了文獻[22]和文獻[23]中的兩個數(shù)據(jù)集對本文的算法進行了驗證。分別是Eclipse的Team數(shù)據(jù)和JUnit 4.12的數(shù)據(jù)。Eclipse的Team數(shù)據(jù)包含多個Team數(shù)據(jù)，每個Team數(shù)據(jù)是一條單觸發(fā)序列，提取了數(shù)據(jù)的categroryName列和commandName列作為單觸發(fā)序列的活動。JUnit 4.12的數(shù)據(jù)本身就是一個單實例數(shù)據(jù)，提取了joinpoint和start結(jié)點的數(shù)據(jù)作為一條單觸發(fā)序列。

5.2 評估結(jié)果

為了評估本文算法的有效性，參考文獻[12]使用F-score對本文算法進行了評估。本文中：真正例(True Positive,TP)代表檢測到漂移點(t1,t2)，且存在一個真實的漂移點屬于[t1-r,t2+r]；假正例(False Positive,FP)代表檢測到漂移點(t1,t2)，但不存在一個真實的漂移點屬于[t1-r,t2+r]；假反例(False Negative,FN)代表存在一個真實的漂移點(t1,t2)，但在區(qū)間[t1-r,t2+r]檢測不到漂移點。其中：t代表活動的時間點，漂移點是活動關(guān)系所以是區(qū)間的形式；r代表滯后期[12]。由于篇幅原因，下面給出CB模式的檢測結(jié)果和r=100時CB模式的準(zhǔn)確率。如表1和表2所示。r=100時所有模式的F-score最終結(jié)果如圖4所示，不同的陰影代表不同模式的F-score，橫軸為日志長度。

表1 CB模式檢測結(jié)果

表2 r=100時CB模式的準(zhǔn)確率

由圖4可以看出，長度為800的所有模式的F-score值為1;長度為2 400時，CB、CD、LP、PL、RE模式的F-score值為1，CF、PM、ORI的F-score值最低為0.7，其余模式為0.8或0.9；其余日志長度依次類推。

同時，使用本文算法對兩個真實的軟件執(zhí)行的數(shù)據(jù)集Eclipse的Team數(shù)據(jù)和JUnit 4.12的數(shù)據(jù)進行了漂移檢測，結(jié)果可以檢測出漂移，并對應(yīng)到日志數(shù)據(jù)中分析漂移產(chǎn)生的原因，證明了算法的可行性。如圖5所示為JUnit 4.12數(shù)據(jù)的實驗結(jié)果，如圖6所示為Eclipse數(shù)據(jù)集中Team 21的實驗結(jié)果。以圖6為例對原始數(shù)據(jù)進行了分析。圖6提取活動時是以timestamp_end排序。由于真實數(shù)據(jù)集的漂移點是未知的，獲得漂移窗口位置后，返回到原數(shù)據(jù)中觀察了窗口3-4和窗口4-5的活動變化，發(fā)現(xiàn)窗口4與窗口3和窗口5比較，窗口4中提取的活動，即categroryName列和commandName列的值，變化較大，如圖7所示，以活動File：Save為例，在窗口3-4，其直接后繼活動發(fā)生了明顯的變化；在窗口4-5，F(xiàn)ile：Save活動在窗口4中頻繁出現(xiàn)，而在窗口5沒有出現(xiàn)，發(fā)生的變化為活動的消失。這些活動次序的變化在相鄰窗口之間不相似有可能就是檢測到的漂移產(chǎn)生的原因。在此例中，說明團隊的操作重心可能發(fā)生了變化，可以適當(dāng)反饋給管理者以作任務(wù)安排的調(diào)整。

6 結(jié)束語

現(xiàn)有的漂移檢測算法是基于有案例屬性的多實例日志數(shù)據(jù)，不適用于單觸發(fā)序列的漂移檢測的研究。因此，對于單觸發(fā)序列的漂移檢測需要提出一種新的方法以適用于以活動為研究對象，且活動不斷增長的事件流數(shù)據(jù)。本文提出一種基于活動距離的突發(fā)漂移檢測方法，力求解決單觸發(fā)序列形式的數(shù)據(jù)因缺乏案例屬性而無法直接使用現(xiàn)有漂移檢測算法的問題。首先將活動關(guān)系的變化轉(zhuǎn)換為距離分布的變化，然后通過KL散度計算距離分布變化的差異，最后定位漂移點。實驗結(jié)果表明，本文算法可以有效檢測出漂移點的位置。下一步將繼續(xù)深入研究優(yōu)化算法目前的時間復(fù)雜度O(n2)及其他漂移類型的問題。