基于邻域互信息的三支特征选择

卓永泰，董又铭，高 灿

1.深圳大学 计算机与软件学院，广东 深圳 518060

2.广东省智能信息处理重点实验室（深圳大学），广东 深圳 518060

现实问题数据，如文本语音或图像，通常包含较多的特征，然而过多的特征将导致计算速度慢、可解释性差和模型过拟合等问题。特征选择能在保持数据的分类能力不变的条件下有效去除数据的冗余和不相关特征，因此成为机器学习、模式识别和数据挖掘的重要预处理过程[1]。

互信息是一种有效的不确定性度量方法，其能够依据变量的概率分布，来衡量变量间互相依赖的程度。传统互信息主要适用于度量离散型随机变量，而现实中往往存在大量连续型变量，需对连续型变量离散化，然而离散化将造成原始数据的信息损失。针对该问题，Hu等[2]提出了邻域互信息概念，能直接处理连续型特征。Liu等[3]将邻域互信息与粒子群优化算法结合，获得了更好的特征选择效果。Lin等[4]在一般邻域互信息的基础上拓展了三种适用于多标签学习的邻域互信息。Wang等[5]基于邻域互信息，提出了一种对标签缺失数据进行多标签特征选择的算法。Liu等[6]提出了局部邻域互信息概念。Sun等[7]将多标签ReliefF和邻域互信息结合，提高了特征选择算法的稳定性和预测精度。

虽然以上方法利用邻域互信息获得了较好的特征选择效果，但均采用了贪婪策略。贪婪策略并不能保证找到一个最小的特征子集，其搜索过程有可能向着更大的特征子集的方向发展。三支决策理论[8-9]是一种处理不确定信息的有效方法，在不确定决策及近似推理中有着重要的应用。李娴等[10]将三支决策理论应用于图神经网络推荐算法，提高了推荐质量。胡峰等[11]将三支决策理论应用于不平衡数据过采样，有效解决了不平衡数据的二分类问题。本文将三支决策思想引入特征选择，以达到原始特征的邻域互信息为迭代终止条件，利用邻域互信息度量迭代，拓展生成三个具有差异性的特征子集，以保证特征选择有更大的机会选择到最优特征子集。同时对三个特征子集进行集成，构建了三支协同决策模型，以获得更好的分类学习效果。UCI实验结果显示了模型的有效性。

1 基本知识

1.1 互信息

假设离散随机变量为A={a1,a2,…,an}，记p(ai)为A=ai发生的概率，则A的信息熵为：

假设两离散随机变量为A={a1,a2,…,an}，B={b1,b2,…,bm}，记p( ai,bj)为A=ai,B=bj同时发生的概率，则A、B的联合熵为：

已知变量B的取值，A的条件熵为：

A和B的互信息为：

1.2 邻域粗糙集

给定样本集合U={ x1,x2,…,xn},xi∈RN,Δ表示为RN上的距离，通常使用欧氏距离。对于U上的任意样本xi，其δ邻域定义为：

如δ()xi中的所有样本决策值都相同，则xi在δ邻域内一致，否则称为不一致样本。

给定邻域决策信息系统NDS=(U,C⋃D,δ)，假设决策特征D将U划分为m个等价类D1,D2,…,Dm，则决策类Dj相对于条件特征集合C的邻域下近似和上近似分别表示为：

则所有决策类的下近似和上近似分别为：

边界为：

由于NC()D=U，当决策特征D的下近似越大，边界越小，当前所选的特征子集S⊆C则可以更加精确地描述此分类任务。因此可将定义为决策特征D对特征子集S的依赖度，依赖度越大，说明特征子集S的描述能力越强。

1.3 邻域互信息

给定邻域决策信息系统NDS=(U,C⋃D,δ)，特征子集S的邻域熵表示为：

给定另一特征子集R，联合邻域熵表示为：

已知特征子集S、R的条件邻域熵表示为：

R、S的邻域互信息表示为：

2 基于邻域互信息的三支特征选择

首先阐述启发式邻域互信息特征选择策略存在的问题，其次描述利用三支决策的思想进行特征选择方法。

2.1 启发式特征选择

由于求取最小子集是NP难题，一般采用启发式搜索算法获取特征子集。文献[2]设计了MD策略，其启发式特征评价函数是：

其中，C为初始特征集合，S为已选择的特征子集，D为决策特征，f为一个候选特征。

特征选择的目的是在保持特征子集的描述能力的条件下，获取具有最少特征的特征子集。MD采用贪心策略即每一步添加一个使得Ψ最大的候选特征，使特征子集与类别的互信息尽量快速地增加，其搜索只能保证局部最优。选择的特征子集可能偏大且存在冗余，特征子集的质量难以保证。

2.2 基于三支决策的特征选择

为了尽量避免贪心策略带来的问题，使特征子集在整体上更优，本文提出了基于三支决策的特征选择策略。

在三支搜索中，一般每一层保持有3个特征子集，由它们分别生成排序前三的新特征子集，合计9个候选的特征子集。然后从这9个特征子集中再选择排序前三，并且约束它们不来源于同一分支，以此作为下一层的3个特征子集。三支特征选择最终将生成3个较优的特征子集。

特征选择并生成后继的方法如式：

其中，C为条件特征集合，i表示分支的序号，则Si表示第i个分支已选择的特征，fi表示第i分支的候选特征。

三支特征选择的思路如图1所示。图中的圆形结点表示一个特征子集。实线箭头指向的结点表示该特征子集将继续拓展，虚线箭头指向的结点表示该特征子集不拓展。结点G表示该特征子集已经达到了停止条件。

三支特征选择算法的具体描述如下：

算法1基于三支决策的特征选择

输入：邻域决策信息系统NDS=U,C⋃D,δ，分支的数目w=3。

输出：redlist-子集列表。

1.计算NMI( )

F;D，生成空列表Queue

2.从初始特征集F中选择NMI前三大的特征分别构成大小为1的3个特征子集，放入redlist

3.对redlist的尾部w个特征子集中的每一个特征子集S：

如果NMI(S;D)≥NMI(F;D)，转步骤3.1；否则，转步骤3.2

/*判断特征子集是否满足终止条件*/

3.1 将S移至redlist的头部，w=w-1；如果w为0，输出redlist

3.2 由S生成Ψ前三大的特征子集，放入Queue，将S从redlist中移除

4.从Queue中找到w个Ψ最大的不源自同一支的特征子集，放入redlist尾，清空Queue队列，转步骤3

算法首先从空集∅开始，选择NMI值前三大的特征构成大小为1的特征子集。其次测试当前各特征子集是否满足终止条件，如果满足条件则将该特征子集加入redlist；不满足的特征子集分别拓展其Ψ最大的3个特征，合计形成w×3个新的特征子集。然后从这些特征子集中选择Ψ最大的w个特征子集。为了保持差异性，算法约束w个特征子集不能来自同一个分支。算法不断迭代以上过程，以达到原始特征的邻域互信息为分支迭代终止条件，直到获得3个满足条件的特征子集。

设数据集有N个初始特征。在第k轮，一个特征子集已经选择了k个特征，计算剩余的N-k个特征的Ψ带来的时间复杂度为O( )N-k。那么在最坏情况下，即所有特征都被选取的情况下，一个特征子集的总复杂度为，3个特征子集的总复杂度近似为O(N2)。

在获得3个特征子集后，将3个特征子集分别构建同质学习器，形成三支协同决策模型，以获得更好的学习性能。

3 实验与结果

3.1 数据集和参数设置

实验选用了12个UCI数据集，具体信息如表1所示。其中，有6个连续型数据集，2个离散型数据集，4个混合型数据集。在“特征数”一列中，括号内的数值表示连续型特征的数量。在实验中，对连续特征进行归一化，离散特征则进行数值化预处理。有3个数据集包含有缺失值，对于连续型特征采用均值填充，离散型特征用众数补全。

表1 实验数据集Table 1 Experimental data sets

所有实验采用10次随机10折交叉验证方法，实验的平均结果作为数据集的最终性能。

根据文献[2]实验结果，基于邻域互信息的方法在邻域半径取值[0.1，0.2]时提取的特征子集较好，本实验邻域半径采用中间值0.15。因为NMI度量随着特征的添加不具备单调性，所以设置算法停止条件为：特征子集的NMI大于等于初始特征集合的NMI时。根据文献[12]的分析，NRS模型采用邻域半径0.125较优，因此实验中NRS模型采用的邻域半径参数为0.125。当最优重要度非正时，停止拓展，表示算法找到了目标的特征子集。

3.2 特征选择分析

在所选数据集上的特征提取结果如表2所示。在表2中，第2列表示原始数据集的特征数量，第3列表示NRS算法得到的特征子集的大小，第4列表示NMI-MD算法得到的特征子集的大小，第5列表示本文算法NMITWD得到的特征子集的大小，第6列NMI-TWD-Best表示本文算法得到的最小的特征子集的大小。第7列展示了NMI-TWD获得的3个特征子集，加粗部分表示存在差异的特征。

表2 NMI-MD和NMI-TWD特征提取的结果Table 2 Results of feature selection of NMI-MD and NMI-TWD

本文提出的NMI-TWD算法在2个数据集中获得了较NMI-MD更小的特征子集，在6个数据集中获得了较NRS更小的特征子集。anneal、segment、cardio、family、genus数据集的3个特征子集仅存在特征顺序上的差异。

3.3 算法性能对比分析

各算法所得特征子集分别利用KNN和SVM分类器进行实验。集成学习采用Stacking方法[13]，其元分类器采用LogisticRegression分类器（最大迭代次数10 000），LR将3个初级分类器输出的3组预测概率水平堆叠在一起，再与原样本的决策相结合作为新的样本进行学习。当初级分类器为SVM时，通过CalibratedClassifierCV将SVM的预测转化为概率形式，再交给元分类器学习。算法的性能取10次随机10折交叉验证的平均值。

在表3和表4中，第2列表示数据集不进行特征选择时的性能，第5至7列表示在指定分类器下三支特征选择获得的各特征子集的性能，第8列表示NMI-TWD算法获得的3个特征子集通过集成后的性能。各数据集上的最优性能加粗表示。另外，各方法在所选数据集上的平均性能在表格的“Avg”行显示。

表3 KNN分类器的分类准确率Table 3 Classification accuracy using KNN 单位：%

表4 SVM分类器的分类准确率Table 4 Classification accuracy using SVM 单位：%

从表3和表4可见，NMI-TWD获得了较NRS和MNIMD更好的分类性能。NMI-TWD基于三支决策的思想，利用邻域互信息生成了3个具有一定差异的特征子集。这3个特征子集独立来看，就已经与其他方法的特征子集的分类性能相近，甚至有所提高。而这3个具有差异性的特征子集，可以从不同角度描述数据的本质信息，对它们进行三支协同学习能够获得更好的性能。

NMI-TWD的准确率在anneal、segment、cardio、family、genus这5个数据集上较NMI-W1、NMI-W2、NMIW3上也有小幅提升。准确率的提升主要源于Stacking方法集成机制，其元分类器可以对初级分类器难以区分的决策做进一步的区分。

在KNN分类器下，NMI-TWD在所选的12个数据集中，有9个获得了最高的性能。其性能较其他三种方法平均提升约7个百分点。在8个数据集中，NMI-TWD至少获得了一个性能最优的特征子集。在SVM分类器下，NMI-TWD在10个数据集中获得了最高的性能，较其他三种方法平均提升约2.75个百分点。在6个数据集中，NMI-TWD至少获得了一个性能最优的特征子集。这说明了本文算法优于NRS和NMI-MD，显示了本文算法的有效性。

4 总结

本文将三支决策的思想引入基于邻域互信息的特征选择，在获得较优的特征子集的同时，通过集成学习进一步提升了分类性能。UCI数据集上的实验表明，本文方法在准确率方面，优于现有的邻域粗糙集和邻域互信息方法，说明了新方法的有效性。进一步将尝试研究新的连续特征重要性度量方法，同时对三支特征子集引入更好的多样性，以进一步提升三支特征选择的性能。