結(jié)合局部全局一致性和支持向量機(jī)的半監(jiān)督分類方法

池辛格，王立國

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001

遙感技術(shù)是近代發(fā)展起來的一種綜合的對地觀測技術(shù)。其定義是通過某種設(shè)備，不接觸被測目標(biāo)或區(qū)域來獲取相關(guān)數(shù)據(jù)，并對其進(jìn)行分析從而得到所需要信息[1]。遙感界根據(jù)光譜分辨率將成像光譜技術(shù)劃分為多光譜遙感、高光譜遙感和超光譜遙感3類[2]。其中，高光譜遙感(hyperspectral remote sensing, HRS)技術(shù)作為遙感領(lǐng)域的前沿技術(shù)，通過融合目標(biāo)探測和光譜成像技術(shù)，能夠表征地物的多維特征信息，實(shí)現(xiàn)更詳細(xì)的地物分類，受到了廣大研究者的青睞，并被廣泛應(yīng)用于軍事、農(nóng)業(yè)、林業(yè)、畜牧業(yè)等領(lǐng)域，為我們的生活和工作帶來了便利[3]。與傳統(tǒng)的遙感技術(shù)相比，高光譜遙感能夠獲得更加豐富的光譜特征并有效反映特征間的細(xì)微差異，通過地物的數(shù)百個連續(xù)的譜段信息提供豐富的光譜信息[1]。高光譜遙感的特點(diǎn)也為處理技術(shù)帶來了新的挑戰(zhàn)。在高光譜圖像的分類方向，龐大高維的數(shù)據(jù)和相互重疊的眾多波段往往會導(dǎo)致維數(shù)災(zāi)難現(xiàn)象，獲得準(zhǔn)確地物標(biāo)簽的極高代價使得有標(biāo)簽樣本數(shù)量極少，且不一定具有代表性，這些問題對高光譜圖像的分類產(chǎn)生了極大的影響。

如今較為常用的高光譜分類方法有無監(jiān)督分類、監(jiān)督分類和半監(jiān)督分類幾種。常用的監(jiān)督分類方法包括最大似然算法[4]、支持向量機(jī)(support vector machine, SVM)和人工神經(jīng)網(wǎng)絡(luò)等。此類方法依賴于先驗(yàn)知識的獲取來進(jìn)行分類，因此需要大量標(biāo)記準(zhǔn)確的訓(xùn)練樣本。當(dāng)訓(xùn)練樣本數(shù)量過少或代表性不夠強(qiáng)時，分類效果不佳。同時高光譜數(shù)據(jù)中大量的準(zhǔn)確標(biāo)記也帶來了成本過高的問題。常用的半監(jiān)督分類方法有半監(jiān)督支持向量機(jī)[5]、基于圖的半監(jiān)督算法[6]和協(xié)同訓(xùn)練(Cotraining)[7]等。此種分類方法不僅利用了先驗(yàn)信息，還能充分挖掘無標(biāo)簽數(shù)據(jù)中的信息，彌補(bǔ)了另外兩種分類方法的不足，有效地提高了分類精度。

在監(jiān)督分類算法中，支持向量機(jī)(support vector machine, SVM)于1995年由Vapnik等提出[8]，該方法以統(tǒng)計(jì)學(xué)習(xí)理論中的VC維(vapnik chervonenks dimension)準(zhǔn)則和結(jié)構(gòu)化風(fēng)險最小化準(zhǔn)則(structural risk minimization inductive principle)作為理論依據(jù)，尋找能將兩種樣本進(jìn)行最佳分類的超平面，在處理高維非線性數(shù)據(jù)方面有極大的優(yōu)勢，分類器的泛化性能和推廣性很強(qiáng)，這些優(yōu)勢使在高光譜圖像分類中得到廣泛應(yīng)用。

在半監(jiān)督分類方法中，基于圖的半監(jiān)督算法因其設(shè)定參數(shù)少，過程較為直觀等優(yōu)點(diǎn)被研究者所青睞。基于圖的半監(jiān)督算法最早由Blum A等[7]提出，此種方法以每個樣本點(diǎn)作為節(jié)點(diǎn)，樣本點(diǎn)間的相似程度作為連接兩個節(jié)點(diǎn)的邊，將數(shù)據(jù)集構(gòu)造為一個圖，以此挖掘無標(biāo)簽樣本的信息。根據(jù)所有的節(jié)點(diǎn)是否兩兩相連可以分為全連接圖和近鄰圖，根據(jù)邊有無方向可以分為有向圖和無向圖。常見的基于圖的半監(jiān)督分類算法有標(biāo)簽傳遞算法[9]，高斯隨機(jī)場算法和流形正則化算法等。

經(jīng)典的標(biāo)簽傳遞算法由于傳遞過程中的隨機(jī)性，分類精度和穩(wěn)定性較差，無法在實(shí)際中應(yīng)用，傳統(tǒng)的SVM算法被監(jiān)督分類方法本身的缺陷限制，受樣本選擇的影響極大，針對兩種算法的缺陷，本文提出了一種結(jié)合局部和全局一致性（learning with local and global consistency，LLGC）算法和SVM算法的半監(jiān)督分類方法，通過篩選2種算法對無標(biāo)簽訓(xùn)練樣本分類結(jié)果相同的樣本并加入有標(biāo)簽訓(xùn)練樣本集輔助分類，用擴(kuò)充后的訓(xùn)練樣本訓(xùn)練SVM分類器預(yù)測測試樣本。在Indian Pines和Paiva兩個數(shù)據(jù)集的實(shí)驗(yàn)中證明了算法的有效性

1 支持向量機(jī)

支持向量機(jī)分類方法的基本思想是尋找一個可以最大程度正確地將2類樣本劃分在兩側(cè)的超平面，即最優(yōu)超平面，保證每類樣本中與超平面距離最近的樣本與超平面之間的距離最大[10]，其本質(zhì)是一種二分類算法。如今SVM理論由于其在處理高維非線性數(shù)據(jù)方面的優(yōu)勢，已經(jīng)成為高光譜分類領(lǐng)域應(yīng)用最廣、適應(yīng)性最強(qiáng)的監(jiān)督分類算法，在模式識別、機(jī)器學(xué)習(xí)等問題中也作為主流算法大量出現(xiàn)。

設(shè)n維空間中存在樣本集(x1,y1),(x2,y2),···,(xl,yl)，其 中xi∈Rd，樣 本 的類別yi∈{?1,+1}，樣本數(shù)目為l。SVM的目標(biāo)是找到超平面wTx+b=0 ，其中w=[w1,w2,···,wn]T為權(quán)向量，b是常數(shù)。當(dāng)樣本線性可分時如圖1所示。

圖1 線性可分情況下最優(yōu)分類面

此時2個類別的支持向量到最優(yōu)分類超平面的距離之和，可以表示為這就是2個類別間的幾何間隔。SVM中需要使類別間的幾何間隔最大，等價于使‖w‖最小，于是尋找最優(yōu)分類超平面的問題轉(zhuǎn)化為如下優(yōu)化問題[11]：

其中αi是拉格朗日乘子，且αi≥0，i=1,2,···,n。

對w和b求偏導(dǎo)后帶入拉格朗日函數(shù)，即可得到對偶問題。此時優(yōu)化問題已經(jīng)轉(zhuǎn)化為最大化如下目標(biāo)函數(shù)：

可以求得：

最終得到相應(yīng)的判別函數(shù)式為

這種對于線性可分的樣本集的間隔最大化過程被稱為“硬間隔最大化”。

在有些情況下訓(xùn)練集中會出現(xiàn)一些異常的樣本點(diǎn)，導(dǎo)致訓(xùn)練集線性不可分。線性不可分樣本集的近似分類如圖2所示。

圖2 線性不可分樣本集的近似分類

此時可將約束條件放寬為代表允許某些異常點(diǎn)被分到錯誤的類中，同時引入松弛變量的懲罰項(xiàng)C以實(shí)現(xiàn)最小化錯分程度和最大化目標(biāo)間隔。此時原始問題可以描述為

對于式(1)～(9)，可以采用同樣的求解方法，可得到最終結(jié)果：

這種通過修正目標(biāo)函數(shù)實(shí)現(xiàn)間隔最大化的過程被稱為“軟間隔最大化”。

在實(shí)際應(yīng)用中往往會遇到非線性的分類問題，此時應(yīng)將原本的樣本空間Rd映射到一個高維的希爾伯特空間H使樣本集線性可分或近似線性可分，此后即可使用硬間隔最大化或軟間隔最大化對樣本進(jìn)行分類。

假設(shè)函數(shù)φ是一個從低維特征空間到高維特征空間的映射,那么在非線性分類過程中內(nèi)積應(yīng)該被替換為

稱K(xi,xj)為核函數(shù)(kernel function)。此時目標(biāo)函數(shù)變?yōu)?/p>

相應(yīng)的判別函數(shù)式為

常見的核函數(shù)有線性核、多項(xiàng)式核、拉普拉斯核、徑向基函數(shù)核等。

2 局部全局一致性算法

LLGC方法的原理就是通過局部和全局一致性假設(shè)來定義能量函數(shù)。依據(jù)相鄰的樣本點(diǎn)可能屬于同一類別傳遞標(biāo)簽信息，使能量函數(shù)取最小值，為不帶標(biāo)簽樣本點(diǎn)進(jìn)行標(biāo)注，得到分類結(jié)果。同其他基于圖的分類方法類似，LLGC包含3個部分：1)構(gòu)造一個包含所有樣本的無向圖；2)求解相似度矩陣W；3)定義恰當(dāng)?shù)哪芰亢瘮?shù)以評價算法。能量函數(shù)是描述整個系統(tǒng)狀態(tài)的測度，也是評價算法性能的重要指標(biāo)。能量函數(shù)一般由損失函數(shù)和正則化項(xiàng)組成，其表達(dá)式為

式中α、β為正則化參數(shù)，損失函數(shù)用于保證得到的類別標(biāo)簽盡可能接近真實(shí)標(biāo)簽，正則化項(xiàng)可以保證圖的局部平滑，即保證特征相似的樣本得到相同的標(biāo)簽。在LLGC中，最小化能量函數(shù)能夠得到最佳的分類結(jié)果。由于LLGC算法在本質(zhì)上是一種標(biāo)簽傳遞算法，所以其主要思想是通過無窮次迭代將有標(biāo)簽樣本的信息傳遞給特征相似的近鄰樣本[12]，最終達(dá)到全局穩(wěn)定狀態(tài)。LLGC算法的具體步驟為

1)構(gòu)造一個包含全部樣本的無向圖，建立圖的鄰接矩陣W。為防止樣本點(diǎn)將自身標(biāo)簽不斷傳遞給自身，當(dāng)i≠j時 ，W=exp(?(x?x)2/2σ2)，其中ijij σ為常數(shù)；當(dāng)i=j時 ，Wii=0。

2)通過鄰接矩陣W得到概率傳播矩陣S=D?1/2WD?1/2，其中D是一個對角矩陣，對角線元素

3)對概率矩陣F(0)進(jìn)行初始化標(biāo)注，使F(0)=Y；樣本間開始傳遞標(biāo)簽，按照如下公式更新每個樣本點(diǎn)標(biāo)簽的概率分布：F(t+1)=αSF(t)+(1?α)Y，不斷迭代直至收斂。

4)設(shè)F?為 {F(t)}在t趨于正無窮時的極限，那么可以得到樣本點(diǎn)xi的標(biāo)簽表達(dá)式：

步驟3)中的Y矩陣為全部樣本的標(biāo)簽信息，假設(shè)某樣本點(diǎn)xi屬于第j類，那么該樣本點(diǎn)對應(yīng)的類別標(biāo)簽為yij=1，第i行的其他位置和無標(biāo)簽樣本對應(yīng)的位置處均為0。

3 本文算法

在半監(jiān)督分類方法中，擴(kuò)充訓(xùn)練樣本集可以有效地解決有標(biāo)簽樣本數(shù)量有限的問題，如自訓(xùn)練方法和協(xié)同訓(xùn)練方法。本文受協(xié)同訓(xùn)練啟發(fā)，提出了一種結(jié)合LLGC和SVM的半監(jiān)督分類算法LL_SVM。LLGC算法在標(biāo)簽的傳遞過程中的隨機(jī)性導(dǎo)致了分類精度不理想、分類結(jié)果不穩(wěn)定的缺陷，SVM是監(jiān)督分類方法，在樣本較少的情況下，分類精度不理想，最終的分類結(jié)果與樣本的選擇關(guān)系較大。由于樣本是隨機(jī)選擇的，不一定具有代表性，因此SVM的分類結(jié)果也不穩(wěn)定。本章算法利用基于圖的分類方法與支持向量機(jī)方法結(jié)合，通過兩種分類器共同篩選具有代表性和類別確定的樣本，盡可能改善二者初始性能較弱的問題，充分挖掘未標(biāo)記樣本中蘊(yùn)藏的信息，輔助少量的已標(biāo)記樣本得到性能良好的分類器。具體實(shí)驗(yàn)步驟如下。

輸入帶標(biāo)簽訓(xùn)練樣本集Dl={(x1,y1),(x2,y2),···,(xl,yl)} ，無標(biāo)簽樣本集U={xl+1,xl+2,···,xn},其中整體訓(xùn)練樣本集 χ=Dl∪U，類別標(biāo)記矩陣Y。

1)使用Dl進(jìn)行SVM分類器訓(xùn)練，獲得分類器HSVM；

2)使用分類器HSVM對U中的無標(biāo)簽樣本類別進(jìn)行預(yù)測，得到預(yù)測標(biāo)簽LSVM；

3)基于樣本集χ，計(jì)算所有樣本之間的相似度，獲得樣本的鄰接矩陣W；

4)基于樣本標(biāo)記矩陣Y，使用LLGC算法預(yù)測樣本集U中未標(biāo)記樣本的類別，得到預(yù)測標(biāo)簽LLLGC；

5)保留預(yù)測標(biāo)簽一致的樣本，加入到已標(biāo)記樣本集Dl，訓(xùn)練SVM分類器；

6)使用該分類器對測試樣本進(jìn)行分類，對算法進(jìn)行評價。

輸出測試樣本的預(yù)測標(biāo)簽和評價指標(biāo)。

算法的流程圖如圖3所示。

圖3 LLGC_SVM算法流程

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用2個經(jīng)典的高光譜數(shù)據(jù)集進(jìn)行仿真：1992年夏季在美國西北部印第安納州農(nóng)林混合實(shí)驗(yàn)場拍攝的AVIRIS高光譜圖像數(shù)據(jù)集的一部分和應(yīng)用成像光譜儀在帕維亞大學(xué)上空獲得的Pavia高光譜數(shù)據(jù)集。兩圖像的大小均為像素，其中AVIRIS高光譜圖像的光譜值區(qū)間大約在0.41～2.45 μm，空間分辨率為20 m，光譜分辨率為10 nm，圖像的原始波段為220個，去除信噪比較低和不能被水反射的20個波段后實(shí)際參與圖像處理的波段共200個。其監(jiān)督圖像如圖4(a)所示。Pavia高光譜圖像光譜值區(qū)間大約在0.43～0.86 μm，空間分辨率為1.3 m，原始波段為115個，去除15個噪聲波段后實(shí)際參與圖像處理的波段共103個。其監(jiān)督圖像如圖4(b)所示。

圖4 實(shí)驗(yàn)數(shù)據(jù)集示意

4.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)仿真條件：電腦處理器為Intel(R) Core(TM) i7-2630QM，6G RAM，64位windows10操作系統(tǒng)，MATLAB軟件版本為matlab2019b。每次實(shí)驗(yàn)進(jìn)行10次取平均值作為實(shí)驗(yàn)結(jié)果。

4.3 評價準(zhǔn)則

混淆矩陣(confusion matrix)是表示高光譜圖像分類精度的一種標(biāo)準(zhǔn)格式，其具體表現(xiàn)形式為式中：mij(i=1,2,…,N,j=1,2,…,N)表示第i類樣本被錯分為第j類的總像元個數(shù)；N為所有類別的總個數(shù)。mii(i=1,2,…,N)為被準(zhǔn)確劃分類所屬類別的像元數(shù)，mii越大則說明分類精度越高[13]。通過混淆矩陣可以得到3個評價指標(biāo)：總體分類精度(overall accuracy，OA)，平均分類精度(average accuracy，AA)和Kappa系數(shù)。

假設(shè)N為總的類別數(shù)，n為樣本總數(shù)，mii為第i類分類正確的樣本數(shù)，mi+表示第i行的所有m值求和。則總體分類精度OA的計(jì)算方法為

平均分類精度AA的計(jì)算方法為

Kappa系數(shù)的計(jì)算方法為

OA、AA和Kappa系數(shù)越大，說明分類效果越好。

4.4 實(shí)驗(yàn)結(jié)果和分析

為了驗(yàn)證本文所提方法的有效性，在印第安農(nóng)林和帕維亞大學(xué)這兩個高光譜據(jù)集上進(jìn)行仿真，總共對4種算法進(jìn)行了對比，包括經(jīng)典的SVM算法，經(jīng)典的LLGC算法，文獻(xiàn)[14]中提出的KNN_LLGC算法和本文提出的結(jié)合LLGC和SVM的半監(jiān)督分類算法LL_SVM算法。KNN_LLGC算法首先選取訓(xùn)練樣本的近鄰標(biāo)簽，然后通過對比KNN算法確定的近鄰標(biāo)簽和LLGC算法確定的近鄰標(biāo)簽，取出預(yù)測結(jié)果相同樣本并加入訓(xùn)練集，然后使用LS-SVM分類器對測試樣本進(jìn)行分類，算法中的近鄰數(shù)目取20個。標(biāo)準(zhǔn)SVM采用徑向基核函數(shù)，采用“one-againest-rest”多分類算法，懲罰因子C以及核參數(shù)σ通過網(wǎng)格搜索法在[10, 103] 和 [10-2, 102]中選取最優(yōu)值。LLGC算法中的參數(shù)α以及對比實(shí)驗(yàn)中的高斯核寬度σ設(shè)定為 α=0.99， σ=0.11，迭代次數(shù)為5次。

表1為4種算法在Indian Pines數(shù)據(jù)集分類中的性能對比，評價標(biāo)準(zhǔn)為OA、AA和Kappa系數(shù)。實(shí)驗(yàn)選取總樣本中的10%作為訓(xùn)練樣本，其余為測試樣本，每類訓(xùn)練樣本中選取10個作為有標(biāo)簽訓(xùn)練樣本，用于模擬小樣本的實(shí)驗(yàn)條件。圖5顯示了4種方法的分類結(jié)果。

表1 Indian Pines高光譜圖像分類結(jié)果

圖5 Indian Pines數(shù)據(jù)集分類結(jié)果

從表1可以看出，在該數(shù)據(jù)集上，KNN_LLGC算法相對于傳統(tǒng)SVM算法的總體分類精度提高了4.72%，均分類精度提高了3.37%，Kappa系數(shù)提高了0.054 5，相對于傳統(tǒng)LLGC算法總體分類精度提高了1.41%，平均分類精度提高了1.59%，Kappa系數(shù)提高了0.017 1。本文提出的算法相對于KNN_LLGC算法效果有了極大的提升，總體分類精度提高了3.04%，平均分類精度提高了1.29%，Kappa系數(shù)提高了0.034 9，證明了在該數(shù)據(jù)集上本文算法的有效性。

從表2可以看出，傳統(tǒng)LLGC算法在小樣本條件下的分類精度很不穩(wěn)定，傳統(tǒng)SVM算法3種評價指標(biāo)的波動幅度相對于LLGC算法較小，在與KNN算法結(jié)合后總體分類精度的波動幅度相對SVM提高了0.11%，相對LLGC算法降低了1.3%；平均分類精度的波動幅度相對于SVM提高了0.51%，相對于LLGC算法降低了0.55%；Kappa系數(shù)的波動幅度相對于LLGC算法降低了0.159。本文提出的算法對比KNN_LLGC算法，總體分類精度的波動幅度降低了1.73%，平均分類精度的波動幅度降低了1.39%，Kappa系數(shù)的波動幅度降低了0.019 7。上述數(shù)據(jù)證明了在該數(shù)據(jù)集上本章算法對于分類穩(wěn)定性的提升效果。

表2 Indian Pines數(shù)據(jù)集分類結(jié)果的波動幅度

表3為上述4種算法在Pavia數(shù)據(jù)集分類中的性能對比，評價標(biāo)準(zhǔn)為OA、AA和Kappa系數(shù)。實(shí)驗(yàn)依然選取總樣本中的10%作為訓(xùn)練樣本，每類訓(xùn)練樣本中選取10個作為有標(biāo)簽訓(xùn)練樣本。圖6顯示了4種方法的分類結(jié)果。

表3 Pavia高光譜圖像分類結(jié)果

從表3可以看出，在該數(shù)據(jù)集上，KNN_LLGC算法相對于傳統(tǒng)SVM算法的總體分類精度提高了0.71%，Kappa系數(shù)提高了0.006 7，相對于傳統(tǒng)LLGC算法總體分類精度提高了0.14%，平均分類精度提高了0.57%，Kappa系數(shù)提高了0.001 1。本文提出的算法相對于KNN_LLGC算法效果有了極大的提升，總體分類精度提高了9.11%，平均分類精度提高了2.01%，Kappa系數(shù)提高了0.118 4，證明了在該數(shù)據(jù)集上本文算法的有效性。

圖6 Pavia數(shù)據(jù)集分類結(jié)果

通過上述兩組實(shí)驗(yàn)?zāi)軌蜃C明本文算法在不同數(shù)據(jù)集上的適應(yīng)性。在Indian Pines數(shù)據(jù)集和Pavia數(shù)據(jù)集上，本文采用的MCLU采樣策略和改進(jìn)的自適應(yīng)參數(shù)對高光譜圖像的分類精度相比于傳統(tǒng)算法有較大的提升。

從表4可以看出，傳統(tǒng)SVM和LLGC算法在小樣本條件下的分類精度很不穩(wěn)定，在與KNN算法結(jié)合后總體分類精度的波動幅度相對于SVM降低了5.31%，相對于LLGC算法降低了2.71%；平均分類精度的波動幅度相對于SVM降低了1.48%，相對于LLGC算法降低了2.1%；Kappa系數(shù)的波動幅度相對于SVM降低了0.063，相對于LLGC算法降低了0.325。本文提出的算法對比KNN_LLGC算法，總體分類精度的波動幅度降低了4.82%，Kappa系數(shù)的波動幅度降低了0.049 3。上述數(shù)據(jù)證明了在該數(shù)據(jù)集上本文算法對于分類穩(wěn)定性的提升效果。

表4 Pavia高光譜數(shù)據(jù)集分類結(jié)果的波動幅度

圖7、8給出了兩數(shù)據(jù)集中4種方法的標(biāo)記樣本數(shù)和分類結(jié)果的關(guān)系曲線對比。橫坐標(biāo)為每類地物的初始已標(biāo)記樣本數(shù)量s，縱坐標(biāo)為總體分類精度OA，已標(biāo)記樣本數(shù)取值：3、5、10、15、20、25?？梢钥闯觯谛颖緱l件下，本文提出的算法優(yōu)于其他3種算法，在實(shí)際工作中高光譜圖像往往面臨有標(biāo)簽樣本數(shù)較少的問題，本文算法可以在這種情況下表現(xiàn)更好。

圖7 Indian Pines數(shù)據(jù)集帶標(biāo)簽樣本數(shù)與OA的關(guān)系曲線

圖8 Pavia數(shù)據(jù)集帶標(biāo)簽樣本數(shù)與OA的關(guān)系曲線

5 結(jié)論

針對LLGC算法的缺陷，本文提出了一種結(jié)合了LLGC和SVM的半監(jiān)督分類算法，首先使用有標(biāo)簽樣本訓(xùn)練SVM分類器對無標(biāo)簽樣本進(jìn)行預(yù)測，然后使用全部樣本構(gòu)造類別標(biāo)記矩陣，通過LLGC算法對無標(biāo)簽樣本進(jìn)行預(yù)測，選取二者中預(yù)測結(jié)果相同的樣本加入訓(xùn)練樣本后重復(fù)上述步驟，直到到達(dá)預(yù)先設(shè)定的迭代次數(shù)。在Indian Pines和Pavia工程學(xué)院2組數(shù)據(jù)集上的實(shí)驗(yàn)證明了該算法能夠克服傳統(tǒng)LLGC算法和SVM算法的部分缺點(diǎn)，有效提高了分類精度及其穩(wěn)定度。