基于改進隨機森林算法的防火墻日志異常檢測并行化方法

劉 成，王佳斌，洪繼煒

（華僑大學工學院，泉州 362021）

0 引言

在現今的大數據時代，網絡在人們生活中不可或缺。隨著互聯網的用戶量和規模不斷增長，網絡流量也呈現出井噴式的增長，網絡安全問題也變得越值得重視，如何保障網民的合法利益也變得越來越重要。因此，如何對大規模的網絡流量進行異常檢測并分類，是非常值得研究的課題。

近年來，許多國內外學者開始使用機器學習的方法來解決網絡入侵流量異常檢測和分類情景中所面臨的問題［1］。Erman 等［2］提出使用K-means 算法對單向流信息進行分類。Moore 等［3］改進了用于網絡流分類的傳統樸素貝葉斯算法，但該算法需要穩定的數據集，不適用于高速和不穩定的網絡。雍凱［4］提出了決策樹屬性的權重評估，生成決策樹時，通過優先選取權重較高的屬性來提升單個決策樹的分類性能。徐鵬等［5］提出利用訓練數據的信息熵構建決策樹分類方法，但該算法難以應用于高維樣本。目前，國內外對網絡流量異常檢測與分類大多是在單機環境下進行研究，有限的資源難以勝任大數據時代下的大規模流量異常檢測任務。

針對以上不足，本文提出了一種基于Spark平臺的改進隨機森林算法，對生成決策樹的Bootstrap 抽樣方法添加約束條件，降低非平衡數據對生成決策樹的影響；同時，利用不平衡度和袋外數據對決策樹進行加權，提高隨機森林算法整體的分類準確率。

1 相關技術及方法

1.1 隨機森林及Bootstrap抽樣介紹

隨機森林是一種由Breiman［6］提出的集成學習分類算法，該算法利用若干個決策樹來對樣本進行學習和預測，隨機森林算法的分類原理為：

步驟1：在樣本集中用Bootstrap 采樣并有放回地抽取m個樣本，產生一個新生成的子集，并在新生成的子集中選取所有特征中的s個特征，作為決策樹的分離節點；

步驟2： 重復步驟1，直到得到n個決策樹組成隨機森林；

步驟3：將預測數據交給上一步驟中產生的隨機森林中的每棵決策樹進行預測，統計各個決策樹的預測結果，最多決策樹預測出的類別就是隨機森林的分類結果。

1.2 抽樣子集的不平衡度劃分

隨機森林算法使用的Bootstrap 重抽樣方法每次抽取總體的三分之二作為一個訓練樣本，不斷地重復這一個抽取動作，以期望用一系列大小為原訓練樣本三分之二的訓練樣本搭建出一個空間，通過這個空間來無限接近總體。

對于抽樣子集的不平衡度定義如下：①假設數據集中的樣本數為 |D|=M。S={(xi,yi) }，i= 1,2,…,m，公式中xi滿足xi∈X，X是維度為n的空間，X={f1,f2,…,fn}，且yi∈Y，Y是樣本的特征值，Y={1,…,C}。②定義數據集的不平衡系數為B：

其中：Smax和Smin分別為數據集的多數類樣本和少數類樣本，滿足Smax∪Smin={S}且Smax∩Smin={?}。

從這個角度可以把抽樣得到的子集分為以下三種：①子集不平衡系數B′小于原數據集不平衡系數B。②子集不平衡系數B′大于原數據集不平衡系數B。③抽樣子集中無少數類樣本，即Smin不存在，子集不平衡系數B′無法計算。

以上三種情況在隨機森林隨機抽樣中都會出現，其中②和③情況所得的抽樣子集只會加重樣本的不平衡性，通過這些抽樣子集訓練得到的決策樹會干擾最終的投票效果。

2 基于Spark的改進隨機森林算法及其并行化

2.1 基于約束條件的Bootstrap重抽樣

針對以上的決策樹子集不平衡問題，設計了一種基于約束條件的重抽樣Bootstrap 算法。改進后的Bootstrap 抽樣會過濾掉不平衡系數B′較大的子集，進而使不平衡數據集對生成的決策樹產生的影響降低。基于約束條件改進后的Bootstrap重抽樣流程如下：

步驟1：利用Bootstrap 抽樣從數據集D 中抽取三分之二的數據樣本；

步驟2：計算所抽取的數據子集的數據非平衡度B，并添加約束條件為數據子集的非平衡度小于或等于原數據集的非平衡度：

其中：D′max為抽樣得到的數據子集中的多數類數據，D′min為抽樣得到的數據子集中的少數類數據；

步驟3：若Bootstrap 抽樣得出的數據子集滿足約束條件，則可利用該數據子集來構造決策樹。

2.2 改進隨機森林算法的并行化建模

但在訓練不平衡數據時，隨機森林的精度和性能下降一直是該算法的應用局限性，本文提出了一種基于袋外數據和非平衡系數的加權隨機森林算法。文獻［7］研究了貝葉斯公式，得出了評估各個分類器性能的公式，將其中的con(i)用袋外數據的F1值代替，得出的加權公式為

其中：N為決策樹分類器的數；F1(i)為第i個決策樹分類器的袋外數據的F1 值；WOOB(i)表示根據袋外數據所求得的第i個決策樹分類器的權值。

同時，將得出的各個數據子集的非平衡度B(i)作為權值的另一個要素：

綜上所述，改進隨機森林算法主要分為以下步驟：

（1）隨機Bootstrap 抽樣獲取樣本特征，計算不平衡度是否滿足構建決策樹的條件；

（2）利用Bagging抽樣構建決策樹；

（3）通過每棵決策樹的袋外數據預測該決策樹的F1值；

（4）利用分類器性能評價公式對各個決策樹進行加權，并耦合成完整的并行化加權隨機森林模型。

3 實驗

3.1 實驗環境及數據集

本文的實驗環境由Windows11 平臺上Vmware Workstation 安裝的三臺虛擬機組成，其中一臺作為Master，兩臺作為Worker，系統為CentOS，Spark 版本為2.4.4，Hadoop 版本為2.7.1，使用的開發語言為Scala 2.13。

本文采用的數據集是加拿大通信安全機構和加拿大網絡安全研究所發布的CIC-IDS-2018網絡入侵檢測數據集，數據集提供的流量模擬真實網絡流量。CIC-IDS-2018 數據集中包括多種不同的攻擊場景，攻擊包含Brute Force FTP，Brute Force SSH，DoS，Heartbleed（OpenSSL 缺陷），Web Attack，Infiltration（滲透），Botnet（僵尸網絡）和DDos。

3.2 評價標準

在分類任務中，一般使用精確率、召回率以及F1作為評價指標。為了便于介紹，用混淆矩陣來表示：TP表示實際與判定都為正類的樣本；FP表示實際為負類，但被錯誤判定為正類的樣本；FN表示實際為正類，但被預測為負類的樣本；TN表示實際與判定結果都為負類的樣本。

表1 混淆矩陣

精確率的數學公式為

召回率的數學公式為

F1綜合考慮了召回率和精確率，公式為

3.3 實驗結果

由表2可以看出，文中改進的隨機森林算法在對CIC-IDS-2018 的分類上要優于傳統RF 算法。綜合來看，本文提出的改進隨機森林算法利用了決策樹的袋外數據和子數據集的不平衡系數，并通過加權來代替隨機森林中相同權重的決策樹投票，有效減少了隨機森林中劣質樹的干擾。

表2 文中算法與傳統隨機森林算法以及AUC值直接作為權重加權的隨機森林算法比較

此外，得益于Spark 分布式平臺的特性，算法的運行時間大幅度縮短，這是因為Spark 將文件讀取進了內存，減少了對硬盤的頻繁I/O 操作。以下為算法在Spark 分布式平臺上與單機平臺上的運行時間對比。

圖1 改進的隨機森林算法建模

圖2 不同平臺下各算法運行時間對比

4 結語

本文提出一種基于Spark 的改進隨機森林算法，先根據數據子集的不平衡度對決策樹的生成過程施加約束，來改善隨機森林分類算法對不平衡數據集條件下的適用性。接著采用加權投票的方式減少了隨機森林中劣質樹的干擾，提高隨機森林算法的分類精度。實驗結果表明，文中的改進隨機森林算法在CIC-IDS-2018 數據集上的分類精度比傳統隨機森林算法更勝一籌。在以后的研究中，考慮將文中算法與分層抽樣相結合，來進一步改善數據子集與原數據集樣本類別的一致性。