半动态集成选择分类方法

李 瑞，袁小玲

(1.陕西财经职业技术学院会计二系，陕西 咸阳 712000;2.陕西财经职业技术学院会计一系，陕西 咸阳 712000)

0 引言

近年来，多分类器系统(MCS)得到了越来越广泛的关注，并且已经成功应用到多个领域，比如风险评估［1］、文本分类［2］、以及变化检测［3］、故障诊断［4］、遥感分类［5］等。目前，已经提出一些经典的集成策略，比 如Bagging［6-7］、Boosting［8-9］和随机子空间方法［10-11］。由于以上这些方法中的每一个子分类器都要为测试样本输出一个结果，可能会存在冗余，而这会导致较高的计算复杂度。更为严重的是，如果子分类器集合中存在弱分类器，那么分类性能会受到极大影响。为了解决这一问题，有学者提出了选择性集成(SE)［12-13］，该方法能够避免传统集成分类器的缺点［14］。目前已经提出了一些方法，比如遗传算法［12］、半正定规划［15］、强化学习［16］、Reduce-error Pruning［15］等方法。

众所周知，在实际应用中，不同的测试样本在分类时会遇到不同的困难。而在SE 中，由于所选择的个体分类器集合相同，也会降低分类性能。但是，如果能够为每一个测试样本动态地选择分类器，会进一步提高分类性能。基于此，近年来，有学者提出了动态集成选择策略(DES)［17］。由于该策略能够动态地为每一个测试样本选择合适的个体分类器组成集成分类器，因而能够获得更好的性能。目前已经提出一些策略，比如K-Nearest-ORAcles(KNORA)［17］、Local Accuracy and Diversity Method［18］、Measure of Competence based on Random Classification Method［19］等。

尽管DES 能够获得更好的性能，但是当前的策略需要为每一个测试样本选择多个分类器。这使得当前策略的计算复杂度较高。为了解决这一问题，本文提出一种新的半动态集成选择策略(Semi-DES)。该策略吸取了SE 和DES 的优点。不仅能够降低计算复杂度，而且能够进一步提高分类性能。在Semi-DES 中，首先为所有的样本选择最好的一部分子分类器，然后在剩余的子分类器集合中为每一个测试样本动态地选择个体分类器，最终的结果通过融合以上2部分的输出得到。为了验证所提策略的性能，本文采用UCI 数据集验证。与其他方法相比，所提策略是一种非常有效的方法。

1 Semi-DES 策略

在这一节，首先给出Semi-DES 策略的框架，然后给出对应的算法。

1.1 框架

Semi-DES 包括2 个阶段:第一阶段静态地选择个体分类器;第二阶段为每一个测试样本动态地选择个体分类器。以一个多分类问题为例。假设训练样本为:

其中yi表示标记，D 表示样本特征的数量，C 表示类别数量，L 表示用来训练样本的数量。

假设所产生的个体分类器为C={C1，C2，...，CM}，其中M 表示个体分类器的数量。由于要生成2个集成分类器，并且将最终的结果融合起来，需要给出权值，这里用w1，w2表示，并且需要满足如下限制:

在第一阶段，为所有的测试样本选择个体分类器。这些子分类器被认为是“优秀的”子分类器。假设所选择的个体分类器为}，其中I 表示分类器的数量。显然C1⊆C，并且I ≤M。由于所选择的个体分类器相对重要性不同，因而这里给出对应的权值］，并且满足如下限制:

最终的标记为:

整个过程如图1 所示。

图1 Semi-DES 的框架

1.2 所提算法

在这一节提出了用于实现Semi-DES 的算法，算法包括2 阶段。这里假设所有的权值均相同，并假设2 阶段的权值为W1，W2。在第一个阶段，为所有的测试样本选择一部分相同的个体分类器。由于进化计算能够取得全局最优解，该算法在第一阶段用于选择个体分类器。本文采用遗传算法实现。在遗传算法中，每一个个体的编码中，“1”表示选择了个体分类器，“0”表示个体分类器没有选择，所产生的个体分类器的数量为M。假设所有选择的分类器的权值相同。种群随机初始化，目标函数为分类准确率，如式(5)所示:

其中N 表示正确分类的样本数量，T 表示训练样本的数量。接下来算法将会迭代执行直到满足终止条件。所选择的个体分类器是}，其中I表示个体分类器的数量，这些个体分类器会为每个测试样本使用。接下来将从剩余的个体分类器中为每一个样本选择个体分类器。在本文中采用KNORA［12］选择个体分类器。验证集合与训练集合相同。对每个测试样本，采用K 近邻的方法提取验证集，然后判断哪一个分类器更合适。如果当前的个体分类器能够正确地分类验证集，那么将选择当前的个体分类器作为该测试样本的个体分类器，否则，该个体分类器不被选择;如果所有的分类器都不能准确地分类验证集，那么令K=K -1。这一过程将会持续进行直到至少选择出一个个体分类器。当K=1 时，如果没有任何一个分类器能够被提取出来，将采用所有的分类器用于分类。所选择的分类器为，其中P 表示分类器的数量。在选择出分类器之后，采用公式(3)得到最终的输出。算法如下所示。

算法1

输入:训练集合T 和测试样本X;

步骤1:产生个体分类器C={C1，C2，…，CM};

步骤3:从剩余的个体分类器中利用K 近邻方法为每一个样本选择分类器;

输出:最终的结果由公式(3)得到。

2 实 验

在这一节，所提算法采用UCI 数据集验证。首先给出实验设置，其次给出实验结果。

2.1 实验设置

本文采用14 个UCI 数据集［20］验证所提算法。表1 给出了数据集的属性，比如样本数量、属性和类别。这里采用10 倍交叉验证，所有实验在MATLAB 2009a 平台上执行，采用Intel 酷睿2 处理器，主频3.0 GHz，内存为2 G，在Windows XP 系统上验证。

本实验采用Bagging 产生个体分类器，Fisher 判别分析(FDA)和K 近邻分类器(KNN)作为个体分类器，产生个体分类器的数量为20。4 种典型的算法用于比较:

1)最好的单分类器(SB)。集成分类器中最好的单分类器。

2)传统集成分类器(ALL)［4］。该集成分类器采用投票机制得到最终的输出。

3)基于遗传算法的选择性集成方法(SE-GE)。该方法利用遗传算法静态的选择个体分类器。

4)KNORA 方法［12］。该方法是一种典型的动态集成选择方法。

表1 数据集的描述

2.2 实验结果

表2 和表4 给出了运行10 次的平均分类准确率，黑体部分表示每一个数据集的最好性能。显然，在大部分情况下，Semi-DES 能够取得更高的分类性能。表2 给出了基分类器是FDA 时的结果。除了Car 和Mammographic 数据集外，所提算法在其他数据集都取得了最好的性能。表3 给出了基分类器是KNN 时的结果(这里近邻的数量设为10)。除了Liver、Brest Cancer、Spam 和Nursery 数据集外，Semi-DES 均能取得最好的性能。表3 和表5 给出了平均分类结果的标准差。通过统计分析，以P ＜0.05 为显著性差异水平，可以看出所提算法要优于其它比较算法。

表2 FDA 作为基分类器时的平均分类结果

表3 FDA 作为基分类器时平均分类结果的标准差

表4 KNN 作为基分类器时的平均分类结果

表5 KNN 作为基分类器时平均分类结果标准差

3 结束语

本文提出了一种新的半动态集成选择策略(Semi-DES)。该策略充分吸收了SE 和DES 的优势，并且能够取得更好的分类性能。首先给出了该策略的框架，并且提出了相应的算法，实验结果和统计分析表明所提算法能够取得较好的分类性能。所提Semi-DES 是一种通用的框架，其他SE 和DES 方法也可以嵌入到该框架中，这将在以后的研究中做进一步阐述。

［1］Marques A I，Garcia V，Sanchez J S.Two-level classifier ensembles for credit risk assessment［J］.Expert Systems with Applications，2012，39(12):10244-10250.

［2］Michelangelo Paci，Loris Nanni，Stefano Severi.An ensemble of classifier based on different texture descriptors fortexture classification［J］.Journal of King Saud University-Science，2013，25(3):235-244.

［3］Moumita Roy，Susmita Ghosh，Ashish Ghosh.A novel approach for change detection of remotely sensed images using semi-supervised multiple classifier system［J］.Information Science，2014，269(10):35-47.

［4］慕昱，夏虹，刘永阔.基于集成学习的核电站故障诊断方法［J］.原子能科学技术，2012，46(10):1254-1258.

［5］刘培，杜培军，谭琨.一种基于集成学习和特征融合的遥感影像分类新方法［J］.红外与毫米波学报，2014，33(3):311-317.

［6］Mordelet F，Vert J P.A bagging SVM to learn from positive and unlabeled examples［J］.Pattern Recognition Letters，2014，37(1)，201-209.

［7］李明方，张化祥.针对不平衡数据集的Bagging 改进算法［J］.计算机工程与应用，2010，46(30):40-42.

［8］Nicolas Garcia-Pedrajas，Aida de Haro-Garcia.Boosting instance selection algorithm［J］.Knowledge-based Systems，2014，67(9):342-360.

［9］于玲，吴铁军.集成学习:Boosting 算法综述［J］.模式识别与人工智能，2004，17(1):52-59.

［10］Le Zhang，Ponnuthrai Nagaratnam Suganthan.Random Forest with ensemble of feature spaces［J］.Pattern Recognition，2014，47(10):3429-3437.

［11］杨明，王飞.一种基于局部随机子空间的分类集成算法［J］.模式识别与人工智能，2012，25(4):595-603.

［12］Zhou Zhihua，Wu Jianxin，Tang Wei.Ensembling neural networks:Many could be better than all［J］.Artificial Intelligence，2002，137(1-2):239-263.

［13］张春霞，张讲社.选择性集成学习算法综述［J］.计算机学报，2011，34(8):1399-1410.

［14］Zhang Li，Zhou Weida.Sparse ensembles using weighted combination methods based on linear programming［J］.Pattern Recognition，2011，44(1):97-106.

［15］Margineantu D D，Dietterich T G.Pruning adaptive boosting［C］// Proceedings of the Fourteenth International Conference on Machine Learning.1997:211-218.

［16］Partalas I，Tsoumakas G，Vlahavas I.Pruning an ensemble of classifiers via reinforcement learning［J］.Neurocomputing，2009，72(7-9):1900-1909.

［17］Albert H R Koa，Robert Sabourina，Alceu Souza Britto Jr.From dynamic classifier selection to dynamic ensemble selection［J］.Pattern Recognition，2008，41(5):1718-1731.

［18］DeSouto M C P，Soares R G F，Santana A，et al.Empirical comparison of dynamic classifier selection methods based on diversity and accuracy for building ensembles［C］// Proceedings of the International Joint Conference on Neural Networks.2008:1480-1487.

［19］Tomasz Woloszynski，Marek Kurzynski，Pawel Podsiadlo，et al.A measure of competence based on random classification for dynamic ensemble selection［J］.Information Fusion，2012，13(3):207-213.

［20］Newman D J，Hettich S，Blake C L，et al.UCI Repository of Machine Learning Databases［EB/OL］.http://www.ics.uci.edu/～mlearn/MLRepository.html，2014-11-21.