一个基于CLIPS的后向不确定推理系统
开篇：润墨网以专业的文秘视角，为您筛选了一篇一个基于CLIPS的后向不确定推理系统范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：基于CLIPS的前向推理构造并实现了后向推理算法，在后向推理算法中，基于确定性因子实现处理不确定性的方法；对该系统性能作了分析。
关键词：CLIPS；后向；不确定；确定性因子；推理
中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)08-1830-06
A CLIPS-Based Backward Inference with Uncertainty
LIU Hai-ming
(Suzhou Polytechnic Institute of Agriculture, Suzhou 215008, China)
Abstract: This topic designs and implements a CLIPS-based backward inference mechanism with uncertainty which works on the basis of Certainty Factor, thus enhancing the inference capability of CLIPS. At last, an analysis of the performance against the CLIPS is presented.
Key words: CLIPS; backward; uncertainty; certainty-factor; inference
1背景
1.1 CLIPS的推理机制
CLIPS(C Language Integrated Production System)作为一种通用的产生式语言和专家系统工具，由于其高效的推理机制，已被广泛用于开发政府、商业及工业等部门的项目。在专家系统中，推理机实现了对推理的控制策略。CLIPS的推理控制策略具有如下特性：1)采用前向推理；
2)使用7种冲突消解策略：分别基于规则优先级的深度和广度、分别基于规则特定性的简单度和复杂度、基于词典(LEX)和基于手段目的分析(MEA)；
3)采用Rete算法将事实与规则中的模式相匹配。
基于Rete的模式匹配算法的基本思想是：根据变化的事实寻找相应的规则；它利用基于规则的专家系统所具有的时间冗余性，通过一个模式网络存储匹配过程的状态和通过连接网络进行跨模式的变量约束比较，决定将被激活的规则。
1.2 CLIPS对后向不确定推理的需求
在我们的数字权限管理安全审计应用中，需要将已发现的数字资源非法使用模式和非法使用事件定义为CLIPS的规则，并以此分析审计日志。使用中，通过监视CLIPS的匹配过程，发现其工作内存中存在大量无用的事实以至当处理的日志范围扩大至6000条时会出现CLIPS工作内存不足以至于异常退出，而每天的日志量则远大于6000。
出现上述问题主要因为CLIPS采用前向推理；当前事实如果不支持某个规则，CLIPS的推理机将通过新的匹配增加事实量；这种方法不适用于上述诊断类应用。因为诊断类问题的解决过程往往是由当前问题开始寻找一条支持它的将证据与假设相连的链，这条链被称为后向链；为此需要后向推理寻找后向链。后向推理将后件匹配当前目标的规则的前件作为当前多个目标，并对它们分别进行后向推理，直到后向链的最末一条规则的前件被匹配成功或不存在可选的规则构造后向链。
在我们的安全审计中，存在着大量具有不确定性的知识；尽管CLIPS内部没有处理不确定性的能力，在事实和规则中放置一些处理不确定性的信息可使其处理不确定性。
为此，我们将CLIPS扩展成一个后向不确定推理系统；它基于两套下推栈和CLIPS的前向规则模拟后向推理系统，通过确定性因子表达不确定信息并在后向推理中加入处理前向规则中确定性因子的方法；后向推理所使用的规则来自于中间规则生成器将针对安全审计的正向规则转换成的CLIPS事实。
为便于描述，将首先介绍此系统如何基于确定性因子处理不确定信息，此方法部分借鉴了MYCIN处理确定性因子的方法；然后介绍目标系统及后向推理机关键算法；最后给出目标系统与CLIPS的性能比较。
2后向推理中的确定性因子（Certainty Factor）
2.1定义
确定性因子以Carnap的确认理论为基础；最初在MYCIN中被使用，其定义如下：
CF(H,E)表证据E支持一个假设H的可信度，MB(H,E)表示E对H的肯定程度，MD(H,E)表示E对H的否定程度；其中MB和MD的值应由专家根据经验给出。
2.2基于CF处理规则的方法
1)规则的激活条件
一个规则前件的确定性因子(CF)的值必须>0.2，才认为该前件为真并激活此规则。设定阀值是为了减少对假设弱支持的规则的数目，因此它是可调整的。
2) CF的计算
表1规则确定性因子的计算法则
根据是否存在支持假设的单条规则且其CF高于阀值可将计算CF的方法分为两种。
a、规则CF的计算
定义1：规则确定性因子CFmono为单条规则前件中所有证据支持同一假设的可信度；这些证据组合后，CFmono的计算法则如表1。
b、组合CF的计算
若不存在CF>0.2的单条规则，需考察是否存在多条规则支持同一假设。
定义2：组合确定性因子（式2）CFcombine为多条规则同时支持同一假设的确定性因子。
上述两种CF计算方法在后向推理中将分别通过析取推理和合取推理实现。
当计算两条以上规则的组合CF时，要迭代使用函数CFcombine，即先计算出两个规则的组合CFcombine，再用这个CFcombine和第三个规则的CF计算新的CFcombine，如此循环。
3目标系统框架
3.1工作原理
1)基于前向推理的后向推理链的构造
后向推理的基本思想为：首先将规则后件与当前假设匹配，选取可用规则，并将该规则前件作为待匹配假设置入目标状态栈；则目标状态栈中存放了一条求解最初假设的后向链。
目标系统框架基于三个栈实现后向推理：目标状态栈，后向推理机议程，后向推理栈。
后向推理机议程用于存放定义3或4描述的推理队列，它们都是已激活的规则；后向推理栈记录后向推理机议程中哪些规则的前件位于目标状态栈中及是否已匹配，它主要用于记录推理过程。
若有多条规则可选，后向推理机首先基于CF值进行冲突消解，若仍存在冲突，则采用CLIPS的冲突消解策略。目标状态栈中假设与工作内存中事实的匹配由CLIPS的前向规则实现。
2)后向推理中的不确定推理
定义3：反向析取推理队列为一规则队列；CFmono大者规则优先级高；CFmono等者规则，按CLIPS冲突消解策略计算优先级；所有规则的CFmono均高于阀值，且这些规则蕴含某一相同假设。
定义4：反向合取推理队列为一规则队列；其中每一规则的CFmono均低于阀值，但它们的CFcombine高于阀值，且这些规则蕴含某一相同假设；规则间的优先级基于CLIPS的Random冲突消解策略定义。
定义3和4定义了后向推理中分别基于定义1和2的计算结果，称构造这两种结果的算法分别为构造析取推理队列和构造合取推理队列；后一算法较前者复杂。
目标系统基于两套下推栈分别实现这两个算法；每套栈各含一个目标状态栈、后向推理机议程和后向推理栈。
3.2框架部件简介
图1基于CLIPS的后向链不确定推理框架结构
图1中的后向推理机基于前述确定因子构造后向链。被虚线框包围部分为原有CLIPS前向推理系统。各部件简介如下：
1)知识库：为CLIPS自身的规则库；用于存放用CLIPS语法表示的前向规则（后简称F-Rule），每条规则对应CLIPS前向推理机分配的规则序号；
2)工作内存(事实部分)：表示用于与正向规则匹配的事实，简称WM-Facts；
3)议程：用于存放被激活等待执行的前向规则；
4)中间规则生成器：将前向规则转换成CLIPS中的事实；这部分事实被称为“工作内存(中间规则部分)”（后简称WM-temp-Rule），将被作为后向推理规则使用；
5)目标状态栈1和2：用于存放待匹配的假设；这两个栈具有相同结构，如图2；一个栈的记录视需要可被置入另一栈中，不同栈的记录通过一标志位被区分，以保存推理线索；
6)后向推理机：基于CLIPS前向规则和C函数实现，控制后向推理中目标状态栈、后向推理议程、后向推理栈及工作内存中部分事实的状态变化和后向推理中的模式匹配；
7)后向推理机议程1：存放反向析取推理队列，为一队列栈；并且队列与对应子目标绑定；结构如图3。
图2目标状态栈结构
图3后向推理机议程1结构
图4后向推理栈1结构
8)后向推理机议程2：存放后向合取推理对列，为一队列栈；结构与图3相似，但图3中的析取栈序号将被改为合取栈序号；
9)后向推理栈1和2：记录目标状态栈1和2中未匹配假设及以这些假设作为前件的规则。
4后向推理机关键算法
后向链推理的主要问题是要找到一条将证据和假设连接起来的链，因此后向推理机主要负责构造后向链和将假设与事实匹配。
4.1算法基本思想
定义5：称后向析取推理队列中的规则的前件所包含证据被称为析取推理子目标；对这些规则或子目标进行的匹配被称为析取推理。
定义6：称后向合取推理队列中的规则的前件所包含证据被称为合取推理子目标；对这些规则或子目标进行的匹配被称为合取推理。
定义5和6中的两种推理模式被后向推理机用于构造后向链；后向推理机首先对当前假设进行析取推理，若失败则进行合取推理；若合取推理失败，则通过前向推理扩大事实量；若发现存在新匹配，则转析取推理，否则表明已构造的后向链不合理，则对推理过程回溯，直至最初架设匹配成功或回溯失败。
通常对含有变量的规则进行前向推理，因为目标系统的后向推理没有变量约束机制。
后向推理机通过CLIPS提供的通配符功能完成对不含变量的规则、规则前件包含的假设及事实三者之间的匹配。
图5基于CLIPS的后向不确定推理基本流程
4.2后向推理算法基本流程
前提：a若将所有正向规则改造成产生式，其前件与后件均用非终结符替代，则这组产生式不应存在递归；b同一规则不含相互矛盾的结论
输入：初始目标
输出：推理结果和推理过程
初态：初始目标进目标状态栈1
结束状态：两个目标状态栈中不含序号为1的目标且后向推理栈1不为空，或后向推理栈1为空
(1)初始目标状态进栈；
(2)析取栈匹配事实：搜索与目标状态栈1栈顶子目标同为某一规则前件的所有子目标相匹配的事实，若匹配成功，则转(5)；若匹配失败，则构造反向析取推理队列：{将可以推出当前子目标并且其CF值高于阀值的中间规则按CF值降序构造一优先级队列，将此队列放入后向推理机议程1}并转（8）；若构造反向析取推理队列失败，则转(9)；
(3)合取栈匹配事实：搜索与目标状态栈2栈顶当前子目标所属组合规则集中所有规则前件的子目标相匹配的事实，若匹配成功，则转(6)；若匹配失败，则转(4)；
(4)析取推理：构造反向析取推理队列，并转(7)（析取推理中构造反向链1），若构造反向析取推理队列失败，则构造反向合取推理队列：{按CFcombine求出所有组合规则集，若存在这样的规则集，则将高于阀值的CF对应的组合规则集按所含规则少则优先级高且优先级低者先进的次序全部压进后向推理机议程2}，并转(11)（析取推理不成功，转合取推理，并在合取推理中构造反向链1）；若构造反向合取推理队列失败，转(12)（合取推理不成功，转前向推理）；
(5)检查目标状态栈1和2，若序号为1的子目标不存在，则转(13)（检查后向推理状态是否成功）；否则，析取栈维护：若匹配成功的目标状态栈1栈顶记录A自于目标状态栈2，则{
a从目标状态栈1中删除被匹配的记录b从后向推理栈1中删除此子目标对应规则下的子目标c检查后向推理栈1的记录，若某一规则中所有子目标全部匹配成功，则把对应的前向规则置入CLIPS议程并触发它，将新产生的事实与目标状态栈1中所有子目标匹配，若成功则删除这些子目标
}，之后，将目标状态栈2中合取栈序号比A的合取栈序号小1的子目标作为当前子目标，转(3)；否则{
a从目标状态栈1中删除被匹配的记录b从后向推理栈1中删除这些对应规则下的子目标c检查后向推理栈1的记录，若某一规则中所有子目标全部匹配成功，则把对应的前向规则置入CLIPS议程并触发它，将新产生的事实与目标状态栈1中所有子目标匹配，若匹配成功则转(5)，否则转(2)
}；
(6)检查目标状态栈1和2，若序号为1的子目标不存在，则转(13)；否则合取栈维护：若匹配成功的子目标为目标状态栈2栈顶记录，则{
a从目标状态栈2删除匹配成功的子目标b从后向推理栈2删除该这些子目标c若后向推理机议程2栈顶队列的所有子目标匹配成功，则相应地清除后向推理栈2栈顶的多条记录d根据后向推理机议程2栈顶记录删除目标状态栈2中对应的子目标e若已删除的目标状态栈2栈顶记录A来自于目标状态栈1，则将析取栈号比A的析取栈序号a小1的目标状态栈1的记录作为当前子目标并转(2)，否则将目标状态栈2的栈顶子目标为当前子目标并转(3)
}；
(7)记录推理线索1：将目标状态栈2当前子目标移进目标状态栈1，并置标为“合取推理”子目标，转(8)（合取推理中的析取推理）；
(8)置后向推理机议程1栈顶优先级队列中第一条规则的前件入目标状态栈1，记录目标状态栈1的推理过程：将此规则在规则库的序号与此规则的前件在目标状态栈1中的析取栈序号构成的记录作为后向推理的一步存放于后向推理栈1，转(2)（析取推理中构造反向链2）；
(9)合取推理：构造反向合取推理队列，转(10)（合取推理中构造反向链1）；若构造失败，转(12)（合取推理不成功，转前向推理）；
(10)记录推理线索2：将目标状态栈1当前子目标移进目标状态栈2，置标为“析取推理”子目标（以标志合取推理栈中这一子目标来自于析取推理栈，作为推理机控制推理过程的线索，决定推理机何时在两个目标状态栈或两种推理模式之间切换），转(11)（合取推理中构造反向链2）；
(11)置后向推理机议程2栈顶优先级队列中所有规则的前件入目标状态栈2，记录目标状态栈2的推理过程：将其中每一条规则在规则库的序号与此规则的前件在目标状态栈2中的合取栈序号构成的记录作为后向推理的一步存放于后向推理栈2，转(3)（合取推理中构造反向链3）（合取栈维护）；
(12)前向推理：将带有变量约束的前向规则与工作内存中的事实相匹配，若连续匹配五次后，仍不存在支持两个目标状态栈中子目标的事实则转(14)（否则回溯）；否则，若产生的新事实与目标状态栈1中某个子目标匹配，转(5)；若与目标状态栈2或两个目标状态栈同时存在子目标与新产生事实匹配，转(6)；
(13)后向推理成功：退出算法；
(14)合取推理回溯：若后向推理栈2为空，则转(15)，否则：按后向推理机议程2栈顶组合规则集的规则删除位于目标状态栈2中的多个栈顶子目标；查找属于后向推理机议程2栈顶组合规则集并位于目标状态栈1中的子目标，若存在，则将目标状态栈1中从此子目标开始至栈顶的所有子目标删除；删除后向推理栈2栈的多个栈顶规则记录；删除与后向推理机议程2栈顶支持同一子目标的多个栈顶组合规则集，若后向推理议程2栈为空，则转(15)，否则，转(11)（若合取推理回溯失败，则析取推理回溯）；
(15)析取推理回溯：若后向推理栈1为空，转(16)，否则：根据后向推理栈1栈顶队列的队头规则删除属于此规则且位于目标状态栈1中的子目标，删除后向推理机议程1栈顶队列中的队头规则；转(8)；
(16)后向推理失败，退出算法；
5实验结果分析
在采用Intel Pentium 4 1.7GHz，256M内存的PC机上，以Windows NT Server4.06为平台，以ACCESS 2000为支撑软件，就基于CLIPS 6.2和ANSI C实现的系统针对三组规则进行了实验。
实验的目的是对2000条数字权限管理系统审计日志分析以发现非法使用数字资源事件，这些日志经过预处理使得其中包含了12种共计22个非法使用模式(badPttn)和9种共计30个非法事件(illEv)。为对比目标系统与CLIPS 6.2的推理能力，基于CLIPS实现的三组规则RS1，RS2，RS3均描述了这12种非法使用模式和9种非法使用事件；这三组规则属性如表2。
表2三个规则集属性
将三组规则分别在两个推理系统上运行，被发现的非法事件数及所费时间(Time)如表3、4、5所示。
表3 RS1的运行结果对比
表4RS2的运行结果对比
表5RS3的运行结果对比
可以看出，目标系统在基于含变量的规则推理时效率较低，因为所有变量约束工作都将在若干次后向推理后被传递给CLIPS的前向推理机制解决；但随着含变量的规则所占百分比的降低，目标系统在判断当前是否存在某种特征模式方面的能力较CLIPS强。但必须注意，这些实验数据与规则的有效性相关；若规则种模式的顺序更加合理，则将节省更多内存和获得更快的速度。
6结论
本文设计和实现了一个基于CLIPS的后向不确定推理系统。该系统除具有CLIPS的全部功能外，还具有以特定模式为目标的后向推理能力；并且该后向推理可以处理基于确定性因子表达的不确定信息。含变量的规则所占百分比较少时，该系统的推理能力显著强于CLIPS。该系统仍在不断完善中。下一步工作将包括如何使该系统具有直接的谓词匹配能力。
参考文献：
[1] Giarratano J,Riley G.专家系统原理与编程[M].印鉴,译.北京:机械工业出版社,2000.
[2]吉奥克.专家系统原理与编程[M].北京:机械工业出版社,2006.