基于隨機森林的IP地址城市級定位方法研究?

蔡 穎 張 琨 尹魏昕 張云純 蔣彤彤 方 悅

（1.南京理工大學計算機科學與工程學院 南京 210094）

（2.國家計算機網絡與信息安全管理中心江蘇分中心 南京 210019）

1 引言

互聯網如今已成為信息時代不可或缺的支撐部分，截至2018年12月，我國網民規模達8.29億［1］。隨著網絡與用戶生活的聯系愈發緊密，大量的網絡服務都需要在通過IP對用戶進行精準定位的前提下進行。例如，在網絡管理領域，網絡管理員可以通過IP測量快速定位網絡錯誤發生的位置［2］；在廣告投放領域，商家可以通過IP精準定位用戶所在的地理位置，從而進行針對性的廣告投放［3］；在網絡安全領域，網絡監管部門可以通過IP實現對網絡犯罪分子的位置定位，有效降低網絡違法案件的偵破難度［4］。IP作為重要的網絡基礎資源，是實現網絡設備映射到用戶實體、網絡空間映射到地理位置的橋梁，因此實現IP地址定位對網絡空間精準監管具有重要意義。

IP地址定位即根據網絡設備的IP確定其在地理上的位置。在研究中，將具有IP的網絡設備劃分為測量點、基準點和待測點三類，其中測量點是指能向目的IP發起主動測量的網絡設備，基準點是指地理位置已知且可對測量點所發數據包做出響應的網絡設備，而待測點則是指需要實現地理位置定位的IP即待定位的網絡設備［5］。

傳統的IP地址定位方法總體上可分為基于推測和基于時延兩類［6］。前者一般通過查詢Whois數據庫，或直接根據主機名來推測當前IP設備所處位置，代表算法包括IP2LL，GeoTrack和Visual?Route［6～8］等。基于時延的定位算法是結合網絡拓撲信息，通過測定目標主機到測量點的時延，來估測目標主機的地理位置，代表算法有GeoPing，CBG，Posit和Octant［6，9］等。

傳統的IP地址定位方法存在定位準確度差，算法復雜度高的問題。基于此，立足于江蘇省內真實的IP數據，本文提出了一種基于隨機森林的IP地址城市級定位方法，旨在利用已有的IP地址數據，首先從IP本身具有的特點，以及IP之間存在的關系出發，定義經過路由特征和地域觸發特征，后結合機器學習中分類的思想，利用隨機森林進行模型訓練，實現IP城市級高準確度定位，從而可以有效輔助精確的定向廣告投放、網絡性能優化、社交網絡推薦、攻擊追蹤溯源等實際應用的實現。

2 數據的獲取與處理

由于電信、移動、聯通等運營商之間的網絡建設是相互獨立的，因此為減少此類情況對分類器構建可能產生的負面影響，應對IP根據其所屬運營商不同進行分類，并在同一類別下選擇基準點，進而發起測量并記錄相關數據。

2.1 主動測量

本文以江蘇省內電信持有的IP為例，從中選取了近4000個IP作為基準點，同時選擇網絡帶寬充裕且時延抖動較小的凌晨時段［10］，由測量點向其發起主動測量。

本文中選取的測量方法為TraceRoute，即路由追蹤。TraceRoute命令是利用ICMP協議來定位源IP與目的IP之間的所有路由器。根據該指令，可以獲得測量點向基準點發出的數據包所經過的路由器數量，以及經過的每一個路由器所返回的時延和路由器信息［11］。其測量結果如圖1所示。

圖1 主動測量示例

測量點向基準點發起TraceRoute命令，每一跳返回結果包括5項，表示為

式中，tracerti表示第i跳返回數據，routeIDi表示當前路由跳數，routeIPi表示途徑路由器的IP地址 ，routeDelayi1，routeDelayi2，routeDelayi3表 示 三次發送數據包的返回時間。

測量中每次探測3次，若測量中第i跳的時延以delayi表示，則有：

式中，routeDelayij表示主動測量中第i跳第j次數據包返回時間，delayi取其最小值。因為時延包括發送、傳播、處理和排隊時延等，因此取最小返回時間可以進一步降低時延抖動帶來的誤差。

從測量點發起的路由追蹤中，存在可追蹤至目的IP部分路由路徑，和可追蹤至目的IP完整路由路徑兩種情況，分別采用下述兩種方法進行測量數據的采集：

1）對于可追蹤至目的IP完整路由路徑的情況，則正常記錄各跳路由跳數、時延和途徑路由IP。對于追蹤路徑中存在的少數“請求超時”情況，此跳時延以默認時延計算，途徑路由IP記作“*”。

2）對于可追蹤至目的IP部分路由路徑的情況，考慮到若路由可達，則一般在30跳內可以完成跳轉的實際情況，因此僅記錄30跳內的時延和路徑。30跳內的各跳路由跳數、時延和途徑路由IP的記錄方法同1）所述。

經過上述處理后，得到測量點到基準點的主動測量數據為

式中，tracert'i={routeIDi，delayi，routeIPi}表示第i跳測量數據。

進一步，若測量中路由跳數以routemum表示，時延以delaysum表示，路由路徑以routeseq表示，則有：

式中，|Tracert|表示集合Tracert的模。

此外，在進行測量的過程中，得到的測量結果將由程序自動保存至數據庫中進行存儲。而為進一步訓練分類器，還需要對數據進行預處理并構建標準的數據集。

2.2 特征提取

考慮到同一網絡運營商往往會將連續的IP地址段分配給相同或相鄰地區的實際情況，本文從IP地址本身具有的特點出發，將基準點IP以“。”字符為分隔符，分割為{ip1，ip2，ip3，ip4}四部分，作為一部分分類特征。

另一方面，從IP間的相關性出發，將測量點到基準點的時延delaysum和路由跳數routemum也納入了訓練分類器所要考慮的特征。

此外，考慮到運營商網絡的拓撲以及用戶的訪問行為，本文將對經過路由特征和地域觸發特征分別進行定義，并加入到分類特征中去。

定義1.經過路由特征。定義經過路由特征為測量點到基準點的路由路徑routeseq所經過的城市骨干路由，以cityroute表示。

針對運營商網絡拓撲，可以將路由器分為省級骨干網節點、市級骨干網節點和普通節點三類［4，12］。通常而言，歸屬城市不同的IP之間不允許互聯，若跨市的兩個普通節點間需要實現互訪，則其數據流量必須經過骨干網節點。通過對測量得到的路由路徑信息按城市進行分類，并分別采用PrefixSpan算法［13］進行關聯規則挖掘，則可分析獲得江蘇省內13個大市的市級骨干網節點的網段特征。

若測量點到某城市所有基準點的路由路徑數據集 為RtSeqc={routeseq1，routeseq2，…，routeseqn}，其中routeseqi表示一個序列。若序列freseqj是序列routeseqi的子序列，則稱routeseqi包含freseqj。序列freseqj在RtSeqc中的支持度，是指RtSeqc中包含freseqj的序列個數，記作sup(freseqj)。給定支持度閾值supΔ，若sup(freseqj)≥supΔ，則稱freseqj在RtSeqc中是頻繁的。現尋找RtSeqc中所有頻繁的最長子序列：

其中，c為當前城市代碼，routeseqi為測量點到第i個基準點的路由路徑，n為基準點總數，m為最長頻繁子序列總數，且有m≤n，freseqj?routeseqi，i∈{1 ，2，…，n}，j∈{1 ，2，…，m}，FreSeqc則為該城市骨干網節點的網段特征。

進一步，判斷測量點至基準點的路由路徑是否經過某城市的骨干路由，即是否包含該城市骨干網節點對應網段下的IP，即：

其中，城市代碼c∈{1，2，…，13}，如表1所示。

表1 江蘇省內城市代碼映射表

定義2.地域觸發特征。定義地域觸發特征為基準點發送的數據包中，包含的關鍵詞所映射的城市，以cityword表示。

基于已有且真實的省內IP間傳輸的數據包信息，對基準點發送的數據包，提取其中與二級及三級行政區相關的關鍵詞，并統計其出現次數，即將一個基準點發送的所有數據包處理為

式中，＜c，count＞表示一個元組，c為城市代碼，count為該城市對應關鍵詞出現次數。將最大count所對應的城市代碼，作為該基準點cityword的值，即：

其中，c→count表示元組內城市代碼和關鍵詞出現次數的映射關系，表示count不為0時，最大count所對應的城市代碼，城市代碼如表1所示，城市相關關鍵詞如表2所示。

2.3 構建數據集

綜上，融合多維度特征，最終將形成包含基準點ip1，ip2，ip3，ip4，時延delaysum，路由跳數routemum，地域觸發特征cityword，經過路由特征cityroute等8個特征在內，以基準點對應城市為分類目標的標準數據集合。若以D={X，y}表示該數據集，則其特征可用矩陣X表示，且有：

其中，N為該數據集中樣本的數量，即從測量點發起主動測量的基準點總數，矩陣X中每一個行可用一個一維數組xi表示，其中包含了8個維度的特征，即有：

其中，y表示該數據集的分類目標，可用一維數組進行存儲。對上述數據集使用隨機森林訓練分類模型并進行IP地址定位的方法將在第3節中進行詳細描述。

表2 城市相關關鍵詞

3 基于隨機森林的IP地址定位方法

在機器學習中，隨機森林（Random Forests）是指利用多棵決策樹對樣本進行訓練并預測的一種分類器，其輸出類別是由所有樹輸出類別的眾數而決定的。該算法最早由Leo Breiman和Adele Cutler發展和推論形成［14］，近年來因其在預測準確率方面存在的優勢，隨機森林算法被廣泛應用于市場營銷建模、醫療保健預測等多個領域［15～16］，具有廣闊的應用前景。

本文基于前期采集和處理得到的數據集，受此算法思想啟發，提出了一種基于隨機森林的IP地址定位方法。

3.1 算法描述

在隨機森林算法中，“森林”是指決策樹的集成。隨機森林是在具有N個樣本的數據集中，每次隨機且有放回地抽取K個樣本訓練產生相應的決策樹。由此，經過M次抽樣后，便可得到M棵決策樹。

對于本文所提算法中的任意一棵決策樹而言，其構建的核心在于特征選擇，即從樣本數據的特征中選擇一個作為當前節點的分裂標準。本文中，衡量分裂質量的性能采用了Gini不純度函數。

對于第2節中處理得到的數據集D={X，y}而言，假設當前抽取出用于訓練決策樹的樣本集為Di，則其分類后Gini不純度為

對于Di包含的F個特征而言，若以特征fea?ture為分裂特征，則Di分裂后的Gini不純度為

式中，c為城市代碼，category為分類總數，在本文中即城市數量，pj為樣本屬于類別j的發生概率，Dij表示Di分裂后的一個子集。

進一步，遍歷F個可能產生分裂的特征feature，分別計算按當前特征對Di進行劃分后的Gini不純度，按其值最小的特征分裂。

在本文所提算法中，而由于樣本選取采用了隨機抽樣的方式，因此這M棵決策樹之間是相互獨立的，將這些決策樹聚集在一起便形成了隨機森林，其定位結果是由M棵決策樹通過投票產生的。

值得注意的是，若原始數據集中每個樣本的特征維度為F，則應指定一個常數f，每次隨機地從F個特征中選取f個特征子集，當前決策樹應從這f個特征中選擇最優的特征進行分裂。模型訓練流程如圖2所示，其中{D1，D2，…，DM}表示第M次抽取出來用于訓練決策樹的樣本集。

圖2 模型訓練示意圖

由上可知，隨機森林中每棵決策樹的訓練都是獨立的。因此，雖然每棵樹的分類能力有限，但是隨機森林產生了大量隨機樹，相較于傳統的決策樹算法，具有更高自適應性。

綜上，對于前期測量獲得的大小為N的數據集D，基于隨機森林的IP地址定位方法具體描述如算法1所示。

算法1.基于隨機森林的IP地址定位算法

Input：數據集D，決策樹數目n_estimators，單棵樹樣本數n_samples，特征選擇標準criterion，特征總數F，特征選擇個數max_features，待測點的特征xpre

Output：待測點的城市級定位結果ypre

S1：對數據集D包含的N個樣本數據，每次隨機有放回地抽取n_samples個樣本作為一個樣本集

S2：重復S1抽取n_estimators次，生成n_estima?tors個含有n_samples個樣本的樣本集

S3：針對每個樣本集，隨機抽取max_features（max_feature＜F）個特征作為決策樹的分類特征，并采用criterion為標準在每個節點上選取特征分裂，直到節點不可分為止

S4：重復S3直到所有樣本集都被訓練，從而得到n_estimators棵自由生長的決策樹

S5：重復S1-S4直到模型準確率達到閾值，將n_estimators棵決策樹組合成隨機森林分類模型RFModel

S6：將待測點特征xpre輸入RFModel，記錄每棵樹的分類結果，并投票產生分類結果ypre

在訓練本文所提算法的分類模型時，應該使每棵樹都盡最大程度的自由生長，且無需剪枝過程，即隨機森林在訓練過程中，每棵樹的訓練樣本及分類特征都是隨機選取的，同時分類結果并不由單棵決策樹決定，因此隨機森林相較于傳統的決策樹分類算法，并不容易陷入過擬合，并且具有更強的抗噪能力。

3.2 模型優化

隨機森林的優化主要有特征選擇和參數優化兩個策略。本文所提算法在第2節中創新性地對經過路由特征和地域觸發特征進行了定義，優化了特征。而此處將進一步對模型的參數進行優化。

基于隨機森林的IP地址定位模型訓練主要涉及到的參數包括框架參數和決策樹參數兩類。其中框架參數包括生成決策樹總數n_estimators，特征選擇標準criterion以及表示是否采用袋外樣本評估模型的參數oob_score共3個。決策樹參數主要包括特征選擇個數max_features，最大深度max_depth，葉子節點最少樣本數min_samples_leaf等共14個。其中，最主要的參數為n_estimators和max_features，這兩個參數決定了模型的好壞以及訓練的效率。

一般而言，n_estimators取值過小易過擬合，過大易欠擬合，同時訓練過多的決策樹也會導致耗時過長和浪費內存。而對于max_features而言，取值越大訓練過程中模型能學習到的信息越多，但也會降低單棵決策樹的多樣性和訓練速度，從而導致模型準確率下降。

為了優化算法，本文將數據集劃分為訓練集和測試集，而后分別改變n_estimators和max_features取值，重復訓練，以模型的分類準確率為依據進行參數優化，其具體結果將在第4節中詳細闡述。

4 實驗驗證

為驗證本文提出的基于隨機森林的IP地址城市級定位方法，本節將從模型評價及基于真實準確的IP地址數據集交叉驗證兩個方面，對所提定位方法進行實證分析。

4.1 數據描述

本文實驗數據來源于南京理工大學與國家計算機網絡與信息安全管理中心江蘇分中心聯合建立的江蘇省研究生工作站。實驗部分以南京某IP為測量點，對江蘇省內共3994個基準點發起了主動測量，其部分數據庫表信息如圖3所示。

包含基準點ip1，ip2，ip3，ip4，時延delaysum，路由跳數routemum，地域觸發特征cityword，經過路由特征cityword等8個特征在內，以基準點對應城市city為分類目標的數據集D，其數據組成如圖4所示，其中橫坐標為城市，縱坐標為對應數據量。

圖3 數據庫中存儲的部分測量數據

圖4 數據集組成

4.2 參數優化

為了平衡適中地選擇最佳參數，以達到本文3.2節中所述模型優化的效果，在實驗過程中，對數據集按7∶3的比例劃分訓練集和測試集，并分別改變n_estimators和max_features取值，重復隨機森林模型訓練，以測試集的分類準確率為依據進行調參。

實驗中除n_estimators和max_features外，crite?rion='gini'表示以Gini不純度作為特征選擇標準，bootstrap=True表示構建決策樹時采用隨機有放回的方法抽取樣本集，max_depth=None表示每棵決策樹會分裂至所有葉子純凈，oob_score=True表示使用袋外樣本來估計模型的泛化精度，剩余11個參數取default值。測試集準確率隨參數變化情況如圖5所示。

如圖5（a）所示，當指定max_features為7時，測試集的準確率隨n_estimators的增大而上升，當n_estimators變化至500左右時，測試集準確率趨于穩定。

圖5 測試集準確率隨參數變化示意圖

如圖5（b）所示，當指定n_estimators為500時，測試集的準確率在一定范圍內隨max_features的增加而上升，但當max_features大于3時，單棵決策樹的多樣性逐漸降低，大量決策樹趨于相似，從而導致模型準確率開始下降。

綜上，經過參數優化后，本文實驗將在n_esti?mators=500和max_features=3的前提下進行。

4.3 結果及分析

取n_estimators=500和max_features=3，訓練集與測試集的數據量比例為7∶3，其余參數與調參過程中的取值一致。通過多次重復實驗，得到的袋外分數及測試集準確率如圖6所示，其中橫坐標表示實驗的次數。

圖6 算法模型性能

圖6中的OOB分數即為隨機森林訓練模型的袋外分數。由于在隨機森林算法中，構建決策樹采用的是有放回的隨機抽樣，因此根據概率論可知，數據集中約有1/3的數據是沒有被選取的，這部分數據也被稱作袋外數據（Out Of Bag，OOB）。在模型訓練的過程中，可以將OOB作為測試樣本來衡量模型的好壞，在樣本數量確定的情況下，袋外分數越高說明模型的泛化能力越好，性能更佳。

另外，通過衡量不同特征時的袋外分數，得到的基準點ip1，ip2，ip3，ip4，時延delaysum，路由跳數routemum，地域觸發特征cityword，經過路由特征cityroute等8個特征的重要性如圖7所示。

由圖7可知，本文所定義的8個特征中，按重要性降序排列依次為經過路由特征cityroute，ip2，時延delaysum，ip3，ip1，ip4，路由跳數routemum和地域觸發特征cityword，這說明IP定位結果與運營商網絡拓撲、數據包傳輸時延和運營商分配IP的習慣關聯性更大。

圖7 特征重要性示意圖

而由圖6數據可知，本文所提出的基于隨機森林的IP地址定位方法，模型泛化能力好，且在城市級的定位中平均準確率可達99%以上，完全滿足實際應用中對于定位準確度的要求。

除此之外，實驗中還將使用基準點之外的一組IP，通過對比本文所提方法的定位結果，與主流IP定位工具的定位結果之間的重合率，進一步衡量本文所提方法的可信度和實用性。

在江蘇省內13個大市中每個城市隨機選擇電信IP進行測量（其中可追蹤到完整路由路徑和可追蹤到部分路由路徑的IP至少各一個），并使用本文所提算法進行了定位，其結果與主流IP定位工具的定位結果，在城市級上完全相同。部分結果如表3所示，由于IP自身的敏感性，因此對于選取IP的詳細信息進行了脫敏處理。由定位結果比對可知，在城市級定位上，本文所提方法的定位結果與主流IP定位工具的定位結果精確度一致。

因此，本文所提的基于隨機森林的IP地址定位方法在對IP進行城市級定位的需求下，定位準確度高，具有較高的可信度。

表3 定位結果對比

此外，本文所提出的基于隨機森林的IP地址城市級定位方法，其時間復雜度為O（M（mnlogn）），其中n為樣本數，m為特征數，M為決策樹棵數。進一步，通過對模型訓練時長和IP定位響應時長進行統計，可以得到，利用隨機森林算法對包含3994個樣本的數據集進行模型訓練平均耗時約2.32s，而根據輸入特征對單個IP進行城市級定位平均耗時約為0.06s。因此，本文所提的基于隨機森林的IP地址定位方法在對IP進行城市級定位的需求下，反應快耗時短，具有較高的實用性。

5 結語

針對傳統IP地址定位方法定位準確度差的缺陷，本文立足于江蘇省內真實的IP數據，提出了一種基于隨機森林的IP地址城市級定位方法。該方法旨在利用已有的IP地址數據，從IP本身具有的特點，以及IP之間存在的關系出發，創新性地定義了經過路由特征和地域觸發特征，后結合機器學習中分類的思想，利用隨機森林進行了模型訓練，從而實現了對IP所處城市的準確定位。

實驗結果表明，本文基于隨機森林算法訓練的分類模型準確率可達99%以上，并且基于該模型得到的定位結果與主流IP定位工具的定位結果一致。同時由于隨機森林算法具有模型訓練時間短且無需進行復雜調優的特點，本文所提方法實現IP城市級定位的響應時間可達毫秒級別，因此可高效適應定向廣告投放、網絡性能優化、社交網絡推薦、攻擊追蹤溯源等實際應用的需求。

總體而言，本文所提出的基于隨機森林的IP地址城市級定位方法準確率高，運行耗時少，但其定位精度僅到城市級別，因此本文下一步工作將致力于研究如何利用已有數據實現IP地址更高精度定位，如定位至區縣街道。