(山東理工大學 計算機科學與技術學院，山東 淄博 255000)

過程挖掘[1-3]旨在從事件日志中提取關于業(yè)務過程的有效信息，從而發(fā)現(xiàn)、監(jiān)控和改進實際過程。事件日志對應于業(yè)務過程的一系列過程實例，過程實例表現(xiàn)為軌跡(軌跡被定義為過程實例從開始執(zhí)行到結束所調(diào)用的活動有序列表)?，F(xiàn)實生活中的過程往往更靈活、非結構化，傳統(tǒng)的過程挖掘算法在處理這種非結構化過程時存在生成難以理解的過程模型(即意大利面模型)等問題，解決這一問題的有效方法之一是對事件日志中的軌跡進行聚類，使得聚類后的子日志對應的過程模型組合能夠清晰完整地表達原始事件日志中的行為，減少類似意大利面過程模型出現(xiàn)的概率，進而更直觀地理解過程模型。

軌跡聚類的基本原則是根據(jù)定義的軌跡之間相似或相異概念，將事件日志劃分為K個(一般K≥2)聚類子日志，使得子日志中的所有軌跡的行為(如活動、直接跟隨活動關系等)是相似的，屬于不同子日志的軌跡是不相似的。有不同的評價指標來評價軌跡聚類的效果，文獻[4]從傳統(tǒng)數(shù)據(jù)挖掘的角度使用聚類熵和分離率等指標評價聚類質(zhì)量；文獻[5]使用加權擬合度值評價聚類的好壞，采用XOR、Joins/Splits等控制流的數(shù)量評估過程模型的復雜性；文獻[6]通過計算過程模型的總體精度以及單個過程實例的擬合度進行實驗評估。從過程挖掘的角度來看，最常用的聚類評估指標是基于擬合度[7]和準確度[8]的綜合指標F-Measure[9]。不同的軌跡聚類方法所用的評價指標不盡相同，目前尚未有一個明確統(tǒng)一的標準。本研究提出一種新的基于日志相似度軌跡聚類評估方法，并與使用已有的軌跡聚類方法在真實事件日志上與傳統(tǒng)評估指標F-Measure進行對比實驗，來驗證新的聚類評估指標的可行性和高效性。

1 相關工作

本節(jié)首先介紹已有的軌跡聚類方法，如基于向量空間方法的聚類、基于上下文感知的聚類、基于模型的序列聚類等，然后從傳統(tǒng)數(shù)據(jù)挖掘角度和過程挖掘角度概述軌跡聚類質(zhì)量評估指標，最后指出已有指標存在的問題并提出一種新的軌跡聚類評估方法。

1.1 軌跡聚類方法

目前已有多種軌跡聚類方法，大多數(shù)是在數(shù)據(jù)挖掘等領域中相關聚類方法的基礎上，將事件日志進行一系列的轉換處理，然后利用現(xiàn)有的聚類算法進行聚類。例如，將事件日志轉換成向量空間模型，在每對軌跡之間定義距離度量，應用傳統(tǒng)聚類算法進行軌跡聚類；也有考慮了上下文感知方式對軌跡聚類技術進行擴展的方法；而基于模型的序列聚類技術也適用于軌跡聚類。

1) 向量空間方法。Greco等[10]是過程挖掘領域中研究事件日志軌跡聚類的先驅(qū)，使用包含活動的向量空間方法聚類事件日志中的軌跡，在聚類后的子日志中使用分離工作流模式來發(fā)現(xiàn)更簡單的過程模型。Song等[11]提出了為事件日志中的軌跡構建向量空間模型的方法，該方法基于一組配置文件，每個配置文件從一個特定的角度測量每個軌跡的多個特征，比如活動、直接跟隨活動關系、活動組織者等，這些特征組成相應的特征矩陣；基于特征矩陣，應用多個距離度量(歐式距離、漢明距離等)計算事件日志中任意兩個軌跡之間的距離；應用數(shù)據(jù)挖掘中傳統(tǒng)的聚類算法，如K-Means聚類、凝聚層次聚類等，將事件日志中的軌跡分組成子日志，這些子日志可以獨立地進行分析，從而使環(huán)境更靈活，顯著提高過程挖掘的質(zhì)量。

2) 上下文感知的軌跡聚類。文獻[5,12]中描述這一軌跡聚類技術，通過改進考慮控制流上下文感知的方式擴展了之前的軌跡聚類方法。此處的上下文感知指的是事件日志中軌跡的控制流屬性，而不是上下文信息，如組織者、案例數(shù)據(jù)等。文獻[5]提出了一種通用編輯距離技術，其中的編輯操作包括插入、刪除或替換。文獻[12]進一步發(fā)展了上下文感知軌跡聚類的思想，重新考慮了為事件日志中的軌跡生成向量空間模型這一思想，使用保守模式或子序列代替之前的活動作為向量空間模型的基礎。以這種方式，定義了極大、超極大和接近超極大重復的概念來創(chuàng)建確定某一軌跡向量的特征集。本研究中對應的軌跡聚類方法是Guide Miner Tree。

3) 基于模型的序列聚類。受到Cadez等[14]在Web使用挖掘領域的工作啟發(fā)，F(xiàn)erreira等[13]提出一種完全不同的軌跡聚類方法，通過使用期望最大化(expectation maximization,EM)算法學習混合一階馬爾可夫模型聚類軌跡。文獻[15]將這種基于模型的軌跡聚類技術應用到服務器日志中，證明了其在現(xiàn)實生活中的可用性。文獻[6]提出在給定數(shù)量的集群上執(zhí)行軌跡尋找最優(yōu)分布的問題，從而最大化關聯(lián)過程模型的組合精度；改變了傳統(tǒng)軌跡聚類的目標，即通過將相似軌跡分在一組來尋找最優(yōu)軌跡分布，提出一種自上而下的貪婪算法，通過對軌跡進行分組來計算，軌跡選擇的標準不是基于相似的行為，而是因其很好地適合特定的過程模型。在本研究中對應的軌跡聚類方法是ActiTrac。

1.2 軌跡聚類質(zhì)量評估指標

1) 數(shù)據(jù)挖掘角度。文獻[4]從數(shù)據(jù)挖掘的角度使用聚類熵和分離率作為評價聚類效果的指標。但此軌跡聚類質(zhì)量度量有一個缺點，即如果事先不了解一些預先信息，如劃分幾個類以及哪些軌跡屬于哪個類等，那么此質(zhì)量評估指標是不可行的。如果有預先的信息可用，則可以使用純度、聚類熵等傳統(tǒng)聚類評估指標量化某項技術區(qū)分不同類別行為的能力。

2) 過程挖掘角度。從過程挖掘角度的量化軌跡聚類質(zhì)量有很多的評估指標。文獻[5]中使用了加權擬合度值作為軌跡聚類評估指標，使用XOR、Joins/Splits等控制流結構數(shù)量描述過程模型的復雜性；文獻[6]通過計算過程模型的總體精度以及單個過程實例的擬合度對聚類后的過程模型進行評估。

1.3 現(xiàn)存挑戰(zhàn)

在傳統(tǒng)的數(shù)據(jù)挖掘領域，通常使用純度、聚類熵等聚類指標衡量一個軌跡聚類方法的質(zhì)量，在過程挖掘領域則使用基于擬合度、精確度的綜合指標F-Measure衡量軌跡聚類效果。然而，這些方法在進行實驗評估時往往需要花費大量的時間，評估效率低下，而且評估過程復雜繁瑣，不具有簡潔性和高效性。因此，本研究提出一種基于日志相似度的軌跡聚類評估方法，能確保評估實驗結果正確的前提下，極大地提高評估效率，為量化軌跡聚類方法的質(zhì)量提供一種新的評估標準。

2 基于日志相似度的軌跡聚類評估方法

圖2 基于日志相似度的軌跡聚類評估框架

傳統(tǒng)的軌跡聚類評估技術框架分為兩個階段，如圖1所示。第1階段通過已有的軌跡聚類技術將原始日志進行聚類，生成幾個子日志；第2階段將這幾個子日志分別通過同一過程挖掘算法得到的過程模型與原始日志做質(zhì)量評估，由F-Measure指標進行量化。

本研究提出一種基于日志相似度的軌跡聚類評估方法，相應的評估框架見圖2，包含兩個階段：①軌跡聚類。首先采用已有的軌跡聚類方法如K-Means聚類、凝聚層次聚類等，對原始日志進行聚類處理后得到幾個子日志，使得屬于同一子日志中的軌跡是相似的，屬于不同子日志的軌跡是相異的。該階段需要預先設定參數(shù)比如聚類的個數(shù)等，而參數(shù)設置不同會影響最終的評估質(zhì)量；②質(zhì)量評估。一般來說，好的聚類效果是日志內(nèi)相似、日志間相異。根據(jù)這一思想，兩兩比較子日志的相似度來說明軌跡聚類的效果，將平均相似度值作為評估軌跡聚類的結果。兩個子日志之間的相似度越高，說明兩個日志中的行為(如活動，直接跟隨活動關系等)重合度越高，表明此軌跡聚類方法得到的結果越差；兩個日志之間的相似度越小，說明兩個日志中存在較大差異性，表明此軌跡聚類方法的效果就越好。

本節(jié)介紹兩種測量日志相似度的方法：余弦相似度和EMD相似度，通過這兩種日志相似度的度量來評價軌跡聚類方法得到的日志質(zhì)量。

2.1 余弦相似度

余弦相似度[16]通過計算事件日志對應矩陣展開行向量的夾角余弦值來計算相似度。在此過程中，將兩個事件日志對應的矩陣表示為行向量的形式，通過一一比較對應行向量的余弦相似度，再對其求平均值，得到的最終相似度即為兩日志的相似度。余弦相似度表示為

(1)

其中，X、Y分別為兩日志生成矩陣對應的行向量。兩個日志對應的生成矩陣的余弦相似度越小，說明兩個日志的相似程度越接近，得到的樣本日志的質(zhì)量就越好。余弦相似度的取值在0到1之間。

2.2 EMD相似度

EMD(earth movers′ distance)[17]是一種在特定區(qū)域兩個概率分布距離的度量。通俗來講，如果兩個分布被看作是在特定區(qū)域上兩種不同方式堆積一定數(shù)量的土堆，那么EMD就是把一堆變成另一堆所需要移動單位的最小距離之和。

首先引入重新分配函數(shù)的概念來說明一種隨機語言如何轉化為另一種隨機語言，再引入一個距離函數(shù)來表達將一個軌跡轉換成另一個軌跡的代價，然后引入一個代價函數(shù)來表達一個特定的再分配函數(shù)的代價，最后定義EMD的隨機一致性度量。

重新分配函數(shù)表示概率質(zhì)量在兩種隨機語言之間的運動。設L和M是隨機語言，一個重新分配函數(shù)r:L×M→[0，1]描述了L如何轉化為M，即r(t,t′)描述了t∈L轉移到t′∈M的概率。

為了確保重新分配函數(shù)正確地將L轉換為M，應該考慮每個t∈L的概率質(zhì)量。因此，t的行之和等于L(t)，即有

(2)

同樣，軌跡t′∈M的質(zhì)量也要保留：

(3)

將符合式(2)和(3)的所有重新分配函數(shù)的集合稱為R(注意，R取決于L和M)。

例如，考慮隨機語言Le=[〈a〉0.25,〈a,a〉0.75]和Me=[〈a〉0.5,〈a,a〉0.25,〈a,a,a〉0.125,〈a,a,a,a〉0.0625,…]。重新分配函數(shù)re的一個例子如表1所示。

表1 重新分配函數(shù)reTab. 1 Reallocation function re

表1中，式(2)規(guī)定每行的總和應該等于隨機語言Le中的相應值(例如，第1行的總和等于1/4，即Le(〈a〉)=1/4)。類似地，式(3)表示每一列應該加起來是Me中對應的概率質(zhì)量。

距離函數(shù)d表示軌跡之間的距離，這里使用的是編輯距離[5]。

例如，考慮上述隨機語言Le和Me，標準化編輯距離函數(shù)dl如表2所示。

代價函數(shù)。給定兩種隨機語言，可能存在多種重新分配函數(shù)，EMD為兩種隨機語言之間的最短距離，即在軌跡之間的最小距離上以最小概率質(zhì)量運動。使用重新分配函數(shù)r將隨機語言L轉換為隨機語言M的代價是重新分配函數(shù)和距離函數(shù)的內(nèi)積，代價函數(shù)的計算公式為：

(4)

表2 標準化編輯距離函數(shù)dlTab. 2 The normalised Levenshtein distance function dl

例如，考慮上述隨機語言Le和Me，成本函數(shù)為

(5)

EMD的隨機一致性即EMSC。給定L和M，EMSC被定義為任何重新分配函數(shù)r的最低代價，即：

(6)

EMSC的值為1表示完美一致性，0表示最差一致性。

在例子中，re是最優(yōu)的重新分配函數(shù)，因此EMSC(Le,Me) ≈0.761 294。

值得注意的是，重新分配函數(shù)可能存在多種，要確定一個最優(yōu)的重新分配函數(shù)可以通過線性規(guī)劃來實現(xiàn)。為了找到具有最低代價的最優(yōu)分配函數(shù)，選擇式(4)作為目標函數(shù)，約束通過式(2)和式(3)來確定。比如，考慮上述隨機語言Le和Me，線性規(guī)劃的問題構造如下：

…

…

可以用上述EMD相似度的方法量化兩個事件日志的相似程度，EMD越大，說明兩日志的相似程度越高。

3 實驗分析

首先介紹實驗環(huán)境和實驗日志的基本信息，然后對不同的聚類方法在不同的聚類個數(shù)下得到的聚類子日志進行質(zhì)量評估，對比傳統(tǒng)指標F-Measure和日志相似度指標的趨勢，說明本研究提出指標的可行性；對比兩個指標的評估時間說明日志相似度指標的高效性。

3.1 實驗設置及數(shù)據(jù)集

實驗均基于PC Intel Core i5-4210M 2.60GHz CPU，12GB RAM環(huán)境，使用Java語言實現(xiàn)，詳細代碼見https://svn.win.tue.nl/repos/prom/Packages/ShandongPM。使用4個真實事件日志對所提出的日志相似度的軌跡聚類評估方法進行實驗評估，表4說明了這些事件日志的部分主要統(tǒng)計數(shù)據(jù)，所用的實驗數(shù)據(jù)集鏈接見https://data.4tu.nl。

1) Sepsis數(shù)據(jù)集：來自醫(yī)院的膿毒癥病例事件，每1條軌跡代表1個膿毒癥患者的治療過程；

2) Helpdesk數(shù)據(jù)集：來自意大利軟件公司服務臺票務管理過程，每1條軌跡代表1個票證的處理過程；

3) BPI2012_O數(shù)據(jù)集：源自荷蘭1家金融機構的個人貸款申請過程，每1條軌跡描述了不同客戶申請個人貸款的過程；

4) BPI2015_3數(shù)據(jù)集：由荷蘭城市市政當局提供的所有建筑許可證申請，期限約為4年，選取了其中一部分數(shù)據(jù)進行處理。

3.2 實驗結果分析

從評估指標結果和評估效率兩方面出發(fā)，在實驗數(shù)據(jù)集上將傳統(tǒng)指標F-Measure與本研究提出的日志相似度指標(余弦相似度和EMD相似度)進行對比，說明基于日志相似度評估指標的可行性和高效性。

測量傳統(tǒng)評估指標F-Measure的具體做法如下：先通過軌跡聚類方法(選擇的是ActiTrac聚類和Guide

表3 實驗日志概述

Miner Tree聚類)將原始實驗日志在不同的聚類個數(shù)(此處用K表示，取值為3，4，5，6)下進行聚類得到幾個子日志，然后將每個子日志通過過程挖掘算法(選擇的是Inductive Miner[18]算法)生成過程模型，再將每個過程模型與原始實驗日志做合規(guī)性檢查，得到基于擬合度、準確度的綜合指標F-Measure，最后將得到的各個F-Measure平均后的結果作為此軌跡聚類方法在選定K值上的傳統(tǒng)評估指標量化值。

F-measure值被定義為擬合度和精確度的調(diào)和平均值，具體計算公式為：

(7)

其中：fitness(L,M)為從樣本日志中發(fā)現(xiàn)的過程模型相對于原始日志的擬合度，表示量化過程模型再現(xiàn)事件日志中記錄軌跡的準確程度和記錄軌跡的能力，值為1表示過程模型可以重新生成事件日志中的所有軌跡，低擬合度表明事件日志中的大部分行為不能被過程模型重演；precision(L,M)為從樣本日志中發(fā)現(xiàn)的過程模型相對于原始日志的精確度，量化在過程模型中能夠重演但在事件日志中看不到的部分行為和生成事件日志中記錄軌跡的能力，值為1表示過程模型生成的所有軌跡都包含在事件日志中，低精確度意味著過程模型允許事件日志外更多的行為。

基于日志相似度的評估方法過程如下：先通過軌跡聚類算法(同上)將原始實驗日志在不同的聚類個數(shù)(同上)下進行軌跡聚類得到聚類后的子日志，然后將子日志通過基于日志相似度評估方法(本次實驗選擇為余弦相似度和EMD相似度)兩兩計算相似度，最后將各個相似度平均后結果作為此聚類算法在選定K值上的日志相似度評估指標量化值。

3.2.1 評估指標對比

好的聚類結果標準是日志內(nèi)相似，日志間相異，故兩兩日志之間的相似程度越低，說明聚類的效果越好；F-Measure越高，說明聚類的效果越好。由此可見，日志相似度指標與傳統(tǒng)指標F-Measure呈負相關。在4個數(shù)據(jù)集上的實驗結果如圖3所示。

由圖3可見，傳統(tǒng)指標F-Measure值與基于日志相似度的兩個指標(余弦相似度和EMD相似度)呈負相關關系。以Sepsis日志(聚類方法為ActiTrac)為例，在不同的聚類個數(shù)設置下，隨著聚類個數(shù)的增大，F(xiàn)-Measure值逐漸降低，而基于日志相似度的指標(余弦相似度和EMD相似度)逐漸升高，兩者呈現(xiàn)出相反的趨勢，這與之前分析的結論是一致的。因此，本研究提出的日志相似度評估指標適用于軌跡聚類方法評估，完全可以代替?zhèn)鹘y(tǒng)評估指標進行評估測量。

值得注意的是，本研究的余弦相似度、EMD相似度這兩個指標在不同的日志中有所差異，比如在BPI2015_3日志、ActiTrac聚類中，隨著聚類個數(shù)的增加，余弦相似度值的范圍在0.1～0.2，EMD相似度值的范圍在0.25～0.4；而在Guide Miner Tree聚類中，余弦相似度值與EMD相似度值的范圍在0.15～0.3，相差不大。由此可以看出，兩個相似度指標之間可能存在差異，這是由于不同指標間的計算方式不同引起的，但兩者總是表現(xiàn)出與傳統(tǒng)指標F-Measure相反的趨勢。

3.2.2 時間性能對比

圖4為本文傳統(tǒng)評估指標與基于日志相似度評估指標的時間對比圖。對于傳統(tǒng)的F-Measure指標，測量時間包括樣本日志通過挖掘算法生成過程模型的時間及過程模型與原始事件日志的擬合度、精確度的綜合指標F-Measure的評估時間；對于基于日志相似度的評估方法，計算聚類子日志之間日志相似度度量時間。

由圖4可以看出，在真實事件日志上，基于日志相似度的評估指標所用時間遠遠小于傳統(tǒng)評估指標F-Measure，說明基于日志相似度的評估指標具有高效性。以Helpdesk日志(聚類方法為ActiTrac，聚類個數(shù)為6)為例，傳統(tǒng)評估指標F-Measure值所用時間為4 179 ms,而余弦相似度評估指標僅花費了56 ms，在時間性能上提升了80倍，EMD相似度用時127 ms,相比于F-Measure指標提升了33倍。由此可見，基于日志相似度的評估方法能有效地縮短日志評估所用的時間，提高了評估效率。

圖3 評估指標對比

圖4 評估時間對比

4 結論

本研究提供了一種基于日志相似度的軌跡聚類評估方法，為衡量軌跡聚類方法提供了一種新的評估指標，相比于傳統(tǒng)的聚類評估指標，該評估指標在保證聚類評估結果正確性的同時，可以更高效地對聚類子日志進行實驗評估。

未來可以從如下3方面繼續(xù)深入研究：將基于日志相似度的軌跡聚類評估方法應用到專門領域(如醫(yī)療、物流、制造業(yè)等)的事件日志；嘗試更多的軌跡聚類方法與評估指標對比基于日志相似度軌跡聚類評估方法的魯棒性；除余弦相似度和EMD相似度等日志相似度指標外，探究更多的日志相似度評估指標。