機器學(xué)習(xí)決策樹學(xué)習(xí)

決策樹學(xué)習(xí)編寫：張磊決策樹決策樹是實例（表示為特征向量）的分類器。結(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日決策樹學(xué)習(xí)實例用(屬性-值)對表示。離散值處理簡單，連續(xù)值可以劃分區(qū)間。輸出可以是離散的分類，也可以是實數(shù)（回歸樹）。能有效處理大量數(shù)據(jù)可處理噪聲數(shù)據(jù)（分類噪聲，屬性噪聲）屬性值缺失，亦可處理2001年6月2日基本決策樹算法訓(xùn)練數(shù)據(jù)批處理，自頂向下遞歸構(gòu)造決策樹DTree(examples,attributes)

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

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

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

ForA的每一個可能的值vi

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

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

如果examplesi為空

則創(chuàng)建標(biāo)號為最普遍分類的葉結(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)可把熵視為對樣本集分類進(jìn)行編碼所需的平均二進(jìn)制位數(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ù)集的樹，但未必是最小的批量學(xué)習(xí)。每項決策需要一次數(shù)據(jù)集掃描，可提前結(jié)束學(xué)習(xí)以減少噪聲影響2001年6月2日決策樹學(xué)習(xí)中的誤區(qū)樹的深度應(yīng)盡量小。但貪婪搜索可能無法找到最小樹，頂層結(jié)點可能不是高區(qū)分度的2001年6月2日計算復(fù)雜度最壞情況是構(gòu)造出一棵完全樹，每條路徑都測試了所有特征

各層i要對剩下的|A|-i個屬性計算最佳分割

一般來說，性能與屬性個數(shù)成線性關(guān)系2001年6月2日決策樹樹研究究的歷歷史1960’’s：：Hunt的完完全搜搜索決決策樹樹方法法（CLS）對對概念念學(xué)習(xí)習(xí)建模模1970后后期：：Quinlan發(fā)發(fā)明用用信息息增益益作為為啟發(fā)發(fā)策略略的ID3方法法，從從樣本本中學(xué)學(xué)習(xí)構(gòu)構(gòu)造專專家系系統(tǒng)同時，，Breiman和和Friedman開發(fā)發(fā)的CART（（分類類與回回歸樹樹）方方法類類似于于ID31980’’s：：對噪噪聲、、連續(xù)續(xù)屬性性、數(shù)數(shù)據(jù)缺缺失、、改善善分割割條件件等進(jìn)進(jìn)行研研究1993：：Quinlan的的改進(jìn)進(jìn)決策策樹歸歸納包包（C4.5）），目目前被被普遍遍采用用2001年年6月月2日日過度擬擬合和和修剪剪通過學(xué)學(xué)習(xí)訓(xùn)訓(xùn)練數(shù)數(shù)據(jù)來來構(gòu)造造分類類樹，，可能能無法法達(dá)到到最好好的泛泛化性性能，，因為為噪聲數(shù)數(shù)據(jù)的的影響響某些決決策僅僅基于于少量量數(shù)據(jù)據(jù)，與與客觀觀事實實不符符合一個假假設(shè)H被稱為為對于于訓(xùn)練練數(shù)據(jù)據(jù)是過過度擬擬合的的，指指的是是如果果存在在另一一個假假設(shè)H’，，在訓(xùn)練練集上上H的的誤差差比H‘小，，但在在測試試集上上H’的誤差差比H小2001年年6月月2日日過度擬擬合與與噪聲聲分類或或?qū)傩孕栽肼暵暥紩?dǎo)致致過度度擬合合增增加噪噪聲實實例<<medium,green,circle>,+>（（實際際為-）噪聲也也會直直接導(dǎo)導(dǎo)致樣樣本的的沖突突(相相同描描述，，不同同分類類)。。應(yīng)將將葉結(jié)結(jié)點標(biāo)標(biāo)號為為主要要的分分類<<big,red,circle>,->(實實際上上為+)若屬性性不完完備且且不足足以判判別分分類時時，也也可能能導(dǎo)致致樣本本的沖沖突2001年年6月月2日日避免過過度擬擬合的的方法法需要修修剪時時的兩兩個基基本方方法預(yù)修剪剪：支持持度不不夠則則停止止樹的的增長長后修剪剪：置信信度不不夠則則修剪剪掉該該分支支子樹是是否需需要修修剪的的判別別方法法：交叉檢檢驗：保留留部分分訓(xùn)練練數(shù)據(jù)據(jù)用于于驗證證統(tǒng)計測測試：通過過訓(xùn)練練集的的統(tǒng)計計來判判別最小描描述長長度(MDL)：判別該該假設(shè)設(shè)的復(fù)復(fù)雜度度是否否比記記憶例例外情情況的的復(fù)雜雜度更更高2001年年6月月2日日減小誤誤差的的修剪剪一種后后修剪剪，交交叉驗驗證的的方法法將將訓(xùn)練練數(shù)據(jù)據(jù)分割割為兩兩個集集合：：“生生長””和““驗證證”用用““生長長”數(shù)數(shù)據(jù)構(gòu)構(gòu)建一一棵完完全樹樹Until驗證數(shù)據(jù)據(jù)集合上上的精度度降低do：Foreach樹中非葉葉結(jié)點n臨時修剪剪掉n下子樹，，用標(biāo)號號為主要要分類的的葉子代代替在在驗證證集上計計算該樹樹的精度度修修剪掉掉那些對對精度影影響最大大的分支支當(dāng)訓(xùn)練集集很小時時，可能能會嚴(yán)重重?fù)p害分分類精度度最好能給給定合適適的結(jié)點點數(shù)，達(dá)達(dá)到最佳佳折衷2001年6月月2日連續(xù)屬性性用分區(qū)方方法，將將連續(xù)值值映射為為離散值值結(jié)點分裂裂，以獲獲得最大大信息增增益達(dá)到最大大信息增增益的單單閾值分分裂算法法Foreach連續(xù)特征征Ai根據(jù)Ai的值對樣樣本排序序Foreach序列中的的每對Xi,Xi+1IfXi和Xi+1的分類不同同將將Xi和Xi+1的中點作作為可能能的閾值值進(jìn)行檢檢驗，即即例如：長長度度(已排序)分分類:-++-++-檢查閾值值：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日增益比率率細(xì)述然而，當(dāng)當(dāng)|Si|=|S|時SplitInfo可能很小小甚至為為0，從從而導(dǎo)致致信息比比率過大大甚至溢溢出C4.5對此進(jìn)進(jìn)行了改改進(jìn)，它它計算每每個特征征的信息息增益，，對于超超過平均均增益的的特征，，再進(jìn)一一步根據(jù)據(jù)增益比比率來選選取特征征2001年6月月2日缺失的屬屬性值屬性值可可能未完完全給出出一種解決決方法是是根據(jù)已已有樣本本屬性值值的先驗驗概率來來對樣本本計算屬屬性值分分布百分分比在訓(xùn)練時時，缺失失的屬性性會按照照其分布布百分比比逐個計計算。例如，給給定一個個缺失了了顏色屬屬性值的的正例，，它將被被視為0.6個個red正例、、0.2個blue正正例和0.2個個green正正例。2001年6月月2日測試時的的值缺失失若屬性值值未給出出，則設(shè)設(shè)定為??(通通配符)，然后后多路徑徑到達(dá)葉葉結(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ù)復(fù)部分決策樹比比DNF更復(fù)雜雜，因為為它常常常存在重重復(fù)部分分范范式必須須分解為為析取范范式，導(dǎo)導(dǎo)致了重重復(fù)子樹樹的出現(xiàn)現(xiàn)解決：使使用復(fù)雜雜特征或或決策圖圖構(gòu)造性歸歸納：原原子特征征的邏輯輯組合或或算術(shù)組組合2001年6月月2日邊緣算法法決策樹構(gòu)構(gòu)造性歸歸納的疊疊代算法法邊緣算法法（總是是沿著樹樹的邊緣緣走）Until沒沒有新新的特征征被創(chuàng)建建或到達(dá)達(dá)限定值值do使使用當(dāng)當(dāng)前的所所有特征征從訓(xùn)練練集構(gòu)造造決策樹樹從從邊緣緣末端(正例)兩個特特征的聯(lián)聯(lián)合來創(chuàng)創(chuàng)建新特特征將將這這些新特特征加入入現(xiàn)有特特征集中中，同時時擴展每每個樣本本的的描描述以包包含所有有新特征征2001年6月月2日邊緣示例例2001年6月月2日多重模型型學(xué)習(xí)概念念的多重重候選定定義最終決策策是基于于多個學(xué)學(xué)習(xí)模型型的(加加權(quán))投投票2001年6月月2日裝袋(Bagging)用訓(xùn)練集集的不同同樣本來來訓(xùn)練同同一個學(xué)學(xué)習(xí)者，，來創(chuàng)建建多重模模型(Breiman,1996)給定訓(xùn)練練集大小小為n，，通過從從原始數(shù)數(shù)據(jù)取樣樣(用替替換方法法)，創(chuàng)創(chuàng)建m個個不同的的訓(xùn)練集集(大小小為n)用簡單的的投票方方法來合合并這m個模型型可用于任任何學(xué)習(xí)習(xí)方法減少了不不穩(wěn)定學(xué)學(xué)習(xí)算法法的一般般化錯誤誤，即當(dāng)當(dāng)訓(xùn)練數(shù)數(shù)據(jù)輕微微改動時時會導(dǎo)致致決策結(jié)結(jié)果劇烈烈變動的的那些學(xué)學(xué)習(xí)方法法2001年6月月2日引導(dǎo)(Boosting)另一個生生成多重重模型的的方法———重復(fù)復(fù)更改同同一個學(xué)學(xué)習(xí)算法法的數(shù)據(jù)據(jù)對弱學(xué)習(xí)習(xí)算法(假設(shè)的的精度只只要超過過1/2即可)能保證證性能的的改進(jìn)對樣本