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

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

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

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

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

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

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

Zengchang

Qin

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

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

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

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