優化隨機森林模型的網絡故障預測

邱少明 楊雯升 杜秀麗 王雪珂

(大連大學通信和網絡重點實驗室 遼寧 大連 116622)

0 引 言

目前，網絡已經遍及國民衣食住行的方方面面，當網絡發生故障時，會嚴重影響國民的基本生活。因此，在網絡發生故障之前，預測故障的發生、排除隱患、保障網絡的正常運行，對于個人生活和企業正常的運行都具有重要的意義。

當前研究主要使用機器學習中的分類算法進行故障預測，根據訓練集建立合適的分類器，然后通過這個分類器對用戶收集的數據作出預測。根據分類器的多少，分類技術可分為單分類器技術和多分類器技術。單分類器技術中比較有代表性的是貝葉斯[4-5]、決策樹[6]和支持向量機[7]。張抗[8]依據相似度理論提出了相似度的概念并給出了計算方法，之后結合支持向量機(SVM)算法設計并實現了一個網絡故障檢測系統。該算法根據相似度對訓練集進行精簡，測試結果表明算法在保持了高準確率的同時，大大提高了訓練和預測速度。陳秀芳等[9]利用決策樹算法，將故障特征作為測試屬性，引入故障點作為類標記，采用ID3算法計算相關信息熵并對故障記錄進行劃分，建立兩者之間的聯系，構建所需要的決策樹，結果表明利用該方法對故障點進行預測，可以有效地縮短故障檢測的時間。郭金玉等[10]通過計算測試樣本和訓練樣本的概率密度進行模態劃分，對各模態的訓練數據建立PCA模型，計算各個模型的控制限和匹配系數，新來數據向對應模態的模型上投影并計算統一的統計量，比較統計量與控制限進行多模態過程故障檢測，結果表明該算法提高了故障分類和檢測的能力。這些算法雖然在一定程度上提升了預測性能，但是由于單分類器自身的限制，其性能提升很容易陷入瓶頸，達不到一個更好的結果。

多分類器組合使用多個基分類器進行分類，并綜合所有分類結果形成一個最終結果[11]。隨機森林(Random Forest，RF)就是在此背景下產生的一種多分類器組合器模型。盡管目前眾多行業都非常青睞于使用RF算法處理分類預測以及回歸問題，但是并不代表RF算法就是完美的，其還有很多提升空間的。

Ishwaran等[12]引入生存樹的概念，對隨機森林構建過程進行改進，提出隨機生存森林算法，通過構建生存函數，生成分析樹的內容和預測結果進行綜合，提高其分類的性能。孫光民等[13]通過對群投票原理進行優化，使用分類與回歸樹(Classification And Regression Tree, CART) 進行預測，將預測結果從小到大排序，最后只取中間20%較好的CART用于最終的預測，降低運算復雜度，縮短了運算時間，減少了預測誤差。王日升等[14]通過計算AUC值，選取隨機森林模型中分類性能好的決策樹，然后對這些決策樹進行相似度計算，根據相似度矩陣選出不相關的決策樹組成新的隨機森林模型，實現對傳統隨機森林算法精度的改進，但是由于算法增加了兩個優化過程，導致改進后模型所消耗的時間增加了。

綜上分析，通過對隨機森林的構造以及分類決策過程進行改進，能夠提高其預測準確率，但是評價一個算法的預測性能好壞，不能單單只從精度方面考慮。例如文獻[14]雖然提升了預測精度，但是卻犧牲掉一些運行時間。而且上述文獻都是使用小樣本數據集進行實驗分析的，當數據集樣本數越來越多時，更要側重考慮算法執行所要消耗的時間。另一方面，由于隨機森林自身的隨機性而導致每次測試的結果都存在一定的波動性，這種不穩定性有時也會影響隨機森林整體的預測性能，目前很少有研究對這方面提出改進。

針對以上問題，并結合本文所使用的網絡故障數據集數據量龐大、冗余度復雜的特點。提出一種優化的隨機森林模型，主要從減少其運算時間，同時提高其預測的準確率和穩定性兩方面提升網絡故障預測性能。

1 隨機森林算法

隨機森林具有隨機性，屬于一種集成學習模型，擁有較強的預測能力。算法利用bagging思想中的隨機采樣(Bootstrap)，從訓練集中采集固定個數的樣本，但是每采集一個樣本后，都將樣本放回，即有放回地采樣[15]。對訓練集進行若干次的隨機采樣后，得到多個不相同的采樣訓練集，并構建對應的決策樹，最后對若干決策樹進行分類投票，將結果預測為得到票數最多的那一類。

隨機森林是一種將決策樹作為基分類器的組合分類器，因此能夠跨越單分類器的限制，達到更佳的預測準確率。除此之外，因為RF自身的隨機性，對異常點和噪聲均具有很好的容忍度，所以能夠有效避免決策樹算法中過擬合問題的出現，提高了泛化能力。

綜上分析，本文選擇使用隨機森林算法進行網絡故障預測，具體算法流程如下：

1) 利用Bootstrap方法重采樣，隨機產生T個訓練集。

2) 使用生成的T個訓練集，對應構建T棵決策樹；在構建的過程中，從總量N個特征變量中，隨機抽取n(n≤N)個特征變量，并從n個特征中選取一個最優的特征變量進行子節點的分裂。

3) 每棵樹都完整成長，而不進行剪枝。

4) 使用測試集，利用構建的多棵決策樹進行測試，得到對應的分類類別。

5) 將T個決策樹中輸出的類別計數投票，選擇票數最多的類別作為隨機森林模型分類的結果。

2 基于PCA的特征降維

包括本文所使用的數據集在內的一些網絡原始數據集，其內部包含信息較多，樣本維度較高，特征較多，而其中有些特征是比較關鍵的，有些特征則對于最終分類器影響較小。這些冗余特征不僅會增加執行時間，甚至可能會對結果帶來干擾。因此為了降低模型構建的時間，提高算法運算性能，本文采用主成分分析(Principal Components Analysis,PCA)對其進行降維[16]。

PCA是一種線性變換，其目的是用少數的新變量(原變量的線性組合)替代原變量，新變量要盡可能多地反映原變量的數據信息[17]。

PCA降維通過比較方差大小來去除那些包含信息較少的維。該降維操作能在保持變量的總方差不變的情況下，將高維數據投影到較低維空間，并且留下的低維特征保證能夠保留原始數據的絕大部分信息。

本文利用PCA降維的實現步驟如下：

1) 將數據集中的數據用向量表示，然后把所有樣本組合起來構成一個矩陣。設輸入的變量矩陣為Xn×k。

2) 求該矩陣的協方差矩陣。

3) 求步驟2)中得到的協方差矩陣的特征值和特征向量，具體步驟如下：

(2) 使得變量P1能攜帶標準化輸入變量矩陣Xn×k的信息。

(3)P1的方差為：

(1)

構造拉格朗日函數：

(2)

式中：λ1為拉格朗日系數。分別計算L對λ1和t1的偏導數，并令其為零，則有：

(3)

由此可知，t1為V的一個標準化特征向量，λ1為其對應的特征值。此時：

(4)

4) 將求得的特征向量按特征值降序排列成一個矩陣，選擇要使用的主成分數目，取其前n行或前n列形成最終的矩陣。

由步驟3)可知，t1就是最大特征值λ1的標準化特征向量。此時所對應的構造變量P1=Xt1稱為第一主成分。

綜上所述，能夠類推求得X的第m個主成分Pm=Xtm，其中，主成分攜帶信息量隨著主成分數目的變大而減少，并且減少的幅度與特征變量自身有關。

5) 使用上述步驟得到的矩陣，即為本文要求的降維后的矩陣。其中前m個主成分攜帶的信息總和為：

(5)

3 基于KDD99數據集隨機森林模型優化

3.1 數據集的優化

本文使用的數據集是KDD CUP99中的kddcup.data_10_percent corrected數據集。該數據集中每個樣本都有41個特征，以下為該數據集中隨機抽取的一條連接記錄：

0,tcp,http,SF,239,486,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,8,8,0,0,0,0,1,0,0,19,19,1,0,0.05,0,0,0,0,0,normal.

其中：第1到第9個特征是TCP連接基本特征，包含一些連接的基本屬性；第10到第22個特征是TCP連接的內容特征；第23到第31個特征是基于時間的網絡流量統計特征；第32到第41個特征是基于主機的網絡流量統計特征[18]。最后的標簽normal表示該條連接記錄是正常的，非normal標簽則表示異常。

KDD99數據集中41個特征中有38個數值型特征和3個非數值型(符號型)特征(2,3,4)，因為非數值型特征不適合聚類測試，所以本文首先將KDD99數據集中3個非數值型特征轉化為數值型特征。對于最后一個標簽，由于本文只討論是否會發生故障，并不討論故障的類型，故數值化時，正常連接(normal)設為1，異常(故障)連接(非normal)設為0。

其次，由于該數據集不同特征之間的數值范圍差異很大，這樣會導致數值范圍大的特征值會對整體數據影響很大，范圍小的特征值則對整體數據的影響可以忽略不計。因此，本文將特征數值化后的數據集進行了數值歸一化，使數值化后的每個數值歸一化到[0，1]區間，從而保證各種特征的重要程度基本相當。

由于歸一化后的數據集依然存在不少對實驗結果影響甚小的特征屬性，嚴重影響了實驗的執行時間。因此，本文又將歸一化數據集使用第2節的主成分分析(PCA)降維操作，降維到一個最佳的維數。降維后的數據集不僅減少了自身的冗余程度，提高了實驗的運行速度，并且只留下對結果貢獻程度大的屬性，這樣對實驗結果的精度又實現了進一步的優化。

3.2 隨機特征變量的選擇

傳統隨機森林算法中，會從總量N個特征變量中，隨機抽取n(n≤N)個特征變量進行最優子節點的選擇。本文選擇使用CART算法對決策樹的內部節點進行劃分。CART決策樹算法的衡量指標為基尼(Gini)系數，在決策樹的構建過程中，選擇Gini系數最小的特征進行子節點劃分。

為了提高隨機森林模型的分類效果，本文利用PCA降維得到的主成分累計貢獻率對特征變量進行降序排列，然后選擇特征重要性好的一部分(比如70%)，因為特征的重要性越高，其對最終預測結果的影響程度越大，即模型的分類效果得到了提高。最后從篩選的這部分特征中隨機選擇n個特征作為當前的劃分子集，之后比較n個特征的Gini系數，選擇最小值作為當前節點的最優特征變量進行節點分裂。這樣在保證較好的特征變量能夠被劃分到分裂屬性集中的同時，相對維持了隨機森林的隨機性，從而提升了決策樹的分類效果，提高了隨機森林模型的預測精度，又在一定程度上削弱了隨機森林的隨機性，使得其模型的穩定性得到了增強。

3.3 預測結果的優化

傳統隨機森林算法中，通過將決策樹中輸出的類別計數投票，并且將票數最高的類別作為隨機森林模型分類的預測結果。但是對于不同的數據集，其自身的情況是不一樣的，比如可能存在以下的情況：一個數據集的結果分為正類和負類。通過分類投票，測試集中的很多樣本兩類的得票數都非常接近，傳統情況下，是將這些樣本預測為得到票數較多的那一類，但是，這些樣本中的大多數實際上為預測票數較少的那一類，這樣就會導致最終的預測結果不理想。另外，本文通過其他一些數據集的測試，發現針對隨機森林模型，不同的閾值對其模型穩定性的影響也不同。

因此為了避免上述情況的發生，本文結合KDD CUP99數據集，通過大量數據的訓練和測試，確定一個閾值進行最后預測結果的分類投票，使用選擇后的閾值不僅能夠保證隨機森林模型在該數據集的預測準確率達到最佳，而且又能提高模型的穩定性。

綜上所述，本文提出的基于KDD CUP99數據集優化隨機森林模型的步驟如下：

1) 對原始KDD CUP99數據集進行數據預處理操作(數值化以及歸一化)，將預處理完的數據集使用PCA進行特征降維操作。

2) 對降維后的訓練數據集使用Bootstrap抽樣，生成T個子訓練集。

3) 利用每個訓練集，對應構建T棵決策樹，對于這些決策樹，從非葉子節點(內部節點)上選擇屬性前，使用PCA降維得到的主成分累計貢獻率對特征變量進行降序排列，選取前n個特征作為當前節點的分裂屬性集，構建CART決策樹，根據前面所述的選取最佳特征變量的步驟進行節點分裂。

4) 將構建的若干決策樹基分類器組合成隨機森林，將測試集數據引入RF模型中進行判斷和分類，選擇一個最佳的閾值，作為預測結果判斷的標準，閾值選取的過程如下：

(1) 將網絡故障預測的結果分為兩類：正類(正常)和負類(異常)。設v+為正類的得票數，pv+為正類的得票率，pv-為負類的得票率，則有：

(6)

式中：ntree為決策樹的棵數；pv++pv-=1。

(7)

(8)

4 實 驗

本文使用MATLAB進行實驗，首先對kddcup.data_10_percent corrected數據集中494 021條連接記錄(樣本)進行3.1節所述的數值化、歸一化操作并且按照第2節所述的步驟，對其進行主成分分析降維操作，選擇出最適合本文要求的降維數據集。然后按照3.3節的步驟進行實驗選取最佳閾值。最后，將本文提出的隨機森林改進模型分別與自身未改進前的算法以及其他預測算法比較，以此證明本文提出算法在網絡故障預測方面的優越性。

4.1 數據集降維分析

本文將經過數值化、歸一化操作的數據集進行PCA降維操作后的結果如圖1所示。圖中柱狀矩形代表單個主成分的貢獻率，折線則代表累計貢獻率。

圖1 主成分貢獻率

主成分序號越大，貢獻率越低，對最后得到的結果貢獻度越小。通常認為累計貢獻率不低于95%是比較令人滿意的結果。主成分數目為5時，其累計貢獻率達到了96.333%。由表1可知，當主成分數目達到10時，貢獻率了超過99%；當主成分數目為14時，累計貢獻率已經增長得很緩慢了，達到99.644%，之后的主成分對最后預測結果的影響微乎其微。因此，本文將分析使用PCA降維得到的前14個主成分，采用隨機森林算法進行故障預測，通過比較實驗運行的時間以及得到結果的準確率綜合判斷，選擇出最適合的維度數據集進行實驗。

表1 主成分數目累計貢獻率表

本次實驗將從kddcup.data_10_percent corrected數據集中隨機選擇150 000條作為實驗樣本，其中70%(105 000條)作為訓練集進行訓練，30%(45 000條)作為測試集(之后實驗如未具體說明，默認采取本次實驗數據集劃分)。實驗結束后，不同維度數據集得到的預測準確率和運行時間關系如圖2所示，其中折線表示預測準確率，柱狀矩形代表運行時間。其具體數值如表2所示。

圖2 KDD99數據集不同主成分數目的預測性能比較

表2 主成分數目準確率和執行時間表

結合表2和圖2可以看出數據集主成分數目越多，故障預測的準確率就越高。當數據集為14維時，預測準確率達到99.867%，但總耗時已達到108.604 s。事實上，從圖2還可以看出，當主成分數目超過5后，其預測準確率的增長已經達到了飽和狀態，增長緩慢。雖然維數越高，其準確率越高，但是其總耗時也在增加，特別是當維數超過9以后，實驗運行消耗的總時間增長幅度明顯增加。

通過以上的分析，本文選擇主成分數目為6的數據集作為最佳數據集。其選擇原因有兩點：一方面當主成分的數目為6時，其累計貢獻率為97.365 7%，而且預測準確率也達到了99.722%，都是比較滿意的結果；另一方面，當主成分數目增加到7和8時，其預測準確率幾乎沒變，但是總耗時卻顯著增加，當主成分數目增加到9時，雖然準確率提高了，但是其執行時間增加了約18 s，為了提高一點點的準確率消耗過多的時間是不劃算的。因此，本文選擇了主成分數目為6，即將原始的41維數據，通過PCA降維到6維，進行接下來的實驗。

4.2 最佳閾值的選擇

按照4.1節的結果，本文使用6維的數據集，為了選擇出適合本文數據集的閾值，按照3.3節閾值選取的步驟進行實驗。其中，本次實驗訓練樣本和測試樣本按照4 ∶1進行隨機分配，對每個閾值均在相同參數的條件下，做10次實驗取預測結果準確率均值進行比較。

表3 閾值選擇的實驗結果

可以看出，當閾值區間在[0.45, 0.60]時，預測的平均準確率達到一個最佳的區間，因此進一步比較不同閾值之間結果的穩定性，計算[0.45, 0.60]區間的平均故障數以及故障樣本故障方差。當閾值為0.47時，故障樣本方差最小，為56.56，平均預測準確率也達到了最佳。因此，基于本文使用的數據集，為了保持隨機森林模型最佳的預測精度以及穩定性，選擇0.47作為閾值進行實驗。

4.3 性能優化比較

性能優化的實驗結果如表4所示，其中第二列數據是將原始數據集經過數值化得到的，維數為原始的41維；第三列是進一步將數據進行歸一化后數據，維數依然為41；第四列數據是將歸一化后數據進行PCA降維得到的，維數為6。其中：第二、三、四列均利用隨機森林算法進行訓練和預測；第五列使用的也是經過處理后的6維數據，利用本文提出的優化隨機森林算法進行訓練。

表4 性能優化的實驗結果

可以看出，利用隨機森林算法對數值化后和歸一化后的數據集進行故障預測，從得到的結果來看，歸一化后在耗時和準確率兩方面，結果都明顯優于未歸一化時的結果，說明本文對數據進行歸一化的操作是有用的。歸一化后數據的范圍都在[0, 1]之間，不會存在數值大的影響數值小的情況，即最終結果不會對個別取值范圍非常大的特征產生大的依賴，這使得測試準確率比較理想。另外由于綜合考慮了各個特征，使得結果收斂更快，耗時也大大減少。

利用算法對歸一化后的41維數據集和降維后的6維數據集進行實驗，得到的結果顯示，降維后訓練耗時減少了85.744%，降幅明顯，但準確率降低了0.207%?？紤]到耗時大幅度地降低，綜合來看，還是降維后的預測性能更優越一些。

對比使用6維數據時，隨機森林算法(第四列)與本文提出的優化算法(第五列)，首先訓練耗時變化不大，但是準確率得到了一定的提升，提升了0.18個百分點，這也充分說明了本文所使用的優化隨機森林算法的優越性。

4.4 預測性能比較

本文選擇網絡故障預測的準確率作為評價指標，用來比較傳統的隨機森林算法、決策樹、主成分分析回歸算法，以及本文提出的優化隨機森林算法的預測性能。

首先使用本文提出的優化RF算法，設置包含500棵樹的隨機森林模型，預測閾值為0.47，按照第3.3節所述的步驟進行實驗，得到預測結果；決策樹預測模型使用MATLAB自帶的決策樹函數建立，使用同樣的數據集對其進行訓練和測試，得到相應的預測精度，并與傳統RF以及本文提出的模型進行比較，如圖3所示；最后本文又使用PCA回歸算法進行相同的步驟得到預測結果，其結果與其他三種方法的具體數值如表5所示。

圖3 本文算法與其他分類算法預測性能的比較

表5 四種預測方法的實驗結果 %

可以看出，優化RF相比于決策樹以及傳統RF算法，其預測準確率分別平均提升了0.4個百分點和0.2個百分點左右，而且本文方法相較于傳統RF方法，其穩定性有了較大的提升。表5顯示，優化RF相較于PCA回歸算法，其預測準確率大幅提升。綜上表明，利用本文提出的優化RF算法，對經過數據預處理的6維KDD CUP99數據集進行網絡故障預測，達到了最佳的預測性能。

5 結 語

將PCA累計貢獻率引入到隨機森林模型中，結合PCA累計貢獻率，選取前m個特征作為當前的分裂屬性集，通過計算比較，選擇一個最佳的閾值進行預測分類，優化了隨機森林模型，并且提高RF模型的分類能力。實驗結果表明，采用本文方法進行網絡故障預測，得到的預測性能優于與本文所比較的其他預測方法。之后，研究工作將從進一步提高算法的運行速度，以及在預測出故障發生的基礎上，能夠預測出不同類型的故障兩方面入手，實現更高性能的多類型網絡故障預測。