实体增强规则的挖掘方法、装置、设备及介质与流程

本技术适用于大数据挖掘，尤其涉及一种实体增强规则的挖掘方法、装置、设备及介质。

背景技术：

1、逻辑规则在数据清洗、关联分析、知识发现、在线推荐、药物发现和制造业等领域得到了广泛的应用。为了实际使用规则，我们必须从现实数据中发现高质量的规则。目前已经研究了许多规则发现方法，这些方法通常将数据集d作为输入，并从d中挖掘或学习规则，使规则具有高于预定义阈值的支持度和置信度，支持度衡量的是规则可以应用的频率，置信度评估的是前提条件和结果的关联程度。然而，工业界的从业者对以前的规则发现方法提出了以下问题：

2、(1)过多的不相关规则。之前的方法通常会返回d上满足的整个规则集σall，其中，每个规则的支持度和置信度都足够高且这个集合通常相当大。例如，从一个具有27个属性和368个元组的小数据集中，发现了128726个函数依赖规则。用户经常被过多的规则所淹没，不得不花费大量的时间手动检查和选择符合他们需求的规则。而且，从业者往往已经对自己的应用形成了先验知识，甚至经过多年的实践积累了一定的规则。因此，从业者想要符合需要的、未知/新颖的规则，而不是那些已经知道的或常识性的规则。

3、(2)高昂的成本。从d中挖掘整个规则集是非常昂贵的。之前的方法枚举所有的候选规则，对于每个规则都通过在整个数据集上应用来验证其支持度和置信度。例如，即使使用20台机器，在具有168万个元组的数据集上也需要>3小时。此外，将大量挖掘的规则应用于完整的数据集通常也是昂贵的。

4、(3)冗余的规则。为了减少不相关规则的数量和规则发现的成本，之前的方法研究了top-k规则发现，根据客观度量(支持度和置信度)和主观度量(与用户需求的相关性)找到排名靠前的规则。然而，由于返回的规则往往彼此过于“同质”，因此，通常被认为是冗余。

5、典型的规则发现算法以深度优先或者广度优先搜索为基础，大致上可分为以下两步：(1)在关系数据中发现所有满足支持度/置信度阈值的ree规则σall；(2)从σall中挑选k条规则组成规则子集σ，使得目标函数f(σ)最大化。

6、第一步：对于每一个ree结果e，这些方法会储存两个谓词集合：psel和pre。其中psel存的是已经被选择组成ree条件的谓词，而pre存的是待选谓词。最开始，psel为空集，pre是所有可能的谓词集合。然后规则发现算法通过深度优先或者广度优先的方式遍历搜索空间，迭代地选择pre里的谓词加入到psel中去，直到所有规则检查完毕。他们的本质是一个在数据上枚举所有谓词排列组合并逐一验证的过程。对于所有可能的谓词，任意的抽取一个或者多个出来都可能和ree结果e组成有效的规则。因此为了进行规则发现，已有方法需要把谓词的所有排列组合都试一遍。从而得到所有满足支持度/置信度阈值的ree规则。

7、第二步：σall算好之后，再次枚举σall里面所有的k条规则的子集，对每一个规则子集，我们再计算他们的排序得分f(σ)，最终返回得分最高的k个规则。

8、基于暴力枚举法的top-k规则发现方法的主要缺点是它的计算效率很低。用户为了得到得分最高的k条规则的规则子集，现有技术首先需要将满足数据的所有可能的规则都枚举一遍并进行计算对应的支持度/置信度，才能得到全部规则σall。然而，在实际中用户往往只对排名靠前的规则感兴趣，不应付出遍历所有规则的代价。在实践中，σall的规模常常是数以百万计的。其次，为了得到σall里面得分最高的k条规则的规则子集，现有技术需要再次枚举σall里面所有的k条规则的规则子集，对每个规则子集计算排序得分f(σ)。当数据规模庞大的时候，这样暴力尝试法的效率毫无疑问是非常低的。即使σall只有100条规则，从中选10条规则需要枚举1.7*1013种规则组合的子集，即使每个子集仅需1毫秒的时间处理，处理完所有子集组合也需要548年。

9、因此，如何在规则挖掘中降低不必要干扰，从而提高规则发现效率成为亟待解决的问题。

技术实现思路

1、有鉴于此，本技术实施例提供了一种实体增强规则的挖掘方法、装置、设备及介质，以解决如何在规则挖掘中降低不必要干扰，从而提高规则发现效率的问题。

2、第一方面，本技术实施例提供一种实体增强规则的挖掘方法，所述挖掘方法包括：

3、初始化初始挖掘规则集合和已使用谓词集合为空集，将候选谓词集合中每一个候选谓词分别与所述已使用谓词集合合并，得到对应候选谓词的已使用谓词集合，使用每个候选谓词的已使用谓词集合中所有谓词，结合已知规则的规则目标，构建得到对应的候选规则；

4、根据预设的相关性度量和预设的多样性度量，对每个候选规则及其扩展得到的规则进行收益评分，得到每个候选规则对应收益得分上界和收益得分下界；

5、计算每个候选规则的可信度，根据每个候选规则的收益得分上界、收益得分下界和可信度，确定候选最佳规则子集和下一轮迭代候选规则子集，将候选最佳规则子集中每个规则分别添加至所述初始挖掘规则集合，得到每个规则对应的更新规则集合；

6、计算每个更新规则集合相较于所述初始挖掘规则集合的收益提升量，确定所述收益提升量最高的更新规则集合对应的规则为本轮迭代的最佳规则，将所述最佳规则添加至所述初始挖掘规则集合，得到更新的挖掘规则集合，将所述候选最佳规则子集中除最佳规则以外的规则添加至所述下一轮迭代候选规则子集，得到更新的下一轮迭代候选规则子集；

7、在下一轮迭代中，以所述更新的下一轮迭代候选规则子集进行扩展搜索，得到扩展规则，将所述扩展规则作为所述候选规则，并将所述更新的挖掘规则集合作为所述初始挖掘规则集合，返回执行计算每个候选规则的可信度，直至所述更新的挖掘规则集合中规则条数达到预设条数或者达到预设迭代次数，得到更新的挖掘规则集合。

8、第二方面，本技术实施例提供一种实体增强规则的挖掘装置，所述挖掘装置包括：

9、候选规则构建模块，用于初始化初始挖掘规则集合和已使用谓词集合为空集，将候选谓词集合中每一个候选谓词分别与所述已使用谓词集合合并，得到对应候选谓词的已使用谓词集合，使用每个候选谓词的已使用谓词集合中所有谓词，结合已知规则的规则目标，构建得到对应的候选规则；

10、上下界计算模块，用于根据预设的相关性度量和预设的多样性度量，对每个候选规则及其扩展得到的规则进行收益评分，得到每个候选规则对应收益得分上界和收益得分下界；

11、规则筛选模块，用于计算每个候选规则的可信度，根据每个候选规则的收益得分上界、收益得分下界和可信度，确定候选最佳规则子集和下一轮迭代候选规则子集，将候选最佳规则子集中每个规则分别添加至所述初始挖掘规则集合，得到每个规则对应的更新规则集合；

12、规则挖掘更新模块，用于计算每个更新规则集合相较于所述初始挖掘规则集合的收益提升量，确定所述收益提升量最高的更新规则集合对应的规则为本轮迭代的最佳规则，将所述最佳规则添加至所述初始挖掘规则集合，得到更新的挖掘规则集合，将所述候选最佳规则子集中除最佳规则以外的规则添加至所述下一轮迭代候选规则子集，得到更新的下一轮迭代候选规则子集；

13、循环迭代模块，用于在下一轮迭代中，以所述更新的下一轮迭代候选规则子集进行扩展搜索，得到扩展规则，将所述扩展规则作为所述候选规则，并将所述更新的挖掘规则集合作为所述初始挖掘规则集合，返回执行计算每个候选规则的可信度，直至所述更新的挖掘规则集合中规则条数达到预设条数或者达到预设迭代次数，得到更新的挖掘规则集合。

14、第三方面，本技术实施例提供一种计算机设备，所述计算机设备包括处理器、存储器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如第一方面所述的挖掘方法。

15、第四方面，本技术实施例提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如第一方面所述的挖掘方法。

16、本技术实施例与现有技术相比存在的有益效果是：本技术初始化初始挖掘规则集合和已使用谓词集合为空集，将候选谓词集合中每一个候选谓词分别与所述已使用谓词集合合并，得到对应候选谓词的已使用谓词集合，使用每个候选谓词的已使用谓词集合中所有谓词，结合已知规则的规则目标，构建得到对应的候选规则；根据预设的相关性度量和预设的多样性度量，对每个候选规则及其扩展得到的规则进行收益评分，得到每个候选规则对应收益得分上界和收益得分下界；计算每个候选规则的可信度，根据每个候选规则的收益得分上界、收益得分下界和可信度，确定候选最佳规则子集和下一轮迭代候选规则子集，将候选最佳规则子集中每个规则分别添加至所述初始挖掘规则集合，得到每个规则对应的更新规则集合；计算每个更新规则集合相较于所述初始挖掘规则集合的收益提升量，确定所述收益提升量最高的更新规则集合对应的规则为本轮迭代的最佳规则，将所述最佳规则添加至所述初始挖掘规则集合，得到更新的挖掘规则集合，将所述候选最佳规则子集中除最佳规则以外的规则添加至所述下一轮迭代候选规则子集，得到更新的下一轮迭代候选规则子集；在下一轮迭代中，以所述更新的下一轮迭代候选规则子集进行扩展搜索，得到扩展规则，将所述扩展规则作为所述候选规则，并将所述更新的挖掘规则集合作为所述初始挖掘规则集合，返回执行计算每个候选规则的可信度，直至所述更新的挖掘规则集合中规则条数达到预设条数或者达到预设迭代次数，得到更新的挖掘规则集合。

17、通过设置收益得分上下界和可信度对候选规则进行筛选，将有效的规则通过收益提升的方式进行判定，并且将已经处理过且未来扩展无法达到最佳的规则进行排除，限定了下一轮迭代的规则，降低不必要干扰，避免了多次迭代的规则冗余处理，由于规则处理量的降低有效地提高了处理效率。