胡昱璞，牛保寧

太原理工大學 計算機科學與技術學院，太原 030024

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

胡昱璞，牛保寧+

太原理工大學 計算機科學與技術學院，太原 030024

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

1　引言

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

目前，與聚類算法結合成為常用的R-樹空間索引構建方式，主要存在以下問題：

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

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

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

本文的主要工作及貢獻如下：

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

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

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

2　研究現(xiàn)狀

2.1構建方式

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

2.2相關工作

近些年，許多學者對R-樹空間索引進行了深入的研究和改進。

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

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

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

2.3空間聚類

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

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

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

改進K-means聚類算法構建R-樹的過程如下：

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

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

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

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

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

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

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

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

3　DKSC算法

3.1相關定義

為了方便說明，首先進行一些定義：

定義1（聚類中心選?。┒x一個衡量鄰近對象的距離指標R[15]，表示如下：

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

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

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

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

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

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

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

3.2算法描述

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

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

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

算法1 GetClusteringCenter

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

算法2 DKSC

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

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

Fig.3　Two clusters圖3　形成2個聚類

Fig.4　Three clusters圖4　形成3個聚類

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

證明見文獻[16]?！?/p>

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

算法3 Construction

4　實驗結果及分析

4.1實驗設計

為了驗證通過DKSC算法構建的R-樹空間索引（以下簡稱DKSC R-樹）的性能，本文設計實驗進行驗證，并同文獻[12-13]提出的方法進行對比。這兩種方法已在第2章進行了介紹，通過文獻[12]構建的R-樹簡稱為K-medoids R-樹，文獻[13]簡稱為TDRC R-樹。

重點設計了以下3個實驗：

實驗1 R-樹構建時間實驗。比較DKSC R-樹、K-medoids R-樹和TDRC R-樹的構建效率。

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

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

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

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

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

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

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

4.3R-樹構建實驗結果及分析

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

Table 2　R-tree construction time表2　R-樹構建時間實驗結果

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

4.4R-樹查找實驗結果及分析

查找區(qū)域大小為整個空間區(qū)域的1%和4%的實驗結果分別如表3和表4所示。

Table 3　Response time for querying 1%area表3　查找區(qū)域(1%)實驗結果

Table 4　Response time for querying 4%area表4　查找區(qū)域(4%)實驗結果

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

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

4.5不同空間分布狀況實驗

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

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

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

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

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

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

5　結束語

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

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

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.

附中文參考文獻：

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

[11]劉潤濤,安曉華,高曉爽.一種基于R-樹空間索引結構[J].計算機工程,2009,35(23):32-34.

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

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

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

[16]沈潔瓊,李海艷.動態(tài)聚類算法收斂的一個新證明[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—），男，山西晉中人，太原理工大學碩士研究生，主要研究領域為空間數(shù)據(jù)庫。

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—），太原理工大學教授、博士生導師，CCF高級會員，主要研究領域為大數(shù)據(jù)，數(shù)據(jù)庫系統(tǒng)的自主計算與性能管理。

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-樹空間聚類技術使用指定k值的聚類算法，初始聚類中心隨機或指定選取。這樣聚類的結果受初始k值影響，且易受離群空間數(shù)據(jù)的干擾。為解決上述問題，根據(jù)空間數(shù)據(jù)分布的特點，提出了動態(tài)確定k值的空間聚類算法(dynamical k-value spatial clustering algorithm,DKSC)。該算法通過聚類劃分空間數(shù)據(jù)，把同一子空間的數(shù)據(jù)組織在同一個子樹下，從根節(jié)點到葉子節(jié)點逐層構建R-樹，形成高效的R-樹空間索引。分別用真實和模擬的空間數(shù)據(jù)集進行了實驗，結果表明該算法優(yō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(國家自然科學基金);the National Science and Technology Support Program of China under Grant No.2015BAH37F01(國家科技支撐計劃項目課題).

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

A

TP311