机器学习算法——决策树5（CART）

三种算法比较

ID3：采用信息增益作为选择特征的标准，越大越好
C4.5：采用信息增益率作为选择特征的标准，越大越好
CART：

回归：平方误差函数，越小越好
分类：基尼系数，越小越好

CART算法

CART算法由特征选择、树的生成及剪枝组成，可以用于回归也可以用于分类。CART假设决策树是二叉树，内部节点特征的取值为"是"和"否"，左边取值为"是"的分支，右边为"否"的分支，进行递归地二分每个特征，算法分为两步：

决策树生成：基于训练数据集生成决策树，生成的决策树尽量大；
决策树剪枝：用验证数据集对已生成的树进行剪枝，并且选择最优树，用最小化损失函数作为剪枝的标准

决策树的生成就是递归地创建二叉树的过程。最小化准则：

回归：平方误差最小化
分类：基尼系数最小化

回归树

假设输入和输出变量分别是X和Y，并且Y是连续变量，在数据集 $D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 上，如果将输入空间划分为M个单元 $R_1,R_2,...,R_M$ ，每个单元对应的输出值为 $c_m$ ，回归树模型为： $f(x)=\sum_{m=1}^{M}c_mI(x\in{R_m})$ 平方误差为 $\sum_{x_i\in R_m}(y_i-f(x_i))^2$ 用来表示回归树对于训练数据的预测误差

分类树

分类数用基尼系数选择最优特征，同时决定该特征的最优二值分切分点。分类问题中，假设有K个类，样本点属于第k类的概率为 $p_k$ ，概率分布的基尼质数定义为：
$\begin{align} Gini(p) & =\sum_{k=1}^{K}p_k(1-p_k) \\ & =\sum_{k=1}^{K}p_k - \sum_{k=1}^{K}p_k^2 \\ & = 1- \sum_{k=1}^{K}p_k^2 \end{align}$
对于二分类问题，若属于第一个类的概率为p，概率分布的基尼系数为： $Gini(D)=p(1-p)+(1-p)(1-(1-p))=2p(1-p)$ 对给定的样本集合D，基尼系数为 $Gini(D)=1-\sum_{k=1}^{K}(\frac {|C_k|} {|D|})^2$ 其中K是类的个数， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集。