基于互鄰信息的樹(shù)型近鄰分類方法

尹 濤,胡新平,鞠恒榮,黃嘉爽,丁衛(wèi)平

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 216002)

作為一種經(jīng)典的分類方法,k近鄰(k-nearest neighbor,kNN)分類方法被廣泛應(yīng)用于機(jī)器學(xué)習(xí),模式識(shí)別和信息檢索等領(lǐng)域。因?yàn)樗惴▽?shí)現(xiàn)簡(jiǎn)單,分類性能較好,目前k近鄰分類算法主要應(yīng)用于分類和回歸問(wèn)題[1-4]。例如,趙晉陵等[5]將高光譜圖像空間信息轉(zhuǎn)化為特征向量,通過(guò)k近鄰分類器提高圖像的分類性能。Han等[6]將k近鄰與遺傳算法(Genetic algorithm,GA)相結(jié)合,用于類星體的光度紅移估計(jì)。張?chǎng)┏萚7]優(yōu)化k近鄰分類中的歐式距離,構(gòu)建Spearman-k近鄰分類地鐵深基坑地連墻變形的預(yù)測(cè)模型,提高預(yù)測(cè)精度。

另一方面,傳統(tǒng)k近鄰分類算法是一種單向判別方法。但該方法僅適用于數(shù)據(jù)均勻分布的場(chǎng)景。然而,在實(shí)際應(yīng)用中,數(shù)據(jù)的分布往往是有差異的。在此情況下,對(duì)于測(cè)試樣本k近鄰中的樣本而言,該測(cè)試樣本并不一定被其認(rèn)定為最近的k個(gè)樣本之一[23]。kNN規(guī)則中單向判別策略在一定程度上導(dǎo)致最近鄰樣本中存在噪聲數(shù)據(jù),降低了k近鄰分類算法的性能。k值代表樣本輻射范圍的大小,假設(shè)未分類樣本x1的k值為3,樣本x2,x3,x4都在樣本x1的鄰近區(qū)域中。然而對(duì)于樣本x2,未分類樣本x1不存在于樣本x2的鄰近區(qū)域。x2是未分類樣本x1的k近鄰樣本,x1卻不是x2的k近鄰樣本。因此樣本x1和x2的關(guān)系是單向的,這種聯(lián)系缺乏可靠性,導(dǎo)致無(wú)關(guān)數(shù)據(jù)x2干擾分類結(jié)果。為了解決這個(gè)問(wèn)題,Denoeux等[23-24]將D-S證據(jù)理論應(yīng)用于k近鄰分類,根據(jù)k個(gè)鄰近樣本證據(jù)信息預(yù)測(cè)樣本類別。Pan等[25]提出了一種基于雙邊模式的k近鄰分類方法。這種雙邊模式下的k近鄰方法通過(guò)擴(kuò)大鄰域范圍,提升分類準(zhǔn)確率。但在一些情況下,同樣會(huì)囊括部分噪聲數(shù)據(jù),造成分類性能的下降。

為了解決上述問(wèn)題,本文借鑒前人的工作,提出了基于三階段的k近鄰分類方法。首先,在第一階段通過(guò)LASSO模型獲取每個(gè)樣本的最優(yōu)k值,構(gòu)造kTree模型,提升待分類樣本搜索最優(yōu)k值的速度。其次,在第二階段,采用雙向策略,排除噪聲數(shù)據(jù)的干擾,確定待分類樣本的近鄰空間。最后,采用投票策略完成分類任務(wù)。

1 基礎(chǔ)知識(shí)介紹

k近鄰分類的主要思想：一個(gè)樣本與其鄰近區(qū)域中的k個(gè)樣本相似度最高,假設(shè)這k個(gè)樣本中的多數(shù)數(shù)據(jù)屬于某一個(gè)類別,則該樣本也屬于此類別。一般地,決策信息系統(tǒng)可定義為S=〈U,AT∪D〉,其中U代表所有樣本的集合。AT為條件屬性集,D為決策屬性集合。依據(jù)決策信息系統(tǒng),可定義樣本的k個(gè)鄰居如下所示：

(1)

式中：d(xi,xj)為樣本xi與樣本xj的距離函數(shù),且滿足如下性質(zhì)：

(1)d(xi,xj)≥0;

(2)d(xi,xj)=0,如果xi=xj;

(3)d(xi,xj)=d(xj,xi);

歐氏距離是一種機(jī)器學(xué)習(xí)中常用的距離計(jì)算方法,對(duì)于樣本xi與樣本xj之間的歐氏距離函數(shù)可定義為

(2)

根據(jù)歐氏距離,樣本的k個(gè)最近鄰居樣本可以被計(jì)算獲得?；卩徑鼧颖镜念悇e標(biāo)簽,可定義k近鄰分類規(guī)則如下所示。

定義2在決策信息系統(tǒng)中,?x∈U,樣本xi的k個(gè)最近鄰居表示為NK(xi)。w1,w2,…,wm為基于決策屬性D的m個(gè)類別標(biāo)簽。NK(xi)對(duì)應(yīng)的樣本標(biāo)簽可表示為

(3)

根據(jù)少數(shù)服從多數(shù)投票原則,樣本x的類別標(biāo)簽wx可定義為

(4)

式中：I(x)為指示函數(shù),x為真時(shí)取值為1,否則取值為0。k近鄰分類算法主要內(nèi)容如下所示。

算法1k近鄰分類算法

輸入：訓(xùn)練樣本集(X1,X2,…,Xn),訓(xùn)練樣本的類別標(biāo)簽(C1,C2,…,Cn),測(cè)試樣本Y,測(cè)試樣本的k值。

輸出：測(cè)試樣本的預(yù)測(cè)標(biāo)簽L。

①計(jì)算測(cè)試樣本Y與訓(xùn)練樣本集(X1,X2,…,Xn)之間的距離(D1,D2,…,Dn);

②根據(jù)距離(D1,D2,…,Dn)的遞增關(guān)系完成排序;

③選取距離最小的k個(gè)樣本(X1,X2,…,Xk)以及對(duì)應(yīng)的類別標(biāo)簽(C1,C2,…,Ck);

④計(jì)算k個(gè)樣本所屬類別的出現(xiàn)頻率;

⑤返回k個(gè)樣本出現(xiàn)頻率最高的類別作為測(cè)試樣本Y的預(yù)測(cè)標(biāo)簽L。

算法1的時(shí)間復(fù)雜度為O(n),具有簡(jiǎn)單高效的優(yōu)點(diǎn)。

2 主要方法

2.1 k值獲取

在k近鄰分類器中,k值的選擇影響分類性能優(yōu)劣。在眾多研究中,k值的選擇一般基于樣本的總個(gè)數(shù),往往忽略樣本之間的聯(lián)系。對(duì)于k近鄰分類算法,距離更近的樣本被認(rèn)為聯(lián)系更加緊密。所以通過(guò)距離尋找最近鄰樣本,同樣是尋找關(guān)系更加緊密的樣本,因此與測(cè)試樣本關(guān)系緊密的樣本數(shù)量是k值的直觀體現(xiàn)。在本文中,筆者鑒于Zhang等的kTree模型,采用LASSO模型[20-22]刻畫(huà)樣本之間的緊密程度。首先,應(yīng)用留一法將一個(gè)訓(xùn)練樣本單獨(dú)列出,通過(guò)LASSO模型與其他訓(xùn)練樣本重構(gòu)此獨(dú)立樣本,得到獨(dú)立樣本的重構(gòu)權(quán)重向量。以此類推,依據(jù)整個(gè)訓(xùn)練樣本的重構(gòu)權(quán)重向量,組成重構(gòu)權(quán)重矩陣。根據(jù)權(quán)重矩陣W與相關(guān)性閾值δ,可以獲得與樣本相關(guān)性較高的樣本數(shù)量,即為該樣本的k值。LASSO模型[20-22]定義如下所示：

定義3X為訓(xùn)練樣本,Y為測(cè)試樣本,W為訓(xùn)練樣本重構(gòu)權(quán)重矩陣。通過(guò)訓(xùn)練樣本重構(gòu)測(cè)試樣本的目標(biāo)函數(shù)如下所示

(5)

在這個(gè)例子中,訓(xùn)練樣本的個(gè)數(shù)為5,權(quán)重矩陣W∈R4×5,相關(guān)性閾值為0.1。權(quán)重矩陣W的第一列數(shù)據(jù)顯示第一個(gè)訓(xùn)練樣本與其他訓(xùn)練樣本的相關(guān)性大小。根據(jù)相關(guān)性閾值,得到第一個(gè)訓(xùn)練樣本的k值為3,第二個(gè)訓(xùn)練樣本的k值為3,以此類推,可以獲得所有樣本的k值。

2.2 kTree模型的構(gòu)建

在獲得樣本的有效k值之后,通過(guò)這些k值,構(gòu)造kTree的學(xué)習(xí)模型,學(xué)習(xí)測(cè)試樣本的有效k值。由上文可知,訓(xùn)練樣本的有效k值通過(guò)LASSO模型獲取。在本文中,采用留一法,獲得訓(xùn)練樣本中其它樣本對(duì)該樣本的緊密程度。以此類推,整個(gè)訓(xùn)練樣本的k值可以計(jì)算得到。筆者鑒于Zhang等的kTree模型,根據(jù)訓(xùn)練樣本和對(duì)應(yīng)的k值,以k值為葉子節(jié)點(diǎn),構(gòu)建kTree[19]。kTree的每一個(gè)葉子節(jié)點(diǎn)都存在一個(gè)有效k值。在測(cè)試階段,從kTree的根節(jié)點(diǎn)到葉子節(jié)點(diǎn),遍歷整個(gè)樹(shù),賦予測(cè)試樣本最優(yōu)k值。通過(guò)kTree學(xué)習(xí)獲取的k值,有效的體現(xiàn)自身的輻射范圍。kTree的流程如圖1所示。

圖1 kTree的構(gòu)建

kTree算法的時(shí)間消耗主要體現(xiàn)在訓(xùn)練樣本的k值獲取。通過(guò)LASSO模型得到訓(xùn)練樣本之間的緊密程度,其主要時(shí)間復(fù)雜度為O(n2),kTree的構(gòu)建主要的時(shí)間消耗為O(logn)?？偟膩?lái)說(shuō),算法的時(shí)間復(fù)雜度為O(n2)。

2.3 MIkTree模型的構(gòu)建

k近鄰分類算法主要依據(jù)與之距離最近的k個(gè)樣本,預(yù)測(cè)樣本的類別。然而,同樣存在一些問(wèn)題。在k近鄰分類過(guò)程中,假設(shè)一個(gè)樣本a被選為樣本b的k個(gè)最近鄰之一,表示樣本a在樣本b的鄰近范圍之內(nèi)。但并不意味著樣本b一定存在于樣本a的鄰近范圍之內(nèi),意味著樣本a可能成為樣本b的無(wú)關(guān)數(shù)據(jù)。同時(shí),引出一個(gè)常見(jiàn)的問(wèn)題,k近鄰分類的k個(gè)樣本的選擇往往只考慮樣本之間單向的聯(lián)系,而雙方之間聯(lián)系沒(méi)有被考慮,這也會(huì)導(dǎo)致樣本預(yù)測(cè)準(zhǔn)確率的下降。

為了解決這個(gè)問(wèn)題,Pan等[25]提出了一種基于雙邊的一般最近鄰算法。訓(xùn)練樣本與測(cè)試樣本的共同鄰域信息被稱為互鄰信息[25]。假設(shè)訓(xùn)練樣本x1屬于測(cè)試樣本y1的k個(gè)最近鄰之一,或者測(cè)試樣本y1屬于訓(xùn)練樣本x1的k個(gè)最近鄰之一,那么x1為測(cè)試樣本y1的k個(gè)一般最近鄰之一。為了提高k近鄰分類的分類性能,本文提出了一種基于雙向策略的k近鄰分類算法。

本文提出的MIkTree分類方法利用訓(xùn)練樣本與測(cè)試樣本互鄰信息的重疊區(qū)域判斷樣本是否為測(cè)試樣本的可靠最近鄰樣本。對(duì)于待分類樣本x,如果樣本y滿足式(6),則可被視為可靠樣本。樣本x,y之間的關(guān)系是可靠的,可以有力地支持樣本的正確分類。

x∈NKy(y)∩y∈NKx(x)

(6)

對(duì)于這些可靠的樣本,通過(guò)最大投票策略,可以預(yù)測(cè)出樣本的類別,提升了樣本的分類性能。具體的算法步驟如算法2所示。

算法2MIkTree分類算法

輸入：訓(xùn)練樣本集(X1,X2,…,Xn),訓(xùn)練樣本的類別標(biāo)簽(C1,C2,…,Cn),測(cè)試樣本Y。

輸出：測(cè)試樣本的預(yù)測(cè)標(biāo)簽L。

①根據(jù)LASSO模型與kTree模型分別獲得訓(xùn)練樣本集和測(cè)試樣本Y對(duì)應(yīng)的k值;

②將測(cè)試樣本Y加入訓(xùn)練樣本集(X1,X2,…,Xn)中,新的訓(xùn)練集表示為T(mén)S′;

③選取距離最小的k個(gè)樣本(X1,X2,…,Xk)以及對(duì)應(yīng)的類別標(biāo)簽(C1,C2,…,Ck);

④根據(jù)式(1),得到TS′中每個(gè)樣本的k個(gè)最近鄰居NK(x);

⑤在訓(xùn)練集TS′,對(duì)于任意樣本Xi,Y(1≤i≤n)如果滿足式(6),則將Xi加入到集合MIkTree(Y);

⑥返回集合MIkTree(Y)中出現(xiàn)頻率最高的類別作為測(cè)試樣本Y的預(yù)測(cè)標(biāo)簽L。

算法2的時(shí)間復(fù)雜度主要體現(xiàn)在步驟1中對(duì)于樣本k值的獲取,主要的時(shí)間消耗為O(n2),步驟2的時(shí)間復(fù)雜度為O(n)。所以,算法2的時(shí)間復(fù)雜度為O(n2)。

3 試驗(yàn)分析

為了驗(yàn)證本文提出的MIkTree分類算法的有效性,本文從美國(guó)加州大學(xué)Irvine分校機(jī)器學(xué)習(xí)測(cè)試數(shù)據(jù)庫(kù)中選取了9組數(shù)據(jù)集對(duì)本文所提出的算法的分類性能進(jìn)行測(cè)試[26]。試驗(yàn)數(shù)據(jù)集的具體信息如表1所示。

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

表2 與其他常用算法的分類對(duì)比

此外,本文在9個(gè)UCI數(shù)據(jù)集上完成基于不同樣本大小的分類任務(wù)。圖2給出了5種分類方法在不同數(shù)據(jù)量下的分類精度(即5次交叉驗(yàn)證的平均分類精度),其中橫坐標(biāo)為樣本量,縱坐標(biāo)為分類精度。在圖2中,第一個(gè)矩形代表傳統(tǒng)k近鄰分類算法,第二個(gè)矩形代表加權(quán)k近鄰分類算法,第三個(gè)矩形代表GkNN分類算法,第四個(gè)矩形代表kTree算法,最后一個(gè)矩形表示本文提出的MIkTree分類算法。由圖2可知,在不同樣本維度下,本文提出的方法MIkTree分類算法在所有數(shù)據(jù)集中擁有較高的分類精度。例如,對(duì)于圖2的第7個(gè)數(shù)據(jù)集Wdbc,無(wú)論樣本的規(guī)模如何變化,MIkTree分類算法的分類準(zhǔn)確率約為0.95,k近鄰分類的分類正確率約為0.93,加權(quán)k近鄰分類和GkNN分類的分類準(zhǔn)確率約為0.92,kTree算法的分類準(zhǔn)確率小于0.93。MIkTree分類獲取的分類精度高于其他對(duì)比算法,表明MIkTree分類算法能夠有效提升分類的性能。

圖2 基于不同樣本維度的分類準(zhǔn)確率

4 結(jié)論

為了提升k近鄰分類算法的效果,本文提出了一種基于互鄰信息的kTree分類方法。首先,本文通過(guò)LASSO模型獲得樣本之間權(quán)重關(guān)系,獲取訓(xùn)練樣本的k值,通過(guò)構(gòu)建kTree,訓(xùn)練測(cè)試樣本,獲得測(cè)試樣本的k值。與傳統(tǒng)k近鄰分類相比,k值的獲取更加準(zhǔn)確合理。其次,不同于傳統(tǒng)k近鄰分類單向選擇k個(gè)最近鄰樣本。本文通過(guò)考慮二者之間的相互關(guān)系,剔除最近鄰中存在的無(wú)關(guān)數(shù)據(jù)。試驗(yàn)結(jié)果證明,本文提出的方法能夠有效的提升k近鄰分類的分類性能。在接下來(lái)的工作,筆者嘗試從以下兩個(gè)方向繼續(xù)k近鄰分類的提升：

(1)對(duì)于樣本之間緊密程度的刻畫(huà),訓(xùn)練樣本重構(gòu)的目標(biāo)函數(shù)應(yīng)該進(jìn)一步優(yōu)化。

(2)對(duì)于k近鄰分類算法的提升,D-S證據(jù)理論應(yīng)該嘗試融入本文提出的k近鄰分類方法。