基于改進聚類分裂的動態R*-樹實現方法

彭召軍，熊 偉，柴 崢

(1.信息工程大學，河南 鄭州 450001；2.61206部隊，北京 100042)

?

基于改進聚類分裂的動態R*-樹實現方法

彭召軍1，熊 偉1，柴 崢2

(1.信息工程大學，河南 鄭州 450001；2.61206部隊，北京 100042)

在R*-樹的構建過程中引入聚類技術能夠有效地提高索引的性能，傳統的k-means聚類算法對初始值非常敏感，聚類過程較為復雜。基于此，文中提出一種改進聚類分裂的動態R*-樹實現方法，在節點分裂的過程中引進聚類技術，對R*-樹的基本結構加以改進，從而獲得動態的結構重組。實驗表明，動態R*-樹以略高的構建開銷換取較高的查詢效率，大幅度提高索引樹的空間利用率，在批量數據動態加載和處理等方面具有較高的實用價值。

R*-樹；聚類；節點分裂；空間利用率

R-樹[1]作為一類平衡的多路查找樹，具有自動平衡、空間利用率較高、便于外存存儲等優點[2]，廣泛應用于大型的數據庫系統中。隨著索引空間維數的增加和索引數據量的增大，R-樹中間節點目錄矩形的覆蓋與重疊迅速增加，嚴重影響R-樹的查詢性能[3]。R*-樹[4]是R-樹的一種變體，其綜合考慮節點的覆蓋、重疊以及目錄矩形周長等參數優化插入和分裂算法，并通過引入強制重新插入技術使索引的檢索性能和空間利用率都有較大的提升。文獻[5]提出一種分割聚類的R-樹結點分裂算法(C-Linear分裂算法)，有效提高R-樹的操作效率，但聚類分裂的過程較為復雜，分裂算法不易收斂。文獻[6]中提出的LR-樹，在確保索引查詢性能的前提下，降低構建代價，并且大幅提高索引結構的空間利用率，但也同樣存在聚類分裂過程復雜的問題。

隨著“大數據”時代的到來，很多有關空間索引技術的研究重點關注R*-樹的動態批量操作技術，這種技術能夠有效地支持海量數據的高效處理(查詢、插入、刪除及更新)。由于數據在空間分布上常常具有“聚集”的特性，在R*-樹的構建過程中引入聚類技術對數據集進行集簇劃分，能夠有效地減少節點之間的重疊與覆蓋，優化R*-樹的結構，大幅度提高索引的操作效率和性能[7]。基于批量動態加載空間數據的需求，本文在綜合考慮節點的最小外接矩形(MBR)的形狀、重疊率、面積以及周長等影響因素的基礎上，通過改進R*-樹的基本結構和分裂方式，實現一種基于改進聚類分裂的動態R*-樹。實驗證明，改進后的動態R*-樹性能更優。

1 聚類算法

文獻[8]中系統闡述常見的聚類技術。本文采用k-中心點輪換法[9]，其時間復雜度為O(n2)，n是對象的個數。在k-中心點輪換法中，優化目標函數的定義為

‖X-Vi‖p.

(1)

式中：E表示所有對象與其對應的簇中心之間偏差的總和；X是對象中心；Vi是簇Ci的平均值。k-中心點輪換法是一種使目標函數下降最快的方法，主要步驟為：

輸入：簇的數目k，對象集S={S1,S2,…,Sn};

輸出：k個簇，每個簇所包含的聚類對象集。

1)隨機選擇k個對象，作為每個簇的初始中心對象。在d維空間中，設一個類簇由M個矩形r1，r2，…,rM的對象中心[5]，可以定義為

，

其中，(min_xij,max_xij)，i∈(1,…,M),j∈(1,…,d)分別表示矩形的左下角和右上角坐標；

2)將剩余的每個對象分配給離它最近的對象中心所代表的簇，依據式(1)計算各個簇的目標函數值；

3)對于S={S1,S2,…,Sn}中的每一個對象Si(i=1,2,…,n)，試圖用當前對象Si依次替換已有的k個聚簇中的每一個對象中心Vi(i=1,2,…,k)，通過計算替換后的目標函數值，最終選擇使目標函數取得最小值的對象中心進行替換。如果替換后并沒有獲得更小的目標函數值，則不進行替換;

4)最終得到一個中心對象集合，根據這個集合按照最近鄰原則將剩余所有對象分配到對應的簇中，所得到的k個簇是一個局部優化的聚類結果。

2 基于改進聚類分裂的動態R*-樹

傳統的R*-樹的構造過程為：①找到待插入數據項的葉節點;②若葉節點未滿，直接將數據項插入此葉節點，依次向上調整父節點的目錄矩形；若葉節點已滿，需要對葉節點進行分裂，同時進行“強制重新插入”操作。動態R*-樹在傳統R*-樹的基礎上，對R*-樹的基本結構、插入算法和分裂算法進行改進。

2.1 動態R*-樹的結構

在原有R*-樹的基礎上，動態R*-樹對R*-樹的基本結構做如下調整：①由于引入聚類算法進行節點分裂時可能存在R*-樹節點不滿的情況，動態R*-樹的節點對數據項和索引項的填充個數的下限沒有嚴格限制(R*-樹要求至少有m個)，這樣做能夠有效避免在空間上并不鄰近的兩個對象被分配到同一節點，造成索引樹結構的惡化;②動態R*-樹節點的數據結構中新增一個用于判斷節點是否進行聚類分裂的標識m_bClusterNode，如果該節點已經參與聚類分裂，并且分裂后節點的數據項已經填充至少90%，則令m_bClusterNode=true。這樣做的目的是避免已經達到局部最優的節點多次參與分裂，提高R*-樹節點的空間利用率，從而提高聚類分裂的效率。

2.2 動態R*-樹的構建

借鑒文獻[6]中的R*-樹構建算法，在插入數據項的過程中，當節點溢出時，并不像傳統R*-樹那樣對節點立即進行分裂，而是將待插入的數據項插入到最合適的未滿兄弟節點中，從而有效地減少分裂次數，提高節點的空間利用率,即動態R*-樹的插入算法(R*-tree_Insert)，輸入：葉節點Leaf，數據項e；輸出：無。具體步驟如下：

1)考慮目錄矩形的重疊、目錄矩形的面積等因素，利用FindLeaf函數找到適合插入的葉子節點Leaf；

2)如果Leaf未滿，將數據項直接插入到Leaf中，返回；如果Leaf已滿，在考慮目錄矩形重疊、面積和周長等因素的基礎上，找到Leaf的k個未滿的兄弟節點；

3)如果k≠0，將數據項插入到kLeaf中，并返回；否則，從k個兄弟節點中找出標識符m_bClusterNode=false的m(m≤k)個兄弟節點，將Leaf與m個兄弟節點一起進行聚類分裂，從而達到數據項優化重組的目的。

2.3 聚類分裂技術

動態R*-樹的構建過程中盡量避免節點分裂，避免索引樹的整體結構惡化，采用聚類分裂技術將處于同一層級的多個兄弟節點進行聚類分裂，能夠有效改善R*-樹的結構，即葉子節點分裂算法(R*-tree_ClusterSplit)，輸入：葉節點Leaf及m個兄弟節點，數據項e；輸出：m+1個或更多的節點。具體步驟如下：

1)確定初始中心對象。選取m+1或更多的初始聚類對象，在選取的過程中引入距離閾值(距離閾值一般可通過實驗的方法得到)以避免陷入局部解，如圖1所示。

(a)未引入距離閾值的聚類中心 (b)引入距離閾值的聚類中心圖1 初始聚類中心

2)為聚簇分配元素。用k-中心點輪換法將剩余對象依次分配到各個聚簇中，具體過程見前文所述。

3)得到聚類分裂結果。新建一個葉子節點，將最后一個聚簇中的數據項放入此葉子節點中，同時更新Leaf及其m個兄弟節點的數據項。

對于不同的m值，k-中心點輪換法的聚類質量和穩定性比k-means算法要好很多。在索引樹的構建過程中：①聚類分裂對R*-樹的結構作最大限度的重組，優化了索引樹的結構，減少節點的覆蓋與重疊；②在葉子節點已滿的情況下，將數據項插入到還未進行聚類分裂的未滿兄弟節點中，減少分裂次數，提高R*-樹的空間利用率。

假定總的數據項的個數為n，數據項維度為d，聚類分裂過程中的迭代次數為t，算法的時間代價主要包括3個方面：選擇子樹、插入數據項以及聚類分裂。聚類分裂過程的代價主要是R*-樹節點的磁盤IO，分裂算法的時間復雜度為O(ndkt)。在實際過程中，分裂時的迭代次數t很小，且聚類分裂標識m_bClusterNode有效限制參與聚類分裂的鄰近節點數量的增加，有效降低節點分裂的代價。

圖2和圖3分別為傳統R*-樹和改進后的動態R*-樹的基本結構。由圖可知，相比于傳統的R*-樹，改進后的動態R*-樹具有更小的重疊率和更高的空間利用率，索引樹的結構更為合理。

(a)平面示意圖 (b)結構示意圖圖2 傳統R*-樹(最大度為5)

圖3 改進后的動態R*-樹(最大度為5)

綜上，在數據集動態插入的過程中，對R*-樹的基本結構加以調整，在節點分裂的過程中引入聚類分裂技術，能夠最大限度地優化動態R*-樹的結構。

3 實驗與結論

為了評估動態R*-樹的性能，將本文所構建的R*-樹與傳統的R-樹、R*-樹進行比較。在VS2010 C++環境下實現動態R*-樹、傳統R-樹和R*-樹的算法，實驗的平臺為Intel 2.59 G，內存8 G的華碩筆記本。

3.1 實驗數據

為了使實驗結果更具有代表性，實驗中使用真實的全國導航圖數據，利用導航圖數據中具有代表性的4個數據集對3種典型的空間索引算法的性能進行測試。詳細的數據集信息如表1所示。

表1 數據集信息詳情

3.2 性能評估及分析

在實驗中，頁面大小設置為4 KB，索引樹節點的最大度(MAXDEGREE)設為50，填充因子設為70%，分別對索引樹的構造時間、查詢時間、生成的索引文件大小和空間利用率進行評估，得到實驗結果是多次測試結果的平均值，查詢時間則是算法執行100次所用的全部時間。

圖4 不同索引樹的構建時間

圖5 不同索引樹生成的索引文件大小

圖6 不同索引樹的查詢時間

圖7 不同索引樹的平均節點訪問次數(范圍查詢)

圖8 不同索引樹節點的空間利用率

圖4所示為3種不同的索引樹對于不同數據集的構建時間，可以看出，在3種索引樹的構建過程中，時間消耗最少的是傳統的R-樹，而本文構建的動態R*-樹的時間消耗比傳統的R*-樹要少。由圖5可以得知，相比于其他兩種索引樹而言，動態R*-樹構建完成后生成的索引文件要小，占用的空間更小。在查詢(區域查詢)性能上(見圖6和圖7)，動態R*-樹具有較為明顯的優勢，動態R*-樹的查詢時間較其他兩種索引樹明顯要少，平均節點訪問次數與傳統R*-樹相當，比傳統R-樹明顯要少。如圖8所示，動態R*-樹的空間利用率得到提高，反復實驗證明，動態R*-樹的填充率約為79%，表明聚類分裂技術收到良好的效果。

綜上所述，本文所構建的動態R*-樹，以略高于傳統R-樹的構建代價，獲得較高的查詢性能和空間利用率。

4 結束語

在傳統R*-樹的基礎上，本文對R*-樹的基本結構進行改進，在節點的分裂過程中引進聚類技術對R*-樹的整體結構進行動態重組，提出一種基于改進聚類分裂的動態R*-樹實現方法。實驗證明，動態R*-樹以略高的構建開銷換取較高的查詢效率和空間利用率，在大批量數據動態處理等方面具有明顯的優勢。由于R*-樹對目錄矩形的重疊率、面積、周長以及目錄矩形的形狀等因素較為敏感，下一步仍需要研究如何利用多目標優化算法綜合考慮這些影響因素，以期進一步提升動態R*-樹的性能。

[1] GUTTMAN A. R-tree: A Dynamic Index Structure for Spatial Searching[C]. In Proc. of 20th Int. Conf. on Very Large Data Bases, Morgan Kaufmann, 1984.

[2] 郭菁, 郭薇, 胡志勇. 空間數據庫索引技術[M]. 上海：上海交通大學出版社, 2006.

[3] 黃繼先, 鮑光淑, 夏斌. 基于混合聚類算法的動態R-樹[J].中南大學學報(自然科學版), 2006, 37(2): 365-370.

[4] BECKMANN N, KRIEGEL H P, SCHNIEIDE R, et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[C]. In: Proc. of ACM Intl. Conf. on the Management of Data(SIGMOD), 1990:322-331.

[5] 吳敏君,陳天滋.基于分割聚類技術的R-樹結點分裂方案[J].計算機應用與軟件,2007,24(10):42-44.

[6] 雷小鋒, 謝昆青. 基于惰性聚類分裂的R-樹實現方法[J]. 計算機科學, 2007, 34(4): 102-104.

[7] 吳欽陽. R*-樹空間索引的改進[J]. 計算機應用, 2010, 30(2):419-422.

[8] HAN J W, KAMBER M. Data Mining: Concepts and Techniques[M]. U. S: Morgan Kaufmann Publishers, Inc, 2001.

[9] 陳新泉. 聚類算法中的優化方法應用[M]. 成都：電子科技大學出版社, 2014.

[責任編輯：張德福]

An implementation method of dynamic R*- tree based on improved cluster splitting

PENG Zhaojun1, XIONG Wei1, CHAI Zheng2

(1.Information Engineering University, Zhengzhou 450001, China;2.Troops 61206, Beijing 100042, China)

Clustering technologies can effectively improve the performance of R*- tree.The traditional K-means clustering algorithm is very sensitive to the initial value, and the process of clustering is very complex. Considering this, an improved clustering algorithm of the dynamic R*- tree is proposed. In the process of node splitting, clustering technologies and improved structure can obtain dynamic structural reorganization of R*- tree. Experimental results show that the dynamic R*- tree can achieve higher query efficiency and space utilization with a slightly higher construction cost, which has practical value in dynamic loading and processing of batch data.

R*- tree;clustering;node splitting;space utilization

10.19349/j.cnki.issn1006-7949.2017.03.016

2016-02-23

國家自然科學基金資助項目(41501507)

彭召軍(1992-)，男，碩士研究生.

P208

A

1006-7949(2017)03-0072-05

引用著錄：彭召軍，熊偉，柴崢.基于改進聚類分裂的動態R*-樹實現方法[J].測繪工程，2017，26(3)：72-76.