决策树ID3,C4.5,CART

简述： 决策树是一种自上而下，对样本数据进行树形分类的过程，由节点和有向边组成。节点分为内部节点和叶子节点，其中每个内部节点表示一个特征或属性，叶子节点表示类别。决策树常用于分类问题于回归问题，完全生长的决策树模型具有简单直观、解释性强的特点。

常用的决策树算法

通常，我们希望决策树能够低复杂度的拟合训练数据，达到良好的分类效果，但是从若干个决策树中选取最优的决策树是一个NP完全问题。常用的决策树算法有ID3，C4.5，CART。

ID3-最大信息增益
设样本集合为D，类别数为K，数据集D的经验熵表示为：
$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$
其中$C_k$是样本集合D中属于$k$类的样本子集，$|C_k|$表示该子集的元素个数，$|D|$表示样本集合元素个数。
再计算某个特征A对于数据集D的经验条件熵$H(D|A)$为：
$H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{\left|D \right|}\left(-\sum_{k=1}^{k} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right)$
其中，$D_i$表示数据集D中特征A取第$i$个特征的样本子集，$D_{ik}$表示$D_i$中属于第$k$个类别的样本子集。于是信息增益$g(D,A)$可以表示为二者之差，为：
$g(D,A)=H(D)-H(D|A)$

C4.5-最大信息增益比
特征A对于数据集D的信息增益比定义为：$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$
其中$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}$称为数据集D关于A的取值熵。

CART-最大基尼指数（Gini）
Gini描述的是数据的纯度，与信息熵含义类似。
$\operatorname{Gini}(D)=1-\sum_{k=1}^{n}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$
CART在每一次迭代中选择的基尼指数最小的特征及其对应的切分点进行分类。但与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切割成两份，分别进入左右子树。特征A的基尼指数定义为：
$\operatorname{Gini}(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \operatorname{Gini}\left(D_{i}\right)$

ID3，C4.5，CART差异

从样本类型的角度：
ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把把连续属性转换为布尔型，从而将连续型变量转换成多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以可以很好的适用于连续型变量。
从应用角度：
ID3和C4.5只能用于分类任务，而CART(Classification and Regression Tree,分类回归树)既可以用于分类，也可以用于回归任务（回归树使用最小平方误差准则）。
从细节、优化过程角度：
ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个节点上产生多叉分支，且每个特征在层级之间不会复用，而CART每个节点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性于泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。