基于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）