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

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

關鍵詞:空間索引;混合聚類;Hilbert R-Tree;K-means;K中心點;空間查詢

中圖分類號:TP311文獻標識碼:A 文章編號: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，地理信息系統)研究和管理的范圍不斷擴大，精度不斷提高，需要處理的數據量也不斷激增。由于空間數據本身的復雜性，以及目前對海量空間數據快速查詢的要求日益提高，當前GIS正面臨著大數據量空間數據存儲及管理的挑戰。如何組織、檢索這些海量數據是空間索引要解決的問題之一。與非空間數據不同，空間索引處理的數據是二維、三維甚至是多維的不規則數據，故空間數據庫的開銷一般要比關系數據庫要大[1]。所以研究空間索引結構、尋求更高效的空間索引算法，引起了人們越來越多的關注和興趣。

近年來，人們提出了大量的空間索引方法，如R-Tree及其變種R*-Tree、R+-Tree、四叉樹、Quad-Tree、Grid索引等等。R-Tree是空間數據庫中最流行的索引結構之一[2]，但是在動態構建樹時容易造成空間區域重疊大，以及產生大量的“死空間”(不包含空間對象的索引空間)，檢索效率不高。

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

Hilbert R-Tree是由R-Tree發展而來的，具有R-Tree的特征，通過對R-Tree和Hilbert R-Tree的結構進行比較和分析，提出了一種利用混合聚類技術和Hilbert R-Tree相結合的空間索引算法，降低了構造樹的時間復雜度，縮短了計算時間，提高了查詢效率。

1 R-Tree簡介

R-Tree最初由Guttman在1984年提出的，它是B-Tree在K維上的自然擴展，是空間數據庫中最常用的空間索引結構[4]。R-Tree是一種完全動態的層次數據結構，在葉子節點中包含指向實際數據對象的指針，插入、刪除和查詢可以同時進行，并且不需要周期性的索引重組。如圖1所示的平面劃分對應的R-Tree為圖2。

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

2 Hilbert R-Tree簡介

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

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

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

3.1混合聚類算法

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

混合聚類算法如下:

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

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

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

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

5)計算標準測度函數，以覆蓋面積，重疊面積作為評估指標。

6)選擇標準測度函數值最小的劃分聚類個數。

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

利用空間距離比較接近的空間對象的Hillbert碼值的也比較接近，空間對象的MBR距離較小的Hilbert碼值相差也較小的性質，直接對葉節點的MBR進行聚類，對非葉節點進行Hilbert碼值聚類。

樹的生成算法如下:

1)以數據MBR為中心，調用上面的聚類算法，得到k個聚類中心Ci(i=1，2，…，k)。

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

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

4)按照各節點產生的時間順序，自底向上生成Hilbert R-Tree。

4 結果測試

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

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

從圖3可以看出，聚類后的算法較好的實現了空間對象的“空間聚類性”，查詢過程中可以有效的減少數據操作范圍，減少了查詢時磁頭的跳轉次數，涉及更少的磁盤頁，查詢效率有明顯提高。

5 結論

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

參考文獻:

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

[2] 廖克，等.地球信息科學導論[M].北京:科學出版社，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] 顧軍，吳長斌.常用空間索引技術的分析[J].微型電腦應用，2001(12):38-42.

[7] 張明波，陸峰，申排偉，等.R樹家族的演變和發展[J].計算機學報，2005，28(3):290-292

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

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

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

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