牟廉明

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

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

牟廉明

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

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

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

0 引 言

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

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

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

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

1.1 鄰域k凸包分類算法

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

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

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

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

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

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

1.2 PMMLE 算法

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

1.3 EMMLE算法

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

2 實驗及結(jié)果分析

2.1 實驗數(shù)據(jù)

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

表1 UCI實驗數(shù)據(jù)集

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

2.2 對比算法

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

2.3 實驗結(jié)果分析

2.3.1 鄰域k凸包分類性能測試

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

圖1 kNN、CKNN、kCH和NCH實驗結(jié)果對比

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

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

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

圖2 6種算法的實驗結(jié)果對比

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

2.3.3 PMMLE和EMMLE中組成成分測試

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

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

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

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

3 結(jié)束語

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

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

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

［3］周曉飛，姜文瀚，楊靜宇.l1范數(shù)最近鄰?fù)拱诸惼髟谌四樧R別中的應(yīng)用［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é)報：自然科學(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］.合肥工業(yè)大學(xué)學(xué)報：自然科學(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

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

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

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