基于k-means 和肘部法则的业务流程聚类方法

龙文佳，张晓峰，张 链

（1.湖北大学知行学院 计算机与信息工程学院，湖北 武汉 430011；2.三峡大学 计算机与信息学院，湖北 宜昌 443002）

流程挖掘的目标是通过观察事件日志中记录的事件来提取与流程相关的信息［1］。事件日志是包含业务流程执行（称为路径）的数据集。现有的流程挖掘算法可以挖掘事件日志并提供关于如何执行记录的过程模型（例如Petri 网），这些模型也可以逐步提取［2］。然而，现有政务和企业信息系统其业务流程的自动发现、一致性检查、模型演化、性能分析、案例预测等智能化处理能力较低，无法满足新型信息系统的建设需求。随着政府和企业信息系统中事件日志的日益积累，以及对更好地支持和改进系统业务流程的迫切需求，流程挖掘技术得到了业界的广泛重视和研究。

聚类在数据的探索性分析中应用较为广泛，人们试图在他们的数据中心识别具有“相似行为”的群体来认知他们的数据。业务流程聚类是将数据对象分为若干个组别或者类簇的过程，各组别或类簇内部数据融合性高，组间或者各类别之间相似性较低［3］。文献［4］提出了一种基于半监督聚类的BPMA 方法，该方法基于改进的流程结构树选择初始聚类，并通过结合流程的控制流一致性和活动的语义相似性来设计约束，以指导聚类过程。关于路径聚类的传统研究可分为两类：（1）将对路径转化为对向量空间模型的研究［5-7］;（2）通过应用具有序列距离度量的聚类算法（例如Levensthein 距离）［8-10］，对操作路径进行研究。文献［11］首先将路径转化为矢量，在矢量空间使用马尔科夫聚类对流程进行多个视角的分组，从而在分组结果中发现流程中的主流行为和偏离行为。

为交付有价值的业务流程模型，业界定义了众多流程挖掘算法。由于实际流程的内在复杂性和高度灵活性，算法常生成难以理解的杂乱流程模型，一定程度上增加了流程建模难度。因此，如何提供支持活动视图的路径聚类方法进行流程的聚类，提升聚类准确性，降低流程建模难度，仍是一个难题。

本文提出一种基于聚类的流程挖掘方法，为后期验证系统的实际流程与理论流程的一致性提供理论基础。将k- means 算法与肘部函数相结合的方法应用到会议平台以解决传统的流程挖掘算法在处理会议平台非结构化流程时遇到的问题，避免生成难以理解的流程模型。将所提流程聚类方法应用于金猫汇会议平台，通过抽取系统中多种会议的报名流程，采用活动特征对会议注册流程进行描述，通过业务流程中活动特征对会议业务子流程进行描述，运用k- means 算法并结合肘部函数对向量化的流程进行聚类。

1 方法描述

图1 给出了本文研究的整体路线，其中抽取会议系统报名流程并进行形式化展示是基于文献［12］的工作进行的。

图1 面向会议平台的流程聚类方法Fig. 1 Process clustering method for the conference platform

1.1 基于活动信息的流程路径描述

大量丰富的事件日志信息有助于活动感知的路径聚类算法的构建，同时可为路径相似性矩阵提供描述支持。首先拟从事件日志的活动视图中获取活动特征向量模型，然后通过该特征向量模型对流程路径进行描述，生成路径向量。视图、特征向量模型、路径向量相似性矩阵和聚类矩阵间的对应关系如表1 所示。

表1 视图、特征向量模型、路径向量相似性矩阵和聚类矩阵间对应关系Tab.1 Corresponding relationship among view,feature vector model,path vector similarity matrix and clustering matrix

基于活动信息的流程路径描述包含以下两个主要步骤。

步骤一特征向量模型获取：特征向量模型来源于流程挖掘中实际的信息系统。首先获取实际信息系统的相关事件日志信息，然后定义特征对日志信息进行描述。

步骤二信息的路径向量获取：依据事件日志中的路径信息，利用特征向量模型对同一日志中不同的路径进行描述，获取路径向量，为基于距离的路径聚类算法的构建奠定基础。

事件日志包含多条流程执行路径，路径具有唯一性，可从多个视图对路径进行描述（如路径视图、组织视图、性能视图、控制流视图）。依据每种视图可获取对应的特征向量模型（如活动特征向量模型、资源特征向量模型、性能特征向量模型、转换特征向量模型）。一条路径T 描述了一个业务流程执行的过程，它是活动的有限序列，即路径中的时间是非递减的（for 1≤i＜j ≤ length（T）：timestamp（ei）≤ timestamp（ej））。事件日志L是一个路径包，一个事件日志片段如表2 所示。

表2 一个事件日志片段Tab. 2 A fragment of event log

由视图生成的特征向量模型包含：活动特征向量模型、资源特征向量模型、性能特征向量模型、转换特征向量模型。活动特征向量模型来源于路径视图，主要关注路径中的一系列活动，事件日志中发现的每种活动构建为向量模型的一个特征。一条路径中具有或不具有某种活动，通过拥有各种活动的数量来描述该路径。参考表2 的事件日志，包含7 种不同类型的活动，分别为

register request（R）、examine thoroughly（ET）、check ticket（CT）、decide（D）、reject request（RR）、examine casually（EC）、pay compensation（PC），因此活动特征向量模型具有7 个特征，每条路径描述为具有7 个特征值的向量，每种特征代表一种活动。每个特征的取值描述了该活动在一个路径中出现的次数。活动特征向量模型如表3 所示。

表3 活动特征向量模型Tab. 3 M odel of active feature vector

通过上述特征向量模型对路径进行描述，生成路径向量，为基于距离的活动视图感知的路径聚类奠定基础。

1.2 基于距离的活动视图感知的路径聚类

基于信息获取路径向量是对路径的形式化表达和预处理，能为基于距离的路径聚类提供基础数据支撑。由于距离易于定义与计算，基于距离的算法常用于流程挖掘的研究，算法通常只需一个参数（最终类簇数量或分隔两个类簇的最小距离），因此拟采用基于距离的聚类算法对路径向量进行聚类，生成路径向量相似性矩阵和聚类矩阵，为矩阵的迭代式更新和聚类模式的渐进式收敛提供聚类信息支撑。具体步骤如下。

步骤一路径向量相似性矩阵构建：采用基于距离的聚类算法并结合路径向量，研究各种视图中路径向量相似性矩阵的构建方法，包括活动特征、资源特征、性能特征、转换特征中路径向量相似性矩阵的创建，为聚类矩阵的建立奠定基础。

步骤二聚类矩阵的构建：基于路径向量相似性矩阵研究聚类矩阵的构建方法，即活动特征中聚类矩阵的生成，聚类矩阵将相似性较高的路径向量分配到同一类簇，为相似性矩阵的建立提供支持。

假设L代表一个事件日志，L记录了n条路径，是特征向量模型集，P是一个具体的特征向量模型，且P∈。

相似性矩阵SP是一个（n×n）矩阵，其对应事件日志L和特征向量模型P，矩阵第i行代表路径向量Ti，Ti∈L，第j列代表路径向量Tj，Ti∈L。路径向量间的相似性SP（i，j）= 1- distance（P，Ti，Tj），其中，distance（P，Ti，Tj）是指在特征向量模型P中，路径向量Ti与Tj间的距离，该距离值落在［0，1］。

依据SP显示出的路径相似性，聚类矩阵CP将日志L中的路径分组成k个类簇。CP是一个（n×k）矩阵，矩阵第i行代表路径向量Ti，Ti∈L，第j列代表类簇Cj，Cj∈CP。Ti的聚类矩阵为

其中size（Cj）是指Cj类簇中的路径数。

通过基于距离的相似性算法对路径向量进行聚类，生成路径向量相似性矩阵和聚类矩阵，为相似性矩阵向源于其他特征向量模型聚类矩阵的迭代式投射和更新提供支持。

1.3 基于k-means和肘部法则的聚类

采用k- means 算法并结合肘部函数预先估算类簇数量，并为每一类簇分配初始中心。给定具有n个原子等级的样本集AR= {r1，r2，…，rn}，k- means 算法首先假定将n个原子等级划分为k个类簇，k= {1，2，…，β}，其中β＜n，且β为肘部函数中斜率出现大幅下降的拐点值。k- means 最小化的问题可以转化为所有数据点到其类簇中心的距离之和的最小化问题，定义k- means 的代价函数公式为

式中，Ci为第i个类簇，i= 1,2,…,n,与r()i最近的聚类中心点为μc(i)，μk代表类簇k的聚类中心，通常k的取值是随机的，这里使用肘部函数来选择k的取值。图2 展示了代价函数J与类簇数k的关系。由图2 可知，当β取值小于3 时，代价函数取值下降较快；当β取值大于3 时，代价函数取值下降缓慢，所以可以选择“肘部点”的值作为k的取值。即关键在于依次将k值分别设定为1、2、3一直到β，重复执行k- means 算法获取各个k对应的输出值，直到在β点的下一个点，函数的输出值并未发生大幅下降（肘部函数斜率大幅降低），将β点视为拐点。确定β值后，k值也随之确定，即预测的k=β。依此随机选取k个样本作为各个类簇的初始中心。

图2 肘部函数Fig. 2 Elbow function

k- means 算法依据预测的k值将n个原子等级划分为k个类簇，算法开始时随机选取k个样本作为类簇的初始中心，分别考察样本集AR中每个样本与这些初始中心的距离，依据距离将每个样本分配给与其距离最短的类簇（初始中心），得到k个类簇聚类结果。再计算每个所获类簇新的簇中心，即该类簇中所有样本到初始中心距离的平均值，然后以该平均值作为新的簇中心。不断迭代上述过程直到目标函数收敛为止，得到最终的聚类结果。k- means 算法的目标函数为

式中，Ci为第i个类簇，i= 1，2，…，k。μi是类簇Ci的中心。

公式（2）在一定程度上描述了同一类簇内样本围绕簇中心的紧密程度，E值越小则同一类簇中样本间距离越小。

2 实验验证

金猫汇是数字化会务服务在线平台，它将会议网站的设立、数据公布、网上注册、酒店、车票的收费和现场报道等融为一体，整合了短信、邮件及微信平台，在平台上提供传统会议项目流程的“一站式”服务，有力改善了传统会议举行过程中效率低、安全系数差、销售业务开展难等问题，极大地增强了办会效率，大大方便了参会代表和会议组织者。本文将金猫汇会议平台作为实验对象，抽取其中的业务流程进行业务流程聚类技术的应用。

2.1 会议注册系统的业务流程提取

图3 展示的是软件会议的注册流程图。图形包含多条子流程，上半部分展示的是登录系统的功能，其中，任务“查询会议”之后出现选择分支，可根据输入的查询关键词（会议名称或会议代码）执行相应的任务。随后在“点击报名”任务执行时，系统会根据人员身份进行选择分支中的“登录”或“注册”任务，登录系统的方式也有多种选择。图形下半部分展示了用户在登录系统以后可以进行的任务。其中包含了多条选择分支，包含参会身份的选择、参会人信息的编辑、缴费方式的选择以及发票信息的编辑等，根据用户操作的不同而产生不同的活动路径，从而可以抽取多条子流程。

图3 软件会议注册流程图Fig. 3 Diagram of registration process of Software Conference

图4 展示了工商管理学科会议的注册流程图。工商管理学科会议的注册流程与软件会议的注册流程图“登录成功”任务之前的子流程基本相同，但参会人员成功登录系统之后的子流程相对简单，仅在“报名信息填写”及“参会人信息填写”时执行相应的选择分支任务。

图4 工商管理学科会议注册流程Fig. 4 Diagram of registration process of Business M anagement Discipline Conference

图5 给出了磁性薄膜与纳米磁学会议的注册流程图。相对于图3 所示的流程，磁性薄膜与纳米磁学会议的注册流程中，流程不再执行“参会人员身份”相关的选择分支，且无需“填写参会专家人数”，其他子任务大致与图3 相同。

图5 磁性薄膜与纳米磁学会议注册流程图Fig. 5 Diagram of registration process of M agnetic Thin Film and Nano-Structure M agnetics Conference

图6 是口腔医学会议的注册流程图。口腔医学会议的注册流程与软件会议的注册流程图同样是实现会议的注册报名功能，但具体实现细节上有细微的区别。在口腔医学会议的注册流程中，参会人员不具有参会身份选择这个分支中，并且由于该会议具有公益属性，在该流程中不包含缴费相关的子任务。

图6 口腔医学会议注册流程图Fig. 6 Diagram of registration process of Stomatological Conference

2.2 会议注册系统的业务流程的标识与量化

为准确有效地针对会议系统的流程进行聚类处理，对会议业务模型特征所属的类别和其拥有的特质进行维度分析是很重要的，它也是使用数学方法进行模型特点标志和量化的前提。

表4 给出了相关任务所使用的标识，通过标识对2.1 所述软件会议、工商管理学科会议、磁性薄膜与纳米磁学会议、口腔医学会议的注册流程图中所有的活动进行标识，结果如图3～图6 所示。

表4 会议系统业务流程标识Tab. 4 Business process identification of conference system

通过业务流程中活动特点来叙述会议的相关流程，并且将活动特点的表达变成描述项目模型能不能拥有这些活动特点的描述，这样就可以将会议业务流程活动特点看作是拥有离散状态0 或1 的二进制特征，0 表示该子流程不拥有这个活动特点，1 代表该子流程具有该特征。通过0、1 数字标识从软件会议注册流程图抽取业务子流程共7 681 条，从工商管理学科会议注册流程图抽取业务子流程共1 313 条，从磁性薄膜与纳米磁学会议注册流程图抽取业务子流程共992条,从口腔医学注册流程图抽取业务子流程共192 条，共计10 178 条子流程。

2.3 会议注册系统的业务流程聚类

将本文抽取的4 类会议报名流程的子流程汇集在一起，构成一个47× 10 178 的矩阵。其中一条路径如下：

图7 流程聚类结果示意图Fig.7 Diagram of process clustering results

通过k- means 算法进行聚类分析：新建k个点当作是开始的质心，当某一点的簇分配结果变化时，对数据聚集的每一个点，计算每个质心与数据点中的间隔，然后把数据点分配给间隔最短的簇，对每一个簇，计算簇中所有点的平均值而且将平均值视作新的质心。

图7 展示了流程聚类的结果。图中横坐标表示质心所处位置，纵坐标表示子流程距离该簇质心的距离，蓝色圆点表示会议报名的子流程，由于流程矩阵为一个多维矩阵，并不是一个二维矩阵，所以聚类结果在线条上呈现为散列分布的状况。图中的蓝色圆点在部分情况下并不代表一个子流程，而是一个与质心距离相等的子流程集合。由图可知，当k= 2 时，2 个质心分别位于（0，0）、（0，1）；当k= 3 时，3 个质心分别位于（0，0）、（0，1）、（0，2）；当k= 4 时，4 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）；当k= 5 时，5 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）、（0，4）；当k= 6 时，6 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）、（0，4）、（0，5）；当k= 7 时，7 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）、（0，4）、（0，5）、（0，6）；当k= 8 时，8 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）、（0，4）、（0，5）、（0，6）、（0，7）；当k= 9 时，9 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）、（0，4）、（0，5）、（0，6）、（0，7）、（0，8）；当k= 10 时，10 个质心分别位于（0，0）、（0，1）、（0，2）、（0，3）、（0，4）、（0，5）、（0，6）、（0，7）、（0，8）、（0，9）。

使用k- means 算法对原子等级进行有效聚类的前提是预先确定类簇数量并为每个类簇分配初始中心，且若初始中心分配不合理，即使准确预测出类簇数量，聚类结果可能仅收敛于局部最优。将各个流程到相应质心的平均距离计为E，平均距离E的大小反映了同一类簇中样本对簇中心的紧密程度，E值越小，同一类簇中的样本间距离越小，各样本间也更加集中。针对k的取值问题，由于无法预知最优的k值，依次将k的取值范围设置为［2，10］，迭代执行k- means 算法获取各个k对应的输出值E，将k值与对应的E值关系表示如图8 所示。依据肘部法则可知，拐点k值为9，由此可知，当k= 9 时各流程收敛程度最高。

图8 k-E 图像Fig. 8 Diagram of k-E

将k- means 聚类算法及肘部函数应用到会议平台之中去解决传统的流程挖掘算法在处理会议平台非结构化流程时遇到问题，并且避免生成难以理解的流程模型。本文将视角聚焦于流程活动视图（活动特征），通过对流程的标识与量化，运用k- means 聚类算法得到具有高一致性和可理解性的流程模型。结合肘部函数特点，可知当k= 9 时，聚类收敛度最高，当系统需要添加新的业务流程或者对现有流程进行更新的时候，可以通过9 个类簇以及质心对业务流程进行标识与量化，采用杰卡德系数等方法来计算业务流程模型实例间的相似性，找到最优质心，通过该类簇所有的子流程对新的业务流程进行改进与决策支持。通过本文所提方法可以依据聚类的结果对其他会议流程提供变更与决策支持。

3 结语

通过解释活动视图信息生成活动特征向量模型，利用特征向量模型对系统流程进行描述，提出一种基于k- means 和肘部法则的流程聚类方法，对描述后的流程进行聚类，生成聚类结果，依据聚类结果获取统一聚类模式。进而提升流程聚类的准确性，为降低流程建模难度提供支持。具体包括：提出一种基于活动视图信息的流程路径描述方法；从系统流程的活动视图中获取对应的特征向量模型，通过活动特征向量模型对流程执行路径进行描述，生成路径向量，为活动视图感知的路径聚类奠定基础；提出一种基于k- means 和肘部法则的活动视图感知的路径聚类算法，即采用k- means 和肘部法则预测类簇中心的数量，依据预测结果对路径向量进行聚类，提升聚类准确性，从而在系统分析的实际应用中降低流程建模的难度。