決策樹的幾個常用算法：ID3, C4.5和CART算法

原理：

要對數據進行分類，涉及到通過選取什麼樣的特徵對數據進行分類，比如將柚子和西瓜進行分類，可以選取（大小、顏色、甜度等特徵）

決策樹的功能就是判斷使用哪個特徵，然後選取他認為最好的特徵對數據進行分類。

那麼他是如何選取最好的特徵呢？

對於ID3（選取信息增益最大的特徵），C4.5（選擇信息增益率最大的特徵），CART（選擇基尼值最小的特徵）

1）ID3信息增益計算：

baseEnt = -Σ p_i * log₂ (p_i)

InfoGain =  baseEnt - Σ p_j * ent(j)  # 信息增益：j 表示以此數據特徵來分類後的其他特徵（需剔除j數據）

2）C4.5信息增益率計算：

信息增益率=信息增益 / Σ p_j*log₂(p_j)

3）gini係數的計算

gini = -Σ p_j²

通常不會一次就能把數據進行分類（比如橘子和檸檬），可能需要不斷地計算當前數據的信息熵（增益率、基尼值）選取最好的特徵然後分類迭代下去，直到達到設置的條件（比如一定的樹深度）。

優點：

1、計算複雜度不高

2、結果易於理解

3、對中間值缺失不敏感

缺點：

可能會產生過度匹配問題