一種基于MMTD的決策樹算法的研究?

朱俚治

（南京航空航天大學信息中心南京210016）

決策樹是一種常用的分類算法，自從ID3算法出現(xiàn)以來相關人員對該算法進行了不同程度的改進，由此出現(xiàn)了多種決策樹算法。在決策樹生成之時都采用遞歸算法來實現(xiàn)決策樹結(jié)點的分裂，如果結(jié)點的信息增益越大，那么該結(jié)點被分裂的幾率就越大。目前的ID3算法和C4.5算法中的信息增益成為結(jié)點是否被分裂的重要依據(jù)，因此根據(jù)決策樹的結(jié)點進行分裂時信息增益所起作用的特點，論文提出了另外一種衡量信息增益大小的算法，該算法具有衡量公式以及核心算法——MMTD算法，論文的創(chuàng)新之處在于將MMTD算法在決策樹中進行首次應用，并且在以MMTD為核心算法的基礎之上，實現(xiàn)了對信息增益大小的衡量。

MMTD；決策樹；信息熵；信息增益；ID3算法

Class NumberTP393

1 引言

在機器學習中決策樹是一種分類算法，通過對樣本的學習能夠從學習中產(chǎn)生分類規(guī)則。決策樹算法的優(yōu)點是不需要大量的學習樣本，通過有限的樣本學習和訓練就可以得出對數(shù)據(jù)分類時所需要的知識和規(guī)則。由于只需要有限的訓練樣本就能夠建立一棵有效的決策樹，因此決策樹與其它算法相比較該算法具有較高的學習效率。

最早決策樹算法是由Quinlan在1986年提出的，ID3算法對數(shù)據(jù)集分類的時候，取值只能是離散型數(shù)值，不能夠?qū)B續(xù)型屬性值進行分類。為了改進ID3算法，在此基礎之上出現(xiàn)了C4.5算法，該算法即可對離散型屬性值進行分類同時又可以對連續(xù)型屬性值進行分類。C4.5算法和ID3算法都是基于信息論的決策樹算法，然而C4.5算法彌補ID3算法的不足之處，成為目前較為受歡迎的決策樹算法［10～12］。盡管在ID3算法出現(xiàn)之后又出現(xiàn)眾多的決策樹算法，這些算法對ID3算法進行了改進工作，這些算法包括：CLS算法，CART算法，MBDT等算法。CLS算法的主要思想是首先構(gòu)造一棵空的決策樹，通過添加新的判斷節(jié)點來完善原來的決策樹，直到該決策樹能夠為訓練實例正確分類為止［3～6］。而MBDT算法最大的優(yōu)點是該算法與其它的算法相結(jié)合的情況下能夠提高決策樹算法分類時的效率［3～6，8］。以上的算法都是目前主要使用的決策樹算法，也是流行的決策樹算法。

在決策樹算法生成過程中有兩個重要步驟；第一步是創(chuàng)建決策樹，第二步使用決策樹對數(shù)據(jù)進行正確有效的分類。在決策樹生成的過程中，最重要的是決定節(jié)點分裂的因素，在部分的決策樹算法中采用信息論中的信息增益作為決策樹結(jié)點分裂時的標準，如果決策樹的某個結(jié)點的信息增益越大，那么該結(jié)點被分裂的可能性就越大。在ID3算法和C4.5算法之中都采用信息增益作為結(jié)點是否進行分裂的標準［10～12］。因此在本文中仍然采用信息增益率作為結(jié)點是否分裂的標準。

2 決策樹技術(shù)簡介

1）決策樹的特點

決策樹算法具體表現(xiàn)形式可以理解為是一棵樹，決策樹生成的時候從根結(jié)點開始以自頂向下的方式，采用遞歸算法不斷地對結(jié)點進行分裂從而形成一棵完整的決策樹。在決策樹中有三種不同的結(jié)點：根結(jié)點，葉結(jié)點和內(nèi)結(jié)點。根結(jié)點，葉結(jié)點和內(nèi)部結(jié)點在決策樹中都表示一個具有某種屬性或多個屬性的數(shù)據(jù)集。

在ID3算法和C4.5算法對結(jié)點進行分裂時，依據(jù)的是信息熵和信息增益來決定進行是否分裂，當決策樹的結(jié)點滿足某種條件的時候，就會進行結(jié)點的分裂和結(jié)點的終止分裂。根結(jié)點是決策樹最頂端的結(jié)點也是最大的結(jié)點，決策樹通過內(nèi)部結(jié)點的不斷地分裂中產(chǎn)生新的內(nèi)部結(jié)點和新的葉結(jié)點，葉結(jié)點代表的含義是該結(jié)點將不能繼續(xù)分裂，是某種屬性數(shù)據(jù)集的終止結(jié)點。而非葉結(jié)點的內(nèi)部結(jié)點是具有多種屬性的數(shù)據(jù)集，該結(jié)點根據(jù)信息熵和信息增益可以進一步分裂成為下一個葉結(jié)點或非葉結(jié)點。在決策樹中需要分裂的最大數(shù)據(jù)集就是根結(jié)點，內(nèi)結(jié)點是數(shù)據(jù)集分類的輸入，葉結(jié)點是數(shù)據(jù)集分類的輸出［3～6，10～12］。

2）決策樹算法的特點

ID3算法和C4.5算法都是采用遞歸算法對樹內(nèi)的結(jié)點不斷進行分裂。在決策樹結(jié)點分裂的過程中，從根結(jié)點到新結(jié)點的每一條路徑都相對應于一條相應的規(guī)則，在決策樹中的每一條規(guī)則都可以轉(zhuǎn)化為相應的IF-THEN規(guī)則。事實上IF-THEN規(guī)則能夠使得決策樹較快地對新數(shù)據(jù)進行分類，通過相應的IF-THEN規(guī)則以及結(jié)點屬性就可以新數(shù)據(jù)進行分類，生成新的決策樹，直到所有決策樹的結(jié)點都成為葉結(jié)點為止。

3 信息熵和信息增益簡介

3.1信息熵

1）ID3算法和C4.5算法都是基于信息論的決策樹算法，在信息論中信息量，信息熵，條件熵，平衡互信息量和信息增益是其中重要的基本概念。

在信息論中，采用信息熵來衡量信息的不確定性。在信源中由于信息的發(fā)送者發(fā)送的信息是多種多樣的，某些信息是已知的，而某些信息是未知的，對于已知的信息是可以確定的，而對于新信息是不能夠確定的，因此在信息源中某些信息存在不確定性。

2）d是某個信息熵的值

分析和討論：

（1）因此當d的值十分小的時候，這個時候訓練集的純度就越高。當信息熵值越接近于0時，這時訓練集的純度就越高，這時該數(shù)據(jù)集的確定性就越明顯。

（2）當d的值十分大的時候，這時信息熵的值就越大，同時這個訓練集的純度就越差。當訓練集的純度越差，那么這時該數(shù)據(jù)集存在不確定性的程度就越明顯。

根據(jù)以上的分析和討論有以下的結(jié)論：

信息熵：在信源中能夠反應整體信源的不確定性［10～12］。

某個信息源總是發(fā)送相同的信息，那么接收者就不存在不確定信息，此時信息源的信息熵就不為零。在信息源中造成不確定性的原因是發(fā)送者發(fā)送的信息不總是相同的信息，新信息是未知的信息，而這些新的未知信息就表示了信源的不確定性。由于在一棵決策樹中每一個內(nèi)部結(jié)點都是一個信源，因此信息熵能夠反應每一個內(nèi)部結(jié)點的不確定性。

3.2信息增益

1）信息增益與信息熵是兩個概念：信心增益：在ID3算法和C4.5算法中是計算數(shù)據(jù)集是否進行分類的依據(jù)，也就是決策樹的結(jié)點是否進行分裂的依據(jù)。而信息熵：信息不確定性的衡量指標。

2）d是某個信息增益

（1）當d的值十分小的時候，這時信息增益將十分地接近于0，當信息增益越小，這時該數(shù)據(jù)集被分裂的要求就越低。

（2）當d的值十分大的時候，這時信息增益越大遠遠大于0時，這時該數(shù)據(jù)集被分裂的要求就越明顯。

在決策樹形成過程中，最重要的部分是對決策樹分裂結(jié)點的選擇，最常用的計算方法是信息增益。由于信息增益越大的屬性分裂數(shù)據(jù)集的可能性越大［10～12，3～6］。因此，如果一個決策樹的某個結(jié)點的信息增益越大，那么該結(jié)點的數(shù)據(jù)集被分裂的可能性就越大，同樣如果一個決策樹的某個結(jié)點的信息增益越小，那么該結(jié)點的數(shù)據(jù)集被分裂的可能性就越小。在決策樹算法的結(jié)點分裂之中，要求每一次都選擇其信息增益最大的屬性作為決策樹的新結(jié)點。

4 MMTD算法技術(shù)簡介

4.1中介真值程度度量知識簡介

中介邏輯將事物的屬性描述成三種狀態(tài)，事物屬性的兩個對立面和對立面的中間過渡狀態(tài)。在中介真值程度度量方法中，提出了事物超態(tài)屬性概念，該方法符合中介思想事物的屬性并且被劃分為五種狀態(tài)：事物的兩個對立面，對立面的中間過渡狀態(tài)和事物超態(tài)對立面［1-2］。這里用符號表示為～P，P與╕P，超態(tài)+p與超態(tài)╕+p?，F(xiàn)用數(shù)軸將以上的描述的概念表達如下［1-2］：

圖1 中介真值程度度量一維函數(shù)圖

對數(shù)軸y=f(x)表示的含義有以下說明［1～2］：

數(shù)軸上用符號P與╕P分別表示事物對立面的兩個屬性，符號～P表示反對對立面的中間過渡狀態(tài)達事物的屬性。

1）如果數(shù)軸上數(shù)值點的位置逐步接近P，則事物A所具有P的屬性逐步增強。

2）如果該數(shù)值點的位置落在真值╕P和P的取范圍之間，則事物A的屬性就部分地具有╕P的屬性，同時又部分地具有P的屬性。

3）如果數(shù)軸上數(shù)值點的位置逐步接近╕P，則事物A所具有╕P的屬性逐步增強。

4.2中介真值程度度量中的距離比率函數(shù)

在中介真值程度度量的方法中，數(shù)軸上某數(shù)值點通過距離比率函數(shù)來計算事物所具有屬性的強弱。

定理1給定y=f(x)∈f(X)，ξ(h(y))=h(y)，則有［1～2］

1）當αF+εF＜y＜αT-εT時，gT(x)∈(0,1)，gF(x)∈(0,1)；

2）當y＞αT+εT時，gT(x)＞1；當y＜αF-εF時，gF(x)＞1；

3）當y＜αF-εF時，gT(x)＜0；當y＞αT+εT時，gF(x)＜0；

4）gT(x)+gF(x)=1。

（1）相對于P的距離比率函數(shù)［1～2］

5 MMTD方法的應用

5.1決策樹結(jié)點信息增益的計算

1）信息增益的衡量函數(shù)：

a表示某個值，d是某一個信息增益，δ是一個很小的值，δ≈0。

以下對信息增益值計算的分析和討論：

2）當a=d-δ＞0時

在一棵決策樹的生成過程中，如果決策樹的非葉結(jié)點的信息增益越大，則對該結(jié)點分裂的作用越大，信息增益越大，則該結(jié)點就越有可能被分裂多個其它的結(jié)點。為了描述和計算信息增益由小變大的過程，在本文中將信息增益與一個十分小的值進行比較和衡量，當信息增益與最小值的差值逐漸變大的過程中，則此時信息增益在不斷的變大過程中。

因此如果a＞0的值越大，d與δ的差值也就越大，并且這時d的值在變大的過程中。如果d在逐漸變大，當差值a大于0時或十分的大于0時，d就遠大于δ。當d變大的時候，這時結(jié)點的信息增益就越大。當信息增益越大，遠遠大于0時，這時該數(shù)據(jù)集被要求分裂的程度就越明顯。在本文中當結(jié)點的信息增益越強的時候，就用真值1表示。

如果結(jié)點數(shù)據(jù)集的信息增益越小，那么結(jié)點分裂的可能性就越小，因此當d與很小的值δ十分接近時，此時該信息增對結(jié)點分裂的意義將變得很小。信息增益越小，則該結(jié)點被分裂的可能性就越小。因此當d十分接近于δ，此時信息增益接近于0，該數(shù)據(jù)集被要求分裂的程度就越低。在本文中當結(jié)點的信息增益越弱的時候，就用真值0表示。

3）當a=d-δ＜0時

在一棵決策樹生成的過程中，非葉結(jié)點的內(nèi)部結(jié)點為了進行不斷地分裂生成新的結(jié)點，則需要該結(jié)點的信息增益盡可能的大。如果信息增益值十分接近于極小值δ時，該結(jié)點被分裂的可能性將十分的小，這樣的信息增益對結(jié)點的分裂是沒有作用的，因此以在本文提出的算法中要求信息增益盡可能的大，這樣對于決策樹的生成是有作用的。

這時信息增益將十分地接近于0，當信息增益的值越小越接近于0時，這時該數(shù)據(jù)集被分裂的要求就越低，這時訓練集的純度就越高。在本文中當結(jié)點的信息增益越弱的時候，使用真值0表示。

5.2中介對網(wǎng)絡流量的描述

以下用中介真值程度度量方法對決策樹的分裂做以下的研究：

數(shù)軸y=f(x)上有P，～P，╕P三個數(shù)據(jù)區(qū)域，P代表信息增益強，╕P代表信息增益弱，～P代表信息增益半強半弱。

5.3距離比率函數(shù)

從數(shù)軸上y=f(x)可以知道，在數(shù)軸上以～P為對稱中心，左右分別為╕P和P。

圖2 中介真值程度度量一維函數(shù)的應用

y=f(x)的值落在三個值域范圍(αr+εr,αl-εl)，(αr-εr,αr+εr)(αl-εl,αl+εl)。～P的區(qū)域為(αr+εr,αl-εl)，╕P的區(qū)域為(αr-εr,αr+εr)，P的區(qū)域為(αl-εl,αl+εl)。P的真值為1，╕P的真值為0

相對于P的距離比率函數(shù)

通過距離比率函數(shù)hT(x)對y值的計算，如果有

1）若函數(shù)hT(x)=1，y值落在區(qū)域(αl-εl,αl+εl)，則此時信息增益強，其真值為1。

2）若函數(shù)hT(x)=0，y值落在區(qū)域(αr-εr,αr+εr)，則此時信息增益弱，其真值為0。

3）若函數(shù)hT(x)=y值落在區(qū)域(αr+εr,αl-εl)，則此時信息增益半強半弱。

6 結(jié)語

決策樹算法是一種機器學習算法，用于對數(shù)據(jù)的分類。決策樹的生成過程中采用遞歸算法使得決策樹的結(jié)點能夠不斷地分裂，從而生成一棵決策樹。在ID3算法和C4.5算法中信息熵和信息增益是決策樹的兩個重要指標，因此在本文中采用MMTD算法對決策樹的信息增益進行研究。在本文采用由作者提出的公式與MMTD算法相結(jié)合在一起生成一種對決策樹信息增益大小的衡量算法，將MMTD算法在決策樹中進行應用是本文的創(chuàng)新點之一，提出一種信息增益衡量的算法是本文的主要創(chuàng)新點。

［1］洪龍，肖奚安，朱梧槚.中介真值程度的度量及其應用（I）［J］.計算機學報，2006（12）：2186-2193.

HUNG Long，XIAO Xian，ZHU Wujia.Medium Truth Scale and Its Applications（I）［J］.Journal of Computers，2006（12）：2186-2193.

［2］朱梧槚，肖奚安.數(shù)學基礎與模糊數(shù)學基礎［J］.自然雜志，1980（7）：723-726.

ZHU Wujia，XIAO Xi'an.foundations of mathematics and fuzzy mathematical foundation［J］.Chinese Journal of Na?ture，1980（7）：723-726.

［3］馮少榮.決策樹算法的研究與改進［J］.廈門大學學報（自然科學版），2007，46（4）：496-500.

FENG Shaorong.Research and Improvement of Decision Tree Algorithm［J］.Xiamen University（Natural Science Edition），2007，46（4）：496-500.

［4］湛寧，徐杰.決策樹算法的改進［J］.電腦知識與技術(shù)，2008（2）：1068-1069.

CHAM Ning，XU Jie.Improved Decision Tree Algorithm［J］.Computer Knowledge and Technology，2008（2）：1068-1069.

［5］譚俊璐，武建華.基于決策樹規(guī)則的分類算法研究［J］.計算機工程與設計，2010，31（5）：1071-1019.

TAN Junlu，WU Jianhua.Classification Based on Decision Tree Algorithm rule［J］.Computer Engineering and De?sign，2010，31（5）：1071-1019.

［6］季桂樹，陳沛玲，宋航.決策樹分類算法研究綜述［J］.科技廣角，2007（1）：9-12.

JI Guishu，CHEN Peiling，SONG Hang.Review of re?search on decision tree classification algorithm［J］.Sci?ence and technology wide angle，2007（1）：9-12.

［7］龍際珍，任海葉，易華容.一種改進決策樹算法的探討［J］.株洲師范高等?？茖W校學報，2006，11（2）：64-66.

LONG Jizhen，REN Haiye，YI Huarong.An improved deci?sion tree algorithm［J］.Journal of Zhuzhou Teachers Col?lege，2006，11（2）：64-66.

［8］滿桂云，林家駿.ID3決策樹算法的改進研究［J］.中國科技信息，2007（13）：268-269.

MAN Guiyun，LIN Jiajun.ID3 decision tree algorithm im?provement research［J］.China Science and technology in?formation，2007（13）：268-269.

［9］楊學兵，張俊.決策樹算法及其核心技術(shù)［J］.計算機技術(shù)與發(fā)展，2007，17（1）：43-45.

ZHANG Jun，YANG Xuebing.Decision tree algorithm and its core technology［J］.computer technology and develop?ment，2007，17（1）：43-45.

［10］胡江洪.基于決策樹的分類算法研究［D］.武漢：武漢理工大學，2006：5-6.

HU Jianghong.Research on classification algorithm based on decision tree［D］.Wuhan：Wuhan University of Technology，2006：5-10.

［11］戴南.基于決策樹的分類算法研究［D］.南京：南京師范大學，2003：8-15.

DAI Nan.Research on classification algorithm based on decision tree［D］.Nanjing：Nanjing Normal University，2003：8-15.

A Decision Tree Algorithm Based on MMTD

ZHU Lizhi
（Information Center，Nanjing University of Aeronautics and Astronautics，Nanjing210016）

decision tree is a kind of commonly used classification algorithm，since the ID3 algorithm has been related to the personnel to improve the algorithm，which appeares a variety of decision tree algorithm.When the decision tree is generated，the re?cursive algorithm is used to split the nodes of the decision tree.If the information gain of nodes is bigger，the probability of node splitting is greater.The ID3 algorithm and C4.5 algorithm in the information gain becomes an important basis for the node is split，so according to characteristics of the decision tree node split when the information gain function，this paper presents another algorithm to measure the size of the information gain，the algorithm with measure formula and the core algorithm——MMTD algorithm.The in?novation of this paper lies in MMTD algorithm in decision tree were used for the first time，and in the MMTD as the basis and the core of the algorithm is to achieve the measure of the size of the information gain.

MMTD，decision tree，information entropy，information gain，ID3 algorithm

TP393

10.3969/j.issn.1672-9722.2017.05.011

2016年11月10日，

2016年12月23日

朱俚治，男，工程師，研究方向：網(wǎng)絡安全，計算機算法和技術(shù)。