基于FDR的证据理论改进算法

侯庆山，邢进生

(山西师范大学 数学与计算机科学学院，山西 临汾 041000)

0 引 言

证据理论[1]是模糊决策的有效工具，在目标识别、决策、优化[2-3]等问题中得到了广泛的应用。为了简化样本在特征融合过程中的复杂性，往往在特征融合前对原始样本的特征进行简单的筛选、降维[4]等一系列处理。此外，样本特征权重分配对实验结果的影响较大，对此可以采用这样的方法：在特征融合时，对于相互矛盾的样本特征，可以分配较低权重或分配权重为零。但是，当数据样本特征过多时，这样的处理方式往往是过于复杂的。

为了减小证据冲突的影响，文献[5]提出了一种基于将证据交集部分转化为联合部分的组合规则。但是，随着冲突的增加，该方法的性能变得越来越差。文献[6]提出了一种基于计算所有证据平均值的证据组合方法，但并没有考虑证据权重对于融合结果的影响，将所有的权重设定为同一值。因此，为了更好地确定每个证据的权重，引入证据相似性来计算每个证据的冲突程度，模糊度较大的证据由于包含的信息少而赋予较小的权重值，这样的证据权重分配更为合理，因此样本分类更准确。文献[7]提出了一种基于文献[8]模糊度测量方法的证据组合规则，文献[8]提出了一种改进的基于证据距离测量的平均组合方法，每个证据主体(body of evidence，BOE)的权重都被考虑在内。但文献[8]的组合规则不能有效地处理高度冲突的证据组合。针对这一问题，文献[7]提出了一种新的加权平均证据组合方法,一方面利用证据的距离，另一方面利用不确定性度量来确定证据主体的权重，可以得到合理的组合结果。但随着样本特征增多，利用不确定性度量来确定证据主体的权重变得困难。文献[9]提出了另一种基于信息熵的证据组合规则，该方法能有效地处理高冲突证据，具有较好的收敛性能，但信息熵的确定需要经过复杂的计算，随着样本的特征数量及分类增多，这种方式的可行性越来越低。文献[10]提出了一种基于证据相似性和惩罚函数的组合规则，该方法将证据分为可信证据和不可信证据两部分。然后，用一种新的信息熵来度量证据的信息量。最后，得到每个证据的权值，并在使用Dempster组合规则之前对证据进行修改，该方法能有效地处理冲突证据，具有较好的收敛性，但对证据进行划分时，由于划分方法存在不足，容易对证据划分错误。文献[11]基于不一致测量值的冲突证据组合方法，提出了一种测量两种证据冲突的新方法，通过选择折现系数对矛盾证据进行修正，但改进后组合规则的融合效果提升不够明显。文献[12-13]提出了两种证据理论的组合方法，前者基于证据距离和模糊偏好，后者基于证据相似性和信念函数熵，然而，这两种方案仍然存在相似性冲突，样本特征的融合过程仍然复杂。

由于相似性碰撞现象[14]以及原始样本特征之间存在关联性，导致现有的证据融合规则过于复杂。此外，现有的融合规则存在无法有效降低冲突证据权重[6]的缺陷。在分析已有算法的基础上，文中提出一种改进的证据融合算法。在样本融合之前进行特征筛选，删除对分类影响较小的特征，简化初始样本特征数量，从而降低融合过程的复杂性。相较于其他融合算法在复杂数据集上的融合过程及融合效果，该算法的过程较为简单，融合效果更好。

1 基础理论

1.1 D-S证据理论

Dempster和Shafer提出的证据理论是一种从不确定信息中进行决策的有效工具。它在许多领域有着广泛应用。有关D-S证据理论的相关定义如下：

定义1：证据理论的基础。在实际应用中，通常2Ω是在空间Ω上的所有子集的集合,2Ω={Ø,{θ1},{θ2},…,{θn},{θ1,θ2},…,{θ1,θ2,…,θn}}。在D-S理论中,数学基本概率分配[15-16]函数,也称为质量函数,满足在2Ω→[0,1]上的映射,满足式(1)。

(1)

定义2：似然函数。似然函数满足式(2)：

(2)

m:m(A),m(B),m(C),…,m(AB),…,m(θ)

定义3：基于定义2，m(A)或m(B)是代表A或B的质量函数，根据Dempster提出的组合规则可以组合一组证据，满足式(3)和式(4)：

(3)

(4)

m是m1和m2的组合结果。当证据数量大于2时，扩展组合规则如式(5)和式(6):

m(A)=

(5)

(6)

运用上述公式可以实现证据融合，但是当某一证据的支持度较小或者不被支持时，组合结果往往是不理想的。为此，一方面可以通过引入证据权值减少此类证据的影响，另一方面可以在样本融合前进行特征筛选，删除支持度小的特征。

1.2 特征选择

在样本特征中往往存在较高的相关度，导致在计算上产生了较大消耗；此外，部分特征对预测结果往往存在不好的影响，甚至是负影响。因此针对样本特征进行选择，即从样本的所有特征中选择部分特征作为新的样本特征，特征值在选择前后可以改变或者不改变，但是选择后的特征维数必然会降低。常用的特征选择方法主要包括以下两种：

(1)均方差分析法。

该方法一般设置某一特定的方差阈值，删除低于阈值的特征；若方差阈值未指定，则保留所有非零方差特征，删除样本中具有相同值的特征。均方差分析法往往适用于样本特征较少的数据集，利用方差对样本数据集进行分析时，与极差和标准差相比较，方差的计算结果能够将样本特征的波动性放大，可以准确地观察出某一样本特征对于样本分类结果的影响程度。不足之处在于，利用方差对样本数据集进行分析要处理数据集上的全部数据，随着数据量和样本数的增多，计算过程将变得复杂。因此方差分析常常运用在数据量或样本特征量较少的数据集上。

(2)主成分分析法。

主成分分析法[17]是一种分析及简化数据集的方法，其目的是降低数据维数，尽可能地降低原始数据的复杂度并使数据损失尽可能的小。利用主成分分析法可以消减回归分析或者聚类分析中特征的数量。在高维数据集中，许多特征之间通常是线性相关的，利用主成分分析可以减小相关特征的个数，降低样本特征间的相关性。但是，对高维数据集进行主成分分析时，首先要确保提取的前几个主成分的贡献率之和应当达到较高水平；其次，对于降维后的样本特征，特征含义一般具有模糊性。在样本特征数量较少时，一般不采用此类方法，因此只有在高维数据集中才使用主成分分析法。

2 基于特征降维的证据理论的改进算法

原始样本数据集进行特征降维之后，减少了相关特征的个数，对降维数据生成新的BPA。对于简单数据集，采用方差分析法，选择方差大于阈值的特征。对于复杂数据集，采用主成分分析法，对样本特征进行选择和降维处理。算法过程描述如下：

输入：原始数据集矩阵

输出：降维数据集矩阵

算法步骤描述如下：

(a)将初始数据按行列排成n行m列的矩阵X；

(b)将矩阵X的每一行进行零均值化处理；

(d)将特征向量按对应特征值的大小按行排列成矩阵，取前K行组成矩阵P；

(e)Y=PX即为降维到K维之后的数据，对所得数据集样本抽样；

(f)对抽样样本进行聚类，标注样本特征以及样本所属类型；

(g)生成区间数模型，针对数据集的某一特征，取所有样本中的最大值以及最小值分别作为所求区间的上界以及下界；

(h)求解某一测试样本特征值与区间数的距离。设A=[a1,a2]和B=[b1,b2]是两个区间数，则区间距离[18]可用式(7)计算：

本工作主要是研究幂零群、内幂零群以及内交换群所对应幂图的一系列图论性质.由于这类群结构比较清晰,可以对其相应幂图或真幂图的性质作进一步研究,主要从能否为线图、独立数性质、可平面性以及连通性等角度讨论.特别地,由于一般群G的任意元素都与单位元相连,故在考察连通性时仅对真幂图P∗(G)进行讨论.

(7)

(i)求解测试样本特征值与区间数模型之间的相似度。设A=[a1,a2]和B=[b1,b2]是两个区间数,相似度计算可采用式(8)：

(8)

其中，α(α>0)为支持度系数。

(j)对求解的相似度进行归一化处理，将归一化之后的结果作为最终BPA。

算法流程如图1所示。

图1 算法流程

特征选择和降维是改进算法中的关键环节，为了便于理解改进算法中包含的降维算法部分，举例如下：

原始数据集矩阵X：

去均值：

特征值：

特征向量：

标准化：

选择大特征值对应的特征向量：

利用公式Y=PX计算经过PCA降维后的数据集矩阵：

3 实 验

3.1 数据集描述

实验所采用数据集取自超过200 000名Instacart用户的300多万份杂货订单的样本，该数据集是匿名的，描述客户订单随时间变化的关系。主要是为了预测哪些产品更有可能出现在用户的下一个订单中。对于每个用户，提供4到100个订单，每个订单中的产品按顺序购买。还提供订单下达的时间，包括星期和小时，以及订单之间的相对时间度量。

3.2 数据库介绍

每个实体(客户、产品和订单等)都具有关联的唯一ID。数据表和变量名称应该是客观真实的。数据表order_products_prior.csv包含所有客户的先前订单内容,数据表orders.csv表明订单的组别，数据表说明如表1所示。

表1 数据说明

3.3 原始数据降维处理

(1)读取四张数据表，利用表中的关联ID将表进行合并处理，然后选取500组合并数据进行实验，部分合并数据如图2所示。

图2 数据表合并处理后部分数据

(2)利用交叉表对每一个用户所购买的物品进行分组，分组后的部分数据如图3所示，表中每一行代表一个用户，每一列代表各用户购买某物品的个数。

图3 用户购买情况部分数据

(3)利用主成分分析算法对数据集进行特征降维，降维后的数据集保存了原数据集90%的信息，特征数量则下降到27个，简化了原始数据集的复杂度，部分降维后的数据如图4所示。

图4 降维后部分数据

(4)对降维后的数据集利用K-means[19-20]算法进行聚类分析，取出数据集中的前500个样本，划分为5类用户，分别由数字0到4表示，聚类结果如图5和图6所示。

图5 样本聚类结果

图6 聚类分布

(5)对以上聚类结果进行分析，计算聚类数据集的轮廓系数为0.612 7，因而可以判定聚类效果良好，轮廓系数可以采用式(9)进行计算：

(9)

其中，i为已聚类数据中的样本，bi为i到其它簇的所有样本的平均距离，ai为i到本身簇的距离平均值，最终通过计算所有样本点的轮廓系数平均值对聚类效果进行分析评定。如果sci小于0，说明ai的平均距离大于最近的其它簇；相反的sci的值越大，说明ai的平均距离小于最近的其他簇，轮廓系数的值是介于[-1,1]，越趋近于1代表数据集的内聚度以及分离度都相对良好。

3.4 对降维后的数据集生成BPA进行分类识别

(1)用降维后的样本数据作为验证数据库,选择5种用户类型的400个样本，每种类型各占80个，取样本中的最大值以及最小值来构造区间数模型，如表2所示。

(2)选取100个测试样本，5类用户各占20个，将它们作为类别未知的测试样本。

(3)通过计算测试样本与区间数模型之间的相似度，求解出各特征值最终的BPA。进一步通过D-S组合规则进行特征融和，产生最终的融合结果。

(4)对融合结果进行分析，测试样本的类型由融合结果决定，哪种类型的BPA的值最大，那么这个BPA对应的类别就是待测样本的类别。

表2 区间数模型

续表2

3.5 实验结果分析

为了检验改进算法在Instacart数据集上的分类效果，选取支持度系数α的值为5，在表2所示的区间数模型的条件下，对500个待测样本的数据集进行测试，包括400个已知分类的训练样本以及100个未知类型的测试样本。实验得出最终的平均类型识别率为94%，对0类型以及3类型用户的识别率达到96%，1类型以及4类型的用户识别率达到92%，2类型用户识别率到达94%。

4 结束语

由于传统证据融合算法在特征融合时过于复杂，样本间存在相似性碰撞，在复杂数据上融合效果不够理想，证据之间存在冲突等问题。文中提出了一种基于特征降维的证据理论改进算法，并采用Instacart数据集对改进算法进行检验。与其他相关算法相比，改进算法简化了证据融合过程中的复杂性，降低了原始样本中特征关联对于融合结果的影响。由实验结果可知，改进算法对于分类问题的平均准确率为94%。由于主成分分析存在降维后特征含义不够明确，证据融合过程中如何将权重合理分配给相关特征等问题，所以下一步工作可以针对特征降维方法以及权重的合理分配做出改进，进一步提高证据融合的效果。