基于模糊邻域判别指数的在线流组特征选择

徐久成，孙元豪+，韩子钦

(1.河南师范大学 计算机与信息工程学院，河南 新乡 453007；2.河南师范大学 智慧商务与物联网技术河南省工程实验室，河南 新乡 453007)

0 引 言

特征选择是一种常见的数据预处理技术[1，2]。传统的特征选择假定特征空间是不变的[3]，然而在实际情况中，特征往往随着时间逐个或逐组地获得，特征空间信息未知[4]。如何在流特征环境中进行高效的特征选择具有重要的实际应用价值。

根据特征组的原始结构信息，在线流特征选择可分为在线流单特征选择和在线流组特征选择[5，6]。在线流单特征选择方法对特征单独处理，忽略了特征流存在的组结构信息[7-10]。而对特征组执行特征选择比单独对特征执行特征选择效果更好[11]。Yu等[12]提出一种可扩展的流特征选择方法，可在群组和个体两个层面对特征组进行有效选择。Zhou等[5]考虑到流特征组内和组间的交互作用，并通过弹性网回归模型中的惩罚函数将变量的系数进行调整，选择有价值的变量，设计了一种新的群组流特征选择方法。然而，现有的在线流特征选择方法不能有效地处理模糊和不确定性环境下的任务。

近年来，基于模糊粗糙集的特征选择方法在处理具有模糊性和不确定性的分类问题中得到了广泛的应用[13-15]。Xu等[16]重新定义了模糊邻域关系并将其引入到条件熵中，提出了一种新的模糊邻域条件熵。Wang等[17]提出一种邻域判别指数，与香农熵具有相似的性质，可反映特征子集的区分能力。但这些基于模糊粗糙集理论的方法不能解决流环境下的特征选择问题。

因此，为了解决模糊性和不确定性背景下的流特征选择问题，本文提出一种基于模糊邻域判别指数的在线流组特征选择方法，并通过与5种流行算法的对比实验，论证了该方法的有效性。

1 基础知识

设OGDS= 为在线流组决策系统。其中U={x1，x2，…，xm} 为样本的论域集合，G={G1，G2，…，Gt} 为条件特征集合，t为时间序列，Gi={f1，f2，…，fn} 为G中的一组特征，D为决策特征集合，在t时刻特征组Gt流入特征空间，h为映射函数。

1.1 模糊邻域熵

令A⊆G为U上的一个条件特征子集，则属性A引出的一组模糊二元关系表示为RA，RA(x，y)=1-|xA-yA|，若RA同时满足：①自反性：RA(x，y)=1，∀x∈U；②对称性：RA(x，y)=RA(y，x)，∀x，y∈U。则称RA为U上的一组模糊相似关系。

定义1[16]设λ为模糊邻域半径，则对于∀x∈U，x关于A的参数化的模糊邻域信息粒定义为

(1)

关于A的模糊邻域熵定义为

(2)

定义2[16]假设D将样本集合U划分为l个等价类，U/D={D1，D2，…，Dl}，由D生成的模糊决策为FD={FD1T，FD2T，…，FDlT}，其中FDj为样本决策的模糊等价类，则x在Dj上的隶属度表示为

(3)

式中：j=1，2，…，l，|·|表示基数，|λA(x)∩Dj|表示样本对λA(x)的隶属度不大于Dj的个数。

1.2 邻域判别指数

(4)

邻域判别指数的计算基于邻域相似关系的基数，具有与香农熵及其变体相似的性质，是一种度量特征子集区分能力的有效方法[18]。

1.3 Lasso模型

Lasso模型是弹性网策略的一种特殊形式，令X为数据矩阵，ê为投影向量，则决策类向量表示为Y=XTê，设γ为调节正则化数目的参数，Lasso方法通过最小化以下目标函数来选择最佳的ê

(5)

2 模糊邻域判别指数的不确定性度量

本节首先定义了模糊邻域判别指数，然后提出了模糊邻域互判别指数和模糊对称不确定性的概念，在此基础上扩展了一些不确定性度量方法。

2.1 模糊邻域判别指数

定义4 给定OGDS= 为在线流组决策系统，其中U={x1，x2，…，xm}，设A⊆G，λA(x) 为x关于A的参数化的模糊邻域粒，则关于A的模糊邻域判别指数定义为

(6)

根据式(6)可知，模糊邻域判别指数通过模糊邻域粒的基数来计算，而式(2)中模糊邻域熵通过累加模糊邻域相似类的基数获得。因此，模糊邻域判别指数的计算复杂度略小于模糊邻域熵。

性质1 若A⊆B，则FNDIλ(A)≤FNDIλ(B)。

证明：令 (xi，xj)∈λB(x)，可得RB(xi，xj)≤λ，由A⊆B可得RA(xi，xj)≤λ，因此 (xi，xj)∈λA(x)，由模糊邻域粒的性质可知λB(x)⊆λA(x)，且|λB(x)|≤|λA(x)|。根据定义4可得FNDIλ(A)≤FNDIλ(B)。

性质1表明模糊邻域判别指数的大小随着特征组的增大单调递增。

定义5 设A，B⊆G，则A和B的模糊邻域互判别指数定义为

(7)

特别地，当B=D时，使用样本生成的模糊决策FD来计算特征与决策类的模糊邻域互判别指数，可以更充分地利用决策信息，进而更好地处理模糊性和不确定性数据。

模糊邻域互判别指数的值越大，表明该特征与决策类越相关，该特征就越重要。

性质2

FNMDIλ(A；B)=

FNDIλ(A)+FNDIλ(B)-FNDIλ(A，B)

证明

FNDIλ(A)+FNDIλ(B)-FNDIλ(A，B)

定义6 设A，B⊆G，则A和B的模糊对称不确定性定义为

(8)

模糊邻域互判别指数和模糊对称不确定性都可以用于评价相关特征的重要性，利用两种度量标准有利于选择更佳的特征子集，提升算法的性能。

2.2 基于不确定性度量的在线流组特征选择

接下来将在线流组特征选择分为组内特征选择和组间特征选择两部分，并扩展了一些不确定性度量方法。首先计算特征的重要度在组内选择具有强近似能力的特征流入特征空间，然后根据交互增益和对比度选择具有交互作用的特征。

2.2.1 组内特征选择

定义7 给定OGDS= 为一个在线流组决策系统，设A⊆Gt，a∈A，则特征a关于决策D的重要度定义为

Sig(a，A，D)=

FNMDIλ(A；D)-FNMDIλ(A-{a}；D)

(9)

定理1 若Sig(a，A，D)>0，则称特征a是重要的，否则称特征a是不重要的。

证明：当Sig(a，A，D)>0时，由式(9)可得FNMDIλ(A；D)>FNMDIλ(A-{a}；D)，这表明去掉特征a导致模糊邻域互判别指数的值变小，特征组提供的近似能力变弱，因此特征a是重要的。显然，当不满足该条件时，特征a是不重要的。

通过将式(9)应用到组内特征选择，可以遍历特征组Gi中的所有特征，选择重要的特征，并将选择后的特征组S′t流入特征空间。

2.2.2 组间特征选择

定义8 给定OGDS= 为一个在线流组决策系统，设f为S′t中的一个特征，St-1为t-1时刻已选择的特征集合，则特征f关于St-1的交互增益定义为

IGλ(f，St-1)=FSUλ(f，St-1；D)-

FSUλ(f；D)-FSUλ(St-1；D)

(10)

定理2 若IGλ(f，St-1)>0，则特征f具有交互作用。

证明：当IGλ(f，St-1)>0时，由式(10)可得FSUλ(f，St-1；D)>FSUλ(f；D)+FSUλ(St-1；D)，这表明f和St-1在一起所提供的信息大于二者分开所提供信息之和，因此特征f具有交互作用。

如果特征f具有交互作用，那么需进一步对该特征进行分析。

定义9 给定OGDS= 为一个在线流组决策系统，设f1为S′t中有交互作用的特征，f2为St-1中的特征，则特征f2关于f1的对比度定义为

Cλ(f1，f2)=FSUλ(f1，D)-FSUλ(f2；D)

(11)

定理3 若Cλ(f1，f2)>0，则特征f1是重要的，特征f2是冗余的。

证明：定义9衡量了新到达特征与已选特征集合的相关性。当Cλ(f1，f2)>0时，由式(11)可得FSUλ(f1；D)>FSUλ(f2；D)，这表明特征f1所提供的信息是大于特征f2所提供的信息的，因此特征f1是重要的，特征f2是冗余的。

当没有新特征流入时，使用Lasso方法对所有选定的特征进行重新评估，丢弃不相关的特征。

3 在线流组特征选择算法

基于上述理论，本文提出了一种基于模糊邻域判别指数的在线流组特征选择(online group streaming feature selection based on fuzzy neighborhood discrimination index，OGSFS-FNDI) 算法。算法描述如下：

算法1：OGSFS-FNDI

输入：OGDS=，模糊邻域半径λ，组规模g；

输出：已选特征子集S.

(1)初始化:S=∅;

(2)在t时刻流入新的特征组Gt;

(3)/*组内特征选择*/

(4)fori=1 to|Gt|

(5) 计算fi的重要度Sig(fi,Gt,D);

(6) ifSig(fi,Gt,D)>0

(7) LetS′t=S′t∪{fi};

(8) end if

(9)end for

(10)/*组间特征选择*/

(11)forj=1 to|S′t|

(12) 计算fj的交互增益IGλ(fj,St-1);

(13) ifIGλ(fj,St-1)>0

(14) fork=1 to|St-1|

(15) 计算fj和fk的对比度Cλ(fj,fk);

(16) ifCλ(fj,fk)>0

(17) LetS=S∪{fj};S=S-{fk};

(18) end if

(19) end for

(20) end if

(21)end for

(22)直到没有Gt流入,使用Lasso选择特征子集S;

(23)returnS.

在算法1中，OGSFS-FNDI算法的时间复杂度由步骤(11)的循环决定，设组内特征选择阶段选择的特征个数为|S′t|，t-1时刻已选择的特征个数为|St-1|，样本个数为m。步骤(15)的时间复杂度在最坏情况下为O(m2)，因此，OGSFS-FNDI算法的时间复杂度在最坏情况下为O(m2×|S′t|×|St-1|)。显然|S′t|和|St-1|的值远小于特征维度|G|，可见OGSFS-FNDI算法选择最佳特征子集的效率较高。

4 实验及结果分析

为了验证OGSFS-FNDI算法的有效性，实验选取8个公共数据集，包括3个UCI数据集(Wpbc、Sonar、Heart)和5个DNA微阵列数据集(Colon、DLBCL、Lymphoma、Breast、MLL)。上述数据集可从http：//arc-hive.ics.uci.edu/ml/index.php和http：//csse.sz u.edu.cn/staff/zhuzx免费下载，表1给出相关数据集的详细信息。

表1 数据集描述

本文实验均在Windows 10 PC，Intel Core i5-3470 CPU@3.20 GHz，4.0 GB RAM环境下进行，并使用Matlab2016a实现和完成所有对比实验。为了减少不同量纲对实验结果的影响，通过以下公式对数据集进行归一化

F(xi)=(xi-xmin)/(xmax-xmin)

(12)

经过预处理操作，数据被归一化到[0，1]区间。借鉴文献[5]中的实验设置，本节选取KNN(k=3)和CART分类器对特征子集进行评估，并将分类准确率和选择特征个数作为评价指标，分析了OGSFS-FNDI算法和对比算法在相关数据集上的分类性能。

本节采用十折交叉验证以测试算法分类性能的准确性，每个数据集被随机分成10份，轮流将其中9份作为训练数据集，另外一份作为测试数据集，取10次分类准确率的平均值作为最终的结果。所有的对比算法都基于相同的设计方法。

4.1 参数分析

OGSFS-FNDI算法中有两个参数，模糊邻域半径λ用于调节模糊邻域的大小，组规模g用于控制在线流组特征选择的特征组大小。为了分析两个参数的取值对算法的影响，本节将λ的值设置为0.1到1，步长为0.1，并根据文献[5]的组规模，将g的值设置为50、100、200、400、800，这个区间设置针对高维数据集是有效的，但是面对低维数据集时并不能发挥划分特征组的作用，因此对于低维数据集将g的值设置为5、10、20、30、60，这更有利于模拟实际工作中特征流的组划分情况。本节重点讨论了不同参数对OGSFS-FNDI算法在分类准确率方面的影响，使用KNN和CART分类器得到的分类准确率随参数变化的曲面图大致相似，因此本文仅列出了使用KNN分类器的情况。

图1呈现了所提算法在3个低维数据集上的分类准确率随参数的变化曲面。由图1可知，参数的变化会对不同的数据集产生不同程度的影响。对于Wpbc和Sonar数据集，当λ的值大于0.4时分类性能整体趋势较为平稳，在大多数参数上均达到了较高的分类准确率，由于数据集的特征维度较低，此时g的值对其分类性能的影响并不明显。而对于Heart数据集，分类性能随着参数的变化呈现不规律性，但整体的分类准确率仍保持在一个稳定的区间内。

图1 3个低维数据集在不同参数下分类准确率的变化曲面

图2为OGSFS-FNDI算法在5个高维数据集上的分类准确率随参数的变化曲面。观测图2，模糊邻域半径和组规模的大小在DNA微阵列数据集上更能呈现出规律性。对于Colon、DLBCL和Lymphoma数据集，算法的分类性能随着参数变化的趋势大致相同，随着λ的增大分类准确率也呈现上升的状态，尤其是当λ的值大于0.4时分类准确率具有明显的提升，且随着g的增大分类准确率同时也在增加。在Breast和MLL数据集上，当λ的值小于0.6时的分类准确率整体呈现较低的水平，在λ大于0.6且g的值较大时达到分类精度的最优值。这表明由于DNA微阵列数据集的特征维数较高，数据具有模糊性和不确定性，模糊邻域判别指数作为一种有效的度量方法，可以有效地考虑到特征之间的相关性，而使用较大的模糊邻域半径和组规模往往可以充分利用特征组的分类信息，从而提高特征子集的强近似能力。

图2 5个高维数据集在不同参数下分类准确率的变化曲面

总的来说，OGSFS-FNDI算法可以在大部分数据集上找到最优的参数以达到较高的分类准确率，但对于不同的数据集所适用的参数是不同的。

4.2 实验对比分析

为了评价算法的有效性，本节选择了目前较流行的5种算法与OGSFS-FNDI算法进行比较，其中包括两种在线流组特征选择算法(OGSFS-FI[5]、Group-SAOLA[12])，两种在线流单特征选择算法(SFS-FI[7]、K-OFSD[8])和一种基于模糊邻域条件熵的特征选择算法(FNCE[16])。对比算法的参数设置均与原论文描述一致，且下文呈现的数据均为算法所达到的最优值。接下来分析了算法在分类准确率和选择特征个数方面的性能对比。

表2和表3分别呈现了对比算法在KNN和CART分类器上取得的分类准确率，加粗字体表示某一算法在该数据集上取得最佳分类准确率，最后一行列出了算法在所有数据集上的平均准确率。

表2 6种算法在KNN分类器上的分类准确率对比

表3 6种算法在CART分类器上的分类准确率对比

由表2和表3可见，基于KNN和CART分类器，OGSFS-FNDI算法在Wpbc、Sonar、Heart、Lymphoma数据集上的表现均优于其它5种对比算法，且在8个数据集上分类准确率的平均值均排名第一。尽管OGSFS-FI和Group-SAOLA算法都可以处理在线流组特征选择问题，但其在两个分类器上的分类准确率都低于本文所提算法。K-OFSD算法与本文所提算法在分类准确率方面保持在同一水平，且在处理DLBCL、MLL这类高维类不平衡数据集时该算法可以实现更高的分类准确率。SFS-FI算法具有最差的分类性能，且K-OFSD和SFS-FI算法仅能在单特征层面进行在线流特征选择。FNCE算法整体的分类性能较差，且只能处理静态的特征选择。OGSFS-FNDI算法在高维数据集上的分类准确率明显高于其它对比算法，这是因为该算法基于粗糙集理论进行推广，在处理DNA微阵列数据集这类不确定性数据时有着明显的优势。同时，算法还考虑到了数据的模糊概念，使用参数化的模糊邻域信息粒构建隶属度函数，实验结果表明该算法对具有模糊性和不确定性数据的处理有较好的效果。

为了更直观地展示OGSFS-FNDI算法的有效性，本节绘制了盒型图来描述对比算法的分类准确率之间的离散分布差异，图3和图4指出了所有算法在KNN和CART分类器上所获得分类准确率的分布情况，盒型图中间的横线表示中位数，“+”表示离群的异常值。

图3 6种算法在KNN分类器上的盒型图对比

图4 6种算法在CART分类器上的盒型图对比

由图3和图4可知，OGSFS-FNDI算法在两个分类器上分类准确率的平均性能(中位数)都是最强的。在KNN和CART分类器上，算法在上四分位数和下四分位数的多数集中在分类准确率较高的区间，且并未出现异常值。对比算法的分类准确率表现较差，中位线所在水平均明显低于所提算法，且其分布并不稳定。Group-SAOLA和SFS-FI算法在整体上处于较低水平；OGSFS-FI和FNCE算法呈现的数值区间较大；而K-OFSD算法在CART分类器上出现了离群的异常值，这表明对比算法虽然在部分数据集上分类性能较好，但其表现并不稳定。由此可得，OGSFS-FNDI算法的分类性能和其它5种算法相比更为稳定。

表4描述了6种算法在8个数据集上选择的特征个数。观察表4发现，OGSFS-FNDI算法在8个数据集上能够实现特征约简的目的，但在所有的对比算法中表现并未达到最优。尽管Group-SAOLA和SFS-FI算法在选择特征个数上体现了很大的优势，但通过表2和表3可见其分类精度明显低于其它算法，这表明在特征选择过程中丢失了较为重要的特征信息。

表4 6种算法在8个数据集上选择的特征个数

与OGSFS-FNDI算法相比，Group-SAOLA和SFS-FI算法的时间复杂度分别为O(|St-1|×|G|) 和O(m2)，尽管其表现较优，但结合实验结果可知其分类准确率较低。此外，K-OFSD和FNCE算法的时间复杂度均为O(m2×|G|)，而OGSFS-FI算法的时间复杂度为O(k3+k2×|St-1|)，其中k为算法调用弹性网的次数，时间复杂度较高。根据实验结果可知，OGSFS-FNDI算法最终选择的特征子集很小，即所提算法在实际应用中的时间复杂度远低于最坏情况。因此，与其它5种特征选择算法相比，本文算法在时间复杂度上的表现较优。

综上所述，本文所提的OGSFS-FNDI算法能够在选择较少特征个数的同时呈现出较优且稳定的分类性能。

5 结束语

针对大多数在线流组特征选择方法无法处理模糊性和不确定性数据的问题，本文提出了一种基于模糊邻域判别指数的在线流组特征选择算法。该算法基于模糊邻域判别指数扩展了相关的不确定性度量，同时使用组内特征选择和组间特征选择两种策略，以在线的方式选择能够提高分类性能的特征。通过一系列实验对比及分析，验证了所提算法可以有效且稳定地选择最佳特征子集。虽然OGSFS-FNDI算法在大部分数据集上达到更高的分类精度，但穷举法寻找最佳参数的方式效率较低，因此未来的工作将重点研究自动寻找最优参数的在线流组特征选择方法。