基于半監督核模糊c-均值算法的北京一號小衛星多光譜圖像分類

劉小芳,何彬彬,李小文

1.電子科技大學地表空間信息技術研究所,四川成都610054;2.四川理工學院計算機學院,四川自貢643000

基于半監督核模糊c-均值算法的北京一號小衛星多光譜圖像分類

劉小芳1,2,何彬彬1,李小文1

1.電子科技大學地表空間信息技術研究所,四川成都610054;2.四川理工學院計算機學院,四川自貢643000

針對遙感圖像數據大多不服從高斯分布以及遙感圖像分類存在非線性、模糊性和標記數據少等問題,提出基于半監督核模糊c-均值算法的多光譜遙感圖像分類方法。首先,把半監督學習理論和核理論同時引入模糊c-均值算法,形成半監督核模糊c-均值算法。然后,用該算法與k-均值算法、最大似然算法、多類支持向量、半監督核支持向量、模糊c-均值算法、核模糊c-均值算法和半監督模糊c-均值算法對IRIS數據和北京一號小衛星多光譜圖像進行分類試驗。最后,對其分類結果進行評價。結果表明,對比其他分類算法,半監督核模糊c-均值算法能顯著提高分類精度。

遙感圖像分類;半監督核模糊c-均值算法;北京一號小衛星;核理論;半監督學習

1 引 言

由于傳統的無監督遙感圖像分類方法是根據數據集潛在的相似性和合適的測度,對輸入數據集進行聚類,這種方法有時得不到好的分類結果[1]。而監督分類需要大量的訓練數據集來設計分類器,如果選擇的訓練數據集不足以估計分類的參數,得到的分類效果也不好[2]。基于上述問題,提出半監督核模糊c均值算法,并以北京一號小衛星多光譜圖像為例進行分類試驗驗證。具體思路如下:①針對遙感數據存在大量的不確定性,采用模糊分類算法更能處理遙感數據的不確定性(模糊性)[3-4];②獲取遙感圖像對應地面上的大量標記(已知類別)數據困難,但并不是對地面的地物信息一無所知,獲取少量的標記數據是可行的,把半監督學習理論引入FCM算法,利用標記過的數據來指導分類,可以提高分類效果,為了減少遙感圖像分類對標記數據的要求,半監督分類方法是一種更有效的遙感圖像分類方法;③遙感圖像分類多數是非線性分類問題,把核理論引入FCM算法,使輸入特征向量被隱式地映射到高維空間,原來在低維空間非線性不可分模式在高維空間變成線性可分。

2 模糊c-均值算法

FCM算法是一種自組織學習方法,通過優化目標函數得到每個數據到類中心的隸屬度,從而決定數據的歸屬。設待分類的數據集為 Xn×q= [x1x2… xn]T?Rq,如果要將矩陣 X劃分為c個類別,Bezdek定義的模糊c-均值算法[5-6]的一般描述為

滿足

式中,Uc×n=[u1…uj…un]?Rc是隸屬度矩陣(模糊劃分矩陣),其中 uj=[u1j…uij…ucj]T;uij表示第j個數據xj屬于第i個類別中心vi的隸屬度; Vc×q=[v1…vi…vc]T?Rq是聚類中心矩陣,vi表示第i類的中心;m控制著隸屬度矩陣在類間的模糊程度,m→1,隸屬度矩陣趨向于硬劃分,m→∞,逐漸軟化隸屬度矩陣,使劃分變得越模糊,也可以根據試驗確定參數 m,實際應用中一般取[2,2.5][7];J(X,U,V)是誤差平方和目標函數; dij=‖vi-xj‖,i=1,2,…,c,j=1,2,…,n,這里dij選擇 Euclid距離。

聚類準則是求得適當的模糊劃分矩陣Uc×n= [uij]與聚類中心 Vc×q=[vi]使得目標函數J(X,U,V)達到極小值,根據拉格朗日乘數法求得uij、vi分別為

3 半監督核模糊c-均值算法

FCM算法是一種模糊模式識別方法,它是對傳統聚類方法的擴展。但是,當數據之間存在交疊時,FCM算法不是很有效[8-10]。該算法是一種無監督算法,不能有效利用標記數據引導未標記數據的分類。因此,這里提出一種更有效的半監督核模糊c-均值(semi-supervised kernel FCM, SSKFCM)算法,它是把核理論和半監督學習理論同時引入FCM算法而形成的。

3.1 核模糊c-均值算法

把核理論引入FCM算法,形成核模糊c-均值(kernel fuzzy c-means,KFCM)算法。核的基本思想是通過構造新的特征向量將輸入模式空間映射到高維特征空間,將原空間的非線性問題轉化為高維特征空間的線性問題進行處理[11-12]。KFCM算法采取核理論修改FCM算法的目標函數,用式(5)的誘導核距離代替 FCM算法在式(1)中的Euclid距離。KFCM算法的目標函數如式(6)所示。

特別的,對徑向基核函數 K(x,y)= exp(-‖x-y‖2/2σ2),當?x∈X,有 K(x,x)= 1,式(6)的 KFCM算法的目標函數簡化為式(7)。

式中

KFCM算法的最小化過程類似于 FCM算法。根據拉格朗日乘數法,為了求得適當U= [uij]、vi使目標函數J(X,U,V)達到極小值,即構造一個拉格朗日函數

由?L(X,U,V,λ)/?uij=0,得

即

把式(10)代入式(9),得模糊劃分矩陣U= [uij]為

由?L(X,U,V,λ)/?vi=0,得

得聚類中心vi為

3.2 半監督核模糊c-均值算法

如果在分類前已知少量數據的類別,則可以將這些數據作為標記數據引入到 FCM算法和KFCM算法形成半監督模糊 c-均值 (semisupervised FCM,SSFCM)算法[13]和半監督核模糊c-均值(SSKFCM)算法。半監督學習方法是使用少量標記數據指導未標記數據的分類。

待分類的數據為 X=[XbXu],其中,Xb和Xu分別表示已標記和未標記數據,nb和nu分別是Xb和 Xu的個數。模糊劃分矩陣U= [UbUu],其中,Ub是已標記數據 Xb的化分矩陣,取值按硬劃分賦值。Uu是未標記數據Xu的模糊化分矩陣,在算法的迭代過程中,對SSFCM和SSKFCM算法,Uu分別按式(3)和式(11)進行更新。因此,初始化的模糊劃分矩陣為U(0)= [Ub],迭代過程中的模糊化分矩陣為

3.3 SSKFCM算法的實現步驟

FCM、KFCM、SSFCM和SSKFCM算法的具體實現步驟相似,都是通過迭代原理實現,不同算法使用的計算公式不一樣。以SSKFCM算法為例,算法的具體實現步驟如下:

(1)給定有部分標記數據的數據 X= [XbXu]。

(2)初始化c、m、迭代截止誤差值ε、算法的最大迭代次數 Tmax。按式(2)的三個約束條件初始化模糊劃分矩陣U(0)=[Ub]中的。用標記數據 Xb的各類的中心初始化聚類中心

(3)修改迭代次數,t=t+1。

(4)根據式(8)的徑向基核函數,計算核函數矩陣 K(t)(xj,vi(t-1))。

(5)由U(t-1)=[UbUu(t-1)],根據式(12)計算聚類中心vi(t)。

(6)根據式(7),計算目標函數 J(t)(X, U(t-1),V(t-1)),判斷算法在迭代過程的收斂性。

模糊劃分矩陣U=[uij]包括了數據集 X的模糊分類結果,如果利用最大隸屬度原則,數據Xj歸屬于最大隸屬度這類,這個過程稱為去模糊化,得到硬劃分矩陣U。

4 試驗仿真與結果分析

為了驗證算法的有效性,試驗數據選取UCI數據庫的數據集 IRIS[14]和一個遙感圖像數據。試驗平臺為pentium4 1.8 GHz處理器、2 G內存、Windows XP操作系統。算法用C和MATLAB混合編程實現。用IRIS數據作為理論驗證數據,因為IRIS數據是國際公認的比較聚類方法效果好壞的典型數據之一。它包含了150個四維的3類數據,每類各50個樣本點,數據特點為一類數據與其他類數據離得較遠,另外兩類數據離得較近,而且有部分數據交疊。遙感數據來源于北京一號小衛星32 m的多光譜(綠B1:520～620 nm、紅B2:630～690 nm、近紅外B3:760～900 nm)的遙感圖像。該數據為經過幾何校正的二級產品,成像時間為2007-09-14T 11:30:29—11:34:59,圖像大小為1 390×1 500像素。分類特征分別為IRIS數據的4種屬性和北京一號小衛星圖像的3個波段。

試驗進行了三方面的分類算法比較:①與傳統的無監督分類的k均值(k-means,KM)算法和監督分類的極大似然(maximum likelihood,ML)算法[15]比較;②與FCM及其改進算法 KFCM、SSFCM的比較;③與利用核方法的多類支持向量機(multiclass support vector machines,MSVM)[16]和半監督支持向量機(semi-supervised support vector machines,S3VM)[17]的比較。

4.1 IRIS數據的試驗結果

對數據集IRIS,每類取65%作為訓練數據, 35%作為測試數據。對 ML、MSVM、S3VM、SSFCM和SSKFCM算法以訓練數據作為監督數據。MSVM、S3VM、KFCM和SSKFCM算法的核函數取式(8)的徑向基核函數,通過五重交叉驗證,MSVM和S3VM算法的核參數σ=0.5、正則化參數C=1,S3VM算法的無標記數據的正則化參數C＊=1;KFCM和SSKFCM算法的核參數σ =0.9。MSVM和S3VM算法采用原模式的對偶模式,用序貫最小優化方法實現,并用一對多分解方法擴展到多類SVM。幾種算法對IRIS數據的分類精度如表1所示。

表1 幾種算法對IRIS數據的分類精度Tab.1 Classification accuracy of several algorithms for IRIS data set

對IRIS數據的分類結果表明,有足夠訓練數據的情況下,監督分類的ML和MSVM算法的分類效果好于其他算法,但半監督分類的S3VM和SSKFCM算法也顯示了強的分類能力。

4.2 北京一號小衛星圖像的試驗仿真與結果分析

北京一號小衛星圖像分類流程如圖1所示。數據規格化處理選用數據標準化變換。評價指標以分類后的混淆矩陣為基礎,計算用戶精度、制圖精度、總體分類精度和kappa系數。

圖1 幾種算法的北京一號小衛星圖像分類流程Fig.1 Flowchart of the classification for Beijing-1 micro-satellite image by several algorithms

4.2.1 試驗結果

試驗數據中主要包括水體、植被、雪、戈壁四類地物,并且有些地物之間波譜特征存在一定交疊,很難進行線性分類。為了更好目視識別地物信息,假彩色合成按近紅外、紅和綠波段順序組合的圖像如圖2(a)所示。

對FCM算法,m=2,ε=10-6,Tmax=30。在無監督分類算法中,k-均值、FCM和KFCM算法的分類圖分別如圖2(b)～(d)所示。圖2(b)中, k-均值算法把水和部分帶陰影的植被分一類,把戈壁和雪分為一類,植被稀疏的為一類,生長旺盛的植被為一類。圖2(c)中,FCM算法對水體、雪、戈壁都得到較好的分類,但帶陰影的植被很多被錯分為水。圖2(d)中,KFCM算法比k-均值和FCM算法分類效果好,但也存在把少量帶陰影植被錯分為水和積雪較少的區域錯分為戈壁。

在監督分類和半監督分類算法中,水體、植被、雪、戈壁的標記數據分別為745、890、912和915個。最大似然分類和MSVM以這些標記數據作為訓練數據,而S3VM、SSFCM和SSKFCM算法以這些數據作為標記數據集 Xb。SSFCM和SSKFCM算法的參數m和ε與FCM算法相同。MSVM、S3VM、KFCM和SSKFCM算法的核函數取式(8)的徑向基核函數,通過五重交叉驗證, MSVM和S3VM算法的核參數σ=30、正則化參數C=100,S3VM算法的無標記數據的正則化參數C＊=100;KFCM和SSKFCM的核參數σ=1。最大似然、MSVM、S3VM、SSFCM和SSKFCM算法的分類圖像分別如圖2(e)～(i)所示。在圖2(e)中,最大似然算法把有些帶陰影植被和積雪較少的區域錯分為戈壁。在圖2(f)～(h)中, MSVM、S3VM和SSFCM算法對四類地物得到較好的區分,但也有少數植被分成水和戈壁,積雪較少的區域和戈壁也存在錯分現象。在圖2(i)中,SSKFCM算法對四類地物得到最好的區分,但SSKFCM算法也存在少量錯分現象,這種錯分現象比其他算法要少。圖2(j)表示分類圖2(b)～(i)中地物類別對應的顏色。

圖2 北京一號小衛星圖像和幾種算法的分類圖Fig.2 Beijing-1 micro-satellite image and the classification images of several algorithms on the image

4.2.2 結果對比與評價

為了定量評價幾種算法的分類效果,以分類后的混淆矩陣為基礎,計算用戶精度、制圖精度、總體分類精度和kappa系數。混淆矩陣是通過將感興趣區的每個地表真實像元的位置和類別與分類圖像中的相應位置和類別相比較計算的。這種感興趣區不包括已標記的數據集。水體、植被、雪和戈壁的感興趣區分別選取644、657、687和633個樣本數據。表2給出了SSKFCM算法的混淆矩陣。

表2 SSKFCM算法的混淆矩陣Tab.2 Classification confusion matrix of the SSKFCM algorithm

其他算法的感興趣區與SSKFCM算法相同。幾種算法的性能比較如表3所示。

遙感圖像分類的試驗結果表明:無監督分類的KM算法的分類精度低于FCM和KFCM算法,FCM算法的分類精度低于KFCM算法;監督分類的ML算法的分類精度低于MSVM算法;半監督分類的S3VM和SSFCM算法的分類精度低于SSKFCM算法。SSKFCM算法的分類精度最高。

由于原始的SVM算法是針對小樣本、非線性、高維數和局部極小點等兩類問題提出來的,從表1和表3可以看出MSVM和S3VM算法在處理小樣本集IRIS很占優勢。但在處理大數據集的遙感圖像數據時,MSVM和S3VM算法的分類結果不如SSKFCM算法,其主要原因:①由于多類SVM分類算法是由兩類SVM算法推廣而來,其本身存在如何提高推廣能力的問題,推廣到多類以后,多類SVM算法的不同最優化技術也產生不同的結果[17];②SVM算法在處理不可分情況引入懲罰參數C,以構造軟間隔的最優超平面來分開樣本,允許存在錯分,但錯分程度應盡可能的小,不同的錯分程度影響其推廣能力。在兩個分類試驗中,S3VM算法的結果遜于監督的MSVM算法的主要原因:MSVM算法的目標函數是凸問題,存在一個最小點;S3VM算法的目標函數中附加了無標記數據的懲罰項,使求解S3VM算法的目標函數變成一個非凸問題,存在多個極小點,尋找合適的解變得更加困難。文獻[18-19]深入討論了S3VM算法的非凸目標函數存在多個極小點的問題,以及非凸目標函數的幾種最優化實現技術。

對比IRIS數據和遙感圖像數據的分類結果,不管對小數據集的IRIS數據和大數據集的遙感圖像數據,SSKFCM算法都顯示了較強的分類能力。

表3 幾種算法的性能比較Tab.3 Performance comparison of several algorithms

5 結 論

由于遙感圖像數據大多不服從高斯分布,以及遙感圖像獲取地面大量標記數據困難、分類存在模糊性和非線性等問題,傳統分類方法在遙感圖像分類中存在一定局限。本文提出用半監督核模糊c-均值算法對北京一號小衛星多光譜圖像分類,取得了較好的效果。隨著核理論的引入,輸入特征向量被隱式地映射到高維空間,原來在低維空間非線性不可分模式在高維空間變成線性可分。通過半監督學習理論,在分類中使用標記數據指導未標記數據,從而提高了分類效果。因此,根據以上試驗結果分析,把半監督學習理論和核理論引入FCM算法而形成的SSKFCM算法,能夠提高北京一號小衛星遙感圖像分類的精度。

[1] J ENSEN J R.Introductory Digital Image Processing:a Remote Sensing Perspective[M].3rd ed.Delhi:Pearson Education,2005.

[2] ZEN G Zhiyuan.Research on Computer Classification of Satellite Images and Application in Geoscience [M]. Beijing:Science Press,2004.(曾志遠.衛星遙感圖像計算機分類與地學應用研究[M].北京:科學出版社,2004.)

[3] BOUCHACHIA A,PEDRYEZ W.Enhancement of Fuzzy Clustering by Mechanisms of Partial Supervision[J].Fuzzy Sets and Systems,2006,157(13):1733-1759.

[4] LIU Yanfang,LAN Zeying,LIU Yang,et al.Multi-scale Evaluation Method forUncertainty ofRemote Sensing Classification Based on Hybrid Entropy Model[J].Acta Geodaetica et Cartographica Sinica,2009,38(1):82-87. (劉艷芳,蘭澤英,劉洋,等.基于混合熵模型的遙感分類不確定性的多尺度評價方法研究 [J].測繪學報,2009, 38(1):82-87.)

[5] BEZDEK J C.Numerical Taxonomy with Fuzzy Sets[J]. Journal Mathemastical Biology,1974,1(1):57-71.

[6] BEZDEKJ C.Cluster Validity with Fuzzy Sets[J].Journal of Cybernetics,1973,3(3):58-73.

[7] PAL N R,BEZDEKJ C.On Cluster Validity for the Fuzzy c-means Model[J].IEEE Transactions Fuzzy on Systems, 1995,3(3):370-379.

[8] DUNN J C.A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact,Well-separated Clusters[J]. Journal of Cybernetics,1973,3(3):32-57.

[9] BEZDEK J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York:Plenum Press,1981.

[10] BEZDEKJ C,EHRLICH W F.FCM:The Fuzzy c-mean Clustering Algorithm[J].Computers and Geosciences, 1984,10(2-3):191-203.

[11] SCHOL KOPF B,SMOLA A J.Learning with Kernels [M].Cambridge:MIT Press,2002.

[12] GIROLAMI M.Mercer Kernel-based Clustering in Feature Space[J].IEEE Transactions on Neural Networks,2002, 13(3):780-784.

[13] BENSAID A M,BEZDEK J C,HALL L O,et al. Partially Supervised Fuzzy c-means Algorithm for Segmentation of MR Images[C]∥Proceedings of SPIE,Science of Artificial Neural Networks.San Diego:SPIE,1992: 522-528.

[14] ASUNCION A,NEWMAN D J.UCI Machine Learning Repository[DB/OL].[2010-01-18].http:∥www.ics. uci.edu/～mlearn/MLRepository.html.

[15] RICHARDS J A.Remote Sensing Digital Image Analysis [M].Berlin:Springer-Verlag,1999.

[16] HSU C W,LIN CJ.A Comparison of Methods for Multiclass Support Vector Machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-440.

[17]CHI M,BRUZZONE L.Semisupervised Classification of Hyperspectral Images by SVMs Optimized in the Primal [J]. IEEE Transactions on Geoscience and Remote Sensing,2007,45(6):1870-1880.

[18] CHAPELLE O,CHI M,ZIEN A.A Continuation Method for Semisupervised SVMs[C]∥Proceedings of the 23rd InternationalConference on MachineLearning. New York:ACM,2006:185-192.

[19] SINDHWANI V,KEERTHI S,CHAPELLE O.Deterministic Annealing for Semi-supervised Kernel Machines [C]∥Proceedings of the 23rd International Conference on Machine Learning.New York:ACM,2006:841-848.

Classification for Beijing-1 Micro-satellite’s Multispectral Image Based on Semisupervised Kernel FCM Algorithm

LIU Xiaofang1,2,HE Binbin1,LI Xiaowen1
1.Institute of Geo-spatial Information Science and Technology,University of Electronic Science and Technology of China,Chengdu 610054,China;2.Department of Computer Science and Technology,Sichuan University of Science and Engineering,Zigong 643000,China

Most of remote sensing image data do not satisfy to Gauss distribution,and still the problems of the nonlinear,fuzziness and in lack of labeled data exist in the remote sensing image classification.A semi-supervised kernel fuzzy c-means(SSKFCM)algorithm is proposed to overcome these disadvantages.First,the SSKFCM algorithm is formed by involving semi-supervised learning technique and kernel method into the standard fuzzy c-means(FCM)algorithm.Then,IRIS data set and Beijing-1 micro-satellite’s multispectral images are classified by those algorithms,such as k-Means(K M),maximum likelihood(ML),multiclass support vector machines (MSVM),semi-supervised support vector machines(S3VM),FCM,kernel FCM(KFCM),semi-supervised FCM (SSFCM)and SSKFCM.Finally,the classification results are estimated by corresponding indexes.The results indicate that the SSKFCM algorithm significantly improved the classification accuracy of remote sensing images compared with the others.

remote sensing image classification;semi-supervised kernel fuzzy c-means algorithm;Beijing-1 microsatellite;kernel method;semi-supervised learning

LIU Xiaofang(1969—),female,PhD candidate,associate professor,majorsin remote sensing image processing and pattern recognition.

1001-1595(2011)03-0301-06

TP751

A

國家863計劃(2007AA12Z227);國家自然科學基金(40701146);北京一號小衛星開放基金

(責任編輯:雷秀麗)

2010-01-05

2010-08-12

劉小芳(1969—),女,博士生,副教授,主要研究方向為遙感圖像處理、模式識別。

E-mail:lxf1969@163.com.