針對不平衡數(shù)據(jù)的決策樹改進方法

王偉 謝耀濱 尹青

摘 要：針對異常檢測中異常數(shù)據(jù)與正常數(shù)據(jù)的比例嚴(yán)重不平衡導(dǎo)致決策樹性能下降的問題，提出了C4.5決策樹的三種改進方法——C4.5+δ、均勻分布熵（UDE）和改進分布熵函數(shù)（IDEF）。首先，推導(dǎo)了C4.5算法中屬性選擇準(zhǔn)則會傾向于選擇偏斜劃分的屬性;然后，分析了偏斜劃分使得異常（少數(shù)類）檢測精度下降的原因;其次，分別通過引入緩和因子、均勻分布熵或替換分布熵函數(shù)改進了C4.5算法的屬性選擇準(zhǔn)則——信息增益率;最后，利用WEKA平臺和NSL-KDD數(shù)據(jù)集對改進的決策樹進行驗證。實驗結(jié)果表明，三種改進方法均能提高異常檢測精度。其中，相比于C4.5，C4.5+7、UDE和IDEF算法在KDDTest-21數(shù)據(jù)集上的少數(shù)類檢測精度（靈敏度）分別提高了3.16、3.02和3.12個百分點，均優(yōu)于采用Rényi熵和Tsallis熵作為分裂準(zhǔn)則的方法。此外，利用三種改進的決策樹檢測工業(yè)控制系統(tǒng)中的異常，不僅可以提高異常的查全率還能減小誤報率。

關(guān)鍵詞：不平衡數(shù)據(jù);異常檢測;決策樹;C4.5;信息增益率

中圖分類號： TP181

文獻標(biāo)志碼：A

文章編號：1001-9081（2019）03-0623-06

Abstract： Focusing on the problem that serious imbalance between abnormal data and normal data in anomaly detection will lead to performance degradation of decision tree， three improved methods for C4.5 decision tree were proposed， which are C4.5+δ， UDE （Uniform Distribution Entropy） and IDEF （Improved Distribution Entropy Function）. Firstly， it was deduced that the attribute selection criterion of C4.5 tends to choose the ones with imbalanced splitting. Secondly， why imbalanced splitting decreases the accuracy of anomaly （minority） detection was analyzed. Thirdly， the attribute selection criterion — information gain ratio of C4.5 was improved by introducing relaxation factor and uniform distribution entropy， or substituting distribution entropy function. Finally， three improved decision trees were verified on WEKA platform and NSL-KDD dataset. Experimental results show that three proposed improved methods can increase the accuracy of anomaly detection. Compared with C4.5， the accuracies of C4.5+7， UDE and IDEF on KDDTest-21 dataset are improved by 3.16， 3.02 and 3.12 percentage points respectively， which are better than the methods using Rényi entropy or Tsallis entropy as splitting criterion. Furthermore， using improved decision trees to detect anomalies in the industrial control system can not only improve the recall ratio of anomalies， but also reduce false positive rate.

Key words： imbalanced data; anomaly detection; decision tree; C4.5; information gain ratio

0 引言

異常檢測是指從某個系統(tǒng)的日常數(shù)據(jù)中識別非預(yù)期模式，即異常數(shù)據(jù)。異常通常由惡意行為或違規(guī)操作引發(fā)，因此異常檢測技術(shù)廣泛應(yīng)用于網(wǎng)絡(luò)安全、故障檢測等領(lǐng)域[1-3]。

異常檢測可以視為一種特殊的分類問題，即分離目標(biāo)數(shù)據(jù)集中的正常數(shù)據(jù)與異常數(shù)據(jù)。因此，絕大多數(shù)基于機器學(xué)習(xí)的分類方法，如神經(jīng)網(wǎng)絡(luò)、支持向量機、決策樹等，都可以應(yīng)用于異常檢測。然而異常檢測面臨數(shù)據(jù)不平衡問題，即目標(biāo)數(shù)據(jù)集中異常數(shù)據(jù)與正常數(shù)據(jù)的分布是不平衡的，其中異常數(shù)據(jù)一般遠(yuǎn)遠(yuǎn)少于正常數(shù)據(jù)。數(shù)據(jù)不平衡問題在醫(yī)療診斷[4]、信用卡詐騙檢測[5]、銀行風(fēng)險管控[6]、系統(tǒng)故障檢測[7]等應(yīng)用中十分常見。在傳統(tǒng)分類問題中，整體準(zhǔn)確度由不同類別的準(zhǔn)確度加權(quán)組成，因此多數(shù)類的準(zhǔn)確度對整體準(zhǔn)確度的影響要遠(yuǎn)大于少數(shù)類。在傳統(tǒng)方法中，分類器會傾向于保證多數(shù)類的準(zhǔn)確度而犧牲少數(shù)類的準(zhǔn)確度，導(dǎo)致少數(shù)類的漏報率較高。然而在很多異常檢測的現(xiàn)實應(yīng)用中將異常（少數(shù)類）誤判為正常（多數(shù)類）的代價要遠(yuǎn)遠(yuǎn)高于相反的情況，因此需要盡可能地檢測出異常，降低漏報率。例如，在癌癥的診斷中，將癌癥（少數(shù)類）患者誤診為健康（多數(shù)類）的危害要遠(yuǎn)大于將非癌癥患者誤診為癌癥的危害，所以要保證檢測結(jié)果為陽性時盡可能地覆蓋真正的癌癥患者。

對于不平衡分類問題，主要從數(shù)據(jù)和算法兩個層面來解決[8]。數(shù)據(jù)層面的方法首先通過數(shù)據(jù)預(yù)處理平衡數(shù)據(jù)分布從而消除多數(shù)類的影響，而后運用傳統(tǒng)方法進行分類;算法層面的方法通過修改學(xué)習(xí)算法來處理不平衡分類問題。這些方法保留原有方法的主體思想，通過調(diào)整決策閾值使其偏向于少數(shù)類或者在學(xué)習(xí)過程中引入錯誤分類代價提高少數(shù)類的重要性。除此之外，許多研究人員將數(shù)據(jù)層面和算法層面的方法相結(jié)合[9-10]，為不平衡分類問題提供了全新的綜合性解決方案。

本文從算法層面入手，對C4.5決策樹的特征選擇準(zhǔn)則進行改進。本文的主要貢獻在于：1）提出了三種針對不平衡數(shù)據(jù)的C4.5決策樹改進方法;2）運用改進的決策樹進行異常檢測并驗證了其有效性。

本文將在下一章中回顧近幾年來不平衡學(xué)習(xí)的相關(guān)方法。第二章介紹了決策樹并分析了特征選擇準(zhǔn)則對不平衡分類的影響。針對第二章中分析的不平衡分布情況下性能下降的原因，第三章詳細(xì)描述了三種改進方法的細(xì)節(jié)。本文將所提的方法應(yīng)用于異常檢測，檢測結(jié)果及分析將在第四章中進行展示。最后，第五章將對全文進行總結(jié)并提出下一步的研究目標(biāo)。

1 相關(guān)工作

為了提升機器學(xué)習(xí)算法處理不平衡數(shù)據(jù)的性能，研究人員提出了許多解決辦法，大致可分為數(shù)據(jù)層面和算法層面。數(shù)據(jù)層面的方法獨立于分類器，具有較高的靈活性與普適性;算法層面的方法通過修改學(xué)習(xí)算法解決不平衡分類問題，具有較強的針對性。

數(shù)據(jù)層面包含過采樣法、欠采樣法、過采樣和欠采樣的綜合法。采樣方式分為啟發(fā)式和非啟發(fā)式，非啟發(fā)式采樣法通常由隨機過采樣和隨機欠采樣組成。合成少數(shù)類過采樣技術(shù)（Synthetic Minority Oversampling TEchnique， SMOTE）[11]是一種典型的啟發(fā)式過采樣方法，該算法的提出是為了解決隨機過采樣法增加過擬合風(fēng)險的問題。另外，啟發(fā)式過采樣方法包括K近鄰規(guī)則（K-Nearest Neighbor， KNN）、鄰域清理規(guī)則（Neighborhood CLeaning rule， NCL）[12]、OSS（One-Sided Selection）[13]和IRUS（Inverse Random Under Sampling）[14]等。

MohammadImran等[15]提出了OSIBD（Over Sampling on Imbalance Big Data）算法提升不平衡分類的性能。該算法采用新型的過采樣策略對數(shù)據(jù)集進行預(yù)處理。首先，根據(jù)數(shù)據(jù)分布移除少數(shù)類樣本中的噪聲和邊緣點;隨后，在處理后的少數(shù)類樣本之間插入合成樣本實現(xiàn)混合過采樣;最后，利用C4.5算法進行分類。實驗結(jié)果證明，改進后的方案中精確度、召回率均有所提升。

在算法層面，不同算法的解決方法有所差異，下面將著重介紹關(guān)于決策樹算法的相關(guān)研究工作。在傳統(tǒng)的決策樹算法中，香農(nóng)熵用于度量樣例集合的不純凈度，并作為樹節(jié)點的分裂依據(jù)。Lima等[16]針對熵的測量方法對決策樹進行改進，分別采用Rényi熵和Tsallis熵代替香農(nóng)熵作為分裂準(zhǔn)則。在KDD（Knowledge Discovery and Data mining）數(shù)據(jù)集上進行實驗，結(jié)果表明依據(jù)Rényi熵和Tsallis熵建立的決策樹模型更加緊湊與高效。

為了提升決策樹在不平衡數(shù)據(jù)集上的學(xué)習(xí)性能，Boonchuay等[17]提出了一種全新的不純凈度度量方法——少數(shù)類熵（Minority Entropy， ME）。首先，確定少數(shù)類分布的范圍并忽視范圍外的多數(shù)類樣本;隨后，計算并衡量少數(shù)類范圍內(nèi)的香農(nóng)熵。該方法通過排除純凈部分的多數(shù)類樣本，緩解了不平衡分布的問題。

Kirshners等[18]在熵函數(shù)的計算公式中引入了權(quán)重概念。其中，權(quán)重代表每一類樣本的重要性，且與分布概率成反比。改進的決策樹算法在學(xué)習(xí)階段之前計算初始的類分布概率，提高學(xué)習(xí)階段中對少數(shù)類的重視程度。實驗結(jié)果表明在不同的數(shù)據(jù)集上該算法的敏感度（即少數(shù)類的準(zhǔn)確率）有顯著提升。

代價敏感學(xué)習(xí)是一種解決不平衡分類問題的有效途徑。Li等[19]提出了一種代價敏感決策樹算法，其中包含了兩種自適應(yīng)機制。自適應(yīng)分割點選擇機制將屬性的代價引入到信息增益率的計算公式中，代替原始的遍歷選擇機制;自適應(yīng)屬性刪除機制在節(jié)點選擇過程中刪除冗余屬性。相比于C4.5，改進后的算法不僅降低了平均分類代價，而且縮短了算法的運行時間;鄭燕等[20]提出了一種代價敏感超網(wǎng)絡(luò)Boosting集成算法，首先將代價敏感學(xué)習(xí)引入超網(wǎng)絡(luò)模型，而后利用Boosting算法對代價敏感超網(wǎng)絡(luò)進行集成，以處理不平衡數(shù)據(jù)分類問題。

除此之外，集成法通過綜合多種方法為不平衡分類問題提供全新的綜合性解決方案，其優(yōu)勢在于通過融合不同方面的優(yōu)勢提高了算法的穩(wěn)定性。文獻[21]中介紹了一種基于包裹式特征選擇的引導(dǎo)聚集（Bagging）框架，該框架包含數(shù)據(jù)預(yù)處理和Bagging兩個過程。數(shù)據(jù)預(yù)處理過程中，首先采用隨機欠采樣壓縮數(shù)據(jù)，而后利用包裹式特征選擇算法刪除冗余屬性;Bagging過程中，通過引導(dǎo)采樣生成多個子集，而后在多個子集上分別訓(xùn)練決策樹，最終輸出由多個決策樹投票決定的結(jié)果。

2 問題分析

為了解決不平衡分類問題，本章對決策樹算法進行分析并尋找導(dǎo)致分類性能下降的原因。在2.1節(jié)中，介紹了決策樹算法的過程及相應(yīng)的準(zhǔn)則;在2.2節(jié)中，通過分析兩種數(shù)據(jù)分布情況探究C4.5算法中屬性選擇對不平衡數(shù)據(jù)分類的影響。

2.1 決策樹算法

1）根據(jù)分裂準(zhǔn)則，在數(shù)據(jù)集D上選擇一個最優(yōu)分裂屬性;

2）在最優(yōu)分裂屬性上選擇最優(yōu)分裂點，將數(shù)據(jù)集D分為DL和DR兩個子節(jié)點;

3）在子節(jié)點上重復(fù)上述步驟，直到所有葉節(jié)點滿足停止準(zhǔn)則。

在每次迭代過程中，決策樹隨著子節(jié)點的分裂不斷生長。當(dāng)所有的葉節(jié)點均滿足停止準(zhǔn)則時，決策樹停止生長。停止準(zhǔn)則通常由純凈度、葉節(jié)點數(shù)和樹深度等條件組成。

分裂準(zhǔn)則通過計算不純凈度決定葉節(jié)點如何分裂。最常用的分裂準(zhǔn)則是基于香農(nóng)熵的信息增益：

其中IG表示分裂前后的信息增益（即熵的衰減值）。香農(nóng)熵的定義如式（2）所示，其值域范圍為[0，lb n]，當(dāng)p（yi）相等時達到極大值，當(dāng)p（yi）等于0或1時達到最小值。因此，最大化信息增益準(zhǔn)則將引導(dǎo)節(jié)點向純凈分類。

常用的決策樹算法有ID3、C4.5[22]等。ID3算法根據(jù)最大化信息增益準(zhǔn)則選擇最優(yōu)分裂屬性，導(dǎo)致其傾向于選擇取值多的屬性; C4.5算法對ID3算法進行改進，根據(jù)最大化信息增益率準(zhǔn)則選擇最優(yōu)分裂屬性。為了濾除虛高的信息增益率——低信息增益、低分布熵，C4.5算法涵蓋一種啟發(fā)式規(guī)則——首先濾除信息增益低于平均值的屬性，而后比較剩余屬性的信息增益率。本文將在下一節(jié)中分析C4.5決策樹建立過程中選擇不同的屬性對不平衡數(shù)據(jù)的影響。

2.2 C4.5處理不平衡數(shù)據(jù)的不足

C4.5算法根據(jù)信息增益率選擇最優(yōu)分裂屬性，信息增益率公式計算如下：

其中H（X）表示同級子節(jié)點的分布熵。隨著子節(jié)點數(shù)量的增多，H（X）相應(yīng)增大，從而抑制子節(jié)點數(shù)量對信息增益的影響。

由于理想子節(jié)點數(shù)量未知，C4.5算法在處理連續(xù)型數(shù)值屬性時，采取迭代二元分裂的方式實現(xiàn)多元分裂。在每次迭代過程中，節(jié)點分裂出兩個子節(jié)點，此時的信息增益不受子節(jié)點數(shù)量影響;而子節(jié)點權(quán)重的差異導(dǎo)致H（X）在[0，1]之區(qū)間波動。當(dāng)數(shù)據(jù)分布不平衡時，子節(jié)點的權(quán)重存在嚴(yán)重偏斜的情況。當(dāng)P（X>x）-P（X

3 改進方法

為了緩和或消除分布熵對信息增益率的影響，本章結(jié)合上文的分析，提出了三種信息增益率的改進方法。

1）引入緩和因子δ。

信息增益率計算公式（式（3））中，分布熵H（X）在0到1之間變化。在極端情況下，信息增益率是信息增益的無窮倍，此時信息增益明顯起不到主導(dǎo)作用。因此，在信息增益率的計算公式中引入緩和因子δ。改進后的信息增益率計算公式如下：

2）用均勻分布熵代替分布熵。

為了消除枚舉型屬性的子節(jié)點數(shù)量對信息增益的影響，C4.5算法引入分布熵。而在處理連續(xù)數(shù)值型屬性時，采取迭代二元分裂的方式實現(xiàn)多元分裂。在每一次迭代過程中，節(jié)點分裂數(shù)為2，此時信息增益不受子節(jié)點數(shù)量的影響。但在面對不平衡數(shù)據(jù)時，分布熵抑制了信息增益的主導(dǎo)作用。因此，本方法采用均勻分布熵（Uniform Distribution Entropy， UDE）代替分布熵，改進后的信息增益率計算公式如下：

其中n為樣例子集的數(shù)量。

改進后的信息增益率不僅抵消了子節(jié)點數(shù)量對信息增益的影響，而且消除了子節(jié)點的分布情況對信息增益的影響。

3）改進分布熵函數(shù)。

二元香農(nóng)分布熵函數(shù)的圖像如圖3中虛線部分所示。二元分布從[0.5，0.5]（即平均分布）到[0.1，0.9]的過程中，香農(nóng)熵衰減超過50%。此時，分布熵在信息增益率中占據(jù)主導(dǎo)地位，因此，可通過改進分布熵函數(shù)（Improved Distribution Entropy Function， IDEF）削弱分布熵的影響，即采用從平均分布到偏斜分布的過程中衰減緩慢的函數(shù)代替分布熵函數(shù)。

新函數(shù)需滿足熵函數(shù)的部分性質(zhì)，如對稱性、確定性、非負(fù)性、連續(xù)性、上凸性和極值性等。本方法采用如下函數(shù)代替香農(nóng)分布熵函數(shù)：

其中：k為系數(shù)，α為可調(diào)參數(shù)，且α<1。為了使峰值與原函數(shù)保持一致，將k設(shè)為nnαlb n。C（X）的圖像如圖3中紅色最上方曲線所示，當(dāng)α=1/3時，二元分布從[0.5，0.5]到[0.1，0.9]的過程中，衰減減少至30%以內(nèi)。

4 實驗與評估

本章將通過兩部分實驗對所提方法的有效性進行驗證。4.1節(jié)將展示在NSL-KDD數(shù)據(jù)集上評估提出的方法處理不平衡數(shù)據(jù)的性能，并與采用Rényi熵和Tsallis熵的方法進行對比;4.2節(jié)將利用改進的決策樹進行工業(yè)控制系統(tǒng)中的異常檢測;本文實驗依托由新西蘭懷卡托大學(xué)開發(fā)的公開數(shù)據(jù)挖掘工作平臺——懷卡托智能分析環(huán)境（Waikato Environment for Knowledge Analysis， WEKA）[23]，通過修改WEKA 3.8.2中的J48（即C4.5）決策樹實現(xiàn)。實驗采用十折交叉驗證方式，并開啟剪枝過程。

4.1 NSL-KDD測試

NSL-KDD數(shù)據(jù)集[24]是一個面向網(wǎng)絡(luò)入侵檢測系統(tǒng)的公開數(shù)據(jù)集，共包含41維特征屬性以及1維目標(biāo)屬性。KDDTest-21數(shù)據(jù)集包含2152個正常樣本與9698個異常樣本;KDDTrain+數(shù)據(jù)集包含67343個異常樣本、58630個正常樣本。為了使偏斜率多樣化并且降低數(shù)據(jù)規(guī)模，本文對KDDTrain+數(shù)據(jù)集中的異常樣本和正常樣本隨機抽樣，構(gòu)造了5個不同偏斜率的數(shù)據(jù)集。本節(jié)實驗中使用的數(shù)據(jù)集如表1所示。

在不平衡數(shù)據(jù)的情況下，準(zhǔn)確率和錯誤率不足以衡量分類算法的性能。因此，本文額外引入兩項衡量指標(biāo)——靈敏度（又稱為召回率或查全率）和特異度。靈敏度表示分類算法正確預(yù)測正樣本數(shù)量占實際正樣本數(shù)量的百分率，其公式表述如式8所示。其中，真陽性（True Positives， TP）表示預(yù)測為正的正樣本數(shù)，假陰性（False Negatives， FN）表示預(yù)測為負(fù)的正樣本數(shù)。

特異度表示分類算法正確預(yù)測負(fù)樣本數(shù)量占實際負(fù)樣本數(shù)量的百分率，其公式表述如式（9）所示。其中，真陰性（True Negatives， TN）表示預(yù)測為負(fù)的負(fù)樣本數(shù)，假陽性（False Positives， FP）表示預(yù)測為正的負(fù)樣本數(shù)。

本文提出的方法在KDDTest-21及KDD101～105數(shù)據(jù)集上的結(jié)果對比如表2所示。

第一列表示數(shù)據(jù)集名稱，第二列為決策樹及其改進方法的簡稱，其中C4.5+δ表示方法（一）引入緩和因子δ、UDE表示方法（二）用均勻分布熵代替分布熵、IDEF表示方法（三）改進分布熵函數(shù)。此外，文獻[16]中提出的基于Rényi熵和Tsallis熵的決策樹作為本文的比對方法，作者針對不純凈度的度量方法對決策樹進行改進，分別采用Rényi熵和Tsallis熵代替香農(nóng)熵作為分裂準(zhǔn)則。Rényi熵和Tsallis熵的計算公式如式（10）和式（11）所示：

在KDDTest-21數(shù)據(jù)集上，C4.5+δ、UDE、IDEF相對于C4.5均有所提升，且C4.5+δ提升幅度最大，如表2所示（加粗部分表示最佳性能）。當(dāng)δ=7時，C4.5+7的準(zhǔn)確率達到97.76%。與C4.5算法相比， C4.5+7的靈敏度（少數(shù)類的分類精度）提升了3.16個百分比，且特異度（即多數(shù)類的分類精度）也有小幅提升。而Rényi熵和Tsallis熵在提升靈敏度的同時，特異度有所下降。此外，葉節(jié)點數(shù)與決策樹大小代表模型的復(fù)雜度（后續(xù)分析中以決策樹大小代表模型復(fù)雜度）。與C4.5算法相比，C4.5+7算法生成的決策樹減小了51.53%。因此，三種改進方法在提升檢測效果的同時，又大幅度降低了模型的復(fù)雜度。

接下來，利用KDD101～105數(shù)據(jù)集對三種改進方法進行驗證與對比，以探究在不同偏斜率的情況下三種算法的適用性。在KDD101數(shù)據(jù)集上，C4.5+δ、UDE、IDEF相對于C4.5均有所提升。其中，UDE算法在準(zhǔn)確率、錯誤率和靈敏度上均取得了最優(yōu)值。相比于C4.5算法，C4.5+5、UDE、IDEF算法的靈敏度分別提升了1.4%、1.5%、0.3%;在特異度指標(biāo)方面，UDE算法略遜色于IDEF算法。雖然三種改進方法均不同程度上增加了模型的復(fù)雜度（UDE模型復(fù)雜度相對于C4.5算法提高了19.55個百分點），但仍優(yōu)于Rényi熵和Tsallis熵（Rényi熵和Tsallis熵分別提高了40.6和26.32個百分點）。因此，可理解為由于KDD101數(shù)據(jù)集偏斜嚴(yán)重，提高模型復(fù)雜度是提升決策樹性能的必要條件。

在KDD102上，C4.5+δ、UDE、IDEF相對于C4.5算法均有所提升。當(dāng)δ增至11時，C4.5+δ的各項性能指標(biāo)達到最優(yōu)值，其中靈敏度從97.8%提升至98.75%;盡管Tsallis熵方法的特異度達到了99.86%，但靈敏度相對于原始算法有所下降。在此數(shù)據(jù)集上雖然Tsallis熵方法提高了準(zhǔn)確率，但其顯然不是解決不平衡分類問題的有效方法。

從KDD101至KDD104，數(shù)據(jù)集趨于平衡，C4.5+δ性能最優(yōu)時對應(yīng)的參數(shù)δ逐漸增大。當(dāng)δ大于最優(yōu)值后，性能趨于穩(wěn)定，但隨著δ增大模型趨于簡單化。除此之外，隨著不平衡情況的減緩，改進方法的提升幅度逐漸降低，而Rényi熵和Tsallis熵方法逐漸失效。例如，在KDD104數(shù)據(jù)集上，雖然基于Rényi熵的方法準(zhǔn)確率高于C4.5算法，但其靈敏度相對于C4.5算法有所降低。與KDD104類似，Rényi熵和Tsallis熵方法在KDD105數(shù)據(jù)集上（即面臨輕微不平衡的情況時）失去效果。

表2展示了幾種方法在面臨不同偏斜率的數(shù)據(jù)集時的性能?？傮w而言，C4.5+δ在解決不平衡分類問題時表現(xiàn)出了突出的性能;而UDE與IDEF也擁有解決不平衡分類問題的能力，并且相對于C4.5+δ而言，具有更好的泛化性能。

4.2 工業(yè)控制過程的異常檢測

工業(yè)控制過程的異常檢測常常也面臨數(shù)據(jù)不平衡問題，因為工控系統(tǒng)中正常狀態(tài)明顯多于異常狀態(tài)。本節(jié)利用改進的決策樹算法進行工業(yè)控制領(lǐng)域的異常檢測，進而證明所提方法的實用價值。

水處理安全測試平臺（Secure Water Treatment， SWaT）[25]是現(xiàn)實工業(yè)中水處理工廠的模型，其處理過程共分為6個階段，如圖4所示。

SWaT數(shù)據(jù)集[26]共記錄了該系統(tǒng)11天的運行數(shù)據(jù)。前7天系統(tǒng)正常運行，后4天對該系統(tǒng)不定時發(fā)動36次攻擊。

本節(jié)實驗在SWaT后4天記錄的數(shù)據(jù)上進行，共包含396019個正常數(shù)據(jù)與53900個異常數(shù)據(jù)。檢測結(jié)果通過混淆矩陣直觀展示，混淆矩陣定義如表3所示。

C4.5算法及三種改進方法關(guān)于SWaT的異常檢測結(jié)果如表4所示。原始的C4.5算法檢測結(jié)果中，異常數(shù)據(jù)的漏報數(shù)量為119，誤報數(shù)量為90。此時，C4.5算法向正常類偏斜。當(dāng)δ=7時，C4.5+δ算法的檢測效果最佳。其中，異常的漏報數(shù)量為92，而誤報數(shù)量為82。與C4.5算法相比，C4.5+7算法的漏檢率減小了22.69%、誤報率減小了8.89%。從實驗結(jié)果來看，兩類數(shù)據(jù)的錯誤分類數(shù)量基本持平。因此，C4.5+δ基本上解決了不平衡分類問題。另外，UDE與IDEF的檢測結(jié)果相同。相對于C4.5而言，異常的漏報數(shù)量從119減少至103，而誤報數(shù)量從90減少至97。從實驗效果來看，UDE和IDEF算法在一定程度上緩解了不平衡分類問題。

由表4可知，三種改進方法均能改善工控異常檢測中的不平衡分類問題。其中，UDE與IDEF提高了異常的檢測效率，但未徹底解決不平衡問題;而C4.5+δ提升效果明顯優(yōu)于UDE與IDEF，經(jīng)過改進，異常數(shù)據(jù)和正常數(shù)據(jù)的錯誤分類數(shù)量基本持平，基本上解決了異常檢測的不平衡問題。

5 結(jié)語

在平衡數(shù)據(jù)的分類任務(wù)中，決策樹因其簡單高效且具有強解釋性而備受矚目。然而，當(dāng)面臨不平衡數(shù)據(jù)時，決策樹算法偏向于多數(shù)類使其性能大打折扣。同時，在異常檢測任務(wù)中，盡管異常數(shù)據(jù)遠(yuǎn)遠(yuǎn)少于正常數(shù)據(jù)，但異常數(shù)據(jù)的檢測率尤其重要。因此，本文分析了C4.5決策樹的不平衡原因，并提出了屬性選擇準(zhǔn)則的三種改進方法——C4.5+δ、UDE、IDEF。

對改進的決策樹算法在不同偏斜率的KDD數(shù)據(jù)集上進行測試，三種方法的靈敏度和特異度均有明顯提升。與Rényi熵和Tsallis熵相比，本文提出的方法在提升少數(shù)類準(zhǔn)確率的同時，還保證了多數(shù)類的準(zhǔn)確率。最后，改進的決策樹應(yīng)用于工業(yè)控制系統(tǒng)的異常檢測過程中，實驗結(jié)果證明本文提出的方法能改善不平衡分類問題。

計劃從數(shù)據(jù)層面開展下一步工作，提出適用于異常檢測的人工合成少數(shù)類方法，結(jié)合本文的方法形成綜合性解決方案，進一步提升異常檢測的性能。

參考文獻 （References）

[1] ESKIN E， ARNOLD A， PRERAU M， et al. A geometric framework for unsupervised anomaly detection [J]. Applications of Data Mining in Computer Security， 2002， 6： 77-101.

[2] ISERMANN R， BALLE P. Trends in the application of model-based fault detection and diagnosis of technical processes [J]. Control Engineering Practice， 1997， 5（5）： 709-719.

[3] KOU Y， LU C T， SIRWONGWATTANA S， et al. Survey of fraud detection techniques [C]// Proceedings of the 2004 IEEE International Conference on Networking， Sensing and Control. Piscataway， NJ： IEEE， 2004： 749-754.

[4] 王莉莉，付忠良，陶攀，等.基于主動學(xué)習(xí)不平衡多分類AdaBoost算法的心臟病分類[J].計算機應(yīng)用，2017，37（7）：1994-1998.（WANG L L， FU Z L， TAO P， et al. Heart disease classification based on active imbalance multi-class AdaBoost algorithm [J]. Journal of Computer Applications， 2017， 37（7）： 1994-1998.）

[5] FU K， CHENG D， TU Y， et al. Credit card fraud detection using convolutional neural networks [C]// Proceedings of the 2016 International Conference on Neural Information Processing. Berlin： Springer， 2016： 483-490.

[6] DANENAS P， GARSVA G. Selection of support vector machines based classifiers for credit risk domain [J]. Expert Systems with Applications， 2015， 42（6）： 3194-3204.

[7] MARTIN-DIAZ I， MORINIGO-SOTELO D， DUQUE-PEREZ O， et al. Early fault detection in induction motors using AdaBoost with imbalanced small data and optimized sampling [J]. IEEE Transactions on Industry Applications， 2017， 53（3）： 3066-3075.

[8] 趙楠，張小芳，張利軍.不平衡數(shù)據(jù)分類研究綜述[J]. 計算機科學(xué)，2018，45（S1）：22-27.（ZHAO N， ZHANG X F， ZHANG L J. Overview of imbalanced data classification [J]. Computer Science， 2018， 45（S1）： 22-27.）

[9] IRTAZA A， ADNAN S M， AHMED K T， et al. An ensemble based evolutionary approach to the class imbalance problem with applications in CBIR [J]. Applied Sciences， 2018， 8（4）： 495.

[10] GALAR M， FERNANDEZ A， BARRENECHEA E， et al. EUSBoost： enhancing ensembles for highly imbalanced data-sets by evolutionary undersampling [J]. Pattern Recognition， 2013， 46（12）： 3460-3471.

[11] CHAWLA N V， BOWYER K W， HALL L O， et al. SMOTE： synthetic minority over-sampling technique [J]. Journal of Artificial Intelligence Research， 2011， 16（1）： 321-357.

[12] LAURIKKALA J. Improving identification of difficult small classes by balancing class distribution [C]// Proceedings of the 8th Conference on Artificial Intelligence in Medicine in Europe. Berlin： Springer， 2001： 63-66.

[13] KUBAT M， MATWIN S. Addressing the curse of imbalanced training sets： one-sided selection [C]// Proceedings of the 14th International Conference on Machine Learning. New York： ACM， 1997： 179-186.

[14] TAHIR M A， KITTLER J， MIKOLAJCZYK K， et al. A multiple expert approach to the class imbalance problem using inverse random under sampling [C]// Proceedings of the 8th International Workshop on Multiple Classifier Systems. Berlin： Springer， 2009： 82-91.

[15] IMRAN M， RAO V S， AMARASIMHA T， et al. A novel technique on class imbalance big data using analogous over sampling approach [J]. International Journal of Computational Intelligence Research， 2017， 13（10）： 2407-2417.

[16] LIMA C F L， de ASSIS F M， de SOUZA C P. Decision tree based on Shannon， Rényi and Tsallis entropies for intrusion tolerant systems [C]// Proceedings of the 5th International Conference on Internet Monitoring and Protection. Piscataway， NJ： IEEE， 2010： 117-122.

[17] BOONCHUAY K， SINAPIROMSARAN K， LURSINSAP C. Decision tree induction based on minority entropy for the class imbalance problem [J]. Pattern Analysis and Applications， 2017， 20（3）： 769-782.

[18] KIRSHNERS A， PARSHUTIN S， GORSKIS H. Entropy-based classifier enhancement to handle imbalanced class problem [J]. Procedia Computer Science， 2017， 104： 586-591.

[19] LI X， ZHAO H， ZHU W. A cost sensitive decision tree algorithm with two adaptive mechanisms [J]. Knowledge-Based Systems， 2015， 88： 24-33.

[20] 鄭燕，王楊，郝青峰，等.用于不平衡數(shù)據(jù)分類的代價敏感超網(wǎng)絡(luò)算法[J].計算機應(yīng)用，2014，34（5）：1336-1340.（ZHENG Y， WANG Y， HAO Q F， et al. Cost-sensitive hypernetworks for imbalanced data classification [J]. Journal of Computer Applications， 2014， 34（5）： 1336-1340.）

[21] LEE S J， XU Z， LI T， et al. A novel bagging C4.5 algorithm based on wrapper feature selection for supporting wise clinical decision making [J]. Journal of Biomedical Informatics， 2018， 78： 144-155.

[22] QUINLAN J R. C4.5： Programs for Machine Learning [M]. San Francisco， CA： Morgan Kaufmann， 1993：17-26.

[23] FRANK E， HALL M A， WITTEN L H. The WEKA workbench. online appendix for “Data mining： practical machine learning tools and techniques” [EB/OL]. （2016-11-22） [2018-05-04]. https：//www.cs.waikato.ac.nz/ml/weka/Witten_et_al_2016_appendix.pdf.

[24] DHANABAL L， SHANTHARAJAH S P. A study on NSL-KDD dataset for intrusion detection system based on classification algorithms [J]. International Journal of Advanced Research in Computer and Communication Engineering， 2015， 4（6）： 446-452.

[25] ADEPU S， MATHUR A. An investigation into the response of a water treatment system to cyber attacks [C]// Proceedings of the 17th IEEE International Symposium on High Assurance Systems Engineering. Washington， DC： IEEE Computer Society， 2016： 141-148.

[26] GOH J， ADEPU S， JUNEJO K N， et al. A dataset to support research in the design of secure water treatment systems [C]// Proceedings of the 11th International Conference on Critical Information Infrastructures Security. Berlin： Springer， 2016： 88-99.