決策樹演算法中，CART與ID3、C4.5特徵選擇之間的區別會對實際應用有哪些影響？哪種的結果會更好些？

12-30

是不是CART只應用與連續型數據，其他兩個應用在離散型數據？

歷史回顧：1984年提出的cart，1986年提出的ID3，1993年提出的c4.5

理論上總的來說，

C4.5是基於ID3優化後產出的演算法，主要優化了關於節點分支的計算方式，優化後解決了ID3分支過程中總喜歡偏向取值較多的屬性

ID3是信息增益分支：

而CART一般是GINI係數分支：

C4.5一般是信息增益率分支：

工程上總的來說：

CART和C4.5之間主要差異在於分類結果上，CART可以回歸分析也可以分類，C4.5隻能做分類；C4.5子節點是可以多分的，而CART是無數個二叉子節點；

以此拓展出以CART為基礎的「樹群」Random forest ，以回歸樹為基礎的「樹群」GBDT

樣本數據的差異：

ID3隻能對分類變數進行處理，C4.5和CART可以處理連續和分類兩種自變數
ID3對缺失值敏感，而C4.5和CART對缺失值可以進行多種方式的處理
只從樣本量考慮，小樣本建議考慮c4.5、大樣本建議考慮cart。c4.5處理過程中需對數據集進行多次排序，處理成本耗時較高，而cart本身是一種大樣本的統計方法，小樣本處理下泛化誤差較大

目標因變數的差異：

ID3和C4.5隻能做分類，CART（分類回歸樹）不僅可以做分類（0/1）還可以做回歸（0-1）
ID3和C4.5節點上可以產出多叉（低、中、高），而CART節點上永遠是二叉（低、非低）

樣本特徵上的差異：

特徵變數的使用中，多分的分類變數ID3和C4.5層級之間只單次使用，CART可多次重複使用

決策樹產生過程中的優化差異：

C4.5是通過枝剪來修正樹的準確性，而CART是直接利用全部數據發現所有樹的結構進行對比

很久之前整理過一些關於決策樹及分散式下的決策樹處理的理論：決策樹類演算法 - 博客頻道 - CSDN.NET

最後，希望能對你有所幫助，謝謝。

ID3演算法在選擇根節點和內部節點中的分支屬性時，採用信息增益作為評價標準。信息增益的缺點是傾向於選擇取值較多的屬性，在有些情況下這類屬性可能不會提供太多有價值的信息。

C4.5演算法主要做出了以下方面的改進

1：可以處理連續數值型屬性

對於離散值，C4.5和ID3的處理方法相同，對於某個屬性的值連續時，假設這這個節點上的數據集合樣本為total，C4.5演算法進行如下處理：

將樣本數據該屬性A上的具體數值按照升序排列，得到屬性序列值：{A1,A2,A3,...,Atotal}
在上一步生成的序列值中生成total-1個分割點。第i個分割點的取值為Ai和Ai+1的均值，每個分割點都將屬性序列劃分為兩個子集。
計算每個分割點的信息增益(Information Gain),得到total-1個信息增益。
對分裂點的信息增益進行修正：減去log2(N-1)/|D|，其中N為可能的分裂點個數，D為數據集合大小。
選擇修正後的信息增益值最大的分類點作為該屬性的最佳分類點
計算最佳分裂點的信息增益率(Gain Ratio)作為該屬性的Gain Ratio
選擇Gain Ratio最大的屬性作為分類屬性。

參考：

Decision Tree：ID3、C4.5

CART的全稱是Classification and Regression Tree, 當然既能處理離散形也能處理連續形的數據.

C4.5也能處理連續形的數據, 具體方式跟CART里Regression Tree里出來方式差不多, 把數據排序以後找到類別不同的分割線做來切分, 根據切分點把連續屬性轉成bool形, 按照信息增益比率來選最優的切分點.

至於ID3, 好像只能處理離散形的數據.

我這裡有一篇關於決策樹的博客, 可以參考: http://leijun00.github.io/2014/09/decision-tree/

ID3演算法：

以信息增益為準則選擇信息增益最大的屬性。

缺點：1）信息增益對可取值數目較多的屬性有所偏好，比如通過ID號可將每個樣本分成一類，但是沒有意義。2）ID3隻能對離散屬性的數據集構造決策樹。

鑒於以上缺點，後來出現了C4.5演算法。

C4.5演算法：

以信息增益率為準則選擇屬性；在信息增益的基礎上對屬性有一個懲罰，抑制可取值較多的屬性，增強泛化性能。

其他優點：1）在樹的構造過程中可以進行剪枝，緩解過擬合；2）能夠對連續屬性進行離散化處理（二分法）；3）能夠對缺失值進行處理；

缺點：構造樹的過程需要對數據集進行多次順序掃描和排序，導致演算法低效；

剛才我們提到 信息增益對可取值數目較多的屬性有所偏好；而信息增益率對可取值數目較少的屬性有所偏好！OK，兩者結合一下就好了！

解決方法：先從候選屬性中找出信息增益高於平均水平的屬性，再從中選擇增益率最高的。而不是大家常說的直接選擇信息增益率最高的屬性！

CART演算法（Classification and Regression Tree）：

顧名思義，可以進行分類和回歸，可以處理離散屬性，也可以處理連續的。

分類樹使用GINI指數來選擇劃分屬性：在所有候選屬性中，選擇劃分後GINI指數最小的屬性作為優先劃分屬性。回歸樹就用最小平方差。

參考：

1.《機器學習》周志華

2.CART分類與回歸樹的原理與實現

1、先說CART

CART中文叫分類與回歸樹，既可以用於分類也可以用於回歸。

CART生成的樹是二叉樹，在選擇變數的過程中，對回歸樹用平方誤差最小準則，對分類樹用基尼指數最小化準則

2、再說ID3

ID3隻能用於分類問題。

ID3最重要的是用信息增益去篩選變數，可以生成多叉樹，但好像不能存在缺失值，需要對確實值進行處理（這個需要確認下）

3、C4.5

用信息增益篩選變數會存在這樣一個問題：模型偏向於選擇取值較多的變數，比如id，但這是沒有意義的，因此C4.5採用信息增益率的方式去選擇變數，就避免了這個問題。

C4.5可以允許變數存在缺失值，會把缺失值單獨作為一類或者按概率分到每一個子樹上。