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

◆甘勇 王一帆 賈東偉

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

◆甘勇 王一帆 賈東偉

（鄭州輕工業大學 河南 450000）

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

IP定位；聚類；支持向量機

1 緒論

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

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

2 基于聚類的IP定位算法

2.1 本文方法總體介紹

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

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

2.2 本文分類模型具體實現

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

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

3 實驗結果

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

表1 三個地標A、B和C的檢測數據

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

圖2 評價結果

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

表2 實驗結果

從表中可以看出，在基于特征相似度的IP定位算法中，基于支持向量機算法的機器學習算法具有較高的定位精度。樸素貝葉斯算法的性能最差。這種結果與國內網絡的層次結構密切相關。

4 結論

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

[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.