哈希索引的扩展置信规则库推理方法

doi:10.19665/j.issn1001-2400.2019.02.024

摘要/Abstract

摘要：

由于扩展置信规则库在推理过程中需要遍历规则库中所有的无序规则,所以当规则库很大时,扩展置信规则库系统的推理效率不高。鉴于此,提出使用局部敏感哈希算法构建置信规则索引的优化方法。首先用局部敏感哈希算法为规则库中的所有规则生成特殊的局部敏感哈希值,该哈希值能尽量保持原始规则之间的相似度,因此相似的规则有较大的概率得到相同的索引值;然后通过对输入数据的处理,在索引表中找到与输入数据邻近的规则,并有选择地激活这些规则,从而提高该系统的组合推理效率;最后通过选用非线性函数拟合实验和输油管道的泄漏检测仿真实验,对基于局部敏感哈希索引的扩展置信规则库系统进行检测和验证。实验结果表明,局部敏感哈希算法能够有效地优化扩展置信规则库系统的推理效率,并能够提高输出结果的准确率。

关键词: 扩展置信规则库, 局部敏感哈希, 索引优化, 证据推理

Abstract:

Since the extended belief rule base needs to iterate by all the unordered rules in the inference process, it will result in a low efficiency of the belief rule base in system inference with a large number of rules. Therefore, this paper proposes to use the Locality Sensitive Hashing algorithm to index the confidence rule. First, Locality Sensitive Hashing is used to generate special locality sensitive hash value for all the rules in the Extended belief rule base and the hash value can keep the similarity between the original rules, so that similar rules have a greater probability of obtaining the same index value. Then, by processing the input data, we find the rules that are adjacent to the input data in the index table, and selectively activate these rules, thus improving the system’s inference efficiency. Finally, by choosing a nonlinear function fitting experiment and a simulation experiment on oil pipeline leak to the detection Extended belief rule base system based on the Locality Sensitive Hashing index, experimental results show that the Locality Sensitive Hashing algorithms can effectively optimize the Extended belief rule base system inference efficiency and improve the accuracy of the output results.

Key words: extended belief rule base, locality sensitive Hashing, index optimization, evidential reasoning

中图分类号:

TP18

刘莞玲,肖承志,傅仰耿. 哈希索引的扩展置信规则库推理方法[J]. 西安电子科技大学学报, 2019, 46(2): 145-151.

LIU Wanling,XIAO Chengzhi,FU Yanggeng. Extended belief rule base inference method based on the Hash index[J]. Journal of Xidian University, 2019, 46(2): 145-151.

图/表 8

图1

图2

表1

图3

图4

图5

表2

表3

参考文献 20

[1]	周志杰, 杨剑波, 胡昌华 . 置信规则库专家系统与复杂系统建模[M]. 北京: 科学出版社, 2011.
[2]	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.1007/978-3-540-44792-4_4
[3]	SHAFER G. A Mathematical Theory of Evidence[M]. Princeton: Princeton University Press, 1976.
[4]	HWANG C L, YOON K . Multiple Attribute Decision Making[M]. Heidelberg: Springer-Verlag, 1981.
[5]	ZADEH L A . Fuzzy Sets[J]. Information and Control, 1965,8(3):338-353. doi: 10.1016/S0019-9958(65)90241-X
[6]	SUN R . Robust Reasoning: Integrating Rule-based and Similarity Based Reasoning[J]. Artificial Intelligence, 1995,75(2):241-295. doi: 10.1016/0004-3702(94)00028-Y
[7]	YANG J B, LIU J, WANG J , 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
[8]	YANG J B . Rule and Utility Based Evidential Reasoning Approach for Multiattribute Decision Analysis under Uncertainties[J]. European Journal of Operational Research, 2001,131(1):31-61. doi: 10.1016/S0377-2217(99)00441-5
[9]	YANG J B, XU D L . On the Evidential Reasoning Algorithm for Multiple Attribute Decision Analysis under Uncertainty[J]. IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, 2002,32(3):289-304. doi: 10.1109/TSMCA.2002.802746
[10]	ABUDAHAB K, XU D L, CHEN Y W . A New Belief Rule Base Knowledge Representation Scheme and Inference Methodology Using the Evidential Reasoning Rule for Evidence Combination[J]. Expert Systems with Applications, 2016,51(C):218-230. doi: 10.1016/j.eswa.2015.12.013
[11]	刘莞玲, 王韩杰, 傅仰耿 , 等. 基于差分进化算法的置信规则库推理的分类方法[J]. 中国科学技术大学学报, 2016,46(9):764-773.
	LIU Wanling, WANG Hanjie, FU Yanggeng , et al. Belief rule based inference methodology for classification based on differential evolution algorithm[J]. Journal of University of Science and Technology of China, 2016,46(9):764-773.
[12]	YANG J B, LIU J, XU D L , et al. Optimization Models for Training Belief-rule-based Systems[J]. IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, 2007,37(4):569-585. doi: 10.1109/TSMCA.2007.897606
[13]	杨慧, 吴沛泽, 倪继良 . 基于改进粒子群置信规则库参数训练算法[J]. 计算机工程与设计, 2017(2):400-404. doi: 10.16208/j.issn1000-7024.2017.02.023
	YANG Hui, WU Peize, NI Jiliang . Belief Rule Base Parameter Training Approach Based on Improved Particle Swarm Optimization[J]. Computer Engineering and Design, 2017(2):400-404. doi: 10.16208/j.issn1000-7024.2017.02.023
[14]	QIAN B, WANG Q Q, HU R , et al. An Effective Soft Computing Technology Based on Belief-rule-base and Particle Swarm Optimization for Tipping Paper Permeability Measurement[J]. Journal of Ambient Intelligence and Humanized Computing, 2017(15):1-10. doi: 10.1007/s12652-017-0667-1
[15]	LIU J, 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
[16]	苏群, 杨隆浩, 傅仰耿 , 等. 基于BK 树的扩展置信规则库结构优化框架[J]. 计算机科学与探索, 2016,10(2):257-267. doi: 10.3778/j.issn.1673-9418.1505065
	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. doi: 10.3778/j.issn.1673-9418.1505065
[17]	DATAR M, INDYK P, IMMORLICA N , et al. Locality-sensitive Hashing Scheme Based on p-stable Distributions[C]// Proceedings of the 2004 Annual Symposium on Computational Geometry. New York: ACM, 2004: 253-262.
[18]	LI J W, LIU X X . Evidence Combination Rule Based on Vector Conflict Representation Method[J]. Computer Science, 2016,43(12):58-62.
[19]	CHEN Y W, YANG J B, XU D L , et al. On the Inference and Approximation Properties of Belief Rule Based Systems[J]. Information Sciences, 2013,234:121-135. doi: 10.1016/j.ins.2013.01.022
[20]	DU Y W, WANG Y M . Evidence Combination Rule with Contrary Support in the Evidential Reasoning Approach[J]. Expert Systems with Applications, 2017,88:193-204. doi: 10.1016/j.eswa.2017.06.045

系统类型	参数r	平均绝对误差	搜索数	时间/s
EBRB		0.581884	665417	0.476
E2LSH-EBEB	0.005	0.165328	210752	0.183
E2LSH-EBEB	0.010	0.020261	2333	0.052
E2LSH-EBEB	0.050	0.044291	15512	0.079

系统类型	参数r	平均绝对误差	搜索数	时间/s
EBRB		0.236659	1395748	2.159
BK-EBRB		0.130538	98849	0.195
E2LSH-EBRB	0.001	0.125886	101530	0.215
E2LSH-EBRB	0.005	0.132593	98988	0.206
E2LSH-EBRB	0.010	0.140714	99845	0.207

每组的函数数量-函数组数	平均绝对误差	搜索数	时间/s
01-01	0.143809	88521	0.138
03-05	0.132593	98988	0.206
05-22	0.128522	98913	0.392