融合鄰域信息的k-近鄰分類

林耀進，李進金,，陳錦坤，馬周明

(1.閩南師范大學 計算機科學與工程系，福建 漳州 363000； 2. 閩南師范大學 數學與統計學院，福建 漳州 363000)

k-近鄰法是一種非常簡單有效的分類算法，廣泛應用于數據挖掘和模式識別的各個領域[1-3]。其基本思想是通過計算尋找訓練集中距離待分類樣本最近的k個鄰居，然后基于它們的類別信息，依據投票的原則對待分類樣本的類別進行判定。k-近鄰算法的分類精度很大程度受影響于樣本之間距離的度量。

近幾年，出現了許多改進的距離度量方法以提高k-近鄰算法的分類性能，主要分為局部距離和全局距離兩大類。在傳統的全局距離度量方面，針對異構特征，提出了相應的距離度量方法，如：值差度量(value difference metric, VDM)、修正的值差度量(modified value difference metric, MVDM) 和異構歐幾里德—重疊度量(heterogeneous euclidean-overlap metric, HEOM)等[4-5]。另外，許多學者考慮了樣本之間的權重以增強樣本之間的相似性。Hu等[6]提出一種通過梯度下降的方法估計樣本之間的權重進行改進KNN的分類算法；Wang等[7]提出一種簡單的自適應距離度量來估算樣本的權重。同時，一些學者通過屬性加權或屬性選擇途徑改進距離度量[8-9]。在局部距離度量方面，許多方法利用局部自適應距離處理全局優化問題，如：ADAMENN中的自適應距離，WAKNN中的權重校正度量方法及DANN中的差異化自適應度量方法[10-11]。

上述方法雖能有效地度量樣本之間的距離，但基本上都是從單一的距離進行考慮，存在著以下缺點：1)并未考慮樣本之間的鄰域結構；2)易受噪聲的影響；3)不能處理多模態分布問題。因此，本文受推薦中的用戶群體影響概念的啟發[12]，提出了一種融合樣本鄰域信息的k-近鄰分類算法。

1 k-近鄰分類法

k-近鄰分類法是一種非常簡單有效的用于分類學習和函數逼近的算法。給定由n個樣本標簽對組成的數據集D，D={(x1,c1),(x2,c2),…,(xn,cn)}，其分類的任務在于獲取映射函數f,使得能正確預測無標簽樣本。設Nk(x)為測試樣本x的k-近鄰集合，k-近鄰分類法在于通過測試樣本x的k-近鄰進行大眾數投票進行確定x的標簽，其公式為

(1)

式中：cj為樣本xj的類標簽，I(·)為指示函數，當ci與cj一樣時，I(cj=ci)=1，否則，I(cj=ci)=0。

2 融合鄰域信息的k-近鄰分類算法

2.1 鄰域信息的影響

傳統的k-近鄰分類算法本質上是利用樣本個體與個體之間的距離(尋找對測試樣本影響最大的前k個近似鄰居)來預測測試樣本的類標簽，該預測只是簡單地考慮樣本個體之間的相似性，而忽略了樣本的鄰域信息。因此，在計算樣本個體距離時不僅要考慮樣本個體之間的距離，也要考慮樣本鄰域信息產生的距離。圖1清楚地描述了樣本鄰域信息產生的影響作用，從圖1可以看出，雖然樣本x1與x2之間的距離與樣本x1與x3之間的距離相等，即d(x1,x2)=d(x1,x3)，但是樣本x1的鄰域信息與x3的鄰域信息之間包含更多的大量的共同鄰居，則從認識論的角度出發，d(x1,x3)≥d(x1,x2)。根據以上分析，可以得出準則1。

準則1 考慮樣本鄰域信息的影響能更加精確地刻畫樣本之間的距離。

圖1 樣本鄰域圖Fig.1 Neighborhood of sample

2.2 樣本鄰域的定義

據2.1節分析可知，考慮樣本鄰域之間的距離可以更加精確地刻畫樣本之間的距離Δ，因此，尋找樣本鄰域對提高k-近鄰分類算法具有重要的影響。本節中給出樣本的度量空間及樣本鄰域的定義。

定義1[13]給定一個m維的樣本空間Ω，Δ:Xm×Xm→X，稱Δ是Xm上的一個度量，如果Δ滿足：1)Δ(x1,x2)≥0,Δ(x1,x2)=0,當且僅當x1=x2,?x1,x2∈Xm；2)Δ(x1,x2)=Δ(x2,x1),?x1,x2∈Xm；3)Δ(x1,x3)≤Δ(x1,x2)+Δ(x2,x3),?x1,x2,x3∈Xm；稱〈Ω,Δ〉為度量空間。

在N維歐氏空間中，給定任意2點xi=(xi1,xi2,…,xiN)和xj=(xj1,xj2,…,xjN)，其距離為

(2)

定義2 給定樣本空間上的非空有限集合X={x1,x2,…,xm}，對于X上的任意樣本xi，定義其δ鄰域為δ(xi)={x|x∈X,Δ(x,xi)≤δ}，其中，0≤δ≤1。δ(xi)稱為樣本xi相應的δ鄰域。

定義3 給定樣本空間上的非空有限集合X={x1,x2,…,xm}，對于X上的任意樣本xi及xj，根據VDM公式，定義樣本xi及xj之間的鄰域距離為

(3)

性質1[13]給定一個度量空間〈Ω,Δ〉，一個非空有限樣本集合X={x1,x2,…,xm}。如果δ1≤δ2，則有

1) ?xi∈X:δ1(xi)≥δ2(xi)；

根據定義3及性質1，隨著樣本距離δ的增大，樣本鄰域中所包含的對象數量隨著增加，樣本之間的區分度將降低。如圖2所示，隨著距離的增大，原來不屬于同一鄰域的樣本x1、x2、x3變成處于同一鄰域：即樣本x1、x2、x3在圖1中不屬于同一鄰域，而在圖2中則處于同一鄰域。根據以上分析，可以得出準則2。

準則2 選擇樣本鄰域的大小影響著樣本之間距離的精確刻畫。

圖2 δ減小后的樣本鄰域圖Fig.2 Neighborhood of sample with smallerδ

3 算法設計

在對樣本鄰域影響分析的基礎上，利用歐式距離計算樣本之間的距離，用改進的VDM計算樣本鄰域之間的距離，設計融合樣本鄰域信息的k-近鄰分類算法如下：

算法1 融合樣本鄰域信息的k-近鄰分類算法(FK3N)。

輸入：數據集D，測試樣本x，距離閾值δ，近鄰個數k；

輸出：測試樣本x的標簽c(x)。

1)初始化c(x)=φ；

2)根據式(2)獲取測試樣本與訓練樣本的k/2個近鄰R1；

3)根據式(3)獲取測試樣本鄰域與訓練樣本鄰域的k/2個近鄰R2；

4)獲得測試樣本x的融合近鄰集合R=R1∪R2后，即測試樣本x的k近鄰Nk(x)；

5)根據式(1)獲得測試樣本x的類標簽c(x)。

4 實驗結果及分析

為了驗證所提出算法的有效性，從UCI 數據集中挑選了6組數據。其中，為了驗證算法的適用性，其數據集的類別從2類到3類，特征數從5～60，具體描述信息見表1。同時，進行2組實驗，第1組實驗與經典的分類算法KNN、NEC[13]、CART、LSVM進行比較；另一組檢測在噪聲數據影響下，本文所提出的FK3N與其他分類器的比較。

表1 數據描述

實驗1 為了驗證FK3N的分類性能，在本實驗中，與其他流行的分類算法進行了比較，如表2。

表2 不同分類器的分類精度比較

其中將FK3N、KNN涉及到的參數k設置為10，將FK3N、NEL涉及到的參數delta設置為0.1。為了顯示標注FK3N在6個UCI數據集上的分類精度，在FK3N中加粗的代表分類精度最高，下劃線代表分類精度第2。另外，在表2最后一行顯示不同分類器的平均分類精度。從表2可以看出，FK3N雖然只在2個數據集上取得最優的分類效果，但是在其他3個數據集上取得第2(或并列)的分類精度。另外，在平均分類精度可以看出，FK3N取得最高的平均分類精度，比LSVM還高出1.19%。因此，從本實驗可以看出，與其他流行的分類器相比，說明了本文提出的FK3N算法具有較為優越的分類性能。

實驗2 為了考察FK3N的穩定性，在訓練數據的屬性中注入噪聲。首先生成一個服從標準正態分布的m×n(m為樣本數，n為屬性數)的噪聲數據，然后乘以系數a后加入原始訓練數據中。本文設a的值為0.1。從表3可以看出，與其他分類器相比，在存在噪聲情況下，FK3N在多個數據集上的分類精度取得良好的結果。

表3 噪聲數據下不同分類器的分類精度比較

5 結束語

本文提出了一種FK3N分類算法。首先，從度量空間角度定義了樣本鄰域信息，分析了樣本的鄰域對能否精確地計算樣本之間的距離具有重要的影響，提出了2條符合實際情況的準則；然后在計算樣本個體之間的距離時，綜合考慮了樣本鄰域之間的相似性；最后提出了一種獲取最近鄰的計算方法。在多個公開UCI數據集上的實驗結果表明，本文方法在原始數據和噪聲數據上分類性能優于或相當于其他相關分類器。

參考文獻:

[1]COVER T, HART P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967 (13) ： 21-27.

[2]WU X D, KUMAR V, QUINLAN J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008，14(1) ： 1-37.

[3]呂鋒, 杜妮, 文成林. 一種模糊-證據kNN分類方法[J]. 電子學報, 2012， 40(12) ： 2930-2935.

[4]WANG H. Nearest neighbors by neighborhood counting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005，28 (6)： 942-953.

[5]WILSON D R, MARTINEZ T R. Improve heterogeneous distance functions[J]. Journal of Artificial Intelligence Research, 1997 (6)： 1-34.

[6]HU Q H, ZHU P F, YANG Y B, et al. Large-margin nearest neighbor classifiers via sample weight learning[J]. Neurocomputing, 2011， 74 (4)： 656-660.

[7]WANG J, NESKOVIC , COOPER L.N. Improving nearest neighbor rule with a simple adaptive distance measure[J]. Pattern Recognition Letters, 2007， 28 ： 207-213.

[8]KOHAVI R, LANGLEY P, YUNG Y. The utility of feature weighting in nearest neighbor algorithms[C]//Proceedings of the Ninth European Conference on Machine Learning. [S.l.]， 1997.

[9]SUN Y J. Iterative RELIEF for feature weighting: algorithms, theories, and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(6): 1035-1051

[10]MU Y, DING W, TAO D C. Local discriminative distance metrics ensemble learning[J]. Pattern Recognition, 2013, 46 (8): 2337-2349.

[11]SONG Y, HUANG J, ZHOU D, et al. IKNN: informative k-nearest neighbor pattern classification[C]//PKDD 2007. [S.l.], 2007: 248-264.

[12]林耀進, 胡學鋼, 李慧宗. 基于用戶群體影響的協同過濾推薦算法 [J], 情報學報, 2013, 32(3): 299-350.

[13]HU Q H, YU D R, XIE Z X. Neighborhood classifiers[J]. Expert Systems with Applications, 2008, 34 (2): 866-876.