基于共享度和B+树结构的Rete推理方法

基于共享度和b+树结构的rete推理方法
技术领域
1.本发明涉及数据分析技术领域，更具体地说，涉及一种基于共享度和b+树结构的rete推理方法。


背景技术：

2.目前主要采用推理算法都是基于rete算法。rete算法将规则库构建成推理网的形式，包括根节点、alpha网络和beta网络三部分，如图1所示。rete算法将通过规则间的相同域降低规则存储成本，并将匹配结果进行存储，以提升匹配效率。算法将各个规则的条件单元作为基本单元连接形成数据判别网络，然后通过网络过滤和传播事实。
3.rete算法是一种高效的模式匹配算法，是一种以空间换取时间的算法。节点共享是rete网络的一大特性，在构建网络过程中，对于相同的节点，该算法则通过节点共享的方式来避免相同节点的多次匹配，提高系统效率。rete算法的高效之处在于避免了通过alpha存储和beta存储多次匹配相同条件的情况，但是它会增加额外的内存。
4.规则的条件顺序是构建网络的关键要素，条件顺序的变动对网络节点的共享性能有着不可避免的影响。假设如图2所示，存在模式分别为和的两条规则，其中，表示相同类型条件，其网络的节点共享为n。然后，如图3所示，将模式变为即将移到后，此时alpha网络的节点共享为0。
5.此外，beta网络的节点共享也由模式的条件顺序决定。如图4所示，假设存在两条模式为(m,n,o)和(m,n,o,p)的规则，则其网络节点共享为2。如图5所示，如果将(m,n,o,p)改变为(n,o,p,m)，则网络不存在节点共享。
6.此外，beta网络在简化后类似于一棵“多叉树”，当规则数量不断增大时，条件数量随之增大，共享节点的概率也会急剧升高，从而使得大量的beta网络拥有多个连接子节点。可以想象的是，随着规则数量的增大，beta网络的深度也会不断增大，而beta网络的深度与匹配链长度成正比。当匹配链长度增加时，深层beta网络中，存在大量的空节点。这些空节点并不会导致算法网络忽略它的存在，反而每次进行联合匹配的时候都会去查询这些深层节点。在大规模条件下正是这种对大量空节点的匹配导致了算法的性能损耗。
7.如公开号为cn110135586a的中国专利文献公开了rete网络的构建方法、装置、计算机设备和存储介质，通过依据训练事实找出每个规则在占网络内存最小时对应的网络节点的排列顺序，然后将每个所述规则中的网络节点按规则对应的排列顺序进行排序，得到第二规则集，第二规则集中所有的规则均是网络节点按对应的排列顺序排序后的规则，最后将第二规则集中所有具有相同约束条件的alpha节点进行共享，以形成目标rete网络。
8.因此，如何提供另一种降低推理网中冗余节点的方法成为亟需解决的问题。


技术实现要素：

9.针对上述不足，本发明的目的是提供一种基于共享度和b+树结构的rete推理方法、设备、存储介质。
10.本发明提供了如下的技术方案：
11.第一方面，本技术提出一种基于共享度和b+树结构的rete推理方法，包括以下步骤：
12.s1、对条件按共享度进行降序排序，得到按共享度降序排列的条件集合，使用所述条件集合构造alpha网络；
13.s2、通过使用连接与投影的方式与alpha节点进行模式匹配构建beta网络；
14.s3、将alpha节点及beta节点和其在网络中的存储位置相互对应，用于加快能够成功匹配的连接节点的搜索速度。
15.作为第一方面的一种可选的实施方式，在s1中，使用节点共享度模型和模式共享度模型对条件按共享度进行降序排序。
16.进一步地，节点的节点共享度通过引用该节点条件的规则数进行量化。
17.进一步地，设dc为条件c的节点共享度，则
[0018][0019]
其中，
[0020][0021]
作为第一方面的一种可选的实施方式，通过模式共享度模型对有相同节点共享度的条件进一步排序。
[0022]
进一步地，设dm为模式m中所有条件节点共享度的和，则
[0023][0024]
当条件c出现在p个模式中，则条件c的模式共享度d
cm
为
[0025][0026]
其中，d
mi
为模式i的节点共享度；
[0027]
依据模式共享度d
cm
对与节点共享度dc相同的条件降序排列。
[0028]
作为第一方面的一种可选的实施方式，构建beta网络时，根据节点共享度模型，计算alpha分类的共享度，表示为
[0029][0030]
其中，alpha分类中的包含alpha节点的个数为n，其对应的节点共享度分别为(d1，d2，
…
，dn)；
[0031]
对共享度相同的分类，按平均共享度进行排序，表示为
[0032]davgcategory
＝d
category
/n。
[0033]
作为第一方面的一种可选的实施方式，当对reta网络的节点共享性能进行量化时，设rete网络的总节点共享性能为s，则
[0034][0035]
其中，a+b表示网络中节点个数，表示规则集的条件总数。
[0036]
第二方面，本技术提出一种计算机设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现第一方面或第一方面任意一种可能的基于共享度和b+树结构的rete推理方法。
[0037]
第三方面，一种计算机存储介质，所述存储介质存储有计算机程序，其特征在于：所述计算机程序被处理器执行时实现第一方面或第一方面任意一种可能的基于共享度和b+树结构的rete推理方法。
[0038]
采用本发明提供的技术方案，与现有技术相比，具有如下有益效果：本技术基于共享度和b+树的rete推理算法对推理速度有较大的提升。高共享性网络通过节点共享度调整规则的条件和alpha节点的顺序，提高了整个rete网络的节点共享性能，减少了冗余节点，再通过b+树索引加快查找分类的速度。事实推理时，就可以有效减少节点匹配次数，进而缩短推理时间，提高推理效率。综合来看，采用高共享性网络和b+树的rete推理算法可使推理效率提高，而且随着事实集的增加，推理效率会有进一步提升。
附图说明
[0039]
图1为现有技术中rete网络示意图；
[0040]
图2为现有技术中规则变化前alpha网络示意图；
[0041]
图3为现有技术中规则变化后alpha网络示意图；
[0042]
图4为现有技术中规则变化前beta网络示意图；
[0043]
图5为现有技术中规则变化后beta网络示意图；
[0044]
图6为本技术一种实施例中推理方法流程图；
[0045]
图7为本技术一种实施例中b+树索引beta网络示意图；
[0046]
图8为数据集为用频规则集时三种事实匹配算法推理性能对比实验图；
[0047]
图9为数据集为nursery时三种事实匹配算法推理性能对比实验图；
[0048]
图10为数据集为groceries时三种事实匹配算法推理性能对比实验图；
[0049]
图11为数据集为adult时三种事实匹配算法推理性能对比实验图。
具体实施方式
[0050]
为进一步了解本发明的内容，结合附图和实施例对本发明作详细描述。
[0051]
本说明书附图所绘示的结构、比例、大小等，均仅用以配合说明书所揭示的内容，以供熟悉此技术的人士了解与阅读，并非用以限定本发明可实施的限定条件，故不具技术上的实质意义，任何结构的修饰、比例关系的改变或大小的调整，在不影响本发明所能产生
的功效及所能达成的目的下，均应仍落在本发明所揭示的技术内容得能涵盖的范围内。同时，本说明书中所引用的如“上”、“下”、“左”、“右”、“中间”等用语，亦仅为便于叙述的明了，而非用以限定可实施的范围，其相对关系的改变或调整，在无实质变更技术内容下，当亦视为本发明可实施的范畴。
[0052]
实施例一
[0053]
在本实施例中，如图6所示，本技术提出一种基于共享度和b+树结构的rete推理方法，包括以下步骤：
[0054]
s1、对条件按共享度进行降序排序，得到按共享度降序排列的条件集合，使用所述条件集合构造alpha网络；
[0055]
s2、通过使用连接与投影的方式与alpha节点进行模式匹配构建beta网络；
[0056]
s3、将alpha节点及beta节点和其在网络中的存储位置相互对应，用于加快能够成功匹配的连接节点的搜索速度。
[0057]
alpha网络实际上是规则条件的网络，其共享性能依赖条件顺序，首先使用对条件按共享度进行降序排序，获得按共享度降序排列的条件集合之后，可以使用这个集合直接构造alpha网络，不需要再次读取规则集。
[0058]
在推理过程中，传统rete算法将会遍历所有的alpha节点，时间复杂度为o(n)。但在面对车联网环境的超多数据的情况下，其算法的时间复杂度导致系统的推理效率低下。此外，当一个事实进入网络时，触发join节点组合测试。join节点离底层越近，越难将事实与条件相匹配，会出现大量的空节点。空节点的组合测试是无效的，但仍然占用了一个cpu时间。因此，随着规则的不断增加，一个事实进入网络的时间也会增加。为了减缓性能的下降，本文提出了alpha和beta节点之间的b+树结构，如图7所示，本发明提出了alpha和beta节点之间的b+树结构，将alpha节点及beta节点和其在网络中的存储位置相互对应，以加快对能够成功匹配的连接节点的搜索速度。那么在rete网络事实匹配的过程中，对于一些节点的查找工作将在的o(1)时间复杂度之内完成。
[0059]
实施例二
[0060]
在本实施例中，进一步地，在步骤s1中，使用节点共享度模型和模式共享度模型对条件按共享度进行降序排序。节点共享度代表一个节点需要被共享的程度，这里使用引用该节点条件的规则数进行量化。
[0061]
设dc为条件c的节点共享度，则
[0062][0063]
其中，
[0064][0065]
在理想情况下，整个rete网络中不存在相同节点，则节点的共享度为该条件出现的次数，显然dc越大，条件的共享程度应当越高。但在实际中，节点共享度相同是比较普遍的现象，当同一节点共享度的条件数量很多时，其排序对rete网络的节点的共享性能影响很大。因此，需要对有相同节点共享度的条件进一步排序，因此引入模式共享度的概念，通
过模式共享度模型对有相同节点共享度的条件进一步排序。
[0066]
具体地，设dm为模式m中所有条件节点共享度的和，则
[0067][0068]
当条件c出现在p个模式中，则条件c的模式共享度d
cm
为
[0069][0070]
其中，d
mi
为模式i的节点共享度；
[0071]
模式共享度反映了其他条件对该条件的依赖情况，d
cm
越大，依赖程度越高。而依赖程度越高，其共享度就越高，顺序应当靠前。因此，可以依据模式共享度d
cm
对节点共享度dc相同的条件降序排列，来区分相同节点共享度的条件。
[0072]
进一步地，beta网络使用连接和投影的方式进行模式匹配，连接的对象是alpha节点而不是条件，因此在考虑条件节点共享度的同时也需要考虑alpha节点的共享度。根据节点共享度模型，计算整个alpha分类的共享度，表示为
[0073][0074]
其中，alpha分类中的包含alpha节点的个数为n，其对应的节点共享度分别为(d1，d2，
…
，dn)；
[0075]
对共享度相同的分类，按平均共享度进行排序，表示为
[0076]davgcategory
＝d
category
/n。
[0077]
实施例三
[0078]
在本实施例中，进一步地，为了体现算法的优化效果，当对reta网络的节点共享性能进行量化时，设rete网络的总节点共享性能为s，则
[0079][0080]
其中，a+b表示网络中节点个数，表示规则集的条件总数。
[0081]
使用构建的用频规则集和uci的nursery、groceries和adult作为测试数据集，其中用频规则集包含100条用频规则，使用xml格式的语言对规则进行格式化描述；nursery数据集包含了8维的12960条数据，最后挖掘出1000条规则；groceries数据集包含了17维的9835条数据，通过apriori算法挖掘出10000条规则；adult数据集包含了14维的48842条数据，通过apriori算法，挖掘出100000规则。对于挖掘出来的规则，我们进行了统一的编码，条件之间使用空格分隔，条件和结果之间使用逗号分隔，编码的规则如下：
[0082]
rulei＝[cond1,cond2
……
condn]＝》[result]。
[0083]
对于每一个数据集，我们使用传统方法在原规则集、传统方法在打乱的规则集和改进方法在原规则集中分别进行实验，每个实验均进行3次，其结果如表1所示。其中，rete组表示使用传统rete算法构建网络，retedisorder组表示在打乱的规则集上使用传统rete
算法构建网络，srete组表示使用基于共享度模型的rete算法构建网络。
[0084]
表1网络构建对比实验结果(s)
[0085][0086]
从表1可以看出，对于用频规则集而言，使用优化之后的基于节点共享模型的网络构建算法，其节点共享性能提升了41％。此外，在uci的数据集中，rete网络中节点共享性都有提升，特别是对于大数据集来说，提升的幅度更大。在adult数据集中,在原数据集上提升了36％，在打乱的数据集上提升了36％；在数据集groceries中，在原数据集上提升了18％，在打乱的数据集上提升了38％。
[0087]
在构建时间上，srete/b+算法构建时间与传统的算法相比，随着规则数量的增加，主要原因是增加了条件排序和alpha分类节点排序，但是增加的时间较其获得的效果(节点共享性能)来说，其代价是比较小的。在实际应用中，规则集是稳定且不轻易发生变化的，因此，rete网络的构建频率很低，网络构建时间不是衡量推理机性能的重要指标，其时间增加的幅度是完全可以接受的。
[0088]
使用在rete网络构建实验中的四个数据集，即用频规则集、nursery、groceries和adult数据集进行事实匹配算法的对比实验，实验条件分别为：在传统rete网络(原规则集)上使用传统事实匹配算法推理，记为rete；在传统rete网络(随机规则集)上使用传统事实匹配算法推理，记为retedisorder；在共享性网络上使用基于b+树的rete推理算法，记为srete/b+。
[0089]
实验分为五组，在用频规则集中，分别选取100，200，300，400，500条数据；nursery数据集中，分别选取1000，2000，3000，4000，5000条数据；groceries数据集中，分别选取10000，20000，30000，40000，50000条数据；adult数据集中，分别选取100000，200000，300000，400000，500000条数据。以上实验均进行三次取均值，结果如图8-11所示。
[0090]
可以看出，高共享性网络和基于b+树的rete推理算法对推理速度都有较大的提升。高共享性网络通过节点共享度调整规则的条件和alpha节点的顺序，提高了整个rete网络的节点共享性能，减少了冗余节点，再通过b+树索引加快查找分类的速度。事实推理时，就可以有效减少节点匹配次数，进而缩短推理时间，提高推理效率。综合来看，采用高共享性网络和b+树的rete推理算法可使推理效率提高，而且随着事实集的增加，推理效率会有
进一步提升。
[0091]
本技术还提出一种计算机设备，包括存储器、处理器以及存储在存储器中并可在处理器上运行的计算机程序，处理器执行计算机程序时实现上述实施例中的基于共享度和b+树结构的rete推理方法。
[0092]
本技术还提出一种计算机存储介质，存储介质存储有计算机程序，计算机程序被处理器执行时实现上述实施例中的基于共享度和b+树结构的rete推理方法。
[0093]
以上示意性的对本发明及其实施方式进行了描述，该描述没有限制性，附图中所示的也只是本发明的实施方式之一，实际的结构并不局限于此。所以，如果本领域的普通技术人员受其启示，在不脱离本发明创造宗旨的情况下，不经创造性的设计出与该技术方案相似的结构方式及实施例，均应属于本发明的保护范围。

技术特征：
1.一种基于共享度和b+树结构的rete推理方法，其特征在于，包括以下步骤：s1、对条件按共享度进行降序排序，得到按共享度降序排列的条件集合，使用所述条件集合构造alpha网络；s2、通过使用连接与投影的方式与alpha节点进行模式匹配构建beta网络；s3、将alpha节点及beta节点和其在网络中的存储位置相互对应，用于加快能够成功匹配的连接节点的搜索速度。2.根据权利要求1所述的基于共享度和b+树结构的rete推理方法，其特征在于：在s1中，使用节点共享度模型和模式共享度模型对条件按共享度进行降序排序。3.根据权利要求2所述的基于共享度和b+树结构的rete推理方法，其特征在于：节点的节点共享度通过引用该节点条件的规则数进行量化。4.根据权利要求3所述的基于共享度和b+树结构的rete推理方法，其特征在于：设d
c
为条件c的节点共享度，则其中，5.根据权利要求4所述的基于共享度和b+树结构的rete推理方法，其特征在于：通过模式共享度模型对有相同节点共享度的条件进一步排序。6.根据权利要求5所述的基于共享度和b+树结构的rete推理方法，其特征在于：设d
m
为模式m中所有条件节点共享度的和，则当条件c出现在p个模式中，则条件c的模式共享度d
cm
为其中，d
mi
为模式i的节点共享度；依据模式共享度d
cm
对与节点共享度d
c
相同的条件降序排列。7.根据权利要求4-6中任意一项所述的基于共享度和b+树结构的rete推理方法，其特征在于：构建beta网络时，根据节点共享度模型，计算alpha分类的共享度，表示为其中，alpha分类中的包含alpha节点的个数为n，其对应的节点共享度分别为(d1，d2，
…
，d
n
)；对共享度相同的分类，按平均共享度进行排序，表示为d
avgcategory
＝d
category
/n。8.根据权利要求7所述的基于共享度和b+树结构的rete推理方法，其特征在于：当对
reta网络的节点共享性能进行量化时，设rete网络的总节点共享性能为s，则其中，a+b表示网络中节点个数，表示规则集的条件总数。9.一种计算机设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，其特征在于：所述处理器执行所述计算机程序时实现如权利要求8所述的基于共享度和b+树结构的rete推理方法。10.一种计算机存储介质，所述存储介质存储有计算机程序，其特征在于：所述计算机程序被处理器执行时实现如权利要求8所述的基于共享度和b+树结构的rete推理方法。

技术总结
本发明属于数据分析技术领域，更具体地说，涉及一种基于共享度和B+树结构的Rete推理方法。方法包括以下步骤：S1、对条件按共享度进行降序排序，得到按共享度降序排列的条件集合，使用所述条件集合构造Alpha网络；S2、通过使用连接与投影的方式与Alpha节点进行模式匹配构建Beta网络；S3、将Alpha节点及Beta节点和其在网络中的存储位置相互对应，用于加快能够成功匹配的连接节点的搜索速度。本申请通过节点共享度调整规则的条件和Alpha节点的顺序，提高了整个Rete网络的节点共享性能，减少了冗余节点，再通过B+树索引加快查找分类的速度。再通过B+树索引加快查找分类的速度。再通过B+树索引加快查找分类的速度。


技术研发人员：张建照 陈勇 王为念 周宇航
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2023.07.04
技术公布日：2023/9/19