一種自適應(yīng)的并行化模糊挖掘算法

趙 洪 博

(復(fù)旦大學(xué)軟件學(xué)院 上海 200433)

0 引 言

流程挖掘是一門(mén)比較年輕的研究學(xué)科，其基本理念是從事件日志數(shù)據(jù)中提取有價(jià)值的流程信息，從而對(duì)實(shí)際模型進(jìn)行發(fā)現(xiàn)、監(jiān)控、改進(jìn)。流程挖掘的發(fā)展已經(jīng)非常成熟，出現(xiàn)了很多挖掘算法，如α算法[1]、啟發(fā)式挖掘算法[2]、歸納式挖掘算法[3]、ILP挖掘算法[4]、eST挖掘算法[5]等，這些算法通過(guò)對(duì)日志數(shù)據(jù)進(jìn)行分析，得到相關(guān)的流程模型并以petri net[6]、C-net[2]等形式展現(xiàn)出來(lái)。盡管這些流程挖掘算法在實(shí)驗(yàn)條件下取得了非常好的效果，但在實(shí)際場(chǎng)景中，由于日志數(shù)據(jù)比較復(fù)雜且包含一些噪聲數(shù)據(jù)，致使它們?cè)趯?shí)際條件下表現(xiàn)不佳，往往會(huì)出現(xiàn)過(guò)擬合現(xiàn)象，得到“意大利面式”的流程模型。模糊挖掘算法[7]可以比較好地解決數(shù)據(jù)過(guò)擬合問(wèn)題，在實(shí)際場(chǎng)景中有著非常廣泛的應(yīng)用。文獻(xiàn)[8]提出了將模糊挖掘算法應(yīng)用到惡意軟件的檢測(cè)中，文獻(xiàn)[9]提出了將模糊挖掘算法應(yīng)用到軟件開(kāi)發(fā)行為分析中。模糊挖掘算法也存在一些缺點(diǎn)，包括使用該算法時(shí)需要預(yù)先手動(dòng)配置參數(shù)，該過(guò)程比較繁瑣，在實(shí)際應(yīng)用場(chǎng)景中，尤其是陌生的環(huán)境下很難直接確定參數(shù)具體值；在數(shù)據(jù)處理階段，模糊挖掘算法需要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行處理，當(dāng)數(shù)據(jù)規(guī)模比較大時(shí)可能會(huì)影響算法的運(yùn)行效率；模糊挖掘算法的建模方法不夠細(xì)致，而且未能針對(duì)長(zhǎng)距離依賴關(guān)系給出具體的解決方案。針對(duì)以上提出的幾個(gè)問(wèn)題，本文對(duì)傳統(tǒng)的模糊挖掘算法進(jìn)行改進(jìn)，提出一種自適應(yīng)的并行化模糊挖掘算法(APFM)，該算法使用起來(lái)更加簡(jiǎn)單方便，具備處理大規(guī)模數(shù)據(jù)集的能力，而且得到的流程模型也更加精確。

1 相關(guān)研究簡(jiǎn)介

目前，流程挖掘的發(fā)展面臨著多方面的挑戰(zhàn)[10]，如何提高算法的運(yùn)行效率，增強(qiáng)算法進(jìn)行大規(guī)模數(shù)據(jù)處理的能力是熱門(mén)研究方向之一。在流程挖掘算法的優(yōu)化方面，文獻(xiàn)[11]提出了將mapreduce計(jì)算框架應(yīng)用到流程挖掘的數(shù)據(jù)處理中，基于數(shù)據(jù)的key值對(duì)數(shù)據(jù)進(jìn)行分塊、排序，完成數(shù)據(jù)的并行處理。文獻(xiàn)[12]給出了基于Hadoop完成流程挖掘任務(wù)的具體實(shí)現(xiàn)方法，并以歸納式挖掘算法為例進(jìn)行測(cè)試。文獻(xiàn)[13]是對(duì)文獻(xiàn)[11]提出的算法進(jìn)行改進(jìn)，提出了一種基于活動(dòng)關(guān)系的聚類方法將數(shù)據(jù)進(jìn)行分塊處理。文獻(xiàn)[14]是使用多線程技術(shù)對(duì)啟發(fā)式挖掘算法進(jìn)行優(yōu)化，提高了算法的運(yùn)行效率。文獻(xiàn)[15]也是對(duì)啟發(fā)式挖掘算法進(jìn)行優(yōu)化，該算法基于Amazon Cloud實(shí)現(xiàn)，數(shù)據(jù)處理能力更強(qiáng)，應(yīng)用場(chǎng)景更加廣泛。文獻(xiàn)[16-17]提出了將分治思想應(yīng)用到流程挖掘中，開(kāi)發(fā)了一種通用的數(shù)據(jù)處理方法(或算法框架)。文獻(xiàn)[18]針對(duì)大規(guī)模數(shù)據(jù)處理場(chǎng)景提出了一種可橫向拓展的流程發(fā)現(xiàn)計(jì)算框架，并給出了流程模型的一致性、完整性檢測(cè)方法。文獻(xiàn)[19]對(duì)eST挖掘算法的缺點(diǎn)進(jìn)行分析并改進(jìn)。

綜合來(lái)看，這些研究都是對(duì)其他流程挖掘算法等進(jìn)行優(yōu)化，很少涉及模糊挖掘算法，而且它們?cè)诮鉀Q數(shù)據(jù)的過(guò)擬合問(wèn)題、處理非結(jié)構(gòu)化的流程模型方面沒(méi)有給出比較好的解決方案?；谶@個(gè)研究現(xiàn)狀，本文將模糊挖掘算法的優(yōu)化作為研究的主要方向，提出的APFM算法保留了模糊挖掘算法的優(yōu)勢(shì)，并對(duì)傳統(tǒng)的模糊挖掘算法不足之處進(jìn)行優(yōu)化。

2 APFM算法

本文提出的APFM算法本質(zhì)上也是一種模糊挖掘算法，其中的“模糊”是指根據(jù)流程日志數(shù)據(jù)挖掘大致的流程模型，并未將所有的活動(dòng)一一還原出來(lái)，只是將重要活動(dòng)表示出來(lái)，相連的非重要活動(dòng)會(huì)被整合為一個(gè)抽象活動(dòng)集合節(jié)點(diǎn)。該流程模型中不包含冗余的活動(dòng)關(guān)系，整體的結(jié)構(gòu)層次比較清晰，解決了數(shù)據(jù)過(guò)擬合問(wèn)題。結(jié)合傳統(tǒng)模糊挖掘算法的不足，APFM算法從自動(dòng)化參數(shù)配置、并行優(yōu)化、建模優(yōu)化三個(gè)方面對(duì)其進(jìn)行改進(jìn)。自動(dòng)化參數(shù)配置是指APFM算法可以根據(jù)日志數(shù)據(jù)計(jì)算相關(guān)的參數(shù)，實(shí)現(xiàn)參數(shù)的自動(dòng)化配置。并行優(yōu)化是指APFM算法中將涉及大規(guī)模數(shù)據(jù)處理的過(guò)程進(jìn)行并行化改進(jìn)，確保在處理大規(guī)模數(shù)據(jù)集時(shí)也有比較好的表現(xiàn)。建模優(yōu)化是指APFM算法將活動(dòng)、活動(dòng)關(guān)系處理過(guò)程分別進(jìn)行優(yōu)化，并添加了長(zhǎng)距離依賴關(guān)系的處理方法，提高流程模型的精準(zhǔn)程度。

圖1展示了本文提出的APFM算法的數(shù)據(jù)處理流程，該算法主要分為兩個(gè)部分，分別是自動(dòng)化參數(shù)配置過(guò)程以及流程模型的處理過(guò)程。自動(dòng)化參數(shù)配置階段需要配置包括活動(dòng)重要程度參數(shù)以及活動(dòng)關(guān)系重要程度參數(shù)。流程模型處理階段又分為三個(gè)部分，分別是活動(dòng)關(guān)系處理、活動(dòng)的抽象與聚合以及長(zhǎng)距離依賴關(guān)系的處理。活動(dòng)關(guān)系處理包括活動(dòng)關(guān)系的過(guò)濾以及活動(dòng)邏輯關(guān)系的識(shí)別，確保流程模型中不包含冗余的活動(dòng)關(guān)系?；顒?dòng)的抽象與聚合就是將部分重要程度較低的活動(dòng)抽象為一個(gè)活動(dòng)集合，在流程模型中區(qū)別展現(xiàn)出來(lái)。前兩個(gè)數(shù)據(jù)處理階段完成得到的流程模型，并未標(biāo)示出長(zhǎng)距離依賴關(guān)系。為了解決這個(gè)問(wèn)題，APFM算法在最后一步計(jì)算長(zhǎng)距離依賴關(guān)系因子，挖掘流程模型中包含的長(zhǎng)距離依賴關(guān)系。

圖1 APFM算法數(shù)據(jù)處理流程

3 參數(shù)的自動(dòng)化配置

模糊挖掘的參數(shù)配置是指在算法的預(yù)處理階段對(duì)日志數(shù)據(jù)中涉及到的每個(gè)活動(dòng)、活動(dòng)關(guān)系配置對(duì)應(yīng)的重要程度參數(shù)，后面的數(shù)據(jù)處理過(guò)程中以這些參數(shù)為基礎(chǔ)進(jìn)行活動(dòng)邏輯關(guān)系識(shí)別、活動(dòng)關(guān)系過(guò)濾、活動(dòng)節(jié)點(diǎn)的抽象與聚合。在很多實(shí)際場(chǎng)景中，活動(dòng)重要程度以及活動(dòng)關(guān)系重要程度的具體數(shù)值很難直接確定，手動(dòng)設(shè)置比較困難。APFM算法中的自動(dòng)化參數(shù)配置方法可以對(duì)日志數(shù)據(jù)進(jìn)行分析，完成參數(shù)的自動(dòng)化配置。

3.1 自動(dòng)化參數(shù)配置方法的基本原理

在傳統(tǒng)的模糊挖掘算法中，頻率是衡量活動(dòng)重要程度、活動(dòng)關(guān)系重要程度的常用指標(biāo)之一，在日志數(shù)據(jù)中出現(xiàn)頻率越高的活動(dòng)，其重要程度越高。然而在很多實(shí)際場(chǎng)景中，有些活動(dòng)在日志中出現(xiàn)的頻率不高，但其對(duì)流程模型的影響較大，如果直接將頻率作為衡量活動(dòng)重要程度指標(biāo)，得到的流程模型可能不夠完整、不夠精確。例如，在進(jìn)行程序開(kāi)發(fā)時(shí)，開(kāi)發(fā)新功能的工作量比較大，而進(jìn)行代碼評(píng)審、代碼提交等工作比較少。因此，在計(jì)算重要程度時(shí)，既要考慮活動(dòng)的頻率，也要考慮活動(dòng)對(duì)流程模型的影響程度。

定義g(A)衡量活動(dòng)A對(duì)于整個(gè)流程模型的影響程度，計(jì)算方式如式(1)所示?；顒?dòng)對(duì)流程模型的影響程度與活動(dòng)軌跡密切相關(guān)，如果某個(gè)活動(dòng)在大多數(shù)活動(dòng)軌跡中均有出現(xiàn)，那么該活動(dòng)對(duì)流程模型具有比較大的影響。在式(1)中，TraceSet表示整個(gè)活動(dòng)軌跡集合，t表示某條活動(dòng)軌跡。統(tǒng)計(jì)活動(dòng)A在哪些活動(dòng)軌跡中出現(xiàn)過(guò)，并與活動(dòng)軌跡總數(shù)相比即可得到活動(dòng)影響因子的具體數(shù)值。例如，計(jì)算某個(gè)活動(dòng)對(duì)流程模型的影響程度數(shù)值為0.98，很接近于1，表明該活動(dòng)在大部分活動(dòng)軌跡中均有出現(xiàn)，對(duì)流程模型具有較大的影響，執(zhí)行流程模型的過(guò)程中很大概率會(huì)遇到該活動(dòng)。

(1)

與活動(dòng)重要程度相關(guān)的另一個(gè)因素就是活動(dòng)的頻率。將活動(dòng)對(duì)流程模型的影響程度與活動(dòng)的頻率相結(jié)合進(jìn)行計(jì)算即可得到活動(dòng)對(duì)流程模型的重要程度，具體計(jì)算方法如式(2)所示。在日志數(shù)據(jù)中，較大的活動(dòng)頻率可能比較小的活動(dòng)頻率大很多倍，直接將活動(dòng)的頻率與影響因子相乘作為重要程度可能不夠準(zhǔn)確。為解決這個(gè)問(wèn)題，這里對(duì)頻率值取log處理，使數(shù)據(jù)有區(qū)分度且差別又不那么大，然后再做歸一化處理，將其轉(zhuǎn)化為[0,1]內(nèi)的數(shù)值。例如，給定兩個(gè)重要程度比較接近的活動(dòng)A、B，且f(A)=1 000f(B)，此時(shí)使用log函數(shù)對(duì)其進(jìn)行處理可以非常好地將巨大的數(shù)量級(jí)差距縮小為倍數(shù)級(jí)，降低頻率倍數(shù)差別過(guò)大的影響。

(2)

活動(dòng)關(guān)系重要程度的計(jì)算方式與活動(dòng)重要程度類似，也是需要計(jì)算活動(dòng)關(guān)系的頻率及其對(duì)流程模型的影響程度，具體計(jì)算方式如式(3)-式(4)所示?；顒?dòng)關(guān)系對(duì)流程模型的影響程度用g(A,B)進(jìn)行表示，與兩端活動(dòng)的重要程度相關(guān)。在大多數(shù)條件下，兩端活動(dòng)的重要程度對(duì)活動(dòng)關(guān)系的重要程度同等重要，因此直接計(jì)算它們的平均值即可?；顒?dòng)關(guān)系的頻率f(A,B)也是參照活動(dòng)處理方式進(jìn)行歸一化處理，然后與活動(dòng)關(guān)系對(duì)流程模型的影響程度g(A,B)相乘即可得到活動(dòng)重要程度sig(A,B)。

(3)

(4)

3.2 自動(dòng)化參數(shù)配置方法的實(shí)現(xiàn)

自動(dòng)化參數(shù)配置方法的實(shí)現(xiàn)主要分為兩個(gè)部分，分別是活動(dòng)重要程度的配置以及活動(dòng)關(guān)系重要程度的配置。在配置活動(dòng)重要程度時(shí)，首先根據(jù)日志數(shù)據(jù)獲取對(duì)應(yīng)的活動(dòng)軌跡數(shù)據(jù)，然后根據(jù)活動(dòng)軌跡數(shù)據(jù)計(jì)算活動(dòng)的頻率以及活動(dòng)對(duì)流程模型的影響程度，最后按照式(2)將活動(dòng)頻率與活動(dòng)對(duì)流程模型的影響程度相結(jié)合計(jì)算得到活動(dòng)重要程度參數(shù)，如算法1所示。

算法1活動(dòng)重要程度配置算法

Input: TraceSet;

//根據(jù)流程日志數(shù)據(jù)得到的活動(dòng)軌跡

Output: sig(A);

//活動(dòng)重要程度

Method:

1 Procedure map(TraceSet)

2 foreach trace in TraceSet do

3 total+=|trace|

4 foreach A in trace do

5 counts(A)+=1

6 gs(A)=1

7 foreach A in ActivitySet do

8 count(A)+=counts(A)

9 g(A)+=gs(A)

10 foreach A in Activity do

11 Output(A, count(A), g(A), total)

12 Procedure reduce(key, CountIterator, GIterator, totalIterator)

13 foreach countItem in CountIterator

14 count(A)+=countItem

15 foreach gItem in GIterator

16 g(A)+=gItem

17 foreach totalItem in totalIterator

18 total+=totalItem

19 f(A)=count(A)/total

20 output(f(A), g(A))

21 max=0;

22 foreach A in ActivitySet

23 if f(A)>max then max=f(A)

24 foreach A in ActivitySet

25 sig(A)=logf(A)/logmax*g(A)

算法1展示了活動(dòng)重要程度配置過(guò)程的偽代碼，輸入數(shù)據(jù)為根據(jù)日志數(shù)據(jù)得到的活動(dòng)軌跡數(shù)據(jù)，輸出為數(shù)據(jù)中涉及到的每個(gè)活動(dòng)對(duì)應(yīng)的重要程度數(shù)值。算法的1-20行是一個(gè)mapreduce任務(wù)，該任務(wù)的map階段遍歷活動(dòng)軌跡，統(tǒng)計(jì)每條活動(dòng)軌跡中各個(gè)活動(dòng)的出現(xiàn)次數(shù)，然后在reduce階段對(duì)每個(gè)活動(dòng)分別進(jìn)行處理，計(jì)算其頻率f(A)以及對(duì)流程模型影響程度函數(shù)g(A)。在算法的21-25行將數(shù)據(jù)進(jìn)行整合處理，計(jì)算每個(gè)活動(dòng)的重要程度。

活動(dòng)關(guān)系重要程度的實(shí)現(xiàn)與其相似，也是通過(guò)一個(gè)mapreduce任務(wù)完成活動(dòng)關(guān)系頻率的計(jì)算，然后按照式(4)計(jì)算每個(gè)活動(dòng)關(guān)系的重要程度參數(shù)，具體過(guò)程此處不再贅述。

4 流程模型的構(gòu)建

為了提高流程模型的精準(zhǔn)程度，APFM算法在流程模型的構(gòu)建方面進(jìn)行了優(yōu)化，首先從整體、局部?jī)煞矫婢C合考慮完成活動(dòng)關(guān)系的處理，然后通過(guò)一種自底向上的方法完成活動(dòng)的抽象與聚合，最后通過(guò)計(jì)算長(zhǎng)距離依賴因子挖掘流程模型中的長(zhǎng)距離依賴關(guān)系。下面分別對(duì)這三個(gè)部分進(jìn)行具體描述。

4.1 活動(dòng)關(guān)系的處理

活動(dòng)關(guān)系的處理包括活動(dòng)關(guān)系的過(guò)濾以及活動(dòng)邏輯關(guān)系的識(shí)別。活動(dòng)關(guān)系的過(guò)濾是從宏觀角度對(duì)活動(dòng)關(guān)系的重要程度進(jìn)行分析，并結(jié)合活動(dòng)相關(guān)度對(duì)活動(dòng)關(guān)系進(jìn)行過(guò)濾，去除重要程度較低的活動(dòng)關(guān)系。活動(dòng)邏輯關(guān)系的識(shí)別是從局部角度，對(duì)活動(dòng)關(guān)系在局部范圍內(nèi)的重要程度進(jìn)行分析，以此為基礎(chǔ)識(shí)別活動(dòng)之間的邏輯關(guān)系，該步驟中也對(duì)部分活動(dòng)關(guān)系進(jìn)行過(guò)濾。

定義活動(dòng)相關(guān)度cor用以描述表示在流程模型中兩個(gè)活動(dòng)之間的關(guān)系是否緊密，具體的計(jì)算方式如式(5)所示。給定活動(dòng)A、B，如果在日志數(shù)據(jù)中，兩個(gè)活動(dòng)經(jīng)常一前一后同時(shí)出現(xiàn)，且活動(dòng)關(guān)系(A，B)在活動(dòng)A、活動(dòng)B各自的關(guān)系中占有比較大的比重，那么可以認(rèn)為兩個(gè)活動(dòng)之間的相關(guān)度較高；反之則認(rèn)為兩個(gè)活動(dòng)的相關(guān)度較低，相關(guān)的數(shù)據(jù)可能為噪聲數(shù)據(jù)。

(5)

定義util值[6]進(jìn)行活動(dòng)關(guān)系的過(guò)濾，util值的計(jì)算方式如式(6)所示，util值與活動(dòng)重要程度、活動(dòng)相關(guān)度有關(guān)，通過(guò)一個(gè)系數(shù)α調(diào)整活動(dòng)重要程度與活動(dòng)相關(guān)度的權(quán)重比例。在具體進(jìn)行活動(dòng)關(guān)系的過(guò)濾時(shí)，需要指定一個(gè)閾值rc，如果某條活動(dòng)關(guān)系的util大于等于閾值rc，那么保留該條活動(dòng)關(guān)系，否則直接過(guò)濾即可。

util(A,B)=α×sig(A,B)+(1-α)×cor(A,B)

(6)

定義活動(dòng)關(guān)系的相對(duì)重要程度rel[6]，用來(lái)表述該活動(dòng)關(guān)系在局部范圍內(nèi)的重要程度，以此為基礎(chǔ)進(jìn)行活動(dòng)邏輯關(guān)系的識(shí)別，其具體計(jì)算方式如式(7)所示。給定活動(dòng)A、B識(shí)別其邏輯關(guān)系，如果rel(A,B)和rel(B,A)都超過(guò)預(yù)設(shè)的循環(huán)因子lf，那么兩個(gè)活動(dòng)可能形成了一個(gè)長(zhǎng)度為2的環(huán)；否則，如果rel(A，B)和rel(B,A)差值大于預(yù)設(shè)的并行因子cf，那么說(shuō)明其中一個(gè)比較重要，另一個(gè)可能為噪聲數(shù)據(jù)產(chǎn)生，保留rel值較大的關(guān)系，將rel值較小的關(guān)系去除。如果rel(A,B)或rel(B,A)有一個(gè)低于lf，且兩者差值小于cf，說(shuō)明兩個(gè)活動(dòng)可能為并行關(guān)系，活動(dòng)之間并不存在依賴關(guān)系。

(7)

算法2展示了活動(dòng)關(guān)系處理過(guò)程的偽代碼，輸入數(shù)據(jù)為OldRelationSet，表示直接根據(jù)活動(dòng)軌跡得到的、未經(jīng)過(guò)處理的活動(dòng)關(guān)系集合，輸出為流程模型的活動(dòng)關(guān)系集合RelationSet，包括循環(huán)結(jié)構(gòu)關(guān)系、直接依賴關(guān)系以及并行關(guān)系。算法的4-8行進(jìn)行活動(dòng)關(guān)系的過(guò)濾，將保留下來(lái)的活動(dòng)關(guān)系保存在NewRelationSet中。算法的9-15行進(jìn)行活動(dòng)邏輯關(guān)系的識(shí)別，遍歷NewRelationSet中的每個(gè)活動(dòng)關(guān)系，計(jì)算其相對(duì)重要程度進(jìn)而識(shí)別兩個(gè)活動(dòng)的邏輯關(guān)系，分別保存在L2Set、SDSet以及PSet中。最后將這三個(gè)集合進(jìn)行整合得到流程模型的活動(dòng)關(guān)系集合。

算法2活動(dòng)關(guān)系處理算法

Input: OldRelationSet;

Output: RelationSet;

//流程模型的活動(dòng)關(guān)系集合

L2Set;

//長(zhǎng)度為2的循環(huán)結(jié)構(gòu)集合

SDSet;

//直接依賴關(guān)系集合

PSet;

//并行關(guān)系集合

Method:

1 Calc(SumCountInSet, SumCountOutSet);

2 Calc(SumSigInSet, SumSigOutSet);

3 Init(NewRelaionSet);

4 for (A,B) in RelationSet do

5 Calc(cor(A,B))

6 Calc(util(A,B))

7 If (util(A,B)>rc) then

8 NewRelationSet=NewRelationSet∪(A,B)

9 for (A,B) in NewRelationSet do

10 Calc(rel(A,B), rel(B,A));

11 if (rel(A,B)>lf && rel(A,B)>lf) then

12 L2Set=L2Set∪(A,B)

13 else if (abs(rel(A,B)-rel(B,A))>cf) then

14 SDSet=SDset∪(A,B)

15 else PSet=PSet∪(A,B)

16 RelationSet=L2Set∪SDSet∪PSet

4.2 活動(dòng)的抽象與聚合

APFM算法通過(guò)一種自底向上的方法完成活動(dòng)的抽象與聚合，該方法的處理思想借鑒了自底向上層次聚類算法的處理思想，首先根據(jù)預(yù)先設(shè)置閾值ac完成活動(dòng)的篩選。然后遍歷每個(gè)需要處理的活動(dòng)進(jìn)行抽象處理，判斷該活動(dòng)是否能夠與其他活動(dòng)進(jìn)行聚合操作。最終流程模型的活動(dòng)集合分為兩個(gè)部分，一部分為重要程度較高、不需要進(jìn)行處理的活動(dòng)，另一部分則是完成抽象與聚合操作后得到的抽象活動(dòng)集合。

活動(dòng)抽象與聚合處理的具體過(guò)程通過(guò)算法3描述的偽代碼進(jìn)行詳細(xì)描述，該步驟的輸入數(shù)據(jù)為活動(dòng)關(guān)系集合以及直接根據(jù)日志數(shù)據(jù)得到的活動(dòng)集合，輸出數(shù)據(jù)為流程模型的活動(dòng)集合。算法的3-6行完成活動(dòng)的篩選，將重要程度較低的活動(dòng)識(shí)別出來(lái)并加入tempActivitySet中，重要程度較高的活動(dòng)直接加入ActivitySet中。算法的7-8行是為tempActivitySet中的每個(gè)活動(dòng)計(jì)算其關(guān)系編碼?；顒?dòng)的關(guān)系編碼是判斷兩個(gè)活動(dòng)是否能夠進(jìn)行聚合操作的依據(jù)，由活動(dòng)是否與其他重要程度相連的二進(jìn)制字符串來(lái)表示，如果兩個(gè)活動(dòng)的關(guān)系編碼相同，那么說(shuō)明它們同時(shí)與某個(gè)重要程度較高的活動(dòng)相連，不能進(jìn)行聚合操作。使用活動(dòng)的關(guān)系編碼進(jìn)行判斷處理，可以降低算法的復(fù)雜度，提高數(shù)據(jù)處理效率。算法的9-18行是活動(dòng)抽象與聚合的核心部分，通過(guò)一個(gè)循環(huán)完成。每次從tempActivitySet中取出一個(gè)抽象活動(dòng)A，遍歷與其相連的其他抽象活動(dòng)B，根據(jù)活動(dòng)關(guān)系編碼判斷B是否能夠與A進(jìn)行聚合操作。如果可以，這將抽象活動(dòng)B加入抽象活動(dòng)A對(duì)應(yīng)的抽象活動(dòng)集合中，更新抽象活動(dòng)A的活動(dòng)關(guān)系編碼以及關(guān)聯(lián)關(guān)系，并將抽象活動(dòng)B從tempActivitySet中移除，表示已完成對(duì)抽象活動(dòng)B的處理，當(dāng)抽象活動(dòng)A的聚合操作完成之后，將其加入AbstractSet中。當(dāng)tempActivitySet中的所有抽象活動(dòng)都被處理完成之后，再將AbstractSet加入ActivitySet中，得到流程模型的活動(dòng)集合。

算法3活動(dòng)的抽象與聚合處理算法

Input: RelationSet;

//活動(dòng)關(guān)系集合

OldActivitySet;

//根據(jù)日志數(shù)據(jù)得到的活動(dòng)集合

Output: ActivitySet;

//活動(dòng)集合

AbstractSet;

//抽象后得到的活動(dòng)集合

Method:

1 Init(tempActivitySet);

2 Init(MarkList);

3 foreach A in OldActivitySet do

4 if (sig(A)

5 tempActivitySet=tempActivitySet∪A;

6 else ActivitySet=ActivitySet∪A;

7 foreach A in tempActivitySet do

8 Calc(MarkList(A));

9 while (!tempActivitySet.empty()) do

10 A=tempActivitySet.get();

11 Mark=MarkList(A);

12 SubRelationSet=A.relation;

13 foreach B in SubRelationSet do

14 if (Mark.hasSameBit(MarkList(B))) then

15 tempActivitySet.remove(B);

16 update(Mark,B);

17 update(SubRelationSet,B);

18 AbstractSet=AbstractSet∪A;

19 ActivitySet=ActivitySet∪AbstractSet;

4.3 長(zhǎng)距離依賴關(guān)系的處理

長(zhǎng)距離依賴關(guān)系是指給定流程模型，存在活動(dòng)A、活動(dòng)B與活動(dòng)C、活動(dòng)D，活動(dòng)C的執(zhí)行依賴于活動(dòng)A的執(zhí)行，活動(dòng)D的執(zhí)行依賴于活動(dòng)B的執(zhí)行。傳統(tǒng)的模糊挖掘算法在建模過(guò)程中并未針對(duì)長(zhǎng)距離依賴關(guān)系給出合理的解決方案，本文提出的APFM算法對(duì)活動(dòng)軌跡進(jìn)行分析，通過(guò)計(jì)算長(zhǎng)距離依賴因子挖掘流程模型中的長(zhǎng)距離依賴關(guān)系。

長(zhǎng)距離依賴因子的具體計(jì)算方式如式(8)所示。為了便于描述，定義活動(dòng)的選擇狀態(tài)，該狀態(tài)是指在流程模型中，在執(zhí)行活動(dòng)之前有一個(gè)中間狀態(tài)，如果后續(xù)可以執(zhí)行的活動(dòng)不唯一，可以任意選擇，那么當(dāng)前的中間狀態(tài)就是活動(dòng)選擇狀態(tài)。給定活動(dòng)A、B，如果兩個(gè)活動(dòng)具有長(zhǎng)距離依賴關(guān)系的話，那么它們的前一個(gè)狀態(tài)一定都是活動(dòng)選擇狀態(tài)，而且在選擇執(zhí)行后續(xù)的活動(dòng)時(shí)，分別選擇執(zhí)行活動(dòng)A和活動(dòng)B，由此可以定義長(zhǎng)距離依賴因子，用來(lái)描述兩個(gè)活動(dòng)是否具有長(zhǎng)距離依賴關(guān)系。給定兩個(gè)活動(dòng)A、B，S1、S2分別是它們對(duì)應(yīng)的活動(dòng)選擇狀態(tài)，如果S1選擇執(zhí)行活動(dòng)A，S2選擇執(zhí)行活動(dòng)B的情況在所有情況中所占比例較高，大于預(yù)設(shè)的閾值lc，則可以判定兩個(gè)活動(dòng)具有長(zhǎng)距離依賴關(guān)系。

(8)

算法4展示了挖掘長(zhǎng)距離依賴關(guān)系的具體過(guò)程。算法的1-9行是一個(gè)mapreduce任務(wù)，該任務(wù)可以根據(jù)活動(dòng)關(guān)系構(gòu)建活動(dòng)依賴關(guān)系網(wǎng)絡(luò)。根據(jù)活動(dòng)依賴關(guān)系網(wǎng)絡(luò)可以非常輕松地找出每個(gè)活動(dòng)的依賴關(guān)系，判斷其前一個(gè)狀態(tài)是否為活動(dòng)選擇狀態(tài)。算法的10-16行完成長(zhǎng)距離依賴關(guān)系的挖掘，對(duì)于每個(gè)活動(dòng)，判斷與其他活動(dòng)是否具有長(zhǎng)距離依賴關(guān)系，如果是則將其加入LongRelationSet中。

算法4長(zhǎng)距離依賴關(guān)系挖掘算法

Input: RelationSet;

//活動(dòng)關(guān)系集合

ActivitySet;

//活動(dòng)集合

Output: LongRelationSet;

//長(zhǎng)距離依賴關(guān)系集合

Method:

1 Procedure map(RelationSet)

2 foreach (A,B) in RelationSet do

3 Output(A, in, B);

4 Output(B, out, A);

5 Procedure reduce(key, mode, value)

6 if (mode==in) then

7 succMap.Count(value).add(1);

8 else preMap.Count(value).add(1);

9 output(key, preMap, succMap);

10 foreach A in ActivitySet do:

11 if (A.getPreState()!=SelectionState) then

12 continue;

13 foreach B in ActivitySet do:

14 if (A.getPreState()!=SelectionState) then

15 continue;

16 Calc(ldr(A,B));

17 if (ldr(A,B)>lf) then

18 update(LongRelationSet,(A,B));

5 實(shí) 驗(yàn)

實(shí)驗(yàn)分為自動(dòng)化參數(shù)配置實(shí)驗(yàn)、算法性能分析、算法運(yùn)行結(jié)果分析三個(gè)部分，分別對(duì)APFM算法三個(gè)方面優(yōu)化是否達(dá)到預(yù)期效果進(jìn)行分析，從而對(duì)APFM算法進(jìn)行比較全面的評(píng)估。實(shí)驗(yàn)使用的數(shù)據(jù)為某高校網(wǎng)絡(luò)課程平臺(tái)的用戶學(xué)習(xí)日志數(shù)據(jù)，整個(gè)數(shù)據(jù)集包含大約8 498萬(wàn)條數(shù)據(jù)，涉及37門(mén)網(wǎng)絡(luò)課程，數(shù)據(jù)中的每條記錄均包含用戶學(xué)號(hào)、用戶所選課程、所學(xué)的課程章節(jié)以及時(shí)間等信息。實(shí)驗(yàn)過(guò)程中，需要根據(jù)課程編號(hào)提取某門(mén)課程相關(guān)的數(shù)據(jù)進(jìn)行分析。

5.1 自動(dòng)化參數(shù)配置實(shí)驗(yàn)分析

為了評(píng)估APFM算法中自動(dòng)化參數(shù)配置方法的有效性，實(shí)驗(yàn)選擇活動(dòng)重要程度、活動(dòng)關(guān)系重要程度已知的數(shù)據(jù)集使用自動(dòng)化參數(shù)配置方法進(jìn)行處理，將自動(dòng)化配置結(jié)果與已知的數(shù)據(jù)參數(shù)值進(jìn)行對(duì)比，判斷它們的差值是否在合理范圍內(nèi)。

表1展示了使用APFM算法中自動(dòng)化參數(shù)配置得到的參數(shù)值以及數(shù)據(jù)原有參數(shù)值對(duì)比的部分結(jié)果。表1選取5個(gè)活動(dòng)以及5對(duì)活動(dòng)關(guān)系，對(duì)比自動(dòng)化配置結(jié)果以及已知的參數(shù)值可以看出，對(duì)于任意一對(duì)數(shù)據(jù)，兩者的差值均不大于0.05，處于合理誤差范圍之內(nèi)。對(duì)于表1中未展示的、數(shù)據(jù)集中包含的數(shù)據(jù)，數(shù)據(jù)差值也在合理范圍內(nèi)，由此證明自動(dòng)化參數(shù)配置方法可以非常好地完成參數(shù)配置的任務(wù)。

表1 自動(dòng)化參數(shù)方法結(jié)果對(duì)照表

5.2 APFM算法的性能分析

在進(jìn)行性能分析實(shí)驗(yàn)時(shí)，實(shí)驗(yàn)環(huán)境為包含2個(gè)數(shù)據(jù)處理節(jié)點(diǎn)的hadoop集群，每臺(tái)機(jī)器的配置為CPU i5- 4460T，4核8線程，內(nèi)存為8 GB，操作系統(tǒng)為ubuntu 18.04，64位操作系統(tǒng)。實(shí)驗(yàn)選擇單機(jī)版的模糊挖掘算法、并行化的啟發(fā)式挖掘算法進(jìn)行對(duì)照，構(gòu)建了日志條數(shù)分別為103至106數(shù)據(jù)規(guī)模大小不同的數(shù)據(jù)集，對(duì)比不同算法在處理不同規(guī)模數(shù)據(jù)集時(shí)的運(yùn)行時(shí)間。

圖2展示了不同算法運(yùn)行時(shí)間的對(duì)比結(jié)果，其中縱坐標(biāo)為時(shí)間(ms)，橫坐標(biāo)為所使用的數(shù)據(jù)集的數(shù)據(jù)規(guī)模。與單機(jī)版的傳統(tǒng)模糊挖掘算法相比，當(dāng)日志數(shù)據(jù)規(guī)模比較小時(shí)，APFM算法的運(yùn)行時(shí)間較長(zhǎng)，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，APFM算法的運(yùn)行效率漸漸高于單機(jī)版模糊挖掘算法，而且數(shù)據(jù)規(guī)模越大，APFM算法的優(yōu)勢(shì)越明顯。盡管并行化的啟發(fā)式挖掘算法在處理不同規(guī)模數(shù)據(jù)集時(shí)表現(xiàn)都不錯(cuò)，數(shù)據(jù)處理耗時(shí)均低于單機(jī)版的模糊挖掘算法，但當(dāng)數(shù)據(jù)規(guī)模達(dá)到50萬(wàn)甚至更大時(shí)，APFM算法數(shù)據(jù)處理效率更具優(yōu)勢(shì)。由此可以得出結(jié)論，APFM算法具備較好的處理大規(guī)模數(shù)據(jù)集能力，表現(xiàn)優(yōu)于單機(jī)版的模糊挖掘算法以及并行化的啟發(fā)式挖掘算法，符合預(yù)期的優(yōu)化目的。

圖2 與單機(jī)版算法運(yùn)行時(shí)間對(duì)比圖

為了更進(jìn)一步分析APFM算法的運(yùn)行性能，統(tǒng)計(jì)APFM算法在不同處理不同規(guī)模數(shù)據(jù)集時(shí)各個(gè)步驟運(yùn)行時(shí)間，以便分析APFM算法的瓶頸。圖3展示了APFM算法運(yùn)行過(guò)程中各個(gè)階段耗時(shí)的對(duì)比圖，橫坐標(biāo)為所使用的數(shù)據(jù)集中數(shù)據(jù)規(guī)模，縱坐標(biāo)為將運(yùn)行時(shí)間取log的值。由于不同階段的運(yùn)行時(shí)間差別較大，需要將運(yùn)行時(shí)間取log后便于觀察?？梢钥闯?，APFM算法最耗時(shí)的部分為自動(dòng)化參數(shù)配置，而其余三個(gè)建模過(guò)程耗時(shí)很少。這是由于自動(dòng)化參數(shù)配置階段通過(guò)執(zhí)行mapreduce任務(wù)完成整個(gè)數(shù)據(jù)集的處理，該過(guò)程復(fù)雜度較高，需要遍歷整個(gè)數(shù)據(jù)集完成參數(shù)配置，是一個(gè)比較耗時(shí)的過(guò)程。而其余三個(gè)數(shù)據(jù)處理過(guò)程復(fù)雜度不高，只與活動(dòng)總數(shù)、活動(dòng)關(guān)系總數(shù)相關(guān)，因此耗時(shí)很短。由此可以得出結(jié)論，APFM算法的瓶頸在于自動(dòng)化參數(shù)配置階段對(duì)整個(gè)數(shù)據(jù)集處理，其他階段耗時(shí)很短。APFM算法數(shù)據(jù)處理方式的特點(diǎn)在于只需要在自動(dòng)化參數(shù)配置階段，對(duì)整個(gè)數(shù)據(jù)集處理一次，完成數(shù)據(jù)集的簡(jiǎn)化，后續(xù)過(guò)程中需要根據(jù)簡(jiǎn)化后的數(shù)據(jù)進(jìn)行處理即可得到流程模型。當(dāng)數(shù)據(jù)集規(guī)模較小時(shí)，這種數(shù)據(jù)處理方法效率不高，但當(dāng)數(shù)據(jù)集的規(guī)模較大時(shí)，這種數(shù)據(jù)處理方法的優(yōu)勢(shì)就逐漸體現(xiàn)出來(lái)。

圖3 APFM算法不同階段運(yùn)行時(shí)間

5.3 APFM算法的運(yùn)行結(jié)果分析

為了驗(yàn)證APFM算法的有效性，對(duì)APFM算法的運(yùn)行結(jié)果進(jìn)行比較客觀、全面的分析，實(shí)驗(yàn)選擇兩組數(shù)據(jù)分別使用APFM算法進(jìn)行建模分析。第一組實(shí)驗(yàn)數(shù)據(jù)為用戶參與網(wǎng)絡(luò)課程《辦公自動(dòng)化》的學(xué)習(xí)行為日志數(shù)據(jù)，該數(shù)據(jù)集包含275 153條日志記錄，處理后得到了17 343條活動(dòng)軌跡。第二組實(shí)驗(yàn)數(shù)據(jù)為用戶參與網(wǎng)絡(luò)課程《公關(guān)與社交禮儀》的學(xué)習(xí)行為日志數(shù)據(jù)，該數(shù)據(jù)集包含267 682條日志記錄，處理后得到了9 730條活動(dòng)軌跡。使用APFM算法進(jìn)行處理時(shí)，將閾值rc、ac、lc均設(shè)置為0.8。

圖4展示了使用APFM算法得到的流程模型的可視化結(jié)果，其中，長(zhǎng)方形節(jié)點(diǎn)表示日志中包含的活動(dòng)，六邊形節(jié)點(diǎn)表示對(duì)部分重要程度較低的活動(dòng)進(jìn)行聚合與抽象后得到的抽象活動(dòng)集合節(jié)點(diǎn)。為了便于表示，每個(gè)活動(dòng)節(jié)點(diǎn)、抽象活動(dòng)集合節(jié)點(diǎn)都用字母表示。實(shí)線箭頭表示簡(jiǎn)單的依賴關(guān)系，虛線箭頭表示長(zhǎng)距離依賴關(guān)系。整體來(lái)看，這兩個(gè)流程模型結(jié)構(gòu)清晰，不包含冗余的活動(dòng)關(guān)系，準(zhǔn)確地挖掘出了長(zhǎng)距離依賴關(guān)系之后，整個(gè)流程模型也顯得更加完整。為了對(duì)以上流程模型進(jìn)行更加透徹的評(píng)估分析，根據(jù)文獻(xiàn)[20]提出的流程模型的評(píng)價(jià)指標(biāo)，分別計(jì)算它們的可重現(xiàn)性、簡(jiǎn)潔性、精確性以及通用性4個(gè)指標(biāo)并進(jìn)行分析。

圖4 流程模型示意圖

實(shí)驗(yàn)選擇了傳統(tǒng)的模糊挖掘算法以及啟發(fā)式挖掘算法進(jìn)行對(duì)照，將這兩個(gè)算法運(yùn)行得到的流程模型與APFM算法得到的流程模型進(jìn)行對(duì)比，具體的評(píng)估指標(biāo)計(jì)算結(jié)果如表2所示，然后分別對(duì)每個(gè)指標(biāo)進(jìn)行分析：

(1) 可重現(xiàn)性：APFM算法得到的流程模型可重現(xiàn)性較傳統(tǒng)的模糊挖掘算法有一定的提升，但兩者均不如啟發(fā)式挖掘算法，這是由于它們?cè)诮＿^(guò)程中對(duì)某些活動(dòng)進(jìn)行了抽象與聚合操作，導(dǎo)致流程模型并不能夠精確地還原活動(dòng)軌跡中的每一個(gè)活動(dòng)，只能還原部分重要程度較高的活動(dòng)。

(2) 簡(jiǎn)潔性：APFM算法繼承了模糊挖掘算法的優(yōu)點(diǎn)，得到流程模型結(jié)構(gòu)層次比較清晰，活動(dòng)關(guān)系也比較簡(jiǎn)潔，不存在冗余的活動(dòng)關(guān)系，挖掘得到的長(zhǎng)距離依賴關(guān)系也能夠比較清楚地展現(xiàn)出來(lái)。因此APFM算法得到的流程模型簡(jiǎn)潔性非常好。

(3) 精確性：APFM算法得到的流程模型結(jié)構(gòu)比較簡(jiǎn)潔，未出現(xiàn)過(guò)擬合問(wèn)題，其精確性比啟發(fā)式挖掘算法更好。APFM算法在建模過(guò)程中進(jìn)行了優(yōu)化，添加了長(zhǎng)距離依賴關(guān)系的處理方法，確保得到的流程模型更加貼近日志數(shù)據(jù)中描述的行為，極少出現(xiàn)日志數(shù)據(jù)描述之外的行為。

(4) 通用性：APFM算法得到的流程模型通用性也是最好，也是得益于APFM算法保留了傳統(tǒng)模糊挖掘算法的優(yōu)勢(shì)以及對(duì)建模方法的進(jìn)一步優(yōu)化，保證得到的流程模型更加符合日志數(shù)據(jù)描述的行為，對(duì)未來(lái)可能出現(xiàn)的執(zhí)行實(shí)例能夠進(jìn)行比較精確的預(yù)測(cè)。

表2 流程模型評(píng)價(jià)表

綜合來(lái)看，APFM算法得到的流程模型簡(jiǎn)潔性非常好，精確性、通用性較傳統(tǒng)的模糊挖掘算法相比均有一定的提升。但受限于算法本身的建模思路，導(dǎo)致流程模型的可重現(xiàn)性一般。因此，在可重現(xiàn)性要求不是非?？量痰臈l件下，使用APFM算法處理日志數(shù)據(jù)可以得到比較精確的流程模型。

6 結(jié) 語(yǔ)

模糊挖掘算法是流程挖掘中常用的算法之一，但該算法存在一些缺陷，本文通過(guò)對(duì)這些缺陷進(jìn)行分析并進(jìn)行改進(jìn)，提出了一種自適應(yīng)的并行化模糊挖掘算法。APFM算法可以進(jìn)行參數(shù)的自動(dòng)化配置，使用起來(lái)更加簡(jiǎn)單；通過(guò)并行化方法完成數(shù)據(jù)處理，增強(qiáng)了處理大規(guī)模數(shù)據(jù)的能力；對(duì)建模過(guò)程進(jìn)行優(yōu)化，添加了長(zhǎng)距離依賴關(guān)系的處理方法，使整個(gè)建模過(guò)程更加細(xì)致、全面，確保得到的流程模型更加精確。實(shí)驗(yàn)證明，APFM算法對(duì)傳統(tǒng)模糊挖掘算法不足之處的優(yōu)化均達(dá)到了預(yù)期的效果。

綜合目前流程挖掘算法優(yōu)化方面的研究來(lái)看，模糊挖掘算法應(yīng)用方面的研究較多，但算法優(yōu)化方面的研究很少，本文對(duì)于模糊挖掘算法的優(yōu)化是比較新的研究方向。盡管本文提出的APFM算法在一定程度上取得了不錯(cuò)的結(jié)果，但還需要在更多其他的應(yīng)用場(chǎng)景中對(duì)其進(jìn)行實(shí)驗(yàn)，嘗試挖掘其不足之處。在算法的優(yōu)化方面，除了提高算法在大規(guī)模數(shù)據(jù)集的處理能力，還可以嘗試對(duì)算法的處理思路、實(shí)際應(yīng)用場(chǎng)景的特點(diǎn)進(jìn)行分析，提出更好地解決方案。