清华学生利用束搜索和改进成本函数优化过程一致性检测，提升效率和准确性。
原文标题：大数据能力提升项目｜学生成果展系列之三
原文作者：数据派THU
冷月清谈：
流程挖掘技术是从流程日志数据中提取有效信息并加以利用的技术，其中过程一致性检测用于发现日志数据与流程模型之间的差异。传统的检测方法在处理复杂流程模型时效率较低。为了解决这个问题，孙沛瑜同学设计了BSFC过程一致性检测算法框架。
该框架的核心思想是通过采样减少数据量，并结合改进的成本函数和束搜索算法提高检测效率和准确性。
采样方法包括完全随机采样、基于概率分布的采样和基于聚类的采样。改进的成本函数考虑了不同事件的重要程度，根据事件出现频率计算成本，使算法更倾向于选择出现频率高的对齐步。束搜索算法在搜索过程中设定阈值，选择成本最小的多个状态进行扩展，兼顾了效率和解的质量。
实验结果表明，该算法在保证较高准确率的同时，显著提高了检测速度。
怜星夜思：
2、成本函数的设计对过程一致性检测结果有什么影响？除了基于频率的方法，还有哪些方法可以用来设计成本函数？
3、束搜索算法的参数如何选择？如何平衡搜索效率和结果的准确性？
原文内容
为了发挥清华大学多学科优势，搭建跨学科交叉融合平台，创新跨学科交叉培养模式，培养具有大数据思维和应用创新的“π”型人才，由清华大学研究生院、清华大学大数据研究中心及相关院系共同设计组织的“清华大学大数据能力提升项目”开始实施并深受校内师生的认可。项目通过整合建设课程模块，形成了大数据思维与技能、跨界学习、实操应用相结合的大数据课程体系和线上线下混合式教学模式，显著提升了学生大数据分析能力和创新应用能力。
回首2024年，清华大学大数据能力提升项目取得了丰硕的成果，同学们将课程中学到的数据思维和技能成功地应用在本专业的学习和科研中，在看到数据科学魅力的同时，也将自己打造成为了交叉复合型的创新型人才。下面让我们通过来自8个院系的8位同学代表一起领略他们的风采吧！
代表性成果
软件学院 孙沛瑜
流程挖掘技术，是一种从流程日志数据中提取有效部分并加以使用的技术，它使用流程模型来表示一个流程是如何进行的，以模型和日志数据作为处理的主要重点，主要的方法有以下三种：流程发现、过程一致性检测与模型优化。
本文所研究的就是其中的过程一致性检测技术。由于在现实流程运行的过程中可能会出现许多意外，导致日志数据与流程模型会有各种不可预料的差异，过程一致性检测技术能够找到这些差异，进而对其进行分析，找到差异产生的原因并加以处理。
而在现实生产生活的应用中，许多流程模型都在变得越发庞大与复杂，所以在进行过程一致性检测的时候，往往会消耗大量的时间。另一方面，在使用流程挖掘技术用来进行错误操作检测与预测的时候，对过程一致性检测又有实时性的需求，于是就对过程一致性检测运行的速度提出了更高的要求。
为了加速过程一致性检测的计算并保证准确性，可以采取采样、减少搜索空间、改进成本函数的方法，因此本文设计了 BSFC 过程一致性检测算法框架。该框架由以下几个部分构成：先使用采样的方法对日志数据进行采样得到日志数据采样，与过程模型一起计算得到成本函数，最终使用引入了束搜索思想的搜索方法搜索对齐方案。
下面是算法的具体流程：
算法的采样部分以需要进行对齐的日志数据作为输入，在经过处理之后输出经过采样的日志数据，用于之后成本函数计算这一步。
具体的采样方法可以分为三类：1、完全随机；2、根据不同事件序列的概率分布使用对应的概率来进行采样，这样能够体现原数据不同的概率分布；3、通过聚类的方法采样得到一部分事件序列，这样能够最体现出原数据的特征，减少信息丢失，在实现中，本文使用 k-medoids 算法进行聚类计算，其中 k-medoids 算法的基本思 想是获得 k 个以给定的数据点作为聚类中心的聚类集。
算法的成本函数计算部分上，默认的成本函数通常设置为非隐变迁的模型步与日志步的数量之和。这种成本函数的设置实际上是基于每一种模型步和每一种日志步对最终的对齐结果的影响程度是一样的假设的。而在现实生活中，各种不同事件的重要程度也不尽相同，而模型步和日志步分别对应着在过程的执行过程中缺失了某一步和多余了某一步，所以它们对过程的影响也应该是不同的，所以这个时候就需要对成本函数进行改进，从而能够更好的对每个对齐步的不同影响进行表达。
为了更好地对每个对齐步的不同影响进行表达，考虑基于每个对齐步的出现频率计算对应的成本函数，这样的话，会使得出现频率更加高的对齐步的成本函数值低于出现频率更加低的对齐步的成本函数值，从而使计算对齐方案时更倾向于使用出现频率高的对齐步进行对齐。
要计算出成本函数，首先是对采样得到的事件序列计算出他们所对应的过程模型的对齐序列，再统计每一个事件所对应的变迁和事件在所有对齐序列中分别对应着多少次同步步、模型步、日志步，分别使用 sync、skip、insert 来表示相应的次数，同时令 totnum 为三者之和，tcnt 为 skip 与 sync 之和，ecnt 为 insert 与 sync 之和，然后使用下述函数求得成本函数的值。
在计算对齐方案的部分，由于基于对齐的过程一致性检测基线算法是基于搜索的，所以计算所需要的时间和空间消耗就与总的状态数息息相关，搜索时需要遍历的状态越多，时间和空间消耗就越大，于是考虑通过减少搜索到的状态数来对搜索过程进行加速从而对对齐过程进行加速。
通常来说，最容易想到的减少搜索时遍历状态数的搜索方法就是贪心搜索，即每一次转移状态时只去进行增加成本最少的一步，直到到达终止状态结束，但是这种方法很容易陷入搜索状态所组成的图中的局部极值里面，所以较难得到一个较优的解，而束搜索算法对贪心搜索的算法进行了一点改进，使得在减少搜索时遍历状态数的同时能够得到一个更优秀的解，因此本文考虑将束搜索的思想引入到对对齐结果的搜索中来。
束搜索与贪心搜索相比，在每一个搜索阶段不止是对成本最小的状态进行扩展，而是设定一个阈值 num_beam，选取成本最小的 num_beam 个状态进行扩展，从而能够对相对更多的搜索状态进行遍历，于是在减少了所需要进行搜索的状态数的同时又保证了结果一定的优秀性。在图中展示了一个 num_beam=2 的束搜索例子，在每个搜索阶段都选取成本最小的两个状态进行进一步搜索，最终搜索到了 ACB 和 CDC 两个字符串。
与本文算法做对照的算法是基于对齐的过程一致性检测算法，耗时变化如下：
而在对齐方案与最优方案的对比上，也有着较高的最优方案比例。
总的来说，在搜索算法中引入束搜索的思想和改进成本函数两种方法后能够在保证精确度的同时对搜索过程进行加速，但同时也可能会导致无法搜索到最优的对齐方案。随着算法参数 m 变大，搜索时间会变长，搜索得到的对齐结果会变得更精确。
上述成果已整理成论文《基于束搜索和改进成本函数的过程一致性检测技术》，被第十三届中国业务过程管理大会（CBPM2023）录用。
编辑：文婧
校对：林亦霖
