牟廉明

（內(nèi)江師范學(xué)院 四川省高等學(xué)校數(shù)值仿真重點(diǎn)實(shí)驗(yàn)室，四川 內(nèi)江 641100）

基于度量學(xué)習(xí)的鄰域k凸包集成方法

牟廉明

（內(nèi)江師范學(xué)院 四川省高等學(xué)校數(shù)值仿真重點(diǎn)實(shí)驗(yàn)室，四川 內(nèi)江 641100）

k局部凸包分類方法通過(guò)改進(jìn)k近鄰算法在處理小樣本問(wèn)題時(shí)的決策邊界而顯著提高分類性能，k子凸包分類方法通過(guò)克服k凸包分類對(duì)類數(shù)和樣本環(huán)狀分布的敏感性而改善了分類性能。但是，該方法仍然對(duì)樣本距離度量方法敏感，并且在k鄰域內(nèi)不同類的樣本數(shù)經(jīng)常嚴(yán)重失衡，導(dǎo)致分類性能下降。針對(duì)上述問(wèn)題，文章提出了一種鄰域k凸包分類方法，并通過(guò)引入距離度量學(xué)習(xí)和集成學(xué)習(xí)技術(shù)來(lái)提高算法對(duì)樣本空間度量的魯棒性。大量實(shí)驗(yàn)表明，文中提出的基于度量學(xué)習(xí)的鄰域k凸包集成方法具有顯著的分類性能優(yōu)勢(shì)。

鄰域k凸包；度量學(xué)習(xí)；k近鄰；集成學(xué)習(xí)

0 引 言

凸包分類技術(shù)將測(cè)試樣本到各類凸包的距離作為相似性度量依據(jù)，繼承了kNN［1－2］的無(wú)需訓(xùn)練直接測(cè)試、能處理多分類問(wèn)題等優(yōu)點(diǎn)，它不僅考慮了可見(jiàn)的訓(xùn)練樣本，而且等價(jià)考慮了不可見(jiàn)的訓(xùn)練樣本，從而使訓(xùn)練樣本集從有限集變?yōu)闊o(wú)限集。從凸包構(gòu)成的角度可以將凸包分類技術(shù)分為：① 整體凸包分類，如最近鄰?fù)拱诸悾?］（Nearest Neighbor Convex Hull Classifier，簡(jiǎn)稱NNCH）；② 局部凸包分類，如k局部凸包分類［4］（k－Local Convex Distance Nearest Neighbor Algorithm，簡(jiǎn)稱CKNN）。最近鄰?fù)拱诸愂菍⒚款惖乃杏?xùn)練樣本構(gòu)成一個(gè)整體類凸包，對(duì)于每個(gè)測(cè)試樣本，計(jì)算它到每個(gè)類的整體凸包距離來(lái)進(jìn)行分類。顯然該方法對(duì)非線性分類效果較差，對(duì)噪聲和類的數(shù)目比較敏感，時(shí)間復(fù)雜度高。文獻(xiàn)［4］對(duì)比了kNN和SVM在局部上的分類邊界，發(fā)現(xiàn)當(dāng)決策邊界的訓(xùn)練樣本較少時(shí)，kNN容易產(chǎn)生過(guò)于復(fù)雜的分類邊界，為解決該問(wèn)題，提出使用k凸包距離來(lái)代替kNN中的樣本距離，即k局部凸包分類，顯著改善了分類性能，其基本思想是計(jì)算測(cè)試樣本到每個(gè)類中最近的k個(gè)樣本構(gòu)成局部凸包距離來(lái)進(jìn)行分類。

但CKNN方法存在以下缺點(diǎn)：① 對(duì)類的數(shù)目敏感；② 當(dāng)樣本呈現(xiàn)一類樣本“包圍”另一類樣本的環(huán)狀等特殊非線性結(jié)構(gòu)時(shí)，易于出現(xiàn)分類錯(cuò)誤。針對(duì)該問(wèn)題，文獻(xiàn)［5］給出了k子凸包分類方法（kSub－Convex－Hull Classifier，簡(jiǎn)稱kCH），將計(jì)算凸包距離限制在一個(gè)k鄰域內(nèi)，有效地抑制了類數(shù)多和樣本環(huán)狀分布對(duì)分類性能的影響。但該方法在k鄰域內(nèi)常常會(huì)出現(xiàn)不同類的樣本數(shù)嚴(yán)重不平衡，會(huì)導(dǎo)致決策邊界的不光滑而降低分類性能。

本文提出了鄰域k凸包分類方法，由于鄰域k凸包分類方法仍然依賴于樣本空間的距離度量和分布結(jié)構(gòu)，本文通過(guò)同時(shí)引入距離度量學(xué)習(xí)和集成學(xué)習(xí)技術(shù)來(lái)提高學(xué)習(xí)過(guò)程對(duì)樣本空間度量的魯棒性，設(shè)計(jì)了PMMLE算法和EMMLE算法。在20個(gè)UCI數(shù)據(jù)集上的大量實(shí)驗(yàn)表明，本文提出的基于度量學(xué)習(xí)的鄰域k凸包集成方法明顯優(yōu)于其他同類分類方法。

1 基于度量學(xué)習(xí)的鄰域k凸包集成

1.1 鄰域k凸包分類算法

針對(duì)CKNN和kCH存在的不足，本文融合幾種方法的優(yōu)點(diǎn)，提出了鄰域k凸包分類方法。該方法首先尋找測(cè)試樣本的k近鄰，確定該鄰域內(nèi)存在的樣本類別；然后計(jì)算測(cè)試樣本到每個(gè)存在的類的k近鄰的局部凸包距離進(jìn)行分類。

定義1 設(shè)S?Rn，S＝｛d1，d2，…，dm｝為由Rn中m個(gè)點(diǎn)組成的集合，則定義S的凸包為：

定義2 對(duì)?x∈Rn，S?Rn，則x到凸包S的距離［4］為：

定義3 設(shè)Nk（x）為測(cè)試樣本x的k鄰域，Si?Nk（x）為該鄰域中存在的第i類的樣本子集，（x）＝｛c1，c2，…，ck｝為x到第i類樣本的k鄰域集合，則x的k鄰域內(nèi)第i類的鄰域k凸包為：

定義4 測(cè)試樣本x的k鄰域包含的類的標(biāo)簽集合記為L(zhǎng)（x）＝｛L1，L2，…，Lp｝，（x）為x的k鄰域中存在的第i類樣本到x的最近的k鄰域集合，則x的類別為：

鄰域k凸包分類（Neighbork－Convex－Hull Classifier，簡(jiǎn)稱為NCH）同時(shí)具有k凸包分類和k子凸包分類的優(yōu)點(diǎn)，不僅克服了k凸包對(duì)噪聲、類數(shù)多和樣本環(huán)狀分布敏感的不足，而且還克服了k子凸包分類鄰域內(nèi)不同類樣本數(shù)的不平衡情況，提高了分類性能；同時(shí)k鄰域內(nèi)類數(shù)少而自適應(yīng)變化，因而也降低了時(shí)間復(fù)雜度。

1.2 PMMLE 算法

研究表明，距離度量學(xué)習(xí)［6］能夠有效改善基于距離的分類器的性能，集成學(xué)習(xí)技術(shù)［7－9］能夠有效提高分類器的魯棒性。為了進(jìn)一步提升鄰域k凸包分類方法的性能，本文在分類集成方法中融入度量學(xué)習(xí)技術(shù)，通過(guò)同時(shí)引入距離度量學(xué)習(xí)和集成學(xué)習(xí)技術(shù)來(lái)提高學(xué)習(xí)過(guò)程對(duì)樣本空間度量的魯棒性，從而提升鄰域k凸包的分類性能，主要優(yōu)點(diǎn)是將屬性子集選擇和距離計(jì)算選擇統(tǒng)一起來(lái)，這樣更能提高集成學(xué)習(xí)中個(gè)體分類器的質(zhì)量。考慮一種簡(jiǎn)單的退化組合模式，首先進(jìn)行度量學(xué)習(xí)，得到一個(gè)有效的度量空間，然后在該度量空間中用集成方法來(lái)提高鄰域k凸包分類的性能，即平行式組合模式（Neighbork－Convex－Hull Classifier Based on Metric Learning and Ensemble Method with the Parallel Mode，簡(jiǎn)稱PMMLE），具體算法如下：

1.3 EMMLE算法

分類集成中，為了在提高每個(gè)個(gè)體分類器性能的同時(shí)增加個(gè)體差異性，對(duì)每個(gè)個(gè)體分類器（NCH）分別先進(jìn)行度量學(xué)習(xí)，得到相應(yīng)的優(yōu)化度量空間，然后在每個(gè)新的度量空間進(jìn)行NCH分類，最后用Bagging［7］方法對(duì)所有NCH分類結(jié)果進(jìn)行集成，簡(jiǎn)記為嵌入式組合模式（Neighbork－Sub－Convex－Hull Classifier Based on Metric Learning and Ensemble Method with the Embed Mode，簡(jiǎn)稱EMMLE），其中個(gè)體分類器的生成和度量學(xué)習(xí)采用離線學(xué)習(xí)方式，算法如下：

2 實(shí)驗(yàn)及結(jié)果分析

2.1 實(shí)驗(yàn)數(shù)據(jù)

本文應(yīng)用20個(gè)UCI數(shù)據(jù)集［10］來(lái)做比較實(shí)驗(yàn)，數(shù)據(jù)集的具體信息見(jiàn)表1所列。

表1 UCI實(shí)驗(yàn)數(shù)據(jù)集

在實(shí)驗(yàn)中，本文對(duì)每個(gè)數(shù)據(jù)集采用10次10倍交叉驗(yàn)證來(lái)比較每種算法的性能，將每個(gè)數(shù)據(jù)集的每個(gè)類隨機(jī)劃分為10等份，每次用其中的9份作訓(xùn)練集，1份作測(cè)試集；運(yùn)行10次得到的分類錯(cuò)誤率的平均值作為1次交叉驗(yàn)證的結(jié)果；反復(fù)執(zhí)行這種交叉驗(yàn)證實(shí)驗(yàn)10次，用10次的平均分類錯(cuò)誤率作為評(píng)價(jià)算法性能的指標(biāo)，所有的比較實(shí)驗(yàn)都在相同的實(shí)驗(yàn)條件和相同的數(shù)據(jù)劃分下進(jìn)行。

2.2 對(duì)比算法

為了驗(yàn)證基于度量學(xué)習(xí)的鄰域k凸包分類集成方法的性能，本文選擇3種算法進(jìn)行對(duì)比：① 最近鄰 分 類 算 法，采 用kNN、CKNN［3］和kCH［5］算法和本文方法進(jìn)行對(duì)比；② 基于度量學(xué)習(xí)的k近鄰方法，采用LMNN［6］算法為代表與本文算法進(jìn)行比較；③ 基于集成學(xué)習(xí)的k近鄰方法，采用FASBIR［8］為代表與本文算法進(jìn)行對(duì)比。在本文算法中度量學(xué)習(xí)用LMNN，集成學(xué)習(xí)用Bagging。

2.3 實(shí)驗(yàn)結(jié)果分析

2.3.1 鄰域k凸包分類性能測(cè)試

鄰域k凸包分類（NCH）是針對(duì)kNN、CKNN和kCH存在的不足進(jìn)行了改進(jìn)，由于NCH僅僅計(jì)算k鄰域內(nèi)存在的每個(gè)類的凸包距離，而不是計(jì)算到所有類的凸包距離，因而時(shí)間效率和kCH一樣，優(yōu)于CKNN。為了檢驗(yàn)NCH在分類性能上的優(yōu)越性，將 NCH 與kNN、CKNN和kCH 3種算法在20個(gè)UCI數(shù)據(jù)集進(jìn)行比較實(shí)驗(yàn)，k值取7，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 kNN、CKNN、kCH和NCH實(shí)驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)結(jié)果表明，NCH整體上均優(yōu)于其他3種方法；NCH在14個(gè)數(shù)據(jù)集上優(yōu)于CKNN，在6個(gè)數(shù)據(jù)集上和CKNN一樣；NCH在15數(shù)據(jù)集上優(yōu)于kCH，在5數(shù)據(jù)集上和kCH一樣，說(shuō)明NCH同時(shí)具備kCH和CKNN的優(yōu)點(diǎn)，分類性能穩(wěn)定。

2.3.2 基于度量學(xué)習(xí)的鄰域k凸包集成測(cè)試

本文將PMMLE和EMMLE與CKNN、LMNN、FASBIR為代表的3種類型分類算法進(jìn)行比較。在20個(gè)數(shù)據(jù)集上，k取11進(jìn)行實(shí)驗(yàn)，集成學(xué)習(xí)中個(gè)體分類器規(guī)模為30，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 6種算法的實(shí)驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)結(jié)果表明，PMMLE和EMMLE的分類性能整體都優(yōu)于其他方法。PMMLE有17個(gè)數(shù)據(jù)集的平均分類錯(cuò)誤率明顯優(yōu)于其他方法，EMMLE有18個(gè)數(shù)據(jù)集的平均分類錯(cuò)誤率明顯優(yōu)于其他方法。

2.3.3 PMMLE和EMMLE中組成成分測(cè)試

PMMLE算法和EMMLE算法是同時(shí)引入距離度量學(xué)習(xí)和集成學(xué)習(xí)技術(shù)來(lái)提高學(xué)習(xí)過(guò)程對(duì)樣本空間度量的魯棒性，提升NCH的性能。為了探討算法中3種成分分別所做的貢獻(xiàn)，對(duì)PMMLE算法考察3個(gè)退化版本：①NCH換成kNN，其他按PMMLE算法不變，即PMMLE（kNN）；② 距離度量學(xué)習(xí)部分去掉，其他按PMMLE算法不變，即Bagging＋NCH；③ 集成部分去掉，其他按PMMLE算法不變，即LMNN＋NCH。 在 balance－scale、ionosphere、sonar、vehicle、digits及segmentation 6個(gè)數(shù)據(jù)集上做比較，k＝9，實(shí)驗(yàn)結(jié)果如圖3所示。同理對(duì)EMMLE算法做比較，實(shí)驗(yàn)結(jié)果如圖4所示。

實(shí)驗(yàn)結(jié)果表明，當(dāng)把PMMLE和EMMLE中的NCH換成kNN后，性能大幅下降，說(shuō)明組成成分中NCH的貢獻(xiàn)較大；當(dāng)去掉PMMLE和EMMLE中的度量學(xué)習(xí)后，性能也有較大下降，說(shuō)明度量學(xué)習(xí)在算法組成中作用較大；當(dāng)去掉PMMLE和EMMLE中的集成學(xué)習(xí)成分后，性能也經(jīng)常下降，說(shuō)明集成學(xué)習(xí)成分對(duì)算法性能也有重要貢獻(xiàn)，但單獨(dú)采用集成學(xué)習(xí)在性能提高上不 明顯。

圖3 PMMLE與其他3種退化版本的性能比較

圖4 EMMLE與其他3種退化版本的性能比較

3 結(jié)束語(yǔ)

由于凸包分類方法在數(shù)據(jù)挖掘中有廣泛的應(yīng)用，提高其分類性能是一個(gè)研究熱點(diǎn)。本文融合了kNN、CKNN和kCH的優(yōu)點(diǎn)，設(shè)計(jì)了一種有效的鄰域k凸包分類方法，解決了k凸包分類和k子凸包分類存在的不足。同時(shí)利用度量學(xué)習(xí)技術(shù)和集成技術(shù)來(lái)提高學(xué)習(xí)過(guò)程對(duì)樣本空間度量的魯棒性，提升鄰域k凸包分類的性能。實(shí)驗(yàn)表明，基于度量學(xué)習(xí)的鄰域k凸包集成方法優(yōu)于CKNN、kCH和其他k近鄰改進(jìn)算法，對(duì)參數(shù)k變化的敏感性也較??；同時(shí)利用度量學(xué)習(xí)和集成學(xué)習(xí)2種技術(shù)要優(yōu)于只利用一種技術(shù)時(shí)的分類性能。進(jìn)一步應(yīng)該研究在大數(shù)據(jù)集和高維數(shù)據(jù)情況下，利用度量學(xué)習(xí)和集成技術(shù)來(lái)提高NCH算法的性能，以及對(duì)于復(fù)雜邊界、邊界噪聲數(shù)據(jù)較多時(shí)，提高NCH算法的分類性能。

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

［2］張 浩，謝 飛.基于語(yǔ)義關(guān)聯(lián)的文本分類研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（10）：1501－1504.

［3］周曉飛，姜文瀚，楊靜宇.l1范數(shù)最近鄰?fù)拱诸惼髟谌四樧R(shí)別中的應(yīng)用［J］.計(jì)算機(jī)科學(xué)，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］.山西大學(xué)學(xué)報(bào)：自然科學(xué)版，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ī)組合分類器［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，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－h(huán)ull 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－h(huán)ull 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－h(huán)ull classifier（NCH）is proposed to address these problems.The robustness of the neighbork－convex－h(huán)ull classifier is improved by the techniques of metric learning and ensemble learning.Experimental results show that the proposed neighbork－convex－h(huán)ull classifier ensemble method，which is based on metric learning，is significantly superior to some state－of－the－art nearest neighbor classifiers.

neighbork－convex－h(huán)ull；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

國(guó)家自然科學(xué)基金資助項(xiàng)目（10872085）；四川省科技廳應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目（07JY029－125）；四川省教育廳重大培育資助項(xiàng)目（07ZZ016）和內(nèi)江師范學(xué)院自然科學(xué)重點(diǎn)基金資助項(xiàng)目 （12NJZ03）

牟廉明（1971－），男，重慶萬(wàn)州人，內(nèi)江師范學(xué)院副教授.

（責(zé)任編輯 閆杏麗）