基于特征选择改进的随机森林IP定位方法

张鹤林，甘 勇,2，刘渊博

（1.郑州轻工业大学计算机与通信工程学院，郑州 450001；2.郑州工程技术学院，郑州 450001）

0 引言

随着互联网的飞速发展，网络应用、网络数据和网络实体等逐步构成了网络空间，网络空间与海陆天空等地理空间不同，是一个动态空间，数据交互极快。但是从网络空间安全的角度出发，还是很有必要对网络空间进行测绘。网络实体定位技术如同地理空间测绘中的水文测量技术一样，能够实现网络实体资源到地理空间的映射，是网络空间测绘的基础，由于网络实体通常可以通过网络实体的IP 地址来进行唯一标识，从而确定该网络实体在一定粒度上的地理空间位置，因此又可以称为IP 定位技术。

目前主流的IP 定位技术有三类：基于数据库查询的方法、基于网络测量的方法和基于机器学习的方法。基于数据库查询的方法方便快捷，但是定位结果完全取决于数据库，可能会有很大的误差。基于网络测量的方法是较传统且有效的方法，主要通过网络测量获取网络实体之间的网络空间信息，比如最常用的时延和跳数两种信息，将其通过一些参数近似转换为物理空间的距离，从而推断出目标IP 的地理位置。基于机器学习的方法其核心思想是将IP 定位转换为分类或者聚类问题，以IP 地址、时延和跳数等信息作为特征来训练模型，从而得出目标IP的地理位置。

本文结合了网络测量的数据和IP 地址本身共同形成多特征的数据集，使用随机森林这一机器学习分类模型，并根据网络IP 地址数据不平衡和各特征重要性不一致会影响网络IP 定位结果的特点，对特征权重算法Relief F 做出改进，融入随机森林分类算法的特征选择步骤中，提出一种基于特征选择改进的随机森林城市级IP定位方法。

1 特征选择算法改进

1.1 Relief F算法改进

Relief 算法是一种比较常见且高效的特征权重算法，其核心思想是根据数据中每个特征对于分类的相关度不同，计算给出不同的权重，再根据不同的要求设定阈值，丢弃不符合阈值要求的特征。假设训练集为，一般是随机选取出一个样本，首先需要找到样本同类型且最近邻的样本，然后再找到样本不同类型同样最近邻的样本。对于数据中任一个特征来说，如果与的距离小于与的距离，就认为特征是有利于提高分类准确率的，该特征的权重就会适当加大，反之则减小权重。一般来说，都会多次计算取各特征权重平均值，假设计算次，各特征的计算方式如式（1）所示。

由于Relief只能处理二分类问题，改进算法Relief F 算法在Relief 算法基础上增加了多分类问题的解决策略，其核心思想是：把抽取样本和样本这一过程，重新设置为从每类样本分别找到个最近邻的样本。此方法不仅能提高算法稳定性，同时也减轻了噪声对结果的干扰，权重计算方式如式（2）所示。

（）是原数据集中类别为的样本所占比例，M（）表示类∉class（）中第个最近邻样本，diff（,,）表示对于特征来说，样本和的差。

Relief F算法的改进仅仅是针对分类问题的，算法在抽取不同类别样本时采用的是随机抽取相同数量的样本的方式，一般情况下能达到很好的稳定性和抗噪声干扰能力，但是要想解决不平衡数据引起的问题，这并不是最佳的方式。

因此，本文对以上Relief F 算法的抽样步骤做出改进，通过提高少数类样本的抽样比重，使得特征对少数类有更多的决定权。具体做法是：假设为训练集样本个数，其中为正类样本的数量，同样的为负类样本的数量，为初始抽样的数量，取值为训练集中少数类样本的数量，为最近邻同类样本的数量，为最近邻异类样本的数量。若抽取的样本为正类和负类时，则分别为式（3）和式（4）所示，的值均为-。

在计算对应特征的权重时，原本的值是固定设置的，改进后分别设定。这样保证其为样本集中的少数类数量，同时也在抽样过程中确保少数类比多数类具有更高的比例，这是针对IP 地址数据的不平衡的特点进行的改进，理论上可以避免多数类造成的分类精度假高问题，改进后的权重公式如式（5）所示。

1.2 R-RF算法流程图及伪代码

Relief F 算法在随机森林中的应用主要是将特征进行排序，按权值大小将特征平均的分成三个区间。在之后随机森林算法生成决策树步骤中，均匀的抽取三个区间的特征，组成分类效果均匀的特征子集训练决策树，将新算法命名为R-RF算法，其具体流程如图1所示。

图1 Relief F结合随机森林算法流程

首先对IP 地址数据集采用Bootstrap 方法进行抽样，随机得到各训练子集，其中袋外数据集作为测试集用于最后的算法评估，然后对所有训练集数据运用上一节的改进Relief F 算法计算特征权重，得到带有权值的特征集合。特征按权值大小排序，权值越大的分类性能越好。将排好序的特征按照分类性能平均的分为高、中、低三个特征集合。在构建决策树时，不再采用随机抽样的策略，而是在高中低三个特征集合中均匀的抽取特征，保证生成的决策树有很高的稳定性。不断地进行特征抽取生成决策树，组成最终的随机森林。

R-RF算法核心步骤伪代码

2 构建多特征IP地址数据库

现有的IP地址数据库，大多数对于信息如何采集并不公开，不同的IP 地址数据库在更新频率、IP地址覆盖率和声称的准确度上都会有一些差异。表1 列举了四个国内外具有代表性的IP地址数据库，对它们的一些关键信息加以展示。

表1 常见IP地址数据库关键信息

IP 地址数据库中的信息通常包含了IP 地址段、运营商、大洲、国家、省级区域、城市级区域、经纬度和邮编等信息，其中IP 地址数据库的部分属性可能会缺失，如：Country=中国，Region =未知，City=未知，ISP=中国电信，ZIP Code=未知。为了补全不同IP地址数据库中可能缺失的信息，同时结合IP 地址本身和网络测量数据作为特征，从而提高算法的分类精度，需要构建多特征IP 地址数据库，其完整的构建过程如图2所示。

图2 多特征IP地址数据库构建流程

首先将各IP 地址数据库里的数据统一化处理，统一处理为数值或者字符串便于分类识别，再根据IP 地址段选择出2个及以上IP 地址数据库均收录的信息，仅有1个数据库收录的IP 地址段信息其可靠性不高，丢弃该条记录。对于其他的特征信息，如果所有数据库都没有记录这些信息，无法互相补全，同样丢弃该条记录。如果有数据库收录了这些特征信息但是完全不相同，根据优先级选择特征信息，如果是不完全相同的情况，通过投票的方式决定特征信息。经过这一步的处理，可以得到初步融合的IP 地址数据库。

其中优先级选取的原则，根据四个IP 地址数据库城市覆盖率大小定义优先级先后为：IP2location、百度、纯真、新浪。经过上述过程初步融合的IP 地址数据库，其中记录的IP 地址数据各特征为IP 地址、运营商、省级区划代码、城市区划代码。再对以上初步融合的IP 地址数据库中每一条IP 地址使用探测源进行网络测量，得到时延和跳数信息，丢弃无法进行网络测量的IP 地址数据。再将IP 地址分割为4 段，最终得到本文实验使用的多特征IP地址数据库，其各特征分别为IP1、IP2、IP3、IP4、运营商、时延、跳数、省级区划代码、城市区划代码。

最终得到的多特征IP 地址数据库，不仅具有更多的特征，信息也更加完整，能有效提高IP定位的准确率。

3 实验与结果分析

3.1 各特征权重计算

根据多特征IP 地址数据库的数据，首先需要评价并计算出每个特征对于分类的贡献度。本文使用随机森林算法分别对多特征IP 数据库中每一个特征进行分类测试，得到准确率、精准率与召回率的调和平均数（F1-Measure）以及ROC 曲线面积这三项评价指标的结果如表2所示。

表2 单一特征分类评价指标对比

表2 中IP1、IP4和运营商三个特征的F1-Measure 为空，因为在仅使用这三个特征中的一个进行分类时，部分城市的分类结果完全错误，造成该城市所对应的F1-Measure 无法计算，从而导致该项特征总体分类情况的F1-Measure 无法计算得出。

由于单独使用个别分类效果较差的特征时，分类的准确度无法真正反映分类的效果，以及部分分类结果全部错误导致部分F1-Measure 为空这两点问题，表2可以简单直观反映各特征的重要性，但是无法直接给出各特征对于分类的贡献度，而各特征的贡献度在特征选择部分至关重要，在R-RF算法的特征选择部分更是需要根据贡献度来对特征进行加权。在图3给出计算得到的各特征对于分类的贡献度，其数值大小与表2里各特征的准确率高低趋势基本一致，同样依次是IP2、IP3、跳数、时延、IP1、IP4、运营商。

图3 各特征对分类贡献度

3.2 IP定位结果

在均使用多特征IP 数据集进行分类的情况下，首先使用随机森林算法对多特征IP 数据库中河南省各城市进行IP 定位，所得到混淆矩阵如图4所示。

图4 随机森林算法分类所得混淆矩阵

再使用R-RF 算法对多特征IP 地址数据库进行IP定位，得到的混淆矩阵如图5。

图5 R-RF算法分类所得混淆矩阵

明显可以从图4的混淆矩阵看出，随机森林算法分类错误的样本个数有一些是大于2个的，但是在R-RF算法的混淆矩阵中，分类错误的样本个数都不超过2个。

使用随机森林算法和改进的R-RF算法分别进行分类测试，得到准确率、精准率与召回率的调和平均数（F1-Measure）以及ROC 曲线面积这三项评价指标的结果如表3所示。

表3 两种算法分类评价指标对比

将准确率、F1-Measure、ROC 曲线面积这三项常用指标的总体结果绘制成折线图，如图6所示。由折线图可以直观的看出在均使用多特征IP数据集进行分类的情况下，R-RF算法比原始随机森林算法得到的分类准确率更高，分类性能更好，证明了改进算法的有效性。

图6 两种算法分类评价指标对比

4 结语

本文结合网络测量数据和IP 地址本身共同构建了多特征IP 地址数据库，并根据网络IP 地址数据不平衡和各特征重要性不一致会影响网络IP 定位结果的特点，对特征权重算法Relief F做出改进，融入随机森林分类算法的特征选择步骤中，对原始随机森林算法在IP 定位领域做出改进。实验结果表明在均使用多特征IP 数据集进行分类的情况下，R-RF 算法比原始随机森林算法得到的分类准确率更高，分类性能更好，证明了改进算法的有效性。