<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>
基本概念
決策樹（decision tree）是一種常見的機(jī)器學(xué)習(xí)方法，它是基于樹結(jié)構(gòu)來進(jìn)行決策的香嗓，這恰是人類在面臨決策問題時(shí)一種很自然的處理機(jī)制。人類在對(duì)一個(gè)問題進(jìn)行決策時(shí)全肮，通常會(huì)進(jìn)行一系列的“子決策”塞蹭，最后得出最終決策。
它既可以作為分類算法，也可以作為回歸算法驼抹，同時(shí)也特別適合集成學(xué)習(xí)比如隨機(jī)森林桑孩。
先來了解一下決策樹的基本流程：
這個(gè)例子中要根據(jù)房產(chǎn)拜鹤、婚姻情況框冀、年收入這三個(gè)特征（屬性）對(duì)10個(gè)樣本數(shù)據(jù)進(jìn)行決策，判斷一個(gè)人是否能夠償還債務(wù)敏簿，可以構(gòu)建如下的決策樹：
一般的明也，一棵決策樹包含一個(gè)根結(jié)點(diǎn)、若干個(gè)內(nèi)部結(jié)點(diǎn)和若干個(gè)葉結(jié)點(diǎn)惯裕。葉結(jié)點(diǎn)對(duì)應(yīng)于最終決策結(jié)果（該例中為“可以償還”和“無法償還”）温数，其他每個(gè)結(jié)點(diǎn)則對(duì)應(yīng)于一個(gè)屬性測(cè)試，根結(jié)點(diǎn)包含樣本全集（該例中為“擁有房產(chǎn)”）蜻势。
決策樹學(xué)習(xí)的目的是為了產(chǎn)生一顆泛化能力強(qiáng)撑刺，即處理未見事例能力強(qiáng)的決策樹。
劃分選擇
決策樹學(xué)習(xí)的難點(diǎn)握玛，就是如何選擇最優(yōu)劃分屬性够傍，特別是當(dāng)特征比較多的時(shí)候，到底應(yīng)該拿哪個(gè)特征當(dāng)根結(jié)點(diǎn)呢挠铲？這就要求我們選取一個(gè)衡量標(biāo)準(zhǔn)冕屯。
熱力學(xué)熵
熵最早來原于物理學(xué)，用于度量一個(gè)熱力學(xué)系統(tǒng)的無序程度拂苹，可以測(cè)量一個(gè)粒子移動(dòng)的自由程度安聘。拿水的三態(tài)舉例:
- 固態(tài)冰中的粒子活動(dòng)空間較小，其結(jié)構(gòu)比較穩(wěn)固瓢棒，粒子大都固定不動(dòng)浴韭。
- 液態(tài)水的粒子結(jié)構(gòu)穩(wěn)固程度次之，粒子有一定的活動(dòng)空間脯宿。
- 水蒸氣的結(jié)構(gòu)則處于另一個(gè)極端囱桨，一個(gè)粒子的去向有多種可能性，可經(jīng)常移動(dòng)嗅绰。
因此舍肠，固態(tài)冰的熵很低，液態(tài)水的熵居中窘面，水蒸氣的熵最高翠语。
信息熵
熵的概念也可以用概率解釋，看下面這個(gè)例子：
上圖的三個(gè)水桶中各有四個(gè)球财边，這些球除了顏色不一樣肌括，其它完全無法進(jìn)行區(qū)分，因此，如果將這些小球全部放成一條直線谍夭，熵就是這些球移動(dòng)的自由程度黑滴。
- 第一個(gè)桶的結(jié)構(gòu)較為固定，無論如何擺放小球紧索，它們總是處于同一狀態(tài)袁辈，因此它的熵最低。
- 第二個(gè)桶中珠漂，我們有4種方式擺放小球晚缩，因此它的熵居中。
- 第三個(gè)桶中媳危，有6中重組球的方法荞彼，因此其熵最高。
以上并不是熵最準(zhǔn)確的定義待笑，但它給我我們這樣一個(gè)觀點(diǎn)：集合越穩(wěn)固或越具有同類性鸣皂，其熵越低，反之亦然暮蹂。
另一種看待熵的方式是依據(jù)知識(shí)寞缝，再來看水桶這個(gè)例子：
如果我們要從水桶中隨機(jī)選出一個(gè)球，我們有多大可能知道球的顏色椎侠？
- 第一個(gè)桶中第租，我們知道該球的顏色必然是紅色的，所以其知識(shí)較高我纪。
- 第二個(gè)桶中慎宾，該球?yàn)榧t色的可能性很大，而為藍(lán)色的可能性較小浅悉，若我們認(rèn)定該球?yàn)榧t色趟据，那絕大多數(shù)情況下，結(jié)果是對(duì)的术健，因此我們對(duì)該球的顏色的知識(shí)居中汹碱。
- 第三個(gè)桶中，該球顏色為紅色和藍(lán)色的可能性一樣大荞估，因此其知識(shí)較低咳促。
結(jié)果顯示，熵和知識(shí)相反勘伺，一個(gè)集合的知識(shí)越高跪腹，其熵越低，反之亦然飞醉。
現(xiàn)在還是回到上面這三個(gè)水桶冲茸，我們來玩?zhèn)€游戲，游戲規(guī)則是：我們重復(fù)地從桶中取出四個(gè)球，每次將球放回轴术，盡量使取出的四個(gè)球的顏色與桶中起初的四個(gè)球的顏色一致难衰。
舉個(gè)例子，對(duì)第二個(gè)三紅一藍(lán)的水桶來說逗栽，若左邊取出的四個(gè)小球的顏色和順序與原來桶中一模一樣盖袭，則該桶贏得比賽，反之祭陷，則輸了比賽苍凛。
現(xiàn)在的問題是趣席，若我們要贏得這個(gè)比賽兵志，以上三個(gè)水桶哪個(gè)是最佳選擇宣肚？
我們來計(jì)算一下每個(gè)水桶贏得比賽的概率，由于每次取小球都是相互獨(dú)立的霉涨，我們可以計(jì)算出：
P(1)=1\times1\times1\times1=1
P(2)=\frac{3}{4}\times\frac{3}{4}\times\frac{3}{4}\times\frac{1}{4}=0.105
P(3)=\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}=0.0625
因此，第一個(gè)水桶贏得比賽的概率最高笙瑟，第二個(gè)次之，第三個(gè)最低往枷。
當(dāng)有1000個(gè)小球時(shí)，概率的計(jì)算結(jié)果有可能會(huì)非常小错洁，而且稍微改變其中一個(gè)因素秉宿，就會(huì)對(duì)最后的積產(chǎn)生極大的影響屯碴，為了使得結(jié)果更加可控，我們采用log函數(shù)將積轉(zhuǎn)換為和（信息論中采用底數(shù)為2的對(duì)數(shù)函數(shù)）忱叭。
-\log_2{P(1)}=-(\log_2{1}+\log_2{1}+\log_2{1}+\log_2{1})=0
-\log_2{P(2)}=-(\log_2{0.75}+\log_2{0.75}+\log_2{0.75}+\log_2{0.25})=3.245
-\log_2{P(3)}=-(\log_2{0.5}+\log_2{0.5}+\log_2{0.5}+\log_2{0.5})=4
使用熵的定義為以我們贏得游戲的方式取出球的概率的對(duì)數(shù)的平均值韵丑，因此洼滚，第一個(gè)水桶的熵為0，第二個(gè)水桶的熵為0.81千康，第三個(gè)水桶的熵為1拾弃。
假設(shè)第4個(gè)水桶中有5個(gè)紅球和3個(gè)籃球：
計(jì)算這個(gè)水桶的熵：
Entropy=-\frac{5}{8}\log_2\left(\frac{5}{8}\right)-\frac{3}{8}\log_2\left(\frac{3}{8}\right)=0.9544
當(dāng)有m個(gè)紅球和n個(gè)藍(lán)球：
Entropy=-\frac{m}{m+n}\log_2\left(\frac{m}{m+n}\right)-\frac{n}{m+n}\log_2\left(\frac{n}{m+n}\right)
信息熵（information entropy）是度量樣本集合純度最常用的一種指標(biāo)豪椿，假定當(dāng)前樣本集合D中第k類樣本所占的比例為p_k(k=1,2,...,|y|)搭盾，則D的信息熵定義為：
Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2p_k
Ent(D)的值越小，樣本集合D的純度越高鸯隅，越具有同類性。
決策樹ID3算法
信息增益計(jì)算方法：
information \ gain=Entropy(parent)-0.5\left[Entropy(child1)+Entropy(child2)\right]
根據(jù)信息熵公式炕舵，我們可以計(jì)算：
Entropy(parent)=-\frac{10}{20}\log_2\left(\frac{10}{20}\right)-\frac{10}{20}\log_2\left(\frac{10}{20}\right)=1
Entropy(child1)=-\frac{2}{10}\log_2\left(\frac{2}{10}\right)-\frac{8}{10}\log_2\left(\frac{8}{10}\right)=0.72
Entropy(child2)=-\frac{8}{10}\log_2\left(\frac{8}{10}\right)-\frac{2}{10}\log_2\left(\frac{2}{10}\right)=0.72
information \ gain=1-0.72=0.28
假定離散屬性a有V個(gè)可能的取值\{a^1, a^2, ...,a^V\}咽筋，若使用a來對(duì)樣本集合D進(jìn)行劃分奸攻，則會(huì)產(chǎn)生V個(gè)分支結(jié)點(diǎn)庇忌，可以根據(jù)信息熵公式計(jì)算出每個(gè)分支結(jié)點(diǎn)的信息熵皆疹，考慮到不同分支結(jié)點(diǎn)所包含的樣本數(shù)的不同，給分支結(jié)點(diǎn)賦予權(quán)重\frac{|D^v|}{|D|}捎迫，于是可以計(jì)算出用屬性a對(duì)樣本集D進(jìn)行劃分所獲得的信息增益：
Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
一般而言窄绒，信息增益越大崔兴，則意味著使用屬性a來進(jìn)行劃分所獲得的“純度提升”越大。因此山析，在進(jìn)行決策樹的劃分屬性選擇時(shí)掏父，選擇屬性a_* =\underset{a\in A}{\operatorname{argmax} }Gain(D,a)赊淑，著名的ID3決策樹學(xué)習(xí)算法[Quinlan,1986]就是以信息增益為準(zhǔn)則來選擇劃分屬性。
下面我們看看具體算法過程大概是怎么樣的钾挟。
假設(shè)輸入的是m個(gè)樣本等龙，樣本輸出集合為D伶贰，每個(gè)樣本有n個(gè)離散特征黍衙，特征集合即為A荠诬，輸出為決策樹T柑贞，算法的過程為：
- 初始化信息增益的閾?钧嘶。
- 判斷樣本是否為同一類輸出D_i，如果是則返回單節(jié)點(diǎn)樹T闸拿，標(biāo)記類別為D_i新荤。
- 判斷特征是否為空台汇，如果是則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別奔缠。
- 計(jì)算特征集合A中的各個(gè)特征（一共n個(gè)）對(duì)輸出D的信息增益吼野，選擇信息增益最大的特征A_g
- 如果A_g的信息增益小于閾值?瞳步，則返回單節(jié)點(diǎn)樹T单起，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別。
- 否則屈留，按特征A_g的不同取值A_{gi}將對(duì)應(yīng)的樣本輸出D分成不同的類別Di灌危，每個(gè)類別產(chǎn)生一個(gè)子節(jié)點(diǎn)勇蝙，對(duì)應(yīng)特征值為 A_{gi}挨约，返回增加了節(jié)點(diǎn)的樹T诫惭。
- 對(duì)于所有的子節(jié)點(diǎn)，令D=D_i , A=A-\{A_g\}遞歸調(diào)用2-6步馆衔，得到子樹Ti并返回哈踱。
決策樹ID3算法的不足
ID3算法雖然提出了新思路梨熙，但是還是有很多值得改進(jìn)的地方：
- ID3沒有考慮連續(xù)特征咽扇，比如長(zhǎng)度、密度都是連續(xù)值树埠，無法在ID3運(yùn)用怎憋，這大大限制了ID3的用途绊袋。
- ID3采用信息增益大的特征優(yōu)先建立決策樹的節(jié)點(diǎn)，但信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好皂岔。
- 算法對(duì)于缺失值的情況沒有做考慮躁垛。
- 沒有考慮過擬合的問題圾笨。
決策樹C4.5算法
ID3 算法的作者昆蘭基于上述不足墅拭，對(duì)ID3算法做了改進(jìn)谍婉，這就是C4.5算法[Quinlan,1993]镀钓，針對(duì)上述的第二個(gè)問題丁溅，它使用“增益率”（gain ratio）來選擇最后劃分屬性，其定義為：
Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}
其中妓柜，IV(a)稱為屬性a的“固有值”（intrinsic value）棍掐，其定義為：
IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}
屬性a的可能取值數(shù)目越多作煌，則IV(a)的值通常會(huì)越大粟誓。
需要注意的是，增益率準(zhǔn)則對(duì)可取數(shù)值數(shù)目較少的屬性有所偏好病瞳，因此仍源，C4.5算法并不是直接選擇增益率最大的候選劃分屬性舔涎，而是先從候選劃分屬性中找出信息增益高于平均水平的屬性亡嫌，再?gòu)闹羞x擇增益率最高的挟冠。
針對(duì)上述第一個(gè)問題，不能處理連續(xù)特征肋僧，C4.5的思路是采用二分法（bi-partition）將連續(xù)的特征離散化嫌吠。比如m個(gè)樣本的連續(xù)特征A有m個(gè)辫诅，從小到大排列為a_1,a_2,...,a_m,則C4.5取相鄰兩樣本值的平均數(shù)涧狮，一共取得m-1個(gè)劃分點(diǎn)者冤，其中第i個(gè)劃分點(diǎn)T_i表示為：T_i=\frac{a_i + a_{i+1}}{2}涉枫。對(duì)于這m-1個(gè)點(diǎn)，分別計(jì)算以該點(diǎn)作為二元分類點(diǎn)時(shí)的信息增益殊鞭，選擇信息增益最大的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)操灿。
要注意的是趾盐，與離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為連續(xù)屬性久窟，則該屬性后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過程斥扛。
對(duì)于第三個(gè)缺失值處理的問題稀颁，主要需要解決的是兩個(gè)問題楣黍，一是在樣本某些特征缺失的情況下選擇劃分的屬性租漂；二是選定了劃分屬性哩治，對(duì)于在該屬性上缺失特征的樣本的處理。
對(duì)于第一個(gè)子問題吞瞪，對(duì)于某一個(gè)有缺失特征值的特征A ，C4.5的思路是將數(shù)據(jù)分成兩部分翠勉，對(duì)每個(gè)樣本設(shè)置一個(gè)權(quán)重（初始可以都為1）对碌，然后劃分?jǐn)?shù)據(jù)蒿偎，一部分是有特征值A的數(shù)據(jù)D_1，另一部分是沒有特征A的數(shù)據(jù)D_2菜枷。然后對(duì)于沒有缺失特征A的數(shù)據(jù)集D_1來和對(duì)應(yīng)的A特征的各個(gè)特征值一起計(jì)算加權(quán)重后的增益率
啤誊，最后乘上一個(gè)系數(shù)蚊锹，這個(gè)系數(shù)是無特征A缺失的樣本加權(quán)后所占加權(quán)總樣本的比例牡昆。
對(duì)于第二個(gè)子問題摊欠，可以將缺失特征的樣本同時(shí)劃分入所有的子節(jié)點(diǎn)凄硼，不過將該樣本的權(quán)重按各個(gè)子節(jié)點(diǎn)樣本的數(shù)量比例來分配摊沉。比如缺失特征A的樣本a之前權(quán)重為1说墨，特征A有3個(gè)特征值A_1 ,A_2,A_3，3個(gè)特征值對(duì)應(yīng)的無缺失A特征的樣本個(gè)數(shù)為2,3,4姜贡，則a同時(shí)劃分入A_1,A_2,A_3楼咳，對(duì)應(yīng)權(quán)重調(diào)節(jié)為\frac{2}{9},\frac{3}{9},\frac{4}{9}母怜。
對(duì)于第4個(gè)問題苹熏，C4.5引入了正則化系數(shù)進(jìn)行初步的剪枝轨域。
除了上面的4點(diǎn)，C4.5和ID3的思路區(qū)別不大朱巨。
C5.0是 Quinlan 根據(jù)專有許可證發(fā)布的最新版本蔬崩，它使用更少的內(nèi)存沥阳，并建立比 C4.5 更小的規(guī)則集自点，同時(shí)更準(zhǔn)確桂敛。
決策樹C4.5算法的不足
C4.5雖然改進(jìn)或者改善了ID3算法的幾個(gè)主要的問題术唬，仍然有優(yōu)化的空間：
- 由于決策樹算法非常容易過擬合粗仓，因此對(duì)于生成的決策樹必須要進(jìn)行剪枝借浊。剪枝的算法有非常多，C4.5的剪枝方法有優(yōu)化的空間存捺。
- C4.5生成的是多叉樹捌治，即一個(gè)父節(jié)點(diǎn)可以有多個(gè)節(jié)點(diǎn)具滴。很多時(shí)候，在計(jì)算機(jī)中二叉樹模型會(huì)比多叉樹運(yùn)算效率高趋艘。如果采用二叉樹瓷胧，可以提高效率。
- C4.5只能用于分類杂数，如果能將決策樹用于回歸的話可以擴(kuò)大它的使用范圍揍移。
- C4.5由于使用了熵模型那伐，里面有大量的耗時(shí)的對(duì)數(shù)運(yùn)算罕邀，如果是連續(xù)值還有大量的排序運(yùn)算诉探。如果能夠加以模型簡(jiǎn)化可以減少運(yùn)算強(qiáng)度但又不犧牲太多準(zhǔn)確性的話肾胯，那就更好了定铜。
決策樹CART算法
CART（Classification and Regression Trees （分類和回歸樹））與 C4.5 非常相似揣炕，但它不同之處在于它支持?jǐn)?shù)值目標(biāo)變量（回歸）畸陡，并且不計(jì)算規(guī)則集丁恭。
CART決策樹采用“基尼指數(shù)”（Gini index）來選擇劃分屬性牲览，其定義為：
Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\neq{1}}p_kp_{k'}=1-\sum_{k=1}^{|y|}p_k^2
Gini(D)越小，則數(shù)據(jù)集的純度越高兔港。
屬性a的基尼指數(shù)定義為：
Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)
在候選屬性集合中衫樊，選擇使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性科侈。
同時(shí)臀栈，為了進(jìn)一步簡(jiǎn)化挂脑，CART分類樹算法每次僅僅對(duì)某個(gè)特征的值進(jìn)行二分欲侮，而不是多分威蕉，這樣CART分類樹算法建立起來的是二叉樹韧涨，而不是多叉樹虑粥。這樣一可以進(jìn)一步簡(jiǎn)化基尼系數(shù)的計(jì)算，二可以建立一個(gè)更加優(yōu)雅的二叉樹模型娩贷，比如：
如果某個(gè)特征A被選取建立決策樹節(jié)點(diǎn)第晰，如果它有A_1,A_2,A_3三種類別，CART分類樹會(huì)考慮把A分成\{A_1\}和\{A_2,A_3\}, \{A_2\}和\{A_1,A_3\}, \{A_3\}和\{A_1,A_2\}三種情況彬祖，找到基尼系數(shù)最小的組合茁瘦，比如\{A_2\}和\{A_1,A_3\},然后建立二叉樹節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)是A_2對(duì)應(yīng)的樣本储笑，另一個(gè)節(jié)點(diǎn)是\{A_1,A_3\}對(duì)應(yīng)的節(jié)點(diǎn)甜熔。
CART采用后剪枝法進(jìn)行剪枝（pruning）突倍，即先生成決策樹腔稀，然后產(chǎn)生所有可能的剪枝后的CART樹盆昙，然后使用交叉驗(yàn)證來檢驗(yàn)各種剪枝的效果，選擇泛化能力最好的剪枝策略烧颖。
決策樹CART算法的不足
- 無論是ID3, C4.5還是CART弱左，在做特征選擇的時(shí)候都是選擇最優(yōu)的一個(gè)特征來做分類決策，所形成的分類邊界的每一段都是與坐標(biāo)軸平行的炕淮，當(dāng)學(xué)習(xí)任務(wù)的真實(shí)分類邊界比較復(fù)雜時(shí)，必須使用很多段劃分才能獲得較好的近似跳夭，此時(shí)預(yù)測(cè)時(shí)間開銷會(huì)很大涂圆。使用多變量決策樹(multi-variate decision tree)可大大簡(jiǎn)化模型，它在學(xué)習(xí)過程中币叹，不是為每個(gè)非葉結(jié)點(diǎn)尋找一個(gè)最優(yōu)劃分屬性润歉，而是試圖建立一個(gè)合適的線性分類器。主要算法有OC1颈抚。
- 如果樣本發(fā)生一點(diǎn)點(diǎn)的改動(dòng)踩衩，就會(huì)導(dǎo)致樹結(jié)構(gòu)的劇烈改變。這個(gè)可以通過集成學(xué)習(xí)里面的隨機(jī)森林之類的方法解決贩汉。
決策樹算法小結(jié)
下表給出了ID3驱富，C4.5和CART的一個(gè)比較：
| 算法 | 支持模型 | 樹結(jié)構(gòu) | 特征選擇 | 連續(xù)值處理 | 缺失值處理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分類 | 多叉樹 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分類 | 多叉樹 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分類，回歸 | 二叉樹 | 基尼系數(shù)匹舞，均方差 | 支持 | 支持 | 支持 |
決策樹算法優(yōu)點(diǎn)：
- 簡(jiǎn)單直觀褐鸥，在邏輯上可以得到很好的解釋。
- 訓(xùn)練需要的數(shù)據(jù)少赐稽，基本不需要預(yù)處理叫榕，不需要提前歸一化、處理缺失值姊舵。
- 使用決策樹預(yù)測(cè)的代價(jià)是O(log_2m)晰绎，m為樣本數(shù)。
- 既可以處理離散值也可以處理連續(xù)值括丁。
- 可以處理多維度輸出的分類問題荞下。
- 可以交叉驗(yàn)證的剪枝來選擇模型，從而提高泛化能力躏将。
- 對(duì)于異常點(diǎn)的容錯(cuò)能力好锄弱，健壯性高。
決策樹算法缺點(diǎn)：
- 決策樹算法非常容易過擬合祸憋，導(dǎo)致泛化能力不強(qiáng)会宪。這個(gè)問題可以通過剪枝、設(shè)置節(jié)點(diǎn)最少樣本數(shù)量和限制決策樹深度來改進(jìn)蚯窥。
- 決策樹可能是不穩(wěn)定的掸鹅，因?yàn)閿?shù)據(jù)中的微小變化可能會(huì)導(dǎo)致完全不同的樹生成塞帐。這個(gè)問題可以通過集成學(xué)習(xí)之類的方法解決。
- 在多方面性能最優(yōu)和簡(jiǎn)單化概念的要求下巍沙，學(xué)習(xí)一棵最優(yōu)決策樹通常是一個(gè)NP難問題葵姥。因此，實(shí)際的決策樹學(xué)習(xí)算法是基于啟發(fā)式算法句携，例如在每個(gè)節(jié)點(diǎn)進(jìn) 行局部最優(yōu)決策的貪心算法榔幸。這樣的算法不能保證返回全局最優(yōu)決策樹。這個(gè)問題可以通過集成學(xué)習(xí)來訓(xùn)練多棵決策樹來緩解矮嫉，這多棵決策樹一般通過對(duì)特征和樣本有放回的隨機(jī)采樣來生成削咆。
- 有些比較復(fù)雜的關(guān)系，決策樹很難學(xué)習(xí)蠢笋，比如異或 拨齐，一般這種關(guān)系可以換神經(jīng)網(wǎng)絡(luò)分類方法來解決。
- 如果某些類在問題中占主導(dǎo)地位會(huì)使得創(chuàng)建的決策樹有偏差昨寞。因此瞻惋，建議在擬合前先對(duì)數(shù)據(jù)集進(jìn)行平衡。
Reference:
[1]周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社援岩，2016：73-95.
[2]http://sklearn.apachecn.org/cn/latest/modules/tree.html#tree-algorithms.
[3]http://www.cnblogs.com/pinard/p/6050306.html.
[4]http://www.cnblogs.com/pinard/p/6053344.html.
[5]https://www.cnblogs.com/nowgood/p/Latexstart.html.
