謝相建,趙俊三,陳學(xué)輝,袁 思
(昆明理工大學(xué)國(guó)土資源工程學(xué)院,昆明 650093)
基于集對(duì)分析的遙感圖像K-均值聚類算法
謝相建,趙俊三,陳學(xué)輝,袁 思
(昆明理工大學(xué)國(guó)土資源工程學(xué)院,昆明 650093)
基于歐式距離的K-均值聚類算法是一種硬分類(把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某個(gè)類中)方法,面對(duì)具有不確定性和混合像元特征的遙感圖像數(shù)據(jù),傳統(tǒng)K-均值聚類算法很難得到滿意的分類結(jié)果。為解決這一難題,將集對(duì)分析(set pair analysis,SPA)理論推廣到遙感圖像聚類算法,通過引入一個(gè)能統(tǒng)一描述同一性、差異性和對(duì)立性的同異反(identical discrepancy contrary,IDC)聯(lián)系度,提出了基于IDC聯(lián)系度的改進(jìn)的K-均值聚類算法。該方法克服了傳統(tǒng)K-均值算法硬分類的缺陷,可以有效地提高遙感圖像聚類精度。對(duì)Landsat5 TM衛(wèi)星數(shù)據(jù)的聚類分析實(shí)驗(yàn)表明,在含有混合像元的遙感圖像地物覆蓋分類中,改進(jìn)的K-均值聚類方法的分類效果要優(yōu)于傳統(tǒng)K-均值聚類方法。
集對(duì)分析;K-均值聚類算法;同異反聯(lián)系度;遙感圖像
遙感圖像的分類根據(jù)分類過程中人工參與的程度可分為監(jiān)督分類和非監(jiān)督分類2大類。非監(jiān)督分類也稱為聚類分析或點(diǎn)群分析。聚類就是不需要人工選擇訓(xùn)練樣本,僅需極少的人工初始輸入,計(jì)算機(jī)按一定規(guī)則自動(dòng)地根據(jù)像元光譜或空間特征等組成集群簇,然后分類器將每個(gè)簇與參考數(shù)據(jù)比較,將其劃分到某一類別中去[1]。在眾多聚類算法中,K-均值聚類以其簡(jiǎn)單和高效的優(yōu)點(diǎn)占據(jù)重要地位[2-4],在遙感圖像信息提取中也得到了廣泛的應(yīng)用[5-8]。K-均值聚類分析把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某個(gè)類中,是一種硬分類。而遙感圖像信息的不確定性和混合像元問題使得對(duì)部分像元很難進(jìn)行非此即彼的劃分。事實(shí)上,遙感數(shù)據(jù)所反映的大多數(shù)地物覆蓋在形態(tài)和類屬方面都存在著中介性,沒有明確的邊界來區(qū)分它們。例如,荒裸地和稀疏草地的邊界、城市和鄉(xiāng)村的邊界都是漸變的而且是非確定的。由 Dunn[9]提出、經(jīng) Bezdek[10]發(fā)展起來的模糊C均值(fuzzy C-means,F(xiàn)CM)聚類算法通過模糊隸屬度得到樣本屬于各個(gè)類別的不確定性程度,表達(dá)了樣本類屬的中介性,即建立起了樣本對(duì)于類別的不確定性的描述,能更客觀地反映現(xiàn)實(shí)世界。然而,從表面上看,隸屬度僅指明所研究對(duì)象屬于給定參考集的程度,并沒有指明所研究對(duì)象不屬于給定參考集的程度以及屬于還是不屬于參考集的不確定程度,實(shí)質(zhì)上是在給出這種隸屬度的同時(shí)并沒有指明這種隸屬度的不確定性[11]。面對(duì)具有復(fù)雜對(duì)象不確定性特征的遙感圖像分類,傳統(tǒng)K-均值聚類算法很難得到滿意的結(jié)果。為此,本文借助于集對(duì)分析(set pair analysis,SPA)的基本思想,從SPA的聯(lián)系度入手,嘗試引入一個(gè)能統(tǒng)一描述同一性、差異性和對(duì)立性的同異反[12](identical discrepancy contrary,IDC)聯(lián)系度 μ =a+bi+cj。IDC 聯(lián)系度中的“同一度”a等價(jià)于模糊集理論中的隸屬度;“對(duì)立度”c指明了所研究對(duì)象不屬于給定參考集的程度;“差異度”b則指明了屬于還是不屬于參考集的不確定程度[11];i,j分別表示差異度和對(duì)立度系數(shù)。通過用IDC距離替代K-均值中的歐式距離來度量像元之間的差異性,建立基于SPA的K-均值算法,使其能夠?qū)哂胁淮_定性的遙感圖像數(shù)據(jù)進(jìn)行有效的聚類分析。以一景Landsat5 TM衛(wèi)星圖像數(shù)據(jù)為例,使用matlab模式分類工具箱進(jìn)行聚類實(shí)驗(yàn),并與傳統(tǒng)K-均值算法聚類結(jié)果進(jìn)行比較,驗(yàn)證基于SPA改進(jìn)的K-均值聚類算法的有效性和優(yōu)越性。
SPA理論是我國(guó)學(xué)者趙克勤[12]于1989年提出的一種新型的處理模糊和不確定知識(shí)的系統(tǒng)理論和方法,該方法能夠有效地分析和處理不精確、不一致、不完整等各種不確定信息,并從中發(fā)現(xiàn)隱含的知識(shí),揭示潛在的規(guī)律。SPA從同一性、差異性和對(duì)立性3個(gè)方面研究2個(gè)事物的確定性與不確定性,全面刻畫了2個(gè)不同事物的聯(lián)系,是一種新的不確定性理論。其核心思想是認(rèn)為任何系統(tǒng)都是由確定性和不確定性信息構(gòu)成的,在這個(gè)系統(tǒng)中的確定性和不確定性可以相互聯(lián)系、相互影響、相互制約,甚至在一定條件下相互轉(zhuǎn)化,并借助于一個(gè)能充分體現(xiàn)上述思想的IDC聯(lián)系度μ=a+bi+cj來統(tǒng)一地描述模糊、隨機(jī)、中介和信息不完全所致的各種不確定性。
SPA的2個(gè)基本概念是“集對(duì)”及其“IDC聯(lián)系度”。所謂集對(duì),就是具有一定聯(lián)系的2個(gè)集合所組成的“對(duì)”。設(shè)有聯(lián)系的2個(gè)集合X和Y,它們各具有n個(gè)屬性??梢越M成一個(gè)集對(duì) H(X,Y),將X和Y的屬性進(jìn)行劃分,如果其中s個(gè)屬性是相同的,p個(gè)屬性是相反的,f個(gè)屬性既不相同又不相對(duì)立(稱其為相異的),則定義s/n為X和Y的同一度,f/n為X和Y的差異度,p/n為X和Y的對(duì)立度。用
表示X和Y之間的關(guān)系,式中:i為差異度系數(shù),i∈[-1,1];j為對(duì)立度系數(shù),一般恒取 j= -1;s+f+p=n; μX-Y為集對(duì) H(X,Y)的 IDC 聯(lián)系度。
記 a=s/n,b=f/n,c=p/n,則式(1)可寫成
式中a,b,c為聯(lián)系度分量,且滿足a+b+c=1。
式(2)為常用的三元聯(lián)系度表達(dá)式,其中a和c是相對(duì)確定的,而b是相對(duì)不確定的。這種相對(duì)性是由于客觀對(duì)象的復(fù)雜性和可變性以及對(duì)客觀對(duì)象認(rèn)識(shí)與刻畫的主觀性和模糊性造成的不確定性,因而式(1)和式(2)是一種確定不確定結(jié)構(gòu)函數(shù),體現(xiàn)了確定不確定系統(tǒng)的對(duì)立統(tǒng)一關(guān)系,具有較深刻的方法論意義。當(dāng)i和j取合理值時(shí),式(1)和式(2)變?yōu)橐粋€(gè)數(shù)值,稱這個(gè)數(shù)值為聯(lián)系數(shù)(記為μ'),根據(jù)聯(lián)系度的定義有 μ'∈[-1,1]。
K-均值(K-means)算法是一種極為普遍和簡(jiǎn)單的基于劃分的聚類算法,有著悠久的發(fā)展歷史,曾被 Ball[13],Lloyd[14],MacQueen[15]和 Steinhaus[16]在各自不同的科學(xué)領(lǐng)域中提出。該算法的基本思想是:在n維歐幾里得(Euclid)空間中把n個(gè)樣本數(shù)據(jù)嚴(yán)格地分成K類。首先由用戶確定所要聚類的準(zhǔn)確數(shù)目K,并隨機(jī)選擇K個(gè)初始聚類中心;然后根據(jù)數(shù)據(jù)與中心的距離來將它賦給距離最近的類,重新計(jì)算每個(gè)類內(nèi)對(duì)象的平均值形成新的聚類中心;反復(fù)迭代,直到所有類簇的誤差平方和最小為止。
原始的K-均值聚類算法流程為:
設(shè)定輸入數(shù)據(jù)集 X={x1,x2,…,xn},最大循環(huán)次數(shù)I,聚類數(shù)目K;輸出為 K個(gè)類簇 Cj,j=1,2,…,K。
步驟一,令I(lǐng)=1,隨機(jī)選取K個(gè)數(shù)據(jù)點(diǎn)作為K個(gè)類簇的初始簇中心mj(I);
步驟二,計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)xi與這K個(gè)簇中心的距離 d(xi,mj(I)),i=1,2,…,n;j=1,2,…,K;如果滿足 d(xi,mj(I))=min{d(xi,mj(I)),j=1,2,…,K},則 xi∈Cj;
步驟三,重新分配K個(gè)新的聚類中心,即
步驟四,計(jì)算目標(biāo)函數(shù)J(C),即
若目標(biāo)函數(shù)J(C)取得最小,則返回mj(I),k=1,2,…,K,算法結(jié)束;否則I=I+1,返回步驟二。
把SPA理論引入K-均值算法[17],形成基于IDC距離的K-均值算法,其基本思想是:將待分類樣本 xl(l=1,2,…,n)和聚類中心 mk(k=1,2,…,K)都看做是具有T個(gè)屬性的集合X和M。首先,分別將待分類樣本xl與聚類中心mk組成集對(duì)H(X,M),得到對(duì)應(yīng)于第t個(gè)屬性的IDC聯(lián)系度,即
然后計(jì)算待分類樣本xl與聚類中心mk的IDC距離Dlk,即
比較樣本xl與各聚類中心mk之間的IDC距離Dlk的大小,若 Dl=min{Dlk,k=1,2,…,K},則認(rèn)為第l個(gè)樣本xl與第k個(gè)聚類中心mk最接近,故將xl歸入簇類k(此即IDC模式識(shí)別的擇近原則)。
該算法的具體實(shí)現(xiàn)步驟如下:
設(shè)定輸入數(shù)據(jù)集 X={x1,x2,…,xn},聚類簇個(gè)數(shù)K,差異度系數(shù)i,最大循環(huán)次數(shù)I;輸出為滿足“誤差平方和最小”標(biāo)準(zhǔn)的K個(gè)聚類Ck。
步驟一,初始化。令I(lǐng)=1,隨機(jī)選取K個(gè)初始類簇中心 mk(I),k=1,2,…,K;
步驟二,計(jì)算IDC聯(lián)系度。計(jì)算待分類樣本xl與聚類中心mk的IDC聯(lián)系度μlk;
步驟三,分配xl。計(jì)算樣本點(diǎn)xl與這K個(gè)簇中心之間的 IDC距離 Dlk,如果滿足 Dlk=min{Dlk,k=1,2,…,K},則 xl∈Ck;
步驟四,修正簇中心Ck。令I(lǐng)=I+1,重新分配K個(gè)新的聚類中心,即
步驟五,計(jì)算誤差平方和J,即
步驟六,收斂判斷。如果J值收斂,則返回mk(I),k=1,2,…,K;算法結(jié)束;否則,返回步驟二。
為了評(píng)價(jià)改進(jìn)算法的聚類性能,選取一景多光譜遙感圖像作為實(shí)驗(yàn)數(shù)據(jù),并與傳統(tǒng)K-均值算法進(jìn)行比較。全部實(shí)驗(yàn)均使用MATLAB 7.11在AMD Athlon642.20 GHz、內(nèi)存為2G 的 Windows XP操作系統(tǒng)上進(jìn)行。
實(shí)驗(yàn)區(qū)為曲靖市陸良縣地區(qū),實(shí)驗(yàn)數(shù)據(jù)為2006年5月19日獲取的Landsat5 TM衛(wèi)星圖像。TM圖像包含7個(gè)波段,圖像大小為400像元×400像元。參照文獻(xiàn)[18],針對(duì)實(shí)驗(yàn)區(qū)的特點(diǎn),結(jié)合2006年曲靖市土地覆蓋利用狀況調(diào)查,確定聚類結(jié)果的類別組成如表1。
表1 實(shí)驗(yàn)區(qū)土地覆蓋利用類別Tab.1 Classes of the land cover in the test area
實(shí)驗(yàn)區(qū)內(nèi)各類地物錯(cuò)綜分布,較為復(fù)雜。為便于更好地對(duì)地物進(jìn)行目視識(shí)別和聚類效果比較,將原始TM圖像按TM4(R),TM3(G)和TM2(B)組合進(jìn)行假彩色合成(圖1,其中黑色橢圓附近為植被稀疏地,白色矩形框附近為建筑用地)。
圖1 TM4(R),TM3(G),TM2(B)假彩色合成圖像Fig.1 False color image composed with TM4(R),TM3(G)and TM2(B)
以TM圖像的TM1—TM5,TM7六個(gè)波段數(shù)據(jù)為分類對(duì)象,分別采用傳統(tǒng)K-均值算法和基于SPA改進(jìn)的K-均值算法對(duì)其進(jìn)行聚類,聚類簇個(gè)數(shù)K=6。
對(duì)改進(jìn)算法中樣本像元與聚類中心之間各波段的IDC聯(lián)系度分量進(jìn)行計(jì)算。其中,同一度為
根據(jù)SPA理論,式(2)必須滿足a+b+c=1,得到對(duì)應(yīng)的差異度,即
最后由式(5)—(6)計(jì)算出滿足“誤差平方和最小”標(biāo)準(zhǔn)的K個(gè)聚類Ck。采用傳統(tǒng)K-均值算法的聚類結(jié)果如圖2(a)所示,基于SPA改進(jìn)的K-均值算法(r=1.63,i=0.5)聚類結(jié)果如圖 2(b)所示。
圖2 傳統(tǒng)與改進(jìn)K-均值算法聚類結(jié)果對(duì)比Fig.2 Comparison between clustering results of traditional and improved K -means algorithm
以實(shí)際土地覆蓋/土地利用狀況調(diào)查為基礎(chǔ),對(duì)照TM假彩色合成圖像進(jìn)行的驗(yàn)證,并在圖像上均勻選取約6000個(gè)像元,判讀出其類別,作為實(shí)驗(yàn)數(shù)據(jù)的地面實(shí)況(ground truth);然后在相同的位置上,分別讀出采用傳統(tǒng)K-均值聚類方法和改進(jìn)的K-均值聚類方法結(jié)果圖上的類別。分類精度的評(píng)價(jià)指標(biāo)以分類后的混淆矩陣為基礎(chǔ),分別計(jì)算制圖精度、用戶精度、總體分類精度和Kappa系數(shù)[1],與地面實(shí)況數(shù)據(jù)對(duì)比后,兩種算法分類結(jié)果見表2和表3。
表2 傳統(tǒng)K-均值算法聚類結(jié)果Tab.2 Clustering result of traditional K -means algorithm
表3 基于SPA改進(jìn)的K-均值算法聚類結(jié)果Tab.3 Clustering result of SPA -based K -means algorithm
通過比較可以看出,與傳統(tǒng)K-均值聚類方法相比,利用基于SPA改進(jìn)的K-均值聚類方法對(duì)含混合地物的土地覆蓋能得到更精確的劃分。比如,通過對(duì)比圖1和圖2(a)可以很清晰地看出,傳統(tǒng)K-均值算法把圖1中黑色橢圓附近的植被稀疏地錯(cuò)分成了荒裸地;而在圖2(b)中改進(jìn)的K-均值算法很清楚地將植被稀疏地與荒裸地劃分開來。同時(shí),圖1中白色矩形框附近的部分建筑用地,在圖2(a)中被錯(cuò)分成了植被稀疏地,而在圖2(b)中基于SPA改進(jìn)的K-均值算法卻對(duì)建筑用地實(shí)現(xiàn)了較好的劃分。從表2和表3中2種分類算法結(jié)果比較也可以看出,對(duì)于建筑用地、植被稀疏地、草地和林地的錯(cuò)分、漏分誤差,基于SPA的改進(jìn)算法要低于傳統(tǒng)K-均值算法;對(duì)于總體分類精度和Kappa系數(shù),基于SPA的改進(jìn)算法明顯高于傳統(tǒng)K-均值算法。
1)由于遙感研究對(duì)象特征的不確定性和混合像元問題,以歐式距離為度量函數(shù)的傳統(tǒng)K-均值聚類算法,在遙感圖像分類中很難得到滿意的結(jié)果。本文將集對(duì)分析(SPA)方法應(yīng)用于K-均值聚類,提出了一種基于SPA改進(jìn)的K-均值聚類方法。
2)改進(jìn)的K-均值聚類方法利用同異反(IDC)聯(lián)系度來度量樣本間的相似性,嘗試解決傳統(tǒng)K-均值算法在含有混合像元的遙感圖像地物覆蓋分類中由硬分類造成分類精度不高的問題。實(shí)驗(yàn)結(jié)果顯示,在傳統(tǒng)K-均值聚類算法面對(duì)具復(fù)雜特征的遙感圖像數(shù)據(jù)無法獲得較好聚類效果時(shí),基于SPA改進(jìn)的K-均值聚類算法仍然能夠獲得較好的聚類效果。
[1]趙英時(shí),陳冬梅,楊立明,等.遙感應(yīng)用分析原理與方法[M].北京:科學(xué)出版社,2003.Zhao Y S,Chen D M,Yang L M,et al.Principles and Methods of Remote Sensing Applications[M].Beijing:Science Press,2003(in Chinese).
[2]Huang Z X.Extensions to the K -means Algorithm for Clustering Large Data Sets with Categorical Values[J].Data Ming and Knowledge Discovery,1998,2(3):283 -297.
[3]Kaufman L,Rousseeuw P J.Finding Groups in Data:An Introduction to Cluster Analysis[M].Beijing:Wiley Online Library,1990.
[4]Hansen P,Jaumard B.Cluster Analysis and Mathematical Programming[J].Math Program,1997,79(1/3):191 - 215.
[5]鄧湘金,王彥平,彭海良.高分辨率遙感圖像的聚類[J].電子與信息學(xué)報(bào),2003,25(8):1073 -1080.Deng X J,Wang Y P,Peng H L.The Clustering of High Resolution of Remote Sensing Imagery[J].Journal of Electrics and Information Technology,2003,25(8):1073 -1080(in Chinese with English Abstract).
[6]鐘燕飛,張良培.遙感影像K均值聚類中的初始化方法[J].系統(tǒng)工程與電子技術(shù),2010,32(9):2009 -2014.Zhong Y F,Zhang L P.Initialization Methods for Remote Sensing Image Clustering Using K - means Algorithm[J].Journal of System Engineering and Electronics,2010,32(9):2009 -2014(in Chinese with English Abstract).
[7]劉小芳,何彬彬,李小文.基于半監(jiān)督核模糊c-均值算法的北京一號(hào)小衛(wèi)星多光譜圖像分類[J].測(cè)繪學(xué)報(bào),2011,40(3):301-306.Liu X F,He B B,Li X W.Classification for Beijing-1 Microsatellite’s Multispectral Image Based on Semi- supervised Kernel FCM Algorithm[J].Acta Geodaetica et Cartographica Sinica,2011,40(3):301 -306(in Chinese with English Abstract).
[8]哈斯巴干,馬建文,李啟青,等.模糊C-均值算法改進(jìn)及其對(duì)衛(wèi)星遙感數(shù)據(jù)聚類的對(duì)比[J].計(jì)算機(jī)工程,2004,30(11):14-15.Hasi B G,Ma J W,Li Q Q,et al.Improved Fuzzy C - mean Classifier and Comparison Study of Its Clustering Results of Satellite Remotely Sensed Data[J].Computer Engineering,2004,30(11):14-15(in Chinese with English Abstract).
[9]Dunn J C.A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well Separated Cluster[J].Cybernetics and Systems,1974,3:32 -57.
[10]Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York:Plenum Press,1981.
[11]趙克勤.集對(duì)分析的不確定性系統(tǒng)理論在AI中的應(yīng)用[J].智能系統(tǒng)學(xué)報(bào),2006,1(2):16 -25.Zhao K Q.The Application of Uncertainty Systems Theory of Set pair Analysis(SPA)in the Artificial Intelligence[J].CAAI Transactions on Intelligent Systems,2006,1(2):16 - 25(in Chinese with English Abstract).
[12]趙克勤.集對(duì)分析及其初步應(yīng)用[M].杭州:浙江科學(xué)技術(shù)出版社,2000.Zhao K Q.Set Pair Analysis and Its Preliminary Application[M].Hang Zhou:Zhejiang Science and Technology Press,2000(in Chinese).
[13]Ball G H.ISODATA,a Novel Method of Data Analysis and Pattern Classification[R].Menlo Park:DTIC Document,1965.
[14]Lloyd S.Least Squares Quantization in PCM[J].IEEE Transactions on Information Theory,1982,28(2):129 -137.
[15]MacQueen J.Some Methods for Classification and Analysis of Multivariate Observations[C]//In:Fifth Berkeley Symosium on Mathematics.Statistics and Probability.California:University of California Press,1967:281 -297.
[16]Steinhaus H.Sur la Division Des Corp Materiels en Parties[J].Bull Acad Polon Sci,1956,4(1):801 -804.
[17]趙克勤.基于集對(duì)分析的對(duì)立分類、度量及應(yīng)用[J].科學(xué)技術(shù)與辯證法,1994,11(2):26 -30.Zhao K Q.The Classification,Measurement and Applications Based on Set Pair Analysis[J].Science,Technology and Dialectics,1994,11(2):26 -30(in Chinese with English Abstract).
[18]中華人民共和國(guó)質(zhì)量監(jiān)督檢驗(yàn)檢疫總局和中國(guó)國(guó)家標(biāo)準(zhǔn)化管理委員.GB/T 21010-2007土地利用現(xiàn)狀分類[S].北京:中國(guó)標(biāo)準(zhǔn)出版社,2007.Standardization Administration and GeneralAdministration of Quality Supervision,Inspection and Quarantine of the People’s Republic of China.GB/T 21010 -2007 The Classification of Current Land Use[S].Beijing:China Standards Publishing House,2007(in Chinese).
SPA-based K-means Clustering Algorithm for Remote Sensing Image
XIE Xiang-jian,ZHAO Jun-san,CHEN Xue-h(huán)ui,YUAN Si
(Faculty of Land and Resource Engineering,Kunming University of Science and Technology,Kunming 650093,China)
K-means clustering algorithm is a kind of hard classification based on the Euclidean distance,with each data point assigned to a single cluster.Due to the uncertainty and mixed pixels in remote sensing image,it is difficult for the traditional K -means clustering algorithm to obtain satisfactory classification results.To overcome this drawback,the authors applied the SPA(set pair analysis)theory to the clustering algorithm of remote sensing image.The IDC(identical discrepancy contrary)connection degree model,which can descript unitarily the identity,discrepancy and opposition,was employed to improve K -means clustering algorithm.The improved algorithm has overcome the limitation of K -means clustering algorithm to certain extent.Clustering analysis experiments of Landsat TM image show that the improved K-means clustering algorithm is superior to K-means in classification accuracy of ground cover class components of mixed pixels.
set pair analysis(SPA);K-means clustering algorithm;identical discrepancy contrary(IDC)connection degree;remote sensing image
TP 751.1
A
1001-070X(2012)04-0082-06
2011-12-29;
2012-02-09
國(guó)家自然科學(xué)基金“面向?qū)ο蟮耐恋乩每臻g多尺度耦合機(jī)理研究”(編號(hào):41161062)資助。
10.6046/gtzyyg.2012.04.14
謝相建(1987-),男,碩士研究生,主要從事遙感圖像處理方面的研究。E-mail:xiexjrs@gmail.com。
(責(zé)任編輯:劉心季)