應(yīng)用Tsallis算法和關(guān)鍵度度量的決策樹構(gòu)建

李 梁，叢培強(qiáng)，陳亞茹

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 重慶 400054)

決策樹是機(jī)器學(xué)習(xí)的主要方法之一，在一些領(lǐng)域仍在積極研究，如圖像插值、語(yǔ)音綜合[1-5]。決策樹是根樹結(jié)構(gòu)，容易理解，并且有較好的計(jì)算結(jié)果和計(jì)算效率，其中每個(gè)非葉節(jié)點(diǎn)是決策節(jié)點(diǎn)，其表示將情況分成兩個(gè)或多個(gè)子樹的標(biāo)準(zhǔn)，每個(gè)分支代表當(dāng)前節(jié)點(diǎn)1種分類情況，每個(gè)葉節(jié)點(diǎn)表示整個(gè)數(shù)據(jù)集1種分類情況，自根節(jié)點(diǎn)至每個(gè)葉節(jié)點(diǎn)存在1條路徑，代表1種分類途徑。決策樹分類器是自上而下的構(gòu)建過程，并進(jìn)行預(yù)剪枝和后剪枝，預(yù)剪枝是在完全正確分裂訓(xùn)練集之前，較早地停止樹的生成，后剪枝是在完全生成樹結(jié)構(gòu)后進(jìn)行剪枝。決策樹分類器通過使用節(jié)點(diǎn)中的條件來決定分支，從根節(jié)點(diǎn)向下移動(dòng)到葉節(jié)點(diǎn)，從而為任何看不見的情況預(yù)測(cè)類別。

當(dāng)前有很多文章對(duì)決策樹提出了改進(jìn)，徐鵬等[6]提出C4.5-K，在C4.5中引入了可調(diào)節(jié)參數(shù)K，限制信息增益率的取值范圍，取得較好的性能，但是該算法只面向期貨數(shù)據(jù)有較好效果；李孝偉等[7]提出了基于分類規(guī)則選取的C4.5改進(jìn)算法，但對(duì)復(fù)雜樣本分類問題有待進(jìn)一步研究；宋廣陵等[8]提出了A-CART，能產(chǎn)生多個(gè)子節(jié)點(diǎn)，但是該算法只適用于兩分類問題。

決策樹的核心問題是樹的構(gòu)建過程，也就是屬性的分割問題，在過去幾十年出現(xiàn)了一系列文獻(xiàn)，提出了一些分割算法，其中最具代表性的如ID3、C4.5、CART等。ID3基于香農(nóng)熵構(gòu)建決策樹；C4.5基于信息增益率，被認(rèn)為是歸一化的香農(nóng)熵，彌補(bǔ)了ID3不能處理連續(xù)屬性的缺陷；而CART算法基于基尼系數(shù)。這些算法是獨(dú)立存在的，都有各自相應(yīng)的優(yōu)勢(shì)。本文提出了一個(gè)統(tǒng)一的Tsallis熵框架，這不僅統(tǒng)一了上述3種流行分割標(biāo)準(zhǔn)，而且還可以通過可調(diào)參數(shù)q值來適應(yīng)各種數(shù)據(jù)集。

訓(xùn)練樣本集存在樣本分類不平衡的情況，也存在小類屬數(shù)據(jù)集的問題，即在訓(xùn)練集中有些類屬的樣本數(shù)量遠(yuǎn)遠(yuǎn)小于其他樣本數(shù)量，見表1。假設(shè)構(gòu)建的決策樹只有2個(gè)葉節(jié)點(diǎn)，A1和A2表示當(dāng)前葉節(jié)點(diǎn)樣本數(shù)據(jù)類別，即A1和A2樣本數(shù)據(jù)各有 2 000個(gè)和200個(gè)，A2屬于小類屬；在決策樹構(gòu)建過程中，對(duì)葉節(jié)點(diǎn)進(jìn)行類屬標(biāo)識(shí)時(shí)，采用“少數(shù)服從多數(shù)”的標(biāo)準(zhǔn)，即在對(duì)葉節(jié)點(diǎn)進(jìn)行類屬標(biāo)識(shí)時(shí)，選出該節(jié)點(diǎn)樣本數(shù)量最多的類，并以該類標(biāo)識(shí)葉節(jié)點(diǎn)。對(duì)表1而言，葉節(jié)點(diǎn)1與葉節(jié)點(diǎn)2均被標(biāo)識(shí)為A1，小類屬A2被忽略。由于上述兩點(diǎn)，使得小類屬被忽略，在預(yù)測(cè)新數(shù)據(jù)時(shí)，無法判別出小類屬數(shù)據(jù)。 為解決該問題，本文提出關(guān)鍵度度量，取代“少數(shù)服從多數(shù)”的標(biāo)準(zhǔn)。

表1 訓(xùn)練樣本實(shí)例

1 Tsallis熵框架

1.1 Tsallis熵

為了解決非廣延熵問題，Tsallis受多重分形的啟示，提出了非廣延熵的概念。 Tsallis熵定義如下：

，q∈R

(1)

其中：X取值為{X1，X2,…,Xn}；隨機(jī)變量p(Xi)是Xi的概率。

1.2 Tsallis熵框架

香農(nóng)熵、增益比率和基尼指數(shù)統(tǒng)一于Tsallis熵框架中，Tsallis熵與三者的具體對(duì)應(yīng)關(guān)系如下：

1) 當(dāng)可調(diào)參數(shù)q→1時(shí)，Tsallis熵等價(jià)為香農(nóng)熵。

(2)

2) 當(dāng)可調(diào)參數(shù)q→2時(shí)，Tsallis熵等價(jià)為基尼指數(shù)Gini。

(3)

計(jì)算信息增益率CainRatio(GR)時(shí)，將計(jì)算香農(nóng)熵的過程替換為計(jì)算Tsallis熵的過程，則信息增益率就轉(zhuǎn)變成了Tsallis信息增益率(TGR)。

當(dāng)可調(diào)參數(shù)q→1時(shí)，TGR等價(jià)為基尼指數(shù)Gini。

(4)

調(diào)節(jié)不同的q，Tsallis熵退化為香農(nóng)熵、信息增益率和基尼指數(shù)。因此，可以通過調(diào)節(jié)q的值來提高構(gòu)建決策樹的性能。

2 關(guān)鍵度度量

決策樹葉節(jié)點(diǎn)的標(biāo)識(shí)基于“少數(shù)服從多數(shù)”原則，在某些領(lǐng)域該原則能代表整體數(shù)據(jù)，但對(duì)分類問題，該原則忽略了一些少數(shù)但不可忽略的類別，或許這些類別才是更重要的。該問題出現(xiàn)的原因在于：對(duì)葉節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)時(shí)只考慮到屬于葉節(jié)點(diǎn)j的樣本數(shù)據(jù)集，而并未考慮到總體樣本數(shù)據(jù)集。在訓(xùn)練樣本集中，一些類Ai的樣本數(shù)量遠(yuǎn)遠(yuǎn)小于其他類別樣本數(shù)量，并在構(gòu)建決策樹過程中該類別數(shù)據(jù)不斷被劃分到不同葉節(jié)點(diǎn)，最終在各樣本子集中，Aj類別的樣本數(shù)量占據(jù)較小比例。因此，使用關(guān)鍵度度量標(biāo)準(zhǔn)替代“少數(shù)服從多數(shù)”原則，不僅考慮當(dāng)前葉節(jié)點(diǎn)中的各類樣本數(shù)據(jù)比例，也注重各類樣本總體數(shù)量，能完全解決小類屬被忽略的問題。

定義1 類分散度aij表示類Ai在節(jié)點(diǎn)j的分散程度，即節(jié)點(diǎn)j中Aj類樣本數(shù)量占總訓(xùn)練樣本集中Ai的比例。

(5)

定義2 類決策度βij描述第i類樣本在節(jié)點(diǎn)j的權(quán)威性，即節(jié)點(diǎn)j中Ai類樣本數(shù)量占節(jié)點(diǎn)j中樣本數(shù)據(jù)的比例。

(6)

當(dāng)建立完決策樹，對(duì)葉節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)時(shí)時(shí)，綜合考慮aij和βij，βij表示當(dāng)前類i的樣本在葉節(jié)點(diǎn)j中所占比例。未改進(jìn)前，決策樹構(gòu)建以βij為基礎(chǔ)按照“少數(shù)服從多數(shù)”的標(biāo)準(zhǔn)標(biāo)識(shí)葉節(jié)點(diǎn)；改進(jìn)后，不僅考慮βij，同時(shí)還將考慮aij，解決了小類屬無“話語(yǔ)權(quán)”的缺陷。當(dāng)βij>0.8時(shí)，以類i標(biāo)識(shí)葉節(jié)點(diǎn)j；當(dāng)βij≤0.8時(shí)，使用關(guān)鍵度度量作為標(biāo)識(shí)標(biāo)準(zhǔn)。

定義3 關(guān)鍵度度量dij為類分散度和類決策度的乘積，即

(7)

由式(6)(7)可知：aij和βij取值范圍均為[0，1]，因此dij取值范圍為[0，1]。當(dāng)dij越接近1，則類i作為葉節(jié)點(diǎn)j的可能性越大；當(dāng)dij=1時(shí)說明類i中所有樣本數(shù)據(jù)均分布在葉節(jié)點(diǎn)j，并且節(jié)點(diǎn)j中的類屬是純類。提出關(guān)鍵度度量后，為葉節(jié)點(diǎn)進(jìn)行類標(biāo)識(shí)時(shí)，選取關(guān)鍵度度量最大的類別，而不是選擇樣本數(shù)據(jù)最多的類別。

由上述可知：最終葉節(jié)點(diǎn)的標(biāo)識(shí)類選取標(biāo)準(zhǔn)為

select(Ai)=arg max{dij}

(8)

對(duì)于表1，其類分散度和類決策度如表2所示。

表2 分散度和決策度

葉節(jié)點(diǎn)1：d11=a11β11=0.894 6，d21=a21β21=0.000 3

葉節(jié)點(diǎn)2：d12=a12β12=0.051 3，d22=a22β22=0.462 7

改進(jìn)前，對(duì)表1中葉節(jié)點(diǎn)的類別標(biāo)識(shí)以“少數(shù)服從多數(shù)”為標(biāo)準(zhǔn)。葉節(jié)點(diǎn)1以A1為標(biāo)識(shí)，葉節(jié)點(diǎn)2以A2為標(biāo)識(shí)。在本訓(xùn)練樣本數(shù)據(jù)集中，A2屬于小類屬，被忽略掉。改進(jìn)后，以“關(guān)鍵度度量”為標(biāo)準(zhǔn)，葉節(jié)點(diǎn)1中β11>0.8，所以葉節(jié)點(diǎn)1的類標(biāo)識(shí)為A1；葉節(jié)點(diǎn)1中β11<0.8，A2類的關(guān)鍵度度量較大，所以葉節(jié)點(diǎn)2的類標(biāo)識(shí)為A2，解決了小類屬屬性被忽略的缺陷。

3 基于Tsallis熵框架和關(guān)鍵度度量的決策樹構(gòu)建

(9)

決策樹構(gòu)建完成后，需要標(biāo)識(shí)每個(gè)葉節(jié)點(diǎn)的類別，此時(shí)摒棄原始“少數(shù)服從多數(shù)”的原則，采用關(guān)鍵度度量的方式標(biāo)識(shí)每個(gè)葉節(jié)點(diǎn)屬于哪種類別。遍歷所有葉節(jié)點(diǎn)，根據(jù)式(7)計(jì)算出每個(gè)葉節(jié)點(diǎn)中不同類別對(duì)應(yīng)的關(guān)鍵度度量，由式(8)得到當(dāng)前葉節(jié)點(diǎn)標(biāo)識(shí)為關(guān)鍵度度量最大的類別。至此，決策樹構(gòu)建完成。

4 實(shí)驗(yàn)

本實(shí)驗(yàn)分為兩部分：第1部分是在不同數(shù)據(jù)集上使用Tsallis框架和ID3、C4.5、CART算法形成決策樹，以這兩種決策樹為對(duì)測(cè)試樣本集進(jìn)行分類，比較分類結(jié)果的準(zhǔn)確度和樹規(guī)模，驗(yàn)證本文基于Tsallis框架構(gòu)建決策樹的性能；第2部分為在不同數(shù)據(jù)集上使用Tsallis框架構(gòu)建決策樹時(shí)，引入“關(guān)鍵度度量”準(zhǔn)則進(jìn)行葉節(jié)點(diǎn)的標(biāo)識(shí)，并在測(cè)試集上驗(yàn)證準(zhǔn)確度和決策樹規(guī)模，并與第1部分基于Tsallis框架構(gòu)建決策樹進(jìn)行比較。

4.1 基于Tsallis框架構(gòu)建決策樹性能分析

在不同數(shù)據(jù)集上基于Tsallis框架和ID3、C4.5、CART算法構(gòu)建決策樹并進(jìn)行測(cè)試，比較準(zhǔn)確度和決策樹規(guī)模。實(shí)驗(yàn)數(shù)據(jù)采用UCI中Abalone數(shù)據(jù)集、Census Income數(shù)據(jù)集、Connect-4數(shù)據(jù)集、Image Segmentation 數(shù)據(jù)集、Mushroom數(shù)據(jù)集，決策樹構(gòu)建過程同本文第3節(jié)，每組數(shù)據(jù)樣本包含的各類樣本數(shù)量均相同，因此避免了數(shù)據(jù)集中小類屬現(xiàn)象，得到5組測(cè)試結(jié)果，如表3所示。

表3 基于Tsallis的決策樹

在Abalone數(shù)據(jù)集、Census Income數(shù)據(jù)集和Image Segmentation數(shù)據(jù)集上，采用C4.5分割算法構(gòu)建決策樹準(zhǔn)確度相對(duì)ID3和CART較好；在決策樹規(guī)模上，CART在Abalone數(shù)據(jù)集、Connect-4數(shù)據(jù)集和Image Segmentation數(shù)據(jù)集上性能好于ID3和C4.5分割算法。但是，基于Tsallis框架構(gòu)建的決策樹，除Mushroom數(shù)據(jù)集外，準(zhǔn)確度和樹規(guī)模上均好于其他3種經(jīng)典算法，尤其是Abalone數(shù)據(jù)集，性能提高更加明顯。

4.2 基于Tsallis框架和關(guān)鍵度度量構(gòu)建決策樹性能分析

在基于Tsallis框架構(gòu)建決策樹的基礎(chǔ)上，以本文提出的“關(guān)鍵度度量”為基準(zhǔn)標(biāo)識(shí)葉節(jié)點(diǎn)，并在測(cè)試集上測(cè)試。其中，驗(yàn)證部分仍采用10折交叉驗(yàn)證法，但數(shù)據(jù)集中每類樣本數(shù)據(jù)不再均分到每組樣本，而是將數(shù)據(jù)集隨機(jī)分為10份，因此訓(xùn)練數(shù)據(jù)集和測(cè)試樣本集中便會(huì)出現(xiàn)小類屬缺陷，目的為驗(yàn)證本文提出的“關(guān)鍵度度量”標(biāo)準(zhǔn)，測(cè)試結(jié)果如表4所示。

表4 基于Tsallis框架和關(guān)鍵度度量的決策樹

對(duì)比表3和表4可知：出現(xiàn)小類屬屬性后的數(shù)據(jù)集，以Tsallis算法構(gòu)建決策樹，準(zhǔn)確性均有所下降，決策樹規(guī)模一定程度增大。當(dāng)數(shù)據(jù)集中出現(xiàn)小類屬后，Tsallis仍以“少數(shù)服從多數(shù)”原則標(biāo)識(shí)葉節(jié)點(diǎn)，因此小類屬分類被忽略后，在測(cè)試階段該類數(shù)據(jù)樣本被分錯(cuò)類。當(dāng)“關(guān)鍵度度量”取代“少數(shù)服從多數(shù)”標(biāo)準(zhǔn)后，在同樣的數(shù)據(jù)集上進(jìn)行測(cè)試，準(zhǔn)確度提高了，決策樹規(guī)模下降了，且相比本文1.2節(jié)基于Tsallis框架構(gòu)建決策樹的性能也提高了。

4.3 不同參數(shù)q對(duì)構(gòu)建決策樹的影響

本實(shí)驗(yàn)采用UCI中Abalone數(shù)據(jù)集，該數(shù)據(jù)集有4 177個(gè)樣本實(shí)例，8個(gè)決策屬性，一個(gè)類別屬性，決策屬性中有1個(gè)離散屬性和7個(gè)連續(xù)屬性。調(diào)節(jié)q參數(shù)，調(diào)節(jié)范圍為[0.1，10.0]，q的變化梯度為0.1，對(duì)每個(gè)q驗(yàn)證決策樹準(zhǔn)確度和規(guī)模，將分類正確的樣本數(shù)量占測(cè)試集樣本數(shù)量的比重作為準(zhǔn)確度。

實(shí)驗(yàn)采用10折交叉驗(yàn)證法，驗(yàn)證構(gòu)建決策樹的準(zhǔn)確度和節(jié)點(diǎn)規(guī)模，整體Abalone數(shù)據(jù)集分為10組，每組數(shù)據(jù)集包含每類樣本均分的1/10，將其中任意9組樣本作為訓(xùn)練集，剩余1組作為測(cè)試集，得到10組測(cè)試結(jié)果，求得10組準(zhǔn)確度的平均值作為最終的準(zhǔn)確度。不同q值在Abalone數(shù)據(jù)集上測(cè)試結(jié)果如圖1所示，圖1(a)是準(zhǔn)確度，圖1(b)是決策樹規(guī)模。圖1(a)顯示：精確度對(duì)于參數(shù)q變化是敏感的，最高精確度在q=2.4處取得。圖1(b)顯示：決策樹規(guī)模對(duì)于參數(shù)q變化也是敏感的，最小決策樹規(guī)模在q=3.9處取得。最終，高精確度和低規(guī)?？梢栽趒=1.7的位置取得。該實(shí)驗(yàn)表明了參數(shù)q對(duì)決策樹精度和規(guī)模存在影響，在實(shí)際應(yīng)用中可以根據(jù)精度和規(guī)模的側(cè)重點(diǎn)不同，調(diào)節(jié)q的取值。

圖1 不同q值在Abalone數(shù)據(jù)集上的測(cè)試結(jié)果

5 結(jié)束語(yǔ)

本文對(duì)決策樹構(gòu)建算法進(jìn)行改進(jìn)，提出Tsallis算法，將ID3、C4.5和CART統(tǒng)一起來，并通過調(diào)節(jié)q適應(yīng)不同數(shù)據(jù)集，使Tsallis算法達(dá)到最優(yōu)，同時(shí)結(jié)合“關(guān)鍵度度量”類標(biāo)識(shí)標(biāo)準(zhǔn)，解決了數(shù)據(jù)集中小類屬被忽略的缺陷，以此方法構(gòu)建的決策樹更加完美，不但準(zhǔn)確度高，而且決策樹規(guī)模較小。實(shí)驗(yàn)分為兩個(gè)部分：第1部分比較了Tsallis算法與傳統(tǒng)屬性分割方法構(gòu)建決策樹準(zhǔn)確度和樹規(guī)模，驗(yàn)證了基于Tsallis算法構(gòu)建決策樹性能的提高；第2部分在Tsallis算法基礎(chǔ)上引入了“關(guān)鍵度度量”并與Tsallis算法構(gòu)建決策樹進(jìn)行比較，準(zhǔn)確度和樹規(guī)模均取得了更好的效果。經(jīng)過兩部分的實(shí)驗(yàn)，循序漸進(jìn)地驗(yàn)證了本文提出的改進(jìn)措施，下一步研究重點(diǎn)為如何快速求得最佳參數(shù)q和進(jìn)一步降低構(gòu)建樹的時(shí)間復(fù)雜度。