基于改进最大相关最小冗余的选择性集成分类器①

吴倩楠 颜学峰

(华东理工大学 能源化工过程智能制造教育部重点实验室 上海 200237)

0 引言

分类是机器学习的核心之一,集成学习在解决分类问题中发挥了重要作用,已被推广到对象识别[1]、对象跟踪[2]和对象检测[3]等领域。其基本思想是根据一定的规则组合若干个同质的基分类器,以获得一个泛化能力强的分类器。然而,当基分类器数量增多时,出现冗余基分类器的可能性提高,进而增加计算复杂度、削弱分类速度和性能。为此,文献[4]提出了选择性集成的方法,从原始基分类器中进行选择之后再集成,以更少的存储消耗和更短的运行时间收获比集成学习更优的结果。相较于集成学习,选择性集成因其较强的泛化性能以及较高的运行效率在各领域受到了越来越多的关注。

在选择性集成中,基分类器的准确性与差异性是影响集成性能的2 个重要因素,二者又互相矛盾[5]。构建可靠性高的选择性集成分类器取决于如何从初始基分类器集合中搜索出一个平衡了准确性和差异性的最优子集。

以选择性集成在寻找最佳子集过程中采用的搜索策略为根据,可将选择性集成分类器划分成基于聚类、优化、排序的分类器。基于聚类的方法包括2个主要步骤:第1 步采用聚类算法将基分类器集合划分为多个聚簇,同一簇中的各个成员有较强的相关性,不同簇之间差异性较强。分层聚类[6]、模糊聚类[7]、近邻传播[8]等已被广泛应用于此。第2 步修剪各簇以获得集成子集[9]。基于优化的方法首先为各基分类器随机分配一个权重,然后利用优化算法将权重向量演化为最优解,最后舍弃权重低于预定阈值的基分类器。目前已有多名学者采用萤火虫算法[10]、蚁群算法[11]、粒子群算法[12]等来演化最优权重向量。基于排序的方法首先对基分类器进行排名,然后按照排名选择满足条件的基分类器。此类方法的关键在于选择对基分类器性能排序的标准。文献[13]采用加权调和公式将多样性和准确性有效结合。文献[14]定义了一种度量函数,分别利用相关熵和距离方差作为准确性和差异性度量,并在目标函数中加入正则化因子。文献[15]采用特征选择中的最大相关最大互补法衡量基分类器性能。

以上策略中,基于聚类的算法受聚类算法不稳定性的影响较大;基于优化的方法中,使用启发式搜索算法难以找到全局最优,且启发式搜索时间复杂度高;相对而言,基于排序的方法最简单。本文构建了一种基于排序的选择性集成分类器,该分类器将特征选择的思想和方法扩展到基分类器的选择上,以改进的最大相关最小冗余准则为核心进行最优基分类器子集的搜索,保障了分类的准确性和实用性。

1 最大相关最小冗余准则

最大相关最小冗余算法(maximum relevance and minimum redundancy,mRMR)是用于特征选择的经典算法,该算法首先计算候选特征与目标类别间的互信息(相关项),然后计算候选特征与已选特征间的平均互信息(冗余项),通过相关项减去冗余项得到候选特征的mRMR 分数,然后从所有待选特征中选择分数最高的加入已选子集[16]。

令D=[d1,d2,…,dn]T为给定样本集,每个样本由一个p 维向量构成,其中的每个元素称为该样本的一个特征,进而di=。给定特征集F={f1,f2,…,fp},S 为已选特征子集;fi∈S 为已选特征,fj∈F -S 为待选特征;l 为类别;I(·) 是互信息。根据mRMR 的思想,fj的mRMR分数为

所选择的第m 个加入子集S 的特征应满足:

2 ImRMRSEC

本文构建了一种基于改进最大相关最小冗余算法的选择性集成分类器(improved mRMR-based selective ensemble classifier,ImRMRSEC),首先利用Bootstrap 采样得到不同训练集并训练一组基分类器,然后基于改进mRMR 选择部分基分类器,最后采用相对多数投票法集成。在选择时,将各基分类器对验证集的预测结果视为特征选择中的一个个特征,然后计算特征与验证集实际类别的相关性及特征间的冗余度,选出最佳基分类器子集。对于mRMR 存在的问题,本文在相关性度量、冗余性度量及搜索方式上作了改进。为方便描述,本节中将用“特征”指代各基分类器对样本的预测类别。

2.1 相关性度量

传统mRMR 中的相关性测度采用互信息,在计算互信息时需要同质化变量的量纲及单位,且其值不是归一化的。为设计一种通用性强的mRMR 算法,首先需要避免互信息的固有弊端,Pearson 系数[17]、距离协方差[18]、Fisher 指数[19]等也可用于度量相关性,但各有优缺点。其中Fisher 指数简单但不能捕获变量间的非线性依赖程度,Pearson 相关系数只适用于呈正态分布的变量且只能衡量线性相关程度,距离协方差不是归一化的系数。而距离相关系数(distance correlation coefficient,DCC)是一个好的选择。DCC 通过两变量间的联合特征函数与变量边际特征函数的差值刻画“距离”。其不需要任何模型及变量假设,能评估不同维数的变量间的线性及非线性相关性,且是归一化的系数,具有较好的普适性[20]。

两变量X、Y 间的距离相关系数定义如下[20]:

式中,dcor(·) 为距离相关系数,dcov(·) 为距离协方差,其定义为

其中,f(·) 是给定变量的特征函数;ω 是权重函数,其大小为

按以上方式计算出的是总体距离相关系数,实际应用时,往往需要计算两两样本之间的距离相关系数,为此,对于n 个样本量的成对随机变量X 和Y,本文按如下方式计算距离相关系数。

步骤1计算各变量的成对距离矩阵a 和b:

其中,akl为矩阵a 中第k 行l 列的元素,bkl同理。

步骤2对成对距离矩阵进行中心化处理,得到中心距离矩阵A 和B,公式为

步骤3计算距离协方差dcov(X,Y)、距离方差dcov(X,X)、dcov(Y,Y)。

步骤4将式(10)～(12)带入式(3),求出两变量X 和Y 的距离相关系数dcor(X,Y)。

DCC 相较经典相关系数有以下优势。

(1) 不需要模型及变量假设

经典相关系数的计算依赖两变量间协方差与各自的方差。概率论中指出,方差存在是协方差存在的必要条件,而随机变量的方差未必存在。DCC 的定义只涉及变量的特征函数,任意随机变量都有特征函数,因此总可以计算DCC。

(2) 两变量维数不需要相同

从本质上看,协方差的计算过程是求向量内积,DCC 是矩阵内积。所以经典相关系数要求两变量维数必须相同,DCC 定义在任意维数的变量间。

(3) 可衡量线性和非线性相关程度

DCC 定义中的权重函数没有选择可积函数。在X 和Y 数值较小时,可积函数会使DCC 退化成经典相关系数,从而失去衡量非线性相关程度的能力。

2.2 冗余性度量

文献[21]强调,可将冗余信息细分为相关冗余及无关冗余信息。相关冗余指特征携带的相同目标类别信息,无关冗余指特征中共同携带但与类别无关的信息。令f1表示已选特征,f2、f3表示待选特征,l 表示目标类别。利用Venn 图来简化特征携带的信息情况及特征之间的关系,如图1 所示。

图1 特征间关系Venn 图(ri 等量)

对于f1与f2,r2是相关冗余,r3为无关冗余。对于图1 给出的示例,在选定f1的情况下,f2中携带3 份新的类别信息(3 ×r5),f3携带1 份(r7)。利用传统mRMR 算法,f2、f3的mRMR 分数为

但是,r3对分类无帮助,不应抵消f2与l 之间的相关信息。换言之,由于无关冗余的存在,算法忽略了f1所不具备而f2携带的目标类别信息,从而根据mRMR 分数,错误地选择f3加入子集。

为消除无关冗余的影响,本文引入施密特正交化(Gram-Schmidt orthogonalization,GSO)算法,用原特征的等价标准正交向量替代原向量。

GSO 是矩阵论中的经典算法之一。对于第1节中给出的特征集F,其对应的正交特征集为O={o1,…,op}。在GSO 过程中,oi由以下方式获得:

式(14)表明,在等价正交向量中,fi在其他所有特征上的投影分量都会被抹去,而这些投影分量对应冗余信息。此外,由于GSO 过程是对自变量进行直角变换,所以不会破坏原始特征的分布假设[22]。

根据GSO 过程,设Sm-1={f1,f2,…,fm-1} 是已选特征集,下一个被选特征为fm,则Sm={f1,f2,…,fm-1,fm}。利用GSO 求Sm等价标准正交向量Em的过程如下。

步骤1正交化。利用式(13)、式(14)构造Sm的等价正交向量组Om={o1,…,om}。

步骤2标准化。将Om中各元素单位化,得到满足要求的标准正交向量组Em={e1,…,em}。

经过GSO,待选特征的等价标准正交向量相对于已选特征已不含冗余,所以使用特征的等价标准正交向量仅需考虑等价向量与目标类别的相关性。因此,选择加入子集的特征应满足:

所选特征子集的性能指标函数为

2.3 搜索方式

传统mRMR 算法在搜索下一个最佳特征时采用序列前向选择(sequential forward selection,SFS)。SFS 初始时将已选特征子集设为空集,每次迭代时从候选特征中选择一个使性能指标取得最大值的特征加入已选子集,直到所选特征个数等于指定特征个数[23]。然而该策略只能获得局部最优,且不能剔除特征,后续的搜索过度依赖已选特征。

为了避免SFS 的弊端,本文引入序列浮动前向选择(sequential floating forward selection,SFFS)。SFFS 在每次迭代中主要由前向选择和特征回溯组成。前向选择即标准SFS 过程;特征回溯将已选子集中性能较差的特征剔除,使后续搜索到的更优特征能被选择[24]。算法过程如下。

(1) 初始化已选特征子集S=Ø;目标特征数量s;使用标准SFS 从候选特征子集中搜索使J(S1) 最大的f1,此时已选特征个数k=1;while k

(2) 前向选择:采用标准SFS 从候选子集中选择fk使得J(Sk) 取最大值;

(3) 特征回溯:遍历Sk,从中依次去掉一个特征得到,若存在某个特征使≥J(Sk-1),则将其剔除,继续遍历,重复上述步骤;否则,k=k +1,并转到步骤(2)。end

2.4 ImRMRSEC 描述

输入:样本数据集D,其中特征F∈Rn×p,类别l∈Rn×l;基分类器个数N;集成规模s

输出:集成分类器预测值

步骤1基分类器生成

(1) 基于训练集Dtrain,利用Bootstrap 采样得到N 个训练集,然后在这一组新的训练集上训练基分类器,记为C={c1,c2,…,cN};

(2) 应用步骤(1)中的集合C 来分类验证集数据,记分类结果为PV={pv1,pv2,…,pvN}。

步骤2基分类器选择

(3) 设已选基分类器集为S,并令S=Ø;

(4) 基于集合PV,利用式(3)计算出pvi与目标类别之间的相关性,记录最高分数对应的分类器编号k,将ck移动到S 中。此时,S1={ck},已选基分类器个数m=1;C1=C -ck;

(5) 利用SFFS 依次选出最佳基分类器:while m

1) 使用标准SFS 从集合Cm-1里选取符合式(17)的基分类器,并记录下此时的性能指标值;

2) 遍历Sm,从中逐项剔除一个子集成员得,若始终存在,则返回1),并令m=m +1,判断是否停止搜索,否则执行3);

步骤3基分类器集成

(6) 基于集合S 中的基分类器预测测试集样本类别,然后运用相对多数投票法集成各预测结果。

2.5 算法复杂度分析

(1) 生成阶段

假设训练单个基分类器的时间复杂度为Tc,则生成阶段的时间复杂度为NTc;

(2) 选择阶段

选择阶段的时间复杂度主要由4 部分组成,即DCC 的计算、排序过程、GSO 和SFFS。

1) DCC:计算两样本量为n 的变量间DCC 的时间复杂度为O(n2);对于N 个数据,快速排序法的时间复杂度为O(N log2N)。所以步骤(4)的时间复杂度为

2) GSO:构造N 个n 维向量的等价标准正交向量所需的时间复杂度为O((N -1)n);

3) SFFS:前向选择的时间复杂度为O(N),特征回溯遍历整个已选集合S,由于| S|≤s,故特征回溯的时间复杂度上界可近似为O(s)[25]。

综合1)、2)、3)及迭代规则,在挑选得第m+1个基分类器时,算法的时间复杂度为

由于m <

进而,步骤(5)的时间复杂度为

(3) 集成阶段

相对多数投票法的时间复杂度为O(Ns)。

综上,ImRMRSEC 算法的时间复杂度为

进一步,log2s >1,s 于log2N 及n 来说是一个相对小的数,式(23)可进一步简化为

3 实验分析

3.1 实验方法与数据

为证明文章中构建的分类器的性能,将其与集成所有基分类器(ALL)、基于排序(MRMCEP[15])、基于聚类(MCAS[7])、基于优化(BGASEC[4])的选择性集成分类器进行比较。实验数据集为10 个来自于UCI 机器学习数据库的数据集,具体参数如表1所示。

表1 实验数据集

对于每一个数据集,首先利用MinMax 归一化将所有数据映射到[0,1]以降低计算复杂度。实验中各训练100 个支持向量机(support vector machine,SVM)、K 近邻(k-nearest neighbor,KNN,取k=5)、误差反向传播神经网络(error back propagation neural network,BP)和C4.5 决策树作为基分类器,除基于优化的方法自适应寻找最优集成基分类器个数外,其他方法的集成规模都定为10,将本文所提方法与前述4 种方法进行比较。

3.2 分类准确率比较

为了提高结果的可靠度,实验中采用十折交叉验证法获得分类准确率,并利用成对t 检验求出置信度为0.95 的置信区间作为最终分类准确率结果。

表2 给出了基分类器为SVM 时各方法的分类结果,ImRMRSEC 的准确率在7 个数据集中达到最高,剩余3 个数据集中为次高,平均准确率最高。表3中展示的为基分类器为BP 模型时的准确率,所提出的算法实现了在8 个数据集中准确率最高、1个数据集中精度次高,其中在Diabetes 数据集中预测误差略高,但平均精度仍最高。同时,在部分数据集上,集成所有基分类器(ALL)的准确率略高于选择性集成分类器。这是由于算法不可避免地在该数据集上选择了高冗余基分类器而忽视了高准确率基分类器带来的偶然偏差,但从平均准确率来看,集成所有基分类器的平均精度仍为最低。表4 中的结果是在基分类器为5-NN 时得到的,在这一类模型中ImRMRSEC 的准确率在8 个数据集中最高,其中,在Balance Scale 和Ionosphere 数据集上的准确率与基于聚类的方法得到的准确率相同,但其置信区间更宽。表5 给出了基分类器取C4.5 决策树时的分类情况,ImRMRSEC 仅实现了在6 个数据集中精度最高,但平均精度依然最高。从平均准确率来看,本文所构建的分类器胜过另外4 个对照组。计算4 种基分类器上平均准确率的总均值,ImRMRSEC 相较于ALL、MRMCEP、MCAS、BGASEC 分别有12.63%、7.14%、3.65%、6.22%的提高。

表2 基分类器为SVM 时各方法分类准确率及置信度为0.95 的置信区间

表3 基分类器为BP 时各方法分类准确率及置信度为0.95 的置信区间

表6～表9 分别给出了基分类器为SVM、BP 神经网络、5-NN 和C4.5 决策树时,5 种方法在所有数据集上的误差比较。表格中,r 表示单元格所在列对应方法的误差几何平均值与所在行对应方法的误差几何平均值的比率;s 给出的是单元格所在列对应方法相较于所在行对应方法的win/tie/los 统计。综合r、s,本文对比的5 种方法的性能排序依次为ImRMRSEC、MCAS、BGASEC、MRMCEP、ALL。同时,从表格中可见,ImRMRSEC 与4 种对比方法的r值均小于1,也可说明ImRMRSEC 的分类性能更优。

表4 基分类器为5-NN 时各方法分类准确率及置信度为0.95 的置信区间

(续表4)

表5 基分类器为C4.5 决策树时各方法分类准确率及置信度为0.95 的置信区间

表6 基分类器为SVM 时各方法误差比较

表7 基分类器为BP 时各方法误差比较

表8 基分类器为5-NN 时各方法误差比较

表9 基分类器为C4.5 决策树时各方法误差比较

3.3 差异性比较

为了检验所构建分类器与对比算法是否具有显著差异,引入Friedman 检验和Nemenyi 后验。Friedman 检验首先计算每种方法在所有数据集上的平均序值,然后比较各平均序值,两种方法的平均序值相同时其性能相同。

表10 给出了5 种方法的平均序值及4 种基分类器下总平均序值的均值。可以看出,5 种方法的平均序值各不相同,即各种方法的性能显著不同。

利用Nemenyi 后验来进一步区分各方法。Nemenyi 后验指出,两种方法的平均序值之差大于临界值CD 时其具有显著差异。临界值为

其中,k=5 为要检验的方法数,N=10 为数据集个数,α=0.05,查“The Studentized Range Statistic”表得q0.05=1.860,从而CD=1.315。

由表10 可知,ImRMRSEC 与ALL、MRMCEP、MCAS、BGASEC 的平均序值之差分别为2.98、1.9、1.15、1.67,除了与MCAS 比,均大于CD,且与MCAS 的差值接近临界值,因此本文所构建的分类器与其他几种分类器之间在统计意义上有显著差别。

3.4 运行时间比较

由于实验中选取的对照算法与本文所构建的基分类器仅在基分类器的选择阶段不同,所以在对比算法耗费时长时将重点放在选择阶段。同时,实验过程中不再采用交叉验证,而是选择70%样本做训练集,30%样本做测试集,记录在不同基分类器模型下各方法在各数据集上单次实验所耗时间,然后求出各方法在4 种基分类器模型下的平均运行时间,结果如表11 所示。

由表11 可以看出,BGASEC 耗费时间最多,这是由于遗传算法在求解复杂问题时的平均时间复杂度是问题规模的指数次方;MRMCEP 所耗费时间最少,ImRMRSEC 次之,二者差异的主要原因在于Im-RMRSEC 在搜索方式上选择了SFFS,增加了一个特征回溯环节。相较之下,ImRMRSEC 增加了时间复杂度,但分类准确率也相应上升了。

表11 各方法运行时间比较(单位:s)

4 结论

本文构建了一种基于改进mRMR 的选择性集成分类器,称为ImRMRSEC。与单个最佳模型或集成所有基分类器的方法相比,选择性集成分类器准确率更高、耗费时间更少。本文所提方法与最大相关最小冗余准则下的其他方法相比,主要优势在于:引入等价的正交向量可排除无关冗余的影响,同时序列浮动前向选择方法的引入消除了前向选择只能添加不能替换的弊端,二者都有益于提升集成子集质量;此外,距离相关系数对基分类器信息的捕获是全面的,故而所提方法在大多数实验中优于其他方法,并在多类模型的集成实验中被证明。