改進(jìn)的K－means算法在遙感圖像分類中的應(yīng)用

趙越，周萍

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

改進(jìn)的K－means算法在遙感圖像分類中的應(yīng)用

趙越，周萍

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

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

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

0 引言

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

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

1 改進(jìn)的K－means算法

1.1 傳統(tǒng)的K－means算法

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

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

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

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

1.2 主成分分析

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

1.3 核密度估計(jì)

在統(tǒng)計(jì)學(xué)中，核密度估計(jì)是一種非參估計(jì)隨機(jī)變量概率密度函數(shù)的方法。如果“x1，x2，…xn”～f是互相獨(dú)立分布的隨機(jī)樣本，那么它的概率密度函數(shù)的密度估計(jì)近似為［6］

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

通常采用均值為0、方差為單位陣的標(biāo)準(zhǔn)正態(tài)分布為密度核，這樣密度估計(jì)只和參數(shù)h相關(guān)。有多種選擇帶寬h的方法，本文采用下面的帶寬公式，因?yàn)樗罱咏鼛捵顑?yōu)值［6］，即

式中，n為樣本數(shù);δ為樣本標(biāo)準(zhǔn)偏差。

1.4 改進(jìn)的K－means算法

改進(jìn)的K－means算法的具體流程如下:

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

(2)應(yīng)用1.2節(jié)原理進(jìn)行主成分變換:(U1，U2，…，Uk)Txi→xi;

(3)采用核密度估算第一主成分的概率密度函數(shù);依據(jù)概率密度函數(shù)的峰態(tài)確定初始分類數(shù)和相應(yīng)的分類中心;對第一主成分進(jìn)行K－means分類，獲得各類的標(biāo)簽;

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

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

2.2 計(jì)算方案

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

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

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

圖3 改進(jìn)的K－means分類圖像Fig.3Image classified by the advanced K－means

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

可以看出，本文提出的改進(jìn)的K－means算法優(yōu)于傳統(tǒng)的基于均值－方差的K－means算法。

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

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

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

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

3 結(jié)論

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

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

［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－)，女，碩士研究生，主要研究方向?yàn)檫b感圖像處理。

周萍，女，博士，副教授，主要研究方向?yàn)檫b感圖像處理。聯(lián)系電話:13671139971。

(責(zé)任編輯:劉心季)

2010－07－13;

2010－09－04