常見(jiàn)網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘算法綜述

朱光

中原工學(xué)院計(jì)算機(jī)學(xué)院 河南 鄭州 450007

社交網(wǎng)絡(luò)存在著龐大的用戶行為數(shù)據(jù)，通過(guò)對(duì)這些網(wǎng)絡(luò)數(shù)據(jù)的收集、處理和分析，可獲取數(shù)據(jù)中的重要信息，這些數(shù)據(jù)具有重要的研究?jī)r(jià)值。網(wǎng)絡(luò)實(shí)體定位就是大量利用網(wǎng)絡(luò)數(shù)據(jù)作為參考地標(biāo)來(lái)獲取IP地址對(duì)應(yīng)地理位置的技術(shù)[1]，其是應(yīng)用廣泛的LBS的基礎(chǔ)。現(xiàn)有的高精度IP定位技術(shù)如GeoPing[2]、Constraint-Based Geolocation[3]、Octant[4]、Topology-Based Geolocation[5]等方法，這些方法的定位精度通常依賴于網(wǎng)絡(luò)地標(biāo)[6]的密度和可靠性[7-8]。因此，網(wǎng)絡(luò)實(shí)體地標(biāo)是基于地標(biāo)的IP定位技術(shù)的基礎(chǔ)，只有獲取足夠多的高可靠性地標(biāo)，才能實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)目標(biāo)實(shí)體的高精度定位。

現(xiàn)有的網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘與篩選方法主要有：基于Web的地標(biāo)挖掘方法[6，9]、基于Internet論壇的地標(biāo)挖掘方法[10]、基于路由跳數(shù)的地標(biāo)篩選方法[11]以及其他地標(biāo)獲取方法。本文將對(duì)上述大批量地標(biāo)獲取與篩選方法的基本原理、特點(diǎn)以及局限性進(jìn)行比較與分析。

1 基于Web的地標(biāo)挖掘方法

基于Web的地標(biāo)挖掘方法主要是通過(guò)對(duì)Web 的HTML信息提取、匹配，獲取該Web域名的IP地址及其對(duì)應(yīng)的地理位置[6]，現(xiàn)有典型的方法有Structon[6]方法和基于Web網(wǎng)頁(yè)和在線地圖相結(jié)合的地標(biāo)挖掘方法[10]。

基于Web的地標(biāo)挖掘方法基本原理如下：Web的HTML頁(yè)面的尾部或內(nèi)容部分中常常包含著該Web網(wǎng)站所屬公司注冊(cè)地、駐地的地理位置信息，通過(guò)提取、匹配，可將這些地理位置信息映射到Web服務(wù)器的IP地址。即從Web的HTML中提取的地理信息，并將該Web網(wǎng)站的域名解析為IP地址，實(shí)現(xiàn)IP地址與地理位置的映射關(guān)系。Guo等人提出的Structon[6]方法是較早且可大批量挖掘網(wǎng)絡(luò)地標(biāo)的一種網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘方法。

Wang等人提出了另一種基于Web網(wǎng)頁(yè)和在線地圖相結(jié)合的地標(biāo)挖掘方法[10]。同Structon方法，許多公司、政府部門(mén)都運(yùn)行著對(duì)外開(kāi)放的Web網(wǎng)站，通過(guò)將這些Web網(wǎng)站所屬的Web服務(wù)器與在線地圖查詢結(jié)合，實(shí)現(xiàn)Web服務(wù)器與地理位置的映射。該方法的基本原理如下：首先，在對(duì)外公開(kāi)提供服務(wù)的在線地圖服務(wù)（如Google地圖）輸入“公司”或“政府”等關(guān)鍵字與想要查詢區(qū)域的Zip Code后，地圖服務(wù)器將會(huì)檢索出一系列與關(guān)鍵字相關(guān)網(wǎng)站的域名以及郵政編碼，獲取網(wǎng)站IP與其所有可能的地理位置的映射關(guān)系。但是，通過(guò)在線地圖篩選出的IP地址及所有的可能的其地理位置可能出現(xiàn)信息不一致或信息映射有誤等問(wèn)題。接著，該方法逐個(gè)驗(yàn)證上一步獲取的所有網(wǎng)絡(luò)實(shí)體地標(biāo)。

文章[10]對(duì)存在此類(lèi)問(wèn)題的地標(biāo)通過(guò)多種方法進(jìn)行驗(yàn)證與篩選，但往往只能排除部分存在此類(lèi)問(wèn)題的地標(biāo)，效果并不理想。基于Web的地標(biāo)挖掘方法雖可獲取大量網(wǎng)絡(luò)地標(biāo)，但在可靠度方面仍有一定的提高空間，通過(guò)基于Web的地標(biāo)挖掘方法獲取的地標(biāo)，需進(jìn)一步驗(yàn)證與篩選，以提高網(wǎng)絡(luò)地標(biāo)的可靠性。

2 基于lnternet論壇的網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘方法

因Web服務(wù)器存在共享主機(jī)、虛擬專(zhuān)用服務(wù)器、CDN網(wǎng)絡(luò)等情況，基于Web的地標(biāo)挖掘方法在原理上受到局限，為彌補(bǔ)上述不足，文章[11]提出了基于Internet論壇的網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘方法。

基于Internet論壇的網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘方法包括3個(gè)部分：論壇選擇策略、獲選地標(biāo)獲取、候選地標(biāo)評(píng)估。

與基于Web的地標(biāo)挖掘方法相比，該方法可獲取的網(wǎng)絡(luò)地標(biāo)數(shù)量多：基于Web的地標(biāo)挖掘方法挖掘?qū)ο鬄閃eb服務(wù)器IP地址，這類(lèi)IP地址僅僅占全球IP地址的較少部分，而該方法將挖掘?qū)ο笾赶蛄藗€(gè)人用戶IP，因此，在網(wǎng)絡(luò)地標(biāo)挖掘數(shù)量上顯著提高；獲取地標(biāo)的范圍廣：Web服務(wù)器通常位于經(jīng)濟(jì)較為發(fā)達(dá)城市，對(duì)于沒(méi)有Web服務(wù)器的地方（如鄉(xiāng)村等地），基于Web的地標(biāo)挖掘方法將會(huì)受到限制，而該方法彌補(bǔ)了基于Web網(wǎng)頁(yè)的地標(biāo)挖掘方法在挖掘范圍方面的不足；獲取地標(biāo)的可靠性高：基于Web的地標(biāo)挖掘方法可能受到共享主機(jī)、VPS、CDN等情況的影響，導(dǎo)致地標(biāo)的可靠性較低，而個(gè)人用戶IP通常不存在上述情況，因此，該方法獲取的地標(biāo)可靠性更高。然而，該方法也存在一定的局限性，為緩解IP地址緊張問(wèn)題，網(wǎng)絡(luò)運(yùn)營(yíng)商通常在一個(gè)城市內(nèi)建立一個(gè)或多個(gè)動(dòng)態(tài)IP地址池，用來(lái)動(dòng)態(tài)分配IP地址給用戶。因此，該方法獲取的網(wǎng)絡(luò)地標(biāo)通常為城市級(jí)粒度。基于Web的地標(biāo)挖掘方法可獲得城市級(jí)甚至是街道級(jí)粒度。

3 基于路由跳數(shù)的網(wǎng)絡(luò)地標(biāo)篩選方法

為驗(yàn)證與評(píng)估網(wǎng)絡(luò)地標(biāo)的可靠性，文章[11]提出了基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選方法，包括訓(xùn)練部分和篩選部分。

4 幾種網(wǎng)絡(luò)地標(biāo)挖掘與篩選方法比較

實(shí)驗(yàn)選取位于北京、深圳、杭州三地VPS，分別根據(jù)基于Web網(wǎng)頁(yè)和在線地圖相結(jié)合的地標(biāo)挖掘方法（方法一）獲取北京、深圳、杭州地標(biāo)數(shù)量分別為546條、637條、403條。實(shí)驗(yàn)選取互聯(lián)網(wǎng)論壇 “北京吧” “杭州吧” “深圳吧”等9個(gè)百度貼吧，根據(jù)基于Internet論壇的網(wǎng)絡(luò)實(shí)體地標(biāo)挖掘方法（方法二）獲取有效IP地址，并通過(guò)E-GeoTrack算法驗(yàn)證后，獲取北京、深圳、杭州三地地標(biāo)數(shù)量分別為3225條、5781條、5144條。兩種方法獲取數(shù)量比較如下表所示：

基于SLG算法，對(duì)100個(gè)已知地理位置的目標(biāo)IP進(jìn)行城市級(jí)定位結(jié)果如表2所示：

表2 定位結(jié)果比較

對(duì)兩種地標(biāo)集進(jìn)行誤差比較，地標(biāo)集定位誤差的累積概率分布如圖1所示：

圖1 兩類(lèi)地標(biāo)集誤差比較

對(duì)上述定位結(jié)果數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，基于論壇獲取的地標(biāo)對(duì)定位平均誤差為14.8km，基于Web方式獲取的地標(biāo)對(duì)定位的平均誤差為42.5km。可知，采用相同的定位算法，基于論壇獲取的地標(biāo)的可靠性更高，即基于論壇獲取的地標(biāo)可提高基于地標(biāo)的定位算法的精度。

將上述兩種方法獲取的地標(biāo)作為候選地標(biāo)，并通過(guò)基于路由跳數(shù)的網(wǎng)絡(luò)地標(biāo)篩選方法進(jìn)行篩選。

同樣基于SLG算法，對(duì)篩選后地標(biāo)對(duì)100個(gè)已知地理位置的目標(biāo)IP進(jìn)行城市級(jí)定位。兩者的定位誤差的累積概率分布如圖2所示：

圖2 篩選后的兩類(lèi)地標(biāo)集誤差比較

對(duì)上述定位結(jié)果數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，基于論壇獲取的地標(biāo)對(duì)定位平均誤差為8.9km，基于Web方式獲取的地標(biāo)對(duì)定位的平均誤差為21.1km。可知， 通過(guò)定位結(jié)果可知，基于路由跳數(shù)的網(wǎng)絡(luò)地標(biāo)篩選方法可有效提高地標(biāo)的可靠性，進(jìn)而提高基于地標(biāo)的定位算法的精度。

5 結(jié)束語(yǔ)

基于Web的地標(biāo)挖掘方法、基于Internet論壇的地標(biāo)挖掘方法是目前較為常用的大批量地標(biāo)獲取方法，基于路由跳數(shù)的地標(biāo)篩選方法可作為地標(biāo)的驗(yàn)證與評(píng)估方法，進(jìn)一步提高網(wǎng)絡(luò)地標(biāo)的可信度。本文對(duì)上述方法的基本原理、特點(diǎn)以及局限性進(jìn)行比較與分析，并對(duì)100個(gè)目標(biāo)IP進(jìn)行實(shí)測(cè)的結(jié)果進(jìn)行誤差比較與分析。