結合局部全局一致性和支持向量機的半監督分類方法

池辛格，王立國

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

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

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

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

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

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

1 支持向量機

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

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

圖1 線性可分情況下最優分類面

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

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

對w和b求偏導后帶入拉格朗日函數，即可得到對偶問題。此時優化問題已經轉化為最大化如下目標函數：

可以求得：

最終得到相應的判別函數式為

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

在有些情況下訓練集中會出現一些異常的樣本點，導致訓練集線性不可分。線性不可分樣本集的近似分類如圖2所示。

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

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

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

這種通過修正目標函數實現間隔最大化的過程被稱為“軟間隔最大化”。

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

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

稱K(xi,xj)為核函數(kernel function)。此時目標函數變為

相應的判別函數式為

常見的核函數有線性核、多項式核、拉普拉斯核、徑向基函數核等。

2 局部全局一致性算法

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

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

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

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

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

4)設F?為 {F(t)}在t趨于正無窮時的極限，那么可以得到樣本點xi的標簽表達式：

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

3 本文算法

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

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

1)使用Dl進行SVM分類器訓練，獲得分類器HSVM；

2)使用分類器HSVM對U中的無標簽樣本類別進行預測，得到預測標簽LSVM；

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

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

5)保留預測標簽一致的樣本，加入到已標記樣本集Dl，訓練SVM分類器；

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

輸出測試樣本的預測標簽和評價指標。

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

圖3 LLGC_SVM算法流程

4 實驗結果與分析

4.1 實驗數據

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

圖4 實驗數據集示意

4.2 實驗環境

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

4.3 評價準則

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

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

平均分類精度AA的計算方法為

Kappa系數的計算方法為

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

4.4 實驗結果和分析

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

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

表1 Indian Pines高光譜圖像分類結果

圖5 Indian Pines數據集分類結果

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

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

表2 Indian Pines數據集分類結果的波動幅度

表3為上述4種算法在Pavia數據集分類中的性能對比，評價標準為OA、AA和Kappa系數。實驗依然選取總樣本中的10%作為訓練樣本，每類訓練樣本中選取10個作為有標簽訓練樣本。圖6顯示了4種方法的分類結果。

表3 Pavia高光譜圖像分類結果

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

圖6 Pavia數據集分類結果

通過上述兩組實驗能夠證明本文算法在不同數據集上的適應性。在Indian Pines數據集和Pavia數據集上，本文采用的MCLU采樣策略和改進的自適應參數對高光譜圖像的分類精度相比于傳統算法有較大的提升。

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

表4 Pavia高光譜數據集分類結果的波動幅度

圖7、8給出了兩數據集中4種方法的標記樣本數和分類結果的關系曲線對比。橫坐標為每類地物的初始已標記樣本數量s，縱坐標為總體分類精度OA，已標記樣本數取值：3、5、10、15、20、25。可以看出，在小樣本條件下，本文提出的算法優于其他3種算法，在實際工作中高光譜圖像往往面臨有標簽樣本數較少的問題，本文算法可以在這種情況下表現更好。

圖7 Indian Pines數據集帶標簽樣本數與OA的關系曲線

圖8 Pavia數據集帶標簽樣本數與OA的關系曲線

5 結論

針對LLGC算法的缺陷，本文提出了一種結合了LLGC和SVM的半監督分類算法，首先使用有標簽樣本訓練SVM分類器對無標簽樣本進行預測，然后使用全部樣本構造類別標記矩陣，通過LLGC算法對無標簽樣本進行預測，選取二者中預測結果相同的樣本加入訓練樣本后重復上述步驟，直到到達預先設定的迭代次數。在Indian Pines和Pavia工程學院2組數據集上的實驗證明了該算法能夠克服傳統LLGC算法和SVM算法的部分缺點，有效提高了分類精度及其穩定度。