流程挖掘之图算法——望繁信VSCelonis
在详细说流程图算法之前，我先谈下学术界和商业界⼏种常见的流程图类型， 1）Petrinets（也叫Petri ⽹），2) Process Tree（简称PT 流程树），3）BPMN 2.0，4）DFG（直接跟随图）。
⼀、Petrinets（也叫Petri⽹）
Petrinets在上个世纪60年代就被提出了，是学术界最主要也是最重要的描述流程节点关联性的图表⽰⽅法，它通过动态特性token来作为流程流转的标识，反映着流程流转的动态情况。Petrinets应⽤很⼴，其中⼀个重要的应⽤就是做Conformance Checking（⼀致性检验），但⽬前⼏乎所有的商业流程挖掘软件都没有⽤Petrinets作为流程图，原因很简单，那就是Petrinets看起来⾮常复杂难懂。
⼆、Process Tree（简称PT，流程树）
PT是通过Process Discovery的产物，⽐如Alpha算法和Inductive mining的产物就是PT，由于PT是通过树形结构存储流程节点关联关系的，因此对于学者和程序员来说是⾮常好理解的结构，但是不适合业务⼈员。
三、BPMN 2.0
BPMN 2.0是商业界⼴泛地⽤于制作企业业务规范的流程图标准，BPMN 2.0可以和PT做⽆缝地转换，并且也可以转换成Petrinets，是⼀个⾮常标准的流程定义的规范，但是，制作流程图的⼀个关键核⼼是要简单，BPMN2.0为了能够精准地描述流程的并⾏关系、选择关系、循环关系等需要在流程图中加很多的控制门，这些控制门⽆疑拖累了流程图的简洁性，也不适合作为流程图的展⽰形式。
四、DFG（直接跟随图）
DFG脱颖⽽出，它也是⽬前所有流程挖掘公司都在使⽤的流程图，虽然很多⼈诟病DFG的准确性，⽐如将多个流程路径混为⼀谈等等，但是DFG简洁⽽⼜清晰地描述了流程的⾛向，⽆疑是最便于业务⼈员使⽤的。
可以说流程图是流程挖掘的“魂”，也是流程挖掘最⼤价值之⼀，优秀的流程图算法可以根据EventLog“清晰”地还原企业的真实业务流，让企业流程的执⾏路径⼀⽬了然。这⾥的我把“清晰”画了重点，“清晰”其实很难⽤学界量化指标来描述，更多地是⼈为主观感觉，简⽽⾔之就是业务⼈员能不能从流程图⾥⼀眼就能看清楚企业流程“从头到尾”的⾛向，流程中的层次等等。为了能够满⾜这⼀“清晰”的要求，望繁信⾛了⼀条⾃⼰的创新流程图算法之路，也是我们团队潜⼼研究的成果，在现有d3-dagre算法的基础上做了很多创新。
为了能够展现望繁信在流程图算法上的优势，我们拿市场上做的最好的Celonis作为⽐较对象给⼤家详
细讲解⼀下。
⼤家看如下两张流程图（图1为望繁信科技的流程图，图2为Celonis的流程图），图⼀：
图⼆：
这两张流程图采⽤的是同⼀客户数据集（客户数据集我们做了匿名化处理），这组数据集的流程节点有个特点，标记数字⼤的节点⼀般发⽣在标记数字⼩的前⾯，⽐如：标记为2.1开头的流程节点⼀般会发⽣在开头为1.1的流程节点前⾯。当时我们的客户看了Celonis的流程图就觉得很费解，接下来，我们简单做个⽐较：
1、“7.1办结”应该为整个流程的结束节点，但是Celonis却将“7.1办结”放在了流程的中间，⽽望繁信的流程图就能很好的将“7.1办结”放在流程的末尾；
2、“1.1业务单位申请岗”应该是流程的开始，Celonis却将它放到了流程的最下⾯，但望繁信科技却能正确地将其放在流程的开始；
3、Celonis⽆法识别正确地识别同级的流程节点，⽐如“1.3业务单位负责⼈审核”和“1.3业务单位负责⼈审核”应该属于同⼀级别
的，Celonis却将这两个节点的上下距离拉开了很⼤，根本⽆法得知两个节点的关系，但是望繁信却能很智能地将同级关系识别出来，并放在同⼀层。
还有很多细节，我就不逐⼀举例了，⼤家如果仔细⽐较⼀下望繁信和Celonis的流程图，就不难发现望繁信的流程图上下结构和层次会更加的清晰。
接下来就是重头戏了，望繁信的流程图算法是怎么做的？为什么望繁信的流程图可以很清晰展现层次，⽽且效率也很⾼？
流程图算法涉及多个学科领域，⽤到了三类数学领域知识（本⼈在法国博⼠学的就是应⽤数学，也是最擅长的领域之⼀）： 组合优化理论、图理论和概率论。流程图算法的输⼊是所有的节点，节点与节点的边，以及节点的案例数量/事件数量/吞吐时间+边的案例数量/事件数量/吞吐时间。“清晰”的流程图必定是“从上到下”⼀⽓呵成，为此我建⽴了⼀个混合整数线性规划模型（MLP模型），以“清晰”为⽬标设计⽬标函数和各种约束条件，最终⽣成流程图。
⽐如，我们在处理节点位置的时候，会考虑如果⼀个节点的出度很少⼊度很多，⽽且这个节点不存在
哈密顿圈，那么它就会被排在靠近下⾯，那么节点的出度和⼊度等统计信息以及图回路就会转换成⽬标函数和约束条件加⼊到MPL模型。再⽐如，我们还考虑了节点与其他节点的关系，我们在经典马尔科夫链基础上扩展了⼀个新的转移概率模型，该模型充分考虑了案例数量/事件数量/吞吐时间三个因素，综合判断节点和其他节点间的转移概率，如果⼤部分节点转移到当前节点的概率很⾼，那么节点会排在更靠后，这些转移概率模型也会抽象成约束条件添加到MPL模型中。
说到这⾥，是不是很多⼈晕了，这只是流程图算法的冰⼭⼀⾓，还有很多因素需要考虑。例如说，⼈们不喜欢看到同⼀层节点有⽔平的边相连，⽔平线给⼈的感觉就是不清楚的前后关系；再有，同⼀层中的节点如何排序才能体现流程的主⼲；还需要考虑，流程图中边与边之间如何⽤聚类算法聚类才能尽量少交叉，交叉的时候尽量让次要的边交叉，主要的边少交叉，如何定位边和节点的坐标等等（就不逐⼀举例了）。这些因素都直接影响流程图的“清晰”性，我们将这些因素全都抽象成了数学语⾔加⼊到了MPL模型中。
接下来⼀个重要的问题是如何求解，我做了⼀个实验，⽤ILogCplex去求解流程图的最优解，但是很可惜当流程图很复杂的时候，求解速度巨慢⽆⽐，根本达不到商业落地的要求，接着我放宽了⼏个条件，将其作为⽬标函数的下界（Lower Bound），设定下界和最优解最多差
巨慢⽆⽐，根本达不到商业落地的要求，接着我放宽了⼏个条件，将其作为⽬标函数的下界（Lower B流程图转换为ns图
ound），设定下界和最优解最多差10%为⽬标求解，可惜速度仍然慢的不能接受。该实验证明了通⽤性分⽀定界算法和切平⾯算法根本⽆法实现在线流程图的计算，这也和我们的数学证明不谋⽽合，因为流程图的MPL模型是⼀个NP Hard问题。
所以，望繁信⼜⾛了⼀条⾃⼰的路，我们⾃⼰设计和开发优化算法，该优化算法⽤到了对偶模型、边切割和Branch-and-Cut算法，将MPL 模型分解成了多个NP-Complete⼦问题进⾏求解，这样不仅求解速度快，⽽且可以实现“清晰”这个⽬标。这就是为什么望繁信在流程图的结构层次上相较于Celonis更加直观，给业务⼈员更“清晰”地展⽰了流程中节点的关系。
虽然流程挖掘看起来是个简单易上⼿的东西，但是请⼤家思考⼀下，流程挖掘的商业落地也会这么简单吗？直接改写开源⼯具（Apromore，Pm4Py，ProM）就可以了吗？我可以很负责任地说流程挖掘有太多的技术需要攻克，这也是为什么Celonis做了近⼗年、Process Gold做了6年多、我的前东家IBM收购意⼤利流程挖掘公司Myinvenio，还有很多知名企业都去收购流程挖掘公司⽽不是⾃⼰去做⼀个流程挖掘平台的重要原因之⼀。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。