動(dòng)態(tài)確定K值聚類算法的R-樹空間索引構(gòu)建*

胡昱璞，牛保寧

太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024

動(dòng)態(tài)確定K值聚類算法的R-樹空間索引構(gòu)建*

胡昱璞，牛保寧+

太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024

空間數(shù)據(jù)；R-樹；空間索引；聚類算法

1　引言

空間索引（spatial index)是根據(jù)空間數(shù)據(jù)的位置或數(shù)據(jù)之間的空間關(guān)系按照一定規(guī)則建立邏輯順序的數(shù)據(jù)結(jié)構(gòu)[1-2]，目的是快速定位空間數(shù)據(jù)，實(shí)現(xiàn)空間數(shù)據(jù)的高效存儲(chǔ)和管理?？臻g索引是空間數(shù)據(jù)庫(kù)的一種關(guān)鍵技術(shù)，其構(gòu)建方式和操作效率對(duì)空間數(shù)據(jù)庫(kù)的性能有直接影響。R-樹空間索引[1,3-4]是目前應(yīng)用最廣泛的空間索引結(jié)構(gòu)，它對(duì)空間數(shù)據(jù)的劃分和操作都是針對(duì)最小外界矩形（minimum bounding rectangle,MBR）[4-5]進(jìn)行的，是按照空間數(shù)據(jù)的分布組織的樹狀結(jié)構(gòu)。對(duì)同一組空間數(shù)據(jù)，有多種R-樹空間索引的構(gòu)建方式，構(gòu)建效率和操作效率有很大的差別。

目前，與聚類算法結(jié)合成為常用的R-樹空間索引構(gòu)建方式，主要存在以下問(wèn)題：

（1）空間聚類算法常采用基于劃分的聚類算法，聚類數(shù)和初始聚類中心預(yù)先設(shè)定，但是設(shè)定不同的聚類數(shù)和不同的初始聚類中心會(huì)有不同的聚類結(jié)果，不符合實(shí)際空間分布，對(duì)聚類結(jié)果影響較大。

（2）空間數(shù)據(jù)中離群數(shù)據(jù)較多，離群數(shù)據(jù)會(huì)導(dǎo)致聚類中心和數(shù)據(jù)劃分偏離，進(jìn)而影響聚類結(jié)果。

針對(duì)上述問(wèn)題，本文提出一種動(dòng)態(tài)確定k值的空間聚類算法（dynamical k-value spatial clustering algorithm,DKSC），該算法考慮實(shí)際空間數(shù)據(jù)分布的特點(diǎn)，動(dòng)態(tài)尋找最優(yōu)k值。從根節(jié)點(diǎn)開始將每個(gè)節(jié)點(diǎn)作為一個(gè)單獨(dú)整體進(jìn)行聚類劃分，將劃分后的類作為子節(jié)點(diǎn)并繼續(xù)劃分，自頂向下逐層構(gòu)建，并在聚類中心選取中采用新的方法，避免了離群數(shù)據(jù)的干擾，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法構(gòu)建的R-樹具有高效的查找效率。

本文的主要工作及貢獻(xiàn)如下：

（1）在R-樹構(gòu)建中首次采取動(dòng)態(tài)確定k值的聚類算法，使得形成的R-樹結(jié)構(gòu)緊湊，查找效率高。

（2）聚類過(guò)程中避免離群空間數(shù)據(jù)的干擾，聚類結(jié)果更符合實(shí)際。

本文組織結(jié)構(gòu)如下：第2章闡述近年來(lái)R-樹空間索引及空間聚類算法的研究情況；第3章闡述DKSC算法的思想及實(shí)現(xiàn)；第4章用實(shí)驗(yàn)驗(yàn)證了DKSC算法產(chǎn)生的R-樹空間索引的性能；第5章是總結(jié)與展望。

2　研究現(xiàn)狀

2.1構(gòu)建方式

R-樹的構(gòu)建方式有OBO（one by one）方式、預(yù)處理方式和聚類方式[6]。OBO方式也叫動(dòng)態(tài)插入方式，即逐個(gè)插入空間數(shù)據(jù)，不斷自底向上進(jìn)行構(gòu)建。預(yù)處理方式是對(duì)空間數(shù)據(jù)預(yù)先按照一定規(guī)則排列，然后進(jìn)行構(gòu)建。聚類方式是通過(guò)特定聚類算法對(duì)空間數(shù)據(jù)進(jìn)行空間劃分，將節(jié)點(diǎn)劃分后的子空間作為子節(jié)點(diǎn)自頂向下迭代構(gòu)建。

2.2相關(guān)工作

近些年，許多學(xué)者對(duì)R-樹空間索引進(jìn)行了深入的研究和改進(jìn)。

R+-樹[7]將存在交疊的節(jié)點(diǎn)分割成多個(gè)MBR，消除了節(jié)點(diǎn)MBR之間的交疊問(wèn)題，減少了多路查找的問(wèn)題，提高了查找效率。但同時(shí)也存在著缺陷，構(gòu)建過(guò)程中的節(jié)點(diǎn)分裂會(huì)向下和向上同時(shí)進(jìn)行，增加了樹的深度，算法的復(fù)雜度會(huì)提高。R*-樹[8]與R-樹算法基本一致，只是對(duì)構(gòu)建算法進(jìn)行了改進(jìn)，提出了重插入技術(shù)，在節(jié)點(diǎn)插入時(shí)有更加合理的選擇，提高了節(jié)點(diǎn)的空間利用率，減少了分裂次數(shù)，查找效率有所提高，但多路查找依舊存在，構(gòu)建時(shí)間也會(huì)少量增加。R+-樹和R*-樹的構(gòu)建方式均為OBO方式，整體效果都不理想。

對(duì)于海量的空間數(shù)據(jù)，該方式存在缺陷：（1）由空樹逐個(gè)插入空間數(shù)據(jù)，插入代價(jià)非常大；（2）每次插入數(shù)據(jù)，只是局部結(jié)構(gòu)優(yōu)化而非全局結(jié)構(gòu)優(yōu)化；（3）構(gòu)建的樹結(jié)構(gòu)不合理，節(jié)點(diǎn)MBR之間存在很多交疊。因此，針對(duì)靜態(tài)空間數(shù)據(jù)（數(shù)據(jù)變化較少，沒(méi)有頻繁的刪除和更新操作），Roussopoulos等人[9]提出Packed R-樹，預(yù)先根據(jù)空間數(shù)據(jù)的分布特征按照一定規(guī)則分組，在同一組內(nèi)的節(jié)點(diǎn)作為同一父節(jié)點(diǎn)的孩子節(jié)點(diǎn)，減少了節(jié)點(diǎn)之間的交疊和構(gòu)建復(fù)雜度。雖然在預(yù)處理后空間查找效率會(huì)相比OBO方式構(gòu)建的R-樹空間索引有所提高，但是在預(yù)處理過(guò)程中，占用的資源和消耗非常大，效果不理想。因此，假設(shè)空間數(shù)據(jù)是相對(duì)靜態(tài)的，在建立索引之前，才可對(duì)空間數(shù)據(jù)進(jìn)行預(yù)處理。

隨后，Brakatsoulas等人提出CR樹[10]，認(rèn)為R-樹空間索引構(gòu)建的本質(zhì)是一個(gè)聚類問(wèn)題，將R-樹操作中分裂算法改進(jìn)為聚類技術(shù)的多路分裂，從整體上提升了R-樹的效率。Liu等人[11]在構(gòu)建R-樹空間索引中結(jié)合改進(jìn)的K-means算法，構(gòu)建的R-樹空間索引具有更緊湊的結(jié)構(gòu)，但存在離群空間數(shù)據(jù)干擾。Wang[12]對(duì)K-medoids聚類算法進(jìn)行了改進(jìn)，遞歸構(gòu)建R-樹空間索引，預(yù)先設(shè)定初始聚類數(shù)并指定聚類中心，減少了節(jié)點(diǎn)MBR之間的交疊，構(gòu)建出的R-樹空間索引節(jié)點(diǎn)分配更合理，查找效率更高，但聚類結(jié)果受初始聚類中心的影響。Huang等人[13]提出了靜態(tài)自頂向下構(gòu)建R-樹空間索引的遞歸聚類方法，該方法在劃分空間數(shù)據(jù)時(shí)采用K-means算法，構(gòu)建R-樹時(shí)采用STLT方法，避免了OBO構(gòu)建方式中分裂節(jié)點(diǎn)帶來(lái)的缺陷。

2.3空間聚類

通過(guò)以上的研究發(fā)現(xiàn)，提高R-樹空間索引性能的關(guān)鍵在于它的構(gòu)建方式，在構(gòu)建中將空間上相近數(shù)據(jù)放在同一子樹下，這是典型的聚類問(wèn)題。因此，在構(gòu)建過(guò)程中使用聚類方式，使R-樹結(jié)構(gòu)更加緊湊，減少多路查找，提高空間查找效率。

基于劃分的聚類算法是將數(shù)據(jù)對(duì)象劃分為多個(gè)類，然后采用迭代重定位，不斷改進(jìn)劃分，符合空間聚類將空間相近數(shù)據(jù)盡可能聚為一類的思想，適合于R-樹空間索引。其中K-means和K-medoids是最具代表性的劃分聚類方法，與R-樹的結(jié)合也大大提高了R-樹空間索引的查找效率。

為了將K-means[11,14]算法應(yīng)用到R-樹空間索引構(gòu)建中，需對(duì)K-means算法改進(jìn)。根據(jù)MBR的特點(diǎn)，將初始聚類數(shù)指定為4，且這4個(gè)初始聚類中心為MBR的4個(gè)頂點(diǎn)，這與原始K-means算法隨機(jī)選取聚類中心不同。

改進(jìn)K-means聚類算法構(gòu)建R-樹的過(guò)程如下：

（1）以全部空間數(shù)據(jù)作為整體，取其MBR作為R-樹的根節(jié)點(diǎn)。

（2）以根節(jié)點(diǎn)MBR的4個(gè)頂點(diǎn)（k=4）作為初始聚類中心，并根據(jù)距離將空間數(shù)據(jù)劃分到最近的聚類中心。

（3）按照K-means算法，計(jì)算聚類中新的聚類中心，并重新劃分，不斷迭代聚類，直到聚類中心不變?yōu)橹?，形?個(gè)聚類Z1、Z2、Z3、Z4；否則迭代執(zhí)行步驟（3）。

（4）以Z1、Z2、Z3、Z4分別作為整體，執(zhí)行步驟（1），直到整個(gè)R-樹構(gòu)建完成。

通過(guò)聚類步驟，可以分析出在改進(jìn)K-means聚類方法中存在的問(wèn)題。首先，k值的選取是否合適對(duì)最終的結(jié)果影響很大；其次，k值確定后，聚類中心的選取也決定著聚類的好壞；且聚類存在著離群數(shù)據(jù)的干擾，如圖1所示，A、B、C、D為4個(gè)空間數(shù)據(jù)MBR，在選取聚類中心時(shí)，若按照K-means算法選取就會(huì)使M作為聚類中心，A、B、C、D就會(huì)受D影響成為同一個(gè)聚類，從而干擾聚類結(jié)果。

Fig.1　An example of outlier圖1　離群數(shù)據(jù)示例

K-medoids聚類算法與K-means聚類算法基本一致，只是在針對(duì)K-means中存在的離群數(shù)據(jù)問(wèn)題上，采用距離均值點(diǎn)最近的對(duì)象作為聚類中心，但是聚類結(jié)果仍然受k值影響，無(wú)法獲得符合實(shí)際的聚類。

因此，針對(duì)聚類算法中存在的選取聚類數(shù)不符合實(shí)際空間數(shù)據(jù)分布和易受離群數(shù)據(jù)影響的問(wèn)題，提出DKSC算法。

3　DKSC算法

3.1相關(guān)定義

為了方便說(shuō)明，首先進(jìn)行一些定義：

定義1（聚類中心選取）定義一個(gè)衡量鄰近對(duì)象的距離指標(biāo)R[15]，表示如下：

其中，n表示空間數(shù)據(jù)的數(shù)量；D表示給定的空間范圍面積，用di表示某數(shù)據(jù)到第i個(gè)數(shù)據(jù)的距離，若di≤R，將第i個(gè)數(shù)據(jù)記為該數(shù)據(jù)的鄰近對(duì)象，若di＞R，將其記為該數(shù)據(jù)的非鄰近對(duì)象。

給定r1,r2,…,rn為n個(gè)Rd空間數(shù)據(jù)的集合，假設(shè)cj為第j個(gè)類的聚類中心，則ri與cj的距離（距離函數(shù)）為：

在選取聚類中心時(shí)，先得到類中數(shù)據(jù)的均值點(diǎn)cj，之后計(jì)算均值點(diǎn)cj到該類其他數(shù)據(jù)的距離，根據(jù)距離指標(biāo)R得到cj的鄰近對(duì)象，并計(jì)算鄰近對(duì)象的均值點(diǎn)cj′，取距離cj′最近的空間數(shù)據(jù)為聚類中心，記為r=argmin(d(cj′,r))，其中r∈{rj1,rj2,…,rjm}。

例如，在圖1中首先選取點(diǎn)M為均值點(diǎn)，計(jì)算M的鄰近對(duì)象為A、B、C（D為非鄰近對(duì)象），然后計(jì)算鄰近對(duì)象A、B、C的均值點(diǎn)，并選取離均值點(diǎn)最近的B作為聚類中心，這樣聚類結(jié)果不受D影響。

定義2（聚類測(cè)度函數(shù)）聚類效果很大程度上取決于聚類測(cè)度函數(shù)。在聚類迭代過(guò)程中，把空間數(shù)據(jù)重新分配給距離最近的聚類中心所在的類，從而使得測(cè)度函數(shù)的值逐漸減小，最終收斂至一個(gè)固定的值，即聚類不再變化。

采用的聚類測(cè)度函數(shù)如下：

其中，p為Sj中的數(shù)據(jù)；k為聚類數(shù)；r為Sj的聚類中心。該函數(shù)設(shè)計(jì)的原則是令所有類中數(shù)據(jù)與聚類中心的距離平方誤差之和最小，滿足“類內(nèi)緊湊，類間距離差大”的準(zhǔn)則。

3.2算法描述

在不知道空間數(shù)據(jù)分布規(guī)律的情況下，預(yù)先設(shè)定聚類數(shù)k值，會(huì)強(qiáng)制按k值劃分空間數(shù)據(jù)，與實(shí)際空間分布不符，使聚類結(jié)果偏離實(shí)際，影響構(gòu)建的R-樹空間索引效率，即使聚類數(shù)k值符合實(shí)際，這k個(gè)聚類中心如何選取也是需解決的問(wèn)題。因此，考慮不預(yù)先設(shè)定聚類數(shù)與聚類中心，而在聚類過(guò)程中動(dòng)態(tài)確定，這樣獲取的k值與空間數(shù)據(jù)分布規(guī)律相符，聚類效果更好，構(gòu)建的R-樹索引節(jié)點(diǎn)MBR之間交疊少，減少多路查找，提高效率。

算法的基本思想是：以整個(gè)空間數(shù)據(jù)集合的MBR作為初始聚類（k=1）并根據(jù)算法1計(jì)算得到聚類中心。令聚類數(shù)k值開始遞增，隨著k值遞增聚類變化的過(guò)程為：取所有聚類中半徑最大的類，依據(jù)層次聚類中的分裂思想，找到類中距離聚類中心最遠(yuǎn)的空間數(shù)據(jù)和距離該數(shù)據(jù)最遠(yuǎn)的另一空間數(shù)據(jù)，將這兩個(gè)空間數(shù)據(jù)和其他類的聚類中心作為新的聚類中心，開始聚類；根據(jù)定義2計(jì)算每次聚類后的聚類測(cè)度函數(shù)值，k值每變化一次均與前一次的聚類測(cè)度函數(shù)值進(jìn)行比較，若函數(shù)值收斂，則當(dāng)前的狀態(tài)為聚類結(jié)果，k值為選取的聚類數(shù)，若不收斂，則k值繼續(xù)遞增。以這k個(gè)聚類作為根節(jié)點(diǎn)的子節(jié)點(diǎn)，再以每個(gè)子節(jié)點(diǎn)作為子樹的根節(jié)點(diǎn)進(jìn)行聚類構(gòu)建，遞歸進(jìn)行以上步驟，直到R-樹空間索引構(gòu)建完成。由于空間數(shù)據(jù)分布無(wú)規(guī)律，在聚類中會(huì)出現(xiàn)聚類結(jié)果數(shù)據(jù)不均等的情況，甚至相差很大，為了解決該問(wèn)題，對(duì)聚類結(jié)果進(jìn)行調(diào)整，將數(shù)據(jù)多于平均值的類中按照距離聚類中心由遠(yuǎn)及近的順序依次劃分給其余數(shù)據(jù)小于平均值的類，使得空間數(shù)據(jù)均衡分布在各類中。采用該算法判斷每次的聚類結(jié)果是否更好，從而決定是否進(jìn)行下一次的聚類。

算法1為空間聚類中心選取算法，第1行是計(jì)算均值點(diǎn)的過(guò)程，cj為聚類均值點(diǎn)。第2～7行得到所有鄰近對(duì)象，其中第3行計(jì)算cj與每個(gè)空間數(shù)據(jù)的距離，第4～6行判斷若為鄰近對(duì)象將其歸于集合M，第8行計(jì)算鄰近對(duì)象（存在于集合M中）的均值點(diǎn)cj′，在第9行中找到空間數(shù)據(jù)中距離鄰近對(duì)象均值點(diǎn)cj′最近的空間數(shù)據(jù)，作為聚類中心rc。若rc不唯一，則分別采用聚類測(cè)度函數(shù)進(jìn)行比較，選取函數(shù)值較小的rc。

算法1 GetClusteringCenter

算法2為動(dòng)態(tài)確定k個(gè)聚類的核心算法，主要功能是將n個(gè)空間數(shù)據(jù)劃分為k個(gè)聚類。第1～5行屬于初始化過(guò)程，以整個(gè)空間數(shù)據(jù)作為一個(gè)初始聚類，計(jì)算得到初始聚類中心c和初始聚類測(cè)度函數(shù)J1，選取距離聚類中心c最遠(yuǎn)的數(shù)據(jù)rm和距離rm最遠(yuǎn)的rn，并以rm和rn作為聚類中心重新聚類，此時(shí)k=2，計(jì)算得到J2。第6～14行為動(dòng)態(tài)確定k值的過(guò)程。第7行在所有聚類中選出半徑最大的聚類和聚類中心cmax，第8～11行選取類中距離cmax最遠(yuǎn)的數(shù)據(jù)rp和距離rp最遠(yuǎn)的數(shù)據(jù)rq，并以rp和rq及其他k-1個(gè)聚類中心（不包含cmax）作為新的聚類中心，此時(shí)k=k+1，開始聚類，形成k個(gè)聚類Z1,Z2,…,Zk。第12行調(diào)整聚類結(jié)構(gòu)：檢查每個(gè)聚類中的數(shù)據(jù)個(gè)數(shù)Ni(i=1,2,…,k)，若，則退出分配；若，則刪除距離聚類中心較遠(yuǎn)的個(gè)數(shù)據(jù)，并將刪除的數(shù)據(jù)根據(jù)距離分配到最近的Zj,j≠i中。重復(fù)迭代執(zhí)行該步驟，直到空間數(shù)據(jù)均勻分配，輸出聚類Z1,Z2,…,Zk。第13行計(jì)算聚類測(cè)度函數(shù)值Jk。若函數(shù)J達(dá)到收斂，則算法完畢，輸出Z；否則，執(zhí)行第7行。

算法2 DKSC

例如，以圖2中空間數(shù)據(jù)作為初始空間數(shù)據(jù)集合，首先選取距離均值點(diǎn)最近的r5初始聚類中心，且k=1；選取距離聚類中心r5最遠(yuǎn)的r12及距r12最遠(yuǎn)的r1作為聚類中心，開始聚類，r9、r10、r11劃分到r12中，r2,r3,…,r8劃分到r1，形成兩個(gè)聚類，此時(shí)k=2，計(jì)算聚類中心及聚類測(cè)度函數(shù)J2，如圖3所示；從兩個(gè)聚類中選出半徑最大的聚類和它的聚類中心r6，選取距離r6最遠(yuǎn)的r1和距離r1最遠(yuǎn)的r7，以r1、r7、r10作為聚類中心，重新聚類，如圖4，然后均勻分配，計(jì)算聚類測(cè)度函數(shù)J3；依次迭代執(zhí)行，k值不斷遞增，直到聚類測(cè)度函數(shù)收斂為止。

Fig.2　Aset of MBRs圖2　一組空間數(shù)據(jù)MBR集合

Fig.3　Two clusters圖3　形成2個(gè)聚類

Fig.4　Three clusters圖4　形成3個(gè)聚類

定理1聚類測(cè)度函數(shù)具有收斂性。

證明見文獻(xiàn)[16]?！?/p>

算法3為通過(guò)DKSC算法構(gòu)建R-樹的過(guò)程。第1行為對(duì)每一層空間劃分進(jìn)行聚類，第2～5行從根節(jié)點(diǎn)root開始逐層遞歸構(gòu)建中間節(jié)點(diǎn)。第3行將每個(gè)聚類分別作為R-樹的子節(jié)點(diǎn)。第4行為將子節(jié)點(diǎn)作為子樹根節(jié)點(diǎn)，開始構(gòu)建子樹。

算法3 Construction

4　實(shí)驗(yàn)結(jié)果及分析

4.1實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證通過(guò)DKSC算法構(gòu)建的R-樹空間索引（以下簡(jiǎn)稱DKSC R-樹）的性能，本文設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證，并同文獻(xiàn)[12-13]提出的方法進(jìn)行對(duì)比。這兩種方法已在第2章進(jìn)行了介紹，通過(guò)文獻(xiàn)[12]構(gòu)建的R-樹簡(jiǎn)稱為K-medoids R-樹，文獻(xiàn)[13]簡(jiǎn)稱為TDRC R-樹。

重點(diǎn)設(shè)計(jì)了以下3個(gè)實(shí)驗(yàn)：

實(shí)驗(yàn)1 R-樹構(gòu)建時(shí)間實(shí)驗(yàn)。比較DKSC R-樹、K-medoids R-樹和TDRC R-樹的構(gòu)建效率。

實(shí)驗(yàn)2 R-樹空間查找實(shí)驗(yàn)。比較DKSC R-樹、K-medoids R-樹和TDRC R-樹的空間查找響應(yīng)時(shí)間，目的是驗(yàn)證DKSC R-樹的區(qū)域查找效率。

實(shí)驗(yàn)3空間分布狀況對(duì)R-樹空間查找的影響。比較在實(shí)際空間數(shù)據(jù)集和隨機(jī)產(chǎn)生的數(shù)據(jù)集下DKSC R-樹空間索引的查找響應(yīng)時(shí)間，目的是驗(yàn)證DKSC R-樹是否在不同空間分布狀態(tài)下均能表現(xiàn)出較高的效率。

在空間查找實(shí)驗(yàn)中，采取針對(duì)R-樹空間索引最具有代表性的區(qū)域查找作為查找方法。查找區(qū)域的大小分別采用整個(gè)空間區(qū)域的1%和4%，實(shí)驗(yàn)頻率為每組30次，然后對(duì)每組數(shù)據(jù)集分別采用3種R-樹空間索引進(jìn)行實(shí)驗(yàn)，客觀得到3種索引的平均查找響應(yīng)時(shí)間。

4.2實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境：處理器Intel Core i7 3.6 GHz，內(nèi)存4 GB，硬盤500 GB，操作系統(tǒng)為Windows 7，編程語(yǔ)言為Java，IDE為MyEclipse 8.6。

數(shù)據(jù)集：為了驗(yàn)證DKSC在不同數(shù)據(jù)量級(jí)下的高效性，通過(guò)百度地圖API獲取北京市5組數(shù)量不同的空間數(shù)據(jù)。數(shù)據(jù)為實(shí)際空間數(shù)據(jù)的經(jīng)緯度信息，將其轉(zhuǎn)換為相對(duì)于整個(gè)空間區(qū)域的相對(duì)坐標(biāo)，數(shù)據(jù)集的大小見表1。

Table 1　Information of datasets表1　數(shù)據(jù)集信息

4.3R-樹構(gòu)建實(shí)驗(yàn)結(jié)果及分析

3種索引結(jié)構(gòu)的構(gòu)建時(shí)間如表2所示。通過(guò)3種R-樹索引在數(shù)據(jù)集T1～T5上的構(gòu)建時(shí)間對(duì)比可以看出，TDRC R-樹構(gòu)建所需要的時(shí)間最短，這是由于它在構(gòu)建過(guò)程中采取改進(jìn)K-means算法，時(shí)間復(fù)雜度最?。籏-medoids R-樹和DKSC R-樹構(gòu)建時(shí)間略多，尤其對(duì)于DKSC R-樹，還需要在聚類中動(dòng)態(tài)確定k值的大小和處理離群空間數(shù)據(jù)，這樣一來(lái)會(huì)消耗一定的時(shí)間，影響總體構(gòu)建時(shí)間。

Table 2　R-tree construction time表2　R-樹構(gòu)建時(shí)間實(shí)驗(yàn)結(jié)果

TDRC R-樹構(gòu)建的時(shí)間復(fù)雜度為O(n×k×t)，K-medoids R-樹的時(shí)間復(fù)雜度為O(n2×t/k)，DKSC R-樹構(gòu)建的時(shí)間復(fù)雜度為O(n2×t)，k為聚類數(shù)，t為迭代次數(shù)，n為空間數(shù)據(jù)數(shù)量。DKSC R-樹與TDRC R-樹和K-medoids R-樹的構(gòu)建時(shí)間相比，只有最多不超過(guò)6%的增加，也就是說(shuō)DKSC R-樹用少量的構(gòu)建時(shí)間來(lái)?yè)Q取高效的查找效率，這對(duì)于靜態(tài)空間數(shù)據(jù)來(lái)構(gòu)建R-樹索引來(lái)說(shuō)是完全可以接受的。

4.4R-樹查找實(shí)驗(yàn)結(jié)果及分析

查找區(qū)域大小為整個(gè)空間區(qū)域的1%和4%的實(shí)驗(yàn)結(jié)果分別如表3和表4所示。

Table 3　Response time for querying 1%area表3　查找區(qū)域(1%)實(shí)驗(yàn)結(jié)果

Table 4　Response time for querying 4%area表4　查找區(qū)域(4%)實(shí)驗(yàn)結(jié)果

首先，單獨(dú)從每一組實(shí)驗(yàn)可以看出，DKSC R-樹空間索引的區(qū)域查找效率最高，K-medoids R-樹空間索引次之，TDRC R-樹空間索引效率相對(duì)最低。這是因?yàn)镈KSC算法在構(gòu)建時(shí)動(dòng)態(tài)地判斷每一層聚類數(shù)，并且避免了離群數(shù)據(jù)的影響，減小R-樹節(jié)點(diǎn)MBR之間的交疊和MBR覆蓋面積，使得產(chǎn)生的R-樹結(jié)構(gòu)緊湊，多路查找的情況少，效率更高。

其次，從兩組實(shí)驗(yàn)結(jié)果可以看到，查找區(qū)域?yàn)?%的查找響應(yīng)時(shí)間在3種R-樹空間索引下都比區(qū)域?yàn)?%的查找響應(yīng)時(shí)間少。這是因?yàn)椴檎覅^(qū)域越大，區(qū)域內(nèi)包含的空間數(shù)據(jù)會(huì)更多，所以出現(xiàn)更多的查找路徑，影響查找響應(yīng)時(shí)間。雖然DKSC R-樹在構(gòu)建時(shí)間上略多于其他兩種，但是查找效率明顯提高。

4.5不同空間分布狀況實(shí)驗(yàn)

為了驗(yàn)證不同空間分布狀況對(duì)R-樹空間索引性能的影響，產(chǎn)生與T1～T5數(shù)目相同的5組隨機(jī)數(shù)據(jù)集T1′、T2′、T3′、T4′、T5′。

在定義1的基礎(chǔ)上，用pi(i=1,2,…,n)表示空間數(shù)據(jù)的鄰近對(duì)象個(gè)數(shù)，定義L為平均分布狀態(tài)：

通常L值越大表示空間分布狀態(tài)越密集，L大于1表示空間分布狀態(tài)為聚集狀態(tài)，越接近1表示空間分布狀態(tài)越均勻，于是對(duì)數(shù)據(jù)集進(jìn)行測(cè)試，如表5。

Table 5　Distribution of spatial data表5　空間數(shù)據(jù)分布狀態(tài)

可以看出，實(shí)際空間數(shù)據(jù)集的分布狀態(tài)L值明顯高于隨機(jī)產(chǎn)生的數(shù)據(jù)集，對(duì)其進(jìn)行查找區(qū)域?yàn)?%的空間查找，結(jié)果如圖5?？梢钥闯?，在分布隨機(jī)的空間中，DKSC R-樹依舊有高效的查找效率，而分布均勻的空間平均查找響應(yīng)時(shí)間略小于空間聚集的空間，這是由于空間聚集的特點(diǎn)會(huì)讓R-樹中節(jié)點(diǎn)MBR之間出現(xiàn)過(guò)多的交疊，查找過(guò)程中多路查找情況較多，降低查找效率。

Fig.5　Contrast of DKSC in different distribution states圖5　DKSC在不同分布狀態(tài)下的對(duì)比

5　結(jié)束語(yǔ)

本文根據(jù)空間數(shù)據(jù)分布的特點(diǎn)，在R-樹空間索引構(gòu)建中提出動(dòng)態(tài)確定k值的DKSC聚類算法，對(duì)空間進(jìn)行聚類劃分，自頂向下逐層構(gòu)建R-樹，避免了受初始k值和聚類中心的影響，且不受離群數(shù)據(jù)的干擾。并通過(guò)實(shí)驗(yàn)與文獻(xiàn)[12-13]提出的方法進(jìn)行了對(duì)比，證明了DKSC算法構(gòu)建的R-樹空間索引提高了區(qū)域查找的效率。

對(duì)DKSC算法的進(jìn)一步研究可以從以下幾個(gè)方面進(jìn)行：在R-樹與聚類結(jié)合過(guò)程中，能否選取到更加合理的初始聚類中心；能否在不影響空間查找效率的基礎(chǔ)上，減少構(gòu)建R-樹空間索引的時(shí)間；在更新頻率大的空間數(shù)據(jù)中，能否保證R-樹空間索引在構(gòu)建時(shí)間與查找響應(yīng)時(shí)間整體上效率最高。

References:

[1]Zhang Mingbo,Lu Feng,Shen Paiwei,et al.The evolvement and progress of R-tree family[J].Chinese Journal of Computers,2005,28(3):289-300.

[2]Chen Lisi,Cong Gao,Jensen C S,et al.Spatial keyword query processing:an experimental evaluation[C]//Proceedings of the 39th International Conference on Very Large Data Bases,Lago Di Garda,Italy,Aug 26-31,2013:217-228.

[3]Bui C G,Duong T A.Improving sort-tile-recusive algorithm for R-tree packing in indexing time series[C]//Proceedings of the 11th IEEE RIVF International Conference on Computing and Communication Technologies-Research, Innovation,and Vision for the Future,Can Tho,Vietnam, Jan 25-28,2015.Piscataway,USA:IEEE,2015:117-122.

[4]Guttman A.R-trees:a dynamic index structure for spatial searching[C]//Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data,Boston,USA, Jun 18-21,1984.New York,USA:ACM,1984:47-57.

[5]Lin P L,Tan W H.An efficient method for the retrieval of objects by topological relations in spatial database systems[J]. Information Processing and Management,2003,39(4):543-559.

[6]He Zhenwei,Wu Chonglong,Wang Cheng.Clustered sorting R-tree:an index for multi-dimensional spatial objects[C]// Proceedings of the 4th International Conference on Natural Computation,Jinan,China,Oct 18-20,2008.Washington, USA:IEEE Computer Society,2008:348-352.

[7]Sellis T,Roussopoulos N,Faloutsos C.The R+-tree:a dynamic index for multi-dimensional objects[C]//Proceedings of the 13th International Conference on Very Large Data Bases,Brighton,1987.San Francisco,USA:Morgan Kaufmann Publishers Inc,1987:507-518.

[8]Beckmann N,Kriegel H P,Schneider R,et al.The R*-tree: an efficient and robust access method for points and rectangles[C]//Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data,Atlantic City, May 23-25,1990.New York,USA:ACM,1990:322-331.

[9]Roussopoulos N,Leifker D.Direct spatial search on pictorial databases using packed R-trees[C]//Proceedings of the 1985 ACM SIGMOD International Conference on Management of Data,Austin,USA,May 28-31,1985.New York,USA: ACM,1985:17-31.

[10]Brakatsoulas S,Pfoser D,Theodoridis Y.Revisiting R-tree construction principles[C]//Proceedings of the 6th Advances in Database and Information Systems,Brarislava,Slovakia, Sep 9-11,2002.Berlin,Heidelberg:Springer,2002:149-162.

[11]Liu Runtao,An Xiaohua,Gao Xiaoshuang.Spatial index structure based on R-tree[J].Computer Engineering,2009, 35(23):32-34.

[12]Wang Jingfen.Optimization algorithm for R-tree combining with spatial-clustering[J].Computer engineering and applications,2014,50(5):112-115.

[13]Huang Zhong,Qin Yaochen,Zhang Xiwang,et al.A static R-tree organization method based on top-down recursive clustering[C]//Proceedings of the 21st International Conference on Geoinformatics,Kaifeng,China,Jun 20-22,2013.Washington,USA:IEEE Computer Society,2013:1-5.

[14]Yu Dongmei.R-tree spatial index based on K-means clustering[J]. Science and Technology Review,2012,30(11):76-79.

[15]Chen Yongkang.An improved R-tree for geo-spatial indexing[J]. Journal of Ecological Economics,2007,5(1/4):279-284.

[16]Shen Jieqiong,Li Haiyan.A new proof of the convergence of dynamic clustering algorithm[J].Digitization User,2013 (6):122.

附中文參考文獻(xiàn)：

[1]張明波,陸鋒,申排偉,等.R樹家族的演變和發(fā)展[J].計(jì)算機(jī)學(xué)報(bào),2005,28(3):289-300.

[11]劉潤(rùn)濤,安曉華,高曉爽.一種基于R-樹空間索引結(jié)構(gòu)[J].計(jì)算機(jī)工程,2009,35(23):32-34.

[12]汪璟玢.一種結(jié)合空間聚類算法的R樹優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(5):112-115.

[14]余冬梅.基于K-Means聚類的R-樹空間索引方法研究與分析[J].科技導(dǎo)報(bào),2012,30(11):76-79.

[15]陳永康.地理空間索引R樹算法的一種改進(jìn)[J].生態(tài)經(jīng)濟(jì)學(xué)報(bào),2007,5(1/4):279-284.

[16]沈潔瓊,李海艷.動(dòng)態(tài)聚類算法收斂的一個(gè)新證明[J].數(shù)字化用戶,2013(6):122.

HU Yupu was born in 1991.He is an M.S.candidate at Taiyuan University of Technology.His research interest is spatial databases.

胡昱璞（1991—），男，山西晉中人，太原理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫(kù)。

NIU Baoning was born in 1964.He is a professor and Ph.D.supervisor at Taiyuan University of Technology.His research interests include big data,and autonomic computing and performance management of database systems.

牛保寧（1964—），太原理工大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)，數(shù)據(jù)庫(kù)系統(tǒng)的自主計(jì)算與性能管理。

R-tree Spatial Index Construction Based on Dynamical K-value ClusteringAlgorithm*

HU Yupu,NIU Baoning+
School of Computer Science and Technology,Taiyuan University of Technology,Taiyuan 030024,China
+Corresponding author:E-mail:niubaoning@tyut.edu.cn

HU Yupu,NIU Baoning.R-tree spatial index construction based on dynamical K-value clustering algorithm. Journal of Frontiers of Computer Science and Technology,2016,10(2):173-181.

The current R-tree spatial clustering algorithms use a predefined k-value for clustering,and choose the initial clustering centers arbitrarily.The clustering results are easily dominated by the initial k-value and the outlier data.In order to solve these problems,this paper proposes a novel spatial clustering algorithm called DKSC(dynamical kvalue spatial clustering algorithm),which dynamically determines the optimized k-value when constructing the tree. By choosing an optimized k-value,the algorithm allows the spatial data in the same subspace to be organized into the same sub-tree,and builds an efficient R-tree layer by layer from the root to leaves.The experiments conducted with real and simulated datasets show that the proposed algorithm can build optimized R-tree spatial indexes and improve retrieval efficiency.

spatial data;R-tree;spatial index;clustering algorithm

目前采用的R-樹空間聚類技術(shù)使用指定k值的聚類算法，初始聚類中心隨機(jī)或指定選取。這樣聚類的結(jié)果受初始k值影響，且易受離群空間數(shù)據(jù)的干擾。為解決上述問(wèn)題，根據(jù)空間數(shù)據(jù)分布的特點(diǎn)，提出了動(dòng)態(tài)確定k值的空間聚類算法(dynamical k-value spatial clustering algorithm,DKSC)。該算法通過(guò)聚類劃分空間數(shù)據(jù)，把同一子空間的數(shù)據(jù)組織在同一個(gè)子樹下，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐層構(gòu)建R-樹，形成高效的R-樹空間索引。分別用真實(shí)和模擬的空間數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，結(jié)果表明該算法優(yōu)化了構(gòu)建的R-樹空間索引，且具有更高效的查找效率。

2015-06,Accepted 2015-09.

10.3778/j.issn.1673-9418.1506089

*The National Natural Science Foundation of China under Grant No.61572345(國(guó)家自然科學(xué)基金);the National Science and Technology Support Program of China under Grant No.2015BAH37F01(國(guó)家科技支撐計(jì)劃項(xiàng)目課題).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-09-06,http://www.cnki.net/kcms/detail/11.5602.TP.20150906.1050.004.html

A

TP311