一种基于聚类的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.