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

胡昱璞，牛保寧

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

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

胡昱璞，牛保寧+

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

空間數據；R-樹；空間索引；聚類算法

1　引言

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

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

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

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

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

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

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

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

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

2　研究現狀

2.1構建方式

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

2.2相關工作

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

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

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

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

2.3空間聚類

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

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

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

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

（1）以全部空間數據作為整體，取其MBR作為R-樹的根節點。

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

（3）按照K-means算法，計算聚類中新的聚類中心，并重新劃分，不斷迭代聚類，直到聚類中心不變為止，形成4個聚類Z1、Z2、Z3、Z4；否則迭代執行步驟（3）。

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

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

Fig.1　An example of outlier圖1　離群數據示例

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

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

3　DKSC算法

3.1相關定義

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

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

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

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

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

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

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

采用的聚類測度函數如下：

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

3.2算法描述

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

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

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

算法1 GetClusteringCenter

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

算法2 DKSC

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

Fig.2　Aset of MBRs圖2　一組空間數據MBR集合

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

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

定理1聚類測度函數具有收斂性。

證明見文獻[16]。□

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

算法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-樹的區域查找效率。

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

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

4.2實驗環境及數據集

實驗環境：處理器Intel Core i7 3.6 GHz，內存4 GB，硬盤500 GB，操作系統為Windows 7，編程語言為Java，IDE為MyEclipse 8.6。

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

Table 1　Information of datasets表1　數據集信息

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

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

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為聚類數，t為迭代次數，n為空間數據數量。DKSC R-樹與TDRC R-樹和K-medoids R-樹的構建時間相比，只有最多不超過6%的增加，也就是說DKSC R-樹用少量的構建時間來換取高效的查找效率，這對于靜態空間數據來構建R-樹索引來說是完全可以接受的。

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

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

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

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

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

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

4.5不同空間分布狀況實驗

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

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

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

Table 5　Distribution of spatial data表5　空間數據分布狀態

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

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

5　結束語

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

對DKSC算法的進一步研究可以從以下幾個方面進行：在R-樹與聚類結合過程中，能否選取到更加合理的初始聚類中心；能否在不影響空間查找效率的基礎上，減少構建R-樹空間索引的時間；在更新頻率大的空間數據中，能否保證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樹家族的演變和發展[J].計算機學報,2005,28(3):289-300.

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

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

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

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

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

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高級會員，主要研究領域為大數據，數據庫系統的自主計算與性能管理。

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值影響，且易受離群空間數據的干擾。為解決上述問題，根據空間數據分布的特點，提出了動態確定k值的空間聚類算法(dynamical k-value spatial clustering algorithm,DKSC)。該算法通過聚類劃分空間數據，把同一子空間的數據組織在同一個子樹下，從根節點到葉子節點逐層構建R-樹，形成高效的R-樹空間索引。分別用真實和模擬的空間數據集進行了實驗，結果表明該算法優化了構建的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網絡優先出版：2015-09-06,http://www.cnki.net/kcms/detail/11.5602.TP.20150906.1050.004.html

A

TP311