趙越，周萍

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

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

趙越，周萍

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

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

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

0 引言

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

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

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

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

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

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

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

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

1.2 主成分分析

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

1.3 核密度估計(jì)

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

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

通常采用均值為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)對(duì)數(shù)化log(xi)→xi;

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

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

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

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

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

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

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

2.2 計(jì)算方案

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

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

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

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

表1 分類(lèi)精度對(duì)比Tab.1Comparison of classification accuracy

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

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

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

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

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

3 結(jié)論

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

(2)針對(duì)傳統(tǒng)的基于均值－方差的K－means算法的不足，本文將對(duì)數(shù)－主成分變換和概率密度函數(shù)引入到K－means算法。實(shí)驗(yàn)表明，本文提出的算法克服了分類(lèi)結(jié)果對(duì)初值的依賴(lài)性，提高了分類(lèi)的穩(wěn)定性和分類(lèi)結(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)系電話(huà):13671139971。

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

2010－07－13;

2010－09－04