徐　濤　孟　野　盧　敏（中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　天津　300300）（中國(guó)民航信息技術(shù)科研基地　天津　300300）

?

基于RankClus算法的機(jī)場(chǎng)流程日志活動(dòng)挖掘

徐濤①②孟野*①盧敏①②①
①（中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院天津300300）
②（中國(guó)民航信息技術(shù)科研基地天津300300）

流程挖掘技術(shù)可以提取機(jī)場(chǎng)流程日志中的有用信息用于流程分析。但機(jī)場(chǎng)流程日志處于細(xì)節(jié)化的低抽象層次，不符合分析者的預(yù)期。對(duì)機(jī)場(chǎng)流程日志挖掘得到的流程模型呈現(xiàn)意面狀的復(fù)雜結(jié)構(gòu)，流程模型的含義難于理解。解決該問(wèn)題的一種方法是通過(guò)活動(dòng)挖掘，將低抽象層次活動(dòng)聚類為流程模型中表征高抽象層次活動(dòng)的活動(dòng)類簇。為此提出了一種基于RankC lus算法的活動(dòng)挖掘方法，將機(jī)場(chǎng)流程日志的活動(dòng)聚類與活動(dòng)排序評(píng)分計(jì)算相結(jié)合，從而構(gòu)建更易理解的活動(dòng)聚類流程模型。實(shí)驗(yàn)結(jié)果表明，RankClus活動(dòng)聚類流程模型的日志回放一致性與原生日志流程模型大致相當(dāng)，但在結(jié)構(gòu)復(fù)雜度上要顯著低于原生日志流程模型。

流程挖掘；活動(dòng)挖掘；RankClus；蹤跡聚類

1　　引言

機(jī)場(chǎng)運(yùn)行過(guò)程中時(shí)刻有各類事件發(fā)生，機(jī)場(chǎng)業(yè)務(wù)信息系統(tǒng)隨之生成一系列機(jī)場(chǎng)流程日志。對(duì)機(jī)場(chǎng)流程日志進(jìn)行流程挖掘可得到相應(yīng)的業(yè)務(wù)流程模型［1］，借由業(yè)務(wù)流程模型指導(dǎo)，機(jī)場(chǎng)可開(kāi)展運(yùn)行決策支持［2］及業(yè)務(wù)趨勢(shì)預(yù)測(cè)［3］等一系列工作以提高機(jī)場(chǎng)運(yùn)行效率。因此機(jī)場(chǎng)流程日志的流程挖掘具有重要意義。

流程挖掘研究通常將流程日志羅列為活動(dòng)組成的蹤跡（trace），構(gòu)建目標(biāo)日志流程模型并分析。流程挖掘研究主要分3個(gè)方向［1］：（1）流程發(fā)現(xiàn)：在無(wú)先驗(yàn)知識(shí)指導(dǎo)下建立流程日志的流程模型；（2）一致性檢測(cè)：對(duì)比已有流程模型與真實(shí)情況以驗(yàn)證模型合理性，常用日志回放實(shí)現(xiàn)；（3）模型增強(qiáng)：根據(jù)所觀測(cè)事件信息擴(kuò)展業(yè)務(wù)流程模型。國(guó)內(nèi)機(jī)場(chǎng)流程日志中活動(dòng)以工作人員上傳的文本描述為主，抽象層次（abstract level）較低。直接對(duì)這類日志進(jìn)行流程發(fā)現(xiàn)時(shí)，得到的流程模型結(jié)構(gòu)復(fù)雜且難以理解。文獻(xiàn)［4］提出一種基于全局蹤跡分割的活動(dòng)挖掘方法，該方法設(shè)定時(shí)間窗口對(duì)鄰近活動(dòng)進(jìn)行層次聚類。但僅考慮事件間的時(shí)間鄰近度，其聚類結(jié)果不能很好反映領(lǐng)域知識(shí)。文獻(xiàn)［5］采用領(lǐng)域?qū)＜沂止?biāo)記方式為流程日志添加活動(dòng)類標(biāo)簽，并用標(biāo)記日志訓(xùn)練活動(dòng)描述的文本分類器，再對(duì)活動(dòng)分類。該方式所得活動(dòng)類別較為細(xì)碎，專家標(biāo)記的主觀誤差對(duì)結(jié)果影響較大。文獻(xiàn)［6］假設(shè)事件與活動(dòng)間存在一對(duì)多或多對(duì)多關(guān)系，采用詞干提取等文本挖掘技術(shù)挖掘日志文本描述中的領(lǐng)域知識(shí)，將所得知識(shí)用于匹配事件與活動(dòng)以合理定位流程日志抽象層次。該方法在中文流程日志中實(shí)現(xiàn)較困難。

本文構(gòu)建二類型網(wǎng)絡(luò)（bi-type network）描述活動(dòng)與蹤跡關(guān)系，視活動(dòng)與蹤跡為不同類型結(jié)點(diǎn)，用活動(dòng)在各蹤跡結(jié)點(diǎn)類簇的排序評(píng)分向量量化表示活動(dòng)，為此需得到合理蹤跡聚類結(jié)果以計(jì)算該排序評(píng)分。文獻(xiàn)［7-9］的蹤跡聚類方法難用于蹤跡聚類的活動(dòng)排序評(píng)分計(jì)算，不能很好銜接后續(xù)活動(dòng)聚類工作。文獻(xiàn)［10］提出有效結(jié)合聚類和排序的RankClus算法。該算法主要功能是對(duì)二類型網(wǎng)絡(luò)排序與聚類。應(yīng)用在機(jī)場(chǎng)流程日志活動(dòng)挖掘能夠得到較準(zhǔn)確的蹤跡結(jié)點(diǎn)劃分結(jié)果，并計(jì)算出活動(dòng)結(jié)點(diǎn)在蹤跡劃分生成子網(wǎng)絡(luò)的排序評(píng)分。在RankClus算法基礎(chǔ)上，本文將蹤跡聚類與活動(dòng)聚類相結(jié)合，設(shè)計(jì)機(jī)場(chǎng)流程日志低抽象層次活動(dòng)的聚類算法，使基于聚類結(jié)果挖掘所得日志流程模型在保持一定日志重現(xiàn)度的同時(shí)，有效降低流程模型的結(jié)構(gòu)復(fù)雜度。

2　　機(jī)場(chǎng)流程日志活動(dòng)挖掘分析

機(jī)場(chǎng)流程日志的流程挖掘主要關(guān)注提交時(shí)間、部門(mén)、模塊、活動(dòng)、實(shí)例號(hào)等屬性。表1是國(guó)內(nèi)某機(jī)場(chǎng)的部分流程日志，類似“新增要客航班：HU7703，CA 1321?！?，“要客航班更新：CA947，請(qǐng)各單位加強(qiáng)關(guān)注?！被顒?dòng)描述的事件大量存在，這類事件可統(tǒng)一視為“要客航班更新”。但流程挖掘時(shí)低抽象層次事件與活動(dòng)間一對(duì)一映射的關(guān)系［11］及復(fù)雜的活動(dòng)描述語(yǔ)義，使數(shù)據(jù)預(yù)處理合并事件的做法難以實(shí)現(xiàn)，挖掘到的流程模型充斥大量低抽象層次活動(dòng)。為此需將低抽象層次事件通過(guò)聚類方式抽象為高抽象層次的活動(dòng)類簇。將“新增”、“更新”等活動(dòng)描述標(biāo)識(shí)的事件聚類為表示“要客航班更新”的活動(dòng)類簇以簡(jiǎn)化流程模型結(jié)構(gòu)。

可將表1中390962號(hào)實(shí)例與390963號(hào)實(shí)例分別表示為蹤跡＜A，C，D，E，F(xiàn)＞與蹤跡＜B，C，D，E，F(xiàn)＞。若將這兩條業(yè)務(wù)響應(yīng)［12］類似的蹤跡聚為一類，形如“新增要客航班”、“要客航班更新”的活動(dòng)便出現(xiàn)于同類?ài)欅E中?；顒?dòng)即可表示為在不同類?ài)欅E中的分布情況。表2的日志結(jié)構(gòu)分析表明機(jī)場(chǎng)流程日志活動(dòng)有較高的絕對(duì)數(shù)目與事件記錄占比，大量低抽象層次活動(dòng)使流程模型結(jié)構(gòu)呈“意面狀”（Spaghettilike）［4］。以模塊或其他屬性構(gòu)建蹤跡可簡(jiǎn)化所發(fā)現(xiàn)流程模型的結(jié)構(gòu)，但造成模型抽象層次過(guò)高，僅能反映“當(dāng)前部門(mén)開(kāi)展了某項(xiàng)活動(dòng)”這類不具體的活動(dòng)語(yǔ)義，模型丟失大量信息。因此聚類時(shí)需為活動(dòng)指定介于兩者間的抽象層次。

可構(gòu)造如圖1所示的二類型網(wǎng)絡(luò)描述活動(dòng)與蹤跡間關(guān)系，并區(qū)分網(wǎng)絡(luò)中活動(dòng)在各類?ài)欅E中重要度以聚類相似的低抽象層次活動(dòng)。用高抽象層次活動(dòng)類簇替代原日志活動(dòng)，構(gòu)建蹤跡集合。該網(wǎng)絡(luò)由活動(dòng)結(jié)點(diǎn)與蹤跡結(jié)點(diǎn)組成，網(wǎng)絡(luò)的實(shí)線視為該活動(dòng)在蹤跡中出現(xiàn)了一次，虛線則表示結(jié)點(diǎn)間存在相似性。采用二類型網(wǎng)絡(luò)來(lái)描述活動(dòng)與蹤跡間的關(guān)系，使得流程日志活動(dòng)挖掘問(wèn)題轉(zhuǎn)變?yōu)榫垲惗愋途W(wǎng)絡(luò)活動(dòng)結(jié)點(diǎn)的問(wèn)題［13，14］。

表1　 國(guó)內(nèi)某大型樞紐機(jī)場(chǎng)部分流程日志

表2　 國(guó)內(nèi)某大型樞紐機(jī)場(chǎng)2013年流程日志結(jié)構(gòu)分析

圖1　 活動(dòng)與蹤跡的二類型網(wǎng)絡(luò)

3　　基于RankClus的機(jī)場(chǎng)流程日志活動(dòng)挖掘算法

3.1 RankClus混合模型

為聚類活動(dòng)與蹤跡的二類型網(wǎng)絡(luò)中的活動(dòng)結(jié)點(diǎn)，需劃分蹤跡結(jié)點(diǎn)，將活動(dòng)結(jié)點(diǎn)表示為在各類?ài)欅E上的重要度排序評(píng)分的評(píng)分向量。為獲取蹤跡結(jié)點(diǎn)的合理劃分結(jié)果，可引入RankC lus算法的混合模型（m ixture m odel），通過(guò)模型參數(shù)估計(jì)得到的蹤跡結(jié)點(diǎn)表示向量，對(duì)蹤跡結(jié)點(diǎn)進(jìn)行劃分。以機(jī)場(chǎng)流程日志活動(dòng)-蹤跡二類型網(wǎng)絡(luò)為例，X表示機(jī)場(chǎng)日志蹤跡結(jié)點(diǎn)集合，Y表示機(jī)場(chǎng)低抽象層次活動(dòng)結(jié)點(diǎn)集合，則可表示機(jī)場(chǎng)日志蹤跡結(jié)點(diǎn)與機(jī)場(chǎng)低抽象層次活動(dòng)構(gòu)成的二類型網(wǎng)絡(luò)，W為網(wǎng)絡(luò)的鄰接矩陣，分塊可得：

將ix與Y中結(jié)點(diǎn)有邊相連的概率表示為則X中的所有結(jié)點(diǎn)ix（1，i= 2，，）m…均滿足這一分布。記，ikπ為ix屬于第k類的后驗(yàn)概率，可對(duì)p（Y|xi）建立如式（2）的RankClus混合模型：

3.2 排序評(píng)分的計(jì)算

rX'=rX'|X'為對(duì)X聚類時(shí)X'的類內(nèi)排序評(píng)分，為對(duì)X聚類時(shí)Y的條件排序評(píng)分，分別反映一類相似蹤跡中某蹤跡出現(xiàn)頻繁程度和各活動(dòng)參與情況。rX|X'為rY|X'在網(wǎng)絡(luò)G上所得傳遞得分，可定義為

3.3 聚類中心和距離的計(jì)算

每個(gè)ix對(duì)應(yīng)一K維向量如令則每個(gè)jy可對(duì)應(yīng)一K維向量；計(jì)算X類簇或Y類簇中所有結(jié)點(diǎn)對(duì)應(yīng)向量的平均值，得到每個(gè)類簇的類簇中心：

3.4 算法流程

文獻(xiàn)［10］為控制聚類數(shù)及得到更具意義聚類結(jié)果，指定算法聚類結(jié)點(diǎn)數(shù)較少類型的結(jié)點(diǎn)，未提供聚類網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)較多類型結(jié)點(diǎn)的相應(yīng)解決方案，不能直接聚類多于蹤跡的活動(dòng)。表3算法流程輸出準(zhǔn)確的基于蹤跡聚類的流程日志活動(dòng)排序評(píng)分后繼續(xù)迭代計(jì)算活動(dòng)排序評(píng)分。這一評(píng)分可為活動(dòng)聚類提供足夠信息。

4　　實(shí)驗(yàn)與分析

對(duì)原生日志添加活動(dòng)聚類標(biāo)簽后，可生成活動(dòng)聚類流程日志 （activity-clustered event log） 挖掘流程模型。比對(duì)各流程模型的日志重現(xiàn)度以驗(yàn)證聚類結(jié)果合理性；分析各流程模型的結(jié)構(gòu)復(fù)雜度以驗(yàn)證活動(dòng)聚類日志能在保持回放準(zhǔn)確度的同時(shí)有效降低模型結(jié)構(gòu)復(fù)雜度。本文實(shí)驗(yàn)數(shù)據(jù)集為表2中3組不同時(shí)間區(qū)間的流程日志，并選用文獻(xiàn)［15］的Inductive M iner方法挖掘流程日志的Petri網(wǎng)流程模型，噪聲參數(shù)設(shè)置為0.1。

4.1 機(jī)場(chǎng)流程日志活動(dòng)聚類實(shí)驗(yàn)

機(jī)場(chǎng)等大型機(jī)構(gòu)數(shù)據(jù)聚類分析的參數(shù)設(shè)定多依賴于領(lǐng)域?qū)＜抑R(shí)［16］。結(jié)合機(jī)場(chǎng)運(yùn)行專家知識(shí)［16，17］及數(shù)據(jù)源機(jī)場(chǎng)實(shí)際運(yùn)行情況歸納得15類業(yè)務(wù)流程及20類業(yè)務(wù)活動(dòng)，分別作為蹤跡結(jié)點(diǎn)聚類數(shù)與活動(dòng)結(jié)點(diǎn)聚類數(shù)。文獻(xiàn)［4］總結(jié)低抽象層次活動(dòng)與業(yè)務(wù)流程間關(guān)系為兩類：（1）業(yè)務(wù)流程由被單一活動(dòng)類簇覆蓋的低抽象層次活動(dòng)組成；（2）業(yè)務(wù)流程由分散在不同活動(dòng)類簇中的低抽象層次活動(dòng)組成。圖2是算法穩(wěn)定時(shí)蹤跡結(jié)點(diǎn)各類簇的活動(dòng)結(jié)點(diǎn)評(píng)分，圖3是活動(dòng)結(jié)點(diǎn)聚類結(jié)果。數(shù)據(jù)集1結(jié)點(diǎn)數(shù)最多的類簇15主要為重點(diǎn)保障航班保障活動(dòng)，活動(dòng)描述以“CZ390有旅客要下機(jī)，需客梯車到現(xiàn)場(chǎng)?！?、“MU5714航班滑回，需客梯車?！钡染佣?。數(shù)據(jù)集2活動(dòng)結(jié)點(diǎn)數(shù)最多的類簇2主要由活動(dòng)描述為“安保公司收到，轉(zhuǎn)飛行區(qū)安檢部。”的機(jī)場(chǎng)安檢公司業(yè)務(wù)響應(yīng)活動(dòng)組成。這些同類簇的低抽象層次活動(dòng)間有較強(qiáng)相關(guān)性且滿足第1類關(guān)系，直接分析原生日志流程模型也能得到類似結(jié)果。

數(shù)據(jù)集3活動(dòng)結(jié)點(diǎn)較多的類簇為1， 11， 12。類簇12的活動(dòng)描述以航班計(jì)劃、共享航班等信息更新活動(dòng)為主，活動(dòng)間關(guān)系與數(shù)據(jù)集1的類簇15、數(shù)據(jù)集2的類簇2相似。類簇1與類簇11的活動(dòng)描述由機(jī)場(chǎng)地服公司開(kāi)展的業(yè)務(wù)活動(dòng)組成，但側(cè)重不同；類簇1與數(shù)據(jù)集1中類簇4的活動(dòng)結(jié)點(diǎn)描述相仿，側(cè)重于機(jī)位作業(yè)業(yè)務(wù)，而類簇11則側(cè)重于開(kāi)展重點(diǎn)航班保障相關(guān)活動(dòng)。類簇1與類簇11的低抽象層次活動(dòng)間相關(guān)性較弱，直接分析原生日志流程模型易混淆這兩類低抽象層次活動(dòng)，影響流程發(fā)現(xiàn)準(zhǔn)確性。只有通過(guò)活動(dòng)聚類結(jié)果反映低抽象層次活動(dòng)與業(yè)務(wù)流程的第2類關(guān)系，才可合理地區(qū)分低抽象層次活動(dòng)。

表3　 基于RankClus算法的流程日志活動(dòng)挖掘算法流程

4.2 機(jī)場(chǎng)流程日志一致性檢測(cè)實(shí)驗(yàn)

日志回放含3種情況［1］：（1）流程模型活動(dòng)與當(dāng)前蹤跡活動(dòng)匹配；（2）蹤跡中活動(dòng)與流程模型活動(dòng)不匹配，模型預(yù)期活動(dòng)未在蹤跡中觀測(cè)到時(shí)，回放算法可不移動(dòng)蹤跡中活動(dòng)，前移流程模型中活動(dòng)以進(jìn)行匹配；（3）蹤跡中活動(dòng)與流程模型活動(dòng)不匹配時(shí)，回放算法可不移動(dòng)流程模型中活動(dòng)，前移蹤跡中活動(dòng)以進(jìn)行匹配。上述3種情況的日志回放準(zhǔn)確度分別對(duì)應(yīng)蹤跡重現(xiàn)度（trace fitness）、模型移動(dòng)重現(xiàn)度（move-model fitness）和日志移動(dòng)重現(xiàn)度（move-log fitness） 3項(xiàng)指標(biāo)，取值范圍均為0到1。為1時(shí)意味著該情況下模型可完全回放日志。日志回放選用文獻(xiàn)［18］基于代價(jià)的A*算法。采用文獻(xiàn)［17］中基于離散實(shí)例仿真系統(tǒng)分析的DTW （Dynam ic T im e Warping）聚類算法作為對(duì)比算法。該方法運(yùn)用離散實(shí)例仿真（Discrete Event Simulation， DES）技術(shù)將機(jī)場(chǎng)行李托運(yùn)系統(tǒng)的運(yùn)行建模為離散實(shí)例序列。采用DTW算法度量特定時(shí)刻用于標(biāo)記系統(tǒng)狀態(tài)變化的實(shí)例序列間的相似性并聚類。根據(jù)實(shí)例序列類簇特征分析系統(tǒng)行為（如是否存在瓶頸等）。實(shí)驗(yàn)結(jié)果如表4所示。

RankClus活動(dòng)挖掘算法活動(dòng)聚類結(jié)果較為準(zhǔn)確，活動(dòng)類簇反映語(yǔ)義清晰，因此RankClus活動(dòng)聚類流程模型的重現(xiàn)度指標(biāo)與原生日志流程模型大致相當(dāng)。DTW活動(dòng)挖掘算法聚類的實(shí)例序列與活動(dòng)發(fā)生時(shí)刻相關(guān)性較強(qiáng)，所得流程模型中活動(dòng)精確到時(shí)刻級(jí)別，模型過(guò)于精密，不能很好適應(yīng)噪聲數(shù)據(jù)。RankC lus活動(dòng)挖掘算法所得的基于蹤跡聚類的活動(dòng)排序評(píng)分在反映當(dāng)前流程日志活動(dòng)信息的同時(shí)，包含更具意義的蹤跡信息。若流程日志因條目更新等原因摻雜噪聲，此時(shí)蹤跡聚類結(jié)果不會(huì)急劇變化，模型通過(guò)日志移動(dòng)仍可較好地重現(xiàn)流程日志。因此RankClus活動(dòng)聚類模型的蹤跡重現(xiàn)度與日志移動(dòng)重現(xiàn)度要顯著高于DTW活動(dòng)聚類流程模型，而模型移動(dòng)重現(xiàn)度與DTW活動(dòng)聚類流程模型相當(dāng)。整體而言，RankC lus活動(dòng)聚類模型的魯棒性要優(yōu)于DTW活動(dòng)聚類流程模型。

4.3 流程模型結(jié)構(gòu)復(fù)雜度對(duì)比實(shí)驗(yàn)

Petri網(wǎng)流程模型的結(jié)構(gòu)復(fù)雜度可用Petri網(wǎng)中的與連接（AND-Joins）、與分歧（AND-Sp lits）、異或連接（XOR-Joins）、異或分歧（XOR-Sp lits）數(shù)評(píng)估。表5是對(duì)3個(gè)數(shù)據(jù)集添加活動(dòng)類標(biāo)簽前后挖掘所得流程模型的結(jié)構(gòu)復(fù)雜度分析結(jié)果。流程模型的結(jié)構(gòu)復(fù)雜度主要決定于流程日志自身的內(nèi)容而非所使用的流程挖掘算法［6］?；赗ankClus的流程日志活動(dòng)挖掘算法將數(shù)量較多的低抽象層次活動(dòng)聚類為高抽象層次活動(dòng)類簇，減少了Petri網(wǎng)變遷數(shù)，所得活動(dòng)聚類流程模型結(jié)構(gòu)復(fù)雜度相較于原生日志流程模型明顯下降，且優(yōu)于DTW活動(dòng)聚類流程模型。

圖2　 各數(shù)據(jù)集下的活動(dòng)評(píng)分

圖3　 各數(shù)據(jù)集下的活動(dòng)聚類結(jié)果

表4　 流程模型一致性檢測(cè)實(shí)驗(yàn)結(jié)果

表5　 流程模型結(jié)構(gòu)復(fù)雜度實(shí)驗(yàn)結(jié)果

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

本文針對(duì)非結(jié)構(gòu)化的機(jī)場(chǎng)流程日志活動(dòng)信息，提出基于RankClus算法的機(jī)場(chǎng)流程日志活動(dòng)挖掘算法，構(gòu)建二類型網(wǎng)絡(luò)描述機(jī)場(chǎng)流程日志中活動(dòng)與蹤跡的關(guān)系，聚類日志中低抽象層次活動(dòng)并得到RankClus活動(dòng)聚類機(jī)場(chǎng)流程日志。實(shí)驗(yàn)表明，對(duì)該活動(dòng)聚類流程日志挖掘所得RankClus活動(dòng)聚類流程模型保持了較高日志重現(xiàn)度，同時(shí)顯著降低流程模型結(jié)構(gòu)復(fù)雜度，使流程模型更易于理解。對(duì)低抽象層次流程日志的流程挖掘有較大幫助。

［1］ VAN DER AALST W M P. Process m ining: Overview and opportunities［J］. ACM Transactions on Management Information System s， 2012， 3（2）: 1-17. doi: 10.1145/2229156. 2229157.

［2］ LANZ A， WEBER B， and REICHERT M. Time patterns for process-aware in formation system s［J］. Requirem ents Engineering， 2014， 19（2）: 113-141. doi: 10.1007/s00766-012-0162-3.

［3］ BOSE R P J C， VAN DER AALST W M P， ZLIOBAITE I，et al. Dealing w ith concept drifts in process m ining［J］. IEEE Transactions on Neural Networks and Learn ing System s，2014， 25（1）: 154-171. doi: 10.1109/TNNLS.2013.2278313.

［4］ GüNTHER C W， ROZINAT A， and VAN DER AALST W M P. A ctivity m ining by global trace segm en tation［C］. Proceed ings of the 8th International Conference on Business Process M anagem en t， Hoboken， 2010: 128-139. doi: 10.1007/ 978-3-642-12186-9_13.

［5］ DESAI N， BHAM IDIPATY A， SHARMA B， et al. Process trace identification from unstructured execution logs［C］. Proceedings of the 7th International Conference on Services Com puting， M iam i， 2010: 17-24. doi: 10.1109/SCC.2010.86.

［6］ BAIER T， MENDLING J， and WESKE M. Bridging abstraction layers in process m ining［J］. Information Systems，2014， 46（12）: 123-139. doi: 10.1016/j.is.2014.04.004.

［7］ SONG M， GüNTHER C W， and VAN DER AALST W M P. Trace clustering in p rocess mining［C］. Proceedings of the 7th International Conference on Business Process M anagement，U lm， 2009: 109-120. doi: 10.1007/978-3-642-00328-8_11.

［8］ BOSE R P J C and VAN DER AALST W M P. Context aware trace clustering: towards imp roving process m ining results［C］. Proceedings of the 2009 SIAM Data M ining Con ference， Sparks， 2009: 401-412. doi: 10.1137/1. 9781611972795.35.

［9］ BOSE R P J C and VAN DER AALST W M P. T race clustering based on conserved patterns: Tow ards achieving better process models［C］. Proceedings of the 8th International Conference on Business P rocess M anagem en t，Hoboken， 2010: 170-181. doi: 10.1007/978-3-642-12186-9_16.

［10］ SUN Y， HAN J， ZHAO P， et al. Rankclus: integrating clustering w ith ranking for heterogeneous inform ation network analysis［C］. Proceedings of the 12th International Con ference on Extending Database Technology: Advances in Database Technology， Sain t-Petersburg， 2009: 565-576. doi: 10.1145/1516360.1516426.

［11］ FERREIRA D R， SZIMANSKI F， and RALHA C G. Im proving process models by m ining mappings of low-level events to high-level activities［J］. Journal of Intelligent Information System s， 2014， 43（2）: 379-407. doi: 10.1007/ s10844-014-0327-2.

［12］ SHAN S， WANG L， and LI L. Modeling of emergency response decision-making p rocess using stochastic Petri net: an e-service perspective［J］. Information Technology and Management， 2012， 13（4）: 363-376. doi: 10.1007/s10799-012-0128-7.

［13］ 陳季夢(mèng)， 陳佳俊， 劉杰， 等. 基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法［J］. 電子與信息學(xué)報(bào)， 2015， 37（2）: 449-454. doi: 10.11999/JEIT140512.

CHEN Jimeng， CHEN Jiajun， LIU Jie， et al. Clustering algorithm s for large-scale social networks based on structural sim ilarity［J］. Journal of Electronics & Information Technology， 2015， 37（2）: 449-454. doi: 10.11999/JEIT 140512.

［14］ 陳麗敏， 楊靜， 張健沛. 一種基于嵌入技術(shù)的異構(gòu)信息網(wǎng)絡(luò)的快速聚類算法［J］. 電子與信息學(xué)報(bào)， 2015， 37（11）: 2634-2641. doi: 10.11999/JEIT 150106.

CHEN Lim in， YANG Jing， and ZHANG Jianpei. A fast clustering algorithm based on embedd ing technology for heterogeneous inform ation networks［J］. Journal of Electronics & Information Technology， 2015， 37（11）: 2634-2641. doi: 10.11999/JEIT150106.

［15］ LEEMANS S J J， FAHLAND D， and VAN DER AALST W M P. D iscovering b lock-structured process m odels from event logs containing infrequent behaviour［C］. Proceedings of the 11th International Conference on Business Process Management， Eindhoven， 2014: 66-78. doi: 10.1007/978-3-319-06257-0_6.

［16］ GRABBE S R， SRIDHAR B， and MUKHERJEE A. Clustering days w ith sim ilar airport weather conditions［C］. Proceedings of the 14th AIAA Aviation Technology，Integration， and Operations Con ference， A tlanta， 2014: 2014-2712. doi: 10.2514/6.2014-2712.

［17］ JOHNSTONE M， LE V T， ZHANG J， et al. A dynam ic time warped clustering technique for discrete event simu lationbased system analysis［J］. Expert Systems with Applications，2015， 42（21）: 8078-8085. doi: 10.1016/j.eswa.2015.06.040.

［18］ ADRIANSYAH A， SIDOROVA N， and VAN DONGEN B F. Cost-based fitness in conformance checking［C］. Proceedings of the 11th International Conference on Application of Concurrency to System Design， Kanazawa， 2011: 57-66. doi: 10.1109/ACSD.2011.19.

徐濤：男，1962 年生，教授，研究方向?yàn)閿?shù)據(jù)挖掘、智能信息處理研究.

孟野：男，1990 年生，碩士生，研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等.

盧敏：男，1985 年生，助理研究員，研究方向?yàn)樾畔z索、文本挖掘等.

Activity Mining for Airport Event Logs Based on RankClus A lgorithm

XU Tao①②MENG Ye①LU M in①②①
①（College of Compu ter Science and Technology， Civil Aviation University of China， T ianjin 300300， China）
②（Information Technology Research Base of Civil Aviation Adm inistration of China， Tianjin 300300， China）

Process m ining is a technology which can extract non-trivial and usefu l in formation from airport event logs. However， the airport event logs are always on a detailed level of abstraction， which may not be in line w ith the expected abstract level of an analyst. Process m odels generated by these event logs are always spaghetti-like and too hard to com prehend. An app roach to overcome this issue is to group low-level events into clusters， w hich represent the execu tion of a higher-level activity in the process model. Therefore， this paper presents a new activity m ining method which is based on RankClus algorithm to generate activity clusters integrated with ranking. On this basis， the activity-clustered model which is easier to comp rehend can be constructed. The experiment results show that this activity-clustered model， which shares a sim ilar level of con formance with the meta model， is significantly less com plex.

Process m ining； Activity m ining； RankClus； Trace clustering

s: The National Natural Science Foundation of Ch ina （61502499）， The Civil Aviation Key Technologies R&D P rogram of Ch ina （MHRD 20140105）， The Fundam ental Research Funds for the Central Universities of Ch ina （3122013C005，3122014D 032， 3122015D 015）， The Scientific Research Foundation from Civil Aviation Un iversity of Ch ina （2013QD18X）， The Open P roject Foundation of Inform ation Technology Research Base of Civil Aviation Adm inistration of Ch ina （CAAC-ITRB-201401）

TP391

A

1009-5896（2016）08-2033-07

10.11999/JEIT 151137

2015-10-10；改回日期：2016-04-15；網(wǎng)絡(luò)出版：2016-06-03*

孟野mykonakona@foxm ail.com

國(guó)家自然科學(xué)基金（61502499），中國(guó)民航科技創(chuàng)新引導(dǎo)資金項(xiàng)目重大專項(xiàng)（M HRD 20140105），中央高?？蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金（3122013C005， 3122014D 032， 3122015D 015），中國(guó)民航大學(xué)科研基金（2013QD 18X），中國(guó)民航信息技術(shù)科研基地開(kāi)放課題基金（CAAC-ITRB-201401）