﻿ 基于改进规则激活率的扩展置信规则库推理方法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (6): 1179-1188  DOI: 10.11992/tis.201906046 0

### 引用本文

CHEN Nannan, GONG Xiaoting, FU Yanggeng. Extended belief rule-based reasoning method based on an improved rule activation rate[J]. CAAI Transactions on Intelligent Systems, 2019, 14(6): 1179-1188. DOI: 10.11992/tis.201906046.

### 文章历史

1. 福州大学 数学与计算机科学学院，福建 福州 350116;
2. 福州大学 决策科学研究所，福建 福州 350116

Extended belief rule-based reasoning method based on an improved rule activation rate
CHEN Nannan 1, GONG Xiaoting 2, FU Yanggeng 1,2
1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China;
2. Decision Sciences Institute, Fuzhou University, Fuzhou 350116, China
Abstract: The data-driven extended belief rule-based system uses relational data to generate rules based on the traditional belief rule base. Using this method to build a rule base is simple and effective. However, the rules activated by this method are inconsistent and incomplete, and this method cannot handle none-activated inputs. Therefore, this paper proposes an extended belief rule-based method, based on an improved rule activation rate. This method improves upon the individual matching degree calculation method through gauss kernels, balances the consistency and completeness of activation rules, and solves the problem of non-activation of rules based on the idea of k-nearest neighbors. Finally, this paper selects a nonlinear function fitting experiment and an oil pipeline leak detection experiment to test the efficiency and accuracy of the proposed method. Experimental results showed that the proposed method not only ensures efficiency, but also improves the accuracy of the extended belief rule-based system.
Key words: belief rule base    data driven    evidence reasoning    individual matching degree    k-nearest neighbors    none activation    consistency    completeness

1 EBRB专家系统 1.1 EBRB表示

EBRB系统中的置信规则格式如式(1)所示：

 $\begin{array}{l} {R_k}:{\rm IF}\;{U_1}\;{\rm is}\;\{ ({A_{11}},\alpha _{11}^k),({A_{12}},\alpha _{12}^k), \cdots ,({A_{1{J_1}}},\alpha _{1{J_1}}^k)\} \wedge \\ \;\;\;\;\;\;\;\;\;\;\;{U_2}\;{\rm is}\;{\rm{\{ }}({A_{21}},\alpha _{21}^k),({A_{22}},\alpha _{22}^k), \cdots ,({A_{2{J_2}}},\alpha _{2{J_2}}^k)\} \wedge \cdots \wedge \\ \;\;\;\;\;\;\;\;\;\;\;{U_T}\;{\rm is}\;\{ ({A_{T1}},\alpha _{T1}^k),({A_{T2}},\alpha _{T2}^k), \cdots ,({A_{T{J_T}}},\alpha _{T{J_T}}^k)\} \\ \;\;\;\;\;\;{\rm THEN}\;\{ ({D_1},\beta _1^k),({D_2},\beta _2^k), \cdots ,({D_N},\beta _N^k)\} \\ \;\;\;\;\;\;{\rm with\;a\;rule\;weight}\;{\theta _k}\; {\rm and\;attribute\;weights}\\ \;\;\;\;\;\;{\delta _1},{\delta _2}, \cdots ,{\delta _T};\\ \;\;\;\;\;\;\displaystyle{\rm{s}}{\rm{.t}}{\rm{.}}\;\sum\limits_{j = 1}^N {\beta _j^k \leqslant 1} ,\;\sum\limits_{{\rm{j}} = 1}^{{J_i}} {\alpha _{ij}^k \leqslant 1} \end{array}$ (1)

1.2 EBRB规则构建

 ${\rm{\{ (}}x_1^k,x_2^k, \cdots ,x_T^k;{y^k})|k = 1,2, \cdots ,L\}$

1) 根据领域专家的经验得到[1]，或者通过模糊隶属函数[27]确定每个条件属性参考值 $\left\{ {{A_{ij}},i = } \right.$ $\left. { 1,2, \cdots ,T,j = 1,2, \cdots ,{J_i}} \right\}$ 和结果属性参考值 $\left\{ {{D_j},j = } \right.$ $\left. { 1,2, \cdots ,N} \right\}$

2) 利用1)确定的条件属性参考值和结果属性参考值，将训练数据的输入X以及输出y分别转化为对应的置信分布形式。本文针对数值型数据给出置信分布转化方法：

 $E(x_i^k) = \{ ({A_{ij}},\alpha _{ij}^k),j = 1,2, \cdots ,{J_i}\}$ (2)

γij表示属性参考值Aij对应的数值，且保证 $\left\{ {{\gamma _i}_{(j + 1)} > {\gamma _{ij}}, j = 1,2, \cdots ,J_i - 1} \right\}$ 。则 $\alpha _{ij}^k$ 的计算公式如下：

 $\alpha _{ij}^k = \frac{{{\gamma _{i(j + 1)}} - x_i^k}}{{{\gamma _{i(j + 1)}} - {\gamma _{ij}}}}, \;{\gamma _{ij}} \leqslant x_i^k \leqslant {\gamma _{i(j + 1)}},\;j = 1,2, \ldots ,{J_i} - 1$ (3)
 $\alpha _{i(j + 1)}^k = 1 - \alpha _{ij}^k,\;{\gamma _{ij}} \leqslant x_i^k \leqslant {\gamma _{i(j + 1)}},\;j = 1,2, \cdots ,{J_i} - 1$ (4)
 $\alpha _{it}^k = 0,\; t = 1,2, \cdots ,j - 1,j + 2, \cdots ,{J_i}$ (5)

 $E({y^k}) = \{ ({D_j},\beta _j^k),j = 1,2, \cdots ,N\}$

3) 利用2)的方法，本文可将数据 ${\rm{(}}x_1^k,x_2^k, \cdots ,$ $x_T^k;{y^k})$ 转化成如式(1)所示的规则，从而得到初步的规则库。

4) 确定EBRB中每条规则的权重以及条件属性权重。由于EBRB的每条规则都由数据生成的，因此规则权重的设定需要考虑到数据质量引起的规则之间的冲突与不一致，将不一致性指标[19]引入规则权重的计算可以缓解规则的冲突性。

1.3 EBRB推理机制

EBRB系统规则库生成之后，即可进行EBRB推理。给定一个T维输入数据 $X = ({x_1},{x_2}, \cdots ,{x_T})$ ，根据式(2)~(5)可得输入对应的置信分布形式：

 $E\left( {{x_i}} \right) = \left\{ {\left( {{A_{ij}},{\alpha _{ij}}} \right),i = 1,2, \cdots T,j = 1,2, \cdots ,{J_i}} \right\}$

 $d_i^k = \sqrt {\sum\limits_{j = 1}^{{J_i}} {{{({\alpha _{i,j}} - \alpha _{i,j}^k)}^2}} }$ (6)
 $S_i^k = 1{\rm{ - }}d_i^k$ (7)

k条规则的激活权重计算公式如下：

 $\begin{gathered} \displaystyle{\omega _k} = \frac{{{\theta _k}\prod\limits_{i = 1}^{{T_k}} {{{\left( {S_i^k} \right)}^{{{\bar \delta }_i}}}} }}{{\sum\limits_{l = 1}^L {\left[ {{\theta _l}\prod\limits_{i = 1}^{{T_l}} {{{\left( {S_i^l} \right)}^{{{\bar \delta }_i}}}} } \right]} }}\;\;,\;\;{{\bar \delta }_i} = \frac{{{\delta _i}}}{{\begin{array}{*{20}{c}} {\max } \\ {j = 1,2, \cdots ,{T_k}} \end{array}\left\{ {{\delta _j}} \right\}}} \\ \displaystyle{\rm{s}}{\rm{.t}}.\;0 \leqslant {\omega _k} \leqslant 1(k = 1,2, \cdots ,L),\sum\limits_{i = 1}^L {{\omega _i}} = 1 \\ \end{gathered}$ (8)

 $\begin{array}{l} \displaystyle m_j^k = {\omega _k}\beta _j^k\\ \displaystyle m_D^k = 1 - {\omega _k}\sum\limits_{j = 1}^N {\beta _j^k} \\ \displaystyle \bar m_D^k = 1 - {\omega _k}\\ \displaystyle \tilde m_D^k = {\omega _k}\left( {1 - \sum\limits_{j = 1}^N {\beta _j^k} } \right) \end{array}$

 ${C_j} = t\left[ {\prod\limits_{l = 1}^L {\left( {m_j^l + \bar m_D^l + \tilde m_D^l} \right)} - \prod\limits_{l = 1}^L {\left( {\bar m_D^l + \tilde m_D^l} \right)} } \right]$
 ${\tilde C_D} = t\left[ {\prod\limits_{l = 1}^L {\left( {\bar m_D^l + \tilde m_D^l} \right)} - \prod\limits_{l = 1}^L {\bar m_D^l} } \right]$
 ${\bar C_D} = t\prod\limits_{l = 1}^L {\bar m_D^l}$
 ${t^{ - 1}} = \sum\limits_{j = 1}^N {\prod\limits_{l = 1}^L {\left( {m_j^l + \bar m_D^l + \tilde m_D^l} \right)} } - \left( {N - 1} \right)\prod\limits_{l = 1}^L {\left( {\bar m_D^l + \tilde m_D^l} \right)}$
 ${\beta _j} = \frac{{{C_j}}}{{1 - {{\bar C}_D}}}, \; j = 1,\ 2,\ \cdots ,N$
 ${\beta _D} = \frac{{{{\tilde C}_D}}}{{1 - {{\bar C}_D}}}$

 $f\left( {{x_t}} \right) = \sum\limits_{j = 1}^N {\left( {\mu \left( {{D_j}} \right){\beta _j}} \right)} + \frac{{\left( {\mu \left( {{D_1}} \right) + \mu \left( {{D_N}} \right)} \right)}}{2}\left( {1 - \sum\limits_{j = 1}^N {{\beta _j}} } \right)$
2 EBRB激活方法优化 2.1 一致性与完整性问题

EBRB属于数据驱动的置信规则库，因此规则库质量会受数据质量的影响。当被激活的规则中存在冲突规则，或者包含大量与输入相关度低的规则时，证据推理的效果会受影响，EBRB系统存在规则不一致性问题。相反，当被激活的规则中只包含少量规则，一些相关度高的规则未被激活时，同样也会影响最终的推理结果，即EBRB系统存在规则不完整性问题。

2.2 个体匹配度计算方法改进

 Download: 图 1 静态个体匹配度计算方法的问题 Fig. 1 Problem of static individual matching calculation method

 $S_i^k = \exp {\rm{( - }}{(d_i^k)^2}/(2{\sigma ^2}){\rm{)}}, \sigma {\rm{ > 0}}$ (9)

 Download: 图 2 不同个体匹配度计算方法对比 Fig. 2 Comparison of different individual matching methods
 Download: 图 3 对应不同σ参数的函数S3 Fig. 3 Function S3 corresponding to different σ parameters
2.3 规则零激活处理方法

 $S_i^k = 1/(1 + d_i^k)$ (10)

1) W = [] /*数组初始化为空*/

2) for Rk in Rules do

3) for Ui in Rk do

4) calculate similarity of (xi,Ui) /*依据式(9), σ取较大值, 保证规则全激活*/

5) end for

6) calculate wk /*式(8)*/

7) W.append(wk)

8) end for

9) sort(W) (descending)

10) threshod = W[t]

11) Rules2 = []

12) for Rk in Rules do

13) if wk > threshod do

14) Rules2.append(Rk)

15) end if

16) end for

17) return Rules2

2.4 EBRB推理方法改进

1) 给定输入 $X = ({x_1},{x_2}, \cdots ,{x_T})$ ，首先根据式(2)~(5)计算得X的置信分布表示：

 $\begin{array}{*{20}{l}} {\alpha {\rm{ }} = \left\{ {{\alpha _{ij}},i = {\rm{ }}1,2, \cdots ,T,j = 1,2, \cdots ,{J_i}} \right\}} \end{array}$

2) 根据式(9)得到该输入与第k条规则对应的每个条件属性的个体匹配度：

 ${S^k} = \{ S_1^k({x_1},{U_1}),S_2^k({x_2},{U_2}), \cdots ,S_T^k({x_T},{U_T})\}$

3) 循环执行2)，得到输入X与规则库中所有规则的个体匹配度；

4) 以步骤2)、3)得到的结果为基础，按照公式(8)计算出每条规则对应的激活权重，如下所示：

 $W(X) = \{ {W_1}(X),{W_2}(X), \cdots ,{W_L}(X)\}$

5) 如果步骤4)中出现规则零激活问题，则执行步骤6)；否则执行步骤7)；

6) 执行2.3节提出的二次处理算法，重新计算个体匹配度，并且只选择激活权重前t大的规则进行ER推理；

7) 运行ER算法融合所有激活规则，得到EBRB系统的输出结果。

2.5 时间复杂度分析

EBRB系统推理部分，将输入转变为对应的置信分布形式需要O(TJ)；计算个体匹配度的时间需要O(LTJ)，规则权重的计算需要O(LT)，若出现规则零激活，需执行二次处理算法，处理时间变为O(LTJ+LlogL)。由于只有激活权重超过零的规则才会进入ER推理，这里假设有αL条规则进入ER推理，其中 $\alpha \in \left[ {0,1} \right]$ ，则有EBRB的推理时间为O(NαL)。因此本文改进的EBRB系统处理每一条输入数据的时间复杂度为O(L(TJ+αN+logL))。

3 实验与结果

3.1 非线性函数拟合

 $f(x) = x\sin ({x^2}),0 \leqslant x \leqslant 3$ (11)

 Download: 图 6 不同σ值函数拟合曲线 Fig. 6 Function fitting curve corresponding to different σ

 Download: 图 7 不同个体匹配度的函数拟合曲线 Fig. 7 Function fitting curve based on different individual matching methods

3.2 输油管道检漏

 Download: 图 8 EBRB-S3与真实输出三维图 Fig. 8 3D diagram of EBRB-S3 and real output
4 结束语

 [1] YANG Jianbo, LIU Jun, WANG Jin, et al. Belief rule-base inference methodology using the evidential reasoning approach-RIMER[J]. IEEE transactions on systems, man, and cybernetics-part A: systems and humans, 2006, 36(2): 266-285. DOI:10.1109/TSMCA.2005.851270 (0) [2] HWANG C L, YOON K. Methods for multiple attribute decision making[M]//HWANG C L, YOON K. Multiple Attribute Decision Making. Berlin, Heidelberg: Springer, 1981: 58–191. (0) [3] ZADEH L A, KLIR G J, YUAN Bo. Fuzzy sets, fuzzy logic, and fuzzy systems: selected papers[M]. River Edge, NJ: World Scientific, 1996. (0) [4] DEMPSTER A P. A generalization of Bayesian inference[J]. Journal of the royal statistical society: series B (methodological), 1968, 30(2): 205-247. DOI:10.1111/j.2517-6161.1968.tb00722.x (0) [5] ROTA G C. A mathematical theory of evidence: G. Shafer, Princeton University Press, 1976, 297 pp[J]. Shafer, Princeton University Press, 1977, 24(3): 341. (0) [6] 周志杰, 杨剑波, 胡昌华, 等. 置信规则库专家系统与复杂系统建模[M]. 北京: 科学出版社, 2011. ZHOU Zhijie, YANG Jianbo, HU Changhua, et al. Belief rule base expert system and complex system modeling[M]. Beijing: Science Press, 2011. (0) [7] XU Dongling, LIU Jun, YANG Jianbo, et al. Inference and learning methodology of belief-rule-based expert system for pipeline leak detection[J]. Expert systems with applications, 2007, 32(1): 103-113. DOI:10.1016/j.eswa.2005.11.015 (0) [8] 杨隆浩, 蔡芷铃, 黄志鑫, 等. 出租车乘车概率预测的置信规则库推理方法[J]. 计算机科学与探索, 2015, 9(8): 985-994. YANG Longhao, CAI Zhiling, HUANG Zhixin, et al. Belief rule-base inference methodology for predicting probability of taking taxi[J]. Journal of frontiers of computer science and technology, 2015, 9(8): 985-994. (0) [9] WANG Yingming, YANG Jianbo, XU Dongling, et al. Consumer preference prediction by using a hybrid evidential reasoning and belief rule-based methodology[J]. Expert systems with applications, 2009, 36(4): 8421-8430. DOI:10.1016/j.eswa.2008.10.052 (0) [10] YANG Jianbo, WANG Yingming, XU Dongling, et al. Belief rule-based methodology for mapping consumer preferences and setting product targets[J]. Expert systems with applications, 2012, 39(5): 4749-4759. DOI:10.1016/j.eswa.2011.09.105 (0) [11] YANG Jianbo, LIU Jun, XU Dongling, et al. Optimization models for training belief-rule-based systems[J]. IEEE transactions on systems, man, and cyberneticspart A: systems and humans, 2007, 37(4): 569-585. DOI:10.1109/TSMCA.2007.897606 (0) [12] CHEN Yuwang, YANG Jianbo, XU Dongling, et al. Inference analysis and adaptive training for belief rule based systems[J]. Expert systems with applications, 2011, 38(10): 12845-12860. DOI:10.1016/j.eswa.2011.04.077 (0) [13] 常瑞, 张速. 基于优化步长和梯度法的置信规则库参数学习方法[J]. 华北水利水电大学学报, 2011, 32(1): 154-157. CHANG Rui, ZHANG Su. An algorithm for training parameters in belief rule-bases based on gradient methods with optimization step size[J]. Journal of North China Institute of Water Conservancy and Hydroelectric Power, 2011, 32(1): 154-157. DOI:10.3969/j.issn.1002-5634.2011.01.044 (0) [14] 王韩杰, 杨隆浩, 傅仰耿, 等. 专家干预下置信规则库参数训练的差分进化算法[J]. 计算机科学, 2015, 42(5): 88-93. WANG Hanjie, YANG Longhao, FU Yanggeng, et al. Differential evolutionary algorithm for parameter training of belief rule base under expert intervention[J]. Computer science, 2015, 42(5): 88-93. DOI:10.11896/j.issn.1002-137X.2015.05.018 (0) [15] 苏群, 杨隆浩, 傅仰耿, 等. 基于变速粒子群优化的置信规则库参数训练方法[J]. 计算机应用, 2014, 34(8): 2161-2165. SU Qun, YANG Longhao, FU Yanggeng, et al. Parameter training approach based on variable particle swarm optimization for belief rule base[J]. Journal of computer applications, 2014, 34(8): 2161-2165. DOI:10.11772/j.issn.1001-9081.2014.08.2161 (0) [16] CHANG Leilei, ZHOU Yu, JIANG Jiang, et al. Structure learning for belief rule base expert system: a comparative study[J]. Knowledge-based systems, 2013, 39: 159-172. DOI:10.1016/j.knosys.2012.10.016 (0) [17] 杨隆浩, 王晓东, 傅仰耿. 基于关联系数标准差融合的置信规则库规则约简方法[J]. 信息与控制, 2015, 44(1): 21-28, 37. YANG Longhao, WANG Xiaodong, FU Yanggeng. Rule reduction approach to belief rule base using correlation coefficient and standard deviation integrated method[J]. Information and control, 2015, 44(1): 21-28, 37. (0) [18] 王应明, 杨隆浩, 常雷雷, 等. 置信规则库规则约简的粗糙集方法[J]. 控制与决策, 2014, 29(11): 1943-1950. WANG Yingming, YANG Longhao, CHANG Leilei, et al. Rough set method for rule reduction in belief rule base[J]. Control and decision, 2014, 29(11): 1943-1950. (0) [19] LIU Jun, MARTINEZ L, CALZADA A, et al. A novel belief rule base representation, generation and its inference methodology[J]. Knowledge-based systems, 2013, 53: 129-141. DOI:10.1016/j.knosys.2013.08.019 (0) [20] YANG Longhao, WANG Yingming, FU Yanggeng. A consistency analysis-based rule activation method for extended belief-rule-based systems[J]. Information sciences, 2018, 445-446: 50-65. DOI:10.1016/j.ins.2018.02.059 (0) [21] 林燕清, 傅仰耿. 基于NSGA-Ⅱ的扩展置信规则库激活规则多目标优化方法[J]. 智能系统学报, 2018, 13(3): 422-430. LIN Yanqing, FU Yanggeng. NSGA-II-based EBRB rules activation multi-objective optimization[J]. CAAI transactions on intelligent systems, 2018, 13(3): 422-430. (0) [22] 苏群, 杨隆浩, 傅仰耿, 等. 基于BK树的扩展置信规则库结构优化框架[J]. 计算机科学与探索, 2016, 10(2): 257-267. SU Qun, YANG Longhao, FU Yanggeng, et al. Structure optimization framework of extended belief rule base based on BK-tree[J]. Journal of frontiers of computer science and technology, 2016, 10(2): 257-267. (0) [23] YANG Longhao, WANG Yingming, SU Qun, et al. Multi-attribute search framework for optimizing extended belief rule-based systems[J]. Information sciences, 2016, 370/371: 159-183. DOI:10.1016/j.ins.2016.07.067 (0) [24] LIN Yanqing, FU Yanggeng, SU Qun, et al. A rule activation method for extended belief rule base with VP-tree and MVP-tree[J]. Journal of intelligent and fuzzy systems, 2017, 33(6): 3695-3705. DOI:10.3233/JIFS-17521 (0) [25] CALZADA A, LIU Jun, WANG Hui, et al. A new dynamic rule activation method for extended belief rule-based systems[J]. IEEE transactions on knowledge and data engineering, 2015, 27(4): 880-894. DOI:10.1109/TKDE.2014.2356460 (0) [26] 林燕清, 傅仰耿. 基于改进相似性度量的扩展置信规则库规则激活方法[J]. 中国科学技术大学学报, 2018, 48(1): 20-27. LIN Yanqing, FU Yanggeng. A rule activation method for extended belief rule base based on improved similarity measures[J]. Journal of University of Science and Technology of China, 2018, 48(1): 20-27. DOI:10.3969/j.issn.0253-2778.2018.01.003 (0) [27] JIAO Lianmeng, PAN Quan, DENOEUX T, et al. Belief rule-based classification system: extension of FRBCS in belief functions framework[J]. Information sciences, 2015, 309: 26-49. DOI:10.1016/j.ins.2015.03.005 (0) [28] COVER T M, HART P E. Nearest neighbor pattern classification[J]. IEEE transactions on information theory, 1967, 13(1): 21-27. DOI:10.1109/TIT.1967.1053964 (0)