基于集對分析的遙感圖像K－均值聚類算法

謝相建，趙俊三，陳學輝，袁 思

(昆明理工大學國土資源工程學院，昆明 650093)

基于集對分析的遙感圖像K－均值聚類算法

謝相建，趙俊三，陳學輝，袁 思

(昆明理工大學國土資源工程學院，昆明 650093)

基于歐式距離的K－均值聚類算法是一種硬分類(把每個待辨識的對象嚴格地劃分到某個類中)方法，面對具有不確定性和混合像元特征的遙感圖像數據，傳統K－均值聚類算法很難得到滿意的分類結果。為解決這一難題，將集對分析(set pair analysis，SPA)理論推廣到遙感圖像聚類算法，通過引入一個能統一描述同一性、差異性和對立性的同異反(identical discrepancy contrary，IDC)聯系度，提出了基于IDC聯系度的改進的K－均值聚類算法。該方法克服了傳統K－均值算法硬分類的缺陷，可以有效地提高遙感圖像聚類精度。對Landsat5 TM衛星數據的聚類分析實驗表明，在含有混合像元的遙感圖像地物覆蓋分類中，改進的K－均值聚類方法的分類效果要優于傳統K－均值聚類方法。

集對分析;K－均值聚類算法;同異反聯系度;遙感圖像

0 引言

遙感圖像的分類根據分類過程中人工參與的程度可分為監督分類和非監督分類2大類。非監督分類也稱為聚類分析或點群分析。聚類就是不需要人工選擇訓練樣本，僅需極少的人工初始輸入，計算機按一定規則自動地根據像元光譜或空間特征等組成集群簇，然后分類器將每個簇與參考數據比較，將其劃分到某一類別中去［1］。在眾多聚類算法中，K－均值聚類以其簡單和高效的優點占據重要地位［2－4］，在遙感圖像信息提取中也得到了廣泛的應用［5－8］。K－均值聚類分析把每個待辨識的對象嚴格地劃分到某個類中，是一種硬分類。而遙感圖像信息的不確定性和混合像元問題使得對部分像元很難進行非此即彼的劃分。事實上，遙感數據所反映的大多數地物覆蓋在形態和類屬方面都存在著中介性，沒有明確的邊界來區分它們。例如，荒裸地和稀疏草地的邊界、城市和鄉村的邊界都是漸變的而且是非確定的。由 Dunn［9］提出、經 Bezdek［10］發展起來的模糊C均值(fuzzy C－means，FCM)聚類算法通過模糊隸屬度得到樣本屬于各個類別的不確定性程度，表達了樣本類屬的中介性，即建立起了樣本對于類別的不確定性的描述，能更客觀地反映現實世界。然而，從表面上看，隸屬度僅指明所研究對象屬于給定參考集的程度，并沒有指明所研究對象不屬于給定參考集的程度以及屬于還是不屬于參考集的不確定程度，實質上是在給出這種隸屬度的同時并沒有指明這種隸屬度的不確定性［11］。面對具有復雜對象不確定性特征的遙感圖像分類，傳統K－均值聚類算法很難得到滿意的結果。為此，本文借助于集對分析(set pair analysis，SPA)的基本思想，從SPA的聯系度入手，嘗試引入一個能統一描述同一性、差異性和對立性的同異反［12］(identical discrepancy contrary，IDC)聯系度 μ =a+bi+cj。IDC 聯系度中的“同一度”a等價于模糊集理論中的隸屬度;“對立度”c指明了所研究對象不屬于給定參考集的程度;“差異度”b則指明了屬于還是不屬于參考集的不確定程度［11］;i，j分別表示差異度和對立度系數。通過用IDC距離替代K－均值中的歐式距離來度量像元之間的差異性，建立基于SPA的K－均值算法，使其能夠對具有不確定性的遙感圖像數據進行有效的聚類分析。以一景Landsat5 TM衛星圖像數據為例，使用matlab模式分類工具箱進行聚類實驗，并與傳統K－均值算法聚類結果進行比較，驗證基于SPA改進的K－均值聚類算法的有效性和優越性。

1 集對分析

SPA理論是我國學者趙克勤［12］于1989年提出的一種新型的處理模糊和不確定知識的系統理論和方法，該方法能夠有效地分析和處理不精確、不一致、不完整等各種不確定信息，并從中發現隱含的知識，揭示潛在的規律。SPA從同一性、差異性和對立性3個方面研究2個事物的確定性與不確定性，全面刻畫了2個不同事物的聯系，是一種新的不確定性理論。其核心思想是認為任何系統都是由確定性和不確定性信息構成的，在這個系統中的確定性和不確定性可以相互聯系、相互影響、相互制約，甚至在一定條件下相互轉化，并借助于一個能充分體現上述思想的IDC聯系度μ=a+bi+cj來統一地描述模糊、隨機、中介和信息不完全所致的各種不確定性。

SPA的2個基本概念是“集對”及其“IDC聯系度”。所謂集對，就是具有一定聯系的2個集合所組成的“對”。設有聯系的2個集合X和Y，它們各具有n個屬性。可以組成一個集對 H(X，Y)，將X和Y的屬性進行劃分，如果其中s個屬性是相同的，p個屬性是相反的，f個屬性既不相同又不相對立(稱其為相異的)，則定義s/n為X和Y的同一度，f/n為X和Y的差異度，p/n為X和Y的對立度。用

表示X和Y之間的關系，式中:i為差異度系數，i∈［－1，1］;j為對立度系數，一般恒取 j= －1;s+f+p=n; μX－Y為集對 H(X，Y)的 IDC 聯系度。

記 a=s/n，b=f/n，c=p/n，則式(1)可寫成

式中a，b，c為聯系度分量，且滿足a+b+c=1。

式(2)為常用的三元聯系度表達式，其中a和c是相對確定的，而b是相對不確定的。這種相對性是由于客觀對象的復雜性和可變性以及對客觀對象認識與刻畫的主觀性和模糊性造成的不確定性，因而式(1)和式(2)是一種確定不確定結構函數，體現了確定不確定系統的對立統一關系，具有較深刻的方法論意義。當i和j取合理值時，式(1)和式(2)變為一個數值，稱這個數值為聯系數(記為μ')，根據聯系度的定義有 μ'∈［－1，1］。

2 改進的K－均值聚類算法

2.1 K－均值聚類法

K－均值(K－means)算法是一種極為普遍和簡單的基于劃分的聚類算法，有著悠久的發展歷史，曾被 Ball［13］，Lloyd［14］，MacQueen［15］和 Steinhaus［16］在各自不同的科學領域中提出。該算法的基本思想是:在n維歐幾里得(Euclid)空間中把n個樣本數據嚴格地分成K類。首先由用戶確定所要聚類的準確數目K，并隨機選擇K個初始聚類中心;然后根據數據與中心的距離來將它賦給距離最近的類，重新計算每個類內對象的平均值形成新的聚類中心;反復迭代，直到所有類簇的誤差平方和最小為止。

原始的K－均值聚類算法流程為:

設定輸入數據集 X={x1，x2，…，xn}，最大循環次數I，聚類數目K;輸出為 K個類簇 Cj，j=1，2，…，K。

步驟一，令I=1，隨機選取K個數據點作為K個類簇的初始簇中心mj(I);

步驟二，計算每一個數據點xi與這K個簇中心的距離 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個新的聚類中心，即

步驟四，計算目標函數J(C)，即

若目標函數J(C)取得最小，則返回mj(I)，k=1，2，…，K，算法結束;否則I=I+1，返回步驟二。

2.2 基于SPA改進的K－均值聚類方法

把SPA理論引入K－均值算法［17］，形成基于IDC距離的K－均值算法，其基本思想是:將待分類樣本 xl(l=1，2，…，n)和聚類中心 mk(k=1，2，…，K)都看做是具有T個屬性的集合X和M。首先，分別將待分類樣本xl與聚類中心mk組成集對H(X，M)，得到對應于第t個屬性的IDC聯系度，即

然后計算待分類樣本xl與聚類中心mk的IDC距離Dlk，即

比較樣本xl與各聚類中心mk之間的IDC距離Dlk的大小，若 Dl=min{Dlk，k=1，2，…，K}，則認為第l個樣本xl與第k個聚類中心mk最接近，故將xl歸入簇類k(此即IDC模式識別的擇近原則)。

該算法的具體實現步驟如下:

設定輸入數據集 X={x1，x2，…，xn}，聚類簇個數K，差異度系數i，最大循環次數I;輸出為滿足“誤差平方和最小”標準的K個聚類Ck。

步驟一，初始化。令I=1，隨機選取K個初始類簇中心 mk(I)，k=1，2，…，K;

步驟二，計算IDC聯系度。計算待分類樣本xl與聚類中心mk的IDC聯系度μlk;

步驟三，分配xl。計算樣本點xl與這K個簇中心之間的 IDC距離 Dlk，如果滿足 Dlk=min{Dlk，k=1，2，…，K}，則 xl∈Ck;

步驟四，修正簇中心Ck。令I=I+1，重新分配K個新的聚類中心，即

步驟五，計算誤差平方和J，即

步驟六，收斂判斷。如果J值收斂，則返回mk(I)，k=1，2，…，K;算法結束;否則，返回步驟二。

3 實驗與結果分析

為了評價改進算法的聚類性能，選取一景多光譜遙感圖像作為實驗數據，并與傳統K－均值算法進行比較。全部實驗均使用MATLAB 7.11在AMD Athlon642.20 GHz、內存為2G 的 Windows XP操作系統上進行。

實驗區為曲靖市陸良縣地區，實驗數據為2006年5月19日獲取的Landsat5 TM衛星圖像。TM圖像包含7個波段，圖像大小為400像元×400像元。參照文獻［18］，針對實驗區的特點，結合2006年曲靖市土地覆蓋利用狀況調查，確定聚類結果的類別組成如表1。

表1 實驗區土地覆蓋利用類別Tab.1 Classes of the land cover in the test area

實驗區內各類地物錯綜分布，較為復雜。為便于更好地對地物進行目視識別和聚類效果比較，將原始TM圖像按TM4(R)，TM3(G)和TM2(B)組合進行假彩色合成(圖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六個波段數據為分類對象，分別采用傳統K－均值算法和基于SPA改進的K－均值算法對其進行聚類，聚類簇個數K=6。

對改進算法中樣本像元與聚類中心之間各波段的IDC聯系度分量進行計算。其中，同一度為

根據SPA理論，式(2)必須滿足a+b+c=1，得到對應的差異度，即

最后由式(5)—(6)計算出滿足“誤差平方和最小”標準的K個聚類Ck。采用傳統K－均值算法的聚類結果如圖2(a)所示，基于SPA改進的K－均值算法(r=1.63，i=0.5)聚類結果如圖 2(b)所示。

圖2 傳統與改進K－均值算法聚類結果對比Fig.2 Comparison between clustering results of traditional and improved K －means algorithm

以實際土地覆蓋/土地利用狀況調查為基礎，對照TM假彩色合成圖像進行的驗證，并在圖像上均勻選取約6000個像元，判讀出其類別，作為實驗數據的地面實況(ground truth);然后在相同的位置上，分別讀出采用傳統K－均值聚類方法和改進的K－均值聚類方法結果圖上的類別。分類精度的評價指標以分類后的混淆矩陣為基礎，分別計算制圖精度、用戶精度、總體分類精度和Kappa系數［1］，與地面實況數據對比后，兩種算法分類結果見表2和表3。

表2 傳統K－均值算法聚類結果Tab.2 Clustering result of traditional K －means algorithm

表3 基于SPA改進的K－均值算法聚類結果Tab.3 Clustering result of SPA －based K －means algorithm

通過比較可以看出，與傳統K－均值聚類方法相比，利用基于SPA改進的K－均值聚類方法對含混合地物的土地覆蓋能得到更精確的劃分。比如，通過對比圖1和圖2(a)可以很清晰地看出，傳統K－均值算法把圖1中黑色橢圓附近的植被稀疏地錯分成了荒裸地;而在圖2(b)中改進的K－均值算法很清楚地將植被稀疏地與荒裸地劃分開來。同時，圖1中白色矩形框附近的部分建筑用地，在圖2(a)中被錯分成了植被稀疏地，而在圖2(b)中基于SPA改進的K－均值算法卻對建筑用地實現了較好的劃分。從表2和表3中2種分類算法結果比較也可以看出，對于建筑用地、植被稀疏地、草地和林地的錯分、漏分誤差，基于SPA的改進算法要低于傳統K－均值算法;對于總體分類精度和Kappa系數，基于SPA的改進算法明顯高于傳統K－均值算法。

4 結論

1)由于遙感研究對象特征的不確定性和混合像元問題，以歐式距離為度量函數的傳統K－均值聚類算法，在遙感圖像分類中很難得到滿意的結果。本文將集對分析(SPA)方法應用于K－均值聚類，提出了一種基于SPA改進的K－均值聚類方法。

2)改進的K－均值聚類方法利用同異反(IDC)聯系度來度量樣本間的相似性，嘗試解決傳統K－均值算法在含有混合像元的遙感圖像地物覆蓋分類中由硬分類造成分類精度不高的問題。實驗結果顯示，在傳統K－均值聚類算法面對具復雜特征的遙感圖像數據無法獲得較好聚類效果時，基于SPA改進的K－均值聚類算法仍然能夠獲得較好的聚類效果。

［1］趙英時，陳冬梅，楊立明，等.遙感應用分析原理與方法［M］.北京:科學出版社，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］.電子與信息學報，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］.系統工程與電子技術，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］劉小芳，何彬彬，李小文.基于半監督核模糊c－均值算法的北京一號小衛星多光譜圖像分類［J］.測繪學報，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］.計算機工程，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］趙克勤.集對分析的不確定性系統理論在AI中的應用［J］.智能系統學報，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］趙克勤.集對分析及其初步應用［M］.杭州:浙江科學技術出版社，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］趙克勤.基于集對分析的對立分類、度量及應用［J］.科學技術與辯證法，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］中華人民共和國質量監督檢驗檢疫總局和中國國家標準化管理委員.GB/T 21010－2007土地利用現狀分類［S］.北京:中國標準出版社，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－hui，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

國家自然科學基金“面向對象的土地利用空間多尺度耦合機理研究”(編號:41161062)資助。

10.6046/gtzyyg.2012.04.14

謝相建(1987－)，男，碩士研究生，主要從事遙感圖像處理方面的研究。E－mail:xiexjrs@gmail.com。

(責任編輯:劉心季)