第42卷第1期2021年02月
长春工业大学学报
Journal of Changchun University of Technology
Vol.42No.1
Feb2021
D0I：10.15923/jki22-1382/t.2021.1.07
基于Catboost的特征选择算法
王丽，王涛*，肖巍，潘超
(长春工业大学计算机科学与工程学院，吉林长春130012)
摘要：应用Catboost构建树模型的分割指标作为特征选择度量标准，在原始前向搜索策略的基础上，结合两种度量标准计算综合加权值进行特征搜索。在UCI数据库中选择7个不同维度的标准数据集进行了测试，并与其他6种算法进行了对比分析。
关键词：特征选择；集成学习；梯度提升
中图分类号：TP18文献标志码:A文章编号：16741374(2021)01003406
A feature selection algorithm based on Catboost
WANG Li,WANG Tao*,XIAO Wei,PAN Chao
(School of Computer Science&Engineering,Changchun Universty of Technology,Changchun130012 ,China)
Abstract:The metrics for building tree in Catboost are taken as the standards of feature selection.The combined metrics based on the original forward search strategy are used to calculate the weighted valueforsearchingthefeatures．7di f erentdimensionalstandard data sets selected from the UCI databasearetested andthealgorithmiscomparedwithother6di f erentmethods．
Key words：feature selection；ensemble learning；gradient boosting.
o引言
特征选择是机器学习中的一个重要步骤，并广泛应用于各领域，在训练模型过程中，不相关的特征会干扰模型学习的正确性，而冗余的特征不会提供任何有用的信息，反而增加模型的复杂性。特征选择的任务是从高维原始特征空间中选出一组有效的特征子集［1］。特征选择方法通过搜索相关特征并移除不相关特征来寻最优特征子集，提高模型的处理性能，减少处理数据维度⑵。
特征选择方法分为对特征重要性进行排序和选择特征子集两种［］。前者是根据一些测量标准对特征进行排序，并相应地选择排在顶部的特征；后者使用评价指标对特征子集进行评价，并筛选关键特征。两种方法都可以使用基于过滤式或包裹式方法进行选择⑷。在过滤式特征选择中，使用一定的评价指标评估每个特征的质量，不考虑它对结果产生的影响。包裹式的特征选择则根据一个或一组分类器的结果来衡量每个特征的影响，与过滤式方法相比，包裹式方法的计算密度更
收稿日期：2020-09-20
基金项目：国家自然科学基金面上项目(1472049)吉林省科技发展计划技术攻关项目(0190302071GX)
作者简介：王丽(1994—)，女，汉族，吉林长春人，长春工业大学硕士研究生，主要从事人工智能与特征选择方向研究，E-mail：wangl_yx@foxmail.*通讯作者：王涛(1969—)女，汉族，吉林长春人，长春工业大学副教授，硕士，主要从事人工智能与特征选择方向研究,E-mail：wangtao690103@163 .
第1期王丽，等：基于Catboost的特征选择算法35
高，在预测结果方面更准确。但过滤式方法计算更快，结果准确性稍逊于包裹式方法［］。
一部分学者将特征选择划分出嵌入式方法，嵌入式方法将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行特征选择［］。
尽管在计算开销上嵌入式方法要比包裹式方法小，但在速度上仍然要比过滤式方法慢很多，并且特征选择的效果很大程度上依赖所选择的学习器叫
集成学习是解决机器学习问题的重要方法之一，集成学习的主要策略是将弱学习器集成为一个强学习器，在输入一组标记样本到弱学习器后，通过生成的模型为新的未标记样本做出预测。其中，弱分类器可以是任何类型的机器学习算法，例如决策树、线性回归模型等［］。集成学习在组合多个学习器过程中，单个学习器的误差可能会被其它学习器补偿，因此，模型整体的预测性能将优于单个学习器的预测性能。集成学习能够更好地解决特征选择问题，如Hakan等⑼提出的分类器集成方法应用于特征选择；Martin等［10］提出的使用应用过滤器集成解决多目标参数调整和特征选择问题；Omar等［11］提出的基于关联度、冗余度和依赖度准则的集成模糊特征选择；Ebrahimpour 等［12］集成了分级算法和相似性度量两种过滤式方法对微阵列数据集进行特征选择。
Catboost是Dorogush等［13］最近提出的一种新的集成学习算法，具有独特的对称树结构，通过计算叶子节点的值来构造决策树，在此过程中, Catboost对特征进行了量化的度量。
利用基于Catboost树模型的特点，以其对特征的重要性排序作为启发式策略，与搜索策略相结合，提出一种新型的特征选择方法CABFS。以Catboost为基本工具，完成以下工作：
1)基于Catboost构建用于求解特征选择问题的启发式策略；
2)提出了基于2种重要性度量的搜索策略；
3)提出了一个新特征选择方法CABFS；
4)通过实验对CABFS的性能做了全面分析与验证。
1背景知识
1.1特征选择
特征选择问题旨在从原始特征集合中选择能提供更多有效信息的特征，同时去除掉不相关特征以及冗余特征。
因此，可以使用二进制来表示特征问题中的解决方案。在这种条件下，解决方案中的每个维度采用1(选定)或0(未选中)来表示在原始特征集合中选择或不选择相应的特征。特征选择过程可以表示为
Fitness=min a^R(D)+0
R M
犖］(1)式中：Y r CD)—
—分类器的分类误差率；
R I——选择的特征数量；
犖——原始特征选择集合中的特征数量；
a分类误差率的权重,G［0,1］；
0——特征子集中选出特征比例的权重, =(1—a)。
1.2 Catboost
Catboost是一种新型的梯度提升算法，它是以决策树作为基本学习器的集成算法，不同于其它梯度提升算法，Catboost采用对称树的结构，在树的整个层次上使用相同的分割标准，这样的树是平衡的，并且加快了训练时间。Catboost的建树过程中，每棵树都是基于上一棵树的残差建立的。
Catboost可表示为
犉犜=士广，(2)正则化描述正确的是
t—1
式中：犉犜—
—由多个弱学习器集成的强学习器；
f------棵决策树，下一棵树在现有树的基础上顺序构造而成。
损失函数为
L(f(x),y)=为狑犻•l(.f(,X i),y t)+J(f),
(3)式中：K.f(.Xi),yi)---样本点(狓犻狔犻)的损失；
狑犻—
—第犻个目标的权重；
J(f)——正则化项。
Catboost使用前一棵树的预测结果来训练下一棵树，这个迭代过程使最终的预测结果更为准确，模型更具有鲁棒性。同时,Catboost提供了独特的特征重要性计算方式，为Catboost能够被用来做特征选择问题的启发式策略提供了重要依据。
36长春工业大学学报第42卷2CABFS算法描述
2.1特征评价策略
重要性度量指标是评估每个特征在所属特征
集中重要程度的一种衡量指标。Catboost提供
了多种重要性度量指标。其中，预测值改变量
(Prediction Values Change,PVC)显示特征值更
改时预测值的平均变化程度，特征越重要，则预测
值平均值的变化率越大。损失函数变化(Loss
FunctionChange，LFC)描述当模型中有此特征
与没有此特征时损失函数的变化，其变化量越大,
则该特征越重要。故对确定结构的树模型有：
PVC f——(狏］—avr)2•leaf letl+
irees,lea〔s F
(狏2—avr)2•leaf r g ht,(4)
avr—狏1•leafen+狏2•leafght
(5)
leafen+leaf r ght
式中:leafett,leafght分别表示左叶子和右叶子的权重；
狏1，狏2—
—分别表示左叶子和右叶子的目标函数值。
LFC i—/(exi)―/(features),(6)式中：/(exi)——不包含特征i时模型的损失函数值；
/(features)——使用全部特征时模型的损失函数值。
2.2特征选择过程
CABFS特征选择过程包含两个步骤：构造Catboost中的树模型和特征子集搜索策略。在构建树结构前，为了防止过拟合，每棵树的权重会随着选择不同的分割或不同的树而变化。在训练过程中,CABFS会连续构造一组树，每棵树会基于前一棵树的基础上，减少损失进行构建。构建一棵树分为两个阶段：选择树结构，得到多种树结构后，计算叶子节点的值。为了选择最佳的树结构，算法贪婪按顺序选择特征作为分割，并用这些分割构建一棵新树。重复以上过程，构建集成模型，依据2.1中的重要性度量指标对特征进行评分，生成新的特征重要性评价排名集合。
CABFS特征选择过程采用加权前向搜索策略进行实现，即在传统前向搜索的基础上进行改进，对特征的
两个度量指标PVC与LFC赋予相应的权重进行搜索，两个指标分别代表特征变化时预测值的改变量以及有无第i个特征时损失函数的变化量。在不同应用场景下，面对不同的特征选择需求时，可以赋予两个指标不同的权重来进行侧重的衡量。文中实验目的是与其他已有的特征选择算法进行比较，不涉及特殊应用场景，故将两个指标都赋予了相同的权重便于比较。
具体搜索过程操作如下：设置一个起始元素为空的特征集合S，根据PVC与LFC加权后得到的综合评价指标对候选特征子集进行搜索，将搜索到的特征依次添加到集合S中，目标是当加入该特征后提高目标集合的适应度值。
2.3伪代码
CABFS伪代码
输入：原始特征集合O
输出：目标特征集合T
步骤：
1:T—0；depth—0
2：建立根节点
3:while depth V树的最大深度do
4:for each s e O do
5：计算最佳特征分割点并为最佳分割点建立孩子节点
6：endfor
7:depth—depth+1
8：endwhie
9：根据式(2)将生成的树集成为统一的模型C
10：依据式(4)和(6)从C中生成重要性指标PVC和LFC
11：将PVC和LFC中相同特征对应的评价结果进行加权求和并排序，生成新的特征重要性评价排名集合I 12：定义最初的特征子集评价结果F(T)-0
13：foriinIdo
14：T'・TUi
15：计算新的特征子集评价结果F(T')
16：ifF(T')〉F(T)
17：TT‘
18：F(T)■F(T')
19：endfor
20：returnT
3实验结果与分析
3.1实验数据与对比算法
使用UCI数据集中的一些经典数据集进行对比实验，详细信息见表1。
第1期王丽，等：基于Catboost的特征选择算法37表1犝CI数据集个表4CABFS及其对比算法在Spambase上的结果%
数据集样本数特征数分类数
Spambase CA FR Glass21496
Spambase4601572CABFS
0.9300.645
Vehicle846184ABACO H0.9230.431 Waveform5000213
Wine178133ACOFS0.9220.447 Wisconsin683 92IBGSA0.9220.465 Yeast148489
IFSFOA0.9180.421实验采用一些近年来具有代表性的特征选择S-bBOA0.9230.456
算法与CABFS进行对比，见表2。
表2对比算法
表5CABFS及其对比算法在Vehicle上的结果%算法描述发表年份Vehcle CA FR
基于引力搜索算法的特征选择算法on1A CABFS0.7280.450 IBGSA[4]2014
ABACO H0.7530.436改进的森林优化特征选择算法9ni Q
IFSFOA[5]2018ACOFS0.7490.426基于二元蝴蝶优化算法的特征选择算法9A1Q IBGSA0.7450.413 S-bBOA[16]2019
IFSFOA0.7400.389基于蚁优化算法的特征选择算法9A1Q
ACOFS[7]2013S-bBOA0.7370.611基于蚁优化算法的特征选择算法oni R
ABACO H[8]2015表6CABFS及其对比算法在Waveform上的结果%
Waveform CA FR
3.2评价指标
实验采用特征分类准确率CA（Classification CABFS0.7980.345
Accuracy）以及特征维度缩减率FR（Feature
ABACO H0.7980.585 Reduction）对特征选择的效果进行评价，
正确分类的样本数
(7)ACOFS0.7970.272
CA测试集的样本数，
IBGSA0.7940.51 FR—总特征数-算法选择的特征数。（）
IFSFOA0.7980.381
总特征数
3.3实验结果与分析S-bBOA0.7950.333
CABFS及其对比算法在Glass、Spambase、
表7CABFS及其对比算法在Wine上的结果% Vehicle、Waveform、Wine、Wisconsin、.Yeast上的
结果分别见表3-表9。Wne CA FR 表3CABFS及其对比算法在Glass上的结果%CABFS0.9640.692 Glass CA FR ABACOH0.9690.484
CABFS0.7630.339
ACOFS0.9640.483 ABACO h0.7580.299
ACOFS0.7500.365IBGSA0.9780.341
IBGSA0.7380.315
IFSFOA0.9440.692 IFSFOA0.7210.444
S-bBOA0.7560.556S-bBOA0.9720.615
38长春工业大学学报第42卷
表8CABFS及其对比算法在Wisconsin上的结果％
Wisconsin CA FR
CABFS0.9800450
ABACO h09760384
ACOFS09740367
IBGSA09770386
IFSFOA09640556
S-bBOA09670.667表9CABFS及其对比算法在Yeast上的结果％
Yeast CA FR
CABFS0.5310106
ABACO h05240063
ACOFS05160102
IBGSA05150129
IFSFOA04830125
S-bBOA05100.250
通过表3-表9可以看到，CABFS在Glass、Spambase、Waveform、Wisconsin、Yeast这5个数据上的分类准确率均达到了最高，说明CABFS 在一定程度上能够很好地确保分类准确率，而针对以上数据集的维度缩减率而言,CABFS仅在Spambase上达到了最优，另外几个数据集上的排名均在居中位置，这说明
CABFS在追求分类准确率的同时，并没有完全的牺牲维度缩减率，而是一定程度上做到了兼顾，但是还无法保证两个衡量标准均达到最优的表现。
综合7个数据集的实验结果分析发现，大多数数据集的准确率都能在分类准确率或维度缩减率达到最优，只有Vehicle数据集上的结果没有达到最优。之所以有这种情况，是因为CABFS 算法应用于Vehicle数据集上在建树时分割特征的过程中无法获得最优的分割点导致的，但在维度缩减率上能排在第2位置，能够说明CABFS 对于降低数据维度方面相对其他对比算法而言，具有较好的效果。
4结语
CABFS将Catboost中构建树模型过程中的分割指标作为特征选择中度量特征重要性的标准，在传统前向搜索中对两种度量赋予了权值，并通过综合计算来进行搜索，实验结果证明, CABFS采用特征重要性度量作为启发式的策略是有效的，但在保证分类准确率结果好的情况下，如何进一步提高维度缩减率，仍需要更进一步的深入研究，并加以改进。
参考文献：
[1]张云鹏，闫一功.一种基于自适应遗传策略的特征选
择算法[J].长春工业大学学报：自然科学版,2010,
31(2):126-131.
[2]Rong M,GongD,GaoX．Featureselectionandits
usein big data：cha l enges,methods,andtrends
[J]IEEE Access,2019(7)1970919725.
[3]Ha l M A,Holmes G．Benchmarking a t ribute se-
lectiontechniquesfordiscreteclassdata mining[J]．
IEEE Transactions on Knowledge&Data Engi­
neering,2003,15(6)1437-1447.
[4]KohaviR,John G H．Wrappersforfeaturesubset
selection]〕]Artificial Intelligence,1997(1/2)：273-
324．
[5]AnarakiJR,UsefiH．Afeatureselectionbasedon
perturbationtheory[J]ExpertSystemswithAppli-
cations,2019,127：1-8．
[]周志华.机器学习[M]北京：清华大学出版社, 2016：252．
[7]VergaraJR,EstevezP A．Areview offeaturese-
lection methods based on mutualinformation[J]．Neural Computing and Applications,2014,24(1)：
175-186．
[8]Sagi O，Rokach L．Ensemblelearning：A survey
[J]．WileyInterdisciplinary Reviews：Data Mining
and Knowledge Discovery,2018,8(4)：1249.
[9]Kiziloz H E．Classifier ensemble methods in feature
selection[J]Neurocomputing202054：234-241．[10]Binder M，MoosbauerJ，ThomasJ，etal．Multi-
objective hyperparameter tuning and feature selec-
tionusingfilterensembles[C]//Proceedingsofthe
2020Geneticand Evolutionary Computation Con-
ference2020：471-479．
[11]Salem O A M，LiuF，ChenY PP，etal．Ensem-
blefuzzyfeatureselectionbasedonrelevancy，re-
dundancyand dependency criteria[J]．Entropy，
2020,22(7)757764.
[12]Ebrahimpour M K，EftekhariM．Ensembleoffea-
tureselection methods：a hesitantfuzzysetsap-
proach[J]．AppliedSoftComputing，2016，31：68-

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。