面向大型數(shù)據(jù)集的高效決策樹(shù)參數(shù)剪枝算法

謝兆賢，鄒興敏，張文靜

（曲阜師范大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，山東 曲阜 273165）

0 引言

在大數(shù)據(jù)時(shí)代，社會(huì)生產(chǎn)、生活方式與信息生態(tài)環(huán)境有著緊密的聯(lián)系，只有當(dāng)信息生態(tài)環(huán)境安全，人們的生活才會(huì)更有保障，但是近年來(lái)越來(lái)越多的網(wǎng)絡(luò)攻擊頻繁出現(xiàn)，網(wǎng)絡(luò)系統(tǒng)遭受著安全威脅，尤其是當(dāng)下更多新型的攻擊模式出現(xiàn)，所以在面對(duì)網(wǎng)絡(luò)攻擊的不確定性、多樣性的模式下，精準(zhǔn)快速地完成攻擊類(lèi)型識(shí)別是亟待解決的問(wèn)題。傳統(tǒng)網(wǎng)絡(luò)保護(hù)已經(jīng)不足以滿(mǎn)足現(xiàn)代的各種網(wǎng)絡(luò)攻擊模式，比如防火墻、入侵檢測(cè)技術(shù)。近年來(lái)，龔儉等［1］提出網(wǎng)絡(luò)安全態(tài)勢(shì)感知模型，基本要素是感知、理解和預(yù)測(cè)。網(wǎng)絡(luò)安全態(tài)勢(shì)感知模型的建立需要決策算法的支撐，即面對(duì)攻擊數(shù)據(jù)的來(lái)襲，采取相應(yīng)的措施分析數(shù)據(jù)并反饋給系統(tǒng)，以便系統(tǒng)對(duì)攻擊做出及時(shí)響應(yīng)。

決策樹(shù)的構(gòu)建模型簡(jiǎn)單，而且分類(lèi)準(zhǔn)確度相對(duì)較高，但是它的核心思想是貪心算法［2］，即一般只考慮局部最優(yōu)，做出當(dāng)前最好的選擇，因此存在過(guò)擬合和欠擬合的風(fēng)險(xiǎn)。目前，有關(guān)決策樹(shù)分類(lèi)的研究多數(shù)仍針對(duì)提升方法的分類(lèi)精度、算法效率或泛化性能。文獻(xiàn)［3］將進(jìn)化算法與決策樹(shù)后剪枝算法相結(jié)合，生成規(guī)模小的決策樹(shù)，它的重點(diǎn)是解決多樣化的決策樹(shù)過(guò)擬合問(wèn)題，但受進(jìn)化算法不穩(wěn)定的影響，該算法只在部分?jǐn)?shù)據(jù)集上處理過(guò)擬合得到了較好的效果，泛化性提升不明顯。一些研究在原有的剪枝算法上做改進(jìn)來(lái)減小過(guò)擬合程度。文獻(xiàn)［4］提出一種改進(jìn)的MEP 決策樹(shù)剪枝算法（IMEP），采用K-折交叉驗(yàn)證來(lái)選擇最優(yōu)的影響因子，但在選取最優(yōu)因子前要將訓(xùn)練集分為K個(gè)子集，然后再?gòu)闹羞x擇一部分作為驗(yàn)證集和訓(xùn)練集，在選取最優(yōu)因子時(shí)還得重復(fù)剪枝，增加了剪枝時(shí)間。文獻(xiàn)［5］提出一種改進(jìn)的后剪枝決策樹(shù)算法，綜合考慮分類(lèi)精度系數(shù)、分類(lèi)穩(wěn)定性系數(shù)、決策樹(shù)規(guī)模系數(shù)以及最優(yōu)樹(shù)評(píng)價(jià)標(biāo)準(zhǔn)4 個(gè)指標(biāo)，以便對(duì)決策樹(shù)進(jìn)行剪枝，但是需要額外獨(dú)立的剪枝集，增加了時(shí)間和空間的開(kāi)銷(xiāo)。文獻(xiàn)［6］提出決策樹(shù)算法的聯(lián)級(jí)網(wǎng)絡(luò)安全態(tài)勢(shì)感知模型，采用歸納算法預(yù)處理數(shù)據(jù)，按照決策規(guī)則生成決策樹(shù)，通過(guò)對(duì)目前常見(jiàn)的幾種攻擊進(jìn)行決策分類(lèi)，可以得到較好的加速比和規(guī)模比，但缺點(diǎn)是在大規(guī)模數(shù)據(jù)中很難保證決策樹(shù)分類(lèi)效果，同時(shí)未對(duì)決策樹(shù)的過(guò)擬合程度進(jìn)行校驗(yàn)和改進(jìn)。

文獻(xiàn)［7］提出一種綜合考慮提高分類(lèi)預(yù)測(cè)準(zhǔn)確率和減小決策樹(shù)生長(zhǎng)規(guī)模的決策樹(shù)剪枝算法，主要結(jié)合分類(lèi)錯(cuò)誤率與決策樹(shù)規(guī)模度形成一個(gè)新的參數(shù)，這里的剪枝是直接剪掉葉節(jié)點(diǎn)，讓其父節(jié)點(diǎn)成為新的葉節(jié)點(diǎn)，即使其分類(lèi)預(yù)測(cè)率提高和決策樹(shù)規(guī)模變小，由于直接剪掉葉節(jié)點(diǎn)可能無(wú)法決策出部分的樣本，因此有欠擬合的風(fēng)險(xiǎn)。文獻(xiàn)［8］采用二元粒子群優(yōu)化剪枝算法對(duì)決策樹(shù)（DT）進(jìn)行剪枝，此算法的缺點(diǎn)在于時(shí)間耗費(fèi)大，當(dāng)擬合程度提高時(shí)還要更新粒子的速度和位置向量，繼續(xù)下一個(gè)節(jié)點(diǎn)的剪枝。

為了降低計(jì)算成本，文獻(xiàn)［9］在卷積神經(jīng)網(wǎng)絡(luò)上采用濾波器剪枝算法，該剪枝算法的核心是采用不同的初始化策略來(lái)充分了解卷積層各個(gè)濾波器的重要權(quán)重，然后迭代修剪不重要的濾波器，但該剪枝性能完全受初始化策略的影響。文獻(xiàn)［10］提出在傳統(tǒng)決策樹(shù)的基礎(chǔ)上采用強(qiáng)化學(xué)習(xí)策略實(shí)現(xiàn)最優(yōu)特征選擇，其中將馬修斯相關(guān)系數(shù)與信息增益率相結(jié)合，作為選擇分類(lèi)的特征標(biāo)準(zhǔn)，以此提高非平衡數(shù)據(jù)集下少數(shù)樣本的預(yù)測(cè)精度，缺點(diǎn)是無(wú)法改善整體數(shù)據(jù)的泛化性。

針對(duì)決策樹(shù)分類(lèi)存在的時(shí)間復(fù)雜度高和模型過(guò)擬合問(wèn)題，本文提出面向大型數(shù)據(jù)集的高效決策樹(shù)參數(shù)剪枝算法，在網(wǎng)絡(luò)安全態(tài)勢(shì)感知模型的基礎(chǔ)上，對(duì)決策樹(shù)采用自上而下的參數(shù)尋優(yōu)方式，簡(jiǎn)稱(chēng)為參數(shù)剪枝（PAP）算法。

1 相關(guān)工作

近年來(lái)，許多領(lǐng)域?qū)Q策樹(shù)分類(lèi)算法應(yīng)用到實(shí)際生活中并取得了明顯進(jìn)步。文獻(xiàn)［11］根據(jù)報(bào)文的離散性特點(diǎn)，在決策樹(shù)生成過(guò)程中采用節(jié)點(diǎn)切割和規(guī)則集分組技術(shù)對(duì)報(bào)文進(jìn)行分類(lèi)。文獻(xiàn)［12］采用梯度提升決策樹(shù)（GBDT）算法，提升設(shè)計(jì)和分類(lèi)儲(chǔ)層質(zhì)量，首先是選擇一些特征值作為該地區(qū)的儲(chǔ)層評(píng)價(jià)標(biāo)準(zhǔn)，然后采用灰色相關(guān)法獲得儲(chǔ)層質(zhì)量的類(lèi)別，最后訓(xùn)練數(shù)據(jù)集。文獻(xiàn)［13］提出決策樹(shù)分類(lèi)的區(qū)塊鏈隱私保護(hù)數(shù)據(jù)挖掘算法，克服區(qū)塊鏈中隱私保護(hù)數(shù)據(jù)在挖掘過(guò)程中精度低、隱私保護(hù)數(shù)據(jù)噪聲高的問(wèn)題。文獻(xiàn)［14］為了改進(jìn)對(duì)抗攻擊的決策樹(shù)系統(tǒng)漏洞，開(kāi)發(fā)一種Adlo Tack 方法，首先開(kāi)發(fā)白盒算法形成具有隱藏功能的攻擊模式，然后對(duì)網(wǎng)絡(luò)發(fā)起預(yù)期攻擊，利用Adlo Tack 模型方法檢測(cè)物聯(lián)網(wǎng)設(shè)備上的所有非對(duì)抗性容量攻擊，發(fā)現(xiàn)在訓(xùn)練的決策樹(shù)集成模型下可檢測(cè)到92%的對(duì)抗性容量耗盡攻擊，效果較好。文獻(xiàn)［15］提出一種Shapley 值的特征歸因方法，用來(lái)解釋決策樹(shù)特征集合以及增強(qiáng)決策樹(shù)分類(lèi)性能，該方法可準(zhǔn)確反映模型預(yù)測(cè)算法的細(xì)節(jié)。

因?yàn)闆Q策樹(shù)的生成過(guò)程是透明的，所以會(huì)導(dǎo)致一些隱私數(shù)據(jù)泄露，文獻(xiàn)［16］采用IP 截?cái)嗟男藜舴椒▽?duì)決策樹(shù)進(jìn)行剪枝，既保證了隱私數(shù)據(jù)的隱蔽性，又降低了決策樹(shù)過(guò)擬合程度，但為了保護(hù)隱私數(shù)據(jù)，采取匿名化方案修剪真實(shí)IP 地址的分類(lèi)效果比原始模型差。

表1 對(duì)現(xiàn)有剪枝算法是否考慮決策樹(shù)規(guī)模、面向大型數(shù)據(jù)集、屬于后剪枝及具有信息增益等方面進(jìn)行歸納總結(jié)，其中，√表示具備該功能，×表示不具備該功能。由于現(xiàn)有剪枝算法多數(shù)沒(méi)有考慮數(shù)量集大小，但其實(shí)數(shù)量集大小也會(huì)對(duì)擬合程度有一定的影響，因此本文算法考慮了數(shù)據(jù)集大小的問(wèn)題，并將實(shí)驗(yàn)數(shù)據(jù)在10 000 條記錄以?xún)?nèi)設(shè)置為小數(shù)量集，超過(guò)10 000 條記錄設(shè)置為大型數(shù)據(jù)集。

表1 現(xiàn)有剪枝算法總結(jié)Table 1 Summary of existing pruning algorithms

2 符號(hào)與問(wèn)題定義

剪枝算法涉及的符號(hào)與定義如表2 所示。在面對(duì)大型數(shù)據(jù)集時(shí)，過(guò)擬合程度會(huì)增大，決策樹(shù)模型會(huì)更加不穩(wěn)定。表3 總結(jié)了決策樹(shù)擬合的3 種情況。本文對(duì)過(guò)擬合轉(zhuǎn)化為適度擬合的情況進(jìn)行研究。

表2 符號(hào)與定義Table 2 Symbols and definitions

表3 在大型數(shù)據(jù)集上的決策樹(shù)擬合情況Table 3 Decision tree fitting on large datasets

定義1特征回歸［17］也稱(chēng)為多特征線(xiàn)性回歸，即在實(shí)現(xiàn)某一類(lèi)型的分類(lèi)時(shí)，由多個(gè)特征共同決定，特征個(gè)數(shù)的選擇取決于線(xiàn)性回歸方程。

假設(shè)決策樹(shù)在創(chuàng)建時(shí)使用的特征數(shù)為xi，規(guī)定φ0和φi為決策樹(shù)模型參數(shù)，那么影響樣本分類(lèi)的線(xiàn)性回歸方程如式（1）所示：

當(dāng)提取的特征規(guī)則越多，決策樹(shù)模型的復(fù)雜度越高，并且可能會(huì)引起數(shù)據(jù)過(guò)擬合，影響分類(lèi)結(jié)果。

定義2網(wǎng)絡(luò)中的部分信息數(shù)據(jù)［7］隱性或顯性地反映數(shù)據(jù)特征，信息系統(tǒng)是真實(shí)對(duì)象集合的抽象表達(dá)形式。

信息系統(tǒng)K=(E,F,P)，其中，E={e1,e2,…,en}為非空有限對(duì)象集合，F(xiàn)={fi|i=1,2,…,k}為屬性集合，P={pi|i=1,2,…,k}，pi為對(duì)象屬性fi的值域，表示e?E在F上的投影，即fi：E→pi,fi(e) ?pi。信息系統(tǒng)K=(E,F,P)，若V?F、G?F，并且V∩G=?、V∪G=F，則稱(chēng)V為條件屬性集，G為決策屬性集，信息系統(tǒng)K為決策表，記為H=(E,V∪G,P)。在決策樹(shù)中，若葉節(jié)點(diǎn)l=(El,V∪G,P)，則當(dāng)|El/G|=1 時(shí)葉節(jié)點(diǎn)類(lèi)別為純，當(dāng)|El/G|>1 時(shí)葉節(jié)點(diǎn)類(lèi)別為不純。

定義3決策樹(shù)深度直接影響分類(lèi)準(zhǔn)確率和決策樹(shù)模型的復(fù)雜度。設(shè)函數(shù)f為剪枝判別函數(shù)，如式（2）所示：

其中：d是樹(shù)的深度，大于4 時(shí)會(huì)啟用PAP 算法；S1為初始準(zhǔn)確率；S2為剪枝后準(zhǔn)確率。當(dāng)剪枝后的準(zhǔn)確率大于剪枝前的準(zhǔn)確率時(shí)開(kāi)始剪枝。

3 系統(tǒng)架構(gòu)與剪枝算法

3.1 系統(tǒng)架構(gòu)

3.1.1 網(wǎng)絡(luò)安全態(tài)勢(shì)感知系統(tǒng)架構(gòu)

網(wǎng)絡(luò)技術(shù)的快速發(fā)展和對(duì)當(dāng)前網(wǎng)絡(luò)安全狀態(tài)感知的迫切需要，近年來(lái)很多學(xué)者［6，18-19］提出不同狀態(tài)下的網(wǎng)絡(luò)安全態(tài)勢(shì)感知模型，但無(wú)論何種狀態(tài)的態(tài)勢(shì)感知模型都是在網(wǎng)絡(luò)安全態(tài)勢(shì)感知的環(huán)境下實(shí)現(xiàn)，如圖1 所示，主要分為網(wǎng)絡(luò)安全數(shù)據(jù)源（感知層）、數(shù)據(jù)分析（理解層）和網(wǎng)絡(luò)安全態(tài)勢(shì)感知（預(yù)測(cè)層）3 個(gè)層次。

圖1 網(wǎng)絡(luò)安全態(tài)勢(shì)感知系統(tǒng)架構(gòu)Fig.1 Architecture of network security situational awareness system

1）網(wǎng)絡(luò)安全數(shù)據(jù)源。網(wǎng)絡(luò)安全數(shù)據(jù)源來(lái)自網(wǎng)絡(luò)設(shè)備和計(jì)算機(jī)系統(tǒng)，提煉為網(wǎng)絡(luò)安全數(shù)據(jù)，這一層次稱(chēng)為感知層。

2）數(shù)據(jù)分析。將采集到的多元異構(gòu)數(shù)據(jù)進(jìn)行清洗和歸一化后，采用統(tǒng)一格式進(jìn)行存儲(chǔ)和管理，通過(guò)相關(guān)算法挖掘數(shù)據(jù)之間的相關(guān)性，這一層次稱(chēng)為數(shù)據(jù)的理解層。

3）網(wǎng)絡(luò)安全態(tài)勢(shì)感知。根據(jù)數(shù)據(jù)分析結(jié)果，計(jì)算當(dāng)前網(wǎng)絡(luò)安全態(tài)勢(shì)值，并且進(jìn)行網(wǎng)絡(luò)態(tài)勢(shì)的評(píng)估。此外，網(wǎng)絡(luò)威脅評(píng)估是估計(jì)惡意攻擊的破壞能力和網(wǎng)絡(luò)威脅的程度。網(wǎng)絡(luò)態(tài)勢(shì)預(yù)測(cè)是通過(guò)已知的數(shù)據(jù)推演分析將要發(fā)生的安全事件以及預(yù)測(cè)安全威脅事件發(fā)生的概率，這一層次稱(chēng)為預(yù)測(cè)層。

在以上3 個(gè)層次中理解層最為重要，它既要確保從感知層獲得各類(lèi)異常攻擊數(shù)據(jù)集，又要精準(zhǔn)反映當(dāng)前網(wǎng)絡(luò)攻擊的狀態(tài)。

3.1.2 決策樹(shù)剪枝的網(wǎng)絡(luò)安全態(tài)勢(shì)感知系統(tǒng)架構(gòu)

特征回歸可以在決策樹(shù)生成前期減小過(guò)擬合程度，但是參與構(gòu)建決策樹(shù)的特征越多，決策樹(shù)生長(zhǎng)得復(fù)雜度越高，此時(shí)也可能會(huì)導(dǎo)致過(guò)擬合，所以建立簡(jiǎn)易模型的參數(shù)剪枝來(lái)降低其復(fù)雜度。同時(shí)，一個(gè)最優(yōu)參數(shù)的獨(dú)立模型不能保證整體的分類(lèi)性能，而只有集結(jié)多個(gè)這樣的最優(yōu)參數(shù)才能提升決策樹(shù)的全局分類(lèi)性能，最重要的3 個(gè)參數(shù)為決策樹(shù)最大深度（dmax）、最小樣本分裂數(shù)（smin）和最大特征數(shù)（fmax）。

圖2 為剪枝決策樹(shù)態(tài)勢(shì)感知系統(tǒng)架構(gòu)，主要分成4 個(gè)部分：第1 個(gè)部分為態(tài)勢(shì)感知系統(tǒng)的網(wǎng)絡(luò)安全數(shù)據(jù)源，主要對(duì)來(lái)自傳感器的數(shù)據(jù)流進(jìn)行整合，匯總成一個(gè)大的csv 文件數(shù)據(jù)；第2 個(gè)部分屬于數(shù)據(jù)分析層，主要包括數(shù)據(jù)清洗、數(shù)據(jù)平衡處理及提取特征建立決策樹(shù)；第3 個(gè)部分為參數(shù)剪枝流程，在建成的決策樹(shù)基礎(chǔ)上進(jìn)行參數(shù)剪枝處理；第4 個(gè)部分屬于態(tài)勢(shì)感知層。

3.2 剪枝算法

3.2.1 后剪枝算法

常用的3 種剪枝算法為最小誤差剪枝（MEP）、降低錯(cuò)誤剪枝（REP）和悲觀錯(cuò)誤剪枝（PEP），它們都屬于后剪枝算法。最小誤差剪枝算法首先計(jì)算該節(jié)點(diǎn)的誤差Er(t)；然后計(jì)算該節(jié)點(diǎn)每個(gè)分支的誤差Er(Tt)進(jìn)行加權(quán)相加，權(quán)重為每個(gè)分支擁有的訓(xùn)練樣本比例；最后比較Er(t)和Er(Tt)，若Er(t)>Er(Tt)，則保留該子樹(shù)，否則對(duì)其進(jìn)行裁剪。Er(t)計(jì)算如式（3）所示：

其中：k為樣本種類(lèi)的數(shù)目。

算法1MEP 算法［5］

降低錯(cuò)誤剪枝算法是將數(shù)據(jù)分為訓(xùn)練集和驗(yàn)證集。訓(xùn)練集用來(lái)訓(xùn)練決策樹(shù)模型，驗(yàn)證集用來(lái)糾正樹(shù)過(guò)擬合問(wèn)題。算法步驟具體為：1）構(gòu)建兩棵決策樹(shù)，一棵是普通的決策樹(shù)，另一棵是自下而上將決策樹(shù)的每一個(gè)非葉子節(jié)點(diǎn)替換為葉子節(jié)點(diǎn)的剪枝決策樹(shù)；2）通過(guò)驗(yàn)證集來(lái)驗(yàn)證這兩棵決策樹(shù)的準(zhǔn)確率，從而判斷該樹(shù)是否剪枝，首先計(jì)算未剪枝前節(jié)點(diǎn)t誤差Er(t)，然后計(jì)算剪枝后該節(jié)點(diǎn)誤差Er(Tt)，若滿(mǎn)足式（4），則保留該子樹(shù)，否則對(duì)其進(jìn)行裁剪。

算法2REP 算法［5］

悲觀錯(cuò)誤剪枝算法引入統(tǒng)計(jì)學(xué)上連續(xù)修正的概念來(lái)彌補(bǔ)REP 算法中的缺陷，在子樹(shù)的誤判公式中添加一個(gè)常數(shù)，即懲罰因子。設(shè)定數(shù)值為0.5，是為了解決每次訓(xùn)練決策樹(shù)采用相同的訓(xùn)練樣本時(shí)每個(gè)節(jié)點(diǎn)剪枝后錯(cuò)分率上升的問(wèn)題。由于樹(shù)是自底向上生成，因此一個(gè)葉子節(jié)點(diǎn)覆蓋N個(gè)樣本，假設(shè)有E個(gè)錯(cuò)誤，則該葉子節(jié)點(diǎn)的誤差為。將其推廣到一整棵決策樹(shù)時(shí)，它有L個(gè)葉子節(jié)點(diǎn)，該子樹(shù)的誤判率如式（5）所示：

其中：Ni是該節(jié)點(diǎn)的樣本個(gè)數(shù)；Ei是該節(jié)點(diǎn)的錯(cuò)誤個(gè)數(shù)。因?yàn)榧糁蟮恼`判率et為，所以葉子節(jié)點(diǎn)的誤判均值、剪枝前的誤判均值、誤判標(biāo)準(zhǔn)差、剪枝條件分別如式（6）、式（7）、式（8）、式（9）所示。若不滿(mǎn)足式（9），則不進(jìn)行剪枝。

算法3PEP 算法［5］

以上剪枝算法雖然采取的剪枝策略不同，但都具有以下3 個(gè)特點(diǎn)：1）除訓(xùn)練集外還需額外的剪枝集；2）剪枝前需先定義決策樹(shù)剪枝標(biāo)準(zhǔn)；3）能夠訪(fǎng)問(wèn)決策樹(shù)的各個(gè)節(jié)點(diǎn)。表4 為3 種算法的剪枝方式比較。PEP 算法采用概率剪枝，精度比REP 和MEP高［5］，但是面對(duì)大型數(shù)據(jù)集時(shí)，PEP 算法在計(jì)算量大時(shí)容易產(chǎn)生不可避免的誤差，同時(shí)通過(guò)自上而下的剪枝方式，容易產(chǎn)生和預(yù)剪枝一樣的視野效應(yīng)。REP 算法雖然簡(jiǎn)單，仍需要訓(xùn)練集以外的剪枝集協(xié)助，在產(chǎn)生與處理兩棵決策樹(shù)的過(guò)程中，時(shí)間與空間需求都會(huì)增加，不利于整體效能。

表4 3 種算法的剪枝方式比較Table 4 Comparison of pruning methods for three algorithms

3.2.2 預(yù)剪枝算法

預(yù)剪枝是指在決策樹(shù)還未生成完畢時(shí)，通過(guò)某種判定方法提前停止決策樹(shù)的生長(zhǎng)。文獻(xiàn)［20］將預(yù)剪枝算法用于序列模式挖掘，在序列較多和序列長(zhǎng)度相似的數(shù)據(jù)集上通過(guò)預(yù)剪枝策略減少運(yùn)行時(shí)間。

考慮在樹(shù)節(jié)點(diǎn)進(jìn)行拓展分支前，利用相關(guān)算法計(jì)算當(dāng)前的劃分是否能帶來(lái)決策樹(shù)泛化能力的提升，若不能則停止樹(shù)的生長(zhǎng)。預(yù)剪枝通常有3 種方式，具體為限定決策樹(shù)的深度、設(shè)定閾值和設(shè)置指標(biāo)，指標(biāo)用于比較節(jié)點(diǎn)劃分前后的泛化能力。本文采用設(shè)定閾值的方式。

設(shè)定閾值實(shí)現(xiàn)預(yù)剪枝主要是在決策樹(shù)進(jìn)行特征選擇時(shí)將信息增益與閾值進(jìn)行比較，決策樹(shù)采取何種剪枝算法主要取決于閾值大小。

算法4預(yù)剪枝算法［5］

3.2.3 網(wǎng)絡(luò)搜索

網(wǎng)絡(luò)搜索利用Sklearn 庫(kù)中的GridSearchCV 窮舉法進(jìn)行，將訓(xùn)練集分為n份，其中，n-1 份作為訓(xùn)練集，1 份作為驗(yàn)證集。通過(guò)交叉驗(yàn)證優(yōu)化估計(jì)函數(shù)的參數(shù)得到最優(yōu)模型，具體為：首先從候選參數(shù)集合中選出一系列參數(shù)，組合后得到一個(gè)候選參數(shù)列表；然后根據(jù)數(shù)據(jù)特征與規(guī)模，遍歷參數(shù)列表，在n次訓(xùn)練后計(jì)算得出各參數(shù)組合的模型分?jǐn)?shù)，即準(zhǔn)確率；最后返回得分最高的一組參數(shù)，構(gòu)造分類(lèi)器。

算法5Grid SearchCV 算法［21］

輸入訓(xùn)練集T1

輸出模型得分最高的參數(shù)組合m

1.劃分參數(shù)范圍

2.從T1-1 份訓(xùn)練集中進(jìn)行網(wǎng)絡(luò)搜索

3.新建決策樹(shù)模型

4.交叉驗(yàn)證，返回模型得分最高的參數(shù)組合m

3.3 PAP 算法

PAP 算法結(jié)合枚舉與二分搜索算法確定樹(shù)的深度范圍，然后自上而下深度遍歷決策樹(shù)各節(jié)點(diǎn)最小樣本分裂數(shù)和最大特征數(shù)。在生成決策樹(shù)后，枚舉決策樹(shù)深度集合D。集合D的特點(diǎn)是每個(gè)元素都是隨機(jī)數(shù)n的倍數(shù)，而且是正序排列，目的在于使用二分查找最優(yōu)深度dk，并記錄此時(shí)的準(zhǔn)確率S1，然后采用樹(shù)的深度優(yōu)先搜索從根節(jié)點(diǎn)遍歷至dk+1深度，即在第k個(gè)節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)處，記錄該層最小樣本分裂數(shù)mk和最大特征數(shù)pk，建立正序排列集合M、P。在集合M、P中元素的中位數(shù)為mk、pk，各個(gè)元素是隨機(jī)數(shù)q的倍數(shù)，集合M中元素最大值不超過(guò)父節(jié)點(diǎn)最小分裂樣本數(shù)，集合P中元素最大值不超過(guò)所有樣本的特征數(shù)。調(diào)用二分搜索算法在集合M、P中尋得最優(yōu)值，考慮深度優(yōu)先搜索與二分搜索算法的特性，調(diào)用次數(shù)不超過(guò)k次，找到的最優(yōu)值記為最終將參數(shù)dk、′輸入模型，記錄準(zhǔn)確率S2。若S1

圖3 PAP 算法流程Fig.3 Procedure of PAP algorithm

算法6PAP 算法

4 實(shí)驗(yàn)過(guò)程

在數(shù)量不同的訓(xùn)練集和測(cè)試集上檢測(cè)算法過(guò)擬合程度，在實(shí)驗(yàn)過(guò)程中選取較大的數(shù)據(jù)集驗(yàn)證實(shí)驗(yàn)準(zhǔn)確性，同時(shí)比較同一數(shù)量集下預(yù)剪枝、后剪枝與PAP 算法的擬合程度，然后與MEP、REP 和PEP 算法在時(shí)間和空間性能上進(jìn)行比對(duì)。

在平衡數(shù)據(jù)集后仍有約160 萬(wàn)條數(shù)據(jù)，在實(shí)驗(yàn)中剪枝過(guò)程按比例選取數(shù)據(jù)，隨著參數(shù)的不斷優(yōu)化，選取更大比例的數(shù)據(jù)。最優(yōu)參數(shù)的初始值dmax設(shè)為None，不限制決策樹(shù)的生長(zhǎng)；smin預(yù)設(shè)為2，至少有兩個(gè)樣本時(shí)才會(huì)分裂此節(jié)點(diǎn)；fmax初始值設(shè)為None，因?yàn)樾枰獩Q策的樣本類(lèi)有15 個(gè)，其中網(wǎng)絡(luò)數(shù)據(jù)流的特征非常多，所以需要根據(jù)建立的模型進(jìn)行數(shù)據(jù)特征的提取，然后利用PAP 算法找到最優(yōu)dmax、smin和fmax。

4.1 實(shí)驗(yàn)數(shù)據(jù)

在實(shí)驗(yàn)中采用CIC-IDS2017 數(shù)據(jù)集，其中攻擊數(shù)據(jù)集的種類(lèi)與目前實(shí)際的攻擊類(lèi)型相近。

4.2 實(shí)驗(yàn)環(huán)境

硬件環(huán)境：采用Intel 平臺(tái)、CPU 主頻2.3 GHz、內(nèi)存15 GB、x64 的處理器；軟件環(huán)境：在PyCharm 2020.2下運(yùn)行。

4.3 數(shù)據(jù)清洗與重采樣

數(shù)據(jù)分析的第一步是數(shù)據(jù)清洗［22］，需要理解數(shù)據(jù)的列、行、記錄、數(shù)據(jù)格式、語(yǔ)義錯(cuò)誤、缺失條目以及一些錯(cuò)誤格式，對(duì)數(shù)據(jù)清洗采取奇異閾值法［23］，實(shí)驗(yàn)中直接將臟數(shù)據(jù)剔除。

因?yàn)槭占降臄?shù)據(jù)集相當(dāng)不平衡，正常數(shù)據(jù)非常多，但是檢測(cè)出的攻擊流量非常少，不利于攻擊型數(shù)據(jù)的分析和分類(lèi)，實(shí)驗(yàn)根據(jù)攻擊類(lèi)型的特征決策真實(shí)的分類(lèi)效果，因此必須對(duì)數(shù)據(jù)進(jìn)行重采樣處理。圖4 顯示了數(shù)據(jù)平衡處理情況（彩色效果見(jiàn)《計(jì)算機(jī)工程》官網(wǎng)HTML 版，下同），其中折線(xiàn)為平衡數(shù)據(jù)前后的落差趨勢(shì)。

圖4 數(shù)據(jù)平衡前后對(duì)比Fig.4 Comparison before and after data balance

重采樣使用SMOTE［24-25］算法生成新數(shù)據(jù)。SMOTE 算法模型顯示數(shù)量小的樣本以歐式距離（如圖5 中矩形框所示）為標(biāo)準(zhǔn)進(jìn)行重采樣，添加到新的數(shù)據(jù)集中，算法步驟具體如下：

圖5 SMOTE 算法模型Fig.5 Model of SMOTE algorithm

步驟1計(jì)算樣本的合成量。將BENIGN、DoS Hulk、PortScan、DDoS 類(lèi)記為多數(shù)類(lèi)樣本，用x表示，將Bot、Web Attack、Brute Force、Web Attack XSS、Infiltration、Web Attack Sql、Injection、Heartbleed 記為少數(shù)類(lèi)樣本，用y表示，α為[0,1]中的隨機(jī)數(shù)。樣本的合成量計(jì)算如式（10）所示：

步驟2計(jì)算K 近鄰中多數(shù)類(lèi)樣本占比。Δi為K近鄰中的多數(shù)類(lèi)樣本數(shù)，其中i?[1,y]，多數(shù)樣本占比如式（11）所示：

步驟3對(duì)Ri進(jìn)行標(biāo)準(zhǔn)化，如式（12）所示：

步驟4計(jì)算少數(shù)類(lèi)樣本所增添的數(shù)量。根據(jù)式（12）的樣本權(quán)重，計(jì)算每一類(lèi)少數(shù)類(lèi)樣本需要新增添的樣本數(shù)目，如式（13）所示：

步驟5生成新樣本。根據(jù)SMOTE 算法生成樣本，如式（14）所示：

其中：Snew表示最終的合成樣本；yi是少數(shù)類(lèi)樣本中的第i個(gè)；yki是yi的K 近鄰中隨機(jī)選取的一個(gè)少數(shù)類(lèi)樣本；β為［0，1］中的隨機(jī)數(shù)。

4.4 數(shù)據(jù)集分析

對(duì)平衡數(shù)據(jù)集進(jìn)行分析，由于CIC-IDS2017 數(shù)據(jù)集有78 個(gè)特征標(biāo)簽，如果將這些標(biāo)簽全都用于構(gòu)建決策樹(shù)，則時(shí)間和空間的需求會(huì)變大，因此為了提高整體效能，對(duì)海量數(shù)據(jù)集進(jìn)行特征提取。

在眾多特征中選取最合適的特征作為建立決策樹(shù)的標(biāo)準(zhǔn)，引入信息增益。目前，最常見(jiàn)的攻擊類(lèi)型有拒絕服務(wù)攻擊、分布式拒絕服務(wù)攻擊、Web 服務(wù)攻擊、端口掃描攻擊、暴力SSH 攻擊、暴力FTP 攻擊、Heartbleed 漏洞攻擊、僵尸網(wǎng)絡(luò)攻擊、滲透攻擊等。依據(jù)實(shí)驗(yàn)環(huán)境中攻擊方式的不同類(lèi)別，再將其細(xì)分為PortScan、DDos、Dos Hulk 等14 類(lèi)樣本，對(duì)從網(wǎng)絡(luò)流上獲取到的數(shù)據(jù)進(jìn)行劃分，隨機(jī)將數(shù)據(jù)劃分為訓(xùn)練集和測(cè)試集，記訓(xùn)練集中的特征為M，它有k種取值情況，樣本純度計(jì)算如式（15）所示：

通過(guò)式（15）得到某一特征的期望信息量，然后逐一對(duì)提取的樣本特征進(jìn)行預(yù)測(cè)。記樣本特征集合為P，特征M、N?P，由于不同特征的樣本純度值不同，因此式（16）對(duì)特征N取值可以得到特征M的熵，以此判定是否選取該特征。

通過(guò)式（15）減去式（16）的結(jié)果差得到特征分式（17）。若得分越高，則越會(huì)被保留下來(lái)，保留下來(lái)的特征記為Mi，作為構(gòu)建決策樹(shù)的重要特征，其他的特征被丟棄。圖6 給出提取特征時(shí)DoS 和Web 攻擊下信息熵最大的前3 個(gè)特征，其中主要影響DoS 攻擊的是信息流到達(dá)的時(shí)間和信息流持續(xù)的時(shí)間，主要影響Web 攻擊的是初始窗口字節(jié)數(shù)、轉(zhuǎn)發(fā)子流字節(jié)數(shù)和轉(zhuǎn)發(fā)數(shù)據(jù)包的長(zhǎng)度。

圖6 樣本信息增益Fig.6 Sample information gain

在面對(duì)大型數(shù)據(jù)集時(shí)，提取數(shù)據(jù)樣本特征可以對(duì)數(shù)據(jù)進(jìn)行降維處理，以此簡(jiǎn)化模型，進(jìn)而提高數(shù)據(jù)分析效率。因此，選擇合適參數(shù)的遍歷數(shù)據(jù)可以提升剪枝速度。

5 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)主要對(duì)以下3 個(gè)方面進(jìn)行驗(yàn)證：1）PAP 剪枝準(zhǔn)確率較高；2）當(dāng)數(shù)據(jù)量逐漸增大時(shí)，決策樹(shù)擬合程度較好；3）在面對(duì)大型數(shù)據(jù)集時(shí)，PAP 剪枝時(shí)間比后剪枝算法短。

當(dāng)γ=0.03 時(shí)，在未找到最優(yōu)參數(shù)時(shí)，訓(xùn)練集和測(cè)試集擬合程度如圖7 所示。由圖7 可以看出，前期的擬合程度比較好，隨著決策樹(shù)深度的增加，過(guò)擬合程度逐漸增大，在決策樹(shù)深度約為25 時(shí)，準(zhǔn)確率開(kāi)始下降。二分搜索算法考慮深度小于25 時(shí)的模型準(zhǔn)確率，枚舉函數(shù)將決策樹(shù)深度從5 枚舉至25得到模型的準(zhǔn)確率。由圖8 可以看出，在最優(yōu)深度為19 時(shí)，模型準(zhǔn)確率最高，找到最優(yōu)參數(shù)dmax為19。然后深度優(yōu)先搜索查找smin、fmax的最優(yōu)值，如圖9 所示。程序輸出smin取17、fmax取9 時(shí)準(zhǔn)確率最高。此時(shí)得到3 個(gè)最優(yōu)參數(shù)值，將其代入模型觀察準(zhǔn)確率，如圖10 所示，可以看出相比于圖7 的訓(xùn)練集和測(cè)試集的擬合程度，通過(guò)最優(yōu)參數(shù)剪枝后的過(guò)擬合程度減小。

圖7 未剪枝前模型擬合程度Fig.7 Fitting degree of the model before pruning

圖8 最優(yōu)深度下的訓(xùn)練集準(zhǔn)確率Fig.8 Accuracy of training set under the optimal depth

圖9 最小分裂樣本數(shù)和最大特征數(shù)下的準(zhǔn)確率Fig.9 Accuracy under the minimum split sample number and maximum feature number

圖10 最優(yōu)參數(shù)下的擬合情況Fig.10 Fitting situation under the optimal parameters

通過(guò)改變實(shí)驗(yàn)訓(xùn)練集和驗(yàn)證集的數(shù)據(jù)，即改變?chǔ)胕的值，取得隨機(jī)不等量的數(shù)據(jù)集，其中，i取1、2、3、4、5，γi的取值依次為0.03、0.05、0.08、0.20、0.80。表5 展示了訓(xùn)練集和測(cè)試集在參數(shù)剪枝后的準(zhǔn)確率。由表5可以看出，兩者準(zhǔn)確率都在95%以上，擬合程度較好，不會(huì)隨著實(shí)驗(yàn)數(shù)據(jù)量的增大出現(xiàn)過(guò)擬合程度增大的現(xiàn)象。但是網(wǎng)絡(luò)搜索算法只在3 000 條數(shù)據(jù)內(nèi)才可以搜索到最優(yōu)參數(shù)，不適用于大型數(shù)據(jù)集。

表5 不同γi 下訓(xùn)練集和測(cè)試集的準(zhǔn)確率Table 5 Accuracy of the training and testing set under different γi

取γ3即參與實(shí)驗(yàn)的數(shù)據(jù)為總數(shù)據(jù)的0.08 倍時(shí)，由實(shí)驗(yàn)得出閾值的預(yù)剪枝、PEP 與PAP 的擬合程度，如圖11 所示。由圖11 可以看出，在面向大型數(shù)據(jù)集時(shí)，PAP 算法的剪枝效果更好。

圖11 3 種剪枝算法的擬合程度Fig.11 Fitting degree of three pruning algorithms

隨著γi數(shù)值增大，在實(shí)驗(yàn)過(guò)程中將PAP 與3 種后剪枝算法進(jìn)行性能對(duì)比，如表6 所示，當(dāng)運(yùn)行數(shù)據(jù)最少約6 000 條記錄時(shí)，γi=0.03，此時(shí)不考慮數(shù)據(jù)集大小對(duì)MEP 算法精度的影響。通過(guò)表6 可以看出PAP的準(zhǔn)確率最高，同時(shí)當(dāng)數(shù)量集規(guī)模增大到一定程度時(shí)，3 種后剪枝算法都很難完成剪枝。

表6 4 種剪枝算法在不同數(shù)據(jù)集下的準(zhǔn)確率Table 6 Accuracy of four pruning algorithms under different datasets

表7 給出了PEP 與PAP 算法在不同數(shù)據(jù)量下耗費(fèi)的時(shí)間，可見(jiàn)PAP 算法的剪枝時(shí)間遠(yuǎn)長(zhǎng)于MEP 算法的剪枝時(shí)間。

表7 不同數(shù)據(jù)集下剪枝算法所耗費(fèi)時(shí)間Table 7 Time consumption by pruning algorithms with different datasets

6 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)決策樹(shù)剪枝算法分類(lèi)準(zhǔn)確率低、時(shí)間復(fù)雜度高、在處理大型數(shù)據(jù)集時(shí)過(guò)擬合程度明顯等問(wèn)題，提出一種面向大型數(shù)據(jù)集的高效決策樹(shù)參數(shù)剪枝算法，對(duì)決策樹(shù)采取自上而下的最優(yōu)參數(shù)剪枝降低決策樹(shù)過(guò)擬合風(fēng)險(xiǎn)，提高泛化能力，并且能在大型數(shù)據(jù)集下快速準(zhǔn)確地找到最優(yōu)參數(shù)，完成剪枝。實(shí)驗(yàn)結(jié)果表明，該算法不需要?jiǎng)澐謫为?dú)的剪枝集，能減小空間能耗，加快剪枝時(shí)間。下一步將繼續(xù)改進(jìn)所提算法，使其既能對(duì)小型數(shù)據(jù)集進(jìn)行決策處理，又能在大型數(shù)據(jù)集上表現(xiàn)良好，同時(shí)設(shè)計(jì)新的枚舉算法，分析決策樹(shù)特征，確定枚舉范圍，進(jìn)一步降低時(shí)間復(fù)雜度。