決策樹算法ID3、C4.5、CART初探

這兩天在學習決策樹的時候對決策樹特征選擇搞得有點混亂，在對李航老師的《統計學習方法》進行反複研讀後，對此有了新的認識，也理清了思路。以下是我在李航老師的基礎上加了一些自己的了解，有不對的地方歡迎大家批評指正。

1 ID3算法中的特征選擇

2 C4.5算法中的特征選擇

ID3算法利用資訊增益作為選擇訓練資料集特征選取的依據，存在選擇取值較多的特征來對資料集進行分割的偏向。使用 資訊增益比來進行特征的選取可以對這一問題進行校正。進而C4.5算法産生了。

3 CART算法中的特征選擇

CART算法中，決策樹的生成就是遞歸地建構二叉樹的過程。對回歸樹用平方誤差最小化準則，對分類樹用基尼指數最小化準則，進行特征選擇，生成二叉樹。

3.1 回歸樹的特征選擇

當以x作為切分變量，以x=4為切分值時，其平方誤差的計算過程為：

依次以x=1、x=2、x=3……x=10為切分點時的平方誤差，選取其中平方誤差最小的點為切分點。

例子的變量隻有一個，當有多個變量時，首先選取每個特征的最優切分點，然後在比較每個變量最優切分點對應的平方誤差。選取其中平方誤差最小的切分點所在的變量作為切分變量，以該變量對應的最優切分點為最終的切分點。

3.2 分類樹的特征選擇

CART算法的分類樹用基尼指數選擇最優特征，同時決定該特征的最優二值切分點。