基于边缘分类能力的动态集成选择算法

第３２卷第６期　２０１５年６月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖｏｌ＿３２　Ｎｏ．６　Ｊｕｎ．２０１５　

基于边缘分类能力的动态集成选择算法水　

陈睿　，黄海军　，黄雯　，胡劲松　

（１．解放军电子工程学院网络系，合肥２３００３７；２．东华理工大学理学院，南昌３３００１３）　

摘要：提出了一种新的基于边缘分类能力排序准则，用于基于排序聚集（ｏｒｄｅｒｅｄ　ａｇｇｒｅｇａｔｉｏｎ，ＯＡ）的分类器选　

择算法。为了表征分类器的分类能力，使用随机参考分类器对原分类器进行模拟，从而获得分类能力的概率模　

型。为了提高分类器集成性能，将提出的基于边缘分类能力的排序准则与动态集成选择算法相结合，首先将特　

征空间划分成不同能力的区域，然后在每个划分内构造最优的分类器集成，最后使用动态集成选择算法对未知　

样本进行分类。在ＵＣＩ数据集上进行的实验表明，对比现有的排序准则，边缘分类能力的排序准则效果更好，进　

一步实验表明，基于边缘分类能力的动态集成选择算法较现有分类器集成算法具有分类正确率更高、集成规模　

更小、分类时间更短的优势。　

关键词：动态集成选择；排序聚类；分类器能力；ｂａｇｇｉｎｇ　

中图分类号：ＴＰ３９１　文献标志码：Ａ　文章编号：１００１—３６９５（２０１５）０６—１６９８．０５　

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１５．０６．０２１　

Ｄｙｎａｍｉｃ　ｅｎｓｅｍｂｌｅ　ｓｅｌｅｃｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｃｌａｓｓｉｆｉｅｒ　ｃｏｍｐｅｔｅｎｃｅ　ｏｆ　ｍａｒｇｉｎ　

Ｃｈｅｎ　Ｒｕｉ　，Ｈｕａｎｇ　Ｈａｉｊｕｎ　，Ｈｕａｎｇ　Ｗｅｎ　，Ｈｕ　Ｊｉｎｇｓｏｎｇ　（１．Ｄｅｐｔ．ｏｆＮｅｔｗｏｒｋ，ＰＬ４　Ｅｌｅｃｔｒｏｎｉｃ　ＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，Ｈｅｆｅｉ　２３００３７，Ｃｈｉｎａ；２．Ｄｅｐｔ．ｏｆＳｃｉｅｎｃｅ，Ｅａｓｔ　Ｃｈｉｎａ　Ｉｎｓｔｉｔｕｔｅ　ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｎａｎ—　ｃｈａｎｇ　３３００１３，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａ　ｎｅｗ　ｏｒｄｅｒｉｎｇ　ｃｒｉｔｅｒｉｏｎ　ｗｈｉｃｈ　ｃｏｕｌｄ　ｂｅ　ｕｓｅｄ　ｂｙ　ｃｌａｓｓｉｆｉｅｒｓ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｏｒ・　ｄｅｒｅｄ　ａｇｇｒｅｇａｔｉｏｎ：Ｆｏｒ　ｃａｌｃｕｌａｔｉｎｇ　ｔｈｅ　ｃｏｍｐｅｔｅｎｃｅ　ｏｆ　ｔｈｅ　ｃｌａｓｓｉｆｉｅｒ，ｉｔ　ｕｓｅｄ　ａ　ｒａｎｄｏｍｉｚｅｄ　ｒｅｆｅｒｅｎｃｅ　ｃｌａｓｓｉｆｉｅｒ　ｆｏｒ　ｍｏｄｅｌｉｎｇ　ｔｈｅ　ｃｌａｓｓｉｆｉｅｒ　ｔｏ　ｇｅｔ　ｔｈｅ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｍｏｄｅｌ　ｏｆ　ｃｌａｓｓｉｆｉｅｒ　ｃｏｍｐｅｔｅｎｃｅ．Ｂｙ　ｃｏｍｂｉｎｉｎｇ　ｗｉｔｈ　ｏｒｄｅｒｉｎｇ　ｃｒｉｔｅｒｉｏｎ　ｂａｓｅｄ　ｏｎ　ｃｌａｓｓｉｆｉｅｒ　ｅｏｍ—　ｐｅｔｅｎｃｅ　ｏｆ　ｍａｒｇｉｎ，ｔｈｅ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａ　ｎｏｖｅｌ　ｄｙｎａｍｉｃ　ｅｎｓｅｍｂｌｅ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ（ＣＣＭ—ＤＥＳ）ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｐｅｒｆｏｒｍ—　ａｎｃｅ　ｏｆ　ｔｈｅ　ｅｎｓｅｍｂｌｅ．ＣＣＭ—ＤＥＳ　ｆｉｒｓｔ　ｄｉｖｉｄｅｄ　ｆｅａｔｕｒｅ　ｓｐａｃｅ　ｉｎｔｏ　ｄｉｆｆｅｒｅｎｔ　ｒｅｇｉｏｎｓ，ａｎｄ　ｔｈｅｎ　ｃｏｎｓｔｒｕｃｔｅｄ　ｏｐｔｉｍａｌ　ｅｎｓｅｍｂｌｅｓ　ｉｎ　ｅｖｅｒｙ　ｒｅｇｉｏｎ．Ｉｔ　ｕｓｅｄ　ＤＥＳ　ｆｏｒ　ｃｌａｓｓｉｆｙ　ｔｈｅ　ｕｎｌａｂｅｌｅｄ　ｓａｍｐｌｅ　ａｔ　ｌａｓｔ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｏｎ　ＵＣＩ　ｄａｔａｓｅｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｃｒｉｔｅｒｉｏｎ　ｂａｓｅｄ　ｏｎ　ｍａｒｇｉｎ　ｃｌａｓｓｉｆｉｅｒｓ　ｃｏｍｐｅｔｅｎｃｅ　ｉｓ　ｂｅｔｔｅｒ　ｔｈａｎ　ｃｕｒｒｅｎｔ　ｏｒｄｅｒｉｎｇ　ｃｒｉｔｅｒｉｏｎ．Ｆｕｒｔｈｅｒｍｏｒｅ，ＣＣＭ—ＤＥＳ　ｈａｓ　ｔｈｅ　ａｄｖａｎｔａｇｅｓ　ｏｆ　ｓｍａｌ—　ｌｅｒ　ｅｎｓｅｍｂｌｅｓ，ｈｉｇｈｅｒ　ａｃｃｕｒａｃｙ，ｓｈｏｒｔｅｒ　ｃｌａｓｓｉｆｙｉｎｇ　ｔｉｍｅ　ｔｈａｎ　ｃｕｒｒｅｎｔ　ｅｎｓｅｍｂｌｅ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｄｙｎａｍｉｃ　ｅｎｓｅｍｂｌｅ　ｓｅｌｅｃｔｉｏｎ；ｏｒｄｅｒｅｄ　ａｇｇｒｅｇａｔｉｏｎ；ｃｌａｓｓｉｆｉｅｒ　ｃｏｍｐｅｔｅｎｃｅ；ｂａｇｇｉｎｇ　

０　引言　

大量的理论和实验研究显示，集成多个分类器的预测结果　是一种提高泛化能力的有效策略。Ｂａｇｇｉｎｇ和Ｂｏｏｓｔｉｎｇ是两种　

被广泛使用分类器集成算法。为了获得较高的分类精度，两种　算法都需要联合大量的分类器，从而导致存储空间需求增加，　同时降低了分类的速度。一种可能解决方案是选择部分分类　器进行集成，Ｚｈｏｕ等人…指出使用部分分类器的集成效果可　

能优于使用全部分类器，该方案不仅能够降低集成的复杂度，　而且可能提高算法的性能。近十年来研究人员提出了各种选　择性集成学习算法，其基本思想是通过某种评测方法对原分类　

器集合中的分类器进行评估，从中选择部分基分类器，使得最　终的分类器集成泛化误差最小。张春霞等人　根据评测方法　不同将选择性集成学习算法分为聚类、排序、选择、优化等类　别。其中，排序聚集算法具有计算复杂度低、较为直观的优点。　

该方法基于对所有可能的分类器集成子集进行贪婪局部搜索　的思想　Ｊ，通过对基分类器进行排序来实现集成选择。通常，　

分类器集成过程中分类器聚集的顺序是随机的，随着集成的分　类器数量的增加，分类器集成的泛化误差随之降低。当采用合　

适的聚集顺序，泛化误差将在分类器数量增加到一定数量（分　

类器全部数量的中间某个值）时达到最小。Ｍａｒｔｉｎｅｚ—Ｍｕｏｚ等　人　指出，排序聚集算法能够有效对分类器集成进行修剪，并　

能够达到复杂度较高的集成选择算法（如基于ＧＡ和基于　ＳＤＰＬ５　的集成选择算法）相近的分类结果。不同文献对于降低　

分类器集成大小的算法称呼不尽相同，如集成修剪（ｅｎｓｅｍｂｌｅ　

ｐｒｕｎｉｎｇ）、集成细化（ｅｎｓｅｍｂｌｅ　ｔｈｉｎｎｉｎｇ）、集成选择（ｅｎｓｅｍｂｌｅ　ｓｅｌｅｃｔｉｏｎ），为了方便解释，下文统一称为集成选择。　

基于ＯＡ的分类器集成选择算法的关键在于排序准则的　选取，其中常用的包括分类精度和多样性等，这些准则基于所　有样本提供相同信息的假设对分类器进行评估。然而研究表　

明，ｍａｒｇｉｎ样本（即类边界样本）能够提供更多分类相关信息，　

为此，本文提出了一种基于边缘分类能力的排序准则，不同以　

收稿日期：２０１４—０４—２２；修回日期：２０１４—０６一ｌ１　基金项目：国家自然科学基金资助项目（６１００４０６９）；安徽省自然科学基金资助项目　

（１２０８０８５ＱＦ１０７）　作者简介：陈睿（１９８６．），男，江西抚州人，博士研究生，主要研究方向为图像处理与模式识别、人工智能、信息安全技术（ｃａｐｔｃｈａｆｕｎ＠１６３．　ｃｏｎ１）；黄海军（１９７５．），男，讲师，博士，主要研究方向为信息安全技术、人工智能；黄雯（１９８２一），女，讲师，硕士，主要研究方向为图像处理与模式识　别、统计学、信息安全技术；胡劲松（１９７１一），男，讲师，博士，主要研究方向为图像处理与模式识别、人工智能、信息安全技术．

　第６期　陈睿，等：基于边缘分类能力的动态集成选择算法　・１６９９・　

往对于分类器能力的评估直接来自于验证集合上获得分类器　的分类精度，本文采用随机参考分类器（ｒａｎｄｏｍｉｓｅｄ　ｒｅｆｅｒｅｎｃｅ　

ｃｌａｓｓｉｆｉｅｒ，ＲＲＣ）对分类器进行模拟，从而获得分类能力的概率　模型。同时结合ｍａｒｇｉｎ值评估分类能力并作为分类器集成选　

择的排序准则。Ｋｏ等人　指出对不同的未知样本采用不同的　分类器集成，即动态分类器集成（ｄｙｎａｍｉｃ　ｅｎｓｅｍｂｌｅ　ｓｅｌｅｃｔｉｏｎ）　

进行分类比静态选择算法更加有效。为此，本文提出了一种新　的基于ｍａｒｇｉｎ分类能力的动态集成选择算法，不同于以往的　基于ＯＡ分类器集成选择算法在整个样本空间对基分类器进　

行一次排序，该算法使用聚类算法将特征空间划分为不同的能　力区域，在每个划分内分别使用ｍａｒｇｉｎ分类能力准则对基分　

类器排序。针对不同的分类区域（划分）选择不同的分类器集　成，从而提高未知样本的分类精度。　

１　相关工作　

本文主要研究基于ＯＡ的分类器集成选择算法，所以本章　

只对目前该算法的研究现状进行简要介绍。基于ＯＡ的分类　器集成选择算法主要运用于ｂａｇｇｉｎｇ方法产生的分类器集成。　

通常情况下ｂａｇｇｉｎｇ算法并不指定分类器聚集的顺序（也就是　说采用随机顺序聚集）。这种情况下，分类器集成的分类错误　随着分类器聚集的数量增加而单调递减（如图１带星号曲线　

所示）。当分类器数量增加到一定程度，分类器集成的分类错　误无限接近一个固定值（该固定值被认为是ｂａｇｇｉｎｇ方法能够　

达到的最小分类错误，如图１实线水平线所示）。而基于ＯＡ　的分类器集成选择算法主要是通过修改基分类器集成的顺序，　

使得首先参与聚集的分类器集成效果最优。假设全部基分类　器集合Ｅ　．已经参与集成的分类器集合Ａ　，根据某种规则，从　

剩余的分类器集合　／Ａ　中选出一个分类器添加到分类器集　成中，使得新的分类器集合Ａ　性能得到优化。修改分类器　聚集顺序以后，分类器集成的分类错误在分类器聚集数量达到　

某一中间值时达到最小（如图１虚线所示）。该值通常小于全　部分类器参与集成的错误，因此，该算法能够在多项式时间复　

杂度内获得分类器集成选择的一个近似最优解　

褂　账　拯　

骼　匡强　ｌ　

｜　

一　、、、一．一一一一，一一一　一一一一　

Ｕ　１Ｕ　２Ｕ　３０　４０　Ｕ　６０，Ｕ　Ｕ　聚集的分类器数量　图１分类器集成错误率随分类器聚集数量的变化示意图　

确定分类器聚集的顺序主要存在两个问题：ａ）如何确定　修剪后分类器集成大小，即如何获得错误最小值或者近似最小　

值对应的集成大小；ｂ）如何确定排序准则。对于问题ａ），通常　

可以采用选择一个验证集合来确定集成大小或者根据经验值　确定　。对于问题ｂ），研究人员提出一些准则，其中包括：　

ａ）误差。误差下降排序首先选择在验证集合Ｖａｌ上错误　率最小的分类器排第一个位置，剩余分类器按照当前聚集分类　

器集成错误最小的原则，依次参与分类器聚集。　

Ｂａｓｅ　＋１＝　ａｘ，　．１［ＦＡｕＵＢ　（　）＝Ｙ］　（１）　、　ｔＹ　Ｅ　Ｖ８１　其中：｜ｊ｝∈Ｅ　／Ａ　；　为由分类器集成Ａ确定的分类判别函数；　

Ｂａｓｅ　为基分类器　为样本　的真实类别；Ⅱ［ｅｘｐ］是Ｉｖｅｒｓｏｎ　运算，其定义为　ｒ　１　ｉｆ　ｅｘｐ＝ｔｒｅｅ　Ⅱ［ｅｘｐ］　ｉ　０　ｉｆ。　：ｆａｌ　。　（２）　

ｂ）Ｋａｐｐａ统计量。Ｋａｐｐａ统计量通过计算验证集上两个　分类器获得相同结果的比例来衡量分类器的差异度。Ｋａｐｐａ　

值越小对应于差异度越大。根据Ｋａｐｐａ统计量进行排序，首先　将Ｋａｐｐａ统计量最小的一对分类器排在前两个位置，剩余的分