莫文通,周 源

(1.南寧市勘察測(cè)繪地理信息院,廣西南寧 530022; 2.同濟(jì)大學(xué)測(cè)繪與地理信息學(xué)院,上海 200092)

基于K近鄰非線性分類器的高光譜遙感數(shù)據(jù)分類研究

莫文通1?,周 源2

(1.南寧市勘察測(cè)繪地理信息院,廣西南寧 530022; 2.同濟(jì)大學(xué)測(cè)繪與地理信息學(xué)院,上海 200092)

K近鄰等傳統(tǒng)分類算法在高光譜遙感影像數(shù)據(jù)上進(jìn)行分類時(shí),由于其高維度、非線性特點(diǎn),分類效果會(huì)受到嚴(yán)重影響。本文利用核函數(shù)方法,融合K近鄰分類算法與Isomap非線性降維算法,提出了一種新的K近鄰非線性分類器。該分類器無需通過降維預(yù)處理,并具備處理非線性數(shù)據(jù)的能力。在實(shí)驗(yàn)中,通過交叉驗(yàn)證與參數(shù)驗(yàn)證證明該方法在高光譜遙感影像上的分類效果明顯優(yōu)于原始K近鄰分類算法以及結(jié)合主成分分析法的K近鄰分類法。

高光譜遙感;分類算法;K近鄰算法;非線性分類器

1 引 言

K近鄰分類算法[1]是利用遙感影像進(jìn)行土地利用/土地覆蓋調(diào)查最常用的傳統(tǒng)分類方法之一。該算法模型簡(jiǎn)單、直觀、易于實(shí)現(xiàn)和操作。目前,絕大多數(shù)遙感應(yīng)用軟件如ERDAS、ENVI等都植入了該算法作為遙感分類的默認(rèn)算法。由于該方法僅依靠有限的近鄰樣本確定待定樣本的類別,因此對(duì)于類間的交叉和重疊較為嚴(yán)重的待定樣本,K近鄰算法能獲得更好的分類效果。隨著高光譜遙感數(shù)據(jù)在土地利用/土地覆蓋應(yīng)用中的廣泛普及,其高維度、非線性特征等特點(diǎn)會(huì)嚴(yán)重影響傳統(tǒng)分類算法,尤其是K近鄰算法的分類效果[2]。

為了解決這一問題,在進(jìn)行分類前通常會(huì)使用降維方法降低遙感數(shù)據(jù)的維度。但傳統(tǒng)的降維方法如主成分分析法(PCA)、最小噪聲分離法(MNF)等缺乏提取非線性特征的能力。近年來,涌現(xiàn)了一批以Isomap算法為代表的基于流形的非線性降維方法[3,4],它們?cè)诮档陀^測(cè)數(shù)據(jù)空間維度的同時(shí)可從觀測(cè)空間中提取嵌入在該空間的非線性特征。該類新方法在遙感數(shù)據(jù)處理中已取得許多成功的應(yīng)用[5,6]。但是,該類方法需要顯式計(jì)算出觀測(cè)數(shù)據(jù)降維后對(duì)應(yīng)的低維坐標(biāo),使得降維過程計(jì)算復(fù)雜度過高。當(dāng)觀測(cè)數(shù)據(jù)量增加時(shí),該類算法降維時(shí)消耗的計(jì)算時(shí)間會(huì)顯著增加。

因此,本文利用核函數(shù)方法[7],提出了一種將Isomap算法與K近鄰算法相融合的K近鄰非線性分類器。在使用該分類器時(shí),無需顯式計(jì)算觀測(cè)數(shù)據(jù)的低維非線性表達(dá),只需利用Isomap算法的核函數(shù)直接將觀測(cè)數(shù)據(jù)的非線性信息帶入到K近鄰算法中進(jìn)行分類。這種做法的優(yōu)點(diǎn)是一方面避免了顯式降維計(jì)算,節(jié)約大量計(jì)算資源;另一方面仍然能有效提高原始K近鄰算法在高光譜遙感影像上的分類精度。

2 研究方法

2.1 K近鄰分類算法

K近鄰分類算法簡(jiǎn)單、直觀。使用該算法將D維空間觀測(cè)數(shù)據(jù)集X=[x1,…,xN](N為數(shù)據(jù)數(shù)量)分為C個(gè)類別的過程如下。首先,記錄訓(xùn)練樣本數(shù)據(jù)集Y= [y1,…,yM](M為訓(xùn)練樣本數(shù)量)以及每個(gè)訓(xùn)練樣本數(shù)據(jù)對(duì)應(yīng)的類別標(biāo)記∈[1,…,C](為第j個(gè)訓(xùn)練樣本數(shù)據(jù)的類別標(biāo)記)。其次,定義該觀測(cè)空間度量d(x,y),通常的選擇包括歐氏距離、角距離、馬氏距離等。在明確度量的前提下,獲取數(shù)據(jù)集中任意觀測(cè)數(shù)據(jù)點(diǎn)xi在訓(xùn)練樣本數(shù)據(jù)集Y中的k個(gè)近鄰:Yi=[ynn1,…,ynnk],{ynn1,…,ynnk∈Y}。最后,依照多數(shù)投票法則,可通過Yi中數(shù)據(jù)點(diǎn)對(duì)應(yīng)的類別得到觀測(cè)數(shù)據(jù)點(diǎn)xi所屬類別:

2.2 Isomap非線性特征提取方法

Isomap是一種基于等角映射的非線性降維方法。在使用分類器前使用Isomap方法對(duì)觀測(cè)空間中的數(shù)據(jù)集進(jìn)行降維,不僅能解決觀測(cè)數(shù)據(jù)高維度造成的分類器計(jì)算復(fù)雜度過高的問題,還能提升分類器處理非線性分布數(shù)據(jù)的能力。

通常高維觀測(cè)空間的數(shù)據(jù)分布具有較強(qiáng)的稀疏性,這些觀測(cè)數(shù)據(jù)可本看做分布在一個(gè)嵌入在高維觀測(cè)空間中的低維流形上。Isomap方法利用最短路徑搜索和多維排列法得到觀測(cè)數(shù)據(jù)在這個(gè)嵌入流形上的測(cè)地線距離關(guān)系,并通過該非線性關(guān)系將觀測(cè)數(shù)據(jù)投影到一個(gè)低維空間中,從而得到原始高維空間中數(shù)據(jù)集的非線性特征。其具體算法可見表1,有關(guān)該方法的證明可參考[8]。

表1 Isomap算法實(shí)現(xiàn)流程

2.3 基于Isomap的K近鄰算法核函數(shù)化

在Isomap方法提取的低維非線性特征空間的基礎(chǔ)上使用K近鄰方法分類可提升其對(duì)非線性分布數(shù)據(jù)的分類能力。但是隨著觀測(cè)空間數(shù)據(jù)量的增加,對(duì)數(shù)據(jù)點(diǎn)進(jìn)行一一顯式空間變換的計(jì)算復(fù)雜度會(huì)越來越高。并且顯式空間變換的解算過程會(huì)數(shù)據(jù)信息丟失和精度降低。為了解決以上問題,本文提出采用核方法將Isomap空間變換的核函數(shù)結(jié)合到K近鄰分類算法中,從而采用隱式空間變換的方法,省略計(jì)算空間變化結(jié)果的步驟,讓結(jié)合核函數(shù)的K近鄰算法直接在觀測(cè)空間中對(duì)數(shù)據(jù)進(jìn)行分類。

核方法的原理如下:遵循Mercer定理。令Φ為D維特征空間S1到d維特征空間S2的映射:

其中,x∈S1,Φ(x)∈S2。則對(duì)于x,y∈S1,有核函數(shù)K:K(x,y)=＜Φ(x),Φ(y)＞

＜∵＞為內(nèi)積符號(hào)。

由于核函數(shù)K(x,y)的計(jì)算復(fù)雜度遠(yuǎn)小于分別計(jì)算x,y在S2中的像以及像間內(nèi)積過程。因此在分類器模型中通常使用核函數(shù)替代原有觀測(cè)數(shù)據(jù)點(diǎn)的內(nèi)積,從而降低空間變換的計(jì)算代價(jià),增強(qiáng)模型對(duì)非線性數(shù)據(jù)的處理能力。該方法已廣泛應(yīng)用于如支持向量機(jī)、簇分析、數(shù)據(jù)降維等應(yīng)用中。

在K近鄰分類算法模型式(1)中雖然沒有可直接轉(zhuǎn)化核函數(shù)的內(nèi)積式,但是由于尋找K近鄰需要使用度量關(guān)系式(2),利用該式可實(shí)現(xiàn)K近鄰分類算法的核函數(shù)化:

根據(jù)式(2)可得到空間變化后數(shù)據(jù)點(diǎn)間的距離度量:

將式(3)的平方形式d2[Φ(x),Φ(y)]展開易得其內(nèi)積的表達(dá)形式:

根據(jù)式(4)即可求解數(shù)據(jù)點(diǎn)在核函數(shù)K對(duì)應(yīng)空間中的距離關(guān)系,進(jìn)而得到其在該空間中的近鄰,從而實(shí)現(xiàn)在變換空間中的K近鄰分類算法。

根據(jù)Nystrom定理[9],易知Isomap方法的核函數(shù)為:

Kiso(x,y)為觀測(cè)空間中任意數(shù)據(jù)點(diǎn)x與訓(xùn)練樣本中任意數(shù)據(jù)點(diǎn)y的核函數(shù),右式中x′、x″為訓(xùn)練樣本中的任意數(shù)據(jù)點(diǎn)點(diǎn),~D(∵)為兩點(diǎn)間測(cè)地線距離,E[~D2(x,·)]是x點(diǎn)與訓(xùn)練樣本集合中數(shù)據(jù)點(diǎn)測(cè)地線距離的期望值。將式(5)帶入式(4)中,即可利用核函數(shù)使K近鄰分類算法在Isomap模型提取的非線性信息的基礎(chǔ)上進(jìn)行分類計(jì)算。

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

本實(shí)驗(yàn)選用了國際通用的標(biāo)準(zhǔn)高光譜遙感數(shù)據(jù)集Indian Pine以檢驗(yàn)新算法的分類效果。該數(shù)據(jù)集由AVIRIS機(jī)載傳感器獲取,空間分辨率為30 m,有效光譜范圍覆蓋400 nm～2 500 nm波段范圍共220個(gè)波段,經(jīng)過剔除噪聲波段與水汽吸收帶,保留158個(gè)波段。該數(shù)據(jù)集影像大小為145×145像素,依據(jù)地面實(shí)況數(shù)據(jù)可分為12個(gè)類別(表2)。數(shù)據(jù)集的假彩色影像以及地面實(shí)況數(shù)據(jù)的分布情況如圖1所示。

表2 實(shí)驗(yàn)數(shù)據(jù)地物類別與分布情況

圖1 影像數(shù)據(jù)實(shí)驗(yàn)對(duì)比圖

為了驗(yàn)證基于Isomap的核函數(shù)化K近鄰分類算法的分類性能,本文采用交叉驗(yàn)證的方法對(duì)比原始K近鄰算法、采用PCA算法的K近鄰算法和本文提出的K近鄰算法的分類精度。在交叉驗(yàn)證過程中,地面實(shí)況數(shù)據(jù)被隨機(jī)平均分為一百份進(jìn)行一百次分類計(jì)算。測(cè)試時(shí),將每份子集作為訓(xùn)練樣本,其余數(shù)據(jù)作為測(cè)試樣本進(jìn)行一次分類,得到當(dāng)次的分類精度。實(shí)驗(yàn)的最終分類精度為一百次分類的平均精度。在分類過程中,三種算法的模型參數(shù)設(shè)置為:K近鄰數(shù)量為3個(gè),訓(xùn)練樣本數(shù)量為100個(gè)像素,分類結(jié)果如圖2所示。其中,原始K近鄰模型的分類精度為54.76%± 1.85%;在使用PCA降維到10個(gè)維度上使用K近鄰分類算法的分類精度為54.63%±1.85%;采用本文提出的非線性K近鄰分類方法的分類精度為60.9%± 1.99%。與原始K近鄰分類算法相比,新算法的分類精度提高了11.21%;與基于PCA的K近鄰分類算法相比,新算法的分類精度提高了11.48%。

在以上實(shí)驗(yàn)中,在算法輸入?yún)?shù)一致的情況下,新算法在分類精度上與原始K近鄰算法相比有較為明顯的提高。為了進(jìn)一步驗(yàn)證新分類算法的穩(wěn)定性,實(shí)驗(yàn)將分別逐漸增加訓(xùn)練樣本數(shù)量與K近鄰數(shù)量,在改變參數(shù)的過程中比較三種分類算法的分類精度及其變化。

圖2 原始K近鄰算法、PCA結(jié)合K近鄰算法與本文算法分類精度對(duì)比圖

其中,圖3為K近鄰數(shù)量為3個(gè),訓(xùn)練樣本數(shù)量由100像素增加至500像素時(shí),三種分類算法的分類精度變化結(jié)果。由該圖可見,隨著訓(xùn)練樣本數(shù)量的增加,三種算法的分類精度都逐漸提高;但是新算法的分類精度始終高于其他兩種算法。其中,當(dāng)訓(xùn)練樣本數(shù)量為100個(gè)像素時(shí),與原始K近鄰算法和基于PCA的K近鄰算法相比新算法分別將分類精度提高11.21%與11.48%;當(dāng)訓(xùn)練樣本數(shù)量為200個(gè)像素時(shí),新算法分別將分類精度提高9.10%與9.43%;當(dāng)訓(xùn)練樣本數(shù)量為300個(gè)像素時(shí),新算法分別將分類精度提高8.92%與8.82%;當(dāng)訓(xùn)練樣本數(shù)量為400個(gè)像素時(shí),新算法分別將分類精度提高7.29%與7.82%;當(dāng)訓(xùn)練樣本數(shù)量為500個(gè)像素時(shí),新算法分別將分類精度提高7.42%與7.97%。

圖3 隨訓(xùn)練樣本數(shù)量增加時(shí)各分類方法的分類精度變化圖

圖4 為訓(xùn)練樣本數(shù)量為500個(gè)像素,K近鄰數(shù)量由3個(gè)增加至9個(gè)時(shí),三種分類算法的分類精度變化結(jié)果。由該圖可見,隨著K近鄰數(shù)量的增加,三種算法的分類精度都逐漸降低;但新算法的分類精度仍然高于其他兩類算法。其中,當(dāng)K近鄰數(shù)量為3個(gè)時(shí),與原始K近鄰算法以及基于PCA的K近鄰算法相比,新算法分別將分類精度提高7.42%與7.97%;當(dāng)K近鄰數(shù)量為4個(gè)時(shí),新算法分別將分類精度提高7.30%與7.78%;當(dāng)K近鄰數(shù)量為5個(gè)時(shí),新算法分別將分類精度提高7.06%與7.48%;當(dāng)K近鄰數(shù)量為6個(gè)時(shí),新算法分別將分類精度提高7.57%與8.10%;當(dāng)K近鄰數(shù)量為7個(gè)時(shí),新算法分別將分類精度提高7.37%與7.79%;當(dāng)K近鄰數(shù)量為8個(gè)時(shí),新算法分別將分類精度提高7.69%與8.00%;當(dāng)K近鄰數(shù)量為9個(gè)時(shí),新算法分別將分類精度提高7.81%與8.16%。

圖4 隨K近鄰增加各分類方法的分類精度變化圖

由以上實(shí)驗(yàn)結(jié)果可以看出,與原始K近鄰算法以及先用PCA算法降維再進(jìn)行K近鄰算法分類的方式相比,本文提出的新算法能有效提高分類精度。并且盡管模型參數(shù)在變化,新算法能始終保持比較明顯的分類精度優(yōu)勢(shì)。尤其是當(dāng)訓(xùn)練樣本數(shù)量降低時(shí),新算法的分類精度有更為明顯的提高。

4 結(jié) 語

本文嘗試在Isomap非線性降維方法的基礎(chǔ)上使用K近鄰分類器進(jìn)行高光譜遙感影像分類。在引入核函數(shù)方法后,本文有效地將兩種算法相結(jié)合,不僅節(jié)約了計(jì)算成本,簡(jiǎn)化了算法實(shí)現(xiàn)步驟,并在最后通過實(shí)驗(yàn)證明這種算法的結(jié)合能有效提升原始K近鄰模型的分類精度,其分類效果更高于簡(jiǎn)單使用PCA算法降維再分類的方式。近年來,越來越多類似Isomap的非線性降維方法被發(fā)明和改進(jìn),在今后的工作中我們希望嘗試將更多類似算法核函數(shù)化并嘗試用于傳統(tǒng)分類器模型中,以提高其處理非線性觀測(cè)數(shù)據(jù)的能力。

[1] 鐘智,朱曼龍,張晨等.最近鄰分類方法的研究[J].計(jì)算機(jī)科學(xué)與探索,2011(5):467～473.

[2] Houle M E,Kriegel H P,Kr?ger P and et al.Can Shared-Neighbor Distances Defeat the Curse of Dimensionality? [A].Statistical and Scientific Database Management-SSDBM,2010:482～500.

[3] Tenenbaum J B,de Silva V,Langford J C.A Global Geometric Framework for Nonlinear Dimensionality Reduction[J].Science,2000:2319～2323.

[4] Roweis S T,Saul L K.Nonlinear Dimensionality Reduction by Locally Linear Embedding[J].Science,2000,2323～2326.

[5] 杜培軍,王小美,譚琨等.利用流形學(xué)習(xí)進(jìn)行高光譜遙感影像的降維與特征提取[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版,2011(2):48～52.

[6] 劉行波,武小軍,周源.利用流形技術(shù)的遙感高光譜圖像邊緣檢測(cè)[J].城市勘測(cè),2010(S1):94～96.

[7] Xiong H.A Unified Framework for Kernelization:The Empirical Kernel Feature Space[A].Chinese Conference on Pattern Recognition-CCPR,2009.

[8] Balasubramanian M,Schwartz E L,Tenenbaum J B and et al.The Isomap Algorithm and Topological Stability[J].Science,2002,7a:7.

[9] Bengio Y,Paiement J,Vincent P and et al.Out-of-Sample Extensions for LLE,Isomap,MDS,Eigenmaps,and Spectral Clustering[A].Neural Information Processing Systems-NIPS,2003.

A Nonlinear K-Nearest Neighbor Classifier for Hyperspectral Remote Sensing Imagery Classification

Mo Wentong1,Zhou Yuan2
(1.Nanning Exploration&Survey Geoinformation Institute,Nanning 530022,China; 2.Tongji University College of Surveying and Geo-informatics,Shanghai 200092,China)

High dimensionality and nonlinearity are two main factors of Hyperspectral remote sensing data that will decrease the classification accuracy for most existing classification algorithms,such as K-nearest neighbor(KNN).This paper proposed a new nonlinear KNN classifier,which fuses the original KNN algorithm and Isomap algorithm by Kernel trick.This classifier does not need explicitly dimensionality reduction but still has the ability to analyze the nonlinearity by taking advantage of the Isomap algorithm.By cross-validation and parameter analysis in the experiments with hyperspectral test data,this new method has been proven to out-perform the original KNN and KNN with PCA algorithm in Classification Accuracy.

hyperspectral remote sensing;classification;KNN;nonlinearity

2014—04—13

莫文通(1981—),男,工程師,主要從事測(cè)繪工程管理、測(cè)繪信息化建設(shè)等技術(shù)工作。