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

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

朱俚治

（南京航空航天大學(xué)信息中心南京210016）

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

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

Class NumberTP393

1 引言

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

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

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

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

1）決策樹的特點(diǎn)

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

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

2）決策樹算法的特點(diǎn)

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

3 信息熵和信息增益簡(jiǎn)介

3.1信息熵

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

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

2）d是某個(gè)信息熵的值

分析和討論：

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

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

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

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

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

3.2信息增益

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

2）d是某個(gè)信息增益

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

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

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

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

4.1中介真值程度度量知識(shí)簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 MMTD方法的應(yīng)用

5.1決策樹結(jié)點(diǎn)信息增益的計(jì)算

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

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

以下對(duì)信息增益值計(jì)算的分析和討論：

2）當(dāng)a=d-δ＞0時(shí)

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

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

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

3）當(dāng)a=d-δ＜0時(shí)

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

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

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

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

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

5.3距離比率函數(shù)

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

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

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

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

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

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

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

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

6 結(jié)語

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

［1］洪龍，肖奚安，朱梧槚.中介真值程度的度量及其應(yīng)用（I）［J］.計(jì)算機(jī)學(xué)報(bào)，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ù)學(xué)基礎(chǔ)與模糊數(shù)學(xué)基礎(chǔ)［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ìn)［J］.廈門大學(xué)學(xué)報(bào)（自然科學(xué)版），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ìn)［J］.電腦知識(shí)與技術(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］.計(jì)算機(jī)工程與設(shè)計(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ìn)決策樹算法的探討［J］.株洲師范高等?？茖W(xué)校學(xué)報(bào)，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ìn)研究［J］.中國(guó)科技信息，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］楊學(xué)兵，張俊.決策樹算法及其核心技術(shù)［J］.計(jì)算機(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］.武漢：武漢理工大學(xué)，2006：5-6.

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

［11］戴南.基于決策樹的分類算法研究［D］.南京：南京師范大學(xué)，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)絡(luò)安全，計(jì)算機(jī)算法和技術(shù)。