基于图挖掘和图距离的流程推荐方法

摘要

本发明涉及流程自动化领域，公开了一种基于图挖掘和图距离的流程推荐方法，具体步骤如下：预处理步骤：将输入的流程集抽象标号为有向图的形式，得到流程子图；模式发现步骤：子图挖据和分解模块对所述预处理步骤输出的合集进行分解，得到上游子图、候选节点集以及置信度，将所得上游子图、候选节点集以及置信度注册为模式表中的数据条目；流程推荐步骤：推荐模块获取参考流程，将参考流程与模式表中的上游子图进行比较，选出最匹配数据条目，将最匹配数据条目所对应的候选节点集输出为推荐流程。本发明的优点在于，推荐效率高，算法的计算复杂度更小，推荐精度高，支持复杂结构流程的处理，具有较高的应用价值。

主权项

一种基于图挖掘和图距离的流程推荐方法，其特征在于，具体步骤如下：预处理步骤：将输入的流程集抽象标号为有向图的形式，得到流程子图，所述流程集包括工艺流程、业务流程以及事务流程，使用频繁子图挖掘算法对流程子图进行挖据，输出包含所有包括流程子图及其子图出现频率的合集；模式发现步骤：子图挖据和分解模块(21)对所述预处理步骤输出的合集进行分解，得到有影响上游子图、候选节点集以及置信度，将所得有影响上游子图、候选节点集以及置信度注册为模式表(3)中的数据条目，所述流程子图的末尾节点作为候选节点，剩余部分作为上游子图，选择候选节点集中置信度大于阈值的上游子图，即为有影响上游子图；流程推荐步骤：推荐模块(4)获取参考流程，所述参考流程由用户界面模块(1)输入，将参考流程与模式表(3)中的有影响上游子图进行比较，选出最匹配数据条目，将最匹配数据条目所对应的候选节点集输出为推荐流程；流程推荐步骤中，所述比较的步骤具体包括：1)对模式表(3)中的每个有影响上游子图p和参考流程R进行处理，得到所述p和R的最小公共超图MCSub和最大公共子图MCSup，计算得到MM距离，所述MM距离为最小公共超图MCSub和最大公共子图MCSup的大小之差，即MMDist＝|MCSup|‑|MCSub|；2)根据参考流程R的节点向后位置，得到所述p和R的位置距离Lop，所述节点向后位置为：令R＝(N，E，Ln，α)表示参考流程，RR(RR∩N＝φ)表示R的待推荐节点集，In(x)和Out(x)分别表示节点x的输入节点集和输出节点集，num(N)表示集合N中节点的个数，x，y，z∈N∪RR；节点x的节点向后位置为：$Lop\left(x\right)=\left\{\begin{array}{c}0,x\in RR\\ Lop\left(y\right)+1,x\in In\left(y\right),num\left(Out\right(In\left(y\right)\left)\right)=1\\ max\left(Lop\right(z)+1),z\in Out\left(In\right(x\left)\right),num\left(Out\right(In\left(y\right)\left)\right)>1\end{array}\right.;$所述位置距离Lop的计算步骤包括：1’)找出所述参考流程R中的循环结构，分别用不同的无关节点替换其中互相独立的循环结构，所述无关节点为独立于活动节点的节点，如果两个或者两个以上的循环结构之间存在公共节点，则将所述两个或者两个以上的循环结构分别用同一个无关节点替换，得到参考流程R的无循环图；2’)根据所得无循环图得到图中节点的节点向后位置；3’)将无循环图中的无关节点恢复为步骤1’)替换之前的循环结构，并将无关节点的位置距离赋值给循环结构的节点，得到参考流程R中所有节点的节点向后位置；4’)根据步骤3’)所得到的节点向后位置，得到所述位置距离Lop；3)根据所述MM距离和位置距离Lop得到所述p和R的总距离，并将候选节点集、总距离以及置信度添加至CNS中；4)将CNS中的条目按照所述总距离由小到大进行排序，如果距离相同，则按照置信度由高到低进行排序，然后将位置靠前的多个结果选为最匹配数据条目。