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

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

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

（2.國家計算機網(wǎng)絡(luò)與信息安全管理中心江蘇分中心 南京 210019）

1 引言

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

IP地址定位即根據(jù)網(wǎng)絡(luò)設(shè)備的IP確定其在地理上的位置。在研究中，將具有IP的網(wǎng)絡(luò)設(shè)備劃分為測量點、基準點和待測點三類，其中測量點是指能向目的IP發(fā)起主動測量的網(wǎng)絡(luò)設(shè)備，基準點是指地理位置已知且可對測量點所發(fā)數(shù)據(jù)包做出響應(yīng)的網(wǎng)絡(luò)設(shè)備，而待測點則是指需要實現(xiàn)地理位置定位的IP即待定位的網(wǎng)絡(luò)設(shè)備［5］。

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

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

2 數(shù)據(jù)的獲取與處理

由于電信、移動、聯(lián)通等運營商之間的網(wǎng)絡(luò)建設(shè)是相互獨立的，因此為減少此類情況對分類器構(gòu)建可能產(chǎn)生的負面影響，應(yīng)對IP根據(jù)其所屬運營商不同進行分類，并在同一類別下選擇基準點，進而發(fā)起測量并記錄相關(guān)數(shù)據(jù)。

2.1 主動測量

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

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

圖1 主動測量示例

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

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

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

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

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

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

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

經(jīng)過上述處理后，得到測量點到基準點的主動測量數(shù)據(jù)為

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

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

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

此外，在進行測量的過程中，得到的測量結(jié)果將由程序自動保存至數(shù)據(jù)庫中進行存儲。而為進一步訓(xùn)練分類器，還需要對數(shù)據(jù)進行預(yù)處理并構(gòu)建標準的數(shù)據(jù)集。

2.2 特征提取

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

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

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

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

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

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

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

進一步，判斷測量點至基準點的路由路徑是否經(jīng)過某城市的骨干路由，即是否包含該城市骨干網(wǎng)節(jié)點對應(yīng)網(wǎng)段下的IP，即：

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

表1 江蘇省內(nèi)城市代碼映射表

定義2.地域觸發(fā)特征。定義地域觸發(fā)特征為基準點發(fā)送的數(shù)據(jù)包中，包含的關(guān)鍵詞所映射的城市，以cityword表示。

基于已有且真實的省內(nèi)IP間傳輸?shù)臄?shù)據(jù)包信息，對基準點發(fā)送的數(shù)據(jù)包，提取其中與二級及三級行政區(qū)相關(guān)的關(guān)鍵詞，并統(tǒng)計其出現(xiàn)次數(shù)，即將一個基準點發(fā)送的所有數(shù)據(jù)包處理為

式中，＜c，count＞表示一個元組，c為城市代碼，count為該城市對應(yīng)關(guān)鍵詞出現(xiàn)次數(shù)。將最大count所對應(yīng)的城市代碼，作為該基準點cityword的值，即：

其中，c→count表示元組內(nèi)城市代碼和關(guān)鍵詞出現(xiàn)次數(shù)的映射關(guān)系，表示count不為0時，最大count所對應(yīng)的城市代碼，城市代碼如表1所示，城市相關(guān)關(guān)鍵詞如表2所示。

2.3 構(gòu)建數(shù)據(jù)集

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

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

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

表2 城市相關(guān)關(guān)鍵詞

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

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

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

3.1 算法描述

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

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

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

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

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

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

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

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

圖2 模型訓(xùn)練示意圖

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

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

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

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

Output：待測點的城市級定位結(jié)果ypre

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

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

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

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

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

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

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

3.2 模型優(yōu)化

隨機森林的優(yōu)化主要有特征選擇和參數(shù)優(yōu)化兩個策略。本文所提算法在第2節(jié)中創(chuàng)新性地對經(jīng)過路由特征和地域觸發(fā)特征進行了定義，優(yōu)化了特征。而此處將進一步對模型的參數(shù)進行優(yōu)化。

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

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

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

4 實驗驗證

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

4.1 數(shù)據(jù)描述

本文實驗數(shù)據(jù)來源于南京理工大學(xué)與國家計算機網(wǎng)絡(luò)與信息安全管理中心江蘇分中心聯(lián)合建立的江蘇省研究生工作站。實驗部分以南京某IP為測量點，對江蘇省內(nèi)共3994個基準點發(fā)起了主動測量，其部分數(shù)據(jù)庫表信息如圖3所示。

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

圖3 數(shù)據(jù)庫中存儲的部分測量數(shù)據(jù)

圖4 數(shù)據(jù)集組成

4.2 參數(shù)優(yōu)化

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

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

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

圖5 測試集準確率隨參數(shù)變化示意圖

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

綜上，經(jīng)過參數(shù)優(yōu)化后，本文實驗將在n_esti?mators=500和max_features=3的前提下進行。

4.3 結(jié)果及分析

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

圖6 算法模型性能

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

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

由圖7可知，本文所定義的8個特征中，按重要性降序排列依次為經(jīng)過路由特征cityroute，ip2，時延delaysum，ip3，ip1，ip4，路由跳數(shù)routemum和地域觸發(fā)特征cityword，這說明IP定位結(jié)果與運營商網(wǎng)絡(luò)拓撲、數(shù)據(jù)包傳輸時延和運營商分配IP的習(xí)慣關(guān)聯(lián)性更大。

圖7 特征重要性示意圖

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

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

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

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

表3 定位結(jié)果對比

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

5 結(jié)語

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

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

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