-
摘要: 专家系统是人工智能领域的重要分支，其中知识表示和知识推理是专家系统的重要组成部分.Rete算法是一种高效的模式匹配算法，能够解决专家系统中推理效率的问题，但是Rete算法在构建Rete网络和推理过程中存在空间和性能方面问题.本文采取有穷自动机理论的思想，阐述了Rete算法中的模式共享度和节点共享度模型，提出了一种Rete网络构建和推理算法来降低Rete网络的复杂度，提升Rete网络推理的速度.最后实验结果表明，本算法能够降低网络复杂度，提升推理速度.Abstract: Expert system is an important brunch of artificial intelligence. Knowledge representation and inference engine is an important part of the expert system. As an efficient pattern-matching algorithm, Rete algorithm can solve the ratiocination efficiency problem in expert system. However, there always exist the problems such as storage and efficiency in building and using Rete network. In this paper, we introduce the idea of finite automata, and the pattern sharing degree and node sharing degree model into Rete algorithm. We propose a Rete network construction and inference algorithm to reduce the complexity of Rete network and improve the speed of Rete network inference. Finally, experimental results show that it can reduce the complexity of the network greatly and raise the inference speed.
-
Key words:
- Expert system /
- Rete /
- finite automaton /
- ratiocination machine
-
专家系统(Expert system)是一种运用专家提供的领域知识进行推理和判断, 求解那些需要专家才能解决的复杂问题的智能计算机程序[1].专家系统在人工智能领域应用广泛.在很多领域, 专家系统发挥了很大作用, 例如智能医疗和决策规划等[2].
专家系统是推理机和知识库的结合[3], 知识库用来保存专门的知识, 推理机使用知识库里的知识来解决问题.一直以来, 专家系统面临两个核心问题[4]:知识表示和知识推理.其中, 知识推理是专家系统中的关键技术, 也是近些年来优化专家系统的主要方向.
Rete算法是Forgy针对专家系统中推理问题提出的一种解决方法[5], 作为一种前向链形推理算法, 其核心思想是采用增量匹配的概念, 根据内容动态构造匹配树, 以达到显著降低计算量的效果.目前大部分规则推理引擎都使用Rete算法作为核心推理算法.但Rete算法也存在诸如推理网络构造复杂、推理速度过低等问题.在生成推理网络的时候, Rete算法没有考虑规则中节点的分布情况, 生成的规则网络可能过于复杂, 导致存储Rete网络的代价过大, 影响Rete网络的推理速度.
针对Rete算法推理过程中存在的问题, 本文提出了一种基于节点共享度模型的高共享性Rete网络构建算法(Rete algorithm based on the shared degree model, ReteSDM), 结合自动机理论优化推理系统中Rete网的构建过程.实验结果显示, 该算法有效提高Rete网络的节点共享性能, 减少冗余节点, 提升推理效率.
1. 有穷自动机理论和Rete算法
1.1 有穷自动机理论
有穷自动机理论最先是在讨论计算理论中的问题时被提出[6].它用来描述计算能力和资源极其有限的计算机模型[7].
首先给出确定型有穷自动机(Deterministic finite automaton, DFA)的形式化定义[8].
定义1. 确定型有穷自动机是一个5元组( $Q$ , $\Sigma$ , , $q_{0}$ , $F$ ), 其中
1) $Q$ 是一个有穷集合, 称为状态集;
2) $\Sigma$ 是一个有穷集合, 称为字母表;
3) $\delta :Q \times \Sigma \to Q$ 称为转移函数;
4) ${q_0} \in Q$ 称为起始状态;
5) $F \subseteq Q$ 称为接受状态集.
非确定型有穷自动机的形式化定义与确定型有穷自动机的形式化定义类似, 不同点在于两者的转移函数.下面给出非确定型有穷自动机(Non deterministic finite automaton, NFA)的形式化定义[9].
定义2. 非确定型有穷自动机是一个5元组( $Q$ , ${\Sigma}$ , ${\delta}$ , $q_{0}$ , $F$ ), 其中
1) $Q$ 是一个有穷集合, 称为状态集;
2) ${\Sigma}$ 是一个有穷集合, 称为字母表;
3) $\delta :Q \times {\Sigma _\varepsilon } \to P(Q)$ 称为转移函数;
4) ${q_0} \in Q$ 称为起始状态;
5) $F \subseteq Q$ 称为接受状态集.
这里, 称 $P(Q)$ 为 $Q$ 的幂集, 称为 ${\Sigma _\varepsilon }$ .
在DFA中, 转移函数取一个输入符号和一个状态, 产生下一个状态.而在NFA中, 状态函数取一个输入符号或者空串, 以及一个状态, 产生下一个状态的集合.可以证明, 每一台非确定型有穷自动机都等价于某一台确定型有穷自动机.
1.2 Rete算法
Rete算法是一种前向规则快速匹配算法, 其匹配速度与规则数目无关.在该算法中, 有以下几个重要的基本概念.
1) 事实.对象之间及对象属性之间的多元关系, 一般使用一个三元组表示;
2) 规则.由条件及其结论构成的推理语句, 当满足事实时, 相应的结论被激活;
3) 模式.规则的IF部分, 是已知事实的泛化形式, 未实例化的多元关系.
Rete算法将规则集转化为Rete网络进行规则匹配. Rete网络是一个用于过滤事实数据的有向无环图, 包括三个部分:根节点(Root node), Alpha网络和Beta网络[10].根节点是所有事实对象进入网络的入口, 是一个虚拟节点, 不具有实际意义. Alpha网络用于过滤事实, 通过模式匹配找出事实集中所有符合的模式集合. Alpha网络包括两种节点:类型节点(Object type node)和条件节点(Alpha node).类型节点是根节点的直接子节点, 保存了规则中事实对象对应的类型.如果对某一对象类型的模式有条件约束, 则该约束会进入Alpha网络形成条件节点; 当对象存在多个条件约束时, 则从类型节点出发, 对每一条规则形成一个条件节点链, 允许模式之间存在节点共享. Beta网络用于匹配规则, 通过连接操作将模式集组合形成匹配集, 最终将匹配集转化为规则结论(Action)并执行. Beta网络包含两类节点:连接节点(Beta node)和终端节点(Terminal node).连接节点接收条件节点的输入, 并将规则中关联的条件节点组合起来.终端节点对应规则的结论部分.
Rete网络和有穷自动机结构类似, 可以这么说, 依据Rete网络推理机其实本身就是自动机的一种, 下面给出基于有穷自动机的Rete网络的定义.
定义3. Rete网络形如为的五元组, 其中
1) 状态集 $Q$ : Rete网络中的各节点, 包含Root节点, Alpha节点, Beta节点和Terminal节点.其中, Root节点为初始状态, Terminal节点为终止状态, Alpha节点和Beta节点对应自动机中的普通状态节点.
2) 字母表 ${\Sigma}$ : Rete网络中事实的幂集, 即Alpha和Beta节点中描述语言.
3) 转移函数 ${\delta}$ : Rete网络中节点合并的规则.表示为, 当然在一般环境下, 此笛卡尔积的规模是一个稀疏结构.
4) 初始状态 ${q_0}$ : Rete网络中的Root节点.
5) 终止状态集 $F$ : Rete网络中的Terminal节点.
通过使用有穷自动机对Rete网络推理机描述, 我们可以使用更加规范的语言来表示Rete网络推理机. Rete网络的构造算法如下.
算法1. Rete网络构造算法
输入. 规则集合
输出. Rete节点网络
for $i=1$ ; $i \le RuleNum$ ; $i++$ do
取出规则 $R_i$
for $j=1$ ; $j \le ConditionNum$ of $R_i$ ; $j++$ do
if $Condition_j$ 不存在于Alpha网络中then
将 $Condition_j$ 作为 $Alpha(j)$ 节点插入
Alpha网络
endif
if ${j = 2}$ then
将 $Beta(1)$ 节点插入Beta网络中, 其父
节点为 $Alpha(1)$ 和 $Alpha(2)$ ;
endif
if ${j > 2}$ then
将 $Beta(j)$ 节点插入Beta网络中, 其父
节点为 $Beta(j-1)$ 和 $Alpha(j)$ ;
endif
endfor
endfor
通过Rete网络构造的过程不难发现, 条件顺序对Alpha网络和Beta网络的节点共享性能有较大影响, 先加入的条件被优先共享.这样会导致Rete网络趋向复杂, 从而影响Rete网络的推理速度[11].
2. 基于共享度模型的改进Rete算法
2.1 问题分析
节点共享是Rete网络的一大特性, 通过节点共享, 可以避免重复匹配, 提高匹配效率[12].但是在建立Rete网络时, 模式的条件顺序会极大影响网络的节点共享性能, 下面分析模式的条件顺序对共享性能的影响.
Rete网络包含Alpha网络和Beta网络, 模式的条件顺序对这两个网络节点共享性能的影响不同, 首先分析对Alpha网络的影响.
假设存在两个规则, 其模式分别为( $c_1, c_2, \cdots$ , )和(, $c_{bq}$ ), 这里 $c_{i}$ 表示同一类型条件.显然这两个模式有 $n$ 个相同条件, 对应的Alpha网络模型如图 1(a)所示.这里将第二个模式的第一个条件移到第 $n$ 个条件后, 即将模式变为(, $c_{bq}$ ).那么当建立Rete网络时, 由于两个模式相同条件的条件顺序不同, 虽然有 $n$ 个相同节点但是却没有一个共享节点, 节点共享失败, 其对应的Rete网络如图 1(b)所示.可以看出, 对于同一类型的条件, 其排列顺序对Alpha网络的节点共享有很大影响.
下面分析模式的条件顺序对Beta网络的影响.假设存在两条规则, 其模式分别为 $(C, D, E)$ 和 $(C$,, 其中 $C, D, E, F$ 代表不同类型的条件, 其对应的Beta网络如图 2所示.如果将第二条规则的条件顺序改变为 $(D, E, F, C)$ , 那么构建Rete网络时, 将不存在节点共享, 如图 3所示.
通过上面的分析可以看出, 条件顺序对Alpha网络和Beta网络的节点共享性能有较大影响, 先加入的条件被优先共享.因此, 对条件进行排序可以降低对性能的影响.为了使排序更加合理, 提高Rete网络的共享性, 本文提出共享度模型的概念.
2.2 共享度模型
节点共享度代表一个节点需要被共享的程度, 这里使用引用该节点条件的规则数对其进行量化.例如, 一个条件如果被三条规则引用, 则该条件对应节点的共享度为3.下面给出形式化定义.
定义4. 节点共享度为其在规则集中被共享的程度.设 $d_c$ 为节点 $c$ 的节点共享度, 则
$ \begin{align} {d_c} = \sum\limits_{i = 1}^n {Contains(Rul{e_i}, d)} \ \end{align} $
(1) 其中
$ \begin{align} Contains(Rul{e_i}, d)= \begin{cases} 1, &{Rul{e_i}\text{包含}c}\\ 0, &{Rul{e_i}\text{不包含}c} \end{cases} \end{align} $
(2) 在理想情况下, 整个Rete网络中不存在相同节点, 则节点的共享度为该条件出现的次数, 显然 $d_c$ 越大, 条件的共享程度应当越高.由于条件的共享程度和顺序相关, 条件顺序越靠前其共享程度越高, 因此需要将条件按其节点共享度排序.例如由模式( $c_1$ , $c_2$ )和( $c_3$ , $c_1$ )组成的模式集, 将其按节点度排序后变为( $c_1$ , $c_2$ ), ( $c_1$ , $c_3$ ), 在构造Rete网络时, $c_1$ 被先加入网络并得到共享.
这种简单排序可以解决一部分共享问题, 但是对于节点共享度相同的条件, 由于其排序是随机的, 同样会对网络的共享性能造成影响, 例如由模式( $c_1$ , $c_2$ , $c_4$ ), ( $c_1$ , $c_3$ ), ( $c_1$ , $c_2$ , $c_3$ , $c_4$ )组成的模式集, 按照节点度对其降序排列, $c_1$ 排在第一位, 剩余的 $c_2$ , $c_3$ , $c_4$ 由于节点共享度相同, 其排序是随机的, 假设其排序为 $c_2$ , $c_3$ , $c_4$ , 那么对应的Alpha网络如图 4(a)所示.只有 $c_2$ 被共享, $c_3$ 和 $c_4$ 没有共享, 如果将排序变为 $c_2$ , $c_4$ , $c_3$ , 则Alpha网络变为如图 4(b)所示.此时, $c_2$ , $c_4$ 被共享, $c_3$ 没有共享.
实际中, 节点共享度相同是比较普遍的现象, 当同一节点共享度的条件数量很多时, 其排序对Rete网络的节点共享性能影响很大.因此需要对有相同节点共享度的条件进一步排序.这里再引入模式节点共享度的概念, 其形式化定义如下.
定义5. 模式是由若干条件组成的, 将模式的节点共享度定义为模式中所有条件节点共享度的和, 设模式 $M$ 包含 $n$ 个条件( $c_1$ , $c_2$ , $\cdots$ , $c_n$ ), 则其模式共享度
$ \begin{align} {d_M} = \sum\limits_{i = 1}^n {{c_i}} \end{align} $
(3) 模式的节点共享度反映了整个模式在网络中的共享程度, $d_M$ 越大, 则模式的共享程度越高.由于模式包含条件, 模式的共享程度高则表示其包含的条件共享程度高, 因此可以使用模式的节点共享度对具有相同节点共享度的条件做进一步排序.条件会出现在多个模式中, 设条件 $c$ 出现在 $p$ 个模式( $M_1$ , $M_2$ , $\cdots$ , $M_p$ )中, 模式的节点共享度为( $d_{M1}$ , $d_{M2}$ , $\cdots$ , $d_{Mp}$ ).则 $c$ 的模式共享度.
模式共享度反映了其他条件对该条件的依赖情况, $d_{cM}$ 越大, 依赖程度越高, 而依赖程度越高, 其共享程度就越高, 顺序应当靠前.因此, 可以依据模式共享度对节点共享度相同的条件降序排列, 来区分相同节点共享度的条件.
根据节点共享度和模式的共享度, 我们可以对节点在规则集中的共享程度进行排序, 构建高共享性Rete网络.
2.3 高共享性Rete网构建算法
2.3.1 Alpha网络构建
在一个Rete网络中, 规则通过网络节点的形式呈现.规则的条件构成Alpha网络, 每一个条件都对应一个Alpha节点; 规则模式构成Beta网络, Beta节点由Alpha节点相互连接形成, 每一个Beta节点代表模式的一部分, $Beta(n)$ 节点代表规则的全部模式, 规则的结论对应终端节点, 是Beta网络的叶子节点, 也是 $Beta(n)$ 节点的子节点.因此, 构建Rete网络需要完成Alpha网络和Beta网络的构建. Alpha网络实际上是规则条件的网络, 其共享性能依赖条件顺序, 首先使用第2.2节提出的节点共享度模型和模式共享度模型, 对条件进行降序排序.获得按共享度降序排列的条件集合之后, 可以使用这个集合直接构造Alpha网络, 不需要再次读取规则集.
2.3.2 Beta网络构建
Beta网络使用连接和投影的方式进行模式匹配, 连接的对象是Alpha节点而不是条件, 因此在考虑条件节点共享度的同时也需要考虑Alpha节点的共享度.
Rete算法在构造Alpha网络时会对Alpha节点进行分类, 节点共享度模型可以保证在同一类型中Alpha节点的排序, 但是却无法保证各个类型的排序, 这不仅影响节点共享性, 还会大大增加匹配的计算规模.
因此需要对构建好的Alpha分类进行排序, Alpha分类包含多个Alpha节点, 每一个Alpha节点对应一个条件, 根据节点共享度模型, 可以计算出整个Alpha分类的共享度.设Alpha分类中有 $n$ 个Alpha节点, 对应的节点共享度为( $d_1$ , $d_2$ , $\cdots$ , $d_n$ ), 那么Alpha分类的共享度.
共享度高的分类, 顺序应当靠前.对于共享度相同的分类, 随机排列顺序可能会降低Beta网络的节点共享性.设两个Alpha分类的共享度均为 $n$ , 一个分类只含1个节点, 一个分类含 $n$ 个节点.如果含 $n$ 个节点的分类被排在前面, 那么每次都需要先和 $n$ 个节点进行 $n$ 次连接; 如果含1个节点的分类排在前面, 每次只需要进行1次连接即可.为了反映分类中节点个数对共享性能的影响, 这里为Alpha分类引入平均共享度的概念, 对于一个含有 $m$ 个Alpha节点, 共享度为 $n$ 的Alpha分类, 其平均共享度.共享度相同的分类, 平均共享度高的顺序靠前. Alpha分类排序算法如下.
算法2. Alpha分类排序算法
输入. Alpha网络
输出. 分类排序之后的Alpha网络
步骤1. 建立分类集合H.
步骤2. 遍历Alpha网络, 计算Alpha分类的共享度保存至分类集合H中.
步骤3. 对Alpha分类按共享度降序排列.
步骤4. 按平均共享度对共享度相同的Alpha分类降序排列.
步骤5. 返回排序后的Alpha网络.
通过算法2可以获得按Alpha分类降序排列的Alpha网络, 使用这个网络可以保证共享度高的Alpha分类被优先连接, 从而提高Beta网络的节点共享性能. Alpha网络配合规则集可以构造Beta网络, 具体描述如下.
算法3. Beta网络构建算法
输入. 排序后的Alpha网络
输出. Beta网络
for $i=1$ ; $i \le $ 规则集数目; $i++$ do
取出规则 $R_i$
for $j=1$ ; $j \le R_i$ 中规则条件数目; $j++$ do
if $j\geq 2$ then
将 $Beta(j)$ 节点插入Beta网络中, 其父
节点为 $Beta(j-1)$ 和 $Alpha(j)$ ;
endif
endfor
将规则 $R_i$ 的结论封装成终端节点, 作为 $Beta(n)$
的子节点
endfor
返回Beta网络.
2.4 Rete网络共享性指标及推理优化
2.4.1 Rete网络共享性指标
为了体现算法的优化效果, 需要对Rete网络的节点共享性能进行量化, 这里引入Rete网络节点共享性能的概念. Rete网络分为Alpha网络和Beta网络, 下面分别讨论这两种网络的节点共享性能.
设规则集 $R$ 共有 $n$ 条规则 $r_1$ , $r_2$ , $\cdots$ , $r_n$ , 每个规则模式包含的条件数为 $c_1$ , $c_2$ , $\cdots$ , $c_n$ .设 $T$ 为规则集 $R$ 的Rete网络, $A$ 为Alpha网络中的总节点数, $B$ 为Beta网络中的总节点数.则 $T$ 的Alpha共享性能为Alpha节点数与条件总数的比值, 记为 $S_A$ , 则
$ \begin{align} {S_A}=\frac{A}{{\sum\limits_{i = 1}^n {{c_i}} }} \end{align} $
(4) 考虑Beta网络, 对于含有 $c_i$ 个条件的规则 $r_i$ , 共进行 $c_i-1$ 次连接操作, 考虑终端节点, 至多生成 $c_i$ 个Beta节点, 将其Beta共享性能记为 $S_B$ , 则
$ \begin{align} {S_B}=\frac{B}{{\sum\limits_{i = 1}^n {{c_i}} }} \end{align} $
(5) 显然, Rete网络的总节点共享性能为Alpha共享性能和Beta共享性能的和, 记为 $S$ , 则
$ \begin{align} {S}={S_A}+{S_B} \end{align} $
(6) 在极端情况下, 则Rete网络没有一个共享节点, 那么, . $S_A$ 和 $S_B$ 的值域均为 $\left(0, 1\right]$ , 则 $S$ 的值域为 $\left(0, 2\right]$ .对于一个Rete网络而言, $S$ 的值越大, 其节点共享性能越差.反之, 其节点共享性能越好, 这同样适用于Alpha网络和Beta网络.
2.4.2 高共享性Rete网络推理优化
在使用传统Rete算法进行推理每次查找Alpha节点时, 总会遍历所有的Alpha节点.其时间复杂度为, 其中 $n$ 为Alpha节点的数量.对于一次查找操作, 的时间复杂度可以忽略.但是随着查找次数上升, 查找时间对总的推理时间仍会产生巨大影响.另外, 在使用传统Rete算法进行推理时, 一般按照严格的顺序, 即先根据事实产生Alpha节点, 再由Alpha节点生成Beta节点依次进行推理.如果可以根据事实产生的Alpha节点, 直接找出后面出现的Beta节点, 推理的速度将会有很大的提升.
针对上述现象, 可以建立一个Hash表快速定位Alpha节点和Beta节点, 加快查找的速度.引入Hash表存储对象的位置映射, 将Alpha节点及Beta节点和其在网络中的存储位置相互对应.那么在Rete网络事实匹配的过程中, 对于一些节点的查找工作将在的时间复杂度之内完成.这样操作之后, 可以大大提升事实匹配的整体效率.
上述对Rete网络的优化构建方法, 主要对规则中的条件依据共享度重新排序, 而对规则本身不产生任何影响.假设有下面一条规则:
$ \begin{align} Cond1 \wedge Cond2\; \cdots \;CondN \Rightarrow Result \end{align} $
(7) 无论其规则中条件如何改变, 对于一个待推理的事件包含且仅包含这条规则中的所有条件, 其推理的结果不会发生变化.这确保了本算法推理结果同传统Rete网络构建的推理结果的一致性.
3. 实验结果及分析
3.1 Rete网络构建
选择UCI的Adult[13]、Bank marketing[14]和Nursery[15]作为测试数据集.其中Adult数据集包含了14维的48842条数据, 通过Apriori算法, 挖掘出3285条规则; Bank marketing数据集包含了17维的45211条数据, 一共挖掘出5987条规则; Nursery数据集包含了8维的12960条数据, 最后挖掘出91条规则.在上述数据挖掘过程中, Apriori算法的置信度均设置为0.5, 支持度均设置为0.025.对于挖掘出来的规则, 我们进行了统一的编码, 条件之间使用空格分隔, 条件和结果之间使用符号$分隔, 编码的规则如下:
$ \begin{align} Rul{e_i} = Cond1\;Cond2\; \cdots \;CondN\$ Result \end{align} $
(8) 由于UCI数据集的条件是按照条件分类进行排序, 本身具有一定的次序, 因此采用传统构造方法得到的Rete网络有较好的节点共享性能.为了更一般的显示各个算法的推理性能, 将规则集中的规则进行打乱操作(Shuffle)作为一个对照实验.
对于每一个数据集, 我们使用传统方法在原规则集、传统方法在打乱的规则集和改进方法在原规则集中分别进行实验, 每个实验均进行4次.其结果如表 1所示.其中, Rete组表示使用传统Rete算法构建网络, Rete Shuffled组表示在打乱的规则集上使用传统Rete算法构建网络, ReteSDM组表示使用基于共享度模型的Rete算法构建网络.
表 1 网络构建对比实验结果(ms)Table 1 The result of network construction (ms)数据集 序号 Rete Rete Shuffled ReteSDM 构建时间 共享性 构建时间 共享性 构建时间 共享性 Adult 1 38 0.095 43 0.301 53 0.077 2 31 0.095 38 0.301 47 0.077 3 31 0.095 38 0.302 55 0.077 4 32 0.095 37 0.302 47 0.077 AVG 33 0.095 39 0.301 50.5 0.077 Bank marketing 1 61 0.077 64 0.296 72 0.059 2 61 0.077 66 0.296 75 0.059 3 61 0.077 66 0.296 74 0.059 4 60 0.077 62 0.295 72 0.059 AVG 60.75 0.077 64.5 0.295 73.25 0.059 Nursery 1 3 0.492 3 0.549 5 0.477 2 4 0.492 4 0.554 5 0.477 3 4 0.492 4 0.538 5 0.477 4 3 0.492 3 0.518 5 0.477 AVG 3.5 0.492 3.5 0.539 5 0.477 从表 1可以看出, 使用优化之后的基于共享度 模型的网络构建算法, 无论是在打乱的数据集和有顺序的数据集中, Rete网络中节点的共享性能都有提升.特别是对于大数据集来说, 提升的幅度更大.在Adult数据集中, 在原数据集上提升了19%, 在打乱的数据集上提升了74%;在Bank Marketing数据集中, 在原数据集上提升了23%, 在打乱的数据集上提升了80%;对于小数据集Nursery而言, 其节点共享性能也略有提升.主要原因是本文提出的ReteSDM算法使用了节点共享度和模式共享度对条件进行了重新排序, 提升了网络中节点的共享性.
在构建时间上, ReteSDM算法构建时间与传统的算法相比略有增加(增加幅度均不超过50%), 主要原因是增加了条件排序和Alpha分类节点排序, 但是增加的时间较其获得的效果(节点共享性能)来说, 其代价是比较小的.在实际应用中, 规则集是稳定且不轻易发生变化的.因此, Rete网络的构建频率很低, 网络构建时间不是衡量推理机性能的重要指标, 其时间增加的幅度是完全可以接受的.
3.2 Rete网络推理
使用在Rete网络构建实验中的三个数据集(Adult、Bank marketing和Nursey数据集)进行事实匹配算法的对比实验.实验条件分别为:
1) 在传统Rete网络上(由原规则集产生)使用传统事实匹配算法推理, 记为Rete.
2) 在传统Rete网络上(由打乱的规则集产生)使用传统事实匹配算法推理, 记为Rete shuffled.
3) 在共享性Rete网络上使用传统事实匹配算法推理, 记为ReteSDM.
4) 在共享性Rete网络上使用基于哈希索引的Rete推理算法, 记为Hashed ReteSDM.
实验分为3组.在Adult和Bank marketing数据集中, 第1组选择其中的10000条数据, 第2组选择其中的20000条数据, 第3组选择其中的30000条数据; 在Nursery数据集中, 第1组选择其中的4000条数据, 第2组选择其中的8000条数据, 第3组选择其中的12000条数据.以上实验均进行了3次, 然后对结果取均值, 其结果如表 2所示.
表 2 推理性能对比实验结果(s)Table 2 The result of ratiocination effiency (s)数据集 分组 Rete Rete Shuffled ReteSDM Hashed ReteSDM 偏差率 Adult 1 0.865 0.962 0.736 0.535 0 2 1.721 1.950 1.472 1.071 0 3 2.633 2.735 2.202 1.553 0 Bank marketing 1 0.996 1.115 0.823 0.625 0 2 2.102 2.327 1.650 1.256 0 3 3.001 3.423 2.436 1.903 0 Nursery 1 0.105 0.115 0.089 0.080 0 2 0.203 0.217 0.193 0.159 0 3 0.312 0.332 0.290 0.250 0 在表 2中, 偏差率是指在ReteSDM组和Hashed ReteSDM组中的推理结果与在Rete中的推理结果的不一致的个数.由于本算法实质是改变规则中条件的顺序, 理想环境下, 不会与传统的网络推理结果产生偏差.实验的结果也验证了这一点.
可以看出, 高共享性网络和基于哈希索引的Rete推理算法对推理速度都有较大的提升.高共享性网络通过节点共享度调整规则的条件和Alpha节点的顺序, 提高了整个Rete网络的节点共享性能, 减少了冗余节点.在事实推理时, 就可以有效减少节点匹配次数, 进而缩短推理时间, 提高推理效率.基于哈希索引的Rete推理算法通过对事实进行分类减少计算规模, 再通过Hash索引加快查找分类的速度, 有效提高推理效率.
综合来看, 同时采用高共享性网络和基于哈希索引的Rete推理算法可使推理效率提高, 而且随着事实集的增加, 推理效率会有进一步提升.
4. 总结
近年来, 人工智能在各方面都取得了良好的应用[16-18], 专家系统在人工智能领域扮演了很重要的角色.在专家系统中, 推理机是一个重要的组成部分.但是专家系统在推理过程上存在不足, 例如规则保存和推理速度等. Rete算法是专家系统中的经典算法, 但是传统的Rete算法也存在空间和性能方面问题.
本文根据节点共享度模型和模式共享度模型, 提出了一种新型Rete网络构造算法, 在Rete网络的构建中, 将规则中条件按照共享度进行排序, 构建出高共享性的Rete网络.并且在此基础上, 使用索引的方法对其进行推理优化.实验结果表明, 使用本算法创建Rete网络之后, 能够降低Rete网络的复杂度, 提升节点的共享度, 进而加快推理速度.
-
表 1 网络构建对比实验结果(ms)
Table 1 The result of network construction (ms)
数据集 序号 Rete Rete Shuffled ReteSDM 构建时间 共享性 构建时间 共享性 构建时间 共享性 Adult 1 38 0.095 43 0.301 53 0.077 2 31 0.095 38 0.301 47 0.077 3 31 0.095 38 0.302 55 0.077 4 32 0.095 37 0.302 47 0.077 AVG 33 0.095 39 0.301 50.5 0.077 Bank marketing 1 61 0.077 64 0.296 72 0.059 2 61 0.077 66 0.296 75 0.059 3 61 0.077 66 0.296 74 0.059 4 60 0.077 62 0.295 72 0.059 AVG 60.75 0.077 64.5 0.295 73.25 0.059 Nursery 1 3 0.492 3 0.549 5 0.477 2 4 0.492 4 0.554 5 0.477 3 4 0.492 4 0.538 5 0.477 4 3 0.492 3 0.518 5 0.477 AVG 3.5 0.492 3.5 0.539 5 0.477 
下载: 导出CSV
表 2 推理性能对比实验结果(s)
Table 2 The result of ratiocination effiency (s)
数据集 分组 Rete Rete Shuffled ReteSDM Hashed ReteSDM 偏差率 Adult 1 0.865 0.962 0.736 0.535 0 2 1.721 1.950 1.472 1.071 0 3 2.633 2.735 2.202 1.553 0 Bank marketing 1 0.996 1.115 0.823 0.625 0 2 2.102 2.327 1.650 1.256 0 3 3.001 3.423 2.436 1.903 0 Nursery 1 0.105 0.115 0.089 0.080 0 2 0.203 0.217 0.193 0.159 0 3 0.312 0.332 0.290 0.250 0
下载: 导出CSV
-
[1] Bemley J L. An introduction to expert systems. In: Proceedings of the 7th Annual National Convention and 10th Anniversary of Black Data Processing Associates "A Decade of Professional Growth". Washington, DC, USA, 1985. 27-34 [2] Giarratano J C, Riley G D. Expert Systems: Principles and Programming. New York: Thomson Learning, 2005. 78-122 [3] Munaiseche C P C, Liando O E S. Evaluation of expert system application based on usability aspects. In: Proceedings of the 2016 International Conference on Innovation in Engineering and Vocational Education. Bandung, Indonesia: IOP, 2016. 128-135 http://adsabs.harvard.edu/abs/2016MS%26E..128a2001M [4] Ochab M, Wajs W. Expert system supporting an early prediction of the bronchopulmonary dysplasia. Computers in Biology and Medicine, 2016, 69(1): 236-244 https://www.researchgate.net/publication/281467838_Expert_system_supporting_an_early_prediction_of_the_Bronchopulmonary_Dysplasia [5] Forgy C L. Rete: a fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence, 1982, 19(1): 17-37 doi: 10.1016/0004-3702(82)90020-0 [6] Sipser M. Introduction to the Theory of Computation (3rd edition). Boston: Cengage Learning, 2013. 44-80 [7] Kornoushenko E K. Operation of closure on the set of states of an incompletely defined deterministic automaton. Cybernetics, 1976, 12(1): 10-17 doi: 10.1007/BF01070337 [8] Topencharov V, Peeva K. Mathematical automata theory: a categorical approach. Problems of Control and Information Theory, 1980, 9(2): 141-161 http://www.ams.org/mathscinet-getitem?mr=561809 [9] Ilie L, Yu S. Reducing NFAs by invariant equivalences. Theoretical Computer Science, 2003, 306(1): 373-390 http://www.sciencedirect.com/science/article/pii/S0304397503003116 [10] Perlin M. Topologically traversing the RETE network. Applied Artificial Intelligence, 1990, 4(3): 155-177 doi: 10.1080/08839519008927948 [11] Shatueva T A. Method for classical Rete algorithm efficiency improvement for the system of production rules aimed at knowledge extraction from terminological dictionaries. Control Systems and Information Technologies, 2012, 4(3): 31-34 [12] Xiao D, Zhong X A. Improving Rete algorithm to enhance performance of rule engine systems. In: Proceedings of the 2010 International Conference on Computer Design and Applications. Qinhuangdao, China: IEEE, 2010. 572-575 http://ieeexplore.ieee.org/document/5541368/ [13] UCI Machine Learning Repository. Adult data set [Online], available: http://archive.ics.uci.edu/ml/datasets/Adult, February 3, 2017 [14] UCI Machine Learning Repository. Bank marketing data set [Online], available: http://archive.ics.uci.edu/ml/datasets/Bank+Marketing, February 3, 2017 [15] UCI Machine Learning Repository. Nursery data set [Online], available: http://archive.ics.uci.edu/ml/datasets/Nursery, February 3, 2017 [16] 段艳杰, 吕宜生, 张杰, 赵学亮, 王飞跃.深度学习在控制领域的研究现状与展望.自动化学报, 2016, 42(5): 643-654 http://www.aas.net.cn/CN/abstract/abstract18852.shtmlDuan Yan-Jie, Lv Yi-Sheng, Zhang Jie, Zhao Xue-Liang, Wang Fei-Yue. Deep learning for control: the state of the art and prospects. Acta Automatica Sinica, 2016, 42(5): 643-654 http://www.aas.net.cn/CN/abstract/abstract18852.shtml [17] 俞斌峰, 季海波.稀疏贝叶斯混合专家模型及其在光谱数据标定中的应用.自动化学报, 2016, 42(4): 566-579 http://www.aas.net.cn/CN/abstract/abstract18844.shtmlYu Bin-Feng, Ji Hai-Bo. Sparse bayesian mixture of experts and its application to spectral multivariate calibration. Acta Automatica Sinica, 2016, 42(4): 566-579 http://www.aas.net.cn/CN/abstract/abstract18844.shtml [18] 管皓, 薛向阳, 安志勇.深度学习在视频目标跟踪中的应用进展与展望.自动化学报, 2016, 42(6): 834-847 http://www.aas.net.cn/CN/abstract/abstract18874.shtmlGuan Hao, Xue Xiang-Yang, An Zhi-Yong. Advances on application of deep learning for video object tracking. Acta Automatica Sinica, 2016, 42(6): 834-847 http://www.aas.net.cn/CN/abstract/abstract18874.shtml -
下载:
计量
- 文章访问数: 1914
- HTML全文浏览量: 616
- PDF下载量: 716
- 被引次数: 0
