基于互鄰信息的樹型近鄰分類方法

尹 濤,胡新平,鞠恒榮,黃嘉爽,丁衛平

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

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

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

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

1 基礎知識介紹

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

(1)

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

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

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

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

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

(2)

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

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

(3)

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

(4)

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

算法1k近鄰分類算法

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

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

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

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

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

④計算k個樣本所屬類別的出現頻率;

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

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

2 主要方法

2.1 k值獲取

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

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

(5)

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

2.2 kTree模型的構建

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

圖1 kTree的構建

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

2.3 MIkTree模型的構建

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

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

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

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

(6)

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

算法2MIkTree分類算法

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

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

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

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

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

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

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

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

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

3 試驗分析

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

表1 UCI數據集

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

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

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

4 結論

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

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

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