大數(shù)據(jù)分析中基于MapReduce的空間權重創(chuàng)建方法研究

郭　平

(廣東交通職業(yè)技術學院 信息管理中心，廣東 廣州 510650)

?

大數(shù)據(jù)分析中基于MapReduce的空間權重創(chuàng)建方法研究

郭平

(廣東交通職業(yè)技術學院 信息管理中心，廣東 廣州 510650)

摘要：大數(shù)據(jù)空間分析是Cyber-GIS的重要方面。如何利用現(xiàn)有的網(wǎng)絡基礎設施(比如大規(guī)模計算集群)對大數(shù)據(jù)進行并行分布式空間分析仍然是一大難題。為此，提出一種基于MapReduce的空間權重創(chuàng)建方法。該方法依托Hadoop框架組織計算資源，基于MapReduce模式從大規(guī)模空間數(shù)據(jù)集中高效創(chuàng)建出空間權重：大空間數(shù)據(jù)被分為多個數(shù)據(jù)塊，將映射器分布給計算集群中的不同節(jié)點，以便在數(shù)據(jù)中尋找出空間對象的相鄰對象，由約簡器從不同節(jié)點處收集相關結果并生成權重文件。利用Amazon公司彈性MapReduce的Hadoop框架，從人工空間數(shù)據(jù)中創(chuàng)建基于鄰近概念的權重矩陣進行仿真。實驗結果表明，該方法的性能優(yōu)于傳統(tǒng)方法，解決了大數(shù)據(jù)的空間權重創(chuàng)建問題。

關鍵詞：大數(shù)據(jù)空間分析；MapReduce；空間權重；附近鄰居；可擴展性

0引言

大空間數(shù)據(jù)的出現(xiàn)產(chǎn)生了一些新穎而又頗具挑戰(zhàn)性的科學問題[1-3]，例如，空間數(shù)據(jù)的多尺度表達、基于服務質量保證的空間數(shù)據(jù)互操作等。為此，人們提出了CyberGIS[4]框架，通過一種空間中間件，利用當前網(wǎng)絡融合基礎設施(converged infrastructure，CI)所具有的強大計算資源(比如高性能云計算[4-5])來解決這些問題。該框架將空間數(shù)據(jù)操作、地理可視化、空間模式檢測、空間過程建模和空間分析等分布式地理處理組件，無縫地集成為一種可以高效利用CI計算能力的空間中間件。在這些分布式空間處理組件中，可以解決大空間數(shù)據(jù)問題的并行空間分析方案是網(wǎng)絡地理信息系統(tǒng)(geographic information system，GIS)的重要組件[7]。

空間分析過程包括數(shù)據(jù)預處理、可視化、勘查、模型規(guī)格、估計和驗證[8]。然而，傳統(tǒng)的空間分析數(shù)據(jù)結構和算法以桌面計算機架構為基礎，且只限于桌面計算機架構。鑒于內(nèi)存空間和計算能力有限，無法用于大空間數(shù)據(jù)的空間分析中[9-10]。因此，有必要設計和開發(fā)一種可擴展的網(wǎng)絡GIS系統(tǒng)平臺，為高效的空間分析提供支持。

本文重點研究大數(shù)據(jù)空間分析時的空間權重生成問題。空間權重代表了空間對象的地理相關性，因此，它是空間分析的重要方面?？臻g權重矩陣廣泛應用于空間自相關和空間回歸等多種空間分析算法[11-12]?？臻g權重生成問題主要是指從空間數(shù)據(jù)中提取出空間相鄰信息(鄰近權重)和空間距離(距離權重)等空間結構。然而，傳統(tǒng)的空間權重生成算法[13-14]基于本地硬件(比如CPU、內(nèi)存和硬盤)，性能受限，無法用于處理超大規(guī)?？臻g數(shù)據(jù)集。

因此，本文提出一種基于MapReduce的空間權重創(chuàng)建算法，利用大空間數(shù)據(jù)創(chuàng)建鄰近空間權重。與傳統(tǒng)的權重創(chuàng)建算法不同，該方法運行于MapReduce模式下：映射器分布于計算集群中，可并行搜索附近鄰居，然后約簡器收集結果，進而生成權重矩陣。為了測試該算法的性能，本文設計了相關實驗，利用Amazon公司彈性MapReduce的Hadoop框架從人工空間數(shù)據(jù)中生成Queen鄰近矩陣文件，所用的人工空間數(shù)據(jù)包含多達1.9億個多邊形。實驗結果表明，該算法通過利用高性能計算資源，解決了大空間數(shù)據(jù)基于鄰近概念的空間權重生成問題。

1基于MapReduce的空間權重生成

1.1空間權重

空間權重是空間分析(比如空間自相關測試、空間回歸)的重要方面，需要進行空間結構表示。空間特征的空間結構往往描述為一個n行n列空間權重矩陣W(n表示幾何特征數(shù)量)。如果用featurei和featuej表示為相鄰特征，則單元值wij≠0。對于近鄰權重矩陣，wij的值要么為1(featurei和featuej相鄰)，要么為0(featurei和featuej不相鄰)。

將一個點定義為2個坐標構成的數(shù)組：point=(x,y)，將一個多邊形定義為M個點構成的集合：Polygon={point1,point2,…,pointM}。對一個包含n個多邊形的空間數(shù)據(jù)集，DS={Polygon1,Polygon2,…,PolygonN}，構建一個基于鄰近概念的權重矩陣W，就是要對DS中的每個多邊形Polygoni,i∈[1,N]尋找出所有的相鄰多邊形。有3種類型的鄰近概念可確定權重矩陣中的數(shù)值分布：①rook型鄰近(相鄰多邊形必須共享一條邊)；②bishop型鄰近(相鄰多邊形需要共享一個角)；③queen型鄰近(相鄰多邊形要么共享一條邊要么共享一個角)。

傳統(tǒng)的鄰近權重矩陣生成算法(如GeoDa[13]和PySAL[14])利用幾何特征來確定2個多邊形有沒有共享邊或共享頂點。如果通過比較所有多邊形對的頂點或邊緣來確定鄰近關系，則這一過程的計算成本太大，時間復雜度為O(n2)。如果對這些幾何形狀編制空間索引，則在搜索候選相鄰多邊形時的時間復雜度下降為O(logN)。然而，此時需要額外比較候選和目標幾何形狀間的原始點或邊，以便確定2個幾何形狀是否相鄰。此外，這些算法需要計算機能夠將所有幾何形狀載入內(nèi)存。因此，無法從超大規(guī)?？臻g數(shù)據(jù)集中生成鄰近權重。

為此，本文提出一種基于Hadoop的MapReduce算法(見算法1)，可從超大規(guī)?？臻g數(shù)據(jù)集中創(chuàng)建鄰近權重。該算法基于如下策略：根據(jù)多邊形包含的頂點和邊來對多邊形的情況進行匯總。如果2個多邊形中出現(xiàn)同一個點/邊，則這2個多邊形應該是queen型鄰近多邊形。為了清晰描述本文算法，我們結合queen鄰近權重的創(chuàng)建來描述MapReduce算法。該算法依照相同的匯總思路經(jīng)過簡單更改后即可用于rook或bishop鄰近權重的創(chuàng)建。

首先，為了利用多個計算機節(jié)點實現(xiàn)map任務的并行化，Hadoop將會把數(shù)據(jù)平均分為多個數(shù)據(jù)塊，每個數(shù)據(jù)塊由一個計算機節(jié)點處理。在每個節(jié)點上，映射器為每個頂點創(chuàng)建一個字典，并將相關多邊形添加到數(shù)據(jù)集中。然后，Hadoop系統(tǒng)將會著眼于約簡階段的計算任務，對所有計算機節(jié)點創(chuàng)建的字典進行混洗排序。約簡器將會根據(jù)鍵(頂點)對這些字典進行融合。所有字典中具有相同鍵值的鄰近多邊形組成的集合或數(shù)值，經(jīng)過融合后生成鄰近權重文件。

算法1：鄰近權重生成。

1：point_polygon_dict {}

/*系統(tǒng)輸入： 點：多邊形 */

2：forline∈sys.stdindo

3：items←line.split()

4：poly_id←items[0]

5：forpoint∈items[1:] do

6： ifpoint?point_polygon_dictthen

7：point_polygon_dict[point]←set()

8： end

9：point_polygon_dict[point].add(poly_id)

10： end

11：end

/*為約簡器生成輸出*/

12：forpoint,neighbors∈point_polygon_dict.items() do

13： ifneighbors.length≡1 then

14： printneighbors

15： else

16:formaster_poly∈neighborsdo

17：forneighbor_poly∈neighborsdo

18： ifmaster_poly≠neighbor_polythen

19： printmaster_poly，neighbor_poly

20：end

21：end

22：end

23： end

24：end

1.2MapReduce過程

1.2.1映射

映射的主要目的是利用頂點創(chuàng)建一個{key-value}字典對象作為鍵，同時，創(chuàng)建包含該頂點的一組多邊形作為值。該算法首先從Hadoop系統(tǒng)的標準輸入中讀取數(shù)據(jù)。逐行處理數(shù)據(jù)。每行表示多邊形的幾何信息，且以逗號分隔：polyid,point1,point2,…,pointN。這些信息將被解析并存儲于poly_polygon_dict字典中。當映射器處理完數(shù)據(jù)后，將會對poly_polygon_dict字典中的所有值進行迭代，為約簡器準備(key value)數(shù)據(jù)。因為poly_polygon_dict中的值表示共享相同鍵(頂點)的多邊形，所以，認為它們相鄰。之后，映射器將鍵-值對{polygon:neighbor_polygon}寫為約簡器的相鄰信息。

1.2.2約簡

Hadoop系統(tǒng)將會監(jiān)測和采集所有映射器的輸出。一旦映射任務的進度達到系統(tǒng)配置或用戶指定閾值，則Hadoop系統(tǒng)將會啟動約簡任務。約簡任務分為3步：混洗，排序和約簡。在混洗步驟，Hadoop系統(tǒng)對映射輸出進行混洗并將映射輸出轉移到約簡器作為輸入。在下一個排序步驟中，將會根據(jù){polyid:neighbor_poly_id}字典中多邊形主ID(鍵)對映射輸出進行排序?；煜春团判虿襟E同時進行，以保證每個約簡器的輸入均被正確排序。在約簡步驟中，運行算法2中定義的算法以并行生成每個約簡器的權重文件內(nèi)容。

算法2：鄰近權重生成時的約簡算法。

1：current_master_poly←None

2：current_neighbor_set←set()

3：temp_master_poly←None

/* 系統(tǒng)輸入：{polyid:neighbor_poly_id} */

4：forline∈sys.stdindo

5：neighbors←line.split()

6：temp_master_poly←neighbors[0]

7：temp_neighbor_poly←None

8： ifneighbor.length>0then

9：temp_neighbor_poly=neighbors[0]

10：end

11：ifcurrent_master_poly≡temp_master_polythen

12： iftemp_neighbor_poly≠Nonethen

13：current_neighbor_set

.add(temp_neighbor_poly)

14:end

15：else

16:ifcurrent_master_poly≡Nonethen

17： ifneighbor_poly≠Nonethen

18：Current_neighbor_set←set()

19： else

20：current_neighbor_set←set([neighbor_poly])

21： end

22:else

23： WriteWeightsFilecurrent_master_poly，current_neighbor_set

24： end

25：end

26：end /* 在需要情況下處理最后一行 */

27：ifcurrent_master_poly≡temp_master_polythen/* 將GAL結果寫入輸出權重文件中 */

28：num_neighbors←current_neighbor_set.length()

29： printcurrent_master_poly,num_neighbors

30： printcurrent_neighbor_set.items()

31：end

1.2.3生成鄰近權重文件

因為每個約簡器只將其輸入寫入本地磁盤，所以，需要一個專門的融合步驟將所有單個結果進行融合，以生成一個有效的權重文件。本文采用Hadoop平臺提供的分布式拷貝工具(DistCp)來完成MapReduce模式下的融合任務。為了加快融合任務的速度，對約簡器做適當配置，將其輸出壓縮為GNU zip格式，于是，數(shù)據(jù)服務器和計算節(jié)點間的數(shù)據(jù)傳輸速度加快，且壓縮后的文件可直接串聯(lián)。

2仿真實驗

2.1樣本數(shù)據(jù)集

本文實驗使用的底圖為美國芝加哥市的地塊數(shù)據(jù)。該地塊數(shù)據(jù)包含592 521個多邊形。為了模擬大規(guī)模數(shù)據(jù)集，利用該底圖創(chuàng)建人工大數(shù)據(jù)：人工多次復制該底圖，然后并排放到一起，生成一個大型人工底圖。例如，圖1即為4倍于原始數(shù)據(jù)且含有2 370 084個多邊形的數(shù)據(jù)圖。在實驗中創(chuàng)建的最大規(guī)模數(shù)據(jù)為32倍于原始數(shù)據(jù)、含有18 960 672個多邊形的數(shù)據(jù)。整個數(shù)據(jù)集包括原始數(shù)據(jù)的1倍、2倍、4倍、8倍、16倍和32倍數(shù)據(jù)。

圖1　底圖連續(xù)復制4次生成的人工數(shù)據(jù)Fig.1　After continuous replication 4 times to generate artificial data

2.2測試系統(tǒng)

本文選擇Amazon的彈性MapReduce(elastic mapreduce，EMR)服務(http://aws.amazon.com/)來創(chuàng)建一個Hadoop測試系統(tǒng)。Amazon EMR服務提供了一種易于使用的可定制Hadoop系統(tǒng)。采用Amazon提供的Hadoop缺省配置。我們選擇運行于Amazon EMR上、節(jié)點數(shù)量為1至18個節(jié)點的“C3 Extra Large(C3.xlarge)”類型計算機實例集群。除了計算機集群外，Hadoop系統(tǒng)運行時還通過一個主節(jié)點來監(jiān)測所有計算機實例并與所有計算機實例進行通信。C3.xlarge節(jié)點的配置包括7.5 GB內(nèi)存，14核(4核×3.5個單元)CPU，80 GB (2×40 GB SSD)，64位操作系統(tǒng)和500 Mbit/s中等網(wǎng)速。除了Hadoop測試系統(tǒng)外，我們還在一臺單機上測試了相同的MapReduce算法，單機配置為2.93 GHz 8核CPU，16 GByte內(nèi)存，100 GByte硬盤，64位操作系統(tǒng)。

2.3結果

為了測試本文MapReduce性能，利用python語言來實現(xiàn)一個桌面版本及通過Hadoop的流式管道功能運行另外一種Hadoop版本。第1個實驗是在一臺測試單機上運行MapReduce算法。該算法從不同數(shù)據(jù)規(guī)模中生成鄰近權重的運行時間如圖2所示。從圖2可以看到，隨著數(shù)據(jù)規(guī)模的增長，本文算法的運行時間也在增加。該算法的復雜度為O(N)，在處理16倍的數(shù)據(jù)集(9 480 338個多邊形)時達到最大計算能力。

圖2　利用6個計算機節(jié)點從不同數(shù)據(jù)規(guī)模中生成鄰近權重Fig.2　Using 6 computer nodes to generate neighboring weights from different data scale

第2個實驗是在Amazon EMR Hadoop系統(tǒng)上運行MapReduce算法。首先，對包含一個主節(jié)點和6個C3.xlarge節(jié)點的Hadoop系統(tǒng)進行配置，分別測試1倍、2倍、4倍、8倍、16倍和32倍數(shù)據(jù)時的算法性能。該算法從不同數(shù)據(jù)規(guī)模中生成鄰近權重的運行時間見圖2(方點線)。因為Hadoop需要花費額外時間傳遞程序及與運行節(jié)點通信，所以，如果數(shù)據(jù)集為原始數(shù)據(jù)的4倍以下(大約2百萬個多邊形)，則運行時間慢于桌面計算機上運行相同程序所需時間。然而，數(shù)據(jù)集越大，該算法在Hadoop系統(tǒng)上的性能越高。例如，對于8倍數(shù)據(jù)，算法在Hadoop上的完成時間為167 s，其運行時間遠快于桌面計算機(482.67 s)。此外，運行時間呈線性增長，表明本文算法隨著數(shù)據(jù)規(guī)模的增長具有良好的可擴展性。

然后，在后續(xù)測試中，本文創(chuàng)建帶有6, 12, 14, 18個計算機節(jié)點的不同Hadoop系統(tǒng)，以便利用32倍數(shù)據(jù)創(chuàng)建鄰近權重。運行時間如圖3所示。利用Hadoop中的18個計算機節(jié)點，可在163 s內(nèi)生成32倍數(shù)據(jù)的鄰近權重，這是我們在所有測試中獲得的最優(yōu)性能。在圖3中，當計算機節(jié)點數(shù)量增多時，運行時間沒有線性下降。這一現(xiàn)象是合理的，因為當計算節(jié)點數(shù)量增多時，需要額外時間在Hadoop系統(tǒng)內(nèi)進行通信。

圖3　利用不同計算機節(jié)點從32倍數(shù)據(jù)中生成鄰近權重Fig.3　Using different computer nodes to generate neighboring weights from 32 times data

最后，為了進一步體現(xiàn)本文方法的優(yōu)越性，比較本文方法與傳統(tǒng)的鄰近權重矩陣生成算法GeoDa[13]和PySAL[14]從不同數(shù)據(jù)規(guī)模中生成鄰近權重的運行時間，實驗結果如圖4所示。從圖4可以看到，隨著數(shù)據(jù)規(guī)模的增加，不同方法的運行時間都在顯著增加。但總的來說，本文方法的性能更優(yōu)，從1倍數(shù)據(jù)到32倍數(shù)據(jù)，本文方法的運行時間相比GeoD和PySAL平均降低了約14.15%和17.64%。仔細分析其原因可知，這主要是因為GeoD和PySAL需要計算幾何特征間的距離，這種基于距離的計算方法容易受到數(shù)據(jù)規(guī)模和數(shù)據(jù)分布的影響，另外GeoD和PySAL主要基于本地硬件，隨著數(shù)據(jù)規(guī)模的增加，它們的性能嚴重受限，因此，運行時間較長。而本文方法基于鄰近概念來創(chuàng)建空間權重，充分利用了空間對象的地理相關性，通過MapReduce模式避免了不必要的搜索操作，節(jié)省了時間。

3結束語

本文對大數(shù)據(jù)空間分析時的空間權重生成問題進行研究，提出一種MapReduce算法。該算法利用Amazon EC2云計算平臺等高性能計算資源，可為大空間數(shù)據(jù)(約1.9億個多邊形)生成權重文件，解決了大空間數(shù)據(jù)的鄰近權重生成問題。仿真實驗結果表明，本文算法的性能優(yōu)于傳統(tǒng)的以桌面計算機架構為基礎的方法。

圖4　不同方法的運行時間比較Fig.4　Running time comparison of different methods

參考文獻：

[1]李德毅．大數(shù)據(jù)認知—“2015 大數(shù)據(jù)價值實現(xiàn)之路高峰論壇”主題報告[J]．重慶理工大學學報：自然科學，2015(9):1-6．

LI Deyi．Big Data Cognition: Keynote Lecture of“2015 Forum of Big Data Value Realization Road”[J]．Journal of Chongqing University of Technology：Natural Science，2015(9):1-6．

[2]吳燁, 陳犖, 熊偉, 等. 面向高效檢索的多源地理空間數(shù)據(jù)關聯(lián)模型[J]. 計算機學報, 2014, 37(9): 1999-2010

WU Ye, CHEN Luo,XIONG Wei,et al. Multi-Source Geospatial Data Correlation Model for Efficient Retrieval [J].Chinese Journal of Computers, 2014, 37(9): 1999-2010

[3]GOODCHILD M F. Whose hand on the tiller? Revisiting Spatial Statistical Analysis and GIS[M]. Berlin Heidelberg:Springer, 2010: 49-59.

[4]WANG S. A CyberGIS framework for the synthesis of cyber infrastructure, GIS, and spatial analysis [J]. Annals of the Association of American Geographers, 2010, 100(3): 535-557.

[5]劉榮華, 魏加華, 翁燕章, 等. HydroMP: 基于云計算的水動力學建模及計算服務平臺[J]. 清華大學學報: 自然科學版, 2014 (5): 575-583.

LIU Ronghua,WEI Jiahua,WENG Yanzhang,et al. HydroMP: A cloud computing based platform for hydraulic modeling and simulation service[J].Journal of Tsinghua University: Science and Technology 2014(5): 575-583.

[6]WANG S, ANSELIN L, BHADURI B, et al. CyberGIS software: a synthetic review and integration roadmap[J]. International Journal of Geographical Information Science, 2013, 27(11): 2122-2145.

[7]ANSELIN L, REY S J. Spatial econometrics in an age of CyberGIScience[J]. International Journal of Geographical Information Science, 2012, 26(12): 2211-2226.

[8]ANSELIN L, REY S J. Spatial econometrics in an age of CyberGIScience[J]. International Journal of Geographical Information Science, 2012, 26(12): 2211-2226.

[9]關麗, 呂雪鋒. 面向空間數(shù)據(jù)組織的地理空間剖分框架性質分析[J]. 北京大學學報: 自然科學版, 2012, 48(1): 123-132.

GUAN Li,LV Xuefeng. Properties Analysis of Geospatial Subdivision Grid Framework for Spatial Data Organization[J].Journal of Peking University: Natural Science Edition, 2012, 48(1): 123-132.

[10] CRAMPTON J W, GRAHAM M, POORTHUIS A, et al. Beyond the geotag: situating ‘big data’and leveraging the potential of the geoweb [J]. Cartography and Geographic Information Science, 2013, 40(2): 130-139.

[11] WAGNER H H, FORTIN M J. A conceptual framework for the spatial analysis of landscape genetic data [J]. Conservation Genetics, 2013, 14(2): 253-261.

[12] 陳江平, 黃炳堅. 數(shù)據(jù)空間自相關性對關聯(lián)規(guī)則的挖掘與實驗分析[J]. 地球信息科學學報, 2011, 13(1): 109-117.

CHEN Jiangping, HUANG Bingjian. Application and Effects of Data Spatial Autocorrelation on Associstion Rule Mining [J].Journal of Geo-Information Science,2011, 13(1): 109-117

[13] ANSELIN L, SYABRI I, KHO Y. GeoDa: an introduction to spatial data analysis[M]. Berlin Heidelberg: Springer, 2010:73-89.

[14] REY S J, ANSELIN L. PySAL: A Python library of spatial analytical methods[M]. Berlin Heidelberg: Springer, 2010: 175-193.

DOI：10.3979/j.issn.1673-825X.2016.04.014

收稿日期：2015-01-28

修訂日期：2016-04-29通訊作者：郭平hdgp@163.com

基金項目：廣東省交通運輸廳科技項目( 2013-02-093)

Foundation Item：The Guangdong Provincial Communications Department Project (2013-02-093)

中圖分類號：TP391

文獻標志碼：A

文章編號：1673-825X(2016)04-0533-06

作者簡介：

郭平(1970-)，男，湖南澧縣人，副教授，碩士,主要研究方向為物聯(lián)網(wǎng)、云計算、大數(shù)據(jù)。E-mail: hdgp@163.com。

(編輯：劉勇)

Research on construction method of spatial weights based on mapreduce in analysis of big data

GUO Ping

(Information Management Center, GuangDong Communications Polytechnic, Guangzhou 510650, P.R. China)

Abstract:Spatial analysis of big data is a key component of Cyber-GIS. However, how to exploit existing cyber infrastructure (e.g. large computing clusters) in performing parallel and distributed spatial analysis on Big data remains a huge challenge. To solve this problem, a construction method of spatial weights based on MapReduce is proposed in this paper, which creates spatial weights from very large spatial datasets efficiently by using computing resources that are organized in the Hadoop framework: the big spatial data is firstly chunked into pieces, then the mappers are distributed to different nodes in the computing cluster to find neighbors of spatial objects in the data, and finally the reducers collect the results from different nodes to generate the weights file. To test the performance of this algorithm, we design experiment to create contiguity-based weights matrix from artificial spatial data using Amazon’s Hadoop framework called Elastic MapReduce. The experimental results show that the performance of the proposed method is better than the traditional method, and solve the construct problem of spatial weight in big data.

Keywords：spatial analysis of big data; MapReduce; spatial weights; contiguous neighbors; scalability