基于Hubness與類加權的k最近鄰分類算法

,

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

0 概述

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

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

本文針對Hubness現象,結合類加權技術,提出一種能有效應用于高維不平衡數據分類的HWNN算法,并在實驗中將其與已有kNN分類算法進行性能比較。

1 相關工作

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

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

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

(1)

其中,λ為拉普拉斯平滑因子,通過實驗經驗選取,本文設置其值為2。

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

2 HWNN算法

針對實際應用中普遍存在的高維不平衡數據,本文提出的HWNN算法結合Hubness-aware和類加權的方式,分別應對由高維帶來的Hubness和由類不平衡帶來的預測傾斜問題。

2.1 基于Hubness的kNN分類

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

(2)

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

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

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

(3)

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

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

(4)

xt被預測為cj類的概率可表示為:

(5)

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

(6)

需要指出的是,傳統的kNN決策只能得到預測標簽值,若要取得在各個類上的預測概率,需要結合距離加權等方式。

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

圖1 k=1時的k最近鄰關系

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

(7)

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

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

(8)

2.2 類加權

在類不平衡數據中,由于少數類數目稀少,一個樣本成為少數類樣本k最近鄰的次數遠小于其成為大數類樣本k最近鄰的次數,因此根據式(8)計算Pk,c(xi)時,其在少數類上的值遠小于其在大數類上的值,進而導致式(6)更偏向將測試樣本預測為大數類。

為了糾正該傾斜預測,引入類權重如下:

(9)

其中,wc為c類的權重,nc、nmin分別為c類和最小類樣本的數目,α為一個縮放因子,值由經驗確定,本文將其值設置為常數2.5。

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

(10)

(11)

其中,y為樣本x的類標簽,wy為依據式(9)計算出的類權重因素。

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

2.3 HWNN算法流程

HWNN算法的具體描述如下:

算法基于Hubness和類加權的kNN分類算法

輸入訓練數據集D,近鄰參數k,閾值θ

輸出測試樣本的類標簽預測概率

/*預處理階段*/

1.統計D中每類樣本的數目nc,根據式(9)計算各類的權重;

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

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

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

/*測試階段*/

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

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

3 實驗結果與分析

3.1 對比方法

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

3.2 性能評價指標

在不平衡數據中,少數類通常代表領域的本質,錯誤預測少數類樣本的代價往往高于錯誤預測大數類樣本的代價,因此,傳統的預測精度并不適合作為不平衡數據學習性能的評價指標。本文采用文獻[23]的建議,使用MG[24]和MAUC[25]作為算法性能的評價指標。MG和MAUC的定義分別如下:

(12)

(13)

MG強調各類預測精度之間的平衡。假設算法在大數類上有較高的預測精度,在少數類上有較低的預測精度,最終會產生低MG值。MAUC是所有類進行成對比較形成的AUC值的平均,其不依賴于具體的決策閾值,是對算法綜合性能的最常用評價。此外,MG和MAUC作為不平衡學習領域廣泛使用的評價指標,一個顯著的優點是它們同時適應于二分類和多分類不平衡數據,且具有統一的表達形式。

3.3 實驗數據

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

表1 數據集基本信息

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

(14)

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

3.4 結果分析

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

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

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

4 結束語

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

[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].計算機應用,2012,32(11):3034-3037.

[21] 張巧達,何振峰.基于Hub的高維數據初始聚類中心的選擇策略[J].計算機系統應用,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.