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

刘莞玲，肖承志，傅仰耿

(福州大学 数学与计算机科学学院，福建 福州 350116)

专家系统是人工智能领域最活跃和最广泛的应用领域之一[1]。置信规则库专家系统(Belief Rule Base，BRB)的理论依据是杨剑波等在2006年以D-S证据理论[2-3]、决策理论[4]、模糊理论[5]和传统IF-THEN规则库[6]为基础而提出的基于证据推理算法的置信规则库推理方法[7](belief Rule base Inference Methodology using the Evidential Reasoning approach, RIMER)。置信规则库推理的过程是通过证据推理(Evidential Reasoning, ER)算法实现的[8-9]，相比于神经网络算法和支持向量机等“黑箱”方法，RIMER方法的推理过程具有更好的解释性和透明性[10]。置信规则库专家系统的一系列参数以及与规则相关的概率设置需要通过参数学习来获得[11]。参数训练可以使用Matlab中的FMINCON函数[12]，或者用文献[13-14]中提出的基于群智能算法的方法。

为了便于在更一般和更高级的应用场景里，在不同类型的输入数据格式下，能同时处理不精准、不完整和具有不确定性的数据，Liu等提出了扩展置信规则库(Extended Belief Rule Base, EBRB)专家系统[15]。扩展置信规则库系统优化了系统构建的过程，但推理过程的效率仍有提高的空间[16]。局部敏感哈希(Locality Sensitive Hashing, LSH)算法是可以处理海量高维数据，并且尽量不损失数据之间相似性的一种哈希算法[17]。因此，笔者提出基于局部敏感哈希算法对扩展置信规则库建立局部敏感索引来查找最近邻规则的优化框架，从而达到提高效率的目的。

1 扩展置信规则库系统

1.1 扩展置信规则库的组成与推理

扩展置信规则库主要由一组无序的置信规则组成，每条规则包括前提属性和结果两个部分。这两个部分都嵌入了置信度的概念，规则的前后两部分都以分布式的结构表示。

扩展置信规则库可以表示为R={R1,R2,…,RL}，L表示扩展置信规则库中规则的数量，第k条规则可以表示为

IF{A,αk},THEN{(D1,β1,k),(D2,β2,k),…,(DN,βN,k)} 。

(1)

在进行系统推理之前，需要构建扩展置信规则库系统。Liu等提出了一种数据驱动的构建扩展置信规则库系统的方法[16]。根据输入数据构建出置信规则后，需要设置每一条置信规则相对应的规则权重θk，以及规则中每一个前提属性的权重δi[1]。由于规则之间可能存在不一致性[18]，所以需要对规则进行相似性度量后，再得出每条规则的权重值。

扩展置信规则库系统的推理基础为证据推理算法，通过证据推理算法对置信规则的分析来获得最终的评价等级。在执行证据推理算法前，需要计算出规则相对于输入信息的激活权重，并将结果置信度转化为基本可信值[1]，再利用证据推理算法的相关公式[8-9]，即可获得推理评价等级的分布式置信度。

1.2 问题提出

相比于置信规则库专家系统，扩展置信规则库系统可直接将输入信息转化为有效的置信规则，避免了置信规则库专家系统预设规则存在的维数灾难问题[19]。然而，当输入信息过多而使得规则数量增大时，由于规则是无序存储于扩展置信规则库中的，仍然需要遍历所有的规则来计算规则的激活权重，使得推理的准确率和效率有所下降。为了解决这一问题，笔者引入了局部敏感哈希算法对置信规则建立哈希索引，以此来提高效率。

2 基于E2LSH索引的扩展置信规则库系统

2.1 欧氏局部敏感哈希算法

欧氏局部敏感哈希算法(Exact Euclidean Locality Sensitive Hashing，E2LSH)是基于P-稳定分布(P-Stable)的位置敏感哈希算法。E2LSH是利用了P-Stable在p=2情况下的正态分布来实现的，其函数族可以表示为

(2)

其中，r是映射空间的分段长度；b∈(0,r),是一个随机数；v为置信规则分布式模型转化而得的欧氏空间数值向量；a为正态分布随机向量。函数族中的不同哈希函数是由不同的a与b值决定的。利用E2LSH，可以对扩展置信规则库中的每一条规则生成相对应的哈希值，同时将具有相同的哈希值的规则放入同一个哈希桶中，从而构造局部敏感哈希索引。

在一般情况下，可以只选用一个E2LSH哈希函数构造局部敏感索引。为了进一步提高准确率，可以选用y组，每组x个E2LSH哈希函数。对于两条置信规则，只要某一组中的所有E2LSH对这两条规则生成的哈希值完全相同时，就可以判定这两条规则为相似规则。

假设一个E2LSH将两条规则判定为相似规则的概率为P，则最终得出的概率公式为

Pi=1-(1-Px)y。

(3)

2.2 基于E2LSH索引的扩展置信规则库系统的构建步骤

为方便叙述，下文将基于E2LSH的扩展置信规则库系统称为E2LSH-EBRB系统。由于该系统只对已生成的规则建立E2LSH索引，所以到规则生成这一步之前的所有步骤与扩展置信规则库系统相同。

构建基于E2LSH的局部敏感哈希表的步骤如下：

步骤1 选取y组，每组x个E2LSH哈希函数，然后在正态分布中选取x·y组随机变量，构造出x·y个a向量，同时选取合适的r值，并生成x·y个b值，这样即可构造出E2LSH函数族。

步骤2 对于每一组E2LSH函数，分别根据置信规则数值向量生成一组哈希值，将这组哈希值相同的置信规则放入同一个哈希桶中，并构造该组哈希表，最后生成多组互相独立的哈希表。

完成局部敏感的哈希索引的构建。

2.3 基于E2LSH索引的扩展置信规则库系统的规则搜索

E2LSH-EBEB系统的搜索策略为：利用构造的哈希表索引，筛选规则并计算输入信息的哈希值，将满足与输入信息的其中一份哈希值相同的规则筛选出来，用于激活推理。具体步骤如下：

步骤1 用生成E2LSH哈希函数族对输入信息生成对应于每个哈希表的哈希值。

步骤2 对每个哈希表，将该哈希表中与输入信息对应于该表的哈希值相同的所有规则取出。

步骤3 对取出的多组规则进行去重合并，这些规则即是通过哈希表获得的输入数据的近邻规则。如果最终获得的规则列表为空，此时的策略是单独为这组输入遍历所有的规则。

2.4 E2LSH-EBRB与扩展置信规则库系统的效率比较

E2LSH-EBRB系统在构建过程中，需要额外保存哈希表和哈希函数，因此构建过程会增加一些时间和空间上的额外开销。但在推理过程中，笔者提出的方法在规则搜索上的时间开销显著减少。

3 实验验证与分析

3.1 非线性函数拟合实验

本实验过程中将通过对一个数学函数的拟合来检验E2LSH-EBRB系统。在拟合非线性数学函数时，将比较扩展置信规则库系统和E2LSH-EBRB系统的效率和推理准确性。

选用的非线性数学函数为

f(x)=xcos(x2)-sin(x2), 0.0≤x≤3.0 。

(4)

在构建扩展置信规则库时，函数的输入值x为前提属性，并且对x设定了7个均匀分布的参考值{0.0,0.5,1.0,1.5,2.0,2.5,3.0}；同时，为系统设定了5个评价等级，对应的评价等级效用值依次为{-3.5,-2.0,-0.5,1.0,3.0}。设定好初始等级参数后，在x的取值范围内均匀地选择1 000个数值，并根据数学函数分别计算出真实函数值，然后将这1 000份数据作为系统的初始构造数据，用前文所述的算法构建出E2LSH-EBRB系统。在构建的系统中，哈希函数的组数为22组，每组含有5个E2LSH哈希函数，根据实验情况，参数r的取值为0.01。测试数据为在x的取值范围内均匀地选择1 500个数值。在构造和测试过程中，将以平均绝对误差(Mean Absolute Error, MAE)作为评价指标之一。

图1为扩展置信规则库系统对非线性数学函数的拟合图，可以发现扩展置信规则库的模拟输出与函数的标准输出有较大的差距。拟合效果不理想，这是由于遍历规则的策略对推理结果的干扰造成的。图2为E2LSH-EBRB系统的函数拟合图，显然拟合效果有所提高，且拟合图像的曲线与标准输出图像的曲线基本重合。

图1 EBRB系统的函数拟合图图2 E2LSH-EBRB系统的函数拟合图

表1中比较了扩展置信规则库和E2LSH-EBRB对非线性数学函数拟合的实验结果以及运行时间。由表1可知，扩展置信规则库系统在函数拟合过程中搜索规则的次数较多，从而使得系统推理过程的效率不高；而由于规则库中存在许多与输入数据无关联的规则，遍历时也会激活这些规则，从而对测试结果造成干扰，增大了平均绝对误差值。而E2LSH-EBRB筛选出了近邻规则参与推理，在提高系统推理的效率的同时，也提高了系统的准确率。在不同的r参数下，E2LSH-EBRB系统的表现也不同，所以需要根据系统的情况来确定参数r的取值，否则或大或小都会影响推理的效率和准确率。在拟合公式(4)的实验中，参数r的最佳取值为0.010。

表1 函数拟合效率与准确率

3.2 输油管道泄漏仿真实验

为了进一步验证E2LSH-EBRB方法解决实际问题的有效性，选择英国的一条100多公里长的输油管道作为研究对象[20]，使用该输油管道的真实泄漏数据对笔者提出的E2LSH优化模型进行验证。在输油管道泄漏的问题中，由于管道泄漏将会使管道中油液的流量和压力发生变化，因此可以根据油管中输入输出的油液流量差(Flow Diff,FD)和油液对管道产生的平均压力差(Pressure Diff, PD)来估计油管泄漏(Leak Size, LS)的大小。

对于本次输油管道泄漏的仿真实验，根据真实输油管道从正常状态到发生管道泄漏25%的事故，选取了2 007组数据作为本次测试的数据。FD和PD作为扩展置信规则库系统的输入。通过输入这两个数值，推理出输油管道的泄漏情况。LS即为规则的评价等级部分。在构建的系统中，哈希函数的组数为5组，每组含有3个E2LSH哈希函数，根据实验情况，参数r的取值为0.005。根据专家经验可以得出，FD的8个前提属性参考值分别为{-11,-6,-3,-1,0,1,2,3}，PD的7个前提属性参考值分别为{-0.061,-0.005,-0.002,0.000,0.005,0.010,0.060}，LS的5个评价等级参考值分别为{0,2,4,6,8}。构建扩展置信规则库(EBRB)、BK-EBRB和E2LSH-EBRB的初始构造数据是按一定比例从2 007组测试数据中选取出的1 500组数据。在构造和测试过程中，将以平均绝对误差作为评价指标之一。

图3至图5分别为EBRB系统、BK-EBRB系统和E2LSH-EBEB系统的推理输出与真实数据的比较。从图中可以发现，扩展置信规则库系统的输出与真实数据的差异性是3个系统中最大的，这是由于无关联规则造成的干扰。如图4所示，BK-EBRB系统在规则查找上引入了基于BK树的树形索引优化，因而获得的推理输出与真实输出比较接近。

图3 EBRB系统输出和测试数据图4 BK-EBRB系统输出和测试数据

图5 E2LSH-EBRB系统输出和测试数据

而笔者提出的E2LSH局部敏感哈希优化模型在规则查找上引入了局部敏感索引哈希桶，从而筛选出了与输入信息近邻的规则参与计算激活权重，在减少查找的规则数的同时，也避免了无关联规则的干扰。所以在图5中，E2LSH-EBRB系统的输出与真实数据的输出能够很好地拟合。综合分析可得到，E2LSH-EBRB系统在准确率上相比于扩展置信规则库系统有很大的提高。

表2中列出了EBRB、BK-EBRB和不同r参数下的E2LSH-EBRB产生的模拟输出的实验结果和各项评价指标。由表2可知，EBRB系统的效率和准确率明显低于BK-EBRB和E2LSH-EBRB。比较和分析不同r参数下的E2LSH-EBRB可以发现，当r=0.005时，E2LSH-EBRB系统推理的效率最优。在这一参数下，对比于BK-EBRB组合系统，效率和准确率的差距并不是很大。

表2 油管泄漏测试效率与准确率

表3中给出了当E2LSH哈希函数的组数和每组的函数数量不同的情况下，E2LSH-EBRB系统的各项测试指标。由表3可以发现，当哈希函数的组数和每组的函数数量增加时，由于产生了更多的相互独立的哈希表，因此每次搜索哈希表时所用的时间会有所增加。但随着数量的增加，系统推理的准确率呈上升趋势。影响因素有两个方面，一方面是多个相互独立的哈希表互相影响，减小了各自漏判近邻规则的概率；另一方面，由于单个哈希表中采取了AND优化，哈希函数数量的增加可以减少对近邻规则误判的概率，两个因素相互影响，从而提高了系统的准确率。

表3 不同参数下的E2LSH-EBRB测试效率与准确率

因此，在实际应用中，需要根据应用情况对推理精度和推理效率的要求来选取哈希函数的组数和每组的函数数量。对于碰撞概率为0.5的情况，在选取哈希函数的组数和每组的函数数量后，应满足转化后的碰撞概率保持为0.5不变。

4 总 结

针对扩展置信规则库系统在推理过程中由于规则是无序的，且计算规则的激活权重时须遍历所有规则，导致系统的推理效率不高的问题，引入了基于正态分布的局部敏感哈希算法(E2LSH)。该算法为扩展置信规则库系统的所有规则建立局部敏感的哈希索引表，通过查找索引哈希桶筛选出较少的近邻规则来计算激活权重。相比于遍历所有规则的扩展置信规则库系统，E2LSH-EBEB系统在推理效率上有了很大的提升；同时，也去除了无关联规则对推理结果的干扰，提高了算法的推理准确率。在实验部分，选用非线性函数的拟合实验和输油管道的泄漏检测仿真实验，证明了E2LSH索引优化算法的有效性，并且说明了不同的参数选取对E2LSH索引优化模型的影响。笔者提出的方法在选取单一E2LSH函数时会对推理结果的准确率造成较小的影响，但在采用多组E2LSH情况下，会大大减少碰撞概率，提高系统的稳定性。未来将进一步了解各参数的最优选取方式，对比其他局部敏感哈希算法的优劣，并对建立局部敏感索引的模型进行更深层次优化，提出更准确、高效的推理方法。