CLIPS专家系统性能改进

论文摘要

众所周知,为了达到良好的预测效果,一个必须的条件是大量的知识。我们可以使用人工输入、机器学习等方法来获得大量的知识,这些知识大都表示为if-then的形式。随着规则引擎系统中知识的不断增加,系统运行的速度也会大幅度的下降。这是因为,规则越多,将规则与当前事实匹配所花费的时间也就越多。同理,事实越多,匹配所花费的时间也越多。CLIPS专家系统是一款开源的规则推理引擎,它采用了RETE模式匹配算法。RETE算法通过空间换时间的方式来提高效率。该算法记录了所有匹配的中间结果,每次插入、删除或者修改工作内存中的事实对象都要对相关的部分匹配进行更新并在网络中传播。由于保存了大量的中间结果,在删除或者修改时都需要将旧的事实插入到网络中传播并与之前的部分匹配进行比较,删除掉相同部分,接着再插入新的事实并在网络中传播。这种方式导致该算法对处理大规模知识库有一定负面的影响。本文针对CLIPS这一不足,在事实处理过程阶段分别采用TREAT算法、记录中间节点、对中间节点进行散列、增加规则分组的特性等方法进行改进。TREAT算法削减了beta存储区,当事实通过模式匹配生成部分匹配保存在alpha存储区之后直接更新冲突集。由于TREAT算法降低了网络的复杂程度,每次插入、删除或者修改时对网络的维护时间会有所减少,但测试结果表明TREAT算法的效率不如原有算法。本文认为是算法实现方式和测试用例选择不当造成的。记录中间节点可以减少删除时对中间结果的匹配和在网络中的传输。对中间节点进行散列即在原CLIPS对节点元素进行散列的基础上增加对alpha存储节点、模式节点的散列。该方法可以减少匹配及传播过程中对中间节点查找、比较和复制的时间开销。为CLIPS增加了规则分组的特性就可以相对减少每个规则集中的规则数,从而在一定程度上提高CLIPS性能。实验结果表明,对原CLIPS算法实现方式的改进使性能有所提升。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题的背景和意义
• 1.2 国内外研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 本文研究的内容
• 第2章 规则引擎
• 2.1 CLIPS专家系统
• 2.1.1 基于规则的专家系统
• 2.1.2 CLIPS的应用
• 2.1.3 CLIPS软件架构
• 2.2 RETE算法
• 2.2.1 规则的编译
• 2.2.2 规则的执行
• 2.2.3 RETE算法的应用
• 2.3 TREAT算法
• 2.3.1 TREAT算法简介
• 2.3.2 TREAT算法的加速比
• 2.4 本章小结
• 第3章 CLIPS改进的设计与实现
• 3.1 算法的改进
• 3.1.1 功能结构
• 3.1.2 规则转化模块
• 3.1.3 工作内存模块
• 3.1.4 条件评估模块
• 3.2 算法实现方式的改进
• 3.2.1 结点记录
• 3.2.2 alpha结点散列
• 3.2.3 规则优先级分组
• 3.2.4 CLIPS规则集
• 3.3 本章小结
• 第4章 性能测试和分析
• 4.1 测试环境搭建
• 4.2 测试用例
• 4.3 测试结果及分析
• 4.3.1 原CLIPS的测试结果
• 4.3.2 TREAT算法的测试结果
• 4.3.3 算法实现方式改进结果
• 4.4 本章小结
• 结论
• 参考文献
• 附录 1 TREAT 算法流程图
• 附录 2 测试用例
• 附录 3 测试结果
• 致谢