改進的K－means算法在遙感圖像分類中的應用

趙越，周萍

(中國地質大學(北京)地球科學與資源學院，北京100083)

改進的K－means算法在遙感圖像分類中的應用

趙越，周萍

(中國地質大學(北京)地球科學與資源學院，北京100083)

遙感圖像分類時，如果類別不明，K－means算法隨機選取不同初值會導致分類結果有較大的差異。針對此問題，提出了一種改進的K－means算法。首先對遙感數據進行對數變換;然后采用主成分變換，依據主成分貢獻率(≥85%)選擇參與分類的主成分數;根據第一主成分的概率密度函數確定初始分類數和初始分類中心，并確定初始分類標簽作為多個主成分的期望最大化(EM)分類算法所需初始值，避開了隨機選取初值的敏感問題。通過實驗數據驗證，本文方法的分類精度優于傳統的基于均值－方差的K－means算法。

K－means;對數變換;主成分變換;概率密度函數

0 引言

K－means是基于劃分的聚類算法。該算法簡單、快速，是一種得到最廣泛使用的聚類算法［1］，在高光譜遙感圖像的非監督分類中具有較強的實用性，并表現出明顯的優點。K－means以K為參數，把n個對象分為K個類別，以使類內具有較高的相似度、類間的相似度較低。根據一個類別中對象的平均值進行相似度的計算，對大數據集的處理，該算法是相對可伸縮和高效率的。但其缺點也非常明顯:①對初始值非常敏感，不同的初始值可能會導致不同的聚類結果［2］;②必須預先設定預計劃分類數K。

針對K－means的上述弱點，Stephen等［3］提出采用kd－tree為K－means賦初始值。先用kdtree估計數據在不同位置的密度，再用Katsavounidis算法修正選擇K－means的中心值，這種方法采用密度函數確定均值，是通過整個密度函數確定初始中心的比較完整的算法;但這種方法計算復雜、效率不高，而且對高維數據的效果不明顯。Lu等［4］用分等級的方法為K－means選擇聚類中心，該方法的核心是把聚類看成加權聚類問題，依據分等級的方法可以選擇更好的初始中心值;但用該方法采樣時容易受到粗差的影響，且效率不高。本文提出的改進的K－means，首先對多光譜數據進行對數變換以突顯或強化類型特征;然后進行主成分變換，采用核密度估算第一主成分的概率密度函數;根據概率密度函數確定初始分類數和相應的初始分類中心，通過迭代計算得到最終的分類圖。

1 改進的K－means算法

1.1 傳統的K－means算法

K－means算法是Mac Queen于1967年提出的，是至今運用最廣泛的聚類算法之一。對于一個觀測數據集X=(x1，x2，…，xn)，每個觀測值是d維的實向量，K－means聚類就是把n個觀測值分為K個子集(K≤n)，S=(s1，s2，…，sk)。具體過程如下:

(1)從全部數據中隨機選取K個數據作為初始中心;

(2)在第m次迭代中，對任一樣本X按如下的方法將其調整到K個類別中的某一類別中。對于所有的i≠j，i=1，2，…，K，如果，則，其中，是以為中心的類;

式中，Nj為Sj類中的樣本數;是按照使J最小的原則確定的，J的表達式為

1.2 主成分分析

多光譜數據用于分類研究和應用是當今遙感技術熱點之一，龐大的數據量往往會降低分類算法的效率。對多(高)光譜數據進行主成分變換［5］，根據各主成分的貢獻率選擇參與分類的主成分數，既實現了對數據的壓縮，也提高了分類效率。為了增強類別差異，一種有效的方法是先對觀測數據進行對數變換，然后進行主成分變換，最后再進行分類。

1.3 核密度估計

在統計學中，核密度估計是一種非參估計隨機變量概率密度函數的方法。如果“x1，x2，…xn”～f是互相獨立分布的隨機樣本，那么它的概率密度函數的密度估計近似為［6］

式中，k為某種密度核;h為平滑參數(也稱為帶寬)。

通常采用均值為0、方差為單位陣的標準正態分布為密度核，這樣密度估計只和參數h相關。有多種選擇帶寬h的方法，本文采用下面的帶寬公式，因為它最接近帶寬最優值［6］，即

式中，n為樣本數;δ為樣本標準偏差。

1.4 改進的K－means算法

改進的K－means算法的具體流程如下:

(1)對數化log(xi)→xi;

(2)應用1.2節原理進行主成分變換:(U1，U2，…，Uk)Txi→xi;

(3)采用核密度估算第一主成分的概率密度函數;依據概率密度函數的峰態確定初始分類數和相應的分類中心;對第一主成分進行K－means分類，獲得各類的標簽;

(5)按照K－means分類法進行分類，最后進行分類精度評定。

2 實驗與結果分析

2.1 實驗數據

實驗區位于亞利桑那州的Maricopa縣境內，主要地類包括綠地、水體、道路、裸地和居民建筑用地等。實驗采用的遙感數據是2004年3月17日獲取的QuickBird多波段圖像，圖像大小為317像素×315像素，空間分辨率為2.44 m，有4個波段(藍光、綠光、紅光和近紅外波段)。圖1為近紅外波段(R)、紅光波段(G)、綠光波段(B)組合的假彩色合成圖像。

圖1 QuickBird假彩色合成圖像Fig.1QuickBird false color composite image

2.2 計算方案

(1)使用傳統的基于均值－方差的K－means方法，對QuickBird原始數據(4個波段)多次采用K－means分類，從中選擇結果最優的一個(圖2);

(2)采用本文提出的改進的K－means算法分類(圖3)。相應的精度評價見表1。

圖2 傳統的均值－方差K－mean分類圖像Fig.2Image classified by traditional K－means based on mean－variance

圖3 改進的K－means分類圖像Fig.3Image classified by the advanced K－means

表1 分類精度對比Tab.1Comparison of classification accuracy

可以看出，本文提出的改進的K－means算法優于傳統的基于均值－方差的K－means算法。

基于均值－方差的K－means算法根據分類數據的均值μ和δ方差，將(μ－δ，μ+δ)分成K等分，獲得初始分類中心。此方法要求類別之間具有明顯的可分性，對于光譜特性相近的兩個類別往往存在誤分現象。本案例中，這種方法把水域和道路混為一個類。

本文提出的改進的K－means通過對數變換強化類型特征(比較原始數據第一主成分密度函數(圖4)和對數—主成分變換第一主成分直方圖(圖5(a))，進一步用對數－主成分變換后的第一主成分密度函數(圖5(a))確定初始分類數和相應的類型幾何中心，然后用一維K－means法針對第一主成分確定的初始分類標簽作為多維K－means方法的初始輸入。由于對數－主成分變換后第一主成分最大限度地包含了地物類型信息，峰態更明顯，根據其密度函數(圖5(a))確定初始分類數(6類:綠地、房屋、裸地1、裸地2、道路和水域)和類型幾何中心，避開了隨機選取初值，得到的初始標簽也最大限度地反映了類型的真實情況。此外，根據主成分貢獻率(≥85%)確定的主成分數(第一、二兩個主成分)，充分利用了多波段信息，壓縮了噪聲(可以看出圖5(c)和圖5(d)中第三、四主成分直方圖為單峰噪聲)，因此所得分類結果優于傳統的均值—方差K－means算法。

圖4 原始影像第一主成分密度函數Fig.4PC1 density function of the original image

圖5 對數－主成分變換后各主成分密度函數Fig.5Density fuction of the PCs after log－principal component transformation

3 結論

(1)K－means分類算法是動態聚類，具有一定的自適應性;但是分類結果易受到類別個數和初始分類中心的影響，因此分類結果取決于K值和初始分類中心的選擇。

(2)針對傳統的基于均值－方差的K－means算法的不足，本文將對數－主成分變換和概率密度函數引入到K－means算法。實驗表明，本文提出的算法克服了分類結果對初值的依賴性，提高了分類的穩定性和分類結果的準確性。

［1］Hartigan J A，Wong M A.A K－means Clustering Algorithm［J］.Applied Statistics，1979，28(1):100－108.

［2］Pena J M，Lozano J A，Larranaga P.An Empirical Comparison of Four Initialization Methods for the K－means Algorithm［J］.Pat-tern Recognition Letters，1999，20:1027－1040.

［3］Stephen J，Redmond，Heneghan C.A Method for Initialising the K－means Clustering Algorithm Using Kd－trees［J］.Pattern Recognition Letters，2007，28(8):965－973.

［4］Lu J F，Tang J B，Tang Z M，et al.Hierarchical Initialization Approach for K－means Clustering［J］.Pattern Recognition Letters，2008，29(6):187－795.

［5］Chang C I，Du Q，Sun T L，et al.A Joint Band Prioritization and Band Decorrelation Approach to Band Selection for Hyperspectral Image Classification［J］.IEEE Transactions on Geoscience and Remote Sensing，1999，37(6):2631－2641.

［6］Bowman A W，Azzalini A.Applied Smoothing Techniques for Data Analysis:the kernel approach with S－plus illustrations［M］.UK:Oxford University Press，1997.

An Improved K－means Algorithm for Remote Sensing Classification

ZHAO Yue，ZHOU Ping
(School of Earth Sciences and Resources，China University of Geosciences，Beijing 100083，China)

If the classification type is unknown，the K－means algorithm will randomly select the initial values，and different initial values will lead to differences in remote sensing image classification results.To solve such problems，this paper proposes an improved K－means algorithm.First，logarithmical transform is performed for the original data，and then principal component transformation is implemented.The number of principal components for the K－means algorithm is determined according to the contribution rate(≥85%).The proposed method can weaken the noise.Kernel density estimation can be used to determine the probability density function of the first principal component，from which the initial label for multi－dimensional K－means algorithm can be efficiently determined，and the sensitivity of the initial value selected at random can be avoided.Experiments show that the accuracy of the method proposed in this paper is higher than that of the traditional K－means based on meanvariance.

K－means;Logarithmical transform;Principal component transformation;Probability density function

TP 751.1

A

1001－070X(2011)02－0087－04

趙越(1986－)，女，碩士研究生，主要研究方向為遙感圖像處理。

周萍，女，博士，副教授，主要研究方向為遙感圖像處理。聯系電話:13671139971。

(責任編輯:劉心季)

2010－07－13;

2010－09－04