基于特征選擇改進(jìn)的隨機(jī)森林IP定位方法

張鶴林，甘 勇,2，劉淵博

（1.鄭州輕工業(yè)大學(xué)計算機(jī)與通信工程學(xué)院，鄭州 450001；2.鄭州工程技術(shù)學(xué)院，鄭州 450001）

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)應(yīng)用、網(wǎng)絡(luò)數(shù)據(jù)和網(wǎng)絡(luò)實體等逐步構(gòu)成了網(wǎng)絡(luò)空間，網(wǎng)絡(luò)空間與海陸天空等地理空間不同，是一個動態(tài)空間，數(shù)據(jù)交互極快。但是從網(wǎng)絡(luò)空間安全的角度出發(fā)，還是很有必要對網(wǎng)絡(luò)空間進(jìn)行測繪。網(wǎng)絡(luò)實體定位技術(shù)如同地理空間測繪中的水文測量技術(shù)一樣，能夠?qū)崿F(xiàn)網(wǎng)絡(luò)實體資源到地理空間的映射，是網(wǎng)絡(luò)空間測繪的基礎(chǔ)，由于網(wǎng)絡(luò)實體通常可以通過網(wǎng)絡(luò)實體的IP 地址來進(jìn)行唯一標(biāo)識，從而確定該網(wǎng)絡(luò)實體在一定粒度上的地理空間位置，因此又可以稱為IP 定位技術(shù)。

目前主流的IP 定位技術(shù)有三類：基于數(shù)據(jù)庫查詢的方法、基于網(wǎng)絡(luò)測量的方法和基于機(jī)器學(xué)習(xí)的方法?；跀?shù)據(jù)庫查詢的方法方便快捷，但是定位結(jié)果完全取決于數(shù)據(jù)庫，可能會有很大的誤差。基于網(wǎng)絡(luò)測量的方法是較傳統(tǒng)且有效的方法，主要通過網(wǎng)絡(luò)測量獲取網(wǎng)絡(luò)實體之間的網(wǎng)絡(luò)空間信息，比如最常用的時延和跳數(shù)兩種信息，將其通過一些參數(shù)近似轉(zhuǎn)換為物理空間的距離，從而推斷出目標(biāo)IP 的地理位置。基于機(jī)器學(xué)習(xí)的方法其核心思想是將IP 定位轉(zhuǎn)換為分類或者聚類問題，以IP 地址、時延和跳數(shù)等信息作為特征來訓(xùn)練模型，從而得出目標(biāo)IP的地理位置。

本文結(jié)合了網(wǎng)絡(luò)測量的數(shù)據(jù)和IP 地址本身共同形成多特征的數(shù)據(jù)集，使用隨機(jī)森林這一機(jī)器學(xué)習(xí)分類模型，并根據(jù)網(wǎng)絡(luò)IP 地址數(shù)據(jù)不平衡和各特征重要性不一致會影響網(wǎng)絡(luò)IP 定位結(jié)果的特點，對特征權(quán)重算法Relief F 做出改進(jìn)，融入隨機(jī)森林分類算法的特征選擇步驟中，提出一種基于特征選擇改進(jìn)的隨機(jī)森林城市級IP定位方法。

1 特征選擇算法改進(jìn)

1.1 Relief F算法改進(jìn)

Relief 算法是一種比較常見且高效的特征權(quán)重算法，其核心思想是根據(jù)數(shù)據(jù)中每個特征對于分類的相關(guān)度不同，計算給出不同的權(quán)重，再根據(jù)不同的要求設(shè)定閾值，丟棄不符合閾值要求的特征。假設(shè)訓(xùn)練集為，一般是隨機(jī)選取出一個樣本，首先需要找到樣本同類型且最近鄰的樣本，然后再找到樣本不同類型同樣最近鄰的樣本。對于數(shù)據(jù)中任一個特征來說，如果與的距離小于與的距離，就認(rèn)為特征是有利于提高分類準(zhǔn)確率的，該特征的權(quán)重就會適當(dāng)加大，反之則減小權(quán)重。一般來說，都會多次計算取各特征權(quán)重平均值，假設(shè)計算次，各特征的計算方式如式（1）所示。

由于Relief只能處理二分類問題，改進(jìn)算法Relief F 算法在Relief 算法基礎(chǔ)上增加了多分類問題的解決策略，其核心思想是：把抽取樣本和樣本這一過程，重新設(shè)置為從每類樣本分別找到個最近鄰的樣本。此方法不僅能提高算法穩(wěn)定性，同時也減輕了噪聲對結(jié)果的干擾，權(quán)重計算方式如式（2）所示。

（）是原數(shù)據(jù)集中類別為的樣本所占比例，M（）表示類?class（）中第個最近鄰樣本，diff（,,）表示對于特征來說，樣本和的差。

Relief F算法的改進(jìn)僅僅是針對分類問題的，算法在抽取不同類別樣本時采用的是隨機(jī)抽取相同數(shù)量的樣本的方式，一般情況下能達(dá)到很好的穩(wěn)定性和抗噪聲干擾能力，但是要想解決不平衡數(shù)據(jù)引起的問題，這并不是最佳的方式。

因此，本文對以上Relief F 算法的抽樣步驟做出改進(jìn)，通過提高少數(shù)類樣本的抽樣比重，使得特征對少數(shù)類有更多的決定權(quán)。具體做法是：假設(shè)為訓(xùn)練集樣本個數(shù)，其中為正類樣本的數(shù)量，同樣的為負(fù)類樣本的數(shù)量，為初始抽樣的數(shù)量，取值為訓(xùn)練集中少數(shù)類樣本的數(shù)量，為最近鄰?fù)悩颖镜臄?shù)量，為最近鄰異類樣本的數(shù)量。若抽取的樣本為正類和負(fù)類時，則分別為式（3）和式（4）所示，的值均為-。

在計算對應(yīng)特征的權(quán)重時，原本的值是固定設(shè)置的，改進(jìn)后分別設(shè)定。這樣保證其為樣本集中的少數(shù)類數(shù)量，同時也在抽樣過程中確保少數(shù)類比多數(shù)類具有更高的比例，這是針對IP 地址數(shù)據(jù)的不平衡的特點進(jìn)行的改進(jìn)，理論上可以避免多數(shù)類造成的分類精度假高問題，改進(jìn)后的權(quán)重公式如式（5）所示。

1.2 R-RF算法流程圖及偽代碼

Relief F 算法在隨機(jī)森林中的應(yīng)用主要是將特征進(jìn)行排序，按權(quán)值大小將特征平均的分成三個區(qū)間。在之后隨機(jī)森林算法生成決策樹步驟中，均勻的抽取三個區(qū)間的特征，組成分類效果均勻的特征子集訓(xùn)練決策樹，將新算法命名為R-RF算法，其具體流程如圖1所示。

圖1 Relief F結(jié)合隨機(jī)森林算法流程

首先對IP 地址數(shù)據(jù)集采用Bootstrap 方法進(jìn)行抽樣，隨機(jī)得到各訓(xùn)練子集，其中袋外數(shù)據(jù)集作為測試集用于最后的算法評估，然后對所有訓(xùn)練集數(shù)據(jù)運用上一節(jié)的改進(jìn)Relief F 算法計算特征權(quán)重，得到帶有權(quán)值的特征集合。特征按權(quán)值大小排序，權(quán)值越大的分類性能越好。將排好序的特征按照分類性能平均的分為高、中、低三個特征集合。在構(gòu)建決策樹時，不再采用隨機(jī)抽樣的策略，而是在高中低三個特征集合中均勻的抽取特征，保證生成的決策樹有很高的穩(wěn)定性。不斷地進(jìn)行特征抽取生成決策樹，組成最終的隨機(jī)森林。

R-RF算法核心步驟偽代碼

2 構(gòu)建多特征IP地址數(shù)據(jù)庫

現(xiàn)有的IP地址數(shù)據(jù)庫，大多數(shù)對于信息如何采集并不公開，不同的IP 地址數(shù)據(jù)庫在更新頻率、IP地址覆蓋率和聲稱的準(zhǔn)確度上都會有一些差異。表1 列舉了四個國內(nèi)外具有代表性的IP地址數(shù)據(jù)庫，對它們的一些關(guān)鍵信息加以展示。

表1 常見IP地址數(shù)據(jù)庫關(guān)鍵信息

IP 地址數(shù)據(jù)庫中的信息通常包含了IP 地址段、運營商、大洲、國家、省級區(qū)域、城市級區(qū)域、經(jīng)緯度和郵編等信息，其中IP 地址數(shù)據(jù)庫的部分屬性可能會缺失，如：Country=中國，Region =未知，City=未知，ISP=中國電信，ZIP Code=未知。為了補(bǔ)全不同IP地址數(shù)據(jù)庫中可能缺失的信息，同時結(jié)合IP 地址本身和網(wǎng)絡(luò)測量數(shù)據(jù)作為特征，從而提高算法的分類精度，需要構(gòu)建多特征IP 地址數(shù)據(jù)庫，其完整的構(gòu)建過程如圖2所示。

圖2 多特征IP地址數(shù)據(jù)庫構(gòu)建流程

首先將各IP 地址數(shù)據(jù)庫里的數(shù)據(jù)統(tǒng)一化處理，統(tǒng)一處理為數(shù)值或者字符串便于分類識別，再根據(jù)IP 地址段選擇出2個及以上IP 地址數(shù)據(jù)庫均收錄的信息，僅有1個數(shù)據(jù)庫收錄的IP 地址段信息其可靠性不高，丟棄該條記錄。對于其他的特征信息，如果所有數(shù)據(jù)庫都沒有記錄這些信息，無法互相補(bǔ)全，同樣丟棄該條記錄。如果有數(shù)據(jù)庫收錄了這些特征信息但是完全不相同，根據(jù)優(yōu)先級選擇特征信息，如果是不完全相同的情況，通過投票的方式?jīng)Q定特征信息。經(jīng)過這一步的處理，可以得到初步融合的IP 地址數(shù)據(jù)庫。

其中優(yōu)先級選取的原則，根據(jù)四個IP 地址數(shù)據(jù)庫城市覆蓋率大小定義優(yōu)先級先后為：IP2location、百度、純真、新浪。經(jīng)過上述過程初步融合的IP 地址數(shù)據(jù)庫，其中記錄的IP 地址數(shù)據(jù)各特征為IP 地址、運營商、省級區(qū)劃代碼、城市區(qū)劃代碼。再對以上初步融合的IP 地址數(shù)據(jù)庫中每一條IP 地址使用探測源進(jìn)行網(wǎng)絡(luò)測量，得到時延和跳數(shù)信息，丟棄無法進(jìn)行網(wǎng)絡(luò)測量的IP 地址數(shù)據(jù)。再將IP 地址分割為4 段，最終得到本文實驗使用的多特征IP地址數(shù)據(jù)庫，其各特征分別為IP1、IP2、IP3、IP4、運營商、時延、跳數(shù)、省級區(qū)劃代碼、城市區(qū)劃代碼。

最終得到的多特征IP 地址數(shù)據(jù)庫，不僅具有更多的特征，信息也更加完整，能有效提高IP定位的準(zhǔn)確率。

3 實驗與結(jié)果分析

3.1 各特征權(quán)重計算

根據(jù)多特征IP 地址數(shù)據(jù)庫的數(shù)據(jù)，首先需要評價并計算出每個特征對于分類的貢獻(xiàn)度。本文使用隨機(jī)森林算法分別對多特征IP 數(shù)據(jù)庫中每一個特征進(jìn)行分類測試，得到準(zhǔn)確率、精準(zhǔn)率與召回率的調(diào)和平均數(shù)（F1-Measure）以及ROC 曲線面積這三項評價指標(biāo)的結(jié)果如表2所示。

表2 單一特征分類評價指標(biāo)對比

表2 中IP1、IP4和運營商三個特征的F1-Measure 為空，因為在僅使用這三個特征中的一個進(jìn)行分類時，部分城市的分類結(jié)果完全錯誤，造成該城市所對應(yīng)的F1-Measure 無法計算，從而導(dǎo)致該項特征總體分類情況的F1-Measure 無法計算得出。

由于單獨使用個別分類效果較差的特征時，分類的準(zhǔn)確度無法真正反映分類的效果，以及部分分類結(jié)果全部錯誤導(dǎo)致部分F1-Measure 為空這兩點問題，表2可以簡單直觀反映各特征的重要性，但是無法直接給出各特征對于分類的貢獻(xiàn)度，而各特征的貢獻(xiàn)度在特征選擇部分至關(guān)重要，在R-RF算法的特征選擇部分更是需要根據(jù)貢獻(xiàn)度來對特征進(jìn)行加權(quán)。在圖3給出計算得到的各特征對于分類的貢獻(xiàn)度，其數(shù)值大小與表2里各特征的準(zhǔn)確率高低趨勢基本一致，同樣依次是IP2、IP3、跳數(shù)、時延、IP1、IP4、運營商。

圖3 各特征對分類貢獻(xiàn)度

3.2 IP定位結(jié)果

在均使用多特征IP 數(shù)據(jù)集進(jìn)行分類的情況下，首先使用隨機(jī)森林算法對多特征IP 數(shù)據(jù)庫中河南省各城市進(jìn)行IP 定位，所得到混淆矩陣如圖4所示。

圖4 隨機(jī)森林算法分類所得混淆矩陣

再使用R-RF 算法對多特征IP 地址數(shù)據(jù)庫進(jìn)行IP定位，得到的混淆矩陣如圖5。

圖5 R-RF算法分類所得混淆矩陣

明顯可以從圖4的混淆矩陣看出，隨機(jī)森林算法分類錯誤的樣本個數(shù)有一些是大于2個的，但是在R-RF算法的混淆矩陣中，分類錯誤的樣本個數(shù)都不超過2個。

使用隨機(jī)森林算法和改進(jìn)的R-RF算法分別進(jìn)行分類測試，得到準(zhǔn)確率、精準(zhǔn)率與召回率的調(diào)和平均數(shù)（F1-Measure）以及ROC 曲線面積這三項評價指標(biāo)的結(jié)果如表3所示。

表3 兩種算法分類評價指標(biāo)對比

將準(zhǔn)確率、F1-Measure、ROC 曲線面積這三項常用指標(biāo)的總體結(jié)果繪制成折線圖，如圖6所示。由折線圖可以直觀的看出在均使用多特征IP數(shù)據(jù)集進(jìn)行分類的情況下，R-RF算法比原始隨機(jī)森林算法得到的分類準(zhǔn)確率更高，分類性能更好，證明了改進(jìn)算法的有效性。

圖6 兩種算法分類評價指標(biāo)對比

4 結(jié)語

本文結(jié)合網(wǎng)絡(luò)測量數(shù)據(jù)和IP 地址本身共同構(gòu)建了多特征IP 地址數(shù)據(jù)庫，并根據(jù)網(wǎng)絡(luò)IP 地址數(shù)據(jù)不平衡和各特征重要性不一致會影響網(wǎng)絡(luò)IP 定位結(jié)果的特點，對特征權(quán)重算法Relief F做出改進(jìn)，融入隨機(jī)森林分類算法的特征選擇步驟中，對原始隨機(jī)森林算法在IP 定位領(lǐng)域做出改進(jìn)。實驗結(jié)果表明在均使用多特征IP 數(shù)據(jù)集進(jìn)行分類的情況下，R-RF 算法比原始隨機(jī)森林算法得到的分類準(zhǔn)確率更高，分類性能更好，證明了改進(jìn)算法的有效性。