決策樹學習資料

決策樹學習編寫：張磊決策樹決策樹是實例（表示為特征向量）的分類器。結(jié)點測試特征，邊表示特征的每個值，葉結(jié)點對應(yīng)分類。

可表示任意析取和合取范式，從而表示任意離散函數(shù)和離散特征可將實例分到多個分類(2)可以重寫為規(guī)則，用析取范式（DNF）形式

red^circle->positive

red^circle->A

blue->B;red^square->B

green->C;red^triangle->C2001年6月2日決策樹學習實例用(屬性-值)對表示。離散值處理簡單，連續(xù)值可以劃分區(qū)間。輸出可以是離散的分類，也可以是實數(shù)（回歸樹）。能有效處理大量數(shù)據(jù)可處理噪聲數(shù)據(jù)（分類噪聲，屬性噪聲）屬性值缺失，亦可處理2001年6月2日基本決策樹算法訓(xùn)練數(shù)據(jù)批處理，自頂向下遞歸構(gòu)造決策樹DTree(examples,attributes)

If所有樣本屬于同一分類，返回標號為該分類的葉結(jié)點

Elseif屬性值為空，返回標號為最普遍分類的葉結(jié)點

Else選取一個屬性，A，作為根結(jié)點

ForA的每一個可能的值vi

令examplesi為具有A=vi的樣本子集

從根結(jié)點出發(fā)增加分支（A=vi)

如果examplesi為空

則創(chuàng)建標號為最普遍分類的葉結(jié)點

否則遞歸創(chuàng)建子樹——調(diào)用DTree(examplesi,attributes-{A})2001年6月2日根屬性的選取決策樹要盡可能小尋找一組數(shù)據(jù)對應(yīng)的最小決策樹是NP-hard的簡單遞歸算法是貪婪啟發(fā)式搜索，無法保證最優(yōu)子集應(yīng)盡可能“純”，從而易于成為葉結(jié)點最常用的啟發(fā)規(guī)則是基于信息增益(InformationGain)2001年6月2日熵(Entropy)一組樣本S對于二元分類的熵(混淆度)為：

其中p+和p-為S中的正例、反例所占比例若所有樣本屬于同一分類，則熵為0(定義0log0=0)若樣本平均分布(p+=p-=0.5)，則熵最大(=1)可把熵視為對樣本集分類進行編碼所需的平均二進制位數(shù)，采用哈夫曼編碼壓縮，越普遍的分類編碼越短對于多分類問題（假設(shè)有c個分類），則熵的推廣定義：

其中pi為屬于分類i的樣本在S中所占比例2001年6月2日信息增益屬性的信息增益是按該屬性分割后熵的消減期望值：

其中Sv是S中屬性A值為v的子集例子：big,red,circle:+small,red,circle:+small,red,square:-big,blue,circle:-2001年6月2日決策樹歸納中的假設(shè)空間決策樹可以表示任何離散函數(shù)，歸納就是在此空間內(nèi)的搜索創(chuàng)建與數(shù)據(jù)一致的單一離散假設(shè)，所以無法提供置信度或構(gòu)造有用的查詢爬山式搜索存在局部最優(yōu)問題。它可以保證找到符合任何無噪聲數(shù)據(jù)集的樹，但未必是最小的批量學習。每項決策需要一次數(shù)據(jù)集掃描，可提前結(jié)束學習以減少噪聲影響2001年6月2日決策樹學習中的誤區(qū)樹的深度應(yīng)盡量小。但貪婪搜索可能無法找到最小樹，頂層結(jié)點可能不是高區(qū)分度的2001年6月2日計算復(fù)雜度最壞情況是構(gòu)構(gòu)造出一棵完完全樹，每條條路徑都測試試了所有特征征各層i要對剩剩下的|A|-i個屬性性計算最佳分分割一般來來說，，性能能與屬屬性個個數(shù)成成線性性關(guān)系系2001年年6月月2日日決策樹樹研究究的歷歷史1960’’s：：Hunt的完完全搜搜索決決策樹樹方法法（CLS）對對概念念學習習建模模1970后后期：：Quinlan發(fā)發(fā)明用用信息息增益益作為為啟發(fā)發(fā)策略略的ID3方法法，從從樣本本中學學習構(gòu)構(gòu)造專專家系系統(tǒng)同時，Breiman和Friedman開發(fā)的的CART（分分類與回回歸樹））方法類類似于ID31980’s：：對噪聲聲、連續(xù)續(xù)屬性、、數(shù)據(jù)缺缺失、改改善分割割條件等等進行研研究1993：Quinlan的的改進決決策樹歸歸納包（（C4.5），，目前被被普遍采采用2001年6月月2日過度擬合合和修剪剪通過學習習訓(xùn)練數(shù)數(shù)據(jù)來構(gòu)構(gòu)造分類類樹，可可能無法法達到最最好的泛泛化性能能，因為為噪聲數(shù)據(jù)據(jù)的影響響某些決策策僅基于于少量數(shù)數(shù)據(jù)，與與客觀事事實不符符合一個假設(shè)設(shè)H被稱為對對于訓(xùn)練練數(shù)據(jù)是是過度擬擬合的，，指的是是如果存存在另一一個假設(shè)設(shè)H’，在訓(xùn)練集集上H的的誤差比比H‘小，但但在測試試集上H’的誤差比比H小2001年6月月2日過度擬合合與噪聲聲分類或?qū)賹傩栽肼暵暥紩?dǎo)導(dǎo)致過度度擬合增增加噪噪聲實例例<<medium,green,circle>,+>（實實際為-）噪聲也會會直接導(dǎo)導(dǎo)致樣本本的沖突突(相同同描述，，不同分分類)。。應(yīng)將葉葉結(jié)點標標號為主主要的分分類<<big,red,circle>,->(實際上上為+)若屬性不不完備且且不足以以判別分分類時，，也可能能導(dǎo)致樣樣本的沖沖突2001年6月月2日避免過度度擬合的的方法需要修剪剪時的兩兩個基本本方法預(yù)修剪：支持度度不夠則則停止樹樹的增長長后修剪：置信度度不夠則則修剪掉掉該分支支子樹是否否需要修修剪的判判別方法法：交叉檢驗驗：保留部部分訓(xùn)練練數(shù)據(jù)用用于驗證證統(tǒng)計測試試：通過訓(xùn)訓(xùn)練集的的統(tǒng)計來來判別最小描述述長度(MDL)：判別該假假設(shè)的復(fù)復(fù)雜度是是否比記記憶例外外情況的的復(fù)雜度度更高2001年6月月2日減小誤差差的修剪剪一種后修修剪，交交叉驗證證的方法法

將訓(xùn)訓(xùn)練數(shù)據(jù)據(jù)分割為為兩個集集合：““生長””和“驗驗證”用用“生生長”數(shù)數(shù)據(jù)構(gòu)建建一棵完完全樹Until驗驗證數(shù)數(shù)據(jù)集合合上的精精度降低低do：Foreach樹中中非葉結(jié)結(jié)點n臨臨時時修剪掉掉n下子子樹，用用標號為為主要分分類的葉葉子代替替在在驗證集集上計算算該樹的的精度修修剪掉那那些對精精度影響響最大的的分支當訓(xùn)練集集很小時時，可能能會嚴重重損害分分類精度度最好能給給定合適適的結(jié)點點數(shù)，達達到最佳佳折衷2001年6月月2日連續(xù)屬性性用分區(qū)方方法，將將連續(xù)值值映射為為離散值值結(jié)點分裂裂，以獲獲得最大大信息增增益達到最大大信息增增益的單單閾值分分裂算法法Foreach連續(xù)特征Ai根據(jù)Ai的值對樣本排排序Foreach序列中的每對對Xi,Xi+1IfXi和Xi+1的分類不同將將Xi和Xi+1的中點作為可可能的閾值進進行檢驗，即即例如：長長度(L):10152128324050(已排序)

分類:-++-++-檢查閾值：L<12.5,L<24.5,L<30,L<452001年6月2日替代屬性選取取啟發(fā)策略(增益比率)信息增益缺點點：偏愛那些些有大量值的的屬性，產(chǎn)生生很多小而純純的子集，如如病人ID、姓名、日期等等要降低這些情情況下的增益益首先計算與分分類無關(guān)屬性性的信息量，，即該屬性的的熵其其中Si為S中具有屬性A第i個值的子集。。某屬性按值值分割樣本越越平均，則SplitInfo越大增益比率利用用SplitInfo來避免選擇這這些屬性2001年6月2日增益比率細述述然而，當|Si|=|S|時SplitInfo可能很小甚至至為0，從而而導(dǎo)致信息比比率過大甚至至溢出C4.5對此進進行了改改進，它它計算每每個特征征的信息息增益，，對于超超過平均均增益的的特征，，再進一一步根據(jù)據(jù)增益比比率來選選取特征征2001年6月月2日缺失的屬屬性值屬性值可可能未完完全給出出一種解決決方法是是根據(jù)已已有樣本本屬性值值的先驗驗概率來來對樣本本計算屬屬性值分分布百分分比在訓(xùn)練練時，，缺失失的屬屬性會會按照照其分分布百百分比比逐個個計算算。例如，，給定定一個個缺失失了顏顏色屬屬性值值的正正例，，它將將被視視為0.6個red正例例、0.2個blue正正例和和0.2個個green正正例。。2001年年6月月2日日測試時的值值缺失若屬性值未未給出，則則設(shè)定為??(通配配符)，然然后多路徑徑到達葉結(jié)結(jié)點，最后后計算分類類結(jié)果的各各分類權(quán)重重例如，<big,??,circle>將得得到0.6個正例，，0.2+0.2=0.4個個反例<big,red,??>將將得到0.2個正例例，0.5+0.3=0.8個反例<big,??,??>將將得到0.6x0.2=0.12個正正例，0.2+0.2+0.3+0.18=0.88個個反例2001年年6月2日日屬性開銷有些領(lǐng)域中中，某些屬屬性比其它它屬性更容容易獲取其其值(例如如病人的體體溫比其膽膽固醇水平平更容易得得到)盡可能采用用那些低開開銷的屬性性來分類在信息增益益中增加屬屬性開銷是是有效的:在不降低精精度的同時時降低了平平均開銷2001年年6月2日日遞增式的決決策樹歸納納ID4和ID5可以以遞增更新新已有的樹樹ID4有時時會丟棄某某些實例，，不保證和和歷史訓(xùn)練練樣本一致致ID5則保保證和ID3的決策策相同ID4速度度快，但精精度降低ID5速度度較快且精精度不變2001年年6月2日日決策樹中的的重復(fù)部分分決策樹比DNF更復(fù)復(fù)雜，因為為它常常存存在重復(fù)部部分范范式必必須分解為為析取范式式，導(dǎo)致了了重復(fù)子樹樹的出現(xiàn)解決：使用用復(fù)雜特征征或決策圖圖構(gòu)造性歸納納：原子特特征的邏輯輯組合或算算術(shù)組合2001年年6月2日日邊緣算法決策樹構(gòu)造造性歸納的的疊代算法法邊緣算法（（總是沿著著樹的邊緣緣走）Until沒有新新的特征被被創(chuàng)建或到到達限定值值do使使用用當前的所所有特征從從訓(xùn)練集構(gòu)構(gòu)造決策樹樹從從邊緣末端端(正例)兩個特征征的聯(lián)合來來創(chuàng)建新特特征將將這些新新特征加入入現(xiàn)有特征征集中，同同時擴展每每個樣本的的描述以包包含所有新新特征2001年年6月2日日邊緣示例2001年年6月2日日多重模型學習概念的的多重候選選定義最終決策是是基于多個個學習模型型的(加權(quán)權(quán))投票2001年年6月2日日裝袋(Bagging)用訓(xùn)練集的的不同樣本本來訓(xùn)練同同一個學習習者，來創(chuàng)創(chuàng)建多重模模型(Breiman,1996)給定訓(xùn)練集集大小為n，通過從從原始數(shù)據(jù)據(jù)取樣(用用替換方法法)，創(chuàng)建建m個不同同的訓(xùn)練集集(大小為為n)用簡單的投投票方法來來合并這m個模型可用于任何何學習方法法減少了不穩(wěn)穩(wěn)定學習算算法的一般般化錯誤，，即當訓(xùn)練練數(shù)據(jù)輕微微改動時會會導(dǎo)致決策策結(jié)果劇烈烈變動的那那些學習方方法2001年年6月2日日引導(dǎo)(Boosting)另一個生成成多重模型型的方法———重復(fù)更更改同一個個學習算法法的數(shù)據(jù)對弱學習算算法(假設(shè)設(shè)的精度只只要超過1/2即可可)能保證證性能的改改進對樣本加權(quán)權(quán)，每次疊疊代產(chǎn)生