分支合并對(duì)決策樹歸納學(xué)習(xí)的影響-河北大學(xué)

分支合并對(duì)決策樹歸納學(xué)習(xí)的影響報(bào)告人：楊晨曉主要內(nèi)容1.分支合并介紹2.分支合并研究現(xiàn)狀3.兩種分支合并算法4.實(shí)驗(yàn)結(jié)果5.一個(gè)定理6.信息補(bǔ)償7.近期完成的工作分支合并介紹分支合并是預(yù)剪枝的一種，其主要思想是在樹的產(chǎn)生過(guò)程中，根據(jù)某種方法將當(dāng)前結(jié)點(diǎn)的兩個(gè)兒子結(jié)點(diǎn)合并為一個(gè)（簡(jiǎn)稱分支合并）并繼續(xù)樹的生長(zhǎng)，直至完成樹的構(gòu)建。

則最終產(chǎn)生的樹與沒(méi)有進(jìn)行分支合并所產(chǎn)生的樹，從結(jié)構(gòu)、規(guī)模、復(fù)雜性、精度等方面上將有很大區(qū)別。

分支合并介紹分支合并介紹分支合并研究現(xiàn)狀洪家榮于1995在《一種新的決策樹歸納學(xué)習(xí)算法

》中最早提出：ID3及其它已有的決策樹算法只是試圖減少樹的深度，而忽略了對(duì)決策樹葉子數(shù)目的研究,然而正是后者對(duì)決策樹的精度起主要作用，因而提出一種基于屬性聚類方法的決策樹分支合并算法；王熙照，洪家榮在《OntheOptimizationofFuzzyDecisionTrees》繼續(xù)了上述的工作將此分支合并策略推廣到了模糊決策樹以及相應(yīng)的優(yōu)化問(wèn)題；分支合并研究現(xiàn)狀畢建東，楊桂芳于《基于熵的決策樹分支合并算法

》提出了一種基于熵的分支合并算法；

最近，吳宣為，史斌寧在《一種新的簡(jiǎn)化ID3決策樹的算法》中提出了一種屬性層次互換的分支合并算法；

Zengchang

Qin

和IonathanLawry在《ROCAnalysisofaLinguisticDecisionTreeMergingAlgorithm》中研究了一種基于語(yǔ)義的向前分支合并算法。兩種分支合并算法基于正例比的分支合并基于Margin的分支合并兩種分支合并算法基于正例比的分支合并：考慮兩類問(wèn)題，將[0,1]區(qū)間分為若干個(gè)小區(qū)間，然后計(jì)算每個(gè)分支中正例所占比例，將比例落入同一個(gè)小區(qū)間的分支合并為一個(gè)分支。兩種分支合并算法基于Margin的分支合并某種程度來(lái)說(shuō)，數(shù)據(jù)間的Margin越大，則其聯(lián)系越小，也就越容易分開(kāi)。那么是否可以說(shuō)Margin越小，數(shù)據(jù)間的聯(lián)系就越大呢？基于這種考慮，提出新的分支合并算法：對(duì)于當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)，計(jì)算每?jī)蓚€(gè)子節(jié)點(diǎn)間數(shù)據(jù)的Margin，將Margin比較小的分支合并為一個(gè)。實(shí)驗(yàn)結(jié)果表1基于正例比例決策樹和ID3的比較結(jié)果

實(shí)驗(yàn)結(jié)果基于Margin的分支合并決策樹算法與ID3比較結(jié)果。一個(gè)定理(證明過(guò)程省略)假定在決策樹的一個(gè)非葉節(jié)點(diǎn)上,選擇某個(gè)屬性A作為擴(kuò)展屬性,A的取值范圍是，則可以通過(guò)某種合并策略可以將m個(gè)屬性值中的某些進(jìn)行合并。但無(wú)論采用什么樣的分支合并策略，合并后屬性A的信息增益都不會(huì)增加。

信息補(bǔ)償從上面定理的證明我們可以知道，進(jìn)行分支合并后熵會(huì)增大，根據(jù)Quinlan

的極小熵原則，我們不應(yīng)該進(jìn)行分支合并。但是兩個(gè)實(shí)驗(yàn)數(shù)據(jù)又說(shuō)明進(jìn)行分支合并后會(huì)降低樹的規(guī)模，提高樹的泛化能力。為了解釋這個(gè)問(wèn)題，我們提出了信息補(bǔ)償。信息補(bǔ)償在分支合并后，熵會(huì)增加，我們稱為信息丟失，而在合并后繼續(xù)選取擴(kuò)展屬性，這個(gè)時(shí)候如果一個(gè)分支得到的信息增益大于合并前兩個(gè)分支的信息增益的加權(quán)和，那么我們可以說(shuō)信息得到了一個(gè)補(bǔ)償，稱作信息補(bǔ)償。目前這個(gè)工作正在研究當(dāng)中?；仡櫍?）上次介紹了決策樹歸納學(xué)習(xí)中的分支合并及其發(fā)展現(xiàn)狀，又給出兩種分支合并算法，分別是基于最大Margin的分支合并算法和基于正例比的分支合并算法。并且通過(guò)定理的形式證明了不管利用何種分支合并方法，合并后信息增益會(huì)減少，我們稱之為信息丟失--IGLoss?；仡櫍?）而在進(jìn)行分支合并后，繼續(xù)為合并后的分支選取擴(kuò)展屬性，這個(gè)時(shí)候得到的信息增益，如果大于合并前兩個(gè)分支繼續(xù)選擇擴(kuò)展屬性得到的信息增益的加權(quán)和，那么我們可以說(shuō)信息得到了一個(gè)補(bǔ)償，稱作信息補(bǔ)償--IGCom?；仡櫍?）我們希望信息補(bǔ)償為正，而且如果補(bǔ)償?shù)男畔⒈葋G失信息多的話，即IGCom-IGLoss>0，那么就可以說(shuō)經(jīng)過(guò)分支合并后，雖然存在信息丟失，但是通過(guò)繼續(xù)選擇擴(kuò)展屬性，可以對(duì)信息進(jìn)行一個(gè)補(bǔ)償?shù)淖饔?，也就在某種程度上為分支合并提供了解釋。近期完成的工作對(duì)信息補(bǔ)償進(jìn)行實(shí)驗(yàn)提出新的分支合并算法—基于最大信息補(bǔ)償分支合并算法信息補(bǔ)償?shù)膶?shí)驗(yàn)對(duì)信息補(bǔ)償?shù)膶?shí)驗(yàn)主要是基于正例比的分支合并。BALANCE-SCALE的實(shí)驗(yàn)結(jié)果表示：信息丟失IGLoss>0；信息補(bǔ)償IGCom有正有負(fù)；并且IGCom-IGLoss<0。信息補(bǔ)償?shù)膶?shí)驗(yàn)這個(gè)實(shí)驗(yàn)并沒(méi)有達(dá)到我們預(yù)想的結(jié)果。但是我們又進(jìn)一步分析了IGCom>0的情況，并且提出了一種基于IGCom的分支合并算法—基于最大IGCom的分支合并算法?；谧畲驣GCom的分支合并在某一個(gè)中間節(jié)點(diǎn)選擇完擴(kuò)展屬性后，對(duì)該屬性發(fā)出的所有分支（除去葉節(jié)點(diǎn)）中的每?jī)蓚€(gè)進(jìn)行預(yù)合并，計(jì)算合并后繼續(xù)擴(kuò)展得到的信息補(bǔ)償，選擇信息補(bǔ)償最大的兩個(gè)分支進(jìn)行真正的合并?；谧畲驣GCom的分支合并目前只選擇了BALANCE-SCALE和Heart兩個(gè)數(shù)據(jù)集合進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表示根據(jù)基于最大信息補(bǔ)償?shù)姆种Ш喜⒎椒?，大多?shù)情況下IGCom>0，并且有時(shí)可以達(dá)到IGCom-IGLoss