,

(湖南大學(xué) 信息科學(xué)與工程學(xué)院,長沙 410082)

0 概述

隨著數(shù)據(jù)采集技術(shù)的發(fā)展和互聯(lián)網(wǎng)的深入,應(yīng)用領(lǐng)域中的數(shù)據(jù)越來越呈現(xiàn)高維化趨勢。相較于低維數(shù)據(jù),各種機器學(xué)習(xí)方法和任務(wù)在高維數(shù)據(jù)上會面臨嚴(yán)重的挑戰(zhàn),例如:數(shù)量眾多的特征屬性之間存在大量冗余和相關(guān)性,明顯違背貝葉斯建模的基本獨立性假設(shè)[1];維數(shù)增加所帶來的樣本間距離的集中化,減弱了各種距離指標(biāo)反映相似性差異的有效性,使得包括k最近鄰(k-Nearest Neighbor,kNN)分類和聚類等不能有效地應(yīng)用于高維數(shù)據(jù)[2]。這些在數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域由高維特征空間所帶來的各種困難與挑戰(zhàn),統(tǒng)稱為維數(shù)災(zāi)難。

文獻(xiàn)[3]探索維數(shù)災(zāi)難的一個新方向:Hubness。假設(shè)Nk(x)為數(shù)據(jù)集D中樣本x出現(xiàn)在其他樣本的k最近鄰列表中的次數(shù),Hubness現(xiàn)象指在高維數(shù)據(jù)空間中Nk(x)的分布呈現(xiàn)明顯的右偏態(tài),即一些樣本點,或非常頻繁地作為其他樣本的k最近鄰(hubs),或很少成為其他樣本的k最近鄰(anti-hubs)。在文獻(xiàn)[3]之后,一些Hubness-aware的kNN和聚類方法相繼被提出,都從Hubness這一全新的角度切入解決方法在應(yīng)對高維數(shù)據(jù)時的低效性問題。然而,上述方法都沒有考慮一個普遍存在的情形:在現(xiàn)實中,許多高維數(shù)據(jù)往往也是類不平衡的,如文本分類、生物醫(yī)療和圖像分類等。由于標(biāo)準(zhǔn)的機器學(xué)習(xí)方法通常以最小化訓(xùn)練錯誤為目標(biāo),少數(shù)類樣本的稀少使得從不平衡數(shù)據(jù)中學(xué)習(xí)的分類器往往忽略少數(shù)類的概念信息,從而趨向?qū)⑺形粗獦颖绢A(yù)測為大數(shù)類[4-5]。此外,已有方法對高維不平衡數(shù)據(jù)進(jìn)行處理時,一般先使用各種降維技術(shù)以減少數(shù)據(jù)維度,然后在降維后的數(shù)據(jù)上應(yīng)用類不平衡技術(shù)以糾正分類器的預(yù)測傾斜[6-7]。該做法的不足之處是其進(jìn)行降維時可能損失原始數(shù)據(jù)信息。

本文針對Hubness現(xiàn)象,結(jié)合類加權(quán)技術(shù),提出一種能有效應(yīng)用于高維不平衡數(shù)據(jù)分類的HWNN算法,并在實驗中將其與已有kNN分類算法進(jìn)行性能比較。

1 相關(guān)工作

近年來,不平衡問題在學(xué)術(shù)界和工業(yè)領(lǐng)域引起了廣泛關(guān)注,為了解決不平衡問題,許多新的算法被提出,這些算法可以分為2類:數(shù)據(jù)水平方法和算法水平方法。數(shù)據(jù)水平方法通過引入新的少數(shù)類樣本或移除一部分大數(shù)類樣本,以減輕原始數(shù)據(jù)的類不平衡分布,該方法的優(yōu)點是其通用性,即不依賴于任何具體的分類算法;缺點是對于具體的不平衡問題,其可能達(dá)不到滿意的效果。算法水平方法嘗試修改已有的標(biāo)準(zhǔn)機器學(xué)習(xí)算法,以得到更適應(yīng)于不平衡數(shù)據(jù)學(xué)習(xí)的歸納偏置。例如,在決策樹[8-9]中使用類不平衡不敏感的分裂準(zhǔn)則,修改葉節(jié)點標(biāo)簽的可能性估計;在SVM[10-12]中,賦予少數(shù)類樣本更高的懲罰因子,修改核函數(shù)以校正傾斜的類邊界。此外,為了處理不平衡數(shù)據(jù)的學(xué)習(xí)問題,許多基于基本kNN分類規(guī)則[13-14]的新型分類算法被提出,它們所采用的一個基本策略是向少數(shù)類中引入顯式的偏置,如樣本加權(quán)[15]和類加權(quán)[16]等。

為了更好地解決不平衡問題,一系列Hubness相關(guān)的分類算法被提出[17-21]。與傳統(tǒng)k最近鄰算法不同的是,Hubness相關(guān)算法通過k最近鄰列表統(tǒng)計訓(xùn)練樣本的Nk,測試點通過其k最近鄰的Nk在每個類中的分布進(jìn)行分類。與傳統(tǒng)kNN算法和權(quán)重kNN算法相比,Hubness相關(guān)算法可以有效提升分類精度。

HW-kNN[22]引入GNk(x)和BNk(x)分別表示Nk中與樣本x同類和異類的次數(shù),Nk(x)=GNk(x)+BNk(x),算法還為kNN列表引入權(quán)重系數(shù)e-(BNk(xi)-μBNk)/σBNk,其中,μBNk和σBNk分別為訓(xùn)練集樣本中BNk(x)的平均值和方差。算法通過降低BNk(x)較大樣本的權(quán)重,消除了樣本在分類中可能產(chǎn)生的負(fù)面影響。該算法雖然在一定程度上減少了由BNk(x)錯誤匹配所帶來的影響,但是,樣本擁有較高的BNk(x)值時,也可能擁有較高的GNk(x)值,降低樣本權(quán)重值時也會損害由GNk(x)所帶來的正確分類信息。

(1)

其中,λ為拉普拉斯平滑因子,通過實驗經(jīng)驗選取,本文設(shè)置其值為2。

通過聯(lián)合所有xi∈D(x)的概率求出樣本x所屬類概率分布。在高維數(shù)據(jù)下,相較于傳統(tǒng)的kNN和HW-kNN算法,NHBNN算法在精度上有較好的提升。然而,雖然在高維不平衡類數(shù)據(jù)下NHBNN算法總體分類精度較高,但其在少數(shù)類上分類精度卻較低。對于高維不平衡類數(shù)據(jù)而言,尤其是少數(shù)類,典型分類學(xué)習(xí)注重的是針對每一類的分類精度,而不是不區(qū)分類別的總體精度。

2 HWNN算法

針對實際應(yīng)用中普遍存在的高維不平衡數(shù)據(jù),本文提出的HWNN算法結(jié)合Hubness-aware和類加權(quán)的方式,分別應(yīng)對由高維帶來的Hubness和由類不平衡帶來的預(yù)測傾斜問題。

2.1 基于Hubness的kNN分類

最近鄰方法基于一個簡單的假設(shè),即鄰近的樣本點通常屬于相同的類。kNN分類算法利用該假設(shè),將一個未知樣本的類標(biāo)簽預(yù)測為它的kNN中出現(xiàn)次數(shù)最多的類別,即對于一個測試樣本xt,其kNN分類決策dck(xt)如下:

(2)

其中,m是類別的數(shù)目,E(yi,c)是一個指示函數(shù),若yi=c,c∈{c1,c2,…,cm},則E(yi,c)返回1;否則,返回0。

為了減少高維數(shù)據(jù)中由hubs所帶來的潛在負(fù)面影響,采用基于Hubness的策略,考察每個訓(xùn)練樣本的k發(fā)生中屬于各個類上的比例,以此作為其成為測試樣本的k最近鄰時對每個類的支持度。

假設(shè)xi為當(dāng)前訓(xùn)練樣本,Nk(xi)和Nk,c(xi)分別為其k發(fā)生和在c類樣本上的k發(fā)生,則xi作為c類樣本k最近鄰的概率為Pk,c(xi),其計算公式如下:

(3)

由式(3)可以看出,當(dāng)xi的k發(fā)生中作為c類樣本k最近鄰的比例較高時,表示xi的近鄰領(lǐng)域中會頻繁出現(xiàn)c類的樣本。因此,如果xi作為一個測試樣本的k最近鄰,則其對該測試樣本預(yù)測為c類有較高的支持度。

通過式(3)得出,測試樣本xi的k最近鄰對xt預(yù)測為c類的支持度和如下:

(4)

xt被預(yù)測為cj類的概率可表示為:

(5)

將式(5)代入式(2),得到考慮樣本k發(fā)生發(fā)布下的新kNN決策規(guī)則:

(6)

需要指出的是,傳統(tǒng)的kNN決策只能得到預(yù)測標(biāo)簽值,若要取得在各個類上的預(yù)測概率,需要結(jié)合距離加權(quán)等方式。

然而,運用式(3)對xi在c類樣本的k最近鄰中的概率進(jìn)行估計時,需要Nk(xi)具有足夠多的統(tǒng)計次數(shù),否則,通過頻率估計概率將缺乏可靠性。在高維數(shù)據(jù)空間中,hubs點擠占了大量的k最近鄰關(guān)系,同時使得一部分樣本(包括anti-hubs點)很少成為其他點的k最近鄰。圖1所示為最近鄰關(guān)系示意圖,其中A和D的高k發(fā)生使得B、E、C的Nk(x)均為0。

圖1 k=1時的k最近鄰關(guān)系

針對圖1中的情況,引入一個閾值參數(shù)θ作為經(jīng)驗影響因子,本文將其設(shè)置為3。對于Nk(xi)<θ的數(shù)據(jù)樣本,利用樣本xi所屬類中所有樣本的k發(fā)生和在c類樣本上的k發(fā)生來計算Pk,c(xi),計算表達(dá)式如下:

(7)

其中,yi表示樣本xi類標(biāo)簽,(x,y)∈(X,Y)|y=yi表示所有與xi同類的樣本。

綜合式(3)和式(7),Pk,c(xi)可表示如下:

(8)

2.2 類加權(quán)

在類不平衡數(shù)據(jù)中,由于少數(shù)類數(shù)目稀少,一個樣本成為少數(shù)類樣本k最近鄰的次數(shù)遠(yuǎn)小于其成為大數(shù)類樣本k最近鄰的次數(shù),因此根據(jù)式(8)計算Pk,c(xi)時,其在少數(shù)類上的值遠(yuǎn)小于其在大數(shù)類上的值,進(jìn)而導(dǎo)致式(6)更偏向?qū)y試樣本預(yù)測為大數(shù)類。

為了糾正該傾斜預(yù)測,引入類權(quán)重如下:

(9)

其中,wc為c類的權(quán)重,nc、nmin分別為c類和最小類樣本的數(shù)目,α為一個縮放因子,值由經(jīng)驗確定,本文將其值設(shè)置為常數(shù)2.5。

由式(9)可以看出,類樣本的數(shù)目越多,所獲得的類權(quán)重越小;反之,獲得的類權(quán)重越大。因此,本文將類權(quán)重加入至樣本的k發(fā)生統(tǒng)計中。令RN(xi,k)表示xi的k發(fā)生列表,對于樣本xi,基于類加權(quán)的Nk和Nk,c計算表達(dá)式如下:

(10)

(11)

其中,y為樣本x的類標(biāo)簽,wy為依據(jù)式(9)計算出的類權(quán)重因素。

可以看出,式(11)使用的加權(quán)方式將提升樣本在少數(shù)類上的k發(fā)生。

2.3 HWNN算法流程

HWNN算法的具體描述如下:

算法基于Hubness和類加權(quán)的kNN分類算法

輸入訓(xùn)練數(shù)據(jù)集D,近鄰參數(shù)k,閾值θ

輸出測試樣本的類標(biāo)簽預(yù)測概率

/*預(yù)處理階段*/

1.統(tǒng)計D中每類樣本的數(shù)目nc,根據(jù)式(9)計算各類的權(quán)重;

2.計算D中每個樣本的k最近鄰;

3.根據(jù)式(10)和式(11)統(tǒng)計D中每個樣本的k發(fā)生和其在各個類上的k發(fā)生;

4.根據(jù)樣本的k發(fā)生和θ大小,使用式(8)計算得到D中每個樣本對各類的支持度;

/*測試階段*/

5.找到測試樣本xt在D中的k最近鄰;

6.根據(jù)式(4)和式(5)依次得到xt屬于各類上的置信度、預(yù)測概率。根據(jù)式(6)得到xt的最終預(yù)測標(biāo)簽。

3 實驗結(jié)果與分析

3.1 對比方法

選用3種已有的k最近鄰分類方法:傳統(tǒng)的k最近鄰(kNN),基于Hubness的權(quán)重k最近鄰(WNN),基于Hubness的樸素貝葉斯最近鄰(NHBNN),與HWNN算法進(jìn)行比較。為了考察類加權(quán)和基于Hubness分別在HWNN應(yīng)對高維不平衡數(shù)據(jù)中所發(fā)揮的作用,引入加權(quán)的k最近鄰分類方法WNN(即一個k最近鄰的投票權(quán)重由式(9)決定)和無類加權(quán)的基于Hubness的k最近鄰分類方法HNN進(jìn)行實驗。

3.2 性能評價指標(biāo)

在不平衡數(shù)據(jù)中,少數(shù)類通常代表領(lǐng)域的本質(zhì),錯誤預(yù)測少數(shù)類樣本的代價往往高于錯誤預(yù)測大數(shù)類樣本的代價,因此,傳統(tǒng)的預(yù)測精度并不適合作為不平衡數(shù)據(jù)學(xué)習(xí)性能的評價指標(biāo)。本文采用文獻(xiàn)[23]的建議,使用MG[24]和MAUC[25]作為算法性能的評價指標(biāo)。MG和MAUC的定義分別如下:

(12)

(13)

MG強調(diào)各類預(yù)測精度之間的平衡。假設(shè)算法在大數(shù)類上有較高的預(yù)測精度,在少數(shù)類上有較低的預(yù)測精度,最終會產(chǎn)生低MG值。MAUC是所有類進(jìn)行成對比較形成的AUC值的平均,其不依賴于具體的決策閾值,是對算法綜合性能的最常用評價。此外,MG和MAUC作為不平衡學(xué)習(xí)領(lǐng)域廣泛使用的評價指標(biāo),一個顯著的優(yōu)點是它們同時適應(yīng)于二分類和多分類不平衡數(shù)據(jù),且具有統(tǒng)一的表達(dá)形式。

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

為了得到一個可靠的性能評價,從UCI數(shù)據(jù)庫中選擇16個類不平衡的數(shù)據(jù)集,該數(shù)據(jù)集具有不同的樣本大小、特征維度和類別數(shù)目,其中較高維(高于100維)的數(shù)據(jù)集為8個。按特征維度為100將這16個數(shù)據(jù)集劃分為2組,一組為特征維度低于100的普通數(shù)據(jù)集,另一組為特征維度高于100的高維數(shù)據(jù)集。表1總結(jié)了該2組數(shù)據(jù)集的特征。

表1 數(shù)據(jù)集基本信息

不平衡度IR用于衡量數(shù)據(jù)集的類不平衡程度。假設(shè)類依據(jù)樣本大小以降序排序,即如果i

(14)

從式(14)可以看出,對于一個類分布平衡的數(shù)據(jù)集,其相應(yīng)的IR為0。IR越高表示類分布越不平衡。

3.4 結(jié)果分析

為了使實驗結(jié)果更具客觀性,采用10折交叉驗證的方法,利用5種分類算法對訓(xùn)練集中的數(shù)據(jù)進(jìn)行分類學(xué)習(xí),并用測試集進(jìn)行測試,10次測試結(jié)果的平均值作為1次10折交叉驗證的結(jié)果,實驗數(shù)據(jù)如表2所示。其中,Average-low與Average-high分別為該算法在8個低維數(shù)據(jù)集和8個高維數(shù)據(jù)集上的平均MAUC值和平均MG值。

表2 不同分類算法的MAUC值和MG值

從表2中可以看出,在低維數(shù)據(jù)集上,本文HWNN算法的平均MAUC值和MG值均高于其他分類算法,這是因為HWNN算法引入了類加權(quán)因子,糾正了向大數(shù)類傾斜的現(xiàn)象,而其他算法忽略了不平衡因素對分類結(jié)果的影響,導(dǎo)致性能較差。此外,在高維數(shù)據(jù)集上,各分類算法的分類精度均有所下降,這是由高維數(shù)據(jù)特性所導(dǎo)致,但是本文HWNN算法仍能達(dá)到較高的平均MAUC值和平均MG值。相對于低維數(shù)據(jù)分類情況,HWNN算法在高維數(shù)據(jù)上分類精度的優(yōu)勢更明顯和突出,證明了該算法對高維不平衡數(shù)據(jù)具有較強的適應(yīng)性。

4 結(jié)束語

針對高維不平衡類數(shù)據(jù)的學(xué)習(xí),本文提出一種基于Hubness和類加權(quán)的kNN分類算法HWNN。用樣本的k發(fā)生分布來緩解高維數(shù)據(jù)空間中產(chǎn)生的hubs對kNN分類的損害,通過使用類加權(quán)的方式提高少數(shù)類在樣本k發(fā)生中的比例以改進(jìn)其對少數(shù)類的預(yù)測精度。在16個UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的實驗結(jié)果表明,無論是普通維數(shù)據(jù)還是高維數(shù)據(jù),相較于已有的幾種基于Hubness的kNN算法,HWNN算法具有較高的性能。由于HWNN算法采用的類加權(quán)是采用全局的方式對各類的權(quán)重進(jìn)行賦值,因此,下一步將考慮測試樣本所在的局部環(huán)境,使算法更適應(yīng)高維不平衡分類的特異性偏置。

[2] BISHOP C M.Pattern recognition and machine learning[M].Berlin,Germany:Springer,2006:461-462.

[3] HASTIE T,TIBSHIRANI R,FRIEDMAN J.The elements of statistical learning:data mining,inference and predic-tion[J].The Mathematical Intelligencer,2005,27(2):83-85.

[4] WEISS G M.Mining with rarity:a unifying frame-work[J].ACM SIGKDD Explorations Newsletter,2004,6(1):7-19.

[5] CHAWLA N V,JAPKOWICZ N,KOTCZ A.Editorial:special issue on learning from imbalanced data sets[J].ACM SIGKDD Explorations Newsletter,2004,6(1):1-6.

[6] LIN W J,CHEN J J.Class-imbalanced classifiers for high-dimensional data[J].Briefings in Bioinformatics,2013,14(1):13-26.

[7] YIN H,GAI K.An empirical study on preprocessing high-dimensional class-imbalanced data for classification[C]//Proceedings of International Conference on High Performance Computing and Communications.Washington D.C.,USA:IEEE Computer Society,2015:1314-1319.

[8] DIETTERICH T,KEARNS M,MANSOUR Y.Applying the weak learning framework to understand and improve C 4.5[EB/OL].[2017-03-02].http://www.doc88.com/p-9864143758186.html.

[9] CIESLAK D A,CHAWLA N V.Learning decision trees for unbalanced data[C]//Proceedings of European Conference on Machine Learning and Knowledge Disco-very in Databases.Berlin,Germany:Springer,2008:241-256.

[10] QUINLAN J R.Improved estimates for the accuracy of small disjuncts[J].Machine Learning,1991,6(1):93-98.

[11] LIN Y,LEE Y,WAHBA G.Support vector machines for classification in nonstandard situations[J].Machine Learning,2002,46(1):191-202.

[12] WU G,CHANG E Y.KBA:kernel boundary alignment considering imbalanced data distribution[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):786-795.

[13] ZHANG X,LI Y.A positive-based nearest neighbour algorithm for imbalanced classification[M]//PEI J,TSENG V S,CAO L B,et al.Advances in Knowledge Discovery and Data Mining.Berlin,Germany:Springer,2013:293-304.

[14] LI Y,ZHANG X.Improving k nearest neighbor with exemplar generalization for imbalanced classification[C]//Proceedings of Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Berlin,Germany:Springer,2011:321-332.

[15] TAN S.Neighbor-weighted k-nearest neighbor for unbalanced text corpus[J].Expert Systems with Applications,2005,28(4):667-671.

[16] DUBEY H,PUDI V.Class based weighted k-nearest neighbor over imbalance dataset[M]//PEI J,TSENG V S,CAO L B,et al.Advances in Knowledge Discovery and Data Mining.Berlin,Germany:Springer,2013:305-316.

[20] 翟婷婷,何振峰.基于Hubness的類別均衡的時間序列實例選擇算法[J].計算機應(yīng)用,2012,32(11):3034-3037.

[21] 張巧達(dá),何振峰.基于Hub的高維數(shù)據(jù)初始聚類中心的選擇策略[J].計算機系統(tǒng)應(yīng)用,2015,24(4):171-175.

[22] ZUO W,ZHANG D,WANG K.On kernel difference-weighted k-nearest neighbor classification[J].Pattern Analysis and Applications,2008,11(3):247-257.

[23] WANG S,YAO X.Multiclass imbalance problems:analysis and potential solutions[J].IEEE Transactions on Systems Manand Cybernetics,Part B,2012,42(4):1119-1130.

[24] SUN Y,KAMEL M S,WANG Y.Boosting for learning multiple classes with imbalanced class distribution[C]//Proceedings of International Conference on Data Mining.Washington D.C.,USA:IEEE Computer Society,2006:592-602.

[25] HAND D J,TILL R J.A simple generalisation of the area under the ROC curve for multiple class classification problems[J].Machine Learning,2001,45(2):171-186.