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

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

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

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

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

1 基礎知識介紹

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

(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);

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

(2)

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

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

(3)

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

(4)

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

算法1k近鄰分類算法

輸入：訓練樣本集(X1,X2,…,Xn),訓練樣本的類別標簽(C1,C2,…,Cn),測試樣本Y,測試樣本的k值。

輸出：測試樣本的預測標簽L。

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

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

③選取距離最小的k個樣本(X1,X2,…,Xk)以及對應的類別標簽(C1,C2,…,Ck);

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

⑤返回k個樣本出現(xiàn)頻率最高的類別作為測試樣本Y的預測標簽L。

算法1的時間復雜度為O(n),具有簡單高效的優(yōu)點。

2 主要方法

2.1 k值獲取

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

定義3X為訓練樣本,Y為測試樣本,W為訓練樣本重構權重矩陣。通過訓練樣本重構測試樣本的目標函數(shù)如下所示

(5)

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

2.2 kTree模型的構建

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

圖1 kTree的構建

kTree算法的時間消耗主要體現(xiàn)在訓練樣本的k值獲取。通過LASSO模型得到訓練樣本之間的緊密程度,其主要時間復雜度為O(n2),kTree的構建主要的時間消耗為O(logn)?？偟膩碚f,算法的時間復雜度為O(n2)。

2.3 MIkTree模型的構建

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

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

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

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

(6)

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

算法2MIkTree分類算法

輸入：訓練樣本集(X1,X2,…,Xn),訓練樣本的類別標簽(C1,C2,…,Cn),測試樣本Y。

輸出：測試樣本的預測標簽L。

①根據(jù)LASSO模型與kTree模型分別獲得訓練樣本集和測試樣本Y對應的k值;

②將測試樣本Y加入訓練樣本集(X1,X2,…,Xn)中,新的訓練集表示為TS′;

③選取距離最小的k個樣本(X1,X2,…,Xk)以及對應的類別標簽(C1,C2,…,Ck);

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

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

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

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

3 試驗分析

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

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

表2 與其他常用算法的分類對比

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

圖2 基于不同樣本維度的分類準確率

4 結論

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

(1)對于樣本之間緊密程度的刻畫,訓練樣本重構的目標函數(shù)應該進一步優(yōu)化。

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