湯雅惠，李 彤，朱 銳，南峰濤，付會林

(1.云南大學(xué) 信息學(xué)院，云南 昆明 650500；2.云南大學(xué) 軟件學(xué)院，云南 昆明 650091；3.云南農(nóng)業(yè)大學(xué) 大數(shù)據(jù)學(xué)院，云南 昆明 650201)

0 引言

過程挖掘能從現(xiàn)代信息系統(tǒng)中提取有價(jià)值的過程知識，起到對過程進(jìn)行發(fā)現(xiàn)和監(jiān)督，最終達(dá)到過程改進(jìn)的作用。過程挖掘是管理復(fù)雜運(yùn)作過程的一種有效的工具，其目標(biāo)是能夠快速生成一個(gè)高簡潔度、高擬合度、高精確度以及高泛化度的過程模型，最終指導(dǎo)過程的分析和改進(jìn)[1]。

現(xiàn)今，過程挖掘方法仍處于不斷發(fā)展和革新中。應(yīng)用于控制流維度的挖掘算法[1]也非常多，不同算法的適用范圍各不相同，故而其對應(yīng)的優(yōu)點(diǎn)和缺點(diǎn)也不同。例如遺傳挖掘(Genetic Process Mining, GPM)算法[2]將4個(gè)質(zhì)量維度作為模型挖掘?qū)?，使其得到的模型較其他算法質(zhì)量更高。但由于GPM算法使用迭代的方法模仿生物自然演變，當(dāng)處理數(shù)據(jù)量較為龐大和結(jié)構(gòu)復(fù)雜的事件日志時(shí)，種群的準(zhǔn)備時(shí)間和算法的迭代時(shí)間將成倍增長，進(jìn)而大大降低算法的效率。

事件日志還包含與過程相關(guān)的人員組織的大量信息，這些信息同樣蘊(yùn)含價(jià)值。組織維度[3]的關(guān)注點(diǎn)在于組織中人與人之間的關(guān)系。對組織維度進(jìn)行挖掘可以發(fā)現(xiàn)典型的組織結(jié)構(gòu)和社交網(wǎng)絡(luò)(social net)[4]。社交網(wǎng)絡(luò)模型可以學(xué)習(xí)關(guān)于人、組織結(jié)構(gòu)(角色和部門)和工作分配的知識。組織知識的發(fā)現(xiàn)使管理人員能夠了解組織結(jié)構(gòu)，進(jìn)而改善組織運(yùn)作過程。例如，社交網(wǎng)絡(luò)可以顯示企業(yè)中的溝通結(jié)構(gòu)，這可用于設(shè)計(jì)通信基礎(chǔ)結(jié)構(gòu)或辦公室布局。

對于業(yè)務(wù)過程而言，過程的發(fā)生與變化，源自于人，而過程模型的發(fā)現(xiàn)與改進(jìn)，最終還是服務(wù)于人。因此，與組織維度相關(guān)的人的行為與交互，對于業(yè)務(wù)過程的影響舉足輕重。同時(shí)，現(xiàn)代工業(yè)產(chǎn)品是人類腦力和體力結(jié)合的產(chǎn)物。隨著企業(yè)規(guī)模的增長和產(chǎn)品開發(fā)技術(shù)的進(jìn)步，企業(yè)的分工和組織也變得越來越復(fù)雜。有效地組織和劃分人員的方法是使企業(yè)價(jià)值最大化的決定性因素。因此，發(fā)現(xiàn)和分析過程中涉及的組織維度信息至關(guān)重要。而與在控制流方面的研究相比，目前在組織維度方面的研究還比較少[5-6]。

控制流維度模型反映活動之間的關(guān)系，組織維度模型反映組織人員之間的關(guān)系。兩個(gè)維度屬于不同層面。而在人類扮演主要角色的環(huán)境中，過程的運(yùn)行與人類行為高度相關(guān)，人的行為與決策對活動的影響至關(guān)重要。例如，在軟件開發(fā)組織、醫(yī)院等許多其他專業(yè)組織中，過程的出現(xiàn)和變化多是由于人為決策。因此，將兩種維度分割來看，較難獲得全局視角，不能直觀看出人員在不同活動上的分工，難以對事件日志進(jìn)行全面的分析。而如果能夠在同一個(gè)模型中同時(shí)展示兩種維度，反映人與活動之間的關(guān)系，則能獲得更為全面的視角。目前，關(guān)于組合兩種維度的研究較為罕見，文獻(xiàn)[4]將日志中的事件與其所對應(yīng)的模型中的元素連接起來，通過仿真工具基于該映射將多個(gè)維度合并。然而，在一個(gè)事件日志和模型之間建立一個(gè)好的連接較為困難。本文將兩種維度組合，以執(zhí)行者過程樹的形式，在同一個(gè)模型中同時(shí)反映兩個(gè)維度的信息，能有效體現(xiàn)出活動與執(zhí)行者之間的關(guān)系。以此提供一種新的洞察力，有助于更準(zhǔn)確地對過程進(jìn)行分析。具體地，本文在控制流維度方面，針對遺傳挖掘算法的不足進(jìn)行改進(jìn)，目的是生成高質(zhì)量的控制流模型；然后使用組織維度擴(kuò)展模型，度量活動在執(zhí)行者層面的距離，并為控制流模型添加執(zhí)行者信息。

本文的主要貢獻(xiàn)如下：

(1)在控制流維度，提出遺傳過程混成挖掘算法。在預(yù)處理階段，使用歸納挖掘算法(Inductive Miner, IM)[7]處理事件日志，以為遺傳過程挖掘算法提供質(zhì)量較高的初始過程樹種群，從而簡化它的挖掘環(huán)境、提高算法效率。同時(shí)，定義綜合質(zhì)量函數(shù)，使算法有效平衡4個(gè)質(zhì)量維度。

(2)在組織維度，基于活動—執(zhí)行者矩陣，提出活動相似度度量方法，能有效度量活動在執(zhí)行者層面的相似度，進(jìn)而獲得組織結(jié)構(gòu)(角色和部門)和工作分配的信息。

(3)使用組織維度擴(kuò)展控制流模型，基于執(zhí)行者過程樹，建立雙維度過程模型。

1 國內(nèi)外研究現(xiàn)狀及發(fā)展趨勢分析

控制流發(fā)現(xiàn)算法旨在發(fā)現(xiàn)活動之間的控制流關(guān)系。目前，已經(jīng)提出許多發(fā)現(xiàn)算法[1]，它們各有各的適用范圍以及優(yōu)缺點(diǎn)。但是這些方法很難在算法效率以及模型的4個(gè)質(zhì)量維度(包括精確度(Precision)、簡潔度(Simplicity)、泛化度(Generalization)以及擬合度(Fitness))方面取得平衡。目前，相關(guān)研究表明，α算法[8]生成的過程模型不能確保簡潔性，且其不能處理短循環(huán)結(jié)構(gòu)，不能考慮發(fā)生次數(shù)。啟發(fā)式挖掘[9]將低頻事件視為噪聲，故其生成的模型的擬合度相對較差[10]?；趨^(qū)域的挖掘算法[11]可以處理具有復(fù)雜結(jié)構(gòu)的事件日志，且能生成具有較高精確度的過程模型，但可能導(dǎo)致空間爆炸，同時(shí)算法效率不高。

遺傳挖掘算法源于遺傳算法，由DE MEDEIROS等[2]提出。最初使用因果矩陣對算法內(nèi)部的模型進(jìn)行表示，但該方法將導(dǎo)致模型存在死鎖。為解決該問題，AALST等[12]提出并使用過程樹作為遺傳挖掘算法內(nèi)部過程模型的表示形式，雖然可以解決死鎖問題，但在處理大型事件日志時(shí)依然存在問題——算法的效率和挖掘所得模型的質(zhì)量難以達(dá)到較好的平衡，即如要挖掘生成較高質(zhì)量的過程模型，必須以大量的時(shí)間做支撐。而本文所提方法通過預(yù)挖掘，可以有效提高遺傳挖掘算法初始種群質(zhì)量，減少算法挖掘生成更高質(zhì)量模型所需要的迭代次數(shù)，最終加快其收斂速度。

組織挖掘的起點(diǎn)始于事件日志中存在的資源屬性，即該活動是由哪位執(zhí)行者完成的。SONG等[4]對組織挖掘方法進(jìn)行了詳盡的描述。對組織維度的挖掘分析方法主要分為3種：①組織維度模型(主要是社交網(wǎng)絡(luò))挖掘；②社交網(wǎng)絡(luò)分析；③組織實(shí)體之間的信息流分析。組織模型挖掘可以對具有相似特征的執(zhí)行者進(jìn)行分組，相似特征判斷既可以基于活動相似性，也可以基于案例相似性；社交網(wǎng)絡(luò)分析的主要目的是探索活動如何在不同的執(zhí)行者之間處理和傳遞，它展示了執(zhí)行者之間的關(guān)系，由代表執(zhí)行者的實(shí)體和代表關(guān)系的弧組成，弧帶有權(quán)重，權(quán)重代表執(zhí)行者之間的距離，距離則通過計(jì)算兩個(gè)執(zhí)行者在相同案例上工作的次數(shù)來度量[4]；組織實(shí)體之間的信息流分析，主要指對社交網(wǎng)絡(luò)中收集的信息進(jìn)行匯總，以產(chǎn)生組織實(shí)體(例如角色或組織單位)，這些實(shí)體可提供更高抽象級別的見解。組織實(shí)體的構(gòu)建考慮了度量標(biāo)準(zhǔn)以及派生的社交網(wǎng)絡(luò)和聚合節(jié)點(diǎn)，可以根據(jù)原始網(wǎng)絡(luò)的權(quán)重對這些新連接進(jìn)行加權(quán)。目前組織維度挖掘主要基于對社交網(wǎng)絡(luò)的分析，而本文通過活動—執(zhí)行者矩陣在執(zhí)行者層面上度量活動之間的距離，活動越近，則該活動的執(zhí)行者越相似，從而反映該事件日志的組織結(jié)構(gòu)特征。

2 控制流與組織維的雙維度遺傳過程挖掘方法

本文提出的雙維度遺傳過程挖掘方法(double-dimenSional genetic process mining method based on excutor process tree, BdSm)如圖1所示。將事件日志作為方法的輸入，得到的雙維度過程模型作為方法的結(jié)果輸出。BdSm方法由兩個(gè)維度構(gòu)成：①控制流維度，使用IM算法分別對案例進(jìn)行挖掘，并將其得到的過程模型作為GPM算法的初始種群，進(jìn)一步通過GPM算法對其進(jìn)行整合優(yōu)化，最終得到與日志相對應(yīng)的過程模型；②組織維度,提取組織信息，用于拓展過程模型。具體的，一方面通過活動—執(zhí)行者矩陣度量活動在執(zhí)行者層面的距離，另一方面將活動與其對應(yīng)的執(zhí)行者建立映射，得到執(zhí)行者過程樹。目前該方法已在過程挖掘工具ProM[13]中進(jìn)行實(shí)現(xiàn)。下面將分別對方法進(jìn)行說明，首先介紹相關(guān)定義。

定義1事件，事件屬性[8]。令ε為所有可能事件標(biāo)識符的集合，即事件空間，事件具有多個(gè)事件屬性，如：事件的執(zhí)行者的名稱、執(zhí)行事件所需成本以及事件的時(shí)間戳等。其中：

(1)屬性名集合為N；

(2)對于?e∈ε及屬性名稱n∈N，將事件e的屬性n所對應(yīng)的值記為#n(e)；

(3)若n屬性不屬于事件e，則#n(e)=⊥。

為方便起見，定義以下標(biāo)準(zhǔn)屬性：

#activity(e)為事件e相關(guān)聯(lián)的活動，將某個(gè)事件上的活動集合簡記為A；

#resource(e)為事件e相關(guān)聯(lián)的執(zhí)行者，將某個(gè)事件上的執(zhí)行者集合簡記為R；

對于事件e=(a,r)，設(shè)a∈A，r∈R，定義πa(e)=a，以及πr(e)=r。(a,r)表示活動a由執(zhí)行者r執(zhí)行。

定義2案例，軌跡，事件日志[8]。令C為所有可能的案例標(biāo)識符的集合，即案例空間，案例也具有多個(gè)案例屬性。

(1)對于?c∈C和屬性名稱n∈N，#n(c)為屬于案例c的屬性n對應(yīng)的值。

(2)若n的屬性不屬于案例c，則#n(c)=⊥。

(3)強(qiáng)制屬性——軌跡，是每個(gè)案例所必須具有的：即#trace(c)∈C*，將軌跡簡稱記為=trace(c)。

(4)對于?σ∈ε*，軌跡是每個(gè)事件只出現(xiàn)一次的一個(gè)有限序列，即對于?1≤i≤j≤|σ|，都有σi≠σj

(5)一組案例L?C集合構(gòu)成了事件日志，其中，對于?c1，c2，L有c1≠c2：?set(1)∩?set(2)=?, 即每個(gè)事件在整個(gè)日志中要么不出現(xiàn)，要么只出現(xiàn)一次。

2.1 控制流維度挖掘

在控制流維度，針對遺傳過程挖掘算法的不足，提出遺傳過程混成挖掘算法。算法的關(guān)鍵在于優(yōu)質(zhì)初始種群準(zhǔn)備、內(nèi)部模型的表示方法、綜合質(zhì)量函數(shù)的設(shè)定以及遺傳算子。下面分別說明。

2.1.1 優(yōu)質(zhì)初始種群準(zhǔn)備

由于初始過程模型的質(zhì)量越高，則達(dá)到高質(zhì)量模型所需的改變就越少，針對遺傳挖掘算法挖掘效率不高的問題，擬對事件日志進(jìn)行預(yù)挖掘，將預(yù)挖掘生成的過程模型替代原來隨機(jī)生成的模型，從而提升GPM算法的初始種群質(zhì)量。采用IM算法，對于每一個(gè)案例，挖掘出所對應(yīng)的子過程模型。采用該算法的原因是：一方面，IM算法可以得到擬合度80%以上的高質(zhì)量過程模型，且其算法時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間復(fù)雜度，而原有的GPM算法的初始種群是隨機(jī)生成的，其模型擬合度只有60%；另一方面，IM算法的過程發(fā)現(xiàn)架構(gòu)[7]能夠保證挖掘得到的所有模型都具有合理性(sound)[14]，即所得模型無死鎖及其他異常。由于GPM的算法特性，即每迭代一次，就需要對過程模型種群中所有過程模型進(jìn)行質(zhì)量評估和結(jié)構(gòu)改進(jìn)。如果過程模型不具備合理性，在評估改進(jìn)之前就需額外進(jìn)行模型修復(fù)，耗時(shí)耗力。因而，IM算法對初始種群預(yù)挖掘和優(yōu)化可以提高GPM算法效率[15]。

2.1.2 遺傳過程挖掘算法

(1)內(nèi)部模型的表示方式

由文獻(xiàn)[14]可知，Petri網(wǎng)包含了日志中的隱式庫所，且對其定義遺傳算子較為困難，故使用Petri網(wǎng)作為GPM算法執(zhí)行內(nèi)部模型表示法時(shí)，可能存在問題。而存在死鎖是使用因果矩陣作為內(nèi)部模型表示法具有的問題，因此，使用過程樹作為GPM內(nèi)部模型的表示方法，其主要優(yōu)點(diǎn)是該模型是基于塊結(jié)構(gòu)的，可以確保模型的合理性[16]。GPM算法需要對過程模型種群中所有過程模型作質(zhì)量評估和結(jié)構(gòu)改進(jìn)。由于過程樹所具有的合理性和健全性，GPM就不必對不完整的過程模型進(jìn)行檢測及修復(fù)。

定義3過程樹[17]。過程樹是一個(gè)三元組PT=(O,L,B)，其中:O是非葉子節(jié)點(diǎn)，即代表運(yùn)算符的節(jié)點(diǎn)的有限集合;L則是葉子節(jié)點(diǎn)，即代表活動的節(jié)點(diǎn)的有限集合，使得O∩L=?;B?(O×L)∪(O×O)是有向弧的集合。過程樹為一個(gè)有向連接圖，該連接圖不含圓，其第一層節(jié)點(diǎn)為(樹)根節(jié)點(diǎn)，下面各層節(jié)點(diǎn)都為對應(yīng)的上一層節(jié)點(diǎn)的子節(jié)點(diǎn)(孩子節(jié)點(diǎn))。過程的控制流結(jié)構(gòu)采用運(yùn)算法節(jié)點(diǎn)表示。其結(jié)構(gòu)包括：排它選擇×、非排它選擇+、順序結(jié)構(gòu)→、并行結(jié)構(gòu)∧以及循環(huán)結(jié)構(gòu)等。

(2)綜合質(zhì)量函數(shù)——CQ函數(shù)

本文使用以下4個(gè)標(biāo)準(zhǔn)進(jìn)行模型的質(zhì)量評估，包括擬合度(fitness)[18]、簡潔度(simplicity)[17]精確度(precision)[19]和泛化度(generalization)[20]。擬合度是指模型可以反映事件日志中行為的程度，簡潔度要求模型可以很好地表達(dá)事件日志中的行為且為最簡單的模型。精確度和泛化度正好相反，前者避免欠擬合，后者則避免過擬合。然而，4個(gè)質(zhì)量維度相互競爭，盡管目前都有相對應(yīng)的量化方法，但在他們之間很難達(dá)到平衡。同時(shí)，多數(shù)過程挖掘算法都只能考慮到部分質(zhì)量指標(biāo)[16]，如基于區(qū)域的挖掘算法可以產(chǎn)生擬合度、精確度較好的過程模型，但其泛化度及簡潔度較差。然而，4個(gè)質(zhì)量維度都很重要[17]，只要一個(gè)的值較低，都會影響到最后的挖掘模型。因此，本文提出綜合質(zhì)量(CQ)函數(shù)[15]，CQ函數(shù)可以平衡4個(gè)質(zhì)量維度，也可以在BdSm算法迭代執(zhí)行過程模型挖掘中對其質(zhì)量進(jìn)行監(jiān)督，最終將CQ作為挖掘?qū)颉?/p>

CQ函數(shù)的計(jì)算公式為：

CQ=(Fr+Pe+Gn+Sm)/4。

式中：Pe，Gn，F(xiàn)r和Sm分別表示過程模型的精確度、泛化度、擬合度和簡潔度；CQ表示模型的綜合質(zhì)量。

(3)遺傳算子的過程樹表示法

種群中所有過程樹的綜合質(zhì)量值，BdSm均使用CQ函數(shù)來計(jì)算。這個(gè)過程中，首先選擇出綜合質(zhì)量較高的多個(gè)過程樹(根據(jù)一定的精英選擇比例)，無需改變地將其保留到下一代，然后對剩余過程樹使用遺傳操作。為使挖掘結(jié)果更好，算法應(yīng)該通過不斷檢索的方式來盡量訪問更大的搜索空間，這樣可以獲取具有多樣性特征的過程樹種群；其次，算法需要使用遺傳操作不斷提升過程樹的綜合質(zhì)量，即過程樹種群應(yīng)當(dāng)滿足“好且不同”的條件。

遺傳操作由突變(mutation)、交叉(crossover)和替換(replacement)[21]3個(gè)步驟組成。突變可以直接操作節(jié)點(diǎn)，提高種群中過程樹的質(zhì)量；交叉隨機(jī)選擇不同過程樹之間的兩個(gè)子樹，對它們進(jìn)行交換，以生成兩棵新的過程樹；替換則剔除種群中質(zhì)量最低的一部分過程樹，然后使用隨機(jī)生成過程樹代替它們。但這兩個(gè)操作只能擴(kuò)大搜索空間，增加種群多樣性，并不能直接提升過程樹質(zhì)量。

(4)遺傳過程混成挖掘算法框架

遺傳過程混成挖掘算法是將過程樹集輸入，優(yōu)化整合后的過程模型及其對應(yīng)的CQ值作為算法的輸出結(jié)果。算法主要包含4個(gè)步驟：

1)初始化。計(jì)算所有的過程樹的CQ值。

2) 選擇。根據(jù)一定的比例選擇多棵有著最高CQ值的過程樹，直接保留至下一代，無需任何其他操作。

3) 繁殖。繁殖操作是通過突變、交叉或是替換操作來改進(jìn)剩余的過程樹。還將設(shè)置如“迭代次數(shù)”等停止條件，若條件不滿足，則迭代進(jìn)行步驟1)～步驟3)的過程。

4)結(jié)束。若停止條件滿足，整個(gè)算法過程結(jié)束。

經(jīng)過以上步驟，算法在滿足停止條件之前多次迭代，每一代種群過程樹的質(zhì)量將不斷升高，最終的挖掘結(jié)果即為最后一代種群中對應(yīng)CQ值最高的過程樹。圖2是遺傳過程混成挖掘算法流程圖。

參照文獻(xiàn)[17]，選擇操作中，比例參數(shù)設(shè)置為25%，這些過程樹將直接保留不作任何更改；將選擇剩余的過程樹中前25%的過程樹進(jìn)行突變操作，以提高過程樹質(zhì)量；接著選擇剩下的排在前25%的過程樹進(jìn)行交叉操作，以擴(kuò)大搜索空間及增加種群多樣性。在此過程中，綜合質(zhì)量值最低的后25%個(gè)體，對其直接使用替換操作進(jìn)行替換。

2.2 提取組織維度信息

組織維度的信息源于事件日志中的#resource屬性，即執(zhí)行者名稱。為將活動與執(zhí)行者信息更好地關(guān)聯(lián)，探明在執(zhí)行者層面上活動與活動之間的關(guān)系，本文提出活動在執(zhí)行者層面的距離度量方法。活動之間度量方法基于活動—執(zhí)行者矩陣，該矩陣記錄每個(gè)活動被某個(gè)特定執(zhí)行者執(zhí)行的頻率，其中：行對應(yīng)活動，列對應(yīng)執(zhí)行者。抽取事件日志中的活動信息和執(zhí)行者信息，可獲得該矩陣。矩陣中的數(shù)值表示某位執(zhí)行者執(zhí)行某個(gè)活動的次數(shù)(如表1)。

定義4活動—執(zhí)行者矩陣M。設(shè)L為事件日志，令a1∈A,r1∈R,c=(c0,c1,c2…)∈L,則：

(1)MC(a1,r1)=

M定義了一個(gè)以A為行，R為列的矩陣，矩陣中的數(shù)值代表執(zhí)行者執(zhí)行活動的次數(shù)。

表1 PM組數(shù)據(jù)活動—執(zhí)行者矩陣

根據(jù)活動—執(zhí)行者矩陣，通過比較行向量之間的距離，可以計(jì)算活動在執(zhí)行者之間的距離(如表2)?；顒又g的距離越近，代表該活動在執(zhí)行人員配備上越相似。通過探究活動在執(zhí)行者層面的相似性，有助于了解項(xiàng)目的人員組成，例如，如果CODE活動和TEST活動距離很近，它們皆由編碼小組的成員完成，而測試小組的成員較少出現(xiàn)在TEST活動中，則該組織的人員配備可能存在問題需要調(diào)整，比如合并兩個(gè)小組成員或者對編碼小組的成員進(jìn)行劃分。在工作任務(wù)分配中，如果兩個(gè)活動距離較近，則可以派遣同樣的人員組成去完成兩個(gè)不同的活動。活動距離表可以記錄日志中所有活動之間的距離，該表能夠?yàn)榻M織維度提供更多信息。本文使用歐氏距離來度量活動之間的距離。由相同的人執(zhí)行的活動在執(zhí)行者層面具有更大的相似性。

表1是PM組數(shù)據(jù)的活動執(zhí)行者矩陣，表2是根據(jù)表1的活動—執(zhí)行者矩陣根據(jù)活動歐氏距離計(jì)算出的活動之間的距離表。活動到自身之間的距離為0，其中，距離越小，代表活動越相似。

表2 PM組數(shù)據(jù)活動到活動之間的距離

2.3 執(zhí)行者信息擴(kuò)充控制流過程模型

控制流維度最終得到的是以過程樹表示的過程模型(如圖3)。然而，該過程模型僅能體現(xiàn)活動之間的控制流結(jié)構(gòu)關(guān)系。因此，本文在挖掘出控制流過程模型的基礎(chǔ)上，添加活動對應(yīng)的執(zhí)行者信息。為此，定義執(zhí)行者過程樹，使用組織維度對過程樹進(jìn)行擴(kuò)展，將活動與執(zhí)行者進(jìn)行映射。執(zhí)行者過程樹是BdSm最終的挖掘結(jié)果(如圖4)。在過程樹的基礎(chǔ)上添加了每個(gè)活動對應(yīng)的執(zhí)行人員，執(zhí)行人員信息從組織維度信息提取得來。執(zhí)行者過程樹組合兩個(gè)維度，獲得全局視角，更直觀地反映過程模型在控制維度以及組織維度的信息。算法1是BdSm的部分偽代碼。

定義6執(zhí)行者過程樹。執(zhí)行者過程樹是一個(gè)五元組PTR=(O,L,B,R,H)，其中：(O,L,B)是如定義3中定義的過程樹，R為每個(gè)葉子節(jié)點(diǎn)L對應(yīng)的執(zhí)行者的有限集合，H?(L×R)是有向弧的集合。其中每個(gè)葉子節(jié)點(diǎn)對應(yīng)至少一個(gè)執(zhí)行者。

算法1BdSm遺傳挖掘算法。

輸入：事件日志L; 迭代次數(shù)q; 過程樹集ProcessTreeSet={t1,t2,…,tN}。

輸出：執(zhí)行者過程樹EPT。

1 foreach (i : [1,2,…,q])

2 foreach (tree: [t1,t2,…tN])

3 CQ (tree); //求每一棵過程樹的CQ值

4 sort(tree); //按照CQ值對過程樹降序排列

5 foreach (j :[1,2,…,N])

6 Save_1=remain(ProcessTreeSet[1:0.25N]);//對排在前25%的CQ值的過程樹無需任何改變直接保留

7 select(ProcessTreeSet[0.25N: 0.5N]);

8 crossover(ProcessTreeSet); //對剩下的排在25%～50%區(qū)間的過程樹進(jìn)行交叉操作

9 Save_2=remain(ProcessTreeSet);

10 select(ProcessTreeSet[0. 5N: 0.75N]);

11 mutation(ProcessTreeSet); //再次選擇剩下的排在50%～75%區(qū)間的過程樹進(jìn)行突變操作

12 Save_3=remain(ProcessTreeSet);

13 select(ProcessTreeSet[0. 75N: 1N]);

14 replacement(ProcessTreeSet); //對最后25%的過程樹進(jìn)行替換操作

15 Save_4=remain(ProcessTreeSet);

16 repeatProcessTreeSet=Save_1∪Save_2∪Save_3∪Save_4;

17 end foreach

18 end foreach

19 end foreach

20 EPT=selectMAX(repeatProcessTreeSet);//選擇質(zhì)量最好的一棵過程樹

21 numA=countActivity(EPT); //獲取過程樹中包含的活動數(shù)目

22 foreach (i : [1,2,…, numA])

23 activity[i]=getActivity();

24 end foreach

25 foreach (i : [1,2,…, numA])

26 numE=countExecutor(activity[i]); //獲取該活動中包含的執(zhí)行者數(shù)目

27 foreach (j : [1,2,…, numE])

28 getExecuto();//獲取執(zhí)行者名稱

29 addExecutor();//添加該執(zhí)行者

30 end foreach

31 end foreach

32 output (EPT)。//輸出執(zhí)行者過程樹

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

為驗(yàn)證所提方法的有效性，本文進(jìn)行了兩組實(shí)驗(yàn)：①從功能角度，展示算法在兩個(gè)不同維度的作用，同時(shí)，使用BdSm算法對數(shù)據(jù)進(jìn)行挖掘，展示迭代次數(shù)隨模型質(zhì)量的變化，觀察初始種群優(yōu)化對最終挖掘結(jié)果的影響；②基于4個(gè)公開數(shù)據(jù)集，從挖掘所得模型質(zhì)量的角度，與其他挖掘算法進(jìn)行對比實(shí)驗(yàn)。

第①組實(shí)驗(yàn)使用過程日志生成器(Process Log Generator,PLG)[22]創(chuàng)建模型，如圖5所示，根據(jù)該模型生成事件日志(簡稱PM數(shù)據(jù))。使用本文方法對事件日志進(jìn)行挖掘，觀察是否能夠生成原始模型，以驗(yàn)證方法的有效性，同時(shí)分析所生成的雙維度模型的含義。圖5中共包含7個(gè)活動，分別是REQ,DES,TEST, CODE,VER, CONF以及REV，基于過程樹表示如圖5所示。根據(jù)該模型生成20個(gè)過程案例。第①組實(shí)驗(yàn)中的第2組數(shù)據(jù)也是由PLG生成的模擬事件日志，記為FW。用于驗(yàn)證控制流維度對生成模型質(zhì)量的提升。

第②組實(shí)驗(yàn)包含4組公開數(shù)據(jù)集的事件日志。Apache Commons Crypto 1.0.0[23]是一個(gè)單元測試軟件事件日志，它描述了ApacheCommonsCrypto 1.0.0庫的流CbcNopad單元測試套件的一次加密運(yùn)行。Ticketing Management(TM)[24]是一家意大利軟件公司服務(wù)臺的票務(wù)管理流程。Sepsis[25]為由醫(yī)院的企業(yè)資源計(jì)劃(Enterprise Resource Planning,ERP)系統(tǒng)記錄的敗血癥案例。Bank Transaction[26]為銀行交易過程數(shù)據(jù)。由于部分?jǐn)?shù)據(jù)過于龐大，結(jié)構(gòu)復(fù)雜，部分過程挖掘算法對其直接挖掘會產(chǎn)生不完備(Unsound)[14]的模型，進(jìn)而無法進(jìn)行模型質(zhì)量評估。因此，本文對事件日志進(jìn)行過濾，事件日志的大小通常根據(jù)4個(gè)指標(biāo)來衡量：案例數(shù)目、事件數(shù)目、活動數(shù)目和案例平均長度(案例中包含事件數(shù)目的平均值)[27]，最終事件日志的大小和結(jié)構(gòu)如表3所示。

表3 實(shí)驗(yàn)中事件日志的大小

3.2 實(shí)驗(yàn)方案及參數(shù)設(shè)置

(1)對PM組事件日志使用BdSm進(jìn)行挖掘，分別生成活動—執(zhí)行者矩陣、執(zhí)行者距離矩陣以及執(zhí)行者過程樹，將PM組數(shù)據(jù)生成的過程模型與原始模型進(jìn)行對比。

(2)對PM組、FW組事件日志分別使用GPM和BdSm進(jìn)行挖掘，對比挖掘獲得模型質(zhì)量與迭代次數(shù)的關(guān)系。

(3)對PM組、FW組以及4個(gè)公開數(shù)據(jù)集的事件日志分別使用α#算法[28]、IM算法、整數(shù)線性規(guī)劃(Integer Linear Programming，ILP)算法[28]以及遺傳挖掘算法(GPM)進(jìn)行挖掘，計(jì)算挖掘所得模型的4個(gè)質(zhì)量維度值以及綜合質(zhì)量，與BdSm的挖掘結(jié)果進(jìn)行對比。

在PM組、FW組以及4組公開數(shù)據(jù)集事件日志的GPM和BdSm的對比實(shí)驗(yàn)中，算法的迭代次數(shù)均設(shè)置為1 000次，4個(gè)遺傳突變操作的操作比例一致。并且由于種群數(shù)量越少，算法的時(shí)間花銷就越少[20]，GPM的初始種群數(shù)量與BdSm中初始種群的數(shù)量設(shè)置一致，BdSm中初始種群的數(shù)目為事件中案例的數(shù)目，而對于案例數(shù)目較多的情況，本文則使用文獻(xiàn)[29]中的方法將相似案例聚類，以確保種群數(shù)目保持在合理范圍內(nèi)。

3.3 實(shí)驗(yàn)結(jié)果

對PM組事件日志生成的20個(gè)案例，一方面，對案例分別使用IM算法挖掘，將該挖掘結(jié)果作為遺傳挖掘算法初始種群，對這些挖掘結(jié)果進(jìn)行優(yōu)化整合之后得到最終的控制流維度過程模型；另一方面，借助活動—執(zhí)行者矩陣(如表1)生成活動距離表(如表2)，拓展控制流維度模型最終生成執(zhí)行者過程樹(如圖6)。

距離越大，則活動在執(zhí)行者層面越不相似；距離越小，則活動越相似，活動到自身的距離為0。由圖4可知，活動DES與REQ的距離最近，這與表1吻合，因?yàn)樵搩蓚€(gè)活動由相同兩個(gè)執(zhí)行者完成且頻率一致。而REQ和CODE的距離較遠(yuǎn)為8.485，這是由于兩個(gè)活動沒有相同的執(zhí)行者執(zhí)行。類似地，結(jié)合執(zhí)行者過程樹和活動與活動之間的距離，能得到較多額外信息。

由挖掘結(jié)果可以看出，BdSm方法能夠挖掘出原始模型，同時(shí)，每個(gè)活動下連接的人名為該活動的執(zhí)行者。

圖7和圖8展示了PM數(shù)據(jù)以及FW數(shù)據(jù)由BdSm以及GPM生成的模型隨著迭代次數(shù)不斷增長綜合質(zhì)量變化的情況。由圖可見，相對于GPM算法而言，BdSm方法的收斂速度更快，同時(shí)達(dá)到高質(zhì)量模型所需迭代次數(shù)更少，最終也生成了綜合質(zhì)量更高的模型。PM組中，BdSm方法在77代便已收斂，GPM算法在150代才收斂;FW組中，BdSm方法在359代便已收斂，GPM算法在602代才收斂。由此說明，使用IM算法確實(shí)可以為遺傳挖掘算法提供更高質(zhì)量的初始種群，進(jìn)而加快算法收斂速度，最終生成更高綜合質(zhì)量的過程模型。

圖9～圖14展示了6組數(shù)據(jù)分別用使用IM算法、α#算法、ILP算法、GPM、以及BdSm挖掘生成模型得到的質(zhì)量，圖中不同的折線代表不同的算法。由圖可見，使用BdSm對6個(gè)數(shù)據(jù)集分別進(jìn)行挖掘，所生成的模型呈現(xiàn)以下規(guī)律：與其他傳統(tǒng)挖掘算法相比，GPM算法以及BdSm方法能夠挖掘得到綜合質(zhì)量較高的模型，這是因?yàn)檫z傳挖掘算法通過質(zhì)量維度指導(dǎo)挖掘的進(jìn)行，從而生成質(zhì)量較高的模型。同時(shí)，從折線的走勢可以看出，相比于其他挖掘算法，BdSm方法挖掘所得模型的4個(gè)質(zhì)量維度值走勢較為穩(wěn)定，折線整體波動幅度不大，這是由于CQ函數(shù)為4個(gè)質(zhì)量維度賦予了相同為1的權(quán)值，最終BdSm方法挖掘生成模型的綜合質(zhì)量也達(dá)到了最高。而對于PM組和FW組而言，事件日志較為簡單、數(shù)據(jù)量較小，因此IM算法、α#算法以及ILP算法生成模型的綜合質(zhì)量都在0.8以上，α#算法、IM算法則達(dá)到了較高的擬合度。而對于Crypto 1.0.0組、TM組以及Bank Transaction組而言，由于事件日志較為復(fù)雜，算法生成的3種模型的綜合質(zhì)量大幅下降，而只有BdSm方法以及GPM算法生成模型的綜合質(zhì)量能維持在較高水平。最后，IM算法能夠產(chǎn)生具有較高擬合度的模型，但模型的簡潔度較低；ILP算法挖掘生成的模型具有較高的簡潔度和擬合度，但是精確度和泛化度較低。而BdSm方法通過CQ函數(shù)作為算法挖掘?qū)颍瑹o論對于哪一個(gè)數(shù)據(jù)集，最終挖掘都能夠得到具有穩(wěn)定的4個(gè)質(zhì)量維度的、綜合質(zhì)量較高的模型。

以上實(shí)驗(yàn)結(jié)果表明，在控制流層面，BdSm方法能夠生成綜合質(zhì)量高于其他挖掘算法的過程模型，究其原因，是遺傳過程挖掘算法使用模型質(zhì)量作為挖掘?qū)颍ＷC能夠生成高綜合質(zhì)量的模型。同時(shí)，BdSm方法相對于GPM算法能夠更快收斂，且達(dá)到更高的綜合質(zhì)量，這是因?yàn)槭褂肐M算法為遺傳挖掘算法準(zhǔn)備了優(yōu)質(zhì)種群，初始種群質(zhì)量越高，則到達(dá)高質(zhì)量模型所需做的改進(jìn)越少，算法收斂更快。而于GPM算法初始種群隨機(jī)生成，質(zhì)量較低，達(dá)到較高質(zhì)量的挖掘結(jié)果需要迭代更多次，算法收斂更慢。而在組織維度層面，結(jié)合活動之間的距離和執(zhí)行者過程樹，能得到更多組織維度的信息，有助于項(xiàng)目管理者了解人員配備所存在的問題，并進(jìn)行調(diào)整。

4 結(jié)束語

本文提出了基于執(zhí)行者過程樹的雙維度遺傳過程挖掘BdSm方法。在控制流維層面，使用預(yù)挖掘的方法為遺傳挖掘算法提供優(yōu)質(zhì)初始種群，從而加快算法收斂速度，實(shí)驗(yàn)證明BdSm方法較其他挖掘方法能夠生成綜合質(zhì)量更高的過程模型，且由于使用綜合質(zhì)量函數(shù)作為挖掘?qū)颍?個(gè)質(zhì)量維度的值較為穩(wěn)定，不存在度量值差距較大的情況；在組織維層面，定義執(zhí)行者過程樹，通過在挖掘模型的基礎(chǔ)上添加對應(yīng)執(zhí)行者信息的方法合并兩種維度，且通過模型可以更加直觀地看出活動和執(zhí)行者之間的關(guān)系。同時(shí)，從執(zhí)行者層面定義活動之間的距離度量方法，距離更近的活動在執(zhí)行者配置層面更為相似，從而幫助項(xiàng)目管理者了解和改進(jìn)組織的人員配備結(jié)構(gòu)。BdSm方法對遺傳過程挖掘算法進(jìn)行改進(jìn)，通過預(yù)挖掘的方法為遺傳挖掘算法提供多個(gè)初始種群，因此，需要多個(gè)案例作為算法的輸入，不適用于單案例事件日志的情況。因此，未來將從單案例事件日志入手，對算法進(jìn)行改進(jìn)。