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

◆甘勇 王一帆 賈東偉

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

◆甘勇 王一帆 賈東偉

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

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

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

1 緒論

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

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

2 基于聚類的IP定位算法

2.1 本文方法總體介紹

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

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

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

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

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

3 實驗結(jié)果

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

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

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

圖2 評價結(jié)果

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

表2 實驗結(jié)果

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

4 結(jié)論

本文給出了一種基于特征聚類的IP定位算法，在基于學(xué)習(xí)的IP定位算法的基礎(chǔ)上，根據(jù)特征聚類的思想，引入支持向量機(jī)算法建立分類模型。最后，引入地址匹配模型作為后續(xù)處理手段從而提高了IP定位結(jié)果的準(zhǔ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.