决策树

决策树的直观理解就是将数据按照树的形状映射在空间的子空间。其基本样子长下面这样：

由上图可知（该图来自于机器学习实战），决策树的生成通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。也就是挑选那个特征作为根节点、如何生成子节点、对于生成的树进行剪枝以避免过拟合。

对于分类树（输出为离散值）的特征选择分为三种选择标准：信息增益，信息增益比，基尼指数，根据公式计算出最优的根节点，再依次计算。

ID3：使用信息增益选择最优特征。

C4.5：使用信息增益比选择最优特征。

CART分类树;使用基尼指数选择最优特征。三种算法的减枝的标准为损失函数最小化也就是正则化极大似然估计。

对于回归树（输出为连续值），此时算法为CART回归树，CART算法包括分类树与回归树。此时由于输出为连续值而非离散值，不能选用前面的三种算法，所以此时特征选择的算法为：平方误差最小化准则。

此时回归树为二叉树，也就是只有两个分支，其基本的思想为：对于任意一对特征j和特征切分点s，将空间中的数据切分为两部分b1和b2，每一部分的平均值为a1和a2，计算b1部分的每一个样本到a1的距离平方和b2部分的每一个样本到a2的距离平方，若两则之和最小，则为最优的特征和最优的切分点，然后继续。

CART回归树是GBDT算法的基本，想要对GBDT算法有更好的了解，则必须了解CART回归树。

该内容主要来自于李航，统计学习方法。