劉 雯，王桂玲+

(1.北方工業(yè)大學(xué) 信息學(xué)院，北京 100144；2.北方工業(yè)大學(xué) 大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點實驗室，北京 100144)

0 引言

面對復(fù)雜的數(shù)據(jù)世界，針對過程感知的信息系統(tǒng)(Process-Aware Information Systems, PAIS)的過程挖掘算法在處理復(fù)雜事件日志時可能會生成難以理解的“意大利面過程”模型[1],難以從中獲得有價值的信息。因此，在進行過程發(fā)現(xiàn)時，不會試圖將所有案例(case)建立為一個龐大復(fù)雜的模型，而是通過抽取特征的方式描述案例，然后對案例的軌跡進行聚類[1]，使每個聚類結(jié)果對應(yīng)于相關(guān)過程執(zhí)行的連貫集合，每個相關(guān)過程的執(zhí)行情況可以用過程模型表示。

目前，相關(guān)研究已經(jīng)提出幾種面向事件日志的軌跡聚類技術(shù)[2-4]，然而軌跡聚類技術(shù)的應(yīng)用潛力因其可解釋性(interpretability)較差而受到很大影響。目前的軌跡聚類技術(shù)大都依賴“案例軌跡之間的距離”，采用軌跡距離解釋聚類結(jié)果時很不直觀，經(jīng)常不被PAIS業(yè)務(wù)用戶認(rèn)可。PAIS的業(yè)務(wù)用戶更傾向于從領(lǐng)域相關(guān)的角度(如控制流的屬性、特點)理解軌跡聚類結(jié)果[5]，而軌跡之間的距離度量對其而言沒有明確的領(lǐng)域相關(guān)的含義，因此需要一種聚類結(jié)果可被業(yè)務(wù)用戶直觀理解的日志聚類分析方法。在人工智能和機器學(xué)習(xí)領(lǐng)域，很多學(xué)者關(guān)注可解釋的機器學(xué)習(xí)方法的研究，對可解釋性則有不同的定義[6-8]，一般認(rèn)為機器學(xué)習(xí)的可解釋性是人類理解決策原因的程度，或是人類可以持續(xù)預(yù)測模型結(jié)果的程度。對于PAIS的事件日志聚類而言，亟需一種可解釋的聚類分析方法：其聚類結(jié)果基于領(lǐng)域相關(guān)的概念、屬性、特點、規(guī)則等表示，從而可被業(yè)務(wù)用戶直觀理解。

針對上述問題，本文定義“過程連接帶”來描述對軌跡進行可解釋聚類分析的輸出結(jié)果，并借鑒機器學(xué)習(xí)中可解釋聚類的相關(guān)思路，提出一種事件日志的可解釋聚類分析方法iBelt(interpretable process belt)。該方法從活動視角和控制流視角提取事件日志的特征構(gòu)建特征向量，其核心是CLBDT(clustering through boosting decision tree)模型，同時針對從事件日志中提取的活動及控制流相關(guān)特征往往存在高維數(shù)據(jù)的情況，提出基于方差和判別特征選擇的無監(jiān)督特征選擇方法來降低聚類結(jié)果解釋的難度；CLBDT模型利用決策樹聚類(又稱聚類樹)(CLustering through decision Tree, CLTree)方法[9]和提升樹(boosting tree)的思想，基于信息增益動態(tài)更新構(gòu)建聚類樹，從而獲得聚類后簇的矩形區(qū)域(由聚類樹葉子節(jié)點取值組成)，使聚類結(jié)果能夠通過案例活動和控制流屬性值組合的方式直觀地展示。

為驗證方法的有效性，本文使用公開數(shù)據(jù)集定量分析事件日志聚類后形成的不同過程連接帶，得到的過程連接帶擁有簡潔易懂的可解釋規(guī)則。通過Alpha算法對聚類后生成的子日志進行過程挖掘，并在擬合度和簡潔度兩個質(zhì)量維度上與聚類前的事件日志進行對比，實驗表明相比聚類前的事件日志，聚類后的子日志在兩個質(zhì)量維度上得到明顯優(yōu)化。

1 相關(guān)概念

定義1事件、屬性[1]。設(shè)ε為事件空間，即所有可能事件標(biāo)識符的結(jié)合；AN為屬性名的集合。對于任意事件e∈ε和屬性名n∈AN，#n(e)是事件e的屬性n值。如果事件e不含屬性名n，則#n(e)=⊥(空值)。

事件由不同屬性描述，典型的屬性有活動、時間戳和資源，示例事件的片段如表1所示。

表1 某事件日志片段

定義2案例、軌跡、事件日志[1]。設(shè)￡為案例空間，即所有可能案例標(biāo)識符的集合。案例也有屬性。對于任意案例c∈￡和名稱n∈AN，#n(c)是案例c的屬性n的值(如果案例c沒有屬性n，則#n(c)=⊥)。每一個案例(case)都有一個特殊的強制屬性——軌跡(trace)。

(1)軌跡是事件σ∈ε*的一個有限序列，其中每個事件只出現(xiàn)一次。

(2)事件日志是案例L?￡的集合，其中每個事件在整個日志中最多出現(xiàn)一次。

定義3軌跡聚類[10]。設(shè)L?￡為一個事件日志，在L上的一個軌跡聚類是L的一個子日志。一個軌跡聚類T￡?P(L)是事件日志L上的一組軌跡。

定義4事件日志視角[1-2]。視角是從特定角度描述軌跡的相關(guān)項，其用具體數(shù)值度量案例中的軌跡，對事件日志進行分析后可用多個視角構(gòu)成一個聚合向量來描述軌跡行為。

(1)控制流視角 描述活動發(fā)生順序，例如(A,B)表示在事件日志的軌跡中，活動A發(fā)生以后緊接著發(fā)生活動B，稱為直接跟隨關(guān)系，可以統(tǒng)計軌跡活動之間的直接跟隨關(guān)系是否發(fā)生或者發(fā)生的次數(shù)。

(2)組織視角 展現(xiàn)資源的組織情況，可以統(tǒng)計事件組織資源者參與的次數(shù)或資源者是否參與。

(3)活動視角 關(guān)注活動的發(fā)生頻率，可以統(tǒng)計事件活動發(fā)生的次數(shù)或活動是否存在。

(4)時間視角 又稱性能視角，其關(guān)注事件的時間和頻率，統(tǒng)計同一個案例中事件發(fā)生的次數(shù)、案例的持續(xù)時間，以及案例中相鄰事件持續(xù)時間的一些統(tǒng)計量，如最值、均值和眾數(shù)等。

決策者根據(jù)組織數(shù)據(jù)能夠深入了解典型的工作模式和組織結(jié)構(gòu)，利用活動數(shù)據(jù)能夠更好地進行科學(xué)決策并分析不同軌跡間的差異，時間戳可以診斷與性能相關(guān)的問題，如瓶頸問題。

定義5過程連接帶。L?￡為一個事件日志，過程連接帶B是一個三元組B=T,I,C，過程連接帶中的過程實例可用基于軌跡特征屬性的規(guī)則直觀解釋。

(1)T為過程連接帶對應(yīng)的軌跡集合。假設(shè)事件日志L聚類后為兩個簇，對應(yīng)兩個過程連接帶的軌跡集合T1(trace1,trace2,trace3)和T2(trace4,trace5)。

(2)I為對過程連接帶的定量描述。對于某過程連接帶對應(yīng)的軌跡集合，假設(shè)其特征組合為[X,Y]，其特征值經(jīng)過可解釋聚類算法形成的定量矩形區(qū)域為{X?[x1,x2],Y?[y1,y2]}，x1和y1是特征值的最小值，x2和y2是特征值的最大值。

(3)C為不同過程連接帶經(jīng)過過程挖掘得到的不同的因果網(wǎng)(C-net)[1]。

過程挖掘的評估主要有擬合度、精確度、泛化度和簡潔度4個質(zhì)量標(biāo)準(zhǔn)(詳見5.2節(jié))，四者彼此競爭，很難達到平衡。一個擬合度好的模型允許事件日志反映行為發(fā)生的過程；精確度避免欠擬合，泛化度則避免過擬合；簡潔度意味著得到的模型越簡單越好。BUIJS等[11]認(rèn)為現(xiàn)有的過程發(fā)現(xiàn)算法通常最多考慮4個主要質(zhì)量維度中的兩個。擬合度目前是評價過程模型質(zhì)量最重要的指標(biāo)，可以在保證提高擬合度、精確度和泛化度的情況下考慮簡潔度。

2 相關(guān)工作

復(fù)雜的事件日志可以通過案例軌跡進行聚類達到簡化的目的，而本文希望得到的是具有可解釋性規(guī)則的事件日志過程連接帶。然而，目前常用的軌跡聚類算法得到的結(jié)果通常缺乏可解釋性或可解釋性弱，傳統(tǒng)軌跡聚類算法的主要思路有兩種：①將事件日志轉(zhuǎn)換到向量空間，執(zhí)行基于距離的聚類算法；②基于模型的序列進行聚類，基于過程模型識別出相似序列的組。方法①，如文獻[2,4]提出的技術(shù)，將事件日志中的軌跡轉(zhuǎn)換到向量空間中，其特征由活動、控制流中的直接跟隨關(guān)系、時間戳等組成，然后應(yīng)用數(shù)據(jù)挖掘領(lǐng)域常用的距離聚類算法(如K-means算法)在向量空間中應(yīng)用不同的距離度量(如歐式距離)進行聚類，然而基于距離的聚類算法方法無法定量描述事件日志的具體視角，缺乏可解釋性；方法②，如文獻[3]提出的技術(shù)，以Markov模型為基準(zhǔn)進行軌跡聚類，在該序列聚類中，每個聚類簇都與一個馬爾科夫鏈相關(guān)聯(lián)，但是基于模型的序列聚類算法無法定量描述軌跡序列中實例的取值情況，可解釋性較弱。

對于如何對過程實例進行解釋說明，WEERDT等[5]提出的聚類過程實例解釋搜索(Searching for Explanations for Clustered Process Instances, SECPI)算法能夠為過程實例找到最小控制流特征集，從控制流角度提供解釋能力，為數(shù)據(jù)添加集群標(biāo)簽后再應(yīng)用有監(jiān)督的支持向量機(Support Vector Machine, SVM)分類器得到解釋規(guī)則。Case2vec基于Word2vec詞嵌入方法對過程實例從活動和案例屬性視角進行向量表示，在此基礎(chǔ)上進行聚類分析[12]。然而Case2vec對屬性的選擇很敏感，如果沒有先驗知識很難找到好的屬性，而且在真實的事件日志中，活動屬性可能會存在沒有實際含義的情況，從而使詞嵌入方法得到的聚類結(jié)果不能被業(yè)務(wù)用戶直觀理解。

復(fù)雜事件日志提取特征向量時很容易因維數(shù)過高而造成“維數(shù)災(zāi)難”，而且會使可解釋性算法生成復(fù)雜的解釋規(guī)則而降低用戶的可讀性。針對決策樹的降維問題，倪春鵬[13]通過比較條件屬性相對于劃分類別的重要性來決定保留哪些屬性參與建立決策樹，其改進的決策樹降維方法是有監(jiān)督的特征選擇方法，而真實的事件日志往往無法準(zhǔn)確得到條件屬性；王偉[14]將原始數(shù)據(jù)空間轉(zhuǎn)換到主成分空間，利用主成分分析算法的思想改進了傳統(tǒng)決策樹的C4.5算法，但是破壞了特征數(shù)據(jù)本身的可解釋性。無監(jiān)督的特征選擇方法能夠在很大程度上保留特征數(shù)據(jù)本身的可解釋性，其中無監(jiān)督的最大方差選擇方法[15]以特征數(shù)據(jù)的最大方差為評價標(biāo)準(zhǔn)，按照其特征重要性排序進行選擇；無監(jiān)督的拉普拉斯特征選擇方法[16]在最大方差的基礎(chǔ)上引入數(shù)據(jù)的局部結(jié)構(gòu)進行分析。然而，這兩種方法僅考慮數(shù)據(jù)本身的區(qū)分度，忽略了特征之間的相關(guān)性?？紤]特征間的相關(guān)性問題，無監(jiān)督判別特征選擇法(Unsupervised Discriminant Feature Selection, UDFS)[17]采用局部類間散度最大化與類內(nèi)散度最小化的策略獲取最優(yōu)特征子集，非負(fù)譜分析無監(jiān)督特征選擇法(Non-negative Discriminative Feature Selection, NDFS)[18]引入非負(fù)約束來獲得更準(zhǔn)確的結(jié)果，多聚類特征選擇法(Multi-Cluster Feature Selection, MCFS)[19]通過譜分析捕獲局部流形結(jié)構(gòu)。

3 iBelt方法

3.1 基本思想

本文用過程連接帶定義對過程事件日志進行可解釋聚類分析的結(jié)果。如圖1所示，事件日志由過程實例(PI01,PI02,…,PIn)構(gòu)成，經(jīng)過具有可解釋性的軌跡聚類算法后產(chǎn)生聚類簇(cluster1,cluster2,…,clustern)，聚類簇中各自包含多組不同的過程實例，形成具有可解釋規(guī)則的過程連接帶(B1,B2,…,Bn)。如圖1所示，基于定義5，對于軌跡聚類后的cluster1，其過程連接帶可表示為B1=T1,I1,C1，其中，對于軌跡組合T1(trace1,trace2,…,tracen)，當(dāng)特征組合為X和Y時，可將其映射到二維空間，軌跡即可表示為二維空間中的點。T1中的點便構(gòu)成矩形區(qū)域I1，可將I1定量描述為{X?[2,3],Y?[1.5,3]}，對T1進行過程挖掘后得到的因果網(wǎng)為C1。

得到過程連接帶可解釋性規(guī)則最關(guān)鍵的一步在于建立可解釋聚類模型。目前，典型的聚類算法往往基于距離算法或密度算法對數(shù)據(jù)點進行分簇，這樣得到的簇邊界往往是不規(guī)則的，而且聚類結(jié)果缺乏可解釋性。因此，考慮決策樹算法規(guī)則簡單、結(jié)果具有可讀性的特點，借鑒可解釋聚類算法CLTree思想構(gòu)建CLBDT模型，得到具有可解釋性的聚類結(jié)果，滿足定量描述過程連接帶的需求。

CLTree的基本思想是在目標(biāo)數(shù)據(jù)Y中均勻地添加一類虛擬數(shù)據(jù)N，再用決策樹對目標(biāo)數(shù)據(jù)和虛擬數(shù)據(jù)進行二分類，將虛擬數(shù)據(jù)從分類結(jié)果移除，剩下的不同特征屬性范圍的目標(biāo)數(shù)據(jù)就成為聚類結(jié)果[9]。這種方法之所以有效，是因為如果目標(biāo)數(shù)據(jù)中存在聚類，則Y點不可能均勻分布于整個空間。若在該空間中添加均勻分布的虛擬數(shù)據(jù)點N后，再采用決策樹二分類方法對Y點和N點進行分類，則可使在目標(biāo)數(shù)據(jù)Y聚集區(qū)域內(nèi)的Y點比N點多，屬于Y點聚集區(qū)域，而在其他區(qū)域N點比Y點多，屬于N點聚集的區(qū)域。CLTree使用的單棵決策樹在聚類時容易受噪聲影響而做出錯誤的決策[20]，提升樹(boosting tree)[21]是以決策樹作為基學(xué)習(xí)器，通過串行迭代得到強學(xué)習(xí)器的算法，每一次迭代均以損失函數(shù)最小為優(yōu)化目標(biāo)學(xué)習(xí)基函數(shù)。相對于提升樹，梯度提升決策樹(Gradient Boosting Decision Tree, GBDT)是一類結(jié)合提升樹[21]和梯度提升思想[22]來提高預(yù)測準(zhǔn)確性的算法，如果能夠借鑒GBDT的優(yōu)點，則可能進一步提升CLTree可解釋聚類算法的聚類準(zhǔn)確性。

如果基于CLTree思想將原始數(shù)據(jù)作為Y類，預(yù)先生成均勻的虛擬數(shù)據(jù)作為N類，采用GBDT思想對數(shù)據(jù)進行二分類，再將葉子節(jié)點作為聚類簇，則難以得到預(yù)想的結(jié)果。通過實驗也發(fā)現(xiàn)，該方法聚類子日志的擬合度質(zhì)量低于未聚類前，且遠低于CLTree方法，這是因為預(yù)先生成所有的N類數(shù)據(jù)并不能將原始數(shù)據(jù)很好地分簇，而是需要在決策樹每次分支時動態(tài)生成虛擬的N類數(shù)據(jù)點，以保障添加足夠的N類數(shù)據(jù)點來隔離聚類[9]。然而，如果在梯度提升決策樹算法中動態(tài)生成N類數(shù)據(jù)，則又將破壞梯度計算的意義。通過觀察CLTree建立決策樹的過程發(fā)現(xiàn)，在當(dāng)前決策樹中，同一聚類中的點比不同聚類中的點有更高的概率在下一個決策樹中仍然屬于同一個聚類，也就是說，如果前一棵決策樹在分支時將同一個聚類中的數(shù)據(jù)點分到了不同分支節(jié)點上，則可以利用提升樹思想，通過下調(diào)信息增益提升建立下一棵決策樹的準(zhǔn)確性[23]。因此，一方面，在生成N類數(shù)據(jù)時沿用CLTree動態(tài)增加虛擬數(shù)據(jù)的方法，當(dāng)節(jié)點中N點數(shù)少于Y點時，將N點增加到與Y點相同的數(shù)量；另一方面，在建立聚類樹時，通過動態(tài)更新信息增益使同一個簇中的點在建立下一棵聚類樹的過程中更傾向于被劃分到一起，從而提高聚類結(jié)果的準(zhǔn)確性。

當(dāng)從事件日志中提取的相關(guān)特征維度較高時，CLBDT模型的決策樹結(jié)構(gòu)將過于復(fù)雜，從而增加聚類結(jié)果可解釋規(guī)則的復(fù)雜性，降低計算效率，因此本文在提取模型特征后通過降維來解決該問題。然而，典型的降維方法是將原始高維特征空間轉(zhuǎn)化到低維特征空間，投影矩陣為稠密矩陣，從而將提取的所有特征混合生成新的特征，這樣的降維方法會丟失原始特征本身的特點和可解釋性，與本文研究目的相悖。因此，為了更好地增強子空間學(xué)習(xí)的可解釋性，考慮特征選擇的過濾式和嵌入式方法，提出方差結(jié)合判別特征選擇[17]的無監(jiān)督特征選擇算法，既能兼顧方差選擇出表現(xiàn)能力強的特征，又能利用離散矩陣和特征相關(guān)性選擇具有判別性的特征。

3.2 方法流程

按照3.1節(jié)所述的算法基本思想，本文首先對事件日志進行特征提取，將提取后的特征作為可解釋聚類模型CLBDT的輸入數(shù)據(jù)，其中通過基于無監(jiān)督特征選擇方法對輸入數(shù)據(jù)進行降維，模型將輸出不同聚類簇的可解釋規(guī)則，用于支持對過程連接帶進行定量描述；然后對聚類后的子日志進行過程發(fā)現(xiàn)，得到對應(yīng)的過程連接帶。iBelt方法的基本流程如圖2所示。

3.3 特征提取

在進行事件日志可解釋性軌跡聚類之前，需要對數(shù)據(jù)進行特征提取，而為了使用戶能更直觀地理解聚類結(jié)果，提取的特征需要能夠體現(xiàn)領(lǐng)域相關(guān)的概念、屬性、特點或規(guī)則。其中，領(lǐng)域相關(guān)的概念和特點可以通過多個過程實例聚類間具有區(qū)別性的特征來體現(xiàn)，這主要依賴于過程的控制流特征[5]，同時領(lǐng)域相關(guān)的屬性以及后續(xù)的過程發(fā)現(xiàn)主要通過從活動視角提取的特征體現(xiàn)。因此，分別提取活動視角和控制流視角的特征進行CLTree聚類，通過實驗結(jié)果可以發(fā)現(xiàn)，當(dāng)基于活動視角提取活動出現(xiàn)的頻數(shù)時，聚類后的輪廓系數(shù)更優(yōu)；當(dāng)基于控制流視角提取“直接跟隨關(guān)系是否存在”的特征時，聚類后的輪廓系數(shù)更優(yōu)。

事件日志通過特征提取后的特征向量如表2和表3所示。表2是2013年BPI挑戰(zhàn)賽的OProblem數(shù)據(jù)集(https://doi.org/10.4121/uuid:3537c19d-6c64-4b1d-815d-915ab0e479da)提取特征后構(gòu)建的特征向量，表3是2020年BPI挑戰(zhàn)賽的DomesticDeclarations數(shù)據(jù)集(https://doi.org/10.4121/uuid:52fb97d4-4588-43c9-9d04-3604d4613b51)提取特征后構(gòu)建的特征向量。其中，OProblem數(shù)據(jù)集特征向量為9維，DomesticDeclarations數(shù)據(jù)集特征向量為56維。

表2 OProblem數(shù)據(jù)集的特征向量

表3 高維數(shù)據(jù)集DomesticDeclarations的特征向量

3.4 CLBDT模型

3.4.1 無監(jiān)督特征選擇

實驗證明，特征維度過高時不僅會消耗大量時間，還會產(chǎn)生大量噪聲點。例如，事件日志InternationalDeclarations聚類后僅有20.20%的點在簇中，事件日志PrepaidTravelCost聚類后僅有39.02%的點在簇中。因此，模型首先要降維，為了不破壞特征本身的可解釋性和后續(xù)聚類結(jié)果的可解釋性，本文采用無監(jiān)督特征選擇方法，主要考慮特征本身是否發(fā)散以及特征之間的相關(guān)性。

方差選擇算法考慮特征數(shù)據(jù)本身的區(qū)分程度，簡單易行，但忽視了數(shù)據(jù)間的相關(guān)性，而不論控制流視角還是活動視角，不同視角的特征間必然存在一定相關(guān)性。當(dāng)數(shù)據(jù)集控制流視角的特征矩陣偏向稀疏且零向量過多時，控制流視角特征本身的區(qū)分度下降，方差選擇算法會偏向于選擇活動視角的特征，為了使輸入的特征向量能夠均衡兩個視角的特征解釋性，采用UDFS方法計算特征間的相關(guān)性，增加控制流視角判別的重要性。最后，將方差選擇算法和無監(jiān)督判別選擇算法結(jié)合，既能通過方差選擇保留本身具有較大區(qū)分度的特征，又能通過UDFS算法同時考慮特征間的相關(guān)性，選擇出具有判別性的特征。

算法1無監(jiān)督特征選擇算法。

輸入：事件日志特征提取后的原始特征集F={f1,f2,…,fm}。

輸出：特征選擇后的事件日志特征集Fs。

1)方差選擇計算特征重要性I1；

2)根據(jù)I1排序，得到拐點的前t個特征集F1={f1,f2,…,ft}；

3)UDFS方法計算判別重要性I2；

3)根據(jù)I2排序，得到拐點的前k個特征集F2={f1,f2,…,fk}；

4)最終特征集Fs=F1∪F2。

3.4.2 通過更新信息增益建立多棵聚類樹

根據(jù)3.1節(jié)的分析，在當(dāng)前決策樹中，同一聚類中的點比不同聚類中的點有更高的概率在下一個決策樹中仍然屬于同一個聚類，由此指導(dǎo)決策樹的構(gòu)建，通過更新信息增益使得同一個簇中的點更傾向于被劃分到一起，從而提高聚類結(jié)果的準(zhǔn)確性。采用無監(jiān)督思想建立決策樹時，首先將事件日志特征數(shù)據(jù)集中的真實數(shù)據(jù)作為類別為Y的點，然后假設(shè)數(shù)據(jù)空間中均勻分布著類別為N的虛擬數(shù)據(jù)點，將原始點聚類問題轉(zhuǎn)變?yōu)閷φ鎸嶞cY和虛擬點N進行分類，即將聚類問題轉(zhuǎn)換為在空間中把數(shù)據(jù)點劃分到密集區(qū)域還是空白區(qū)域的問題。決策樹用劃分前后信息熵的差值(即信息增益)衡量用當(dāng)前特征對樣本集合D劃分效果的優(yōu)劣，信息增益越大，特征屬性對樣本集合D進行劃分所獲得的純度越高。

假設(shè)一個原始數(shù)據(jù)集有q類，即C1,…,Cq，將原始數(shù)據(jù)集D信息熵定義為

(1)

式中：freq(Cj,D)為類Cj在D的數(shù)據(jù)點數(shù)；|D|為D中的數(shù)據(jù)記錄總數(shù)。

對于樣本集合D而言，其樣本屬性A有m個不同的屬性值，可根據(jù)屬性A將D劃分為m個子集{A1,A2,…,Am}，根據(jù)屬性A劃分樣本后的信息熵為

(2)

式中|Di|為分區(qū)后子集Di中的數(shù)據(jù)點數(shù)。

最后，屬性A對樣本集合D分區(qū)所得的信息增益為

gain(D,A)=info(D)-infoA(D)。

(3)

CLBDT模型基于提升樹的思想，在建立多棵決策樹時更新信息增益，即通過計算決策樹，在分支時將當(dāng)前在同一個聚類中、但分到了下一棵決策樹不同分支節(jié)點上的數(shù)據(jù)點信息增益作為調(diào)整項，調(diào)整項的計算公式為

(4)

更新后的新信息增益

(5)

式中α為學(xué)習(xí)率，用于控制每棵樹對前一棵樹信息增益的糾正強度。

算法2CLBDT建立多棵聚類樹算法。

輸入：事件日志特征選擇后的特征集F={f1,f2,…,fk}。

輸出：聚類簇C={C1,C2,…,Cn}。

1) 對每個屬性遍歷特征值，由信息增益標(biāo)準(zhǔn)gain分裂節(jié)點得到第1棵聚類樹；

2) Repeat:

3) get_GainRes(gainRes)

4) buildTree(Tree) ：

5) calculate_Gain(newGain)

6) Until第M棵樹與前一次的迭代結(jié)果基本不變

7) 返回第M棵樹

3.4.3 尋找聚類樹的最佳分割點

本節(jié)分析提取的活動視角和控制流視角特征。顯然，活動視角的特征為數(shù)值型數(shù)據(jù)，是一些活動出現(xiàn)的頻數(shù)，而基于控制流視角提取的特征是“直接跟隨關(guān)系是否存在”，特征的取值只有0和1，屬于類別型數(shù)據(jù)。傳統(tǒng)決策樹的信息增益標(biāo)準(zhǔn)不會考慮之前計算的信息增益結(jié)果，而CLBDT中的聚類樹則會在每個維度上通過信息增益標(biāo)準(zhǔn)找到一個最佳分割，而且通過比較聚類簇的相對密度(r=rY/rN，rY和rN分別為區(qū)域中Y點和N點的數(shù)量)，能夠向前尋找(最多兩步)切割較少的聚類簇區(qū)域，從而找到最佳分割點，將其稱為前瞻策略。數(shù)值型數(shù)據(jù)在尋找最佳分割點時要考慮數(shù)據(jù)點是否稠密，即點和點之間的距離盡可能小，因此需要采用前瞻策略尋找最佳分割點；對于類別型數(shù)據(jù)，不同取值不存在距離關(guān)系[24]，控制流視角中的直接跟隨關(guān)系只有0和1兩種取值，根據(jù)過程連接帶的需求，存在相同流動關(guān)系的軌跡應(yīng)被劃分到一個簇中，因此只需分別計算這兩種取值分裂時左右子樹的信息增益，信息增益最大的即為最佳分割點。

3.5 模型時間復(fù)雜度分析

方差選擇算法的時間復(fù)雜度為O(n)，無監(jiān)督判別特征選擇算法的時間復(fù)雜度為O(d3+n2c)，無監(jiān)督特征選擇算法由這兩種算法組成，時間復(fù)雜度為O(d3+n2c+n)，其中n為樣本數(shù)，d為特征數(shù)，c為聚類中的類數(shù)。

數(shù)值型特征分裂時采用{取值≤value}和{取值>value}的二分裂方式，決策樹分裂一個節(jié)點的時間復(fù)雜度為O(dnlgn)，構(gòu)建整顆決策樹的時間復(fù)雜度為O(dn2lgn)。對CLTree時間復(fù)雜度影響最大的為其前瞻策略，因為當(dāng)數(shù)據(jù)類型為數(shù)值型時，前瞻策略最多可能會為一個特征尋找3個切分點，使得分裂一個節(jié)點的時間復(fù)雜度為O(dnlgn)+O(dn3)，其時間復(fù)雜度為O(dn4)，而當(dāng)數(shù)據(jù)為類別型數(shù)據(jù)時，不需要尋找3個切分點，其時間復(fù)雜度為O(dn2)。根據(jù)3.4.3節(jié)的分析，本文的活動視角為數(shù)據(jù)型，控制流視角特征為類別型，因此將特征數(shù)d分為數(shù)值型特征dnum個和類別型特征dcat個，則建立一個聚類樹的總時間復(fù)雜度為O(dnumn4+dcatn2)，CLBDT對迭代的m棵決策樹的總時間復(fù)雜度為O(mdnumn4+mdcatn2)。再進行特征選擇以后，特征數(shù)量變?yōu)閗，時間復(fù)雜度則變?yōu)镺(mknumn4+mkcatn2)。

傳統(tǒng)的聚類方法K-means的時間復(fù)雜度為O(nkdt)，其中k為所選擇的聚類中心，t為迭代次數(shù)。

4 實驗

4.1 實驗數(shù)據(jù)

本文用6個事件日志展示過程活動，驗證模型的過程發(fā)現(xiàn)質(zhì)量。OProblem(https://doi.org/10.4121/uuid:3537c19d-6c64-4b1d-815d-915ab0e479d

a，819個軌跡，2 351個事件)和事件日志Incidents(https://doi.org/10.4121/uuid:500573e6-accc-4b0c-9576-aa5468b10cee，7 554個軌跡，65 533個事件)是沃爾沃比利時信息技術(shù)公司(Volvo IT Belgium)的真實事件日志，來自VINST的事件和問題管理系統(tǒng)，這兩個事件日志來自2013年BPI挑戰(zhàn)賽。另外4個事件日志來自2020年的BPI挑戰(zhàn)賽(https://doi.org/10.4121/uuid:52fb97d4-4588-43c9-9d04-3604d4613b51)，是埃因霍芬理工大學(xué)報銷過程中的真實事件日志。其中，事件日志DomesticDeclarations(10 500個軌跡，56 437個事件)主要記錄國內(nèi)旅行的聲明要求，事件日志InternationalDeclarations(6 449個軌跡，72 151個事件)主要記錄國際旅行聲明要求，事件日志PrepaidTravelCost(2 099個軌跡，18 246個事件)主要記錄預(yù)付旅行費，事件日志RequestForPayment(6 886個軌跡，36 796個事件)主要記錄付款請求。

4.2 評價指標(biāo)

無監(jiān)督特征選擇的CLBDT模型用輪廓系數(shù)(Silhouette Coefficient, SC)、程序執(zhí)行時間和最終在簇中的數(shù)據(jù)點占比評估事件日志的案例軌跡聚類后的效果，預(yù)先將案例屬性作為類標(biāo)簽的Case2vec方法[12]用歸一化互信息(Normalized Mutual Information, NMI)作為評價指標(biāo)，具體說明如下：

(1)SC指標(biāo)根據(jù)簇內(nèi)所有點之間的距離計算簇內(nèi)緊密度，根據(jù)不同簇樣本點之間的最近距離計算簇間分離度，其值的取值范圍為[-1,1]，越接近1，聚類效果越好。

(2)NMI指標(biāo)度量算法結(jié)果與標(biāo)準(zhǔn)結(jié)果之間的相似度，結(jié)果越相似，NMI值越接近1；如果算法結(jié)果很差，則NMI值接近0。

(3)程序執(zhí)行時間指進行聚類的整個時間，單位為s。

(4)簇中的數(shù)據(jù)點占比指聚類后簇中的數(shù)據(jù)點總數(shù)比原始數(shù)據(jù)點總數(shù)。

將聚類以后形成的簇對應(yīng)的案例生成子日志，分別用Alpha挖掘算法進行過程發(fā)現(xiàn)，其中質(zhì)量評估標(biāo)準(zhǔn)擬合度和簡潔度定義如下：

(1)擬合度指標(biāo)fitness用于評價挖掘得到的過程模型能夠重現(xiàn)事件日志的能力[1]。能被模型重現(xiàn)的軌跡越多，該模型的擬合度值就越高。擬合度目前是評價過程模型質(zhì)量最重要的指標(biāo)，定義為

(6)

式中：m為缺失的token；q為消耗的token；p為產(chǎn)生的token；r為遺留的token。擬合度的取值范圍為[0,1]，值越大，擬合度越好。

(2)簡潔度指標(biāo)考慮奧卡姆剃須刀原則，根據(jù)該原則，最好的模型不僅是能解釋事件日志中所見行為的執(zhí)行過程，而且是最簡單的模型。首先考慮Petri網(wǎng)的轉(zhuǎn)換平均度meanDegree，將其定義為輸入弧和輸出弧的數(shù)量之和。在0～∞之間選擇一個數(shù)字h，然后將基于反弧度的簡潔度定義為

(7)

簡潔度的取值范圍為[0,1]，值越大，結(jié)構(gòu)越簡潔。

4.3 實驗過程

4.3.1 特征提取結(jié)果

對6個事件日志進行活動和控制流視角轉(zhuǎn)換關(guān)系的特征提取，先采用方差特征選擇算法選擇出區(qū)分度大的特征，因為當(dāng)控制流視角矩陣過于稀疏時，結(jié)果會偏向活動視角的特征，所以進行UDFS選擇，為控制流視角的特征增加判別重要性。特征提取后的降維結(jié)果如表4所示。

表4 事件日志特征提取情況

4.3.2 方法結(jié)果分析

相比傳統(tǒng)的聚類方法K-means，CLBDT模型的聚類結(jié)果具有可解釋性，其能夠清晰地了解如何決策得到每個簇，而且滿足過程連接帶的需求。因為K-means算法本身屬于黑盒模型，即不提供直接的、可由人類解釋的決策規(guī)則，所以在選擇降維方法時，不用考慮其是否破壞特征本身的可解釋性，因此選用最傳統(tǒng)的主成分分析(Principal Component Analysis, PCA)降維方法與之搭配。聚類最終的K值由最優(yōu)輪廓系數(shù)決定，如表5所示。

表5 K-means算法結(jié)果對比

將CLBDT模型與文獻[12]中的Case2vec方法對比，Case2vec方法能夠根據(jù)軌跡和事件的語義信息進行聚類，其需要預(yù)先決定用案例的某個屬性作為類標(biāo)簽，其NMI值受類標(biāo)簽的影響很大，而在真實的數(shù)據(jù)集中很難找到合適的案例屬性作為類標(biāo)簽，因此，該方法在真實數(shù)據(jù)集的應(yīng)用中具有局限性。如表6所示，在InternationalDeclarations數(shù)據(jù)集中使用不同的類標(biāo)簽，得到的NMI值相差較大。數(shù)據(jù)集OProblem和Incidents的事件日志軌跡中只有一個案例屬性concept:name，表示案例編號具有唯一性，并沒有其他額外的案例屬性可以作為類標(biāo)簽，因此無法采用Case2vec方法。對于2020年BPI挑戰(zhàn)賽的4個數(shù)據(jù)集，首先需要分別通過具體數(shù)據(jù)集的實際情況設(shè)置類標(biāo)簽，然后選擇其他屬性，如案例的concep:name、事件的concep:name等構(gòu)成特征向量，最后對比聚類后的NMI效果、程序執(zhí)行時間等評價指標(biāo)，對比結(jié)果如表6所示。

表6 Case2vec聚類結(jié)果對比

4.4 iBelt方法結(jié)果分析

4.4.1 可解釋聚類結(jié)果分析

本節(jié)以數(shù)據(jù)集DomesticDeclarations進行CLBDT聚類后簇的情況為例分析數(shù)據(jù)集DomesticDeclarations聚類后簇所對應(yīng)的過程連接帶。分析數(shù)據(jù)集DomesticDeclarations所提取的特征矩陣，一共56維，分為數(shù)值型和類別型兩類數(shù)據(jù)，如表3所示。通過無監(jiān)督特征選擇方法從原本的56個特征中保留9個區(qū)分度大且具有判別性的特征(如表7)，通過可解釋聚類方法生成3個簇。

聚類結(jié)果的3個簇對應(yīng)3個過程連接帶(B1,B2,B3)，其軌跡組合分別為(T1,T2,T3)。第1個過程連接帶B1的軌跡組合T1共有9 775條軌跡，第2個過程連接帶B2的軌跡組合T2共有133條軌跡，第3個過程連接帶B3的軌跡組合T3共有161條軌跡，案例軌跡點最多的連接帶軌跡組合為T1。

過程連接帶的定量描述I如下：B1和B3控制流角度的跟隨關(guān)系(0,9)，(9,7)，(10,9)，(10,15)都不存在，B2的跟隨關(guān)系(0,9)和(10,15)不存在，但是(9,7)和(10,9)一定存在；相比B1和B2，B3中Declaration REJECTED by SUPERVISOR活動必然發(fā)生1次，活動特征Declaration APPROVED by ADMINISTRATION在3個過程連接帶中的取值范圍各不相同，其中B1∈[0,1]，B2∈[1,1]，B3∈[2,2]。

表7 DomesticDeclarations的過程連接帶

4.4.2 聚類評價指標(biāo)分析

分別使用CLTree和CLBDT對事件日志進行聚類，結(jié)果如表8所示。對于特征維度低的數(shù)據(jù)集(如OProblem)，CLBDT模型的程序執(zhí)行時間降低得相對較小，效果不夠明顯，而對于特征相對較多的數(shù)據(jù)集(如DomesticDeclarations)，CLBDT模型能夠極大減少程序執(zhí)行時間，明顯提升聚類效果輪廓系數(shù)，同時解決產(chǎn)生大量噪聲點的問題。例如，InternationalDeclarations聚類后僅有20.20%的點在簇中，而經(jīng)過降維后簇中點總數(shù)的占比為84.77%；PrepaidTravelCost聚類后僅有39.02%的點在簇中，而經(jīng)過降維后簇中點總數(shù)的占比為92.85%。

表8 模型聚類結(jié)果對比

續(xù)表8

4.4.3 過程發(fā)現(xiàn)結(jié)果分析

對6個事件日志的原日志以及經(jīng)過可解釋聚類后的子日志進行過程發(fā)現(xiàn),結(jié)果如表9所示。

表9 過程發(fā)現(xiàn)結(jié)果

續(xù)表9

由表9可見，過程相對復(fù)雜的事件日志，其提取的特征維度相對較高，基線簡潔度相對較低。如果不進行降維，維數(shù)過高的數(shù)據(jù)集會產(chǎn)生大量噪聲點，最終結(jié)果的擬合度和簡潔度雖然表現(xiàn)良好，但是犧牲了大量的過程實例。高維數(shù)據(jù)集降低維度后，雖然擬合度和簡潔度表現(xiàn)不如降維前，但也遠優(yōu)于基線。從過程發(fā)現(xiàn)結(jié)果的擬合度質(zhì)量來看，CLBDT模型基本優(yōu)于基線質(zhì)量和CLTree模型；從過程發(fā)現(xiàn)結(jié)果的簡潔度質(zhì)量來看，CLBDT模型和CLTree模型的簡潔度均優(yōu)于基線質(zhì)量，在部分?jǐn)?shù)據(jù)集(如DomesticDeclarations)上CLBDT模型會低于CLTree模型。如果追求Petri網(wǎng)的一致性，則看重擬合度，選擇CLBDT模型不但合適，而且簡潔度也會優(yōu)于本身結(jié)構(gòu)；如果單純只追求過程簡單，則CLTree模型已經(jīng)滿足需求。

6 結(jié)束語

本文提出一種可解釋聚類分析方法iBelt來解決過程發(fā)現(xiàn)的事件日志結(jié)構(gòu)復(fù)雜和可解釋性差的問題。該方法中定義了“過程連接帶”描述對事件日志分析的結(jié)果，并基于聚類樹思想設(shè)計了梯度提升聚類樹CLBDT模型，該模型能夠通過動態(tài)更新信息增益提高已有方法CLTree的聚類效果和擬合度，同時還能夠處理高維數(shù)據(jù)，提高模型的執(zhí)行效率。從實驗結(jié)果來看，iBelt方法成功地降低了算法的時間復(fù)雜度，找到了事件日志的過程連接帶，過程發(fā)現(xiàn)的擬合度和簡潔度均優(yōu)于基線。下一步工作主要集中在優(yōu)化構(gòu)成的特征向量，并根據(jù)特征特點優(yōu)化模型。