RETE算法国内外研究现状(2)
时间:2018-04-19 21:28 来源:毕业论文 作者:毕业论文 点击:次
RETE算法自从1979年首次被提出来，也经历了三十多年的历史，期间也经历了各种的改进和实现。其中包括了最明了的对于自身的RETE网络进行优化构造，同时也包括了一些不确定研究，模糊处理以及并行化的探讨。期间当然经历了很多困难，但是还是取得了一些进步。 1 结构优化 结构优化，就如其定义的名字一样，就是对构建的RETE网络进行优化，以便于提高RETE网络的灵活性和高效快速匹配。其中包含了：（1）混合逻辑符的处理。逻辑符号就是指and, not, or等逻辑符号。最原始的RETE算法设计时，只考虑了and逻辑符号。但慢慢的通过研究，RETE算法被设计的可以对除了and的其它逻辑符号进行操作。例如，在DROOLS中，就被设计成可以同时支持and和or逻辑符号的混合操作，但是DROOLS只是简单地在or逻辑符号之处，将规则切割成多条规则，这种方法将会造成大量的切割开销。（2）规则LHS部分的重排序。LHS部分的顺序就是指条件中各个模式的排列顺序，但这样会影响到条件各个模式进行连接操作的执行顺序，后续影响就是会造成中间存储状态大小的改变，这也会成为规则匹配效率的决定性因素。连接顺序不同将会影响到共享结点的数量，从而影响到匹配的效率。（3）索引方法。索引方法就是指在RETE网络中，在当前结点之中，建立对后继结点的索引，这样做的好处就是，当事实进行匹配时，如果匹配成功，就可以快速找到当前结点的后继结点继续进行匹配，而无需一个一个地进行查找，这将节省大量的时间，提高匹配的效率。DROOLS在RETE算法面向对象[7]的版本RETE-OO算法。此算法中就对类型结点（type-node）结点中加入了对后继alpha结点的索引，以事实（fact）属性为key，alpha结点为value，这样事实（fact）在通过了类型结点（type-node）的匹配验证之后，就可以顺序的找到后继结点alpha结点，继而进行后续匹配。相同的道理，对于beta结点中的左右存储区建立索引，进行快速查询。 2 功能扩展 RETE算法最初的设计，只是用来对于确定性的一阶布尔逻辑下的进行规制匹配操作。但是随着广泛应用其它逻辑，缺失数据的问题，逻辑模糊等问题的不断出现，对于传统的规则引擎的功能需求提出了更高的要求。为了解决这些复杂的问题，近年来对RETE算法不断的改进，进行了必要的扩展。（1）能够处理其余逻辑。RETE算法设计之时，只考虑了一阶的布尔逻辑的操作，因此最初的RETE算法只能对一阶布尔逻辑的表达式进行操作。近些年，RETE算法已经被扩展成能够处理其它的逻辑，并且产生了多种版本，比如像F-逻辑（F-logic），三值布尔逻辑（3-Valued Boolean）等。Florian等人研究在演绎数据库中用RETE算法进行面向集合的自底向上的规则匹配评估计算。而三值布尔逻辑广泛用于缺失数据的处理。（2）对于包含时间信息事件的处理。RETE算法是通过事实（fact）来表示当前的状态，但是有些应用中包含的一些事件流，它们中间的时间在事件的并发执行中却有着至关重要的作用。但是如前文所提到的，RETE算法其中包含的一个缺陷就是：RETE算法不提供对时间敏感模式表达的支持。这样就会催生出对于包含事件处理的RETE算法研究。其中的一种方法就是：引入包含时间戳的事件和事件之间的时间间隔的约束的概念，使得RETE算法可以对事实和事件在同一时间进行处理[6]。 3 特殊数据处理 1.关于瑕疵数据以及其不确定性推理：在许多场景之下，产生式系统对问题领域已经表现得很成功，可以用基于逻辑的语言表示这些领域的知识。一个传统逻辑中的问题，判别结果不是正确就是错误。但是在现实生活中，许多问题是比较模糊的或不明确的，也就是说问题本身就是不怎么准确，我们把这种问题本身称之为瑕疵数据。例如，有这么一条规则“如果成绩好，那么容易拿到高薪”，那么规则中“成绩好”“容易”“高薪”这些概念，在产生式系统中就不能被精确的表达出来。在这种情况下，最初的RETE算法就变得非常没有优势，因为RETE算法的语义表达能力是非常有限的。因此就必须对RETE算法进行改进，以便于处理这种瑕疵数据和逻辑的不确定性。 (责任编辑：qin) |