iBelt：一種事件日志的可解釋聚類分析方法

劉 雯，王桂玲+

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

0 引言

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

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

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

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

1 相關(guān)概念

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

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

表1 某事件日志片段

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

復(fù)雜事件日志提取特征向量時(shí)很容易因維數(shù)過高而造成“維數(shù)災(zāi)難”，而且會(huì)使可解釋性算法生成復(fù)雜的解釋規(guī)則而降低用戶的可讀性。針對(duì)決策樹的降維問題，倪春鵬[13]通過比較條件屬性相對(duì)于劃分類別的重要性來決定保留哪些屬性參與建立決策樹，其改進(jìn)的決策樹降維方法是有監(jiān)督的特征選擇方法，而真實(shí)的事件日志往往無法準(zhǔn)確得到條件屬性；王偉[14]將原始數(shù)據(jù)空間轉(zhuǎn)換到主成分空間，利用主成分分析算法的思想改進(jìn)了傳統(tǒng)決策樹的C4.5算法，但是破壞了特征數(shù)據(jù)本身的可解釋性。無監(jiān)督的特征選擇方法能夠在很大程度上保留特征數(shù)據(jù)本身的可解釋性，其中無監(jiān)督的最大方差選擇方法[15]以特征數(shù)據(jù)的最大方差為評(píng)價(jià)標(biāo)準(zhǔn)，按照其特征重要性排序進(jìn)行選擇；無監(jiān)督的拉普拉斯特征選擇方法[16]在最大方差的基礎(chǔ)上引入數(shù)據(jù)的局部結(jié)構(gòu)進(jìn)行分析。然而，這兩種方法僅考慮數(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 基本思想

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

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

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

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

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

3.2 方法流程

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

3.3 特征提取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

(4)

更新后的新信息增益

(5)

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

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

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

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

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

2) Repeat:

3) get_GainRes(gainRes)

4) buildTree(Tree) ：

5) calculate_Gain(newGain)

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

7) 返回第M棵樹

3.4.3 尋找聚類樹的最佳分割點(diǎn)

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

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

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

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

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

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

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

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

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

4.2 評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

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

(6)

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

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

(7)

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

4.3 實(shí)驗(yàn)過程

4.3.1 特征提取結(jié)果

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

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

4.3.2 方法結(jié)果分析

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

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

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

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

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

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

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

聚類結(jié)果的3個(gè)簇對(duì)應(yīng)3個(gè)過程連接帶(B1,B2,B3)，其軌跡組合分別為(T1,T2,T3)。第1個(gè)過程連接帶B1的軌跡組合T1共有9 775條軌跡，第2個(gè)過程連接帶B2的軌跡組合T2共有133條軌跡，第3個(gè)過程連接帶B3的軌跡組合T3共有161條軌跡，案例軌跡點(diǎn)最多的連接帶軌跡組合為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活動(dòng)必然發(fā)生1次，活動(dòng)特征Declaration APPROVED by ADMINISTRATION在3個(gè)過程連接帶中的取值范圍各不相同，其中B1∈[0,1]，B2∈[1,1]，B3∈[2,2]。

表7 DomesticDeclarations的過程連接帶

4.4.2 聚類評(píng)價(jià)指標(biāo)分析

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

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

續(xù)表8

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

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

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

續(xù)表9

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

6 結(jié)束語(yǔ)

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