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

蔡 穎 張 琨 尹魏昕 張?jiān)萍?蔣彤彤 方 悅

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

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

1 引言

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

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

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

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

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

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

2.1 主動(dòng)測(cè)量

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

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

圖1 主動(dòng)測(cè)量示例

測(cè)量點(diǎn)向基準(zhǔn)點(diǎn)發(fā)起TraceRoute命令，每一跳返回結(jié)果包括5項(xiàng)，表示為

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

測(cè)量中每次探測(cè)3次，若測(cè)量中第i跳的時(shí)延以delayi表示，則有：

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

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

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

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

經(jīng)過上述處理后，得到測(cè)量點(diǎn)到基準(zhǔn)點(diǎn)的主動(dòng)測(cè)量數(shù)據(jù)為

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

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

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

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

2.2 特征提取

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

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

此外，考慮到運(yùn)營(yíng)商網(wǎng)絡(luò)的拓?fù)湟约坝脩舻脑L問行為，本文將對(duì)經(jīng)過路由特征和地域觸發(fā)特征分別進(jìn)行定義，并加入到分類特征中去。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于隨機(jī)森林的IP地址定位方法

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

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

3.1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

Input：數(shù)據(jù)集D，決策樹數(shù)目n_estimators，單棵樹樣本數(shù)n_samples，特征選擇標(biāo)準(zhǔn)criterion，特征總數(shù)F，特征選擇個(gè)數(shù)max_features，待測(cè)點(diǎn)的特征xpre

Output：待測(cè)點(diǎn)的城市級(jí)定位結(jié)果ypre

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

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

S3：針對(duì)每個(gè)樣本集，隨機(jī)抽取max_features（max_feature＜F）個(gè)特征作為決策樹的分類特征，并采用criterion為標(biāo)準(zhǔn)在每個(gè)節(jié)點(diǎn)上選取特征分裂，直到節(jié)點(diǎn)不可分為止

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

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

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

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

3.2 模型優(yōu)化

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

圖3 數(shù)據(jù)庫(kù)中存儲(chǔ)的部分測(cè)量數(shù)據(jù)

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

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

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

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

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

圖5 測(cè)試集準(zhǔn)確率隨參數(shù)變化示意圖

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

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

4.3 結(jié)果及分析

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

圖6 算法模型性能

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

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

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

圖7 特征重要性示意圖

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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