改進(jìn)Ｋ－ｍｅａｎｓ的空間聚類算法

摘 要：提出了基于K-means的四叉樹與Rlink樹的混合結(jié)構(gòu)樹，提高了Rlink樹的查詢性能，在K-means中采用均值—標(biāo)準(zhǔn)差確定初始聚類中心，提高了收斂速度，通過距離準(zhǔn)則函數(shù)來優(yōu)化K值，避免K值的盲目選取。與Rlink相比空間開銷代價有時略大，但換取了更高的性能，且數(shù)據(jù)量越多，此種結(jié)構(gòu)的整體性能越好，適合于海量數(shù)據(jù)。

關(guān)鍵詞：空間數(shù)據(jù)庫；Rlink樹；四叉樹；空間聚類;空間索引

中圖分類號：TP301．6 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)07-1995-03



Improved K-means clustering algorithm on space

ZHAO Wei1，2，ZHANG Shu2，LI Wenhui1

(1.College of Computer Science Technology， Jilin University， Changchun 130012， China；2.School of Computer Science Engineering， Changchun University of Technology， Changchun 130012， China)

Abstract:This paper presented a quick speed spatial indexing structure which was based on Rlink tree. And it used K-means algorithm in the structure. In K-means algorithm，adopted valuestandard deviation to ascertain the initial clustering centres to improve convergence speed and ascertain ultimate K value by distance criterion function to make K value most suitable.The structure sometimes consumes more storage than Rlink but gains better performance. Furthermore，data quantity more， this kind of structure overall performance is better.

Key words:spatial database；Rlink tree;quadtree；spatial clustering；spatial index structure

隨著計(jì)算機(jī)技術(shù)的發(fā)展，空間數(shù)據(jù)庫應(yīng)用范圍已經(jīng)擴(kuò)展到了機(jī)器人、計(jì)算機(jī)視覺、圖像識別、環(huán)境保護(hù)、地理信息處理等領(lǐng)域^[1]。為了提高空間數(shù)據(jù)的處理效率，空間數(shù)據(jù)庫必須利用有效的空間索引機(jī)制。常見的空間索引一般是采用自頂向下、逐級劃分空間的方法，比較有代表性的有BSP樹、KDB樹、R樹、R+樹、CELL樹、四叉樹和網(wǎng)型空間索引等^[2]。

聚類分析是提高空間索引性能的一種非常有效的方法。目前已有K均值、CURE、ISODATA等多種算法。這些算法多數(shù)依賴于初始解的選擇。當(dāng)初始解選擇不好時，會影響聚類質(zhì)量，降低空間檢索效率，且這些算法執(zhí)行結(jié)果與數(shù)據(jù)輸入次序有關(guān)^[3]。

本文采用均值—標(biāo)準(zhǔn)差的方法決定初始聚類中心，使用準(zhǔn)則函數(shù)優(yōu)化K值，改進(jìn)了K-means算法，并用此構(gòu)造R

link，從而提高了空間檢索的效率。

1 基本原理

1．1 K-means算法

定義1 K-means聚類問題：假設(shè)N個數(shù)據(jù)集合X={X1，…，Xn}是待聚類數(shù)據(jù)。其中：Xj={Xj1， …，Xjq}∈Rq， j=1，…，n。K均值聚類問題是要找到X的一個劃分Pk={C1，…，Ck}，使目標(biāo)函數(shù)f(Pk)=ki=lxl∈cid(xl，mi)最小。其中:mi=1/nixl∈cixl表示第i個簇的中心位置，i=1，…，k；ni是簇Ci中數(shù)據(jù)項(xiàng)的個數(shù)；d(xl，mi)表示xl到mi的距離。

K-means聚類算法屬于聚類分析方法中一種基本的且應(yīng)用最廣的劃分方法，是一種在無類標(biāo)號數(shù)據(jù)中發(fā)現(xiàn)簇和簇中心的方法^[4]。該算法的基本思想是：給定一個包含n個數(shù)據(jù)對象的數(shù)據(jù)庫，以及要生成簇的數(shù)目K，隨機(jī)選取K個對象作為初始的K個聚類中心；然后計(jì)算剩余各個樣本到每一個聚類中心的距離，把該樣本歸到離它最近的那個聚類中心所在的類，對調(diào)整后的新類使用平均值的方法計(jì)算新的聚類中心；如果相鄰兩次的聚類中心沒有任何變化，說明樣本調(diào)整結(jié)束且聚類平均誤差準(zhǔn)則函數(shù)已經(jīng)收斂。本算法在每次迭代中都要考察每個樣本的分類是否正確，若不正確，就要調(diào)整，在全部樣本調(diào)整完后，修改聚類中心，進(jìn)入下一次迭代。如果在一次迭代算法中，所有的樣本被正確分類，則不會有調(diào)整，聚類中心不會有變化。在算法迭代中值在不斷減小，最終收斂至一個固定的值。該準(zhǔn)則也是衡量算法是否正確的依據(jù)之一。

1．2 四叉樹與Rlink樹混合的結(jié)構(gòu)

四叉樹是2k叉樹。讓四叉樹的每個節(jié)點(diǎn)均指向一棵與其對應(yīng)索引空間相關(guān)聯(lián)的Rlink樹。實(shí)質(zhì)就是將一棵大的Rlink樹分解成多棵小的Rlink樹，將查詢盡可能限定在局部空間區(qū)域，從而提高查找性能。



混合結(jié)構(gòu)是由一棵深度為d的2k四叉樹Qt和n棵Rlink樹組成。其中設(shè)d>0，n=d-1i=0(2k)i，四叉樹Qt共有n個節(jié)點(diǎn)，按寬度遍歷方法進(jìn)行編號依次為Qt0，Qt1，…，Qtn-1。Qt將整個索引空間（S）分成n個d 級子空間（IS0，IS1，…，ISn-1）。每一級的所有子空間兩兩不相交，且一起構(gòu)成整個索引空間S。

n棵Rlink樹（Rt0，Rt1，…，Rtn-1）分別與四叉樹Qt的n個節(jié)點(diǎn)及四叉樹Qt劃分的n個子空間相關(guān)聯(lián)，[(i=0，1，…，n-1)，Qti←→Si←→Rti]。Si與Rti相關(guān)聯(lián)，即Rti用于索引屬于Si的空間目標(biāo)。

定義2 空間目標(biāo)r屬于Si。

r完全被Si所包圍，并且Si是所有包圍P的子空間中最小的。以圖1所示的二維空間為例，混合結(jié)構(gòu)由一棵深度為2的四叉樹和5棵Rlink樹組成，整個空間分成2級共5個子空間：I(xiàn)S0，IS1，IS2，IS3，IS4（IS0=IS1∪IS2∪IS3∪IS4），Rt0，Rt1，Rt2，Rt3和Rt4這5棵RLink樹分別與它們相關(guān)聯(lián)。

2 基于改進(jìn)的K-means構(gòu)建的Rlink算法

2．1 改進(jìn)的K-means算法

2．1．1 初始點(diǎn)的選取

由K均值算法可知，如果所選取的初始聚類中心在幾個分布密集區(qū)域的中心，其周圍的點(diǎn)容易分到最近的點(diǎn)，聚類收斂越快，需要迭代的次數(shù)越少^[7]。

要分析所有數(shù)據(jù)的分布情況，計(jì)算其分布密度，可以根據(jù)隨機(jī)函數(shù)的分布知識，聚類的數(shù)據(jù)應(yīng)主要分布在所有數(shù)據(jù)的均值附近。標(biāo)準(zhǔn)差是評價數(shù)據(jù)分布的一個重要指標(biāo)，假設(shè)所有數(shù)據(jù)的均值為μ，標(biāo)準(zhǔn)差為σ，則數(shù)據(jù)應(yīng)該主要分布在（μ-σ，μ+σ）之間。假設(shè)分類數(shù)為N，選擇初始分類點(diǎn)為（μ-σ，μ+σ）之間的N個等分點(diǎn)。設(shè)第i類的初始分類中心為mi， 則

mi=(μ-σ)+2σi/N;i=1，…，N

如果參與分類的是多維數(shù)據(jù)，如d維，則每個聚類初始聚類中心的各個向量應(yīng)在(μl-σl，μl+σl)之間，設(shè)第i類聚類初始中心值為｛mi1，mi2，…，mid｝，則有mil=(μl-σl)+2σil/N。

2．1．2 優(yōu)化K值的準(zhǔn)則函數(shù)

定義3 類際離散度。

令K={X，R}為空間聚類的聚類空間。其中:X={x1，x2，…，xn}，假設(shè)n個空間對象被聚類為k個簇，定義類際離散度為所有聚類中心到全域中心的距離之和，即L=ki=1|mi-m|。其中:L為類際離散度；m為全部樣本的均值；mi為簇Ci所含樣本的均值；k為所要聚類的個數(shù)。

定義4 類內(nèi)離散度。

令K={X，R}為空間聚類的聚類空間。其中:X={x1，x2，…，xn}，假設(shè)n個空間對象被聚類為k個簇，定義類內(nèi)距離為所有聚類簇內(nèi)部距離的總和，即D=ki=1p∈ci|p-mi|。其中:D為類內(nèi)離散度；p為任一空間對象，即樣本。

定義5 距離準(zhǔn)則函數(shù)。

令K={X，R}為空間聚類的聚類空間。其中:X={x1，x2，xn}，假設(shè)n個空間對象被聚類為k個簇，定義距離準(zhǔn)則函數(shù)為類內(nèi)離散度與類際離散度之商:

F(s，k)=D/L=ki=1|mi-m|/(ki=1p∈ci|p-mi|)

其中：F(s，k)為距離準(zhǔn)則函數(shù)。當(dāng)距離準(zhǔn)則函數(shù)F（s，k）達(dá)到最小值時，K為最優(yōu)解。

2．2 基于改進(jìn)的K-means構(gòu)建的Rlink算法

Rlink樹采用最小外接矩形來界定空間實(shí)體，其不可避免地導(dǎo)致約束矩形區(qū)重疊，而覆蓋區(qū)域的大小和區(qū)域的重疊程度是影響搜索性能的重要因素。受聚類算法啟發(fā)，引入新的節(jié)點(diǎn)分配原則，在建構(gòu)Rlink樹時，使用改進(jìn)的K-means 算法來代替?zhèn)鹘y(tǒng)Rlink樹的面積增量最小準(zhǔn)則，以減少Rlink樹的空間矩形的空白區(qū)域與重疊區(qū)域，從而大大提高空間查詢的效率。

它的基本思想是采用均值—標(biāo)準(zhǔn)差選取初始聚類中心。算法的基本思想是：

a）算出所有數(shù)據(jù)的均值假定為μ，標(biāo)準(zhǔn)差為σ。也就是說數(shù)據(jù)主要分布在（μ-σ，μ+σ）之間，在此區(qū)間由公式mi=(μ-σ)+2σi/N(i=1，…，N/M)選取K個點(diǎn)，即為初始聚類中心。其中K=N/M。

b）計(jì)算各個數(shù)據(jù)對象到各聚類中心的距離，把數(shù)據(jù)對象歸到離它最近的那個聚類中心所在的類。

c）對調(diào)整后的新類計(jì)算新的聚類中心，如果相鄰兩次的聚類中心沒有任何變化，說明數(shù)據(jù)對象調(diào)整結(jié)束。

d）K值是預(yù)先給定的，未必就是最優(yōu)解。基于類際離散度最大、類內(nèi)離散度最小的原則，使用準(zhǔn)則函數(shù)對K值進(jìn)一步優(yōu)化。

以確定的聚類中心為初始聚類中心，計(jì)算各個數(shù)據(jù)對象與初始聚類中心距離，并計(jì)算距離準(zhǔn)則函數(shù)，直到K大于或等于[N/M]。其中使準(zhǔn)則函數(shù)值最小的K值作為最終劃分聚類的個數(shù)。

e）將空間對象重新根據(jù)歐氏距離公式分配到相應(yīng)的聚類，更新各聚類中心，直到聚類結(jié)果不變。

在對空間對象分組時，基于改進(jìn)的K-means產(chǎn)生的分組要優(yōu)于基于面積增量最小準(zhǔn)則產(chǎn)生的分組，如圖2、3所示。

具體算法的實(shí)例分析如下：設(shè)N為R_Link樹某節(jié)點(diǎn)當(dāng)前擁有的子節(jié)點(diǎn)個數(shù)，m與M分別為R_Link樹中每個節(jié)點(diǎn)能容納的實(shí)體最小與最大個數(shù)。

輸入：N個d維待分類數(shù)據(jù){X1，X2，…，Xn}。其中Xi={Xi1， …，Xid}；待分類的簇數(shù)為K。

輸出：K個簇，使得類際離散度最大，而類內(nèi)離散度最小。

a)采用均值—標(biāo)準(zhǔn)差選擇K個初始聚類中心{c1，c2，…，ck}。其中：K的取值為[N/M]~[N/m]，初值為[N/M]；cj={cj1，cj2，…，cjd}。

b)根據(jù)歐氏距離公式，計(jì)算每個數(shù)據(jù)到各簇的距離，將各數(shù)據(jù)劃分到具有最小距離的簇中。其中距離計(jì)算公式為

其中：d(xi，mj)為第i個矢量數(shù)據(jù)到第j個聚類的距離。

c）根據(jù)分配的結(jié)果更新各聚類中心。

d）重復(fù)步驟b）和c），直到聚類結(jié)果不變。

e）計(jì)算類際離散度L=ki=1|mi-m|、類內(nèi)離散度D=ki=1p∈ci|p-mi|及計(jì)算距離準(zhǔn)則函數(shù)F(S，K)=L/D=(ki=1p∈ci|p-mi|)/ki=1|mi-m|。

重復(fù)上述步驟，直到K值大于或等于[N/m]。

f)選擇使距離準(zhǔn)則函數(shù)值最小的k值作為劃分聚類的個數(shù)，將空間對象按上述步驟b)~e)分配到相應(yīng)的聚類。

3 實(shí)驗(yàn)結(jié)果與性能分析

為了便于性能評價，在實(shí)驗(yàn)時選定三個參考對象，即R樹、Rlink樹和改進(jìn)的Rlink樹。其測試環(huán)境為Windows XP操作系統(tǒng)，CPU為賽揚(yáng)IV 1.7 GHz，內(nèi)存256 MB，磁盤盤頁大小1 024 Byte，采用隨機(jī)數(shù)據(jù)進(jìn)行性能測試。

本文進(jìn)行如下兩個實(shí)驗(yàn)：

a）將R樹、Rlink樹與改進(jìn)后的Rlink樹在查詢時間效率上作比較。

以深度為2的四叉樹為例，當(dāng)用于查詢的實(shí)驗(yàn)數(shù)據(jù)增加時，R樹、Rlink樹與改進(jìn)后的Rlink樹需要的頁面數(shù)都在不斷增加，如表1所示。本文給出了實(shí)驗(yàn)結(jié)果的圖像描述，如圖4所示。從圖4可以看出，在具有相同查詢數(shù)據(jù)的條件下，改進(jìn)后的Rlink樹在查詢上占用的頁面總數(shù)要優(yōu)于R樹與Rlink樹；當(dāng)樹的深度增加時，Leveli=3，4，5，…，k時，結(jié)果也是一致的。由于改進(jìn)后的Rlink樹在查詢相同數(shù)量的數(shù)據(jù)時占用的頁面數(shù)要少于R樹，查詢速度要優(yōu)于R樹與Rlink樹。

b）將R樹、Rlink樹和改進(jìn)后的Rlink樹進(jìn)行空間性能的比較。

本文仍然采用相同的隨機(jī)數(shù)據(jù)進(jìn)行空間性能測試，如表2所示。從圖5中可以看出，當(dāng)測試的隨機(jī)數(shù)數(shù)目相同時，無論改進(jìn)后的Rlink樹Leveli中i取何值，占用的頁面數(shù)都要多于R樹與Rlink樹。改進(jìn)后的Rlink樹的存儲空間開銷與四叉樹的深度成正比，一般比R樹、Rlink樹要大，但索引目標(biāo)數(shù)越多時，它們的存儲開銷越接近。因此，這個方法比較適合于海量數(shù)據(jù)。

就插入、刪除、查找效率而言，由于改進(jìn)后的Rlink樹采用四叉樹對整個索引空間進(jìn)行了劃分，且四叉樹節(jié)點(diǎn)所對應(yīng)的Rlink是基于空間聚類所構(gòu)造的，使Rlink各子節(jié)點(diǎn)緊湊、其聚類性能更高。其查詢、插入、刪除操作在一棵矮的具有高聚類性的Rlink樹上進(jìn)行，不再針對整個索引空間，而被限定在某些局部區(qū)域，因此其插入、刪除、查詢性能優(yōu)于Rlink樹。

4 結(jié)束語

本文針對Rlink樹允許索引空間重疊、多路查詢且各子節(jié)點(diǎn)越緊湊，聚類性能越高的特點(diǎn)，提出了基于空間聚類的四叉樹與Rlink樹的混合結(jié)構(gòu)，以提高查找、插入、刪除的效率。用四叉樹將整個索引空間劃分成多級子索引空間，用Rlink樹索引每級的每個子空間。采用K-means算法來構(gòu)造Rlink樹，并通過距離準(zhǔn)則函數(shù)優(yōu)化K值，使得Rlink樹各子節(jié)點(diǎn)緊湊、聚類性能高，達(dá)到了提高Rlink樹查詢效率的目的。

在今后的研究工作中，筆者將仍然以索引結(jié)構(gòu)為重點(diǎn)，可以選擇下列問題為研究方向:

a)高維(k>20)數(shù)據(jù)對象的索引結(jié)構(gòu)。

b)大數(shù)據(jù)量空間物體的存儲研究，怎樣在傳遞數(shù)據(jù)時減少磁盤訪問開銷。

c)空間查詢方法與傳統(tǒng)SQL語言的結(jié)合。

d)空間索引的分布化或并行化。

參考文獻(xiàn)：

［1］

陳述彭，魯學(xué)軍，周成虎.地理信息系統(tǒng)導(dǎo)論[M].北京：科學(xué)技術(shù)出版社， 2001.

[2]KIM M，EO S.Efficient indexing of moving objects using timebased partitioning with Rtree[C]//Proc of International Conference on Computational Science.2005:568-575.

[3]KANUNGO T，MOUNT D M，NETANYAHU N S，et al.An efficient K-means clustering algorithm:analysis and implementation[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2002，24(7):881-892.

[4]周水庚，周傲英，曹晶，等.一種基于密度的快速聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2002，37(11):12871292.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”