面向海量规则的产生式系统研究与实现

论文摘要

基于产生式规则发展而来的业务规则和产生式系统产品化的成果——规则引擎,正被越来越多的企业用来描述和维护业务知识、构建企业级系统。规则引擎技术能够实现企业级系统业务逻辑和业务规则的分离,从而将业务规则的频繁变更与信息系统解耦,增强了专家系统、企业级信息系统等应用系统的智能性、健壮性和适应性。随着所要解决的领域问题范围和复杂度的扩大,专家系统知识库和企业应用系统规则库中的知识规模急剧增长、结构日趋复杂,亟待具有更高效处理能力的产生式系统,即规则引擎来应对这种挑战。为了应对这种海量知识所对应海量规则的处理挑战,要求产生式系统能够提供更快速更精确的匹配和处理能力。采用分布式计算、并行计算的思想来构建更有效的产生式系统架构,并结合更高效的算法来加快模式匹配,是实现对海量规则高效处理的一种必然趋势。本文通过对现有产生式系统中海量规则处理方法的研究分析,提出了基于MapReduce编程模型和改进Rete算法的海量规则分布式匹配方法,实现了基于干扰分析的多重规则触发方法,并开发了面向海量规则的产生式系统原型。本文的主要工作包括以下几个方面的内容：1.提出了Alpha网络二重哈希过滤方法,并结合Beta节点索引技术来改进Rete算法,以加快集群环境中每个计算节点的模式匹配过程。该方法将FactType节点引入Rete网络,在Root节点构建“事实类型-FactType节点”的映射,在FactType节点建立“属性约束-Alpha节点”的映射,利用这样的二重哈希过滤机制来加快事实集在Alpha网络中的过滤。同时,还在Beta节点的输入内存中以加入的事实对象为参数计算得到的索引来建立哈希表,以避免Beta节点连接操作中不必要的迭代。2.提出了基于MapReduce的分布式规则匹配方法,以应对海量规则的匹配需求。本文在分析产生式规则的结构和面向集群的规则分解原则基础上,基于规则条件部分的模式元素将规则分解为子规则；在考虑Worker机负载的情况下,将子规则集分配给集群中的Worker机,并采用改进的Rete算法来构建Map Worker的Rete网络；将工作内存的改变封装为Token,并基于规则分解信息将这些Token集进行有效分发；然后在Map过程中进行Token集与子规则集的匹配,并在Reduce过程中归并和汇总子规则的匹配情况。3.提出了基于干扰分析的多重规则触发方法,以解决传统冲突解决策略所造成产生式推理归结阶段的性能瓶颈。针对这种多重规则触发方法引发的工作内存不一致问题,本文首先在详细分析规则间依赖关系的基础上,给出了规则间干扰关系的形式化定义；接着基于访问请求控制的方法,通过访问请求入列和兼容规则触发的过程,选择出更大容量的兼容规则集。在保证并行规则集能够串行化的基础上,该方法提升了产生式系统归结阶段并行性。4.在上述关键技术研究的基础上,构建了面向海量规则的产生式系统总体架构,并开发了相应的原型系统。本文还对该系统进行性能测试实验,实验结果表明并行匹配和多重触发的方法能够提高产生式系统的规则处理能力,能够在一定程度上应对海量规则的处理需求。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 选题背景
• 1.2 论文研究意义
• 1.3 国内外研究现状
• 1.4 本文主要研究内容
• 1.5 论文组织结构
• 第2章 产生式系统与Rete算法概述
• 2.1 产生式系统概述
• 2.1.1 产生式系统的应用背景
• 2.1.2 产生式系统的优点
• 2.1.3 产生式系统的知识表示
• 2.1.4 产生式系统的架构
• 2.1.5 产生式系统的冲突解决策略
• 2.2 Rete模式匹配算法概述
• 2.2.1 Rete算法的思路
• 2.2.2 Rete算法的匹配网络
• 第3章 Rete模式匹配算法改进研究
• 3.1 Rete算法改进研究现状
• 3.2 本文对Rete算法的改进
• 3.2.1 Alpha网络二重哈希过滤机制
• 3.2.2 Beta节点索引技术
• 3.3 改进Rete算法的应用
• 第4章 基于MapReduce的分布式规则匹配研究
• 4.1 分布式产生式系统研究现状
• 4.1.1 基于专用机的分布式架构
• 4.1.2 基于集群的分布式架构
• 4.2 规则的预处理和分配
• 4.2.1 规则的分解
• 4.2.2 规则的分配
• 4.3 Token的预处理和分配
• 4.4 Map任务
• 4.5 Reduce任务
• 第5章 基于干扰分析的多重规则触发与执行
• 5.1 规则间干扰关系概述
• 5.2 多重规则触发研究现状
• 5.3 基于访问请求控制的多重规则触发算法
• 5.3.1 算法基本思路
• 5.3.2 相关数据结构
• 5.3.3 算法请求阶段
• 5.3.4 算法触发阶段
• 5.3.5 串行化验证
• 5.4 多重规则触发方法的并行性比较
• 5.5 多重规则的执行
• 第6章 分布式产生式系统实现及其性能测试
• 6.1 系统总体架构
• 6.1.1 分布式产生式系统架构
• 6.1.2 分布式产生式系统应用环境
• 6.1.3 面向海量规则的产生式系统架构
• 6.2 分布式产生式系统的实现
• 6.2.1 Master机实现
• 6.2.2 Worker机实现
• 6.2.3 系统I/O实现
• 6.2.4 规则编译模块实现
• 6.2.5 规则执行模块实现
• 6.3 产生式系统辅助使用工具的实现
• 6.3.1 规则管理工具的实现
• 6.3.2 规则管理工具的实现
• 6.4 性能测试及分析
• 6.4.1 给定事实数量的测试
• 6.4.2 给定规则数量的测试
• 第7章 总结与展望
• 7.1 本文研究总结
• 7.2 未来工作展望
• 参考文献
• 附录
• 致谢
• 攻读学位期间参加的科研项目和成果