遙感影像K-最近鄰圖目標(biāo)分類改進(jìn)算法的研究

王振力，滕 藤，王 群，黃忠演

（1. 江蘇警官學(xué)院，江蘇 南京 210031；2. 國防科技大學(xué)國際關(guān)系學(xué)院，江蘇 南京 210039）

傳統(tǒng)的目標(biāo)檢測識別方法[1]如極大似然法、最小距離法和K-均值聚類法等，已經(jīng)實現(xiàn)利用光譜統(tǒng)計特征完成目標(biāo)識別與分類，但是當(dāng)遙感影像中出現(xiàn)大量細(xì)節(jié)、地物光譜特征較為復(fù)雜時，這些傳統(tǒng)方法的準(zhǔn)確度會降低[2]。針對此類問題，文獻(xiàn)[3]提出將機(jī)器學(xué)習(xí)算法應(yīng)用于高分辨率影像的分類，比如神經(jīng)網(wǎng)絡(luò)（NN）、支持向量機(jī)（SVM），并且在分類過程中加入影像的紋理、結(jié)構(gòu)等特征。文獻(xiàn)[3]方法在提高分類準(zhǔn)確率的同時，仍需要進(jìn)一步提高對目標(biāo)的具體判別。

文獻(xiàn)[4]中提出一種基于K-最近鄰圖的改進(jìn)策略，在小樣本的情況下可取得較好的結(jié)果，但是對于樣本數(shù)據(jù)分布不均勻、待測樣本數(shù)量較多時效果不佳。針對這一問題，本文提出基于K-最近鄰圖KNN 改進(jìn)算法的深度學(xué)習(xí)模型，以提高對典型目標(biāo)的分類和判別能力，實現(xiàn)高精度的目標(biāo)檢測[5]。

1 K-最近鄰圖分類方法的改進(jìn)

深度學(xué)習(xí)領(lǐng)域中，可以用于分類的方法有決策樹、遺傳算法、神經(jīng)網(wǎng)絡(luò)、樸素貝葉斯、支持向量機(jī)、基于投票的方法、Rocchio 分類、KNN 分類、最大熵等[5]，其中KNN 作為一種較為成熟的算法，是向量空間模型（VSM）下最好的分類算法之一，如圖1 所示。

KNN 分類方法是一種傳統(tǒng)的無參量、有效、較流行的惰性學(xué)習(xí)方法，其基本的計算方法如下：記指示器函數(shù)為I(x)，有

式中，D 為訓(xùn)練集；x 為待分類的數(shù)據(jù)對象，本文中表示維度為N 的矩陣；U 為未標(biāo)記數(shù)據(jù)集，有x∈U；NK(x,D)為訓(xùn)練集D 中距離x 最近的K 個點，K 稱為最近鄰閾值；y 為訓(xùn)練集的分類數(shù)；

對于待分類的數(shù)據(jù)對象x，在訓(xùn)練集D 下采用K N N 分類法進(jìn)行分類，其分類數(shù)為c 可能性p(y=c|x,D,K)為

選取最大的p(y=c|x,D,K)值，并將x 標(biāo)記為分類數(shù)為c 的分類，重復(fù)此操作直至所有未標(biāo)記訓(xùn)練集U 中的對象分類完成。

圖1 KNN 分類原理示意圖

2 基于K-最近鄰圖的改進(jìn)策略

2.1 算法的基本思路

文獻(xiàn)[4]通過對于K-最近鄰圖的劃分，將必屬于某一分類的未標(biāo)記數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)對象進(jìn)行分類標(biāo)號，并加入原訓(xùn)練集，減少噪聲數(shù)據(jù)對于分類的影響。接下來，再對剩余未分類的未標(biāo)記數(shù)據(jù)進(jìn)行KNN 分類。

構(gòu)造合并數(shù)據(jù)集D，其中D 包含了訓(xùn)練集U 和樣本集R。指定樣本集中U 的每一個數(shù)據(jù)對象xi（i=1、2、…、n）為頂點i，A[i,j]表示從頂點i 到頂點j 的弧。選取每一個數(shù)據(jù)對象xi最近的k 個數(shù)據(jù)對象，連接k 條弧。由此，構(gòu)成了有n 個頂點的稀疏有向圖。

根據(jù)弧劃分該稀疏有向圖可知兩頂點間的弧數(shù)小于（等于）2。

頂點可分為以下三類：

1）頂點i 作為弧頭的弧數(shù)較多，可以判斷該頂點為這一類數(shù)據(jù)的中心數(shù)據(jù)對象；

2）頂點i 作為弧頭的弧數(shù)較少，可以判斷該頂點為這一類數(shù)據(jù)的邊緣數(shù)據(jù)對象；

3）頂點i 不作為弧頭，可以判斷該頂點為這一類數(shù)據(jù)的孤立點。

由此不難發(fā)現(xiàn)，當(dāng)兩頂點間弧數(shù)為2 時，這兩個頂點為邊緣數(shù)據(jù)對象。據(jù)此，若頂點i 和頂點j 之間的弧數(shù)不為2，刪去兩頂點之間的弧。由此，該稀疏有向圖被劃分為互不相連的有向子圖，n 個數(shù)據(jù)被劃分為多個簇。

根據(jù)子圖的特點，先給部分未標(biāo)記數(shù)據(jù)集中的數(shù)據(jù)標(biāo)記并加入樣本集。

標(biāo)記方法如下：

1）在一個簇中，若只存在已標(biāo)記對象，則不進(jìn)行處理；

2）只存在未標(biāo)記對象，則做上標(biāo)記并等待下一步處理；

3）同時存在已標(biāo)記和未標(biāo)記的對象，將所有未標(biāo)記的對象標(biāo)記為該簇中出現(xiàn)數(shù)量最多的分類，并將該簇中非此分類的已標(biāo)記對象認(rèn)作噪聲數(shù)據(jù)，并加以標(biāo)記。

使用KNN 分類法對未標(biāo)記的數(shù)據(jù)對象進(jìn)行分類。

2.2 算法的改進(jìn)

將部分未標(biāo)記數(shù)據(jù)集中的數(shù)據(jù)標(biāo)記時，待測樣本的密度直接影響了判斷的精度。如果待測樣本位于高密度區(qū)域，邊緣的少數(shù)已標(biāo)記數(shù)據(jù)會直接決定樣本的分類。因此，本文提出在分類時設(shè)定一個權(quán)值λ=λ0。

顯然有0≤λ≤1。

當(dāng)λ≥λ0時，分類并加入樣本集；

當(dāng)λ＜λ0時，不再將該樣本分類并加入樣本集，而是留作下一步處理。

該算法中，將未分類樣本集的部分樣本補(bǔ)充到訓(xùn)練樣本中，提高了分類準(zhǔn)確率。然而，容易受到已分類和未分類樣本偏斜的影響，使得結(jié)果向密度更高的類別傾斜，導(dǎo)致誤分率增加。為解決這一問題，本文提出針對在第二次分類前進(jìn)行均勻化裁剪的方法。

記ni為Xi在樣本集中ε 鄰域中的點的個數(shù)，若ni＞MinPts，則稱Xi為高密度點。

遍歷新樣本集的每一個Xi，若Xi為高密度點，在該元素的ε 鄰域中的所有點中，刪去高密度可達(dá)的點，直至該元素沒有高密度可達(dá)的點或者成為平均密度的點。

ε 鄰域的大小為

式中，D 為新樣本集；Distk 為Xi到距離最近的第k 個樣本的距離；MinPts 為最小樣本數(shù)。根據(jù)文獻(xiàn)[3]所述，MinPts 選取類別的平均樣本數(shù)的5%～8%效果較好。

2.3 算法描述

A=[n×n];//n 為數(shù)據(jù)集的數(shù)據(jù)對象數(shù)

Foreach(Xi in D)

{ S=find_nearest(Xi,k)//找到Xi 的k 個最//近鄰

Foreach(Xj in S)

{ A(i,j)=dist(Xi,Xj);//計算Xi 到其k 個最近鄰的距離并賦值給鄰接矩陣

}

//劃分有向圖，留下兩個頂點間有兩條弧的//邊緣點

For(i=1;i ≤n;i++)

For(j=1;j ≤n;j++)

If(A(i,j)==0) A(j,i)=0;

//下面利用鄰接矩陣A 進(jìn)行分類，并將分類的//結(jié)果加入訓(xùn)練樣本

For(i=1;i ≤n;i++)

If(Xi.label==0)S=find_group(Xi);//如果Xi 屬于未分類//樣本集，則查找Xi 所在簇中的頂點

Foreach(Xj in S)

If(Xi.label==0) num_zero++;

If(Xi.label!=0) num_var++;

//分別計算未分類和已分類的數(shù)目

If(num_var/num_var+num_zero＜λ0)

Xi.label=-1;

// 如果λ取值過小，即該簇中的未分類樣本比// 重過大，則label=-1

Else Xi.label=mode(S);

//下面對新構(gòu)成的樣本集進(jìn)行均勻化操作

If(Xi.label!=-1)

X_new=Xi;//X_new 為新樣本集

Foreach(Xi in X_new)

While num_neigh(Xi)＞MinPts

//當(dāng)Xi 為高密度點時

{

Y=pts_neigh(Xi);//找到Xi 的ε鄰域的點

l=argmax(|num_neigh(Y(l))|);

Xi=[];//刪去ε鄰域中密度最高的點

}

//以下使用傳統(tǒng)KNN 分類方法來分類未標(biāo)記對//象

Foreach(Xi in D and Xi.label==-1)

{

S=find_nearest(Xi,k);

Xi.label=mode(S);//用新的樣本集對剩//余未分類樣本進(jìn)行分類

}

3 實驗結(jié)果與分析

仿真實驗采用以常見高分辨率衛(wèi)星影像中飛機(jī)目標(biāo)長寬為基礎(chǔ)的模擬數(shù)據(jù)，選取目標(biāo)為F-16、F-15、Mig-29 和Su-27 四類飛機(jī)。在樣本數(shù)量上，貼近實際目標(biāo)出現(xiàn)的頻率，模擬了有偏斜的樣本[7]和無偏斜的樣本，實驗中分別運行原方法（文獻(xiàn)[4]方法）和改進(jìn)后的方法。第一組驗證樣本偏斜對原方法產(chǎn)生的影響，第二組驗證改進(jìn)后的方法對偏斜樣本的適應(yīng)能力。

從圖2 可以看出，樣本偏斜時，原方法的誤分率會顯著提高，而整體誤分率隨著K值的增加呈下降趨勢。這是因為在原方法中，樣本偏斜較大時，分類的結(jié)果傾向于密度較大的類別。

圖2 樣本偏斜對原方法的影響

圖3 改進(jìn)方法和原方法在處理偏斜數(shù)據(jù)時的對比

圖3 結(jié)果表明對于偏斜數(shù)據(jù)的處理，改進(jìn)的方法誤分率低于原方法。在K值較低時，樣本集的裁剪和權(quán)值λ發(fā)揮作用不明顯，因此誤分率的降低不夠明顯。當(dāng)K值在10 ～17 時，兩種方法的誤分率都有一定的降低，但是改進(jìn)后的方法降低更加明顯。當(dāng)K值超過17 時，誤分率又有一定的上升，這是由于樣本的數(shù)目隨著均勻化的裁剪有所降低，使得誤分率略有上升。

4 結(jié) 語

針對文獻(xiàn)[4]方法在偏斜數(shù)據(jù)上的不足，本文研究了基于K-最近鄰圖的改進(jìn)策略，誤分率低于該方法。對于權(quán)值λ的取值，在本文實驗中取0.7 ～0.9 效果最佳，但是如何找到一個通用的方法求出權(quán)值λ也是今后研究的方向。