王炳乾，陳建華，許開行，盧健

?

分層貪心聚簇算法研究

王炳乾1，陳建華2，許開行2，盧健2

（1.成都理工大學 地球科學學院，四川 成都 610059；2.成都理工大學 地球物理學院，四川 成都 610059）

第三方地圖API功能的增強給地圖應用的搭建提供了便利，但是在地圖應用中，經常會遇到海量空間點數(shù)據(jù)的顯示問題。那么如何在有限的可視區(qū)域內利用最小的區(qū)域顯示最全面的信息，同時又不產生影響地圖可視化效果的重疊覆蓋，就需要利用地圖標記點聚簇技術。重點研究了采用KD-Tree的分層貪心聚簇算法，并基于OpenLayers API實現(xiàn)了該算法，對比分析該算法與基于距離的標記點聚簇算法在處理大量數(shù)據(jù)點時的運行效果。

海量空間點數(shù)據(jù)；聚簇算法；OpenLayers API；KD-Tree

1 引言

近年來，伴隨著互聯(lián)網科技的快速發(fā)展以及新興技術的迅速崛起，瀏覽器端所能呈現(xiàn)的功能越來越豐富。應運而生的數(shù)字地圖逐漸取代了傳統(tǒng)地圖的“地位”，獨創(chuàng)性地將傳統(tǒng)地圖與網頁相結合，并以其立體化、動態(tài)化、虛擬化的特點迅速成為新時代的寵兒，極大豐富和便利了人們的生活。

在用戶體驗上，數(shù)字地圖為用戶提供了一種信息與地圖相結合的新的信息查詢方式，而且信息的查詢結果通常以標記點的形式直觀、全面、精準地呈現(xiàn)在地圖上[1]。但是，在數(shù)據(jù)急速膨脹的今天，海量的標記點數(shù)據(jù)如果同時呈現(xiàn)在地圖上，不僅會大大增加客戶端的渲染時間，造成客戶端卡頓，更重要的是會使人產生密集恐懼癥，極大降低用戶體驗的舒適度。為了解決這一問題，即在用戶有限的可視區(qū)域范圍內利用最小的可視區(qū)域展示最全面的信息，但又不產生數(shù)據(jù)的相互重疊，我們需要用到標記聚簇技術。由于不同的聚簇算法在顯示效率上千差萬別，效率的高低也直接影響著用戶體驗的舒適度，因此，考慮到聚合效率的問題，地圖聚合通常采用原理簡單、效率較高的聚合算法[2]，研究聚簇算法的效率也是文章討論的重點之一。

聚簇分析是統(tǒng)計學的分支之一，學術界已進行了廣泛研究，但以往的研究主要集中在基于距離的聚簇分析，諸如K-means算法、K-medoids算法及其他一些算法等，而且這些算法的聚簇分析工具早已被加入到許多統(tǒng)計分析軟件包或系統(tǒng)中[3]。為了進一步提升聚簇算法的性能，彌補數(shù)據(jù)挖掘領域中聚簇方法的某些不足，學術界開始將聚簇方法與其他領域相結合，以期實現(xiàn)并發(fā)揮聚簇方法的最優(yōu)性能[4]，常用的有免疫算法、螞蟻算法、遺傳算法等一些著名算法。就免疫算法而言，隨著免疫計算的發(fā)展，人工免疫系統(tǒng)這一嶄新的應用領域的出現(xiàn)，給聚簇分析領域注入了新的活力[5]。

目前，在線地圖點聚簇算法已有較成熟的應用，很多在線地圖API均提供點聚簇的功能。點聚簇算法不僅相對簡單，而且很實用，但是如果缺少了，在線地圖則無法對海量的標記點要素進行較好顯示。因此，對于在線地圖的二次開發(fā)者來說，這也是一個十分重要的功能，而且對于研究Web地圖點聚簇算法有重要意義[6]。

2 分層貪心聚類

2.1 原理

2.1.1 分層貪心聚簇

將點集合到特定縮放級別中的簡單有效的方法稱為貪心聚簇（Greedy Clustering）[7]，它的工作原理如下：①從數(shù)據(jù)集的任何一點開始；②查找該點周圍某一半徑內的所有點；③與附近的點組成一個新的群集；④選擇一個不屬于集群的新點，并重復，直到訪問了所有的點。

貪心聚類工作原理如圖1所示。

圖1 貪心聚類工作原理

對于地圖的每個縮放級別，都進行上述步驟操作的代價是極其高昂的。例如，如果縮放級別是從0～18級，瀏覽器就不得不處理整個數(shù)據(jù)集19次，而且由于每個集群需要適應指數(shù)級增加的點數(shù)，所以在較低縮放級別上的聚類將變得很慢。通過重用計算可以避免這樣的問題。對縮放級別18進行聚類后，將生成的聚類分組為新的z17聚類，使用z17簇形成16簇，以此類推，直至最小縮放級別。由于每個這樣的步驟所需要處理的點數(shù)都呈指數(shù)下降，所以能快速對所有縮放級別進行聚類。分層貪心聚類工作原理如圖2所示。

圖2 分層貪心聚類工作原理

以上方法即為分層貪心聚簇（Hierarchical Greedy Clustering）[8]，不同于更復雜的集群算法，它可以迅速在瀏覽器中處理數(shù)百萬個點，而且可以在交互式地圖上瀏覽點數(shù)據(jù)集。在交互式地圖中實現(xiàn)這種聚簇方法存在兩個潛在的煩瑣的操作：①找到一定半徑內的所有點；②在當前屏幕上查找集群。

半徑查詢的最簡單方法是循環(huán)遍歷所有的點，并保存那些足夠接近查詢點的點。但是對于每個潛在的集群都需要進行多次這樣的查詢，難免造成效率低下的問題。另外，點擊拖動或縮放地圖時都需要這些點，如何遍歷屏幕查詢所有的點也是一個問題。為了有效解決這一問題，本文引入了空間索引，并利用空間索引中特殊的數(shù)據(jù)結構處理點，它的優(yōu)勢是能夠有效、快速地進行查詢，并立即進行任意數(shù)量的后續(xù)查詢，KD-Tree數(shù)據(jù)結構即可完成這樣的任務。

2.1.2 KD-Tree

KD-Tree是一棵二叉樹，樹中存儲的數(shù)據(jù)是維數(shù)據(jù)。在一個維數(shù)據(jù)集合上構建一棵KD-Tree代表了對該維數(shù)據(jù)集合構成的維空間的一個劃分，即樹中的每個結點對應一個維的超矩形區(qū)域（Hyperrectangle）[9]。本文所用到的KD-Tree主要對二維數(shù)據(jù)集合所構成的二維平面進行劃分。

KD-Tree作為BSP-Tree（Binary Space Partition Tree）分割空間時存在的特殊情況，在了解KD-Tree之前先對BSP-Tree進行簡單介紹。BSP-Tree，即二叉空間分割樹，也是一棵二叉樹，基本思想是：任何一個平面都可以將空間劃分為兩個半空間，此外，如果在任何一個半空間中仍存在一個平面，這個平面將會繼續(xù)分割該空間為更小的半空間。推廣至二維平面，平面映射為一條直線，任何一條直線都能將一個二維平面分割為兩個子平面。BSP-Tree分割二維平面如圖3所示。接下來再不斷劃分，如此便構成了一棵BSP-Tree。分割線稱之為分割超平面（splitting hyperplane）。超平面都垂直于軸的BSP-Tree就是KD-Tree，同樣的數(shù)據(jù)集用KD-Tree來進行分割時，結果如圖4所示。

KD-Tree算法可以分為兩個部分，一部分是構建KD-Tree本身的數(shù)據(jù)結構，另一部分是建立在KD-Tree這種數(shù)據(jù)結構之上的查詢算法。KD-Tree中每個節(jié)點表示了一個空間范圍，每個節(jié)點中主要包含的數(shù)據(jù)結構如表1所示。

注：直線上的標記點為根節(jié)點，上面的點歸為左子樹，下面的點歸為右子樹

注：中間直線上的點為根節(jié)點，下一層是淺灰色，再下一層是深灰色，最后是黑色，這樣就構成了一棵簡單的KD-Tree

表1 KD-Tree中每個節(jié)點的數(shù)據(jù)結構

域名數(shù)據(jù)類型描述 Node-data數(shù)據(jù)矢量數(shù)據(jù)集中某個數(shù)據(jù)點，是n維矢量（這里也就是k維） Range空間矢量該節(jié)點所代表的空間范圍 Split整數(shù)垂直于分割超平面的方向軸序號 LeftKD-Tree左子樹 RightKD-Tree右子樹 ParentKD-Tree父節(jié)點

軸點的選擇是建立樹的關鍵，當數(shù)據(jù)維度只有2維時，表1中Split的值可由、軸確定，可將兩個軸分別編號為0和1，通過計算、方向上數(shù)據(jù)的方差，以得到的方差大小確定Split域首先該取何值，方向上的方差大則首先取0，反之則取1，即Split={0，1}或Split={1，0}，這里的方法稱為最大方差法，方差越大，說明數(shù)據(jù)在或方向上的離散程度越大，即數(shù)據(jù)分布分散，此時在這個方向上容易將它們劃分開，而且在該方向上進行的數(shù)據(jù)分割可以獲得最大的平衡程度。建樹需要遵循兩個準則：①建立的樹應盡量平衡，平衡度越高說明分割得越均勻，所用搜索時間也相應越少；②最大化鄰域搜索的剪枝機會，所謂剪枝，可理解為在搜索算法中，通過某種判斷避免一些不必要的遍歷。

2.2 實驗

SuperCluster（超級聚合）是由MapBox的工程師Vladimir Agafonkin于2016年發(fā)布的，是一個用于瀏覽器和節(jié)點的快速地理空間點集群JavaScript庫。由于其對于Mapbox GL JS來說非常適用，所以將其作為一個獨立的庫發(fā)布，可以方便其他軟件利用其進行快速算法。

實驗中，同樣基于OSM地圖，本文在劃定的矩形范圍內進行了隨機標記點的生成，初步設置了5 000個標記點。為了將分層貪心聚類算法與OpenLayers在線地圖平臺相結合，構建了名為superCluster的類，類中主要對OpenLayers地圖上聚類結果的顯示樣式進行設置，使用時只需實例化此類，然后傳入點圖層數(shù)據(jù)即可。聚合前標記點分布情況如圖5所示，聚合后分布情況如圖6所示。

圖5 點聚合前標記點分布情況

圖6 點聚合后標記點分布情況

3 算法效果對比分析

3.1 算法運行測試環(huán)境概述

算法運行測試環(huán)境如表2所示。

表2 算法測試環(huán)境

操作系統(tǒng)Windows 10 CPUAMD A6-5200 APU with Radeon（TM）HD Graphics 2.00 GHz 系統(tǒng)內存4.00 GB 瀏覽器及其版本Google Chrome 58.0.3029.110

3.2 算法對比分析

實驗中分別對20組數(shù)據(jù)點集合的算法運行效果進行測試，數(shù)據(jù)點數(shù)量為5 000～100 000，每組之間數(shù)據(jù)點跨度為5 000個點。取前7組效果對比，結果如表3所示。

表3中流暢、卡頓現(xiàn)象為運行算法進行不同縮放級別點瀏覽時地圖顯示點的情況。從表3可以看出分貪心聚簇算法較之基于距離的點聚簇算法在效果上有明顯優(yōu)勢。后續(xù)實驗中對分層貪心聚類算法進行了數(shù)十萬乃至百萬數(shù)據(jù)點的聚合，效果也十分明顯，瀏覽不同縮放級別下點的情況也沒有卡頓現(xiàn)象?；诰嚯x的點聚簇算法由于迭代的原因，每個點集群均需對所有點進行遍歷，運行效率可想而知。分層貪心聚簇算法本身即對分層數(shù)據(jù)進行處理，加之空間索引技術KD-Tree的使用對算法本身產生如虎添翼的效果。

表3 效果對比

數(shù)據(jù)點數(shù)量基于距離點聚簇算法運行效果分層貪心聚簇算法運行效果 5 000流暢流暢 10 000流暢流暢 15 000出現(xiàn)卡頓流暢 25 000卡頓流暢 30 000明顯卡頓流暢 35 000明顯卡頓流暢 40 000明顯卡頓流暢

4 結論

通過比較分析，本文得出如下結論：基于距離的標記點聚簇算法雖然實現(xiàn)簡單，但該算法對于海量數(shù)據(jù)點的聚簇實現(xiàn)效果不佳；分層貪心聚簇算法實現(xiàn)相對復雜，在加入了空間索引技術KD-Tree之后，該算法在處理海量數(shù)據(jù)點呈現(xiàn)聚簇效果上更具優(yōu)勢，且更適用于在瀏覽器上處理空間點聚簇顯示，是一個非常優(yōu)秀的算法。

［1］戴鳳嬌，肖林華，楊琭，等.基于百度地圖的標記點聚合算法研究［J］.中國科技信息，2013（23）：82-85.

［2］劉果.基于網格密度的海量空間點聚合顯示算法［J］.測繪與空間地理信息，2015，38（4）：174-176.

［3］黃韜，劉勝輝，譚艷娜.基于k-means聚類算法的研究［J］.計算機技術與發(fā)展，2011（7）：54-57，62.

［4］李波.基于單親遺傳算法的聚類分析研究［D］.呼和浩特：內蒙古大學，2011.

［5］方方，王子英.K-means 聚類分析在人體體型分類中的應用［J］.東華大學學報（自然科學版），2014， 40（5）：593-598.

［6］崔鄧.基于智能手機軌跡提取停留點的時空聚類算法研究［D］.重慶：西南大學，2016.

［7］Gou S P，Zhang J，Jiao L C.SAR image segmentation based on Immune Greedy Spectral Clustering［C］//Asian-pacific Conference on Synthetic Aperture，2009：672-675.

［8］Ernst Althaus，Andreas Hildebrandt，Anna Katharina Hildebrandt.A Greedy Algorithm for Hierarchical Complete Linkage Clustering［M］.Berlin：Springer International Publishing，2014.

［9］杜振鵬，李德華.基于KD-Tree搜索和SURF特征的圖像匹配算法研究［J］.計算機與數(shù)字工程，2012（02）：96-98，126.

［10］徐建民，李歡，劉博寧.在游戲中利用鄰域特性擴展的KD-Tree及其查找算法［J］.計算機科學，2011，38（3）：257-262.

2095－6835（2019）01－0043－03

TP301.6

A

10.15913/j.cnki.kjycx.2019.01.043

〔編輯：嚴麗琴〕