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

林耀進(jìn)，李進(jìn)金,，陳錦坤，馬周明

(1.閩南師范大學(xué) 計算機(jī)科學(xué)與工程系，福建 漳州 363000； 2. 閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，福建 漳州 363000)

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

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

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

1 k-近鄰分類法

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

(1)

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

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

2.1 鄰域信息的影響

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

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

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

2.2 樣本鄰域的定義

據(jù)2.1節(jié)分析可知，考慮樣本鄰域之間的距離可以更加精確地刻畫樣本之間的距離Δ，因此，尋找樣本鄰域?qū)μ岣遦-近鄰分類算法具有重要的影響。本節(jié)中給出樣本的度量空間及樣本鄰域的定義。

定義1[13]給定一個m維的樣本空間Ω，Δ:Xm×Xm→X，稱Δ是Xm上的一個度量，如果Δ滿足：1)Δ(x1,x2)≥0,Δ(x1,x2)=0,當(dāng)且僅當(dāng)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相應(yīng)的δ鄰域。

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

(3)

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

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

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

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

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

3 算法設(shè)計

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果及分析

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

表1 數(shù)據(jù)描述

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

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

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

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

表3 噪聲數(shù)據(jù)下不同分類器的分類精度比較

5 結(jié)束語

本文提出了一種FK3N分類算法。首先，從度量空間角度定義了樣本鄰域信息，分析了樣本的鄰域?qū)δ芊窬_地計算樣本之間的距離具有重要的影響，提出了2條符合實際情況的準(zhǔn)則；然后在計算樣本個體之間的距離時，綜合考慮了樣本鄰域之間的相似性；最后提出了一種獲取最近鄰的計算方法。在多個公開UCI數(shù)據(jù)集上的實驗結(jié)果表明，本文方法在原始數(shù)據(jù)和噪聲數(shù)據(jù)上分類性能優(yōu)于或相當(dāng)于其他相關(guān)分類器。

參考文獻(xiàn):

[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]呂鋒, 杜妮, 文成林. 一種模糊-證據(jù)kNN分類方法[J]. 電子學(xué)報, 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ìn), 胡學(xué)鋼, 李慧宗. 基于用戶群體影響的協(xié)同過濾推薦算法 [J], 情報學(xué)報, 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.