一種改進的決策樹算法在入侵檢測中的應用

摘 ?要：為了改進傳統(tǒng)決策樹算法存在的一些問題，文章結(jié)合粗糙集理論提出一種基于粒度決策熵的決策樹算法DTGDE。DTGDE算法采用粒度決策熵作為分裂屬性的選擇標準。在該信息熵模型中，粒度決策熵可以同時表示知識的完備性和知識的粒度大小，因此，利用粒度決策熵來選擇分裂屬性能夠更加全面地考察每個屬性對決策分類的貢獻。實驗結(jié)果表明，DTGDE算法具有比現(xiàn)有決策樹算法更好的入侵檢測性能。

關(guān)鍵詞：決策樹;粗糙集;信息熵;粒度決策熵;屬性重要性;入侵檢測

中圖分類號：TP309 ? ? 文獻標識碼：A 文章編號：2096-4706（2020）23-0147-07

The Application of an Improved Decision Tree Algorithm in Intrusion Detection

ZHANG Minyu

（College of Information Science and Technology，Qingdao University of Science & Technology，Qingdao ?266061，China）

Abstract：In order to improve the existing problems of traditional decision tree algorithm，a decision tree algorithm DTGDE based on granular decision entropy is proposed by combining with rough set theory. DTGDE algorithm uses granular decision entropy as the selection standard of splitting attributes. In the information entropy model，the granular decision entropy can represent both the completeness of knowledge and the granularity size of knowledge. Therefore，using granular decision entropy to select split attributes can more comprehensively investigate the contribution of each attribute to decision classification. Experimental results show that DTGDE algorithm has better intrusion detection performance than existing decision tree algorithms.

Keywords：decision tree;rough set;information entropy;granular decision entropy;significance of attribute;intrusion detection

0 ?引 ?言

決策樹算法作為一種分類方法，其優(yōu)點在于分類精度高、運行速度快、模型理解容易等方面，一直都被廣泛應用在各類數(shù)據(jù)挖掘問題中。決策樹算法在獲取決策規(guī)則的過程中，需要不斷選擇其中一個屬性作為分裂屬性來生成子樹，于是分裂屬性的選擇標準對決策樹的性能來說至關(guān)重要。目前，Quinlan提出的傳統(tǒng)決策樹算法ID3和C4.5最為經(jīng)典，這兩種算法選擇分裂屬性的標準分別是信息增益和信息增益率[1，2]。然而，在實際應用場景中，使用的數(shù)據(jù)往往存在著大量的冗余屬性，同時由于此類算法得到的決策樹子樹有重復，需要反復檢驗決策樹中的某一屬性。因此，傳統(tǒng)決策樹算法的計算量較大，存在著計算開銷大、分類精度不夠高等問題。

Pawlak提出的粗糙集理論可以用來解決不確定、不精確知識的處理問題[3，4]。目前，很多學者也將粗糙集理論應用于決策樹的構(gòu)建。決策樹與粗糙集相結(jié)合，可以優(yōu)勢互補，從而解決傳統(tǒng)決策樹算法的計算開銷大、分類精度不夠高等問題?；诖植诩碚搧砀倪M傳統(tǒng)的決策樹算法一直是決策樹領(lǐng)域的熱門研究方向[5-8]，其研究重點主要包括：分裂屬性的選擇標準、屬性重要性的計算、屬性約簡等等?；诖植诩碚摰臎Q策樹算法不僅可以應用在垃圾郵件過濾[9]，也可以應用在政府決策輔助[10]、產(chǎn)品缺陷檢測[11]和醫(yī)療衛(wèi)生科技應用[12]等。

筆者是青島科技大學信息科學與技術(shù)學院在讀碩士研究生，研究方向是網(wǎng)絡安全技術(shù)，在導師帶領(lǐng)的課題組中，研究內(nèi)容多與粗糙集理論相關(guān)。在受到課題組所發(fā)表的論文啟發(fā)后，結(jié)合相關(guān)粗糙集理論與入侵檢測算法，提出一種新的基于粒度決策熵的決策樹算法，取得了相比原算法更好的結(jié)果。

該文主要關(guān)注于如何利用粗糙集的方法來為決策樹算法選擇合適的分裂屬性。筆者將從粗糙集的角度構(gòu)建一種新的信息熵模型，并利用該模型來為決策樹算法選擇分裂屬性。近年來，有不少研究者基于粗糙集理論提出了不同的信息熵模型[13-16]，這些學者將這些信息熵模型作為決策樹算法分裂屬性的選擇標準，從而得到了一些改進的決策樹算法。文獻[13]提出一種決策樹算法，該算法用粗糙度定義信息熵，能夠較為全面地反映每個屬性的貢獻;文獻[14]提出的決策樹算法，除了采用粗糙度，還結(jié)合屬性依賴度來定義信息熵，更為充分地考慮到?jīng)Q策屬性對每個條件屬性的依賴程度;文獻[15]提出的屬性選擇算法，通過定義不同屬性的相對重要性來獲取選擇屬性的規(guī)則;文獻[16]提出的決策樹算法中，分裂屬性的選擇標準是從一種基于變精度加權(quán)平均粗糙度中得到的。

雖然現(xiàn)有的基于粗糙集的決策樹算法具有很多優(yōu)點，但是也存在一些問題。例如，文獻[13]和[14]所提出的決策樹算法都是采用粗糙度這一粗糙集的基本概念來構(gòu)建信息熵模型（即相對決策熵或依賴決策熵）。作為粗糙集理論中的一個重要概念，粗糙度雖然可以用于度量知識的完備性，但是知識的粒度大小卻不能有效表示。這就造成文獻[13]和[14]中所定義的信息熵模型都不能反映知識的粒度大小。當給定的知識IND（B）的粒度變小了（即IND（B）所對應的論域劃分的粒度變細），相對決策熵（或依賴決策熵）卻保持不變，這顯然是不合理的。一般來說，使用信息熵來表示一個系統(tǒng)的不確定性，當知識所對應的論域劃分的粒度變細，信息熵（不確定性）應該下降。由于知識粒度的粗細變化并不能在上述信息熵模型中體現(xiàn)出來，因此，上述決策樹算法分裂屬性的選擇結(jié)果就不能完全符合真實情況，分類結(jié)果必然會產(chǎn)生一定的偏差。為了針對上述問題，有必要提出一種新的信息熵模型，即在構(gòu)建信息熵模型時同時考慮知識的完備性和知識的粒度大小。

基于上述考慮，該文將引入一個新的信息熵模型——粒度決策熵。在決策樹算法中，筆者通過粒度決策熵來選擇分裂屬性，從而得到一種新的決策樹算法DTGDE，此外，筆者還將DTGDE算法應用于網(wǎng)絡入侵檢測。粒度決策熵是對文獻[13]中所定義的相對決策熵模型的一種有效改進。與相對決策熵不同，粒度決策熵不僅考慮到知識的完備性問題，而且還考慮到知識的粒度粗細問題。具體而言，粒度決策熵是將粗糙度這一粗糙集的基本概念與苗奪謙等提出的知識粒度概念有機地結(jié)合在一起，即知識IND（B）的完備性可以通過粗糙度來描述，同時知識IND（B）的粒度粗細可以用知識粒度來表示。由于粒度決策熵能夠同時對以上兩者進行有效度量，從而使得在利用粒度決策熵來選擇分裂屬性時可以更加全面地考察每個屬性對決策分類的貢獻，因此，相對于現(xiàn)有的信息熵模型（例如，相對決策熵、依賴決策熵），粒度決策熵更適合于作為決策樹算法的分裂屬性選擇標準。此外，由于在DTGDE算法中筆者還考慮到了屬性之間的依賴性和相關(guān)性，從而彌補了傳統(tǒng)決策樹算法對于屬性的依賴性強調(diào)不夠這一缺點。

為了將DTGDE算法更好地應用于網(wǎng)絡入侵檢測，該文采用基于粒度決策熵的屬性約簡算法來對數(shù)據(jù)集中的冗余以及不相關(guān)屬性進行剔除?；诹６葲Q策熵的屬性約簡算法使用粒度決策熵模型重新定義了屬性重要性，此外，采用了增量式學習和計數(shù)排序的思想，可以有效提升入侵檢測的效率。通過在KDD Cup 1999數(shù)據(jù)集上的實驗表明，相對于現(xiàn)有的決策樹算法，DTGDE算法具有更好的入侵檢測性能，此外，其在入侵檢測效率（即建模時間）上也表現(xiàn)較好。

1 ?相關(guān)概念介紹

1.1 ?信息表與決策表

定義1：信息表S可以用一個四元組表示為：S=（U，A，V，f），其中，U為一個非空有限的對象集，即論域;A為非空有限的屬性集;V為所有屬性值域的總和，即V= Ua∈AVa，其中Va為a的值域;f：U×A→V為一個映射關(guān)系，使得對任意的屬性a∈A以及對象x∈U，都有f（x，a）∈Va成立。

信息表中的非空有限屬性集A可以劃分為不相交的兩個屬性子集——條件屬性集和決策屬性集，分別用C和D表示。這樣劃分條件屬性集和決策屬性集的信息表被稱為決策表，表示為：DT=（U，C，D，V，f）。

1.2 ?不可分辨關(guān)系

定義2：給定決策表DT=（U，C，D，V，f），對任意B?C∪D，可確定一個不可分辨關(guān)系IND（B），其定義為：

IND（B）={（x，y）∈U×U：?a∈B，（f（x，a）=f（y，a））}

論域U可以通過IND（B）劃分為多個等價類，這樣一個劃分可以記為U/IND（B）或U/B。

1.3 ?上近似與下近似

定義3：給定決策表DT=（U，C，D，V，f），對任意B?C∪D和X?U，X的B-上近似和B-下近似可分別定義為：

=∪{[x]B∈U/IND（B）：[x]B∩X≠Φ}

=∪{[x]B∈U/IND（B）：[x]B?X}

1.4 ?粗糙度

定義4：給定決策表DT=（U，C，D，V，f），對任意B?C∪D和X?U（X≠Φ），X的B-粗糙度ρB（X）定義為：

ρB（X）=|-|/||

1.5 ?相對正區(qū)域

定義5：給定決策表DT=（U，C，D，V，f），對任意B?C，定義決策屬性集D的B-正區(qū)域PosB（D）為：

PosB（D）=

1.6 ?屬性依賴度

定義6：給定決策表DT=（U，C，D，V，f），對任意c∈C，D相對于c的依賴度γC（D）定義為：

γC（D）=|Pos{C}（D）|/|U|

1.7 ?知識粒度

定義7：給定決策表DT=（U，C，D，V，f），對任意B?C，令U/IND（B）={X1，X2，…，Xt}為U/IND（B）對U的劃分，其中Xi?U（1≤i≤t），B的知識粒度[17]GK（B）定義為：

GK（B）=

1.8 ?相對決策熵

定義8：給定決策表DT=（U，C，D，V，f），對任意B?C，令U/IND（D）={D1，D2，…，Dt}為IND（D）對U的劃分，決策屬性集D在知識IND（D）下的相對決策熵[13]RDE（D，B）定義為：

RDE（D，B）=（Di）log2（ρB（Di）+1）

其中，ρB（Di）為集合Di的B-粗糙度，1≤i≤t。

2 ?粒度決策熵

文獻[13]中所提出的相對決策熵模型主要采用粗糙度這一粗糙集的基本概念來定義。引入苗奪謙等提出的知識粒度概念可以對這一信息熵模型進行改進，從而得到更加合理的模型——粒度決策熵。

2.1 ?粒度決策熵

定義9：給定決策表DT=（U，C，D，V，f），對任意B?C，令U/IND（D）={D1，D2，…，Dm}為IND（D）對U的劃分。決策屬性集D相對于條件屬性子集B的粒度決策熵定義為：

GDE（D，B）=GK（B）×（Di）log2（ρB（Di）+1）

其中，GK（B）為知識IND（B）的粒度大小，ρB（Di）為集合Di的B-粗糙度，1≤i≤m。通過結(jié)合知識粒度和粗糙度的概念定義信息熵模型，相對于現(xiàn)有的信息熵模型（例如相對決策熵），粒度決策熵不僅考慮了知識的完備性問題，而且還考慮到知識的粒度粗細問題，可以更加全面地考察決策表中每個條件屬性對于決策分類的貢獻。因此，在決策樹算法中，粒度決策熵相對于其他信息熵，更適合于作為分裂屬性選擇標準。

2.2 ?基于粒度決策熵的屬性重要性

定義10：給定決策表DT=（U，C，D，V，f），對于任意B?C和a∈C-B，將屬性a在決策表DT中相對于B和D的重要性Sig（a，B，D）定義為：

Sig（a，B，D）=GDE（D，B）-GDE（D，B∪{a}）

其中，GDE（D，B）為決策屬性集D相對于條件屬性子集B的粒度決策熵。

3 ?基于粒度決策熵的決策樹算法DTGDE

在本節(jié)中，該文給出基于粒度決策熵的決策樹算法DTGDE，并分析其復雜度。

3.1 ?DTGDE算法

該算法輸入訓練集作為決策表，在算法中生成相應的決策樹后，輸出的內(nèi)容為此決策樹的規(guī)則集：

輸入：決策表T1=（U，C，D，V，f）。

輸出：規(guī)則的集合R。

3.2 ?算法流程

DTGDE算法Function Main中先離散化決策表中的連續(xù)屬性，經(jīng)過屬性約簡后，使用約簡的決策表在Function Decision_Tree中生成決策樹，最終遍歷該決策樹獲取規(guī)則集：

Function Main（T1）：

（1）對決策表T1中條件屬性集C的每個連續(xù)型屬性進行離散化，得到離散化之后的決策表T2=（U2，C，D，V2，f2）。

（2）對決策表T2中的條件屬性集C進行屬性約簡，結(jié)果記錄為Red。

（3）根據(jù)約簡Red，去掉決策表T2中的冗余屬性和不相關(guān)屬性以及U2中的重復記錄，從而得到約簡之后的決策表T3=（U3，Red，D，V3，f3）。

（4）根據(jù)決策表T3調(diào)用函數(shù)Decision_Tree（T3）生成一個決策樹。

（5）遍歷該生成的決策樹，得到規(guī)則集合R。

（6）返回R。

使用Function Decision_Tree對當前使用的決策表T0=（U′，C′，D，V′，F(xiàn)′）通過計算得到粒度決策熵來獲取合理的分裂屬性，最終生成決策樹：

Function Decision_Tree（T0）：

（1）令B=Red-C′。

（2）如果B=Φ，則令GDE（D，B）=0;如果B≠ Φ，則首先對U′進行計數(shù)排序，然后分別計算出劃分U′/IND（D）={D1，D2，…，Dm}，U′/IND（B）和U′/IND（B∪D）。另外，計算知識粒度GK（B），并且對任意Di∈U′/IND

（D），計算粗糙度ρB（Di），1≤i≤m。最后，計算粒度決策熵GDE（D，B）。

（3）對c∈C′，循環(huán)執(zhí)行：

1）通過對U′進行計數(shù)排序，來分別計算出劃分U′/IND（B∪{c}）和U′/IND（B∪{c}∪D）。

2）計算知識粒度GK（B∪{c}），并且對每個等價類Di∈U′/IND（D），計算Di相對于B∪{c}的粗糙度ρB∪{c}（Di），1≤i≤m。

3）計算粒度決策熵GDE（D，B∪{c}）。

4）計算屬性c的屬性重要性Sig（a，B，D）=GDE（D，B）-GDE（D，B∪{a}）。

（4）將分裂屬性s標記為C′中屬性重要性最大的屬性。

（5）如果C′中有多個屬性的重要性同為最大值（令s′?C表示這些屬性的集合），則分別對任意屬性a∈s′，計算D對屬性a的依賴度γa（D），此時將分裂屬性標記為γa（D）值最大時的屬性a′。如果同時有多個屬性計算得到的γa（D）值相同且都為最大值，那么將分裂屬性標記為其中序號靠前的屬性。

（6）創(chuàng)建節(jié)點P，用前面所選擇的分裂屬性s來標記P，并且令C′=C′-{s}，即把s從C′中刪除。

（7）計算不可分辨關(guān)系IND（{s}）所對應的劃分U′/IND（{s}）={E1，…，Ek}。

（8）對任意Ei∈U′/IND（{s}），循環(huán)執(zhí)行：

1）創(chuàng)建節(jié)點P的一個子樹，用屬性值v標記該子樹，其中v=f ′（e，v），e∈Ei。

2）如果Ei中所有樣本都屬于同一類別d0，用該類別d0標記一個新的葉子節(jié)點Pb。

3）如果Ei中所有樣本屬于不同類別，并且C′不能再往下分，則用出現(xiàn)次數(shù)最多的類別dc標記一個新的葉子節(jié)點Pc。

4）如果Ei中的樣本屬于不同類別，并且C′可以繼續(xù)往下分，則創(chuàng)建決策表T0的一個子決策表Tc=（Ei，C′，D，Vc，fc），并且調(diào)用Decision_Tree（Tc）來遞歸生成子樹。

在算法DTGDE中，對任意B?C′，處理時首先對U′進行計數(shù)排序，然后再計算U′/IND（B）[18]。對比傳統(tǒng)計算方法，計算U′/IND（B）的時間復雜度從O（n2）降低為O（m×n），其中m=|B|。根據(jù)定義10，計算a的屬性重要性Sig（a，B，D）的時間復雜度為O（m×n）。根據(jù)定義6，計算屬性依賴度γa（D）的時間復雜度為O（m×n）。因此，在最差的情形，算法DTGDE的Function Main中第（4）步建樹的時間復雜度為O（|Red|3×|U3|）。此外，算法DTGDE的時間復雜度還取決于Function Main函數(shù)中第（1）步所選擇的離散化方法的復雜度以及第（2）步所選擇的屬性約簡方法的復雜度。

3.3 ?數(shù)據(jù)集預處理

在算法DTGDE的數(shù)據(jù)集預處理中，該文使用以下三種操作。

3.3.1 ?離散化連續(xù)屬性

入侵檢測使用的數(shù)據(jù)集KDD Cup 1999有42個特征屬性，其中的條件屬性中有34個屬性是連續(xù)型的[19]。因為決策樹等數(shù)據(jù)挖掘算法更適合處理離散型屬性，所以需要通過一定的方法處理使用的數(shù)據(jù)集，這樣的處理過程被稱為“離散化”。目前，離散化方法有無監(jiān)督和有監(jiān)督兩類。該文中使用一種常用的無監(jiān)督離散化方法——等寬度離散化，來處理數(shù)據(jù)集中的連續(xù)屬性。

3.3.2 ?數(shù)據(jù)集重采樣

由于實驗數(shù)據(jù)集中不同類別樣本之間的數(shù)量處于嚴重不平衡狀態(tài)。這將會導致對大類樣本的過擬合問題，分類模型將會偏向于大類樣本。對于類別不平衡問題，可以通過重采樣的方法來消除因不平衡數(shù)據(jù)造成的影響[20]。在該文的實驗過程中，使用上采樣和下采樣結(jié)合的方法，即SMOTE+ENN的方法對數(shù)據(jù)集進行重采樣[21]。

3.3.3 ?約簡冗余和不相關(guān)屬性

在實際應用中，并非所有屬性都是影響決策的因素。如果能夠有效地剔除冗余和不相關(guān)屬性，這將必然會減少檢測時間同時提高檢測效率[22-25]。目前，基于信息熵的屬性約簡算法、基于可分辨矩陣的屬性約簡算法和基于正區(qū)域的屬性約簡算法是常用的屬性約簡算法[26]。在該文的實驗過程中，采用基于粒度決策熵的屬性約簡方法來進行屬性約簡。該約簡算法采用了增量式學習和計數(shù)排序的思想，并使用粒度決策熵的概念重新定義了屬性重要性，可以得到更有效的約簡結(jié)果。

4 ?實驗

實驗所采用的數(shù)據(jù)集是KDD Cup 1999數(shù)據(jù)集[19]，該數(shù)據(jù)集是從一個模擬的美國空軍局域網(wǎng)上采集來的9個星期的網(wǎng)絡連接數(shù)據(jù)，接近有500萬條記錄。每條連接記錄中包含了41個屬性和1個類別標識，類別標識用來表示該條連接記錄是正常的，或者是某個具體的攻擊類型。實驗的硬件環(huán)境為：Intel 2.40 GHz處理器，8 GB內(nèi)存。操作系統(tǒng)：Windows10 64位。

筆者將文章所提出的DTGDE算法與五種常見的決策樹算法進行了性能對比。這五個對比算法分別是：ID3、C4.5、RandomTree、REPTree和RandomForest。DTGDE算法采用Java語言實現(xiàn)，ID3、C4.5、RandomTree、REPTree和RandomForest這五個對比算法則直接使用Weka平臺中所提供的算法[27]。

4.1 ?實驗數(shù)據(jù)

由于KDD Cup 1999的數(shù)據(jù)總量太大，該文只選取其子集“kddcup.data_10_percent”[19]來進行實驗，該子集的樣本數(shù)量為總量的10%。在KDD Cup 1999數(shù)據(jù)集中，class屬性的取值可分為以下五大類：

（1）Normal;

（2）DoS;

（3）Probe;

（4）U2R;

（5）R2L。

預處理時，為了便于操作，先將源文件中的符號型取值

轉(zhuǎn)化為數(shù)值型取值，例如屬性“service”中有“TCP”“UDP”

“ICMP”三類符號性取值，預處理時將其分別替換成“0”

“1”“2”這三個數(shù)值型取值。對現(xiàn)有實驗環(huán)境而言，10%-KDD數(shù)據(jù)集仍然太大，而且其中的入侵行為偏向于特定的攻擊類型（例如，超過一半的記錄為Smurf類型的攻擊）。為了解決這些問題，該文仿照陳仕濤等的做法[28]，對于kddcup.data_10_percent數(shù)據(jù)集中的各種攻擊類型和正常連接，依據(jù)不同的比率采用隨機不放回地方式抽取一定數(shù)量的記錄，最終得到數(shù)據(jù)集“Final_Dataset”。其中不同攻擊類型樣本和正常樣本的數(shù)目如表1所示。

4.2 ?實驗步驟

4.2.1 ?屬性離散化

該文使用Weka中提供的無監(jiān)督離散化算法Equal-width Binning（EW）來離散化Final_Dataset中的連續(xù)型屬性。同時，通過設置不同的bins值，分別對該數(shù)據(jù)集中的連續(xù)型屬性進行離散化，得到不同離散化程度的數(shù)據(jù)集。在該文章中，選取其中26個連續(xù)屬性分別進行離散化;在不需要進行離散化的15個屬性中，其中有7個是字符型數(shù)值，本身就是離散的，另外8個屬性雖然是連續(xù)的，但是由于不同屬性取值的數(shù)量較少，不需要進行離散化處理。

4.2.2 ?數(shù)據(jù)重采樣

Final_Dataset中仍然存在著類別不平衡問題，例如，屬于類別DoS的樣本數(shù)量約是屬于類別U2R的樣本數(shù)量的167倍。為了解決這個問題，該文首先采用SMOTE+ENN方法對數(shù)據(jù)進行混合采樣[21]。隨后，對于經(jīng)過離散化和混合采樣后的數(shù)據(jù)集，將其隨機分成訓練集（占70%）和測試集（占30%）兩個部分?；旌喜蓸又蟮挠柧毤蜏y試集情況如表2所示。

4.2.3 ?屬性約簡

采用基于粒度決策熵的屬性約簡算法，對經(jīng)過數(shù)據(jù)重采樣生成的訓練集進行屬性約簡。用經(jīng)過屬性約簡后的屬性集用于DTGDE算法，建立決策樹模型。

4.2.4 ?建立決策樹與獲得規(guī)則集

對于DTGDE算法，該文使用Java語言來實現(xiàn)。DTGDE算法在經(jīng)過預處理和屬性約簡之后的訓練集上創(chuàng)建決策樹，并得到相應的規(guī)則集。

對于ID3、C4.5、RandomTree、REPTree和RandomForest算法，該文直接使用Weka所提供的算法在預處理之后的訓練集上創(chuàng)建決策樹，并得到相應的規(guī)則集[27]。

4.2.5 ?分類測試

對已經(jīng)獲取產(chǎn)生的各個規(guī)則集，使用測試集進行測試。對于DTGDE算法，筆者先對測試集的預測結(jié)果進行處理，用多數(shù)類投票的方法處理復合葉子節(jié)點Pc，然后使用測試集中的決策屬性值與預測結(jié)果生成混淆矩陣，得到算法的召回率和精確率，通過分析F1-value來得到該算法的檢測結(jié)果;對于ID3、C4.5、RandomTree、REPTree和RandomForest算法，分類測試同樣借助于Weka來完成[27]，與測試集標簽結(jié)果對比，得到混淆矩陣，通過精確率和召回率計算出F1-value，最終得到該算法的檢測結(jié)果。

4.3 ?實驗結(jié)果

F-值（F-value）可以來衡量分類模型的性能。分類模型的精確率和召回率越高時，F(xiàn)-值越高。它的計算公式為：

Fβ=

其中，β為一個參數(shù)，P為精確率（Precision），R為召回率（Recall）[29]。該實驗中取參數(shù)β=1，即計算F1-value。

不同算法在bins=3時的分類結(jié)果如表3所示。

從表3可以看出，在bins=3時，DTGDE算法的檢測性能明顯要好于其他算法。例如，DTGDE算法的精確率、召回率和F1-value比ID3算法分別要高0.6%，而DTGDE算法的精確率、召回率和F1-value比C4.5算法則分別要高0.9%、0.8%和0.9%。另外，DTGDE算法的精確率、召回率和F1-value也要顯著優(yōu)于RandomTree、REPTree和RandomForest這三個算法。

不同算法在bins=3時的建模時間如圖1所示。

從圖1可以看出，DTGDE算法的建模時間要稍微多于RandomTree算法，這是因為RandomTree算法通過隨機選擇若干個屬性，而不是全部屬性來構(gòu)建決策樹，因此，其建模時間會大幅降低。不過，由于DTGDE算法使用經(jīng)過屬性約簡之后的數(shù)據(jù)集，其在建模時間上也表現(xiàn)較好，DTGDE算法的建模時間明顯少于ID3、C4.5、REPTree和RandomForest這四個算法。因此，從總體上看（即綜合考慮檢測性能和建模時間），DTGDE算法的表現(xiàn)仍然是最優(yōu)的。

不同算法在bins=5時的分類結(jié)果如表4所示。

從表4可以看出，在bins=5時，DTGDE算法的檢測性能明顯要好于其他算法。例如，DTGDE算法的精確率、召回率和F1-value比ID3算法分別要高0.4%，而DTGDE算法的精確率、召回率和F1-value比C4.5算法則分別要高0.7%。另外，DTGDE算法的精確率、召回率和F1-value也要顯著優(yōu)于RandomTree、REPTree和RandomForest這三個算法。

不同算法在bins=5時的建模時間如圖2所示。

從圖2可以看出，雖然DTGDE算法的建模時間要多于RandomTree算法，但卻顯著少于ID3、C4.5、REPTree和RandomForest這四個算法。因此，從總體上看（即綜合考慮檢測性能和建模時間），DTGDE算法的表現(xiàn)仍然是最優(yōu)的。

5 ?結(jié) ?論

該文基于粒度決策熵和屬性依賴性設計出一種新的分裂屬性選擇標準，并給出了相應的決策樹算法DTGDE。在建樹之前，DTGDE算法首先利用基于粒度決策熵的屬性約簡技術(shù)降低決策樹的規(guī)模。在KDD Cup 1999數(shù)據(jù)集上的實驗表明，DTGDE算法對于網(wǎng)絡入侵的檢測效果要好于其他算法。在訓練時間方面，DTGDE算法比傳統(tǒng)決策樹算法也有較大提升，從而使得入侵檢測更加高效。

參考文獻：

[1] QUINLAN R J. Induction of decision trees [J].Machine Learning，1986，1（1）：81-106.

[2] QUINLAN R J. C4.5：Programs for Machine Learning [M].San Francisco：Morgan Kaufmann Publishers Inc.，1993：1-131.

[3] PAWLAK Z. Rough sets [J].International Journal of Computer & Information Sciences，1982，11（5）：341-356.

[4] PAWLAK Z. Rough Sets：Theoretical Aspects of Reasoning about Data [M].Norwell：Kluwer Academic Publishing，1991：1-231.

[5] LEI Z J，WU L L. Construction of Decision Tree Based on Rough Sets Theory [J].Advanced Materials Research，2012（433-440）：5208-5213.

[6] 王蓉，劉遵仁，紀俊.基于屬性重要度的決策樹算法 [J].計算機科學，2017，44（S2）：129-132.

[7] 余建軍，張瓊之.基于粗糙集的決策樹ID3算法 [J].計算機系統(tǒng)應用，2020，29（4）：156-162.

[8] 林芷欣.基于鄰域粗糙集的屬性約簡算法研究及應用 [D].山東青島：青島大學，2020.

[9] 王靖，王興偉，趙悅.基于變精度粗糙集決策樹垃圾郵件過濾 [J].系統(tǒng)仿真學報，2016，28（3）：705-710.

[10] LIU D，LI T R，LIANG D C. Three-way Government Decision Analysis With Decision-Theoretic Rough Sets [J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2012，20（supp1）：119-132.

[11] 吳學輝.基于粗糙集的決策樹在產(chǎn)品缺陷檢測中的應用 [J].太原師范學院學報（自然科學版），2015，14（3）：37-41.

[12] 譚永奇，樊建聰，任延德，等.改進的屬性約簡算法及其在肝癌微血管侵犯預測中的應用 [J].計算機應用，2019，39（11）：3221-3226.

[13] 江峰，王春平，曾惠芬.基于相對決策熵的決策樹算法及其在入侵檢測中的應用 [J].計算機科學，2012，39（4）：223-226.

[14] 王希玲，江峰，張友強，等.基于依賴決策熵的決策樹分類算法 [J].青島科技大學學報（自然科學版），2016，37（6）：687-692.

[15] 陳波，于泠，吉根林.基于條件信息熵的網(wǎng)絡攻擊特征選擇技術(shù) [J].小型微型計算機系統(tǒng)，2008，29（3）：428-432.

[16] 劉帥.基于決策樹和信息熵的屬性約簡算法研究 [D].沈陽：東北大學，2010.

[17] 苗奪謙，范世棟.知識粒度的計算及其應用 [J].系統(tǒng)工程理論與實踐，2002，22（1）：48-56.

[18] 徐章艷，劉作鵬，楊炳儒，等.一個復雜度為max（O（|C||U|），O（|C|^2|U/C|））的快速屬性約簡算法 [J].計算機學報，2006，29（3）：391-399.

[19] UCI. KDD Cup 1999 Dataset [DB/OL].（1999-10-28）.http：//kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

[20] ESTABROOKS A，TAEHO J，JAPKOWICZ N. A Multiple Resampling Method for Learning from Imbalanced Data Sets [J].Computational Intelligence，2004，20（1）：18-36.

[21] Github. imblearn.combine.SMOTEENN [EB/OL].（2018-01-17）.http：//glemaitre.github.io/imbalanced-learn/generated/imblearn.combine.SMOTEENN.html.

[22] 曲朝陽，陳帥，楊帆，等.基于云計算技術(shù)的電力大數(shù)據(jù)預處理屬性約簡方法 [J].電力系統(tǒng)自動化，2014，38（8）：67-71.

[23] 劉金平，張五霞，唐朝暉，等.基于模糊粗糙集屬性約簡與GMM-LDA最優(yōu)聚類簇特征學習的自適應網(wǎng)絡入侵檢測 [J].控制與決策，2019，34（2）：243-251.

[24] 邵瑞.基于粗糙集的高維數(shù)據(jù)高效屬性約簡研究與應用 [D].重慶：重慶郵電大學，2018.

[25] 余建航.基于粗糙集的幾類廣義信息系統(tǒng)知識發(fā)現(xiàn)與決策方法研究 [D].哈爾濱：哈爾濱工業(yè)大學，2020.

[26] 楊傳健，葛浩，汪志圣.基于粗糙集的屬性約簡方法研究綜述 [J].計算機應用研究，2012，29（1）：16-20.

[27] WITTEN L H，F(xiàn)RANK E，HALL M A. Data Mining：Practical Machine Learning Tools and Techniques with Java Implementations [M].San Francisco：Morgan Kaufmann Publishers Inc.，2000：416.

[28] 陳仕濤，陳國龍，郭文忠，等.基于粒子群優(yōu)化和鄰域約簡的入侵檢測日志數(shù)據(jù)特征選擇 [J].計算機研究與發(fā)展，2010，47（7）：1261-1267.

[29] Cambridge University Press. Evaluation of clustering [EB/OL].（2009-04-07）.https：//nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html.

作者簡介：張旻宇（1993—），男，漢族，江西永豐人，碩士研究生在讀，研究方向：網(wǎng)絡安全技術(shù)。