一種基于混合聚類的空間索引算法

摘要:R-Tree允許兄弟節(jié)點(diǎn)之間的相互重疊，具有多路查找的特點(diǎn)，而Hilbert R-Tree也不能有效降低子空間的相互重疊，直接影響查詢效率。提出了一種基于混合聚類的空間索引算法，將K-means和K中心點(diǎn)引入索引結(jié)構(gòu)，改變了經(jīng)典K-means算法對(duì)初始聚類中心的隨機(jī)選取，減少了葉節(jié)點(diǎn)的MBR面積和各個(gè)子空間的重疊。通過(guò)實(shí)驗(yàn)表明，該算法具有更快的響應(yīng)速度和查詢效率。

關(guān)鍵詞:空間索引;混合聚類;Hilbert R-Tree;K-means;K中心點(diǎn);空間查詢

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2009)35-10047-02

A Spatial Index Algorithm Based on Spatial Cluster Analysis

HAN Qiu-ying1， MA Jun1，2， ZHANG Shao-hui3

(1.College of Computer and Information Engineering， Henan University， Kaifeng 475004，China;2.Institute of Data and Knowledge Engineering， Henan University，Kaifeng 475004，China;3.Department of Computer Science， Zhoukou Normal University，Zhoukou 466000，China)

Abstract: The R-Tree spatial index structure was analyzed.There are overlap between brothers nodes and multi-path in search ，and Hilbert R-Tree can not effectively reduce the overlap， which is a direct impact on query efficiency. Based on hybrid spatial clustering algorithms， a spatial index algorithm used K-means algorithm and K-center algorithm is proposed， which improve the random choice of the initial centrists in the classic K-means algorithm and decrease the leaf nodes MBR area and overlap between interior nodes. Experiments show that the algorithm has the faster response speed and the higher query efficiency.

Key words: spatial index; hybrid spatial clustering; hilbert R-tree; K-means; K-center; spatial query

隨著GIS(Geographic Information System，地理信息系統(tǒng))研究和管理的范圍不斷擴(kuò)大，精度不斷提高，需要處理的數(shù)據(jù)量也不斷激增。由于空間數(shù)據(jù)本身的復(fù)雜性，以及目前對(duì)海量空間數(shù)據(jù)快速查詢的要求日益提高，當(dāng)前GIS正面臨著大數(shù)據(jù)量空間數(shù)據(jù)存儲(chǔ)及管理的挑戰(zhàn)。如何組織、檢索這些海量數(shù)據(jù)是空間索引要解決的問(wèn)題之一。與非空間數(shù)據(jù)不同，空間索引處理的數(shù)據(jù)是二維、三維甚至是多維的不規(guī)則數(shù)據(jù)，故空間數(shù)據(jù)庫(kù)的開銷一般要比關(guān)系數(shù)據(jù)庫(kù)要大[1]。所以研究空間索引結(jié)構(gòu)、尋求更高效的空間索引算法，引起了人們?cè)絹?lái)越多的關(guān)注和興趣。

近年來(lái)，人們提出了大量的空間索引方法，如R-Tree及其變種R*-Tree、R+-Tree、四叉樹、Quad-Tree、Grid索引等等。R-Tree是空間數(shù)據(jù)庫(kù)中最流行的索引結(jié)構(gòu)之一[2]，但是在動(dòng)態(tài)構(gòu)建樹時(shí)容易造成空間區(qū)域重疊大，以及產(chǎn)生大量的“死空間”(不包含空間對(duì)象的索引空間)，檢索效率不高。

聚類分析是提高空間索引性能的一個(gè)非常有效的方法。目前已有K-means、CURE、ISODATA等多種算法，這些算法多數(shù)依賴于初始解的選擇。當(dāng)初始解選擇不好時(shí)，會(huì)影響聚類質(zhì)量，降低空間檢索效率，且這些算法執(zhí)行結(jié)果與數(shù)據(jù)輸入次序有關(guān)[3]。

Hilbert R-Tree是由R-Tree發(fā)展而來(lái)的，具有R-Tree的特征，通過(guò)對(duì)R-Tree和Hilbert R-Tree的結(jié)構(gòu)進(jìn)行比較和分析，提出了一種利用混合聚類技術(shù)和Hilbert R-Tree相結(jié)合的空間索引算法，降低了構(gòu)造樹的時(shí)間復(fù)雜度，縮短了計(jì)算時(shí)間，提高了查詢效率。

1 R-Tree簡(jiǎn)介

R-Tree最初由Guttman在1984年提出的，它是B-Tree在K維上的自然擴(kuò)展，是空間數(shù)據(jù)庫(kù)中最常用的空間索引結(jié)構(gòu)[4]。R-Tree是一種完全動(dòng)態(tài)的層次數(shù)據(jù)結(jié)構(gòu)，在葉子節(jié)點(diǎn)中包含指向?qū)嶋H數(shù)據(jù)對(duì)象的指針，插入、刪除和查詢可以同時(shí)進(jìn)行，并且不需要周期性的索引重組。如圖1所示的平面劃分對(duì)應(yīng)的R-Tree為圖2。

R-Tree索引具有其它索引方法無(wú)法企及的優(yōu)勢(shì):1)它按數(shù)據(jù)來(lái)組織索引結(jié)構(gòu)。這使它具有很強(qiáng)的靈活性、可調(diào)節(jié)性，不須預(yù)知整個(gè)空間對(duì)象所在的空間范圍就可以建立索引。2)由于它是由B-Tree在K維上的自然擴(kuò)展，具有相似的結(jié)構(gòu)和特性，能很好的和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)融合，這也是國(guó)外很多空間數(shù)據(jù)庫(kù)選擇R-Tree作為空間索引的重要原因之一。但是R-Tree中當(dāng)節(jié)點(diǎn)中記錄項(xiàng)超過(guò)M(每個(gè)節(jié)點(diǎn)存貯的最多索引記錄項(xiàng))時(shí)，節(jié)點(diǎn)必須分裂，這種分裂往往會(huì)導(dǎo)致節(jié)點(diǎn)內(nèi)的數(shù)據(jù)重新聚類，并導(dǎo)致索引數(shù)據(jù)重組，反而降低了效率。而且，R-Tree允許兄弟節(jié)點(diǎn)的之間的相互重疊，對(duì)于精確匹配查詢，不能保證唯一的搜索路徑。

2 Hilbert R-Tree簡(jiǎn)介

Hilbert R-Tree是利用Hilbert曲線將高維對(duì)象映射到一維中，并保存了大部分空間信息。它將空間對(duì)象根據(jù)位置相鄰關(guān)系打包，形成MBR(MinimumBounding Rectangle， 最小外接矩形)，再把這些MBR的中心映射到Hilbert曲線上并進(jìn)行升序排列，然后將排列好的數(shù)據(jù)依次放入葉節(jié)點(diǎn)中，再按照各節(jié)點(diǎn)產(chǎn)生的時(shí)間順序，自底向上建立高層的目錄節(jié)點(diǎn)，最后就得到一棵的空間存儲(chǔ)利用率幾乎100% Hilbert R-Tree。地圖顯示時(shí)，空間中距離近的空間對(duì)象被一起讀取顯示的概率大于距離遠(yuǎn)的空間對(duì)象，所以，將距離近的空間對(duì)象物理上靠近存儲(chǔ)，在查詢過(guò)程中可以有效的減少數(shù)據(jù)操作范圍，減少了計(jì)算機(jī)I/O讀取外存的次數(shù)和尋道時(shí)間(I/O的存取單元是一個(gè)物理磁盤塊)，加快查詢過(guò)程。因?yàn)镠ilbert曲線具有優(yōu)良的聚類性質(zhì)，能獲得比一般R-Tree更小的節(jié)點(diǎn)覆蓋區(qū)域，因此具有更高的存儲(chǔ)利用率。

3 基于混合聚類的Hilbert R-Tree的空間索引算法

R-Tree是一種高度平衡樹，顯而易見總節(jié)點(diǎn)數(shù)量越少，查詢效率越高;從R-Tree的結(jié)構(gòu)來(lái)看，讓空間上靠近的空間對(duì)象擁有盡可能近的共同祖先，則R-Tree的查詢效率越高;根據(jù)R-Tree的聚類特性，對(duì)固定數(shù)目的空間對(duì)象劃分聚類個(gè)數(shù)越多，聚類的性能越好。根據(jù)這種思路，本文將K-means聚類算法和K中心聚類算法相結(jié)合，提出一種基于混合聚類的Hilbert R-Tree構(gòu)造方法，將空間相近的點(diǎn)放入相近的葉節(jié)點(diǎn)內(nèi)，從而提高Hilbert R-Tree查詢效率。

3.1混合聚類算法

所謂聚類就是在設(shè)計(jì)空間數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)時(shí)，將空間上相鄰的和查詢上有關(guān)聯(lián)的對(duì)象存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，減少存取時(shí)間，提高查詢效率。在構(gòu)建Hilbert R-Tree之前對(duì)數(shù)據(jù)進(jìn)行采用混合聚類算法處理，將空間上鄰近的對(duì)象聚集到同一個(gè)聚類中，可以得到更小葉節(jié)點(diǎn)的面積，極大提高R-Tree的查詢效率。K-means算法從N個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心，而對(duì)于剩下的其它對(duì)象，則根據(jù)它們與這些聚類中心的距離，分別將它們分配給與其最近的聚類，然后再計(jì)算每個(gè)新聚類的聚類中心(即該聚類中所有對(duì)象的均值)，不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。選擇適當(dāng)?shù)某跏冀饪梢垣@得較好的聚類效果，但是，K-means算法依賴于初始解的選擇，我們引進(jìn)K中心聚類算法。K中心法使用中心點(diǎn)定義原型，其中中心點(diǎn)是一組點(diǎn)中最有代表性的點(diǎn)，利用空間點(diǎn)群之間的距離找到典型點(diǎn)位作為聚類的種子對(duì)象，根據(jù)空間對(duì)象與典型點(diǎn)的距離，將剩余對(duì)象歸到最近的聚類。我們用空間對(duì)象的MBR的中心點(diǎn)代替每一個(gè)空間實(shí)體，設(shè)定N為空間對(duì)象數(shù)，M為R-Tree中每個(gè)節(jié)點(diǎn)所能包含的最大實(shí)體數(shù)，m是每個(gè)節(jié)點(diǎn)包含的最小實(shí)體數(shù)，k為劃分的聚類個(gè)數(shù)。

混合聚類算法如下:

1)設(shè)置k的初值為[N/M]，k的取值范圍[N/M]~[N/m];

2)根據(jù)K中心聚類算法選擇k個(gè)對(duì)象分別賦給k個(gè)集合，作為這k個(gè)集合的初始聚類中心。將k個(gè)對(duì)象的中心作為k個(gè)集合的中心。

3)利用K-means算法，對(duì)剩余的每一個(gè)對(duì)象找到離它最近的聚類中心(該聚類中所有對(duì)象的均值)，并將該對(duì)象分配到該聚類中，對(duì)調(diào)整后的新類計(jì)算新的聚類中心。

4)重復(fù)步驟2)，3)，直至所有空間對(duì)象完全分配到k個(gè)集合中。

5)計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，以覆蓋面積，重疊面積作為評(píng)估指標(biāo)。

6)選擇標(biāo)準(zhǔn)測(cè)度函數(shù)值最小的劃分聚類個(gè)數(shù)。

3.2基于混合聚類的Hilbert R-Tree索引生成算法

利用空間距離比較接近的空間對(duì)象的Hillbert碼值的也比較接近，空間對(duì)象的MBR距離較小的Hilbert碼值相差也較小的性質(zhì)，直接對(duì)葉節(jié)點(diǎn)的MBR進(jìn)行聚類，對(duì)非葉節(jié)點(diǎn)進(jìn)行Hilbert碼值聚類。

樹的生成算法如下:

1)以數(shù)據(jù)MBR為中心，調(diào)用上面的聚類算法，得到k個(gè)聚類中心Ci(i=1，2，…，k)。

2)根據(jù)Hilbert 映射函數(shù)將二維或三維空間映射到一維空間上，求出各個(gè)聚類中要素MBR的Hilbert碼值，并按照各自的Hilbert值升序排列。

3)對(duì)產(chǎn)生的k個(gè)聚類進(jìn)行判別，如果聚類中包含對(duì)象個(gè)數(shù)不大于M，不作處理，自成一個(gè)葉節(jié)點(diǎn)。對(duì)于聚類中對(duì)象個(gè)數(shù)大于M的，求出聚類中實(shí)體對(duì)象MBR的Hilbert碼值，從第一個(gè)開始，按照Hilbert碼值依次分為各含M個(gè)數(shù)據(jù)的組(最后一個(gè)節(jié)點(diǎn)除外)。

4)按照各節(jié)點(diǎn)產(chǎn)生的時(shí)間順序，自底向上生成Hilbert R-Tree。

4 結(jié)果測(cè)試

在相同的軟硬件平臺(tái)上，分別用兩種算法執(zhí)行同一組查詢，實(shí)驗(yàn)選用東莞市地圖數(shù)據(jù)庫(kù)，對(duì)同樣的水文測(cè)站數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)。查詢的響應(yīng)時(shí)間主要有兩部分組成，一部分是讀取與查詢區(qū)域相交的節(jié)點(diǎn)所需時(shí)間;另一部分是CPU處理這些節(jié)點(diǎn)所需時(shí)間。與從外存訪問(wèn)一個(gè)節(jié)點(diǎn)的時(shí)間相比，CPU的響應(yīng)時(shí)間可以忽略。假定沒有緩沖區(qū)的條件下，把所需訪問(wèn)的節(jié)點(diǎn)裝入全部?jī)?nèi)存，磁盤訪問(wèn)次數(shù)和節(jié)點(diǎn)的訪問(wèn)次數(shù)是相等的。由于Hilbert R-Tree具有很好的聚類性質(zhì)，從高維到一維的線性映射的速度也很快，自底向上的建樹次序也使并行處理成為可能，多個(gè)CPU可同時(shí)處理不同的數(shù)據(jù)。從表1可以看出，聚類后的算法節(jié)省建樹的時(shí)間，建立索引耗時(shí)更少。

采用的混合聚類算法基本能夠把實(shí)際空間中比較接近的點(diǎn)聚集在同一個(gè)聚類中，改進(jìn)后的方法實(shí)現(xiàn)了將相近的點(diǎn)放入相同葉節(jié)點(diǎn)中而相距較遠(yuǎn)的點(diǎn)放入不同葉節(jié)點(diǎn)的目的，從而降低了葉節(jié)點(diǎn)的面積，尤其是當(dāng)數(shù)據(jù)分布非均勻時(shí)，對(duì)稀疏和稠密區(qū)域的分別處理，稠密區(qū)域的對(duì)象聚集放置，稀疏的對(duì)象分散放置，查詢性能提高明顯。從表2可以看出，改進(jìn)后的Hilbert R-Treee檢索效率可以提高30%以上。

從圖3可以看出，聚類后的算法較好的實(shí)現(xiàn)了空間對(duì)象的“空間聚類性”，查詢過(guò)程中可以有效的減少數(shù)據(jù)操作范圍，減少了查詢時(shí)磁頭的跳轉(zhuǎn)次數(shù)，涉及更少的磁盤頁(yè)，查詢效率有明顯提高。

5 結(jié)論

本文根據(jù)空間對(duì)象的特征，采用聚類思想對(duì)Hilbert R-Tree的算法進(jìn)行了改進(jìn)，將K-mean聚類算法和K中心聚類算法引入了Hilbert R-Tree中。實(shí)驗(yàn)表明，通過(guò)對(duì)Hilbert R-Tree節(jié)點(diǎn)數(shù)據(jù)的聚類，空間節(jié)點(diǎn)分布也比R-Tree更均勻，減少了需要搜索的路徑以及磁盤訪問(wèn)次數(shù)，提高了查詢效率。以后將進(jìn)一步深入研究緩存對(duì)空間索引的影響。

參考文獻(xiàn):

[1] 過(guò)志峰，王宇翔，楊崇俊.空間數(shù)據(jù)索引與查詢技術(shù)研究及其應(yīng)用[I].計(jì)算機(jī)工程及應(yīng)用，2002，23(1):11-13.

[2] 廖克，等.地球信息科學(xué)導(dǎo)論[M].北京:科學(xué)出版社，2007.

[3] Kanungo T，Mount D M，Netanyahu N S.An Efficient K-means Clustering Algorithm[J].Communications and Computer Sciences，2005，23(9):66-70.

[4] Gaede V， Oliver Gunther. Multidimensional Access Methods[J].ACM Computing Surveys，1998，30(2):170-231.

[5] Beckmann N，Kriegel H P，Schneider R，et al.The R*-Tree:An Efficient Robust Access Method for Points and Rectangles[C].Atlantic City，NJ:Proc. ACM SIGMOD Int.Conf.on Management of Data，1990:322-331.

[6] 顧軍，吳長(zhǎng)斌.常用空間索引技術(shù)的分析[J].微型電腦應(yīng)用，2001(12):38-42.

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

[8] 何江，李志蜀，陳宇.一種基于R樹空間索引技術(shù)的GIS數(shù)據(jù)索引方法[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版，2008，45(6):1342-1343.

[9] 劉彥斌.基于聚類分析的R-Tree空間索引[J].廊坊師范學(xué)院學(xué)報(bào)，2009，9(3):27-292.

[10] Tan Pangning，Steinbach M，Kumar V.Introduction to Data Mining[M].北京:北京人民郵電出版社，2006.

[11] 何小苑，閔華清.基于聚類的Hilbert R-樹空間索引算法[J].計(jì)算機(jī)工程，2009，35(9):39-42.