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

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

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

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

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

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

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

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

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

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

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

圖1 KNN 分類(lèi)原理示意圖

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

2.1 算法的基本思路

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

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

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

頂點(diǎn)可分為以下三類(lèi)：

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

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

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

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

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

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

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

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

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

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

2.2 算法的改進(jìn)

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

顯然有0≤λ≤1。

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

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

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

記ni為Xi在樣本集中ε 鄰域中的點(diǎn)的個(gè)數(shù)，若ni＞MinPts，則稱(chēng)Xi為高密度點(diǎn)。

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

ε 鄰域的大小為

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

2.3 算法描述

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

Foreach(Xi in D)

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

Foreach(Xj in S)

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

}

//劃分有向圖，留下兩個(gè)頂點(diǎn)間有兩條弧的//邊緣點(diǎn)

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

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

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

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

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

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

Foreach(Xj in S)

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

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

//分別計(jì)算未分類(lèi)和已分類(lèi)的數(shù)目

If(num_var/num_var+num_zero＜λ0)

Xi.label=-1;

// 如果λ取值過(guò)小，即該簇中的未分類(lèi)樣本比// 重過(guò)大，則label=-1

Else Xi.label=mode(S);

//下面對(duì)新構(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 為高密度點(diǎn)時(shí)

{

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

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

Xi=[];//刪去ε鄰域中密度最高的點(diǎn)

}

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

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

{

S=find_nearest(Xi,k);

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

}

3 實(shí)驗(yàn)結(jié)果與分析

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

從圖2 可以看出，樣本偏斜時(shí)，原方法的誤分率會(huì)顯著提高，而整體誤分率隨著K值的增加呈下降趨勢(shì)。這是因?yàn)樵谠椒ㄖ?，樣本偏斜較大時(shí)，分類(lèi)的結(jié)果傾向于密度較大的類(lèi)別。

圖2 樣本偏斜對(duì)原方法的影響

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

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

4 結(jié) 語(yǔ)

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