基于特征选择和两步分类策略的证据分类器

本文研究了利用信任函数从不确定数据中高效学习的方法，提出了一种由特征选择过程和两步分类策略组成的监督学习方法。 利用训练信息，提出特征选择过程通过最小化目标函数自动确定信息最丰富的特征子集。 提出的两步分类策略进一步提高了决策精度通过使用在分类过程中获得的互补信息。 在各种合成数据集和真实数据集上对该方法的性能进行了评价。

1、背景知识

1.1 信任函数

1.2 E-KNN

2、提出的方法

本文提出的特征选择过程和两步分类策略都需要适当处理数据中的不确定性和不精确性。为此，第2.1节将首先介绍一个简单而具体的mass函数构建过程。 提出的特征选择程序和两步分类策略分别在第2.2和2.3节中提出。

2.1 构建mass函数

假设{(Xi,Yi)∣i=1,...,N}\{(X_i,Y_i)|i = 1,...,N\}{(Xi​,Yi​)∣i=1,...,N}为训练集，其中X为样本，Y为样本对应的标签，识别框架Ω={ω1,...,ωc}\Omega = \{\omega_1,...,\omega_c\}Ω={ω1​,...,ωc​}为对应的标签。对输入样本$X^t$进行标签测试，使用DS+Yager规则进行以下mass函数的构建：
（1）首先找出样本$X^t$基于欧氏距离在测试集中的K近邻；假设$X_j$为$X^t$的第j个近邻，且其标签$Y_j={\omega }_q$。根据E-KNN方法得出$X^t$标签同样为${\omega }_q$的证据。
（2）${\Gamma }_q(q=1,...,c)$为有着相同标签${\omega }_q$的近邻集合， 由于同一集合${\Gamma }_q$中的mass函数Γq具有相同的焦点元素，故这些mass函数之间没有冲突。 因此，无视异常值（在我们的方法中没有考虑的特定情况），Dempster的规则适合于将${\Gamma }_q$中的证据结合起来。 因此，非空${\Gamma }_q$提供的证据被表示为一个简单的mass函数：

如果${\Gamma }_q$为空，那么$m_t^{{\Gamma }_q}$被定义空质量函数$m_t^{{\Gamma }_q}(\Omega )=1$。
（3）当大部分的测试样本$X^t$都属于某一个标签时（如${\omega }_q$），那么$X^t$属于该标签的信任度也应该较大。 因此，我们可以假设每一组${\Gamma }_q$提供的证据的可靠性随着其基数$|{\Gamma }_q|$而增加。 因此，在最后一步中得到的质量函数已经是打折过的：

其中${\Gamma }_{max}$是{∣Γ1∣,...,∣Γc∣}\{|\Gamma_1|,...,|\Gamma_c|\}{∣Γ1​∣,...,∣Γc​∣}中的最大基数，$\eta$是控制打折水平的系数。
（4） 在上一步描述的打折过程之后，现有的质量函数可能仍然是部分冲突的，特别是当具有较小近邻数却有着不同标签的样本。 由于Yager的融合规则在结合高度冲突的证据比Dempster的规则表现更好，故它是用来融合在上一步中获得从的可能相互冲突的mass函数集合${\Gamma }_1$到${\Gamma }_c$。 因此，关于对象$X^t$的类标签的全局mass
函数最终为：

$m_t$的焦点元素是单例和整个识别框架，因此，可信度和plausibity将导致对$X^t$有着相同假设。 上述方法结合了Dempster和Yager规则的优点。 因此，在分类应用中，这个特定的过程允许比我们获得的更稳健的不确定性表示 两个经典组合规则中的任何一个。

2.2 基于信任函数的特征选择

在模式识别应用中，数据可能包含不相关或冗余的特征。 特征选择技术旨在应对这一问题。目标是选择一个子集的特征，可以促进数据解释，同时减少存储需求和提高预测性能。 滤波器、包装器和嵌入式方法是广泛用于特征选择的三大类算法，应当满足一下三个要求：
（1）所选择的特征应该是关于类标签的信息，也就是说，它们不应该产生比完整的特征集更低的分类精度。
（2）所选特征子集应该有能力减少数据的不确定性，即它应该导致特征空间中不同类之间的小重叠。
（3） 所选择的特征应该是稀疏的可能的。 具有较小基数的特征子集意味着较低的存储需求和较低的过度拟合风险。
通过最小化来自训练样本的目标函数，可以同时满足上述三个要求。 为了清晰地呈现这一目标函数，首先应该讨论加权的欧式距离。加权欧氏距离将为被测样本生成不同的K最近邻集。测试样本$X^t$同有m个特征的测试集样本$X_i$之间的加权欧式距离定义如下：

其中$d_{t,i}^p(1\le p\le m)$是第p个特征元素两个特征向量的差值，λp∈{0,1}\lambda_p\in\{0,1\}λp​∈{0,1}是相应的系数。 显然，可以通过改变系数向量的值来选择特征子集。 因此，当${\lambda }_p=1$时，特征向量的第p个分量将被选择，当${\lambda }_p=0$时，它将被消除。
基于加权欧氏距离和2.1提到的mass函数构建方法， 我们可以提出一个目标函数，构建满足上述三个要求的合格特征子集。设{(Xi,Yi)∣i=1,...,N}\{(X_i,Y_i)|i = 1,...,N\}{(Xi​,Yi​)∣i=1,...,N}为训练集，目标函数定义为：

其中第一项是是对应于上述讨论的第一个要求的平方误差，其中$P{L}_i$是训练样本$X_i$的plausibility方程，$t_{i,q}$是一个c维二进制向量的第q个组成元素，当$Y_i={\omega }_q$时$t_{i,q}=1$，反之亦然。第二项是分配给整个识别框架的平均mass值， 它是导致高不确定性和不精确的特征子集的罚项，从而允许我们满足第二个要求。最后一项是在另一篇文章中用到的$l_0-norm$的近似值，作用是使得选中的特征子集稀疏化。这里的$\rho ,\delta$是介于$[0,1]$之间的超参数， 分别影响不确定性样本的数量和得到的特征子集的稀疏性，它们的值应该被调整以最大限度地提高分类精度。参数$\mu$设置为常量，一般为5。对该公式进行化简，可得公式（13）：
$$obj=\frac{1}{n}\sum _{i=1}^n\sum _{q=1}^c(1-t_{i,q}-\sum _{h\ne q}{B}_h^i{)}^2+\frac{\rho }{n}\sum _{i=1}^n(1-\sum _{q=1}^c{B}_q^i)+\delta \sum _{p-1}^m[1-exp(-\mu {\lambda }_p)]$$
其中：


其中$d_{ij}$是测试样本$X_i$和训练集使用加权欧氏距离计算的距离，其中用到的优化参数为{λ1,...,λc}\{\lambda1, ...,\lambda_c\}{λ1,...,λc​}。 在优化过程中，每个训练样本的K最近邻$(X_i,Y_i)$ 由具有当前权重的加权距离度量{λ1,...,λc}\{\lambda1, ...,\lambda_c\}{λ1,...,λc​}确定。mass函数$m_i$是使用3.1节中提出的构造过程计算的，mass和plausibility随二元系数的{λ1,...,λc}\{\lambda1, ...,\lambda_c\}{λ1,...,λc​}而变化，最终驱动目标函数（12)-(13)的减小。

2.3两步分类

在使用上一节中描述的过程选择特征后，两步分类策略允许我们根据信任函数对未知测试样本进行分类。 作为测试数据T={sj,j=1,...,nt}T=\{s_j,j=1,...,n_t\}T={sj​,j=1,...,nt​}，两步分类策略可以描述如下：
（1）对于训练样本对$(X_i,Y_i),i=1,...N$使用DS+yager规则对每个训练样本$S_j$计算mass函数$m_j$；基于$m_j$，集合T被分为了两个子集$T^1$和$T^2$，T1={Sj:maxA⊆Ωmj(A)≠mj(Ω)}T^1=\{S_j:max_{A\subseteq\Omega}m_j(A)\neq m_j(\Omega)\}T1={Sj​:maxA⊆Ω​mj​(A)​=mj​(Ω)}，T2={Sj:maxA⊆Ωmj(A)=mj(Ω)}T^2=\{S_j:max_{A\subseteq\Omega}m_j(A)= m_j(\Omega)\}T2={Sj​:maxA⊆Ω​mj​(A)=mj​(Ω)}。
（2） 然后，将$T^1$中的测试样本划分为有着最高mass函数的类。 例如，如果对于所有的$q\ne 1$都有m({ω1})>m({ωq})m(\{\omega_1\})>m(\{\omega_q\})m({ω1​})>m({ωq​})，我们将$S_j$标记为${\omega }_1$。
（3） 在对$T^1$中的测试样本进行分类后，我们将这些标记测试样本添加到训练集$(X_i,Y_i),i=1,...N$，从而获得更大的训练集$(X_i^{,},Y_i^{,}),i=1,...N^{,}$。 然后通过对对应于该类的训练样本进行平均来定义每个类${\omega }_j$的ER（或原型）$p_j$:

其中$c_j$是在类训练样本在${\omega }_j$类下的集合{Xi∣Yi=ωj}\{X_i|Y_i=\omega_j\}{Xi​∣Yi​=ωj​}的基数，以及$j=1,...,c$。
（4）对于$T^2$（标签不明确但是$\Omega$的信任函数值最大）中的样本，应考虑与给出样本的相关度，故使用马氏距离（ Mahalanobis distance）计算该集合中样本与每个类中心的距离。假设$S_0$为$T^2$中的样本，则其与类中心$p_j$的马氏距离为：

其中$S_0^q,p_j^q$分别是$S_0$和$p_j$的第q维，${\delta }_j^q$ 是属于${\omega }_j$类的训练样本中第q个特征的标准差。最终得到集合{md(S0,p1),...,md(S0,pj)}\{md(S_0,p_1),...,md(S_0,p_j)\}{md(S0​,p1​),...,md(S0​,pj​)}，则$S_0$最终属于最近的类。
使用上面讨论的程序，易于分类的测试样本提供了额外的证据，以帮助对高度不确定性的测试样本进行分类。