分層貪心聚簇算法研究

王炳乾，陳建華，許開(kāi)行，盧健

?

分層貪心聚簇算法研究

王炳乾1，陳建華2，許開(kāi)行2，盧健2

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

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

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

1 引言

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

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

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

目前，在線地圖點(diǎn)聚簇算法已有較成熟的應(yīng)用，很多在線地圖API均提供點(diǎn)聚簇的功能。點(diǎn)聚簇算法不僅相對(duì)簡(jiǎn)單，而且很實(shí)用，但是如果缺少了，在線地圖則無(wú)法對(duì)海量的標(biāo)記點(diǎn)要素進(jìn)行較好顯示。因此，對(duì)于在線地圖的二次開(kāi)發(fā)者來(lái)說(shuō)，這也是一個(gè)十分重要的功能，而且對(duì)于研究Web地圖點(diǎn)聚簇算法有重要意義[6]。

2 分層貪心聚類

2.1 原理

2.1.1 分層貪心聚簇

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

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

圖1 貪心聚類工作原理

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

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

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

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

2.1.2 KD-Tree

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

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

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

注：直線上的標(biāo)記點(diǎn)為根節(jié)點(diǎn)，上面的點(diǎn)歸為左子樹(shù)，下面的點(diǎn)歸為右子樹(shù)

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

表1 KD-Tree中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

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

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

2.2 實(shí)驗(yàn)

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

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

圖5 點(diǎn)聚合前標(biāo)記點(diǎn)分布情況

圖6 點(diǎn)聚合后標(biāo)記點(diǎn)分布情況

3 算法效果對(duì)比分析

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

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

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

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

3.2 算法對(duì)比分析

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

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

表3 效果對(duì)比

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

4 結(jié)論

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

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

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

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

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

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

［6］崔鄧.基于智能手機(jī)軌跡提取停留點(diǎn)的時(shí)空聚類算法研究［D］.重慶：西南大學(xué)，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］.計(jì)算機(jī)與數(shù)字工程，2012（02）：96-98，126.

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

2095－6835（2019）01－0043－03

TP301.6

A

10.15913/j.cnki.kjycx.2019.01.043

〔編輯：嚴(yán)麗琴〕