一種微博POI簽到數(shù)據(jù)的四叉樹格網(wǎng)獲取方法

黃 磊，許大璐，任 福，杜清運(yùn)，李浪姣，張 琛

（1. 武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079；2. 浙江省地理信息中心，浙江 杭州 310012）

0 引 言

如何快速高效地獲取大規(guī)模簽到數(shù)據(jù)是進(jìn)行人類活動(dòng)有關(guān)的數(shù)據(jù)分析和挖掘必須解決的問題。新浪微博作為我國最活躍的社交媒體平臺(tái)之一，月活躍用戶達(dá)3.13億，日活躍用戶為1.39億[10]。龐大的新浪微博用戶群體狀態(tài)信息更新頻繁，產(chǎn)生大量的活動(dòng)信息。本文以抓取新浪微博興趣點(diǎn)（Point of Interest, POI）簽到數(shù)據(jù)為例，設(shè)計(jì)了一種四叉樹動(dòng)態(tài)格網(wǎng)抓取數(shù)據(jù)方法，由于新浪微博為了防止客戶端的過度采集導(dǎo)致服務(wù)器資源的濫用，對(duì)返回的POI數(shù)量作了一定的限制，因此，本文在設(shè)計(jì)四叉樹格網(wǎng)時(shí)對(duì)采集的POI數(shù)量設(shè)定了閾值，當(dāng)某一格網(wǎng)內(nèi)返回的POI數(shù)量達(dá)到閾值時(shí)，就采用四叉樹分裂法動(dòng)態(tài)分割當(dāng)前格網(wǎng)遞歸獲取數(shù)據(jù)，從而保證數(shù)據(jù)采集的完整性。與傳統(tǒng)的規(guī)則格網(wǎng)的獲取方式相比，四叉樹格網(wǎng)在獲取數(shù)據(jù)的完整性方面有明顯的優(yōu)勢，從獲取數(shù)據(jù)的結(jié)果分布來看，采用規(guī)則格網(wǎng)方式的數(shù)據(jù)缺失主要集中在高密度的POI地區(qū)，并沒有將高密度區(qū)域的POI數(shù)據(jù)采集完畢，而采用四叉樹方式能避免此問題。在現(xiàn)行的開放平臺(tái)都對(duì)開發(fā)者作了相應(yīng)限制的背景下，采用四叉樹劃分格網(wǎng)的方法對(duì)于獲取完整的研究數(shù)據(jù)具有一定的實(shí)際作用。

1 常規(guī)的數(shù)據(jù)獲取方式

目前常見的新浪微博數(shù)據(jù)獲取主要有3種方式：通過網(wǎng)絡(luò)爬蟲的方式、調(diào)用新浪微博開放平臺(tái)API的方式和將網(wǎng)絡(luò)爬蟲與微博API相結(jié)合的策略。

1.1 網(wǎng)絡(luò)爬蟲的數(shù)據(jù)獲取

網(wǎng)絡(luò)爬蟲（Web Crawler）也稱網(wǎng)絡(luò)蜘蛛（Web Spider），是一種按照特定規(guī)則抓取網(wǎng)頁信息的程序。抓取網(wǎng)頁的過程，實(shí)際上和平時(shí)使用瀏覽器訪問網(wǎng)頁的原理是一樣的。在瀏覽器地址欄輸入某個(gè)網(wǎng)址之后，打開網(wǎng)頁的過程其實(shí)是瀏覽器作為客戶端，向服務(wù)器發(fā)送一個(gè)請(qǐng)求。經(jīng)過DNS服務(wù)器，找到服務(wù)器主機(jī)，經(jīng)服務(wù)器解析，將請(qǐng)求的資源返回給瀏覽器，瀏覽器最終將這些內(nèi)容經(jīng)過解析處理之后在頁面上呈現(xiàn)給用戶。目前，通過網(wǎng)絡(luò)爬蟲采集微博數(shù)據(jù)的技術(shù)應(yīng)用較為廣泛。主要通過采集用戶的帶有位置信息的微博，從中提取POI簽到信息，統(tǒng)計(jì)各個(gè)POI的累計(jì)簽到次數(shù)作為該P(yáng)OI總的簽到次數(shù)，從而得到微博POI簽到數(shù)據(jù)。文獻(xiàn)[11]提出了基于模擬登陸的網(wǎng)絡(luò)爬蟲采集方案，解決了傳統(tǒng)網(wǎng)絡(luò)爬蟲需要身份驗(yàn)證的問題。文獻(xiàn)[12]開發(fā)了一款支持并行微博數(shù)據(jù)獲取的應(yīng)用，提供了一種基于廣度優(yōu)先搜索的算法來獲取微博數(shù)據(jù)。文獻(xiàn)[13]利用隊(duì)列的思想實(shí)現(xiàn)了非遞歸爬蟲，實(shí)現(xiàn)了大規(guī)模數(shù)據(jù)的快速高效獲取。隨著新浪微博的不斷升級(jí)，反爬蟲機(jī)制更加嚴(yán)格，該方法不僅受到的限制多，而且數(shù)據(jù)采集的范圍有限、程序設(shè)計(jì)更加復(fù)雜、數(shù)據(jù)采集周期更長、數(shù)據(jù)處理難度大。

1.2 調(diào)用微博開放平臺(tái)API的數(shù)據(jù)獲取

開放平臺(tái)（Open Platform）是指軟件系統(tǒng)向第三方開發(fā)者提供應(yīng)用程序編程接口（Application Programming Interface, API）或函數(shù)，使得開發(fā)者能夠調(diào)用該系統(tǒng)的資源以實(shí)現(xiàn)滿足自己需求的程序或增加該系統(tǒng)的功能，而不需要更改系統(tǒng)的源代碼。2010年新浪推出了新浪微博開放平臺(tái)，通過接入第三方合作伙伴的方式，向用戶提供更加豐富的應(yīng)用和完善的服務(wù)[14]。文獻(xiàn)[15]通過調(diào)用API實(shí)現(xiàn)了某景區(qū)一年的微博數(shù)據(jù)采集。文獻(xiàn)[16]以固定大小的格網(wǎng)調(diào)用微博API進(jìn)行簽到數(shù)據(jù)的獲取。利用該方法采集POI數(shù)據(jù)會(huì)造成高密度區(qū)域的數(shù)據(jù)目標(biāo)丟失，很難保證數(shù)據(jù)采集的完整性。文獻(xiàn)[17]在數(shù)據(jù)采集過程中對(duì)高密度的數(shù)據(jù)區(qū)域采用更加精細(xì)的格網(wǎng)進(jìn)行數(shù)據(jù)獲取。此方法設(shè)計(jì)缺乏靈活性，難以滿足大范圍內(nèi)的數(shù)據(jù)獲取需求。

1.3 綜合數(shù)據(jù)獲取策略

由于新浪微博開放平臺(tái)API對(duì)開發(fā)者訪問次數(shù)的限制，大多數(shù)學(xué)者采用將網(wǎng)絡(luò)爬蟲與微博API相結(jié)合的策略采集微博數(shù)據(jù)[18-19]。通過這種綜合策略的方式可以最大效率的采集微博數(shù)據(jù)，完成新浪微博API中由于權(quán)限等問題無法獲取的數(shù)據(jù)。由于網(wǎng)絡(luò)爬蟲采集的微博POI信息與通過API方式采集的信息存在一定的差異，一般調(diào)用API方式返回的信息比網(wǎng)絡(luò)爬蟲方式豐富。因此，很難將兩種方式采集的微博POI數(shù)據(jù)融合到一起。

從已有的研究可以看出，大多數(shù)采集方案并沒有對(duì)研究區(qū)域進(jìn)行處理，容易造成高密度數(shù)據(jù)區(qū)域目標(biāo)丟失的問題。而隨著新浪微博的不斷升級(jí)，通過網(wǎng)絡(luò)爬蟲方式采集數(shù)據(jù)受到的限制逐漸增多，難以滿足大范圍內(nèi)的海量POI數(shù)據(jù)采集。因此，本文提出一種四叉樹動(dòng)態(tài)格網(wǎng)的數(shù)據(jù)采集方法。能夠避免由于API限制導(dǎo)致數(shù)據(jù)目標(biāo)丟失的問題，最大程度地保證數(shù)據(jù)采集的完整性。

2 四叉樹動(dòng)態(tài)格網(wǎng)的數(shù)據(jù)獲取

本文在分析了傳統(tǒng)規(guī)則格網(wǎng)的數(shù)據(jù)獲取方式所存在缺陷的基礎(chǔ)上，采用了四叉樹思想動(dòng)態(tài)劃分格網(wǎng)來獲取數(shù)據(jù)，能夠最大程度地保證數(shù)據(jù)采集的完整性，并兼顧了不同數(shù)據(jù)密度區(qū)域下的采集效率，適用于大范圍內(nèi)的微博POI簽到數(shù)據(jù)采集。

今《全宋文》收有陳景沂文兩篇，一是《全芳備祖序》，另一是《招隱寺玉蕊花記》，出《全芳備祖》前集卷六，見《全宋文》卷七九三○、第343冊(cè)第292-293頁，題目均為編者所加。由于所據(jù)版本的缺陷，兩文與我們校點(diǎn)整理所得都有個(gè)別字詞出入，此依其題，全文羅列如下。

2.1 基礎(chǔ)格網(wǎng)劃分

1）API參數(shù)說明

本文主要使用獲取附近的地點(diǎn)等接口來采集微博POI數(shù)據(jù)，通過輸入相應(yīng)的參數(shù)，如經(jīng)緯度、半徑、返回的頁數(shù)、每頁記錄數(shù)等，就可以獲取到附近位置的微博POI簽到數(shù)據(jù)。接口請(qǐng)求參數(shù)見表1。

表1 API請(qǐng)求參數(shù)說明Tab.1 The acquisition parameters of microblog API

由于新浪微博開放平臺(tái)API提供的參數(shù)是某一半徑的搜索圓，所以想要獲取一定范圍內(nèi)的POI數(shù)據(jù)，需要根據(jù)半徑參數(shù)對(duì)研究區(qū)域進(jìn)行格網(wǎng)化處理，并保留合適的重疊范圍，從而保證數(shù)據(jù)采集的完整性。

2）格網(wǎng)間距計(jì)算

合理的格網(wǎng)間距既要能夠保證采集范圍的有效重疊，又不能使得采集范圍重疊過多導(dǎo)致大量的重復(fù)采集。如圖1所示，采用搜索圓的內(nèi)接矩形作為基本的格網(wǎng)單元，假定搜索圓的半徑為r，那么格網(wǎng)邊長為2r，格網(wǎng)點(diǎn)間距應(yīng)小于等于2r，這樣才能實(shí)現(xiàn)格網(wǎng)單元的有效重疊，避免某些區(qū)域數(shù)據(jù)目標(biāo)的缺失。本文采用的搜索圓半徑為2km、格網(wǎng)間距采用2.8 km。

圖1 格網(wǎng)劃分示意圖Fig.1 The display of grid partition

3）格網(wǎng)點(diǎn)生成

首先利用ArcGIS的漁網(wǎng)工具對(duì)目標(biāo)區(qū)域進(jìn)行格網(wǎng)化處理，得到格網(wǎng)中心點(diǎn)坐標(biāo)，以格網(wǎng)中心點(diǎn)作為數(shù)據(jù)坐標(biāo)采集中心點(diǎn)來調(diào)用API獲取全國范圍內(nèi)的POI數(shù)據(jù)。

2.2 數(shù)據(jù)采集

1）規(guī)則格網(wǎng)的數(shù)據(jù)獲取

規(guī)則格網(wǎng)的數(shù)據(jù)獲取首先通過讀取坐標(biāo)采集中心點(diǎn)經(jīng)緯度，調(diào)用新浪微博開放平臺(tái)相應(yīng)的API，結(jié)合網(wǎng)頁解析技術(shù)，從返回的數(shù)據(jù)中提取有價(jià)值的字段信息存儲(chǔ)到數(shù)據(jù)庫中，直到遍歷完所有的坐標(biāo)采集中心點(diǎn)為止。技術(shù)流程如圖2所示。

圖2 規(guī)則格網(wǎng)數(shù)據(jù)獲取流程圖Fig.2 The fl ow chart of data fetching based on regular grid

2）動(dòng)態(tài)格網(wǎng)的數(shù)據(jù)獲取

動(dòng)態(tài)格網(wǎng)的數(shù)據(jù)獲取首先采用類似規(guī)則格網(wǎng)的方式去調(diào)用API，檢查當(dāng)前格網(wǎng)內(nèi)返回的POI總數(shù)，如果超過一定的閾值（200），則采用四叉樹分裂法對(duì)該格網(wǎng)進(jìn)行動(dòng)態(tài)分割，分成4個(gè)小的格網(wǎng)遞歸獲取數(shù)據(jù)。直到返回的數(shù)據(jù)小于設(shè)定的閾值時(shí)，表明當(dāng)前格網(wǎng)內(nèi)的POI數(shù)據(jù)采集完畢，否則繼續(xù)動(dòng)態(tài)分割格網(wǎng)。四叉樹動(dòng)態(tài)格網(wǎng)劃分示意圖如圖3所示。

圖3 四叉樹動(dòng)態(tài)格網(wǎng)劃分示意圖Fig.3 The display of quadtree dynamic grid partition

四叉樹動(dòng)態(tài)格網(wǎng)的數(shù)據(jù)獲取技術(shù)流程如圖4所示。

圖4 四叉樹動(dòng)態(tài)格網(wǎng)的數(shù)據(jù)獲取技術(shù)流程圖Fig.4 Technical workf l ow of data fetching based dynamic quadtree grid

3 數(shù)據(jù)獲取結(jié)果分析

為了最大程度保證數(shù)據(jù)獲取的完整性，數(shù)據(jù)采集格網(wǎng)存在一定的重疊，因此，在數(shù)據(jù)采集完成之后需要對(duì)其進(jìn)行分析并去掉冗余數(shù)據(jù)。調(diào)用API返回的數(shù)據(jù)格式為json格式，數(shù)據(jù)存儲(chǔ)在MongoDB中，MongoDB是一種面向文檔的，采用BSON的格式存儲(chǔ)的數(shù)據(jù)庫，可以對(duì)比較復(fù)雜的數(shù)據(jù)類型進(jìn)行存儲(chǔ)，對(duì)文檔索引提供了十分廣泛的支持，能夠很好地解決這種大量的非結(jié)構(gòu)化的微博POI數(shù)據(jù)的存儲(chǔ)問題。

通過規(guī)則格網(wǎng)方式最終得到有效數(shù)據(jù)415 655條，而利用四叉樹動(dòng)態(tài)格網(wǎng)方式得到有效數(shù)據(jù)為1963 851條。兩種數(shù)據(jù)獲取方案的對(duì)比見表2。

表2 數(shù)據(jù)獲取結(jié)果的對(duì)比Tab.2 The results of data acquisition

以北京市微博POI數(shù)據(jù)為例，按照一定經(jīng)緯度或距離劃分格網(wǎng)，統(tǒng)計(jì)單位格網(wǎng)內(nèi)的POI總數(shù)，對(duì)比兩種方式獲取的數(shù)據(jù)結(jié)果的分布。規(guī)則格網(wǎng)的數(shù)據(jù)獲取結(jié)果分布如圖5所示，四叉樹格網(wǎng)的數(shù)據(jù)獲取結(jié)果如圖6所示，規(guī)則格網(wǎng)相比于四叉樹格網(wǎng)所缺失數(shù)據(jù)的分布如圖7所示。

圖5 規(guī)則格網(wǎng)的數(shù)據(jù)獲取結(jié)果分布圖Fig.5 The distribution of data acquisition based on regular grid

圖6 四叉樹數(shù)據(jù)獲取結(jié)果分布圖Fig.6 The distribution of data acquisition based on quadtree grid

圖7 規(guī)則格網(wǎng)相較于四叉樹格網(wǎng)缺失數(shù)據(jù)分布Fig.7 The distribution of missing data compared with regular grid to quadtree grid

從以上數(shù)據(jù)獲取結(jié)果的分布可以看出，規(guī)則格網(wǎng)相較于四叉樹格網(wǎng)所缺失的數(shù)據(jù)主要分布在內(nèi)城區(qū)等POI比較密集的區(qū)域，如西城區(qū)、東城區(qū)、朝陽區(qū)、海定區(qū)、石景山區(qū)、豐臺(tái)區(qū)等。其他像昌平區(qū)、順義區(qū)、通州區(qū)等城中心區(qū)域缺失的也比較多。POI越密集區(qū)域，規(guī)則格網(wǎng)所造成的數(shù)據(jù)缺失越多。城郊地區(qū)本身POI相對(duì)較少，所以缺失的數(shù)據(jù)也相對(duì)較少。

下面以2 km、6 km、10 km半徑去檢索北京故宮博物院附近的POI數(shù)據(jù)，數(shù)據(jù)獲取結(jié)果見表3。

表3 不同半徑的檢索結(jié)果對(duì)比Tab.3 The results of data acquisition based on diあerent radius

由此可以發(fā)現(xiàn)，在調(diào)用新浪微博API時(shí)，返回?cái)?shù)據(jù)的最大值為200，所以通過規(guī)則格網(wǎng)的數(shù)據(jù)獲取方式在高密度數(shù)據(jù)區(qū)域容易造成數(shù)據(jù)目標(biāo)丟失的問題，難以保證數(shù)據(jù)采集的完整性。

通過前面的實(shí)驗(yàn)結(jié)果對(duì)比，四叉樹動(dòng)態(tài)格網(wǎng)的獲取方式在獲取數(shù)據(jù)的完整性上具有明顯的優(yōu)勢，能夠很好地適應(yīng)大范圍內(nèi)的微博POI采集。另外，通過規(guī)則格網(wǎng)的方式獲得同等規(guī)模的數(shù)據(jù)就需要將格網(wǎng)劃分的足夠小，此時(shí)就會(huì)導(dǎo)致在低密度數(shù)據(jù)區(qū)域的采集效率大大降低。而四叉樹動(dòng)態(tài)格網(wǎng)方式只會(huì)在高密度數(shù)據(jù)區(qū)域進(jìn)行動(dòng)態(tài)分割為更加細(xì)小的格網(wǎng)，因此，四叉樹動(dòng)態(tài)格網(wǎng)方式能夠兼顧不同密度區(qū)域下的數(shù)據(jù)采集效率。為了規(guī)范API的使用，防止服務(wù)器資源被濫用，新浪微博API對(duì)返回的數(shù)據(jù)量有一定的限制，所以四叉樹動(dòng)態(tài)格網(wǎng)的獲取方式能夠最大程度地保證數(shù)據(jù)獲取的完整性。事實(shí)上，目前主流的開放平臺(tái)API都采取類似的措施從而防止API資源的濫用，如百度地圖API、高德地圖API等。

4 結(jié)束語

本文按照一定的經(jīng)緯度將研究區(qū)域進(jìn)行格網(wǎng)化處理，通過調(diào)用新浪微博開放平臺(tái)API獲取微博POI數(shù)據(jù)，由于該平臺(tái)的限制，在POI數(shù)據(jù)密集區(qū)域采用四叉樹動(dòng)態(tài)格網(wǎng)獲取數(shù)據(jù)，從而保證數(shù)據(jù)采集的完整性，能夠適應(yīng)大范圍內(nèi)的海量微博POI簽到數(shù)據(jù)采集。與通過網(wǎng)絡(luò)爬蟲的方式相比，本方案具有程序設(shè)計(jì)簡單、限制少、數(shù)據(jù)處理簡單、數(shù)據(jù)質(zhì)量高等特點(diǎn)，相同數(shù)據(jù)量下的采集周期更短。與傳統(tǒng)的采用規(guī)則格網(wǎng)的方式相比，該方案很好地解決了高密度數(shù)據(jù)區(qū)域數(shù)據(jù)目標(biāo)容易丟失的問題，能夠最大程度地保證數(shù)據(jù)采集的完整性。利用四叉樹思想動(dòng)態(tài)劃分格網(wǎng)的方法同樣適用于其他開放平臺(tái)的數(shù)據(jù)采集，如百度地圖API、高德地圖API等。