基于度量学习的邻域k凸包集成方法

牟廉明

（内江师范学院 四川省高等学校数值仿真重点实验室，四川 内江 641100）

基于度量学习的邻域k凸包集成方法

牟廉明

（内江师范学院 四川省高等学校数值仿真重点实验室，四川 内江 641100）

k局部凸包分类方法通过改进k近邻算法在处理小样本问题时的决策边界而显著提高分类性能，k子凸包分类方法通过克服k凸包分类对类数和样本环状分布的敏感性而改善了分类性能。但是，该方法仍然对样本距离度量方法敏感，并且在k邻域内不同类的样本数经常严重失衡，导致分类性能下降。针对上述问题，文章提出了一种邻域k凸包分类方法，并通过引入距离度量学习和集成学习技术来提高算法对样本空间度量的鲁棒性。大量实验表明，文中提出的基于度量学习的邻域k凸包集成方法具有显著的分类性能优势。

邻域k凸包；度量学习；k近邻；集成学习

0 引 言

凸包分类技术将测试样本到各类凸包的距离作为相似性度量依据，继承了kNN［1－2］的无需训练直接测试、能处理多分类问题等优点，它不仅考虑了可见的训练样本，而且等价考虑了不可见的训练样本，从而使训练样本集从有限集变为无限集。从凸包构成的角度可以将凸包分类技术分为：① 整体凸包分类，如最近邻凸包分类［3］（Nearest Neighbor Convex Hull Classifier，简称NNCH）；② 局部凸包分类，如k局部凸包分类［4］（k－Local Convex Distance Nearest Neighbor Algorithm，简称CKNN）。最近邻凸包分类是将每类的所有训练样本构成一个整体类凸包，对于每个测试样本，计算它到每个类的整体凸包距离来进行分类。显然该方法对非线性分类效果较差，对噪声和类的数目比较敏感，时间复杂度高。文献［4］对比了kNN和SVM在局部上的分类边界，发现当决策边界的训练样本较少时，kNN容易产生过于复杂的分类边界，为解决该问题，提出使用k凸包距离来代替kNN中的样本距离，即k局部凸包分类，显著改善了分类性能，其基本思想是计算测试样本到每个类中最近的k个样本构成局部凸包距离来进行分类。

但CKNN方法存在以下缺点：① 对类的数目敏感；② 当样本呈现一类样本“包围”另一类样本的环状等特殊非线性结构时，易于出现分类错误。针对该问题，文献［5］给出了k子凸包分类方法（kSub－Convex－Hull Classifier，简称kCH），将计算凸包距离限制在一个k邻域内，有效地抑制了类数多和样本环状分布对分类性能的影响。但该方法在k邻域内常常会出现不同类的样本数严重不平衡，会导致决策边界的不光滑而降低分类性能。

本文提出了邻域k凸包分类方法，由于邻域k凸包分类方法仍然依赖于样本空间的距离度量和分布结构，本文通过同时引入距离度量学习和集成学习技术来提高学习过程对样本空间度量的鲁棒性，设计了PMMLE算法和EMMLE算法。在20个UCI数据集上的大量实验表明，本文提出的基于度量学习的邻域k凸包集成方法明显优于其他同类分类方法。

1 基于度量学习的邻域k凸包集成

1.1 邻域k凸包分类算法

针对CKNN和kCH存在的不足，本文融合几种方法的优点，提出了邻域k凸包分类方法。该方法首先寻找测试样本的k近邻，确定该邻域内存在的样本类别；然后计算测试样本到每个存在的类的k近邻的局部凸包距离进行分类。

定义1 设S⊂Rn，S＝｛d1，d2，…，dm｝为由Rn中m个点组成的集合，则定义S的凸包为：

定义2 对∀x∈Rn，S⊂Rn，则x到凸包S的距离［4］为：

定义3 设Nk（x）为测试样本x的k邻域，Si⊂Nk（x）为该邻域中存在的第i类的样本子集，（x）＝｛c1，c2，…，ck｝为x到第i类样本的k邻域集合，则x的k邻域内第i类的邻域k凸包为：

定义4 测试样本x的k邻域包含的类的标签集合记为L（x）＝｛L1，L2，…，Lp｝，（x）为x的k邻域中存在的第i类样本到x的最近的k邻域集合，则x的类别为：

邻域k凸包分类（Neighbork－Convex－Hull Classifier，简称为NCH）同时具有k凸包分类和k子凸包分类的优点，不仅克服了k凸包对噪声、类数多和样本环状分布敏感的不足，而且还克服了k子凸包分类邻域内不同类样本数的不平衡情况，提高了分类性能；同时k邻域内类数少而自适应变化，因而也降低了时间复杂度。

1.2 PMMLE 算法

研究表明，距离度量学习［6］能够有效改善基于距离的分类器的性能，集成学习技术［7－9］能够有效提高分类器的鲁棒性。为了进一步提升邻域k凸包分类方法的性能，本文在分类集成方法中融入度量学习技术，通过同时引入距离度量学习和集成学习技术来提高学习过程对样本空间度量的鲁棒性，从而提升邻域k凸包的分类性能，主要优点是将属性子集选择和距离计算选择统一起来，这样更能提高集成学习中个体分类器的质量。考虑一种简单的退化组合模式，首先进行度量学习，得到一个有效的度量空间，然后在该度量空间中用集成方法来提高邻域k凸包分类的性能，即平行式组合模式（Neighbork－Convex－Hull Classifier Based on Metric Learning and Ensemble Method with the Parallel Mode，简称PMMLE），具体算法如下：

1.3 EMMLE算法

分类集成中，为了在提高每个个体分类器性能的同时增加个体差异性，对每个个体分类器（NCH）分别先进行度量学习，得到相应的优化度量空间，然后在每个新的度量空间进行NCH分类，最后用Bagging［7］方法对所有NCH分类结果进行集成，简记为嵌入式组合模式（Neighbork－Sub－Convex－Hull Classifier Based on Metric Learning and Ensemble Method with the Embed Mode，简称EMMLE），其中个体分类器的生成和度量学习采用离线学习方式，算法如下：

2 实验及结果分析

2.1 实验数据

本文应用20个UCI数据集［10］来做比较实验，数据集的具体信息见表1所列。

表1 UCI实验数据集

在实验中，本文对每个数据集采用10次10倍交叉验证来比较每种算法的性能，将每个数据集的每个类随机划分为10等份，每次用其中的9份作训练集，1份作测试集；运行10次得到的分类错误率的平均值作为1次交叉验证的结果；反复执行这种交叉验证实验10次，用10次的平均分类错误率作为评价算法性能的指标，所有的比较实验都在相同的实验条件和相同的数据划分下进行。

2.2 对比算法

为了验证基于度量学习的邻域k凸包分类集成方法的性能，本文选择3种算法进行对比：① 最近邻 分 类 算 法，采 用kNN、CKNN［3］和kCH［5］算法和本文方法进行对比；② 基于度量学习的k近邻方法，采用LMNN［6］算法为代表与本文算法进行比较；③ 基于集成学习的k近邻方法，采用FASBIR［8］为代表与本文算法进行对比。在本文算法中度量学习用LMNN，集成学习用Bagging。

2.3 实验结果分析

2.3.1 邻域k凸包分类性能测试

邻域k凸包分类（NCH）是针对kNN、CKNN和kCH存在的不足进行了改进，由于NCH仅仅计算k邻域内存在的每个类的凸包距离，而不是计算到所有类的凸包距离，因而时间效率和kCH一样，优于CKNN。为了检验NCH在分类性能上的优越性，将 NCH 与kNN、CKNN和kCH 3种算法在20个UCI数据集进行比较实验，k值取7，实验结果如图1所示。

图1 kNN、CKNN、kCH和NCH实验结果对比

实验结果表明，NCH整体上均优于其他3种方法；NCH在14个数据集上优于CKNN，在6个数据集上和CKNN一样；NCH在15数据集上优于kCH，在5数据集上和kCH一样，说明NCH同时具备kCH和CKNN的优点，分类性能稳定。

2.3.2 基于度量学习的邻域k凸包集成测试

本文将PMMLE和EMMLE与CKNN、LMNN、FASBIR为代表的3种类型分类算法进行比较。在20个数据集上，k取11进行实验，集成学习中个体分类器规模为30，实验结果如图2所示。

图2 6种算法的实验结果对比

实验结果表明，PMMLE和EMMLE的分类性能整体都优于其他方法。PMMLE有17个数据集的平均分类错误率明显优于其他方法，EMMLE有18个数据集的平均分类错误率明显优于其他方法。

2.3.3 PMMLE和EMMLE中组成成分测试

PMMLE算法和EMMLE算法是同时引入距离度量学习和集成学习技术来提高学习过程对样本空间度量的鲁棒性，提升NCH的性能。为了探讨算法中3种成分分别所做的贡献，对PMMLE算法考察3个退化版本：①NCH换成kNN，其他按PMMLE算法不变，即PMMLE（kNN）；② 距离度量学习部分去掉，其他按PMMLE算法不变，即Bagging＋NCH；③ 集成部分去掉，其他按PMMLE算法不变，即LMNN＋NCH。 在 balance－scale、ionosphere、sonar、vehicle、digits及segmentation 6个数据集上做比较，k＝9，实验结果如图3所示。同理对EMMLE算法做比较，实验结果如图4所示。

实验结果表明，当把PMMLE和EMMLE中的NCH换成kNN后，性能大幅下降，说明组成成分中NCH的贡献较大；当去掉PMMLE和EMMLE中的度量学习后，性能也有较大下降，说明度量学习在算法组成中作用较大；当去掉PMMLE和EMMLE中的集成学习成分后，性能也经常下降，说明集成学习成分对算法性能也有重要贡献，但单独采用集成学习在性能提高上不 明显。

图3 PMMLE与其他3种退化版本的性能比较

图4 EMMLE与其他3种退化版本的性能比较

3 结束语

由于凸包分类方法在数据挖掘中有广泛的应用，提高其分类性能是一个研究热点。本文融合了kNN、CKNN和kCH的优点，设计了一种有效的邻域k凸包分类方法，解决了k凸包分类和k子凸包分类存在的不足。同时利用度量学习技术和集成技术来提高学习过程对样本空间度量的鲁棒性，提升邻域k凸包分类的性能。实验表明，基于度量学习的邻域k凸包集成方法优于CKNN、kCH和其他k近邻改进算法，对参数k变化的敏感性也较小；同时利用度量学习和集成学习2种技术要优于只利用一种技术时的分类性能。进一步应该研究在大数据集和高维数据情况下，利用度量学习和集成技术来提高NCH算法的性能，以及对于复杂边界、边界噪声数据较多时，提高NCH算法的分类性能。

［1］Tan S.An effective refinement strategy for KNN text classifier［J］.Expert Systems with Applications，2006，30：290－298.

［2］张 浩，谢 飞.基于语义关联的文本分类研究［J］.合肥工业大学学报：自然科学版，2011，34（10）：1501－1504.

［3］周晓飞，姜文瀚，杨静宇.l1范数最近邻凸包分类器在人脸识别中的应用［J］.计算机科学，2007，34（4）：234－235.

［4］Vincent P，Bengio Y.K－local hyperplane and convex distance nearest neighbor algorithms［C］／／Advances in Neural Information Processing Systems（NIPS），2001：985－992.

［5］牟廉明.k子凸包分类［J］.山西大学学报：自然科学版，2011，34（3）：374－380.

［6］Weinberger K，Blitzer J，Saul L.Distance metric learning for large margin nearest neighbor classification［C］／／Advances in Neural Information Processing Systems（NIPS），2006：1473－1480.

［7］Zhou Z H.Ensemble learning［M］.Berlin：Springer，2009：270－273.

［8］Zhou Z H，Yu Y.Ensembling local learners through multimodal perturbation ［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2005，35（4）：725－735.

［9］琚 旭，王 浩，姚宏亮.基于Boosting的支持向量机组合分类器［J］.合肥工业大学学报：自然科学版，2006，29（10）：1220－1222.

［10］Asuncion A.UCI machine learning repository［DB／OL］.［2012－03－01］.http：／／www.ics.uci.edu／～mlearn／MLRepository.html.

Neighbork－convex－hull ensemble method based on metric learning

MOU Lian－ming
（Key Laboratory of Numerical Simulation of Sichuan Province College，Neijiang Normal University，Neijiang 641100，China）

Thek－local convex distance nearest neighbor classifier（CKNN）corrects the decision boundary ofkNN when the amount of the training data is small，thus improving the performance ofkNN.Theksub－convex－hull classifier（kCH）weakens the sensitivity of CKNN to the number of classes and the ring structure of samples distribution，hence improves the classification performance.But this method is still sensitive to the distance metric.Moreover，different types of samples inknearest neighbors of a test instance are often seriously imbalanced，which leads to the decline of classification performance.In this paper，a neighbork－convex－hull classifier（NCH）is proposed to address these problems.The robustness of the neighbork－convex－hull classifier is improved by the techniques of metric learning and ensemble learning.Experimental results show that the proposed neighbork－convex－hull classifier ensemble method，which is based on metric learning，is significantly superior to some state－of－the－art nearest neighbor classifiers.

neighbork－convex－hull；metric learning；k－nearest neighbor；ensemble learning

TP391

A

1003－5060（2013）02－0171－05

10.3969／j.issn.1003－5060.2013.02.010

2012－07－11

国家自然科学基金资助项目（10872085）；四川省科技厅应用基础研究基金资助项目（07JY029－125）；四川省教育厅重大培育资助项目（07ZZ016）和内江师范学院自然科学重点基金资助项目 （12NJZ03）

牟廉明（1971－），男，重庆万州人，内江师范学院副教授.

（责任编辑 闫杏丽）