◆甘勇 王一帆 賈東偉

一種基于聚類的IP定位算法

◆甘勇 王一帆 賈東偉

（鄭州輕工業(yè)大學(xué) 河南 450000）

網(wǎng)絡(luò) IP 的地理位置是基于位置的服務(wù)的重要基礎(chǔ)。然而，現(xiàn)有的基于數(shù)據(jù)庫(kù)查詢、網(wǎng)絡(luò)測(cè)量和機(jī)器學(xué)習(xí)的IP定位方法往往難以滿足實(shí)時(shí)性和可靠性的要求，無(wú)法滿足實(shí)際需要。針對(duì)這一問(wèn)題，本文提出了一種基于聚類的IP定位方法。通過(guò)訓(xùn)練分類器實(shí)現(xiàn)了IP地址的初始定位。結(jié)合IP地址數(shù)據(jù)庫(kù)匹配方法，最終實(shí)現(xiàn)IP地址的準(zhǔn)確定位。實(shí)驗(yàn)結(jié)果表明了該方法的有效性。

IP定位；聚類；支持向量機(jī)

1 緒論

IP定位技術(shù)具有重要的應(yīng)用和研究?jī)r(jià)值，其目的是在宏觀世界中確定網(wǎng)絡(luò)實(shí)體地理位置[1]。定位結(jié)果通常包括國(guó)家名稱、地區(qū)名稱、經(jīng)緯度、時(shí)區(qū)等[2]。在一些社交軟件中，IP地址也可以用來(lái)推薦朋友的位置。利用市級(jí)定位，根據(jù)用戶IP確定用戶位置，推送其網(wǎng)絡(luò)廣播平臺(tái)的視頻內(nèi)容[3-4]。

本文提出了一種基于聚類的IP定位算法?；趯W(xué)習(xí)的IP定位算法，檢測(cè)目標(biāo)IP地址的多維特征。根據(jù)特征聚類的思想，引入支持向量機(jī)算法建立分類模型，提高目標(biāo)IP地理位置的預(yù)測(cè)精度。

2 基于聚類的IP定位算法

2.1 本文方法總體介紹

針對(duì)網(wǎng)絡(luò)測(cè)量模式下IP定位算法效率低的問(wèn)題，為了充分利用歷史測(cè)量數(shù)據(jù)，提出了一種基于特征聚類的IP定位算法。最后，基于多維支持向量機(jī)的思想，進(jìn)一步提高了目標(biāo)的定位精度。算法的具體工作流程如下圖所示。對(duì)于待定位IP，將其輸入分類器得到IP城市級(jí)地址后，利用城市內(nèi)街道IP地址劃分?jǐn)?shù)據(jù)庫(kù)進(jìn)行匹配，從而實(shí)現(xiàn)街道級(jí)IP定位。

圖1 基于支持向量機(jī)的IP定位算法運(yùn)行框架

2.2 本文分類模型具體實(shí)現(xiàn)

對(duì)于非線性分類問(wèn)題，支持向量機(jī)分類模型可表示為

其中，高斯核可寫作如下形式：

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)選取了1022個(gè)城市有效地址。選取北京和上海作為檢測(cè)源，對(duì)標(biāo)志點(diǎn)進(jìn)行檢測(cè)，獲取時(shí)延和跳數(shù)信息。測(cè)量過(guò)程受網(wǎng)絡(luò)狀態(tài)的影響，容易產(chǎn)生大量的誤差。與此同時(shí)，部分采集數(shù)據(jù)的屬性存在不完整的因素，導(dǎo)致這些數(shù)據(jù)在傳統(tǒng)的機(jī)器學(xué)習(xí)模型中應(yīng)用效果下降。因此，需要對(duì)原始數(shù)據(jù)缺失的屬性取同一類數(shù)據(jù)中的平均數(shù)或多個(gè)數(shù)字進(jìn)行屬性填充。在這個(gè)實(shí)驗(yàn)中，平均時(shí)間延遲的離群值，跳數(shù)是眾包的。表1包含三個(gè)地標(biāo)A、B和C的檢測(cè)數(shù)據(jù)。B點(diǎn)上海源數(shù)據(jù)缺失，需要從完整的A、C點(diǎn)數(shù)據(jù)中選擇一個(gè)更合適的數(shù)據(jù)進(jìn)行數(shù)據(jù)填充。此時(shí)，只能使用北京源數(shù)據(jù)。利用聚類算法，可以得出C點(diǎn)的北京檢測(cè)數(shù)據(jù)更接近B點(diǎn)的結(jié)論，因此C點(diǎn)和B點(diǎn)聚類到同一類的可能性更大，C點(diǎn)的上海檢測(cè)源數(shù)據(jù)可以直接填充到B點(diǎn)。

表1 三個(gè)地標(biāo)A、B和C的檢測(cè)數(shù)據(jù)

為了評(píng)估探測(cè)源數(shù)量對(duì)于定位性能的影響，本文在上述兩個(gè)探測(cè)源基礎(chǔ)上，分別比較了單獨(dú)使用兩個(gè)探測(cè)源中其中一個(gè)進(jìn)行分類器訓(xùn)練，并對(duì)準(zhǔn)確率進(jìn)行評(píng)價(jià)。評(píng)價(jià)結(jié)果見(jiàn)圖2。從圖中結(jié)果可以看出，不論對(duì)于哪一種探測(cè)源，支持向量機(jī)均能取得優(yōu)于其他分類器的性能。同時(shí)，結(jié)合了兩個(gè)探測(cè)源的IP數(shù)據(jù)特征訓(xùn)練的分類器比單獨(dú)任何一個(gè)數(shù)據(jù)源性能更優(yōu)。因此在后續(xù)對(duì)比實(shí)驗(yàn)中將采用兩個(gè)數(shù)據(jù)源進(jìn)行性能比較。

圖2 評(píng)價(jià)結(jié)果

將處理后的數(shù)據(jù)以7：3的比例劃分為訓(xùn)練集和測(cè)試集。利用訓(xùn)練集分別構(gòu)建了樸素貝葉斯、決策樹(shù)和支持向量機(jī)三種學(xué)習(xí)算法的分類器。通過(guò)測(cè)試集對(duì)分類精度進(jìn)行了比較。實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 實(shí)驗(yàn)結(jié)果

從表中可以看出，在基于特征相似度的IP定位算法中，基于支持向量機(jī)算法的機(jī)器學(xué)習(xí)算法具有較高的定位精度。樸素貝葉斯算法的性能最差。這種結(jié)果與國(guó)內(nèi)網(wǎng)絡(luò)的層次結(jié)構(gòu)密切相關(guān)。

4 結(jié)論

本文給出了一種基于特征聚類的IP定位算法，在基于學(xué)習(xí)的IP定位算法的基礎(chǔ)上，根據(jù)特征聚類的思想，引入支持向量機(jī)算法建立分類模型。最后，引入地址匹配模型作為后續(xù)處理手段從而提高了IP定位結(jié)果的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明了該方法的有效性。

[1]V. N. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for internet hosts[C]， Proceedings of the ACM SIGCOMM Conference on Applications， Technologies，Architectures，and Protocols for Computer Communications，2001：173-185.

[2]Taylor J，Devlin J，Curran K. Bringing location to IP addresses with IP Geolocation[J]，Journal of Emerging Technologies in Web Intelligence，2012，4（3）：273-277.

[3]Li D，Chen J，Guo C，et al. IP-geolocation mapping for moderately connected Internet regions[J]，IEEE Transactions on Parallel and Distributed Systems，2013，24（2）：381-391.

[4]Gill P，Ganjali Y，Wong B，et al. Dude，where’s that IP?：circumventing measurement-based IP geolocation[C]， Proceedings of the 19th USENIX conference on Security，2010：16-22.