博客園：http://www.cnblogs.com/wxquare/p/5379970.html
ID3（多叉樹）筛峭，C4.5（多叉樹）铐刘，C5.0（多叉樹），CART（二叉樹）影晓，CHAID（多叉樹）镰吵，RandomForest（二叉樹群）。其生成樹的思想大同小異挂签，區(qū)別在于屬性選擇指標(biāo)和樹的形式疤祭。
0. 理解信息熵
1. 決策樹概括
- 決策樹也屬于非線性模型，可以用于分類饵婆，也可用于回歸勺馆。它是一種樹形結(jié)構(gòu)，可以認(rèn)為是if-then規(guī)則的集合侨核，是以實例為基礎(chǔ)的歸納學(xué)習(xí)谓传。基本思想是自頂向下芹关，以信息增益（或信息增益比续挟，基尼系數(shù)等）為度量構(gòu)建一顆度量標(biāo)準(zhǔn)下降最快的樹，每個內(nèi)部節(jié)點代表一個屬性的測試侥衬，直到葉子節(jié)點處只剩下同一類別的樣本诗祸。
- 決策樹的學(xué)習(xí)包括三個重要的步驟，特征選擇轴总，決策樹的生成以及決策樹的剪枝直颅。
- 特征選擇：常用的特征選擇有信息增益，信息增益比怀樟，基尼系數(shù)等功偿。
- 生成過程：通過計算信息增益或其它指標(biāo)，選擇最佳特征往堡。從根結(jié)點開始械荷，遞歸地產(chǎn)生決策樹，不斷的選取局部最優(yōu)的特征虑灰，將訓(xùn)練集分割成能夠基本正確分類的子集吨瞎。
- 剪枝過程：首先定義決策樹的評價指標(biāo)，對于所有的葉子結(jié)點穆咐，累加計算每個葉子結(jié)點中的（樣本數(shù)）與其（葉子節(jié)點熵值）的乘積颤诀，以葉子數(shù)目作為正則項（它的系數(shù)為剪枝系數(shù)）字旭。然后計算每個結(jié)點的剪枝系數(shù)，它的大概含義是刪除該結(jié)點的子樹崖叫，損失不變的前提下遗淳，正則項系數(shù)的值為多少，這個值越小說明該子樹越?jīng)]有存在的必要心傀。依次選取剪枝系數(shù)最小的結(jié)點剪枝洲脂，得到?jīng)Q策樹序列，通過交叉驗證得到最優(yōu)子樹剧包。
優(yōu)點：
- 決策樹算法中學(xué)習(xí)簡單的決策規(guī)則建立決策樹模型的過程非常容易理解恐锦，
- 決策樹模型可以可視化，非常直觀
- 應(yīng)用范圍廣疆液，可用于分類和回歸一铅，而且非常容易做多類別的分類
- 能夠處理數(shù)值型和連續(xù)的樣本特征
缺點：
- 很容易在訓(xùn)練數(shù)據(jù)中生成復(fù)雜的樹結(jié)構(gòu)，造成過擬合（overfitting）堕油。剪枝可以緩解過擬合的負(fù)作用潘飘，常用方法是限制樹的高度、葉子節(jié)點中的最少樣本數(shù)量掉缺。
- 學(xué)習(xí)一棵最優(yōu)的決策樹被認(rèn)為是NP-Complete問題卜录。實際中的決策樹是基于啟發(fā)式的貪心算法建立的，這種算法不能保證建立全局最優(yōu)的決策樹眶明。Random Forest 引入隨機能緩解這個問題
2. ID3算法
ID3由Ross Quinlan在1986年提出艰毒。ID3決策樹可以有多個分支，但是不能處理特征值為連續(xù)的情況搜囱。決策樹是一種貪心算法丑瞧，每次選取的分割數(shù)據(jù)的特征都是當(dāng)前的最佳選擇，并不關(guān)心是否達到最優(yōu)蜀肘。在ID3中绊汹，每次根據(jù)“最大信息熵增益”選取當(dāng)前最佳的特征來分割數(shù)據(jù)，并按照該特征的所有取值來切分扮宠，也就是說如果一個特征有4種取值西乖，數(shù)據(jù)將被切分4份，一旦按某特征切分后坛增，該特征在之后的算法執(zhí)行中获雕，將不再起作用，所以有觀點認(rèn)為這種切分方式過于迅速轿偎。ID3算法十分簡單典鸡，核心是根據(jù)“最大信息熵增益”原則選擇劃分當(dāng)前數(shù)據(jù)集的最好特征被廓，信息熵是信息論里面的概念坏晦，是信息的度量方式，不確定度越大或者說越混亂，熵就越大昆婿。在建立決策樹的過程中球碉，根據(jù)特征屬性劃分?jǐn)?shù)據(jù)，使得原本“混亂”的數(shù)據(jù)的熵(混亂度)減少仓蛆，按照不同特征劃分?jǐn)?shù)據(jù)熵減少的程度會不一樣睁冬。在ID3中選擇熵減少程度最大的特征來劃分?jǐn)?shù)據(jù)（貪心），也就是“最大信息熵增益”原則看疙。下面是計算公式豆拨，建議看鏈接計算信息上增益的實例。
3. C4.5算法
C4.5是Ross Quinlan在1993年在ID3的基礎(chǔ)上改進而提出的能庆。.ID3采用的信息增益度量存在一個缺點施禾，它一般會優(yōu)先選擇有較多屬性值的Feature,因為屬性值多的Feature會有相對較大的信息增益?(信息增益反映的給定一個條件以后不確定性減少的程度,必然是分得越細的數(shù)據(jù)集確定性更高,也就是條件熵越小,信息增益越大).為了避免這個不足C4.5中是用信息增益比率(gain ratio)來作為選擇分支的準(zhǔn)則。信息增益比率通過引入一個被稱作分裂信息(Split information)的項來懲罰取值較多的Feature搁胆。除此之外弥搞，C4.5還彌補了ID3中不能處理特征屬性值連續(xù)的問題。但是渠旁，對連續(xù)屬性值需要掃描排序攀例，會使C4.5性能下降，有興趣可以參考博客
4. CART算法
CART（Classification and Regression tree）分類回歸樹由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出顾腊。ID3中根據(jù)屬性值分割數(shù)據(jù)粤铭，之后該特征不會再起作用，這種快速切割的方式會影響算法的準(zhǔn)確率杂靶。CART是一棵二叉樹承耿，采用二元切分法，每次把數(shù)據(jù)切成兩份伪煤，分別進入左子樹加袋、右子樹。而且每個非葉子節(jié)點都有兩個孩子抱既，所以CART的葉子節(jié)點比非葉子多1职烧。相比ID3和C4.5，CART應(yīng)用要多一些防泵，既可以用于分類也可以用于回歸蚀之。CART分類時，使用基尼指數(shù)（Gini）來選擇最好的數(shù)據(jù)分割的特征捷泞，gini描述的是純度足删，與信息熵的含義相似。CART中每一次迭代都會降低GINI系數(shù)锁右。下圖顯示信息熵增益的一半失受，Gini指數(shù)讶泰，分類誤差率三種評價指標(biāo)非常接近》鞯剑回歸時使用均方差作為loss function痪署。基尼系數(shù)的計算與信息熵增益的方式非常類似兄旬，公式如下
5. 分類樹VS回歸樹
提到?jīng)Q策樹算法狼犯，很多想到的就是上面提到的ID3、C4.5领铐、CART分類決策樹悯森。其實決策樹分為分類樹和回歸樹，前者用于分類绪撵，如晴天/陰天/雨天呐馆、用戶性別、郵件是否是垃圾郵件莲兢，后者用于預(yù)測實數(shù)值汹来，如明天的溫度芦劣、用戶的年齡等佳鳖。
作為對比，先說分類樹豫缨，我們知道ID3谒兄、C4.5分類樹在每次分枝時摔桦，是窮舉每一個特征屬性的每一個閾值，找到使得按照feature<=閾值承疲，和feature>閾值分成的兩個分枝的熵最大的feature和閾值邻耕。按照該標(biāo)準(zhǔn)分枝得到兩個新節(jié)點，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點燕鸽，或達到預(yù)設(shè)的終止條件兄世，若最終葉子節(jié)點中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點的性別啊研。
回歸樹總體流程也是類似御滩，不過在每個節(jié)點（不一定是葉子節(jié)點）都會得一個預(yù)測值，以年齡為例党远，該預(yù)測值等于屬于這個節(jié)點的所有人年齡的平均值削解。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標(biāo)準(zhǔn)不再是最大熵沟娱，而是最小化均方差--即（每個人的年齡-預(yù)測年齡）^2 的總和 / N氛驮，或者說是每個人的預(yù)測誤差平方和 除以 N。這很好理解济似，被預(yù)測出錯的人數(shù)越多矫废，錯的越離譜盏缤，均方差就越大，通過最小化均方差能夠找到最靠譜的分枝依據(jù)磷脯。分枝直到每個葉子節(jié)點上人的年齡都唯一（這太難了）或者達到預(yù)設(shè)的終止條件（如葉子個數(shù)上限）蛾找，若最終葉子節(jié)點上人的年齡不唯一娩脾，則以該節(jié)點上所有人的平均年齡做為該葉子節(jié)點的預(yù)測年齡赵誓。
