基于RankClus算法的機場流程日志活動挖掘

徐　濤　孟　野　盧　敏（中國民航大學計算機科學與技術學院　天津　300300）（中國民航信息技術科研基地　天津　300300）

?

基于RankClus算法的機場流程日志活動挖掘

徐濤①②孟野*①盧敏①②①
①（中國民航大學計算機科學與技術學院天津300300）
②（中國民航信息技術科研基地天津300300）

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

流程挖掘；活動挖掘；RankClus；蹤跡聚類

1　　引言

機場運行過程中時刻有各類事件發生，機場業務信息系統隨之生成一系列機場流程日志。對機場流程日志進行流程挖掘可得到相應的業務流程模型［1］，借由業務流程模型指導，機場可開展運行決策支持［2］及業務趨勢預測［3］等一系列工作以提高機場運行效率。因此機場流程日志的流程挖掘具有重要意義。

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

本文構建二類型網絡（bi-type network）描述活動與蹤跡關系，視活動與蹤跡為不同類型結點，用活動在各蹤跡結點類簇的排序評分向量量化表示活動，為此需得到合理蹤跡聚類結果以計算該排序評分。文獻［7-9］的蹤跡聚類方法難用于蹤跡聚類的活動排序評分計算，不能很好銜接后續活動聚類工作。文獻［10］提出有效結合聚類和排序的RankClus算法。該算法主要功能是對二類型網絡排序與聚類。應用在機場流程日志活動挖掘能夠得到較準確的蹤跡結點劃分結果，并計算出活動結點在蹤跡劃分生成子網絡的排序評分。在RankClus算法基礎上，本文將蹤跡聚類與活動聚類相結合，設計機場流程日志低抽象層次活動的聚類算法，使基于聚類結果挖掘所得日志流程模型在保持一定日志重現度的同時，有效降低流程模型的結構復雜度。

2　　機場流程日志活動挖掘分析

機場流程日志的流程挖掘主要關注提交時間、部門、模塊、活動、實例號等屬性。表1是國內某機場的部分流程日志，類似“新增要客航班：HU7703，CA 1321。”，“要客航班更新：CA947，請各單位加強關注。”活動描述的事件大量存在，這類事件可統一視為“要客航班更新”。但流程挖掘時低抽象層次事件與活動間一對一映射的關系［11］及復雜的活動描述語義，使數據預處理合并事件的做法難以實現，挖掘到的流程模型充斥大量低抽象層次活動。為此需將低抽象層次事件通過聚類方式抽象為高抽象層次的活動類簇。將“新增”、“更新”等活動描述標識的事件聚類為表示“要客航班更新”的活動類簇以簡化流程模型結構。

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

可構造如圖1所示的二類型網絡描述活動與蹤跡間關系，并區分網絡中活動在各類蹤跡中重要度以聚類相似的低抽象層次活動。用高抽象層次活動類簇替代原日志活動，構建蹤跡集合。該網絡由活動結點與蹤跡結點組成，網絡的實線視為該活動在蹤跡中出現了一次，虛線則表示結點間存在相似性。采用二類型網絡來描述活動與蹤跡間的關系，使得流程日志活動挖掘問題轉變為聚類二類型網絡活動結點的問題［13，14］。

表1　 國內某大型樞紐機場部分流程日志

表2　 國內某大型樞紐機場2013年流程日志結構分析

圖1　 活動與蹤跡的二類型網絡

3　　基于RankClus的機場流程日志活動挖掘算法

3.1 RankClus混合模型

為聚類活動與蹤跡的二類型網絡中的活動結點，需劃分蹤跡結點，將活動結點表示為在各類蹤跡上的重要度排序評分的評分向量。為獲取蹤跡結點的合理劃分結果，可引入RankC lus算法的混合模型（m ixture m odel），通過模型參數估計得到的蹤跡結點表示向量，對蹤跡結點進行劃分。以機場流程日志活動-蹤跡二類型網絡為例，X表示機場日志蹤跡結點集合，Y表示機場低抽象層次活動結點集合，則可表示機場日志蹤跡結點與機場低抽象層次活動構成的二類型網絡，W為網絡的鄰接矩陣，分塊可得：

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

3.2 排序評分的計算

rX'=rX'|X'為對X聚類時X'的類內排序評分，為對X聚類時Y的條件排序評分，分別反映一類相似蹤跡中某蹤跡出現頻繁程度和各活動參與情況。rX|X'為rY|X'在網絡G上所得傳遞得分，可定義為

3.3 聚類中心和距離的計算

每個ix對應一K維向量如令則每個jy可對應一K維向量；計算X類簇或Y類簇中所有結點對應向量的平均值，得到每個類簇的類簇中心：

3.4 算法流程

文獻［10］為控制聚類數及得到更具意義聚類結果，指定算法聚類結點數較少類型的結點，未提供聚類網絡中結點數較多類型結點的相應解決方案，不能直接聚類多于蹤跡的活動。表3算法流程輸出準確的基于蹤跡聚類的流程日志活動排序評分后繼續迭代計算活動排序評分。這一評分可為活動聚類提供足夠信息。

4　　實驗與分析

對原生日志添加活動聚類標簽后，可生成活動聚類流程日志 （activity-clustered event log） 挖掘流程模型。比對各流程模型的日志重現度以驗證聚類結果合理性；分析各流程模型的結構復雜度以驗證活動聚類日志能在保持回放準確度的同時有效降低模型結構復雜度。本文實驗數據集為表2中3組不同時間區間的流程日志，并選用文獻［15］的Inductive M iner方法挖掘流程日志的Petri網流程模型，噪聲參數設置為0.1。

4.1 機場流程日志活動聚類實驗

機場等大型機構數據聚類分析的參數設定多依賴于領域專家知識［16］。結合機場運行專家知識［16，17］及數據源機場實際運行情況歸納得15類業務流程及20類業務活動，分別作為蹤跡結點聚類數與活動結點聚類數。文獻［4］總結低抽象層次活動與業務流程間關系為兩類：（1）業務流程由被單一活動類簇覆蓋的低抽象層次活動組成；（2）業務流程由分散在不同活動類簇中的低抽象層次活動組成。圖2是算法穩定時蹤跡結點各類簇的活動結點評分，圖3是活動結點聚類結果。數據集1結點數最多的類簇15主要為重點保障航班保障活動，活動描述以“CZ390有旅客要下機，需客梯車到現場。”、“MU5714航班滑回，需客梯車。”等居多。數據集2活動結點數最多的類簇2主要由活動描述為“安保公司收到，轉飛行區安檢部。”的機場安檢公司業務響應活動組成。這些同類簇的低抽象層次活動間有較強相關性且滿足第1類關系，直接分析原生日志流程模型也能得到類似結果。

數據集3活動結點較多的類簇為1， 11， 12。類簇12的活動描述以航班計劃、共享航班等信息更新活動為主，活動間關系與數據集1的類簇15、數據集2的類簇2相似。類簇1與類簇11的活動描述由機場地服公司開展的業務活動組成，但側重不同；類簇1與數據集1中類簇4的活動結點描述相仿，側重于機位作業業務，而類簇11則側重于開展重點航班保障相關活動。類簇1與類簇11的低抽象層次活動間相關性較弱，直接分析原生日志流程模型易混淆這兩類低抽象層次活動，影響流程發現準確性。只有通過活動聚類結果反映低抽象層次活動與業務流程的第2類關系，才可合理地區分低抽象層次活動。

表3　 基于RankClus算法的流程日志活動挖掘算法流程

4.2 機場流程日志一致性檢測實驗

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

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

4.3 流程模型結構復雜度對比實驗

Petri網流程模型的結構復雜度可用Petri網中的與連接（AND-Joins）、與分歧（AND-Sp lits）、異或連接（XOR-Joins）、異或分歧（XOR-Sp lits）數評估。表5是對3個數據集添加活動類標簽前后挖掘所得流程模型的結構復雜度分析結果。流程模型的結構復雜度主要決定于流程日志自身的內容而非所使用的流程挖掘算法［6］。基于RankClus的流程日志活動挖掘算法將數量較多的低抽象層次活動聚類為高抽象層次活動類簇，減少了Petri網變遷數，所得活動聚類流程模型結構復雜度相較于原生日志流程模型明顯下降，且優于DTW活動聚類流程模型。

圖2　 各數據集下的活動評分

圖3　 各數據集下的活動聚類結果

表4　 流程模型一致性檢測實驗結果

表5　 流程模型結構復雜度實驗結果

5　　結束語

本文針對非結構化的機場流程日志活動信息，提出基于RankClus算法的機場流程日志活動挖掘算法，構建二類型網絡描述機場流程日志中活動與蹤跡的關系，聚類日志中低抽象層次活動并得到RankClus活動聚類機場流程日志。實驗表明，對該活動聚類流程日志挖掘所得RankClus活動聚類流程模型保持了較高日志重現度，同時顯著降低流程模型結構復雜度，使流程模型更易于理解。對低抽象層次流程日志的流程挖掘有較大幫助。

［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］ 陳季夢， 陳佳俊， 劉杰， 等. 基于結構相似度的大規模社交網絡聚類算法［J］. 電子與信息學報， 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］ 陳麗敏， 楊靜， 張健沛. 一種基于嵌入技術的異構信息網絡的快速聚類算法［J］. 電子與信息學報， 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 年生，教授，研究方向為數據挖掘、智能信息處理研究.

孟野：男，1990 年生，碩士生，研究方向為機器學習、數據挖掘等.

盧敏：男，1985 年生，助理研究員，研究方向為信息檢索、文本挖掘等.

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；網絡出版：2016-06-03*

孟野mykonakona@foxm ail.com

國家自然科學基金（61502499），中國民航科技創新引導資金項目重大專項（M HRD 20140105），中央高校科研業務費專項資金（3122013C005， 3122014D 032， 3122015D 015），中國民航大學科研基金（2013QD 18X），中國民航信息技術科研基地開放課題基金（CAAC-ITRB-201401）