2 機(jī)器學(xué)習(xí)-決策樹學(xué)習(xí)

決策樹學(xué)習(xí)編寫：張磊來源：1決策樹決策樹是實(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->C2決策樹學(xué)習(xí)實(shí)例用(屬性-值)對(duì)表示。離散值處理簡單，連續(xù)值可以劃分區(qū)間。輸出可以是離散的分類，也可以是實(shí)數(shù)（回歸樹）。能有效處理大量數(shù)據(jù)可處理噪聲數(shù)據(jù)（分類噪聲，屬性噪聲）屬性值缺失，亦可處理3基本決策樹算法訓(xùn)練數(shù)據(jù)批處理，自頂向下遞歸構(gòu)造決策樹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)建子樹——調(diào)用DTree(examplesi,attributes-{A})4根屬性的選取決策樹要盡可能小尋找一組數(shù)據(jù)對(duì)應(yīng)的最小決策樹是NP-hard的簡單遞歸算法是貪婪啟發(fā)式搜索，無法保證最優(yōu)子集應(yīng)盡可能“純”，從而易于成為葉結(jié)點(diǎn)最常用的啟發(fā)規(guī)則是基于信息增益(InformationGain)5熵(Entropy)一組樣本S對(duì)于二元分類的熵(混淆度)為：

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

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

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

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

一般來說，性能與屬性個(gè)數(shù)成線性關(guān)系10決策樹研究的歷史1960’s：Hunt的完全搜索決策樹方法（CLS）對(duì)概念學(xué)習(xí)建模1970后期：Quinlan發(fā)明用信息增益作為啟發(fā)策略的ID3方法，從樣本中學(xué)習(xí)構(gòu)造專家系統(tǒng)同時(shí)，Breiman和Friedman開發(fā)的CART（分類與回歸樹）方法類似于ID31980’s：對(duì)噪聲、連續(xù)屬性、數(shù)據(jù)缺失、改善分割條件等進(jìn)行研究1993：Quinlan的改進(jìn)決策樹歸納包（C4.5），目前被普遍采用11過度擬合和修剪通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)來構(gòu)造分類樹，可能無法達(dá)到最好的泛化性能，因?yàn)樵肼晹?shù)據(jù)的影響某些決策僅基于少量數(shù)據(jù)，與客觀事實(shí)不符合一個(gè)假設(shè)H被稱為對(duì)于訓(xùn)練數(shù)據(jù)是過度擬合的，指的是如果存在另一個(gè)假設(shè)H’，在訓(xùn)練集上H的誤差比H‘小，但在測(cè)試集上H’的誤差比H小12過度擬合與噪聲分類或?qū)傩栽肼暥紩?huì)導(dǎo)致過度擬合

增加噪聲實(shí)例<<medium,green,circle>,+>（實(shí)際為-）

噪聲也會(huì)直接導(dǎo)致樣本的沖突(相同描述，不同分類)。應(yīng)將葉結(jié)點(diǎn)標(biāo)號(hào)為主要的分類

<<big,red,circle>,->(實(shí)際上為+)若屬性不完備且不足以判別分類時(shí)，也可能導(dǎo)致樣本的沖突13避免過度擬合的方法需要修剪時(shí)的兩個(gè)基本方法預(yù)修剪：支持度不夠則停止樹的增長后修剪：置信度不夠則修剪掉該分支子樹是否需要修剪的判別方法：交叉檢驗(yàn)：保留部分訓(xùn)練數(shù)據(jù)用于驗(yàn)證統(tǒng)計(jì)測(cè)試：通過訓(xùn)練集的統(tǒng)計(jì)來判別最小描述長度(MDL)：判別該假設(shè)的復(fù)雜度是否比記憶例外情況的復(fù)雜度更高14減小誤差的修剪一種后修剪，交叉驗(yàn)證的方法

將訓(xùn)練數(shù)據(jù)分割為兩個(gè)集合：“生長”和“驗(yàn)證”

用“生長”數(shù)據(jù)構(gòu)建一棵完全樹

Until驗(yàn)證數(shù)據(jù)集合上的精度降低do：

Foreach樹中非葉結(jié)點(diǎn)n

臨時(shí)修剪掉n下子樹，用標(biāo)號(hào)為主要分類的葉子代替

在驗(yàn)證集上計(jì)算該樹的精度

修剪掉那些對(duì)精度影響最大的分支當(dāng)訓(xùn)練集很小時(shí)，可能會(huì)嚴(yán)重?fù)p害分類精度最好能給定合適的結(jié)點(diǎn)數(shù)，達(dá)到最佳折衷15連續(xù)屬性用分區(qū)方法，將連續(xù)值映射為離散值結(jié)點(diǎn)分裂，以獲得最大信息增益達(dá)到最大信息增益的單閾值分裂算法

Foreach連續(xù)特征Ai

根據(jù)Ai的值對(duì)樣本排序

Foreach序列中的每對(duì)Xi,Xi+1

IfXi和Xi+1的分類不同

將Xi和Xi+1的中點(diǎn)作為可能的閾值進(jìn)行檢驗(yàn)，即

例如：

長度(L):10152128324050(已排序)

分類:-++-++-檢查閾值：L<12.5,L<24.5,L<30,L<4516替代屬性選取啟發(fā)策略(增益比率)信息增益缺點(diǎn)：偏愛那些有大量值的屬性，產(chǎn)生很多小而純的子集，如病人ID、姓名、日期等要降低這些情況下的增益首先計(jì)算與分類無關(guān)屬性的信息量，即該屬性的熵

其中Si為S中具有屬性A第i個(gè)值的子集。某屬性按值分割樣本越平均，則SplitInfo越大增益比率利用SplitInfo來避免選擇這些屬性

17增益比率細(xì)述然而，當(dāng)|Si|=|S|時(shí)SplitInfo可能很小甚至為0，從而導(dǎo)致信息比率過大甚至溢出C4.5對(duì)此進(jìn)行了改進(jìn)，它計(jì)算每個(gè)特征的信息增益，對(duì)于超過平均增益的特征，再進(jìn)一步根據(jù)增益比率來選取特征18缺失的屬性值屬性值可能未完全給出一種解決方法是根據(jù)已有樣本屬性值的先驗(yàn)概率來對(duì)樣本計(jì)算屬性值分布百分比

在訓(xùn)練時(shí)，缺失的屬性會(huì)按照其分布百分比逐個(gè)計(jì)算。例如，給定一個(gè)缺失了顏色屬性值的正例，它將被視為0.6個(gè)red正例、0.2個(gè)blue正例和0.2個(gè)green正例。19測(cè)試時(shí)的值缺失若屬性值未給出，則設(shè)定為??(通配符)，然后多路徑到達(dá)葉結(jié)點(diǎn)，最后計(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è)反例20屬性開銷有些領(lǐng)域中，某些屬性比其它屬性更容易獲取其值(例如病人的體溫比其膽固醇水平更容易得到)盡可能采用那些低開銷的屬性來分類在信息增益中增加屬性開銷是有效的:

在不降低精度的同時(shí)降低了平均開銷21遞增式的決策樹歸納ID4和ID5可以遞增更新已有的樹ID4有時(shí)會(huì)丟棄某些實(shí)例，不保證和歷史訓(xùn)練樣本一致ID5則保證和ID3的決策相同ID4速度快，但精度降低ID5速度較快且精度不變22決策樹中的重復(fù)部分決策樹比DNF更復(fù)雜，因?yàn)樗３４嬖谥貜?fù)部分

范式必須分解為析取范式，導(dǎo)致了重復(fù)子樹的出現(xiàn)解決：使用復(fù)雜特征或決策圖構(gòu)造性歸納：原子特征的邏輯組合或算術(shù)組合23邊緣算法決策樹構(gòu)造性歸納的疊代算法邊緣算法（總是沿著樹的邊緣走）

Until沒有新的特征被創(chuàng)建或到達(dá)限定值do

使用當(dāng)前的所有特征從訓(xùn)練集構(gòu)造決策樹

從邊緣末端(正例)兩個(gè)特征的聯(lián)合來創(chuàng)建新特征

將這些新特征加入現(xiàn)有特征集中，同時(shí)擴(kuò)展每個(gè)樣本 的描述以包含所有新特征24邊緣示例25多重模型學(xué)習(xí)概念的多重候選定義最終決策是基于多個(gè)學(xué)習(xí)模型的(加權(quán))投票26裝袋(Bagging)用訓(xùn)練集的不同樣本來訓(xùn)練同一個(gè)學(xué)習(xí)者，來創(chuàng)建多重模型(Breiman,1996)給定訓(xùn)練集大小為n，通過從原始數(shù)據(jù)取樣(用替換方法)，創(chuàng)建m個(gè)不同的訓(xùn)練集(大小為n)用簡單的投票方法來合并這m個(gè)模型可用于任何學(xué)習(xí)方法減少了不穩(wěn)定學(xué)習(xí)算法的一般化錯(cuò)誤，即當(dāng)訓(xùn)練數(shù)據(jù)輕微改動(dòng)時(shí)會(huì)導(dǎo)致決策結(jié)果劇烈變動(dòng)的那些學(xué)習(xí)方法27引導(dǎo)(Boosting)另一個(gè)生成多重模型的方法——重復(fù)更改同一個(gè)學(xué)習(xí)算法的數(shù)據(jù)對(duì)弱學(xué)習(xí)算法(假設(shè)的精度只要超過1/2即可)能保證性能的改進(jìn)對(duì)樣本加權(quán)，每次疊代產(chǎn)生一個(gè)新的假設(shè)，對(duì)那些導(dǎo)致最終假設(shè)精度變差的樣本重新加權(quán)基本算法

給所有樣本賦予一個(gè)初始權(quán)重

Forifrom1toTdo

從加權(quán)的樣本中學(xué)習(xí)一個(gè)假設(shè)hi

減小那些與hi一致的樣本的權(quán)重在測(cè)試時(shí)，每個(gè)假設(shè)會(huì)得到一個(gè)加權(quán)的投票(與訓(xùn)練數(shù)據(jù)上的精度成比例)28引導(dǎo)算法ForD中的每個(gè)樣本，令其權(quán)重wi=1/|D|Fortfrom1toTdo

從加權(quán)樣本中學(xué)習(xí)一個(gè)假設(shè)ht

計(jì)算ht的誤差t，作為被錯(cuò)誤