決策樹是機(jī)器學(xué)習(xí)中非常經(jīng)典的一類學(xué)習(xí)算法，它通過樹的結(jié)構(gòu)革半，利用樹的分支來表示對樣本特征的判斷規(guī)則丛晦，從樹的葉子節(jié)點所包含的訓(xùn)練樣本中得到預(yù)測值。決策樹如何生成決定了所能處理的數(shù)據(jù)類型和預(yù)測性能涩馆。主要的決策樹算法包括ID3行施，C4.5， CART等魂那。
ID3
ID3是由 Ross Quinlan在1986年提出的一種構(gòu)造決策樹的方法蛾号。用于處理標(biāo)稱型數(shù)據(jù)集。
在節(jié)點上選取能對該節(jié)點處的訓(xùn)練數(shù)據(jù)進(jìn)行最優(yōu)劃分的屬性涯雅。最后劃分的標(biāo)準(zhǔn)是信息增益（Information Gain）鲜结。
ID3的特點是：（1）容易造成過度擬合。（2） 使用標(biāo)稱型數(shù)據(jù)活逆，但是很難處理連續(xù)型數(shù)據(jù)精刷。
C4.5
C4.5是對ID3的改進(jìn)，其基本過程與ID3類似蔗候，改進(jìn)的地方在于：
（1）既能處理標(biāo)稱型數(shù)據(jù)怒允，又能連續(xù)型數(shù)據(jù)。為了處理連續(xù)型數(shù)據(jù)锈遥，該算法在相應(yīng)的節(jié)點使用一個屬性的閾值误算，利用閾值將樣本劃分成兩部分仰美。
（2）能處理缺失了一些屬性的數(shù)據(jù)。該算法允許屬性值缺失時被標(biāo)記為儿礼？咖杂，屬性值缺失的樣本在計算熵增益時被忽略。
（3）構(gòu)造完成后可以剪枝蚊夫。合并相鄰的無法產(chǎn)生大量信息增益的葉節(jié)點诉字，消除過渡匹配問題。
3知纷，CART
CART稱為分類決策樹（二叉樹）壤圃，既能處理分類問題，又能處理回歸問題琅轧。與ID3不能直接處理連續(xù)型特征不同的是伍绳，CART使用二元切分，即使用一個屬性閾值對樣本數(shù)據(jù)進(jìn)行劃分乍桂。劃分的標(biāo)準(zhǔn)除了使用熵增益外冲杀，還有基尼純凈度（Gini impurity）和方差縮減（variance reduction)（用于回歸）。
ID3算法是決策樹的一個經(jīng)典的構(gòu)造算法睹酌，在一段時期內(nèi)曾是同類研究工作的比較對象权谁，但通過近些年國內(nèi)外學(xué)者的研究，ID3算法也暴露出一些問題憋沿，具體如下： (1)信息增益的計算依賴于特征數(shù)目較多的特征旺芽，而屬性取值最多的屬性并不一定最優(yōu)。
(2)ID3是非遞增算法辐啄。
(3)ID3是單變量決策樹(在分枝節(jié)點上只考慮單個屬性)采章，許多復(fù)雜概念的表達(dá)困難，屬性相互關(guān)系強(qiáng)調(diào)不夠壶辜，容易導(dǎo)致決策樹中子樹的重復(fù)或有些屬性在決策樹的某一路徑上被檢驗多次悯舟。
(4)抗噪性差，訓(xùn)練例子中正例和反例的比例較難控制士复。
于是Quilan改進(jìn)了ID3，提出了C4.5算法翩活。C4.5算法現(xiàn)在已經(jīng)成為最經(jīng)典的決策樹構(gòu)造算法阱洪，排名數(shù)據(jù)挖掘十大經(jīng)典算法之首，下一篇文章將重點討論菠镇。
決策樹的經(jīng)典構(gòu)造算法——C4.5（WEKA中稱J48）
由于ID3算法在實際應(yīng)用中存在一些問題冗荸，于是Quilan提出了C4.5算法，嚴(yán)格上說C4.5只能是ID3的一個改進(jìn)算法利耍。
C4.5算法繼承了ID3算法的優(yōu)點蚌本，并在以下幾方面對ID3算法進(jìn)行了改進(jìn)：
1) 用信息增益率來選擇屬性盔粹，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構(gòu)造過程中進(jìn)行剪枝程癌；
3) 能夠完成對連續(xù)屬性的離散化處理舷嗡；
4) 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。
C4.5算法有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解嵌莉，準(zhǔn)確率較高进萄。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序锐峭，因而導(dǎo)致算法的低效中鼠。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集沿癞，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行援雇。
另外，無論是ID3還是C4.5最好在小數(shù)據(jù)集上使用椎扬，決策樹分類一般只試用于小數(shù)據(jù)惫搏。當(dāng)屬性取值很多時最好選擇C4.5算法，ID3得出的效果會非常差盗舰。
