彭召軍，熊 偉，柴 崢

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

?

基于改進(jìn)聚類分裂的動(dòng)態(tài)R*-樹實(shí)現(xiàn)方法

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

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

在R*-樹的構(gòu)建過程中引入聚類技術(shù)能夠有效地提高索引的性能，傳統(tǒng)的k-means聚類算法對(duì)初始值非常敏感，聚類過程較為復(fù)雜?；诖?，文中提出一種改進(jìn)聚類分裂的動(dòng)態(tài)R*-樹實(shí)現(xiàn)方法，在節(jié)點(diǎn)分裂的過程中引進(jìn)聚類技術(shù)，對(duì)R*-樹的基本結(jié)構(gòu)加以改進(jìn)，從而獲得動(dòng)態(tài)的結(jié)構(gòu)重組。實(shí)驗(yàn)表明，動(dòng)態(tài)R*-樹以略高的構(gòu)建開銷換取較高的查詢效率，大幅度提高索引樹的空間利用率，在批量數(shù)據(jù)動(dòng)態(tài)加載和處理等方面具有較高的實(shí)用價(jià)值。

R*-樹；聚類；節(jié)點(diǎn)分裂；空間利用率

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

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

1 聚類算法

文獻(xiàn)[8]中系統(tǒng)闡述常見的聚類技術(shù)。本文采用k-中心點(diǎn)輪換法[9]，其時(shí)間復(fù)雜度為O(n2)，n是對(duì)象的個(gè)數(shù)。在k-中心點(diǎn)輪換法中，優(yōu)化目標(biāo)函數(shù)的定義為

‖X-Vi‖p.

(1)

式中：E表示所有對(duì)象與其對(duì)應(yīng)的簇中心之間偏差的總和；X是對(duì)象中心；Vi是簇Ci的平均值。k-中心點(diǎn)輪換法是一種使目標(biāo)函數(shù)下降最快的方法，主要步驟為：

輸入：簇的數(shù)目k，對(duì)象集S={S1,S2,…,Sn};

輸出：k個(gè)簇，每個(gè)簇所包含的聚類對(duì)象集。

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

，

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

2)將剩余的每個(gè)對(duì)象分配給離它最近的對(duì)象中心所代表的簇，依據(jù)式(1)計(jì)算各個(gè)簇的目標(biāo)函數(shù)值；

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

4)最終得到一個(gè)中心對(duì)象集合，根據(jù)這個(gè)集合按照最近鄰原則將剩余所有對(duì)象分配到對(duì)應(yīng)的簇中，所得到的k個(gè)簇是一個(gè)局部?jī)?yōu)化的聚類結(jié)果。

2 基于改進(jìn)聚類分裂的動(dòng)態(tài)R*-樹

傳統(tǒng)的R*-樹的構(gòu)造過程為：①找到待插入數(shù)據(jù)項(xiàng)的葉節(jié)點(diǎn);②若葉節(jié)點(diǎn)未滿，直接將數(shù)據(jù)項(xiàng)插入此葉節(jié)點(diǎn)，依次向上調(diào)整父節(jié)點(diǎn)的目錄矩形；若葉節(jié)點(diǎn)已滿，需要對(duì)葉節(jié)點(diǎn)進(jìn)行分裂，同時(shí)進(jìn)行“強(qiáng)制重新插入”操作。動(dòng)態(tài)R*-樹在傳統(tǒng)R*-樹的基礎(chǔ)上，對(duì)R*-樹的基本結(jié)構(gòu)、插入算法和分裂算法進(jìn)行改進(jìn)。

2.1 動(dòng)態(tài)R*-樹的結(jié)構(gòu)

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

2.2 動(dòng)態(tài)R*-樹的構(gòu)建

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

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

2)如果Leaf未滿，將數(shù)據(jù)項(xiàng)直接插入到Leaf中，返回；如果Leaf已滿，在考慮目錄矩形重疊、面積和周長(zhǎng)等因素的基礎(chǔ)上，找到Leaf的k個(gè)未滿的兄弟節(jié)點(diǎn)；

3)如果k≠0，將數(shù)據(jù)項(xiàng)插入到kLeaf中，并返回；否則，從k個(gè)兄弟節(jié)點(diǎn)中找出標(biāo)識(shí)符m_bClusterNode=false的m(m≤k)個(gè)兄弟節(jié)點(diǎn)，將Leaf與m個(gè)兄弟節(jié)點(diǎn)一起進(jìn)行聚類分裂，從而達(dá)到數(shù)據(jù)項(xiàng)優(yōu)化重組的目的。

2.3 聚類分裂技術(shù)

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

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

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

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

3)得到聚類分裂結(jié)果。新建一個(gè)葉子節(jié)點(diǎn)，將最后一個(gè)聚簇中的數(shù)據(jù)項(xiàng)放入此葉子節(jié)點(diǎn)中，同時(shí)更新Leaf及其m個(gè)兄弟節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)。

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

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

圖2和圖3分別為傳統(tǒng)R*-樹和改進(jìn)后的動(dòng)態(tài)R*-樹的基本結(jié)構(gòu)。由圖可知，相比于傳統(tǒng)的R*-樹，改進(jìn)后的動(dòng)態(tài)R*-樹具有更小的重疊率和更高的空間利用率，索引樹的結(jié)構(gòu)更為合理。

(a)平面示意圖 (b)結(jié)構(gòu)示意圖圖2 傳統(tǒng)R*-樹(最大度為5)

圖3 改進(jìn)后的動(dòng)態(tài)R*-樹(最大度為5)

綜上，在數(shù)據(jù)集動(dòng)態(tài)插入的過程中，對(duì)R*-樹的基本結(jié)構(gòu)加以調(diào)整，在節(jié)點(diǎn)分裂的過程中引入聚類分裂技術(shù)，能夠最大限度地優(yōu)化動(dòng)態(tài)R*-樹的結(jié)構(gòu)。

3 實(shí)驗(yàn)與結(jié)論

為了評(píng)估動(dòng)態(tài)R*-樹的性能，將本文所構(gòu)建的R*-樹與傳統(tǒng)的R-樹、R*-樹進(jìn)行比較。在VS2010 C++環(huán)境下實(shí)現(xiàn)動(dòng)態(tài)R*-樹、傳統(tǒng)R-樹和R*-樹的算法，實(shí)驗(yàn)的平臺(tái)為Intel 2.59 G，內(nèi)存8 G的華碩筆記本。

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了使實(shí)驗(yàn)結(jié)果更具有代表性，實(shí)驗(yàn)中使用真實(shí)的全國(guó)導(dǎo)航圖數(shù)據(jù)，利用導(dǎo)航圖數(shù)據(jù)中具有代表性的4個(gè)數(shù)據(jù)集對(duì)3種典型的空間索引算法的性能進(jìn)行測(cè)試。詳細(xì)的數(shù)據(jù)集信息如表1所示。

表1 數(shù)據(jù)集信息詳情

3.2 性能評(píng)估及分析

在實(shí)驗(yàn)中，頁面大小設(shè)置為4 KB，索引樹節(jié)點(diǎn)的最大度(MAXDEGREE)設(shè)為50，填充因子設(shè)為70%，分別對(duì)索引樹的構(gòu)造時(shí)間、查詢時(shí)間、生成的索引文件大小和空間利用率進(jìn)行評(píng)估，得到實(shí)驗(yàn)結(jié)果是多次測(cè)試結(jié)果的平均值，查詢時(shí)間則是算法執(zhí)行100次所用的全部時(shí)間。

圖4 不同索引樹的構(gòu)建時(shí)間

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

圖6 不同索引樹的查詢時(shí)間

圖7 不同索引樹的平均節(jié)點(diǎn)訪問次數(shù)(范圍查詢)

圖8 不同索引樹節(jié)點(diǎn)的空間利用率

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

綜上所述，本文所構(gòu)建的動(dòng)態(tài)R*-樹，以略高于傳統(tǒng)R-樹的構(gòu)建代價(jià)，獲得較高的查詢性能和空間利用率。

4 結(jié)束語

在傳統(tǒng)R*-樹的基礎(chǔ)上，本文對(duì)R*-樹的基本結(jié)構(gòu)進(jìn)行改進(jìn)，在節(jié)點(diǎn)的分裂過程中引進(jìn)聚類技術(shù)對(duì)R*-樹的整體結(jié)構(gòu)進(jìn)行動(dòng)態(tài)重組，提出一種基于改進(jìn)聚類分裂的動(dòng)態(tài)R*-樹實(shí)現(xiàn)方法。實(shí)驗(yàn)證明，動(dòng)態(tài)R*-樹以略高的構(gòu)建開銷換取較高的查詢效率和空間利用率，在大批量數(shù)據(jù)動(dòng)態(tài)處理等方面具有明顯的優(yōu)勢(shì)。由于R*-樹對(duì)目錄矩形的重疊率、面積、周長(zhǎng)以及目錄矩形的形狀等因素較為敏感，下一步仍需要研究如何利用多目標(biāo)優(yōu)化算法綜合考慮這些影響因素，以期進(jìn)一步提升動(dòng)態(tài)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] 郭菁, 郭薇, 胡志勇. 空間數(shù)據(jù)庫索引技術(shù)[M]. 上海：上海交通大學(xué)出版社, 2006.

[3] 黃繼先, 鮑光淑, 夏斌. 基于混合聚類算法的動(dòng)態(tài)R-樹[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 吳敏君,陳天滋.基于分割聚類技術(shù)的R-樹結(jié)點(diǎn)分裂方案[J].計(jì)算機(jī)應(yīng)用與軟件,2007,24(10):42-44.

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

[7] 吳欽陽. R*-樹空間索引的改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用, 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] 陳新泉. 聚類算法中的優(yōu)化方法應(yīng)用[M]. 成都：電子科技大學(xué)出版社, 2014.

[責(zé)任編輯：張德福]

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(41501507)

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

P208

A

1006-7949(2017)03-0072-05

引用著錄：彭召軍，熊偉，柴崢.基于改進(jìn)聚類分裂的動(dòng)態(tài)R*-樹實(shí)現(xiàn)方法[J].測(cè)繪工程，2017，26(3)：72-76.