基于Hubness與類加權(quán)的k最近鄰分類算法

,

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

0 概述

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

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

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

1 相關(guān)工作

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

為了更好地解決不平衡問題,一系列Hubness相關(guān)的分類算法被提出[17-21]。與傳統(tǒng)k最近鄰算法不同的是,Hubness相關(guān)算法通過k最近鄰列表統(tǒng)計(jì)訓(xùn)練樣本的Nk,測(cè)試點(diǎn)通過其k最近鄰的Nk在每個(gè)類中的分布進(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)錯(cuò)誤匹配所帶來的影響,但是,樣本擁有較高的BNk(x)值時(shí),也可能擁有較高的GNk(x)值,降低樣本權(quán)重值時(shí)也會(huì)損害由GNk(x)所帶來的正確分類信息。

(1)

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

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

2 HWNN算法

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

2.1 基于Hubness的kNN分類

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

(2)

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

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

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

(3)

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

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

(4)

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

(5)

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

(6)

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

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

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

針對(duì)圖1中的情況,引入一個(gè)閾值參數(shù)θ作為經(jīng)驗(yàn)影響因子,本文將其設(shè)置為3。對(duì)于Nk(xi)<θ的數(shù)據(jù)樣本,利用樣本xi所屬類中所有樣本的k發(fā)生和在c類樣本上的k發(fā)生來計(jì)算Pk,c(xi),計(jì)算表達(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ù)目稀少,一個(gè)樣本成為少數(shù)類樣本k最近鄰的次數(shù)遠(yuǎn)小于其成為大數(shù)類樣本k最近鄰的次數(shù),因此根據(jù)式(8)計(jì)算Pk,c(xi)時(shí),其在少數(shù)類上的值遠(yuǎn)小于其在大數(shù)類上的值,進(jìn)而導(dǎo)致式(6)更偏向?qū)y(cè)試樣本預(yù)測(cè)為大數(shù)類。

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

(9)

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

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

(10)

(11)

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

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

2.3 HWNN算法流程

HWNN算法的具體描述如下:

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

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

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

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

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

2.計(jì)算D中每個(gè)樣本的k最近鄰;

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

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

/*測(cè)試階段*/

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

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

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

3.1 對(duì)比方法

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

3.2 性能評(píng)價(jià)指標(biāo)

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

(12)

(13)

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

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

為了得到一個(gè)可靠的性能評(píng)價(jià),從UCI數(shù)據(jù)庫中選擇16個(gè)類不平衡的數(shù)據(jù)集,該數(shù)據(jù)集具有不同的樣本大小、特征維度和類別數(shù)目,其中較高維(高于100維)的數(shù)據(jù)集為8個(gè)。按特征維度為100將這16個(gè)數(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)可以看出,對(duì)于一個(gè)類分布平衡的數(shù)據(jù)集,其相應(yīng)的IR為0。IR越高表示類分布越不平衡。

3.4 結(jié)果分析

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

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

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

4 結(jié)束語

針對(duì)高維不平衡類數(shù)據(jù)的學(xué)習(xí),本文提出一種基于Hubness和類加權(quán)的kNN分類算法HWNN。用樣本的k發(fā)生分布來緩解高維數(shù)據(jù)空間中產(chǎn)生的hubs對(duì)kNN分類的損害,通過使用類加權(quán)的方式提高少數(shù)類在樣本k發(fā)生中的比例以改進(jìn)其對(duì)少數(shù)類的預(yù)測(cè)精度。在16個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,無論是普通維數(shù)據(jù)還是高維數(shù)據(jù),相較于已有的幾種基于Hubness的kNN算法,HWNN算法具有較高的性能。由于HWNN算法采用的類加權(quán)是采用全局的方式對(duì)各類的權(quán)重進(jìn)行賦值,因此,下一步將考慮測(cè)試樣本所在的局部環(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的類別均衡的時(shí)間序列實(shí)例選擇算法[J].計(jì)算機(jī)應(yīng)用,2012,32(11):3034-3037.

[21] 張巧達(dá),何振峰.基于Hub的高維數(shù)據(jù)初始聚類中心的選擇策略[J].計(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.