機(jī)器學(xué)習(xí)決策樹(shù)學(xué)習(xí)

決策樹(shù)學(xué)習(xí)編寫：張磊決策樹(shù)決策樹(shù)是實(shí)例（表示為特征向量）的分類器。結(jié)點(diǎn)測(cè)試特征，邊表示特征的每個(gè)值，葉結(jié)點(diǎn)對(duì)應(yīng)分類。

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

red^circle->positive

red^circle->A

blue->B;red^square->B

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

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

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

Else選取一個(gè)屬性，A，作為根結(jié)點(diǎn)

ForA的每一個(gè)可能的值vi

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

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

如果examplesi為空

則創(chuàng)建標(biāo)號(hào)為最普遍分類的葉結(jié)點(diǎn)

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

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

其中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è)空間決策樹(shù)可以表示任何離散函數(shù)，歸納就是在此空間內(nèi)的搜索創(chuàng)建與數(shù)據(jù)一致的單一離散假設(shè)，所以無(wú)法提供置信度或構(gòu)造有用的查詢爬山式搜索存在局部最優(yōu)問(wèn)題。它可以保證找到符合任何無(wú)噪聲數(shù)據(jù)集的樹(shù)，但未必是最小的批量學(xué)習(xí)。每項(xiàng)決策需要一次數(shù)據(jù)集掃描，可提前結(jié)束學(xué)習(xí)以減少噪聲影響2001年6月2日決策樹(shù)學(xué)習(xí)中的誤區(qū)樹(shù)的深度應(yīng)盡量小。但貪婪搜索可能無(wú)法找到最小樹(shù)，頂層結(jié)點(diǎn)可能不是高區(qū)分度的2001年6月2日計(jì)算復(fù)雜度最壞情況是構(gòu)造出一棵完全樹(shù)，每條路徑都測(cè)試了所有特征

各層i要對(duì)剩下的|A|-i個(gè)屬性計(jì)算最佳分割

一般來(lái)說(shuō)，性能與屬性個(gè)數(shù)成線性關(guān)系2001年6月2日決策樹(shù)樹(shù)研究究的歷歷史1960’’s：：Hunt的完完全搜搜索決決策樹(shù)樹(shù)方法法（CLS）對(duì)對(duì)概念念學(xué)習(xí)習(xí)建模模1970后后期：：Quinlan發(fā)發(fā)明用用信息息增益益作為為啟發(fā)發(fā)策略略的ID3方法法，從從樣本本中學(xué)學(xué)習(xí)構(gòu)構(gòu)造專專家系系統(tǒng)同時(shí)，，Breiman和和Friedman開(kāi)發(fā)發(fā)的CART（（分類類與回回歸樹(shù)樹(shù)）方方法類類似于于ID31980’’s：：對(duì)噪噪聲、、連續(xù)續(xù)屬性性、數(shù)數(shù)據(jù)缺缺失、、改善善分割割條件件等進(jìn)進(jìn)行研研究1993：：Quinlan的的改進(jìn)進(jìn)決策策樹(shù)歸歸納包包（C4.5）），目目前被被普遍遍采用用2001年年6月月2日日過(guò)度擬擬合和和修剪剪通過(guò)學(xué)學(xué)習(xí)訓(xùn)訓(xùn)練數(shù)數(shù)據(jù)來(lái)來(lái)構(gòu)造造分類類樹(shù)，，可能能無(wú)法法達(dá)到到最好好的泛泛化性性能，，因?yàn)闉樵肼晹?shù)數(shù)據(jù)的的影響響某些決決策僅僅基于于少量量數(shù)據(jù)據(jù)，與與客觀觀事實(shí)實(shí)不符符合一個(gè)假假設(shè)H被稱為為對(duì)于于訓(xùn)練練數(shù)據(jù)據(jù)是過(guò)過(guò)度擬擬合的的，指指的是是如果果存在在另一一個(gè)假假設(shè)H’，，在訓(xùn)練練集上上H的的誤差差比H‘小，，但在在測(cè)試試集上上H’的誤差差比H小2001年年6月月2日日過(guò)度擬擬合與與噪聲聲分類或或?qū)傩孕栽肼暵暥紩?huì)會(huì)導(dǎo)致致過(guò)度度擬合合增增加噪噪聲實(shí)實(shí)例<<medium,green,circle>,+>（（實(shí)際際為-）噪聲也也會(huì)直直接導(dǎo)導(dǎo)致樣樣本的的沖突突(相相同描描述，，不同同分類類)。。應(yīng)將將葉結(jié)結(jié)點(diǎn)標(biāo)標(biāo)號(hào)為為主要要的分分類<<big,red,circle>,->(實(shí)實(shí)際上上為+)若屬性性不完完備且且不足足以判判別分分類時(shí)時(shí)，也也可能能導(dǎo)致致樣本本的沖沖突2001年年6月月2日日避免過(guò)過(guò)度擬擬合的的方法法需要修修剪時(shí)時(shí)的兩兩個(gè)基基本方方法預(yù)修剪剪：支持持度不不夠則則停止止樹(shù)的的增長(zhǎng)長(zhǎng)后修剪剪：置信信度不不夠則則修剪剪掉該該分支支子樹(shù)是是否需需要修修剪的的判別別方法法：交叉檢檢驗(yàn)：保留留部分分訓(xùn)練練數(shù)據(jù)據(jù)用于于驗(yàn)證證統(tǒng)計(jì)測(cè)測(cè)試：通過(guò)過(guò)訓(xùn)練練集的的統(tǒng)計(jì)計(jì)來(lái)判判別最小描描述長(zhǎng)長(zhǎng)度(MDL)：判別該該假設(shè)設(shè)的復(fù)復(fù)雜度度是否否比記記憶例例外情情況的的復(fù)雜雜度更更高2001年年6月月2日日減小誤誤差的的修剪剪一種后后修剪剪，交交叉驗(yàn)驗(yàn)證的的方法法將將訓(xùn)練練數(shù)據(jù)據(jù)分割割為兩兩個(gè)集集合：：“生生長(zhǎng)””和““驗(yàn)證證”用用““生長(zhǎng)長(zhǎng)”數(shù)數(shù)據(jù)構(gòu)構(gòu)建一一棵完完全樹(shù)樹(shù)Until驗(yàn)證數(shù)據(jù)據(jù)集合上上的精度度降低do：Foreach樹(shù)中非葉葉結(jié)點(diǎn)n臨時(shí)修剪剪掉n下子樹(shù)，，用標(biāo)號(hào)號(hào)為主要要分類的的葉子代代替在在驗(yàn)證證集上計(jì)計(jì)算該樹(shù)樹(shù)的精度度修修剪掉掉那些對(duì)對(duì)精度影影響最大大的分支支當(dāng)訓(xùn)練集集很小時(shí)時(shí)，可能能會(huì)嚴(yán)重重?fù)p害分分類精度度最好能給給定合適適的結(jié)點(diǎn)點(diǎn)數(shù)，達(dá)達(dá)到最佳佳折衷2001年6月月2日連續(xù)屬性性用分區(qū)方方法，將將連續(xù)值值映射為為離散值值結(jié)點(diǎn)分裂裂，以獲獲得最大大信息增增益達(dá)到最大大信息增增益的單單閾值分分裂算法法Foreach連續(xù)特征征Ai根據(jù)Ai的值對(duì)樣樣本排序序Foreach序列中的的每對(duì)Xi,Xi+1IfXi和Xi+1的分類不同同將將Xi和Xi+1的中點(diǎn)作作為可能能的閾值值進(jìn)行檢檢驗(yàn)，即即例如：長(zhǎng)長(zhǎng)度度(已排序)分分類:-++-++-檢查閾值值：L<12.5,L<24.5,L<30,L<452001年6月月2日替代屬性性選取啟啟發(fā)策略略(增益益比率)信息增益益缺點(diǎn)：：偏愛(ài)那那些有大大量值的的屬性，，產(chǎn)生很很多小而而純的子子集，如如病人ID、姓名、日日期等要降低這這些情況況下的增增益首先計(jì)算算與分類類無(wú)關(guān)屬屬性的信信息量，，即該屬屬性的熵熵其其中Si為S中具有屬屬性A第i個(gè)值的子子集。某某屬性按按值分割割樣本越越平均，，則SplitInfo越大增益比率率利用SplitInfo來(lái)避免選選擇這些些屬性2001年6月月2日增益比率率細(xì)述然而，當(dāng)當(dāng)|Si|=|S|時(shí)SplitInfo可能很小小甚至為為0，從從而導(dǎo)致致信息比比率過(guò)大大甚至溢溢出C4.5對(duì)此進(jìn)進(jìn)行了改改進(jìn)，它它計(jì)算每每個(gè)特征征的信息息增益，，對(duì)于超超過(guò)平均均增益的的特征，，再進(jìn)一一步根據(jù)據(jù)增益比比率來(lái)選選取特征征2001年6月月2日缺失的屬屬性值屬性值可可能未完完全給出出一種解決決方法是是根據(jù)已已有樣本本屬性值值的先驗(yàn)驗(yàn)概率來(lái)來(lái)對(duì)樣本本計(jì)算屬屬性值分分布百分分比在訓(xùn)練時(shí)時(shí)，缺失失的屬性性會(huì)按照照其分布布百分比比逐個(gè)計(jì)計(jì)算。例如，給給定一個(gè)個(gè)缺失了了顏色屬屬性值的的正例，，它將被被視為0.6個(gè)個(gè)red正例、、0.2個(gè)blue正正例和0.2個(gè)個(gè)green正正例。2001年6月月2日測(cè)試時(shí)的的值缺失失若屬性值值未給出出，則設(shè)設(shè)定為??(通通配符)，然后后多路徑徑到達(dá)葉葉結(jié)點(diǎn)，，最后計(jì)計(jì)算分類類結(jié)果的的各分類類權(quán)重例如，<big,??,circle>將得到到0.6個(gè)正例例，0.2+0.2=0.4個(gè)反例例

<big,red,??>將得得到0.2個(gè)正正例，0.5+0.3=0.8個(gè)反反例<big,??,??>將得得到0.6x0.2=0.12個(gè)正正例，0.2+0.2+0.3+0.18=0.88個(gè)個(gè)反例2001年6月月2日屬性開(kāi)銷銷有些領(lǐng)域域中，某某些屬性性比其它它屬性更更容易獲獲取其值值(例如如病人的的體溫比比其膽固固醇水平平更容易易得到)盡可能采采用那些些低開(kāi)銷銷的屬性性來(lái)分類類在信息增增益中增增加屬性性開(kāi)銷是是有效的的:在不降低低精度的的同時(shí)降降低了平平均開(kāi)銷銷2001年6月月2日遞增式的的決策樹(shù)樹(shù)歸納ID4和和ID5可以遞遞增更新新已有的的樹(shù)ID4有有時(shí)會(huì)丟丟棄某些些實(shí)例，，不保證證和歷史史訓(xùn)練樣樣本一致致ID5則則保證和和ID3的決策策相同ID4速速度快，，但精度度降低ID5速速度較快快且精度度不變2001年6月月2日決策樹(shù)中中的重復(fù)復(fù)部分決策樹(shù)比比DNF更復(fù)雜雜，因?yàn)闉樗３３４嬖谥刂貜?fù)部分分范范式必須須分解為為析取范范式，導(dǎo)導(dǎo)致了重重復(fù)子樹(shù)樹(shù)的出現(xiàn)現(xiàn)解決：使使用復(fù)雜雜特征或或決策圖圖構(gòu)造性歸歸納：原原子特征征的邏輯輯組合或或算術(shù)組組合2001年6月月2日邊緣算法法決策樹(shù)構(gòu)構(gòu)造性歸歸納的疊疊代算法法邊緣算法法（總是是沿著樹(shù)樹(shù)的邊緣緣走）Until沒(méi)沒(méi)有新新的特征征被創(chuàng)建建或到達(dá)達(dá)限定值值do使使用當(dāng)當(dāng)前的所所有特征征從訓(xùn)練練集構(gòu)造造決策樹(shù)樹(shù)從從邊緣緣末端(正例)兩個(gè)特特征的聯(lián)聯(lián)合來(lái)創(chuàng)創(chuàng)建新特特征將將這這些新特特征加入入現(xiàn)有特特征集中中，同時(shí)時(shí)擴(kuò)展每每個(gè)樣本本的的描描述以包包含所有有新特征征2001年6月月2日邊緣示例例2001年6月月2日多重模型型學(xué)習(xí)概念念的多重重候選定定義最終決策策是基于于多個(gè)學(xué)學(xué)習(xí)模型型的(加加權(quán))投投票2001年6月月2日裝袋(Bagging)用訓(xùn)練集集的不同同樣本來(lái)來(lái)訓(xùn)練同同一個(gè)學(xué)學(xué)習(xí)者，，來(lái)創(chuàng)建建多重模模型(Breiman,1996)給定訓(xùn)練練集大小小為n，，通過(guò)從從原始數(shù)數(shù)據(jù)取樣樣(用替替換方法法)，創(chuàng)創(chuàng)建m個(gè)個(gè)不同的的訓(xùn)練集集(大小小為n)用簡(jiǎn)單的的投票方方法來(lái)合合并這m個(gè)模型型可用于任任何學(xué)習(xí)習(xí)方法減少了不不穩(wěn)定學(xué)學(xué)習(xí)算法法的一般般化錯(cuò)誤誤，即當(dāng)當(dāng)訓(xùn)練數(shù)數(shù)據(jù)輕微微改動(dòng)時(shí)時(shí)會(huì)導(dǎo)致致決策結(jié)結(jié)果劇烈烈變動(dòng)的的那些學(xué)學(xué)習(xí)方法法2001年6月月2日引導(dǎo)(Boosting)另一個(gè)生生成多重重模型的的方法———重復(fù)復(fù)更改同同一個(gè)學(xué)學(xué)習(xí)算法法的數(shù)據(jù)據(jù)對(duì)弱學(xué)習(xí)習(xí)算法(假設(shè)的的精度只只要超過(guò)過(guò)1/2即可)能保證證性能的的改進(jìn)對(duì)樣本