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

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

朱俚治

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

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

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

Class NumberTP393

1 引言

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

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

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

2 決策樹技術簡介

1）決策樹的特點

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

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

2）決策樹算法的特點

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

3 信息熵和信息增益簡介

3.1信息熵

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

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

2）d是某個信息熵的值

分析和討論：

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

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

根據以上的分析和討論有以下的結論：

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

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

3.2信息增益

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

2）d是某個信息增益

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

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

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

4 MMTD算法技術簡介

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

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

圖1 中介真值程度度量一維函數圖

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

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

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

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

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

4.2中介真值程度度量中的距離比率函數

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

定理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的距離比率函數［1～2］

5 MMTD方法的應用

5.1決策樹結點信息增益的計算

1）信息增益的衡量函數：

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

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

2）當a=d-δ＞0時

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

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

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

3）當a=d-δ＜0時

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

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

5.2中介對網絡流量的描述

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

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

5.3距離比率函數

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

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

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

相對于P的距離比率函數

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

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

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

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

6 結語

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

［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］朱梧槚，肖奚安.數學基礎與模糊數學基礎［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］.電腦知識與技術，2008（2）：1068-1069.

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

［5］譚俊璐，武建華.基于決策樹規則的分類算法研究［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］.株洲師范高等專科學校學報，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］楊學兵，張俊.決策樹算法及其核心技術［J］.計算機技術與發展，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日

朱俚治，男，工程師，研究方向：網絡安全，計算機算法和技術。