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

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255000)

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

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

1 相關(guān)工作

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

1.1 軌跡聚類方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 余弦相似度

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

(1)

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

2.2 EMD相似度

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

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

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

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

(2)

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

(3)

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

例如，考慮隨機(jī)語言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ī)定每行的總和應(yīng)該等于隨機(jī)語言Le中的相應(yīng)值(例如，第1行的總和等于1/4，即Le(〈a〉)=1/4)。類似地，式(3)表示每一列應(yīng)該加起來是Me中對應(yīng)的概率質(zhì)量。

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

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

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

(4)

表2 標(biāo)準(zhǔn)化編輯距離函數(shù)dlTab. 2 The normalised Levenshtein distance function dl

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

(5)

EMD的隨機(jī)一致性即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ī)劃來實(shí)現(xiàn)。為了找到具有最低代價的最優(yōu)分配函數(shù)，選擇式(4)作為目標(biāo)函數(shù)，約束通過式(2)和式(3)來確定。比如，考慮上述隨機(jī)語言Le和Me，線性規(guī)劃的問題構(gòu)造如下：

…

…

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

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

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

3.1 實(shí)驗(yàn)設(shè)置及數(shù)據(jù)集

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

表3 實(shí)驗(yàn)日志概述

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

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

(7)

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

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

3.2.1 評估指標(biāo)對比

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

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

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

3.2.2 時間性能對比

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

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

圖3 評估指標(biāo)對比

圖4 評估時間對比

4 結(jié)論

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

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