预测性能和选择速度方面均位居列。其他基于排 名法的选择性集成算法还有Ｋａｐｐａ算法、基于 ＢＯｏｓｔｉｎｇ的选择性集成法等。 排名法的关键是采用何种标准对各基分类器 进行评估，即所使用的排序标准。早期的算法大都 是基于预测性能以及源于信息论的各种统计量，但 是实验证明：个体基分类器预测性能好并不能保证 集成分类器也具有较好的预测性能，因此目前许多 基于排名的算法都是通过分析分类器之间的相关 性，使得所选的基分类器具有互补性，从而避免它 们的优势互相抵消。 排名法的另一个重要问题是如何确定最终获 得的目标集成分类器的大小。最简单的方法是预 设目标集成分类器的大小或基分类器数目占总数 的百分比；另一种方法是设定基于精度或其他度量 的阈值，只有达到该阈值的基分类器才能入选。为
究重点。
Ａｂｓｔｒａｃｔ：Ｅｎｓｅｍｂｌｅ ｐｒｕｎｉｎｇ ｉｓ
ａｎ
ａｃｔｉｖｅ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎ ｉｎ ｔｈｅ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｆｉｅｌｄ．
ｕｓｅ
Ｅｎｓｅｍｂｌｅ Ｔｈｅｒｅ
ｏｎ
ｐｒｕｎｉｎｇ ｉｓ ａｎ ＮＰ—ｈａｒｄ ｐｒｏｂｌｅｍ，ｍｏｓｔ ｒｅｓｅａｒｃｈｅｒｓ
ｐｒｕｎｉｎｇ ａｐｐｒｏａｃｈｅｓ
ｂａｓｅｄ， ｉｔ ｉｓ ｄｉｆｆｉｃｕｌｔ
ｔｏ
ｕｎｄｅｒｓｔａｎｄ ｔｈｅｍ ｃｌｅａｒｌｙ．
ｔｏ
Ｉｎ
ｔｈｉｓ
ｐａｐｅｒ，
ቤተ መጻሕፍቲ ባይዱ
ｔｈｅ ｅｎｓｅｍｂｌｅ ｏｐｔｉｍｉｚａｔｉｏｎ—
ａｒｅ
ｄｉｖｉｄｅｄ ｉｎｔｏ ｆｏｕｒ ｃａｔｅｇｏｒｉｅｓ ａｃｃｏｒｄｉｎｇ
ｔｈｅｉｒ ｐｒｕｎｉｎｇ ｓｔｒａｔｅｇｉｅｓ：
赵强利，蒋艳凰，徐明
ＺＨＡＯ Ｑｉａｎ矿¨，ＪＩＡＮＧ Ｙａｎ－ｈｕａｎｇ。ＸＵ Ｍｉｎｇ
（国防科学技术大学计算机学院。湖南长沙４１００７３）
（Ｓｃｈｏｏｌ
ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ
４１００７３，Ｃｈｉｎａ）
排名法 排名法采用特定函数对所有基分类器进行评
估并排序，然后按照该次序选择基分类器。排名法 的最大优势在于分类器选择速度快，该类方法涵盖 的选择性集成算法较多，其中方向排序（Ｏｒｉｅｎｔｅｄ ｏｒｄｅｒ，简称ｏｏ）［４］、边界距离最小化（Ｍａｒｇｉｎ
ｔａｎｃｅ
Ｄｉｓ—
Ｍｉｎｉｍｉｚａｔｉｏｎ，简称ＭＤＳＱ）Ｌ５３这两种算法在
ｂａｓｅｄ，ｒａｎｋｉｎｇ—ｂａｓｅｄ，ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ａｎｄ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ—ｂａｓｅｄ．
ｃａｔｅｇｏｒｙ
ａｒｅ
Ｎｅｘｔ，ｔｈｅ ｐｏｐｕｌａｒ ａｌｇｏｒｉｔｈｍｓ ｏｆ ｅａｃｈ
ｉｍｐｌｅｍｅｎｔｅｄ ａｎｄ ｔｅｓｔｅｄ
ｏｎ
２０ ｄａｔａｓｅｔｓ ｆｒｏｍ
ｔｈｅ ＵＣＩ ｒｅｐｏｓｉｔｏｒｙ，ａｎｄ ｃｏｍｐａｒｅｄ ｆｒｏｍ ｔｈｒｅｅ Ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ
２．２
２选择性集成算法分类
根据不同的分类标准，可将选择性集成算法分 为不同的几类。主要的分类方法有如下三种： （１）根据基分类器的选择时机的不同，可分为 静态法和动态法。静态法是利用一个校验样本集 来计算最佳的基分类器集合，该基分类器集合将持 续用于对新样本的预测。动态法是在预测新样本 类别时才进行分类器选择，选择的依据是新样本的 属性特征以及基分类器在训练时的表现，每个新样 本所选的基分类器集合可能互不相同。目前选择 性集成方法的研究多集中在静态方法上。 （２）根据选择过程中对集成分类器的度量标准 的不同，可分为基于预测精度的方法和基于多样性 的方法。预测精度度量包括基分类器的预测准确 度及其变体，而多样性度量的目的则是发现和利用 分类器之间的互补性，从而间接地提升集成预测性 能。 （３）根据算法采用的选择策略，可将选择性集 成方法分为四类：迭代优化法、排名法、分簇法、模 式挖掘法。 下面对第三种划分进行详细介绍。 ２．１迭代优化法 给定一个度量准则（例如集成分类器在校验样 本集上的预测精度），选择性集成的目的是找到一 个基分类器集合，使得该度量的值最优。分类器的 选择过程是一个组合优化问题，如采用穷举法则存 在组合爆炸问题，因此研究者们将选择性集成问题
ａｒｅ
ｈｅｕ“ｓｔｉｃｓ
ｔｏ
ｏｂｔａｉｎ
ｎｅａｒ
ｏｐｔｉｍａｌ ｓ０１ｕｔｉｏｎｓ．
ａｌｒｅａｄｙ ｍａｎｙ ｅｎｓｅｍｂｌｅ ｐｒｕｎｉｎｇ ａｐｐｒｏａｃｈｅｓ ｉｎ １ｉｔｅｒａｔｕｒｅｓ，ｂｕｔ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｐｅｒｓｐｅｃｔｉｖｅｓ
ａｒｅ
ｗｈｉｃｈ ｔｈｏｓｅ ｍｅｔｈｏｄｓ
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—１３０Ｘ．２０１２．０２．０２５
中图分类号：ＴＰｌ８
文献标识码：Ａ 对这些分类器进行某种方式的组合，共同解决同一
１
引言
集成学习（Ｅｎｓｅｍｂｌｅ Ｌｅａｒｎｉｎｇ）‘１３通过对训练
个学习任务。集成学习过程可分为两大阶段，一是 构造基分类器，二是对这些基分类器的预测结果进 行组合。相对于单个分类器，集成学习有效地提高 了分类器的泛化能力。选择性集成（Ｅｎｓｅｍｂｌｅ
ＣＮ４３—１２５８／ＴＰ ＩＳＳＮ １００７—１３０Ｘ
计算机工程与科学
ＣＯＭＰＵＴＥＲ ＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥ
２０１２年第３４卷第２期
Ｖ０１．３４，Ｎｏ．２，２０１２
文章编号：１００７—１３０Ｘ（２０１２）０２一０１３４一０５
选择性集成算法分类与比较＋
Ｃａｔｅｇｏｒｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ Ｅｎｓｅｍｂｌｅ Ｐｒｕｎｉｎｇ Ａｌｇｏｒｉｔｈｍｓ
样本的学习获取若干分类器（称为基分类器），然后
＊
收稿日期：２０１０一Ｏ卜０６；修订日期：２０ｌｏ—０４—２５
基金项目：国家自然科学基金资助项目（６０９０５０３２，６０７７３０１７） 通讯地址：４１００７３湖南省长沙市国防科学技术大学计算机学院博士生队
Ａｄｄｒ姻ｓ：Ｄｏｃｔｏｒａｌ Ｂｒｉｇａｄｅ，Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ ４１００７３，Ｐ．Ｒ． Ｃｈｉｎａ
转换为逐步求优问题，以便在较短的时间内获得问 题的近似最优解。迭代优化方法涵盖了一大批选 择性集成算法，这类方法的核心是问题的映射，即 如何将分类器选择问题表示为相应的优化问题。 迭代优化法需要引入某一优化处理过程，例如 ＧＡＳＥＮ算法凹］利用遗传算法来进化一组与分类 器对应的权重向量，目标是使得集成分类器对校验 样本集的预测精度最优。ＥＰＲＬ算法利用强化学 习的方法获得一个最优的决策函数，同时将该函数 作为启发式来指导搜索过程的进行。ＳＤＰ算法利 用数学变换将选择性集成转化为二次整数规划问 题，并利用整数规划法求得近似最优的基分类器集 合。受限于优化方法的特性，这些选择性集成算法 的收敛速度均较慢。 爬山法也将选择性集成看作是一个逐步求优 的搜索过程，不过它每一次搜索都是建立在对前一 次搜索评估的基础之上，因此它的搜索空间可以迅 速减小，速度大为提高。爬山法根据搜索的方向分 为前向选择（Ｆｏｒｗａｒｄ Ｓｅｌｅｃｔｉｏｎ，简称ＦＳ）和向后 消除（Ｂａｃｋｗａｒｄ Ｅｌｉｍｉｎａｔｉｏｎ）两种¨ｊ。爬山法的关 键在于评估标准的确定。由于爬山法思想简单，速 度较快，因此得到了广泛的关注。
关键词：集成学习；选择性集成；排名法；分簇法；迭代优化法；模式挖掘法
Ｋｅｙ ｗｏｒｄｓ：ｅｎｓｅｍｂｌｅ １ｅａｒｎｉｎｇ；ｅｎｓｅｍｂｌｅ
ｐｒｕｎｉｎｇ；ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ ｐｒｕｎｉｎｇ；ｒａｎｋｉｎｇ ｂａｓｅｄ ｐｒｕｎ—
ｉｎｇ；ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｐｒｕｎｉｎｇ；ｐａｔｔｅｒｎ ｍｉｎｉｎｇ ｂａｓｅｄ ｐｒｕｎｉｎｇ
万方数据
赵强利等：选择性集成算法分类与比较
１３５
Ｐｒｕｎｉｎｇ）［２］是在集成学习的基分类器构造和分类 器组合之间又增加了一个阶段，即分类器选择阶 段。选择性集成具有两个方面的优越性：（１）提高 泛化能力：通过剔除对集成分类器的预测能力具有 负面影响的基分类器，进一步提高预测性能；（２）降 低预测阶段的开销：去掉冗余基分类器以减少集成 分类器的存储空间、降低预测运算量、加快预测速 度。 本文对选择性集成算法的分类进行了介绍，并 根据选择策略将已有的选择性集成算法分为四类， 最后从预测精度、分类器选择时间、目标集成分类 器大小三个方面对各类典型算法进行了比较分析。 文章的结构如下：第２节介绍选择性集成算法分类 以及典型的选择性集成算法；第３节对实验结果进 行比较分析；最后总结全文，并展望了未来这一方 向的研究重点。
来自不同领域的数据集。
３．１
实验方法 实验采用十次交叉验证的方法。为了充分验
证各算法的性能，实验采用了四种异构的基分类 器［１…，所生成基分类器中有４０个ＢＰＮＮ神经网 络，２０个Ｃ４．５决策树，２０个简单贝叶斯，２０个 ＳＶＭ支持向量机。 ３．２预测精度 从表１可以看出，ＳｅｌＢ的结果表明选择单个 最优基分类器极有可能出现过适应问题。Ｂａｇｇｉｎｇ 的结果说明在绝大多数情况下集成学习的性能优 于单个分类器，同时也可能表明基分类器相关性强 或是性能较差会对集成分类器的预测性能有较大 影响。其他六种选择性集成算法的实验结果再次 验证了选择性集成能够提高集成分类器的泛化能 力。ＧＡＳＥＮ算法的性能相对不佳，我们认为其主 要原因在于ＧＡＳＥＮ终止条件的确定相对困难，从 而难以达到全局最优。ＣＰＦ利用分簇思想引入了 多样性的考虑，其存在的问题是即使性能较差的基 分类器，由于其差异性较高，也可能被选人到目标 集成分类器。ＦＳ算法以预测精度作为度量标准进 行贪婪式选择，ＯＯ算法以基分类器签名向量与参 考向量间的角度进行排序，它们均获得较好的预测 性能。ＭＤＳＱ和ＰＭＥＰ是最近提出的新算法，这 两种算法均综合考虑了基分类器的预测精度和多 样性，并获得了优异的性能。