一種自適應的并行化模糊挖掘算法

趙 洪 博

(復旦大學軟件學院 上海 200433)

0 引 言

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

1 相關研究簡介

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

綜合來看，這些研究都是對其他流程挖掘算法等進行優化，很少涉及模糊挖掘算法，而且它們在解決數據的過擬合問題、處理非結構化的流程模型方面沒有給出比較好的解決方案。基于這個研究現狀，本文將模糊挖掘算法的優化作為研究的主要方向，提出的APFM算法保留了模糊挖掘算法的優勢，并對傳統的模糊挖掘算法不足之處進行優化。

2 APFM算法

本文提出的APFM算法本質上也是一種模糊挖掘算法，其中的“模糊”是指根據流程日志數據挖掘大致的流程模型，并未將所有的活動一一還原出來，只是將重要活動表示出來，相連的非重要活動會被整合為一個抽象活動集合節點。該流程模型中不包含冗余的活動關系，整體的結構層次比較清晰，解決了數據過擬合問題。結合傳統模糊挖掘算法的不足，APFM算法從自動化參數配置、并行優化、建模優化三個方面對其進行改進。自動化參數配置是指APFM算法可以根據日志數據計算相關的參數，實現參數的自動化配置。并行優化是指APFM算法中將涉及大規模數據處理的過程進行并行化改進，確保在處理大規模數據集時也有比較好的表現。建模優化是指APFM算法將活動、活動關系處理過程分別進行優化，并添加了長距離依賴關系的處理方法，提高流程模型的精準程度。

圖1展示了本文提出的APFM算法的數據處理流程，該算法主要分為兩個部分，分別是自動化參數配置過程以及流程模型的處理過程。自動化參數配置階段需要配置包括活動重要程度參數以及活動關系重要程度參數。流程模型處理階段又分為三個部分，分別是活動關系處理、活動的抽象與聚合以及長距離依賴關系的處理。活動關系處理包括活動關系的過濾以及活動邏輯關系的識別，確保流程模型中不包含冗余的活動關系。活動的抽象與聚合就是將部分重要程度較低的活動抽象為一個活動集合，在流程模型中區別展現出來。前兩個數據處理階段完成得到的流程模型，并未標示出長距離依賴關系。為了解決這個問題，APFM算法在最后一步計算長距離依賴關系因子，挖掘流程模型中包含的長距離依賴關系。

圖1 APFM算法數據處理流程

3 參數的自動化配置

模糊挖掘的參數配置是指在算法的預處理階段對日志數據中涉及到的每個活動、活動關系配置對應的重要程度參數，后面的數據處理過程中以這些參數為基礎進行活動邏輯關系識別、活動關系過濾、活動節點的抽象與聚合。在很多實際場景中，活動重要程度以及活動關系重要程度的具體數值很難直接確定，手動設置比較困難。APFM算法中的自動化參數配置方法可以對日志數據進行分析，完成參數的自動化配置。

3.1 自動化參數配置方法的基本原理

在傳統的模糊挖掘算法中，頻率是衡量活動重要程度、活動關系重要程度的常用指標之一，在日志數據中出現頻率越高的活動，其重要程度越高。然而在很多實際場景中，有些活動在日志中出現的頻率不高，但其對流程模型的影響較大，如果直接將頻率作為衡量活動重要程度指標，得到的流程模型可能不夠完整、不夠精確。例如，在進行程序開發時，開發新功能的工作量比較大，而進行代碼評審、代碼提交等工作比較少。因此，在計算重要程度時，既要考慮活動的頻率，也要考慮活動對流程模型的影響程度。

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

(1)

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

(2)

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

(3)

(4)

3.2 自動化參數配置方法的實現

自動化參數配置方法的實現主要分為兩個部分，分別是活動重要程度的配置以及活動關系重要程度的配置。在配置活動重要程度時，首先根據日志數據獲取對應的活動軌跡數據，然后根據活動軌跡數據計算活動的頻率以及活動對流程模型的影響程度，最后按照式(2)將活動頻率與活動對流程模型的影響程度相結合計算得到活動重要程度參數，如算法1所示。

算法1活動重要程度配置算法

Input: TraceSet;

//根據流程日志數據得到的活動軌跡

Output: sig(A);

//活動重要程度

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展示了活動重要程度配置過程的偽代碼，輸入數據為根據日志數據得到的活動軌跡數據，輸出為數據中涉及到的每個活動對應的重要程度數值。算法的1-20行是一個mapreduce任務，該任務的map階段遍歷活動軌跡，統計每條活動軌跡中各個活動的出現次數，然后在reduce階段對每個活動分別進行處理，計算其頻率f(A)以及對流程模型影響程度函數g(A)。在算法的21-25行將數據進行整合處理，計算每個活動的重要程度。

活動關系重要程度的實現與其相似，也是通過一個mapreduce任務完成活動關系頻率的計算，然后按照式(4)計算每個活動關系的重要程度參數，具體過程此處不再贅述。

4 流程模型的構建

為了提高流程模型的精準程度，APFM算法在流程模型的構建方面進行了優化，首先從整體、局部兩方面綜合考慮完成活動關系的處理，然后通過一種自底向上的方法完成活動的抽象與聚合，最后通過計算長距離依賴因子挖掘流程模型中的長距離依賴關系。下面分別對這三個部分進行具體描述。

4.1 活動關系的處理

活動關系的處理包括活動關系的過濾以及活動邏輯關系的識別。活動關系的過濾是從宏觀角度對活動關系的重要程度進行分析，并結合活動相關度對活動關系進行過濾，去除重要程度較低的活動關系。活動邏輯關系的識別是從局部角度，對活動關系在局部范圍內的重要程度進行分析，以此為基礎識別活動之間的邏輯關系，該步驟中也對部分活動關系進行過濾。

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

(5)

定義util值[6]進行活動關系的過濾，util值的計算方式如式(6)所示，util值與活動重要程度、活動相關度有關，通過一個系數α調整活動重要程度與活動相關度的權重比例。在具體進行活動關系的過濾時，需要指定一個閾值rc，如果某條活動關系的util大于等于閾值rc，那么保留該條活動關系，否則直接過濾即可。

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

(6)

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

(7)

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

算法2活動關系處理算法

Input: OldRelationSet;

Output: RelationSet;

//流程模型的活動關系集合

L2Set;

//長度為2的循環結構集合

SDSet;

//直接依賴關系集合

PSet;

//并行關系集合

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 活動的抽象與聚合

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

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

算法3活動的抽象與聚合處理算法

Input: RelationSet;

//活動關系集合

OldActivitySet;

//根據日志數據得到的活動集合

Output: ActivitySet;

//活動集合

AbstractSet;

//抽象后得到的活動集合

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 長距離依賴關系的處理

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

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

(8)

算法4展示了挖掘長距離依賴關系的具體過程。算法的1-9行是一個mapreduce任務，該任務可以根據活動關系構建活動依賴關系網絡。根據活動依賴關系網絡可以非常輕松地找出每個活動的依賴關系，判斷其前一個狀態是否為活動選擇狀態。算法的10-16行完成長距離依賴關系的挖掘，對于每個活動，判斷與其他活動是否具有長距離依賴關系，如果是則將其加入LongRelationSet中。

算法4長距離依賴關系挖掘算法

Input: RelationSet;

//活動關系集合

ActivitySet;

//活動集合

Output: LongRelationSet;

//長距離依賴關系集合

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 實 驗

實驗分為自動化參數配置實驗、算法性能分析、算法運行結果分析三個部分，分別對APFM算法三個方面優化是否達到預期效果進行分析，從而對APFM算法進行比較全面的評估。實驗使用的數據為某高校網絡課程平臺的用戶學習日志數據，整個數據集包含大約8 498萬條數據，涉及37門網絡課程，數據中的每條記錄均包含用戶學號、用戶所選課程、所學的課程章節以及時間等信息。實驗過程中，需要根據課程編號提取某門課程相關的數據進行分析。

5.1 自動化參數配置實驗分析

為了評估APFM算法中自動化參數配置方法的有效性，實驗選擇活動重要程度、活動關系重要程度已知的數據集使用自動化參數配置方法進行處理，將自動化配置結果與已知的數據參數值進行對比，判斷它們的差值是否在合理范圍內。

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

表1 自動化參數方法結果對照表

5.2 APFM算法的性能分析

在進行性能分析實驗時，實驗環境為包含2個數據處理節點的hadoop集群，每臺機器的配置為CPU i5- 4460T，4核8線程，內存為8 GB，操作系統為ubuntu 18.04，64位操作系統。實驗選擇單機版的模糊挖掘算法、并行化的啟發式挖掘算法進行對照，構建了日志條數分別為103至106數據規模大小不同的數據集，對比不同算法在處理不同規模數據集時的運行時間。

圖2展示了不同算法運行時間的對比結果，其中縱坐標為時間(ms)，橫坐標為所使用的數據集的數據規模。與單機版的傳統模糊挖掘算法相比，當日志數據規模比較小時，APFM算法的運行時間較長，當數據規模較大時，APFM算法的運行效率漸漸高于單機版模糊挖掘算法，而且數據規模越大，APFM算法的優勢越明顯。盡管并行化的啟發式挖掘算法在處理不同規模數據集時表現都不錯，數據處理耗時均低于單機版的模糊挖掘算法，但當數據規模達到50萬甚至更大時，APFM算法數據處理效率更具優勢。由此可以得出結論，APFM算法具備較好的處理大規模數據集能力，表現優于單機版的模糊挖掘算法以及并行化的啟發式挖掘算法，符合預期的優化目的。

圖2 與單機版算法運行時間對比圖

為了更進一步分析APFM算法的運行性能，統計APFM算法在不同處理不同規模數據集時各個步驟運行時間，以便分析APFM算法的瓶頸。圖3展示了APFM算法運行過程中各個階段耗時的對比圖，橫坐標為所使用的數據集中數據規模，縱坐標為將運行時間取log的值。由于不同階段的運行時間差別較大，需要將運行時間取log后便于觀察。可以看出，APFM算法最耗時的部分為自動化參數配置，而其余三個建模過程耗時很少。這是由于自動化參數配置階段通過執行mapreduce任務完成整個數據集的處理，該過程復雜度較高，需要遍歷整個數據集完成參數配置，是一個比較耗時的過程。而其余三個數據處理過程復雜度不高，只與活動總數、活動關系總數相關，因此耗時很短。由此可以得出結論，APFM算法的瓶頸在于自動化參數配置階段對整個數據集處理，其他階段耗時很短。APFM算法數據處理方式的特點在于只需要在自動化參數配置階段，對整個數據集處理一次，完成數據集的簡化，后續過程中需要根據簡化后的數據進行處理即可得到流程模型。當數據集規模較小時，這種數據處理方法效率不高，但當數據集的規模較大時，這種數據處理方法的優勢就逐漸體現出來。

圖3 APFM算法不同階段運行時間

5.3 APFM算法的運行結果分析

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

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

圖4 流程模型示意圖

實驗選擇了傳統的模糊挖掘算法以及啟發式挖掘算法進行對照，將這兩個算法運行得到的流程模型與APFM算法得到的流程模型進行對比，具體的評估指標計算結果如表2所示，然后分別對每個指標進行分析：

(1) 可重現性：APFM算法得到的流程模型可重現性較傳統的模糊挖掘算法有一定的提升，但兩者均不如啟發式挖掘算法，這是由于它們在建模過程中對某些活動進行了抽象與聚合操作，導致流程模型并不能夠精確地還原活動軌跡中的每一個活動，只能還原部分重要程度較高的活動。

(2) 簡潔性：APFM算法繼承了模糊挖掘算法的優點，得到流程模型結構層次比較清晰，活動關系也比較簡潔，不存在冗余的活動關系，挖掘得到的長距離依賴關系也能夠比較清楚地展現出來。因此APFM算法得到的流程模型簡潔性非常好。

(3) 精確性：APFM算法得到的流程模型結構比較簡潔，未出現過擬合問題，其精確性比啟發式挖掘算法更好。APFM算法在建模過程中進行了優化，添加了長距離依賴關系的處理方法，確保得到的流程模型更加貼近日志數據中描述的行為，極少出現日志數據描述之外的行為。

(4) 通用性：APFM算法得到的流程模型通用性也是最好，也是得益于APFM算法保留了傳統模糊挖掘算法的優勢以及對建模方法的進一步優化，保證得到的流程模型更加符合日志數據描述的行為，對未來可能出現的執行實例能夠進行比較精確的預測。

表2 流程模型評價表

綜合來看，APFM算法得到的流程模型簡潔性非常好，精確性、通用性較傳統的模糊挖掘算法相比均有一定的提升。但受限于算法本身的建模思路，導致流程模型的可重現性一般。因此，在可重現性要求不是非常苛刻的條件下，使用APFM算法處理日志數據可以得到比較精確的流程模型。

6 結 語

模糊挖掘算法是流程挖掘中常用的算法之一，但該算法存在一些缺陷，本文通過對這些缺陷進行分析并進行改進，提出了一種自適應的并行化模糊挖掘算法。APFM算法可以進行參數的自動化配置，使用起來更加簡單；通過并行化方法完成數據處理，增強了處理大規模數據的能力；對建模過程進行優化，添加了長距離依賴關系的處理方法，使整個建模過程更加細致、全面，確保得到的流程模型更加精確。實驗證明，APFM算法對傳統模糊挖掘算法不足之處的優化均達到了預期的效果。

綜合目前流程挖掘算法優化方面的研究來看，模糊挖掘算法應用方面的研究較多，但算法優化方面的研究很少，本文對于模糊挖掘算法的優化是比較新的研究方向。盡管本文提出的APFM算法在一定程度上取得了不錯的結果，但還需要在更多其他的應用場景中對其進行實驗，嘗試挖掘其不足之處。在算法的優化方面，除了提高算法在大規模數據集的處理能力，還可以嘗試對算法的處理思路、實際應用場景的特點進行分析，提出更好地解決方案。