ID3算法
使用信息增益选择特征，递归构建决策树。
ID3相当于用极大似然法进行概率模型的选择（最大熵模型）。
输入：训练数据集D，特征集A，阈值
输出：决策树T
（1）若D中所有实例属于同一类，则T为单结点树，
作为该结点的类标记，返回T。
（2）若A=，则T为单结点树，并将D中实例数最大的类
作为该结点的类标记，返回T。
（3）计算A中各特征对D的信息增益，选择信息增益最大的特征。
（4）如果的信息增益小于阈值
，则置T为单结点树，并将D中实例数最大的类
作为该结点的类标记，返回T。
（5）对的每一可能值
，依
将D分割为若干非空子集
，构建子结点，由结点D和子结点
构成树T，返回T。
（6）对第i个子结点，以为训练集，以
为特征集，递归调用(1)~(5)
(1)(2)(4)得到单结点树，作为递归终止条件
(5)生成多叉树，有多少可能值就有多少分支
(6)每个子树进行递归，从剩余所有特征中选择
C4.5算法：使用信息增益比选择特征。
决策树的剪枝
剪枝(pruning)，从已生成的树上裁掉一些子树或叶结点，并将其父结点作为新的叶结点。
决策树剪枝，类似线性回归中的正则化，包括预剪枝和后剪枝。
预剪枝是在决策树生成过程中，提前结束结点的分裂，一般包括:
• 树到达一定深度
• 结点下包含的样本点小于一定数目
• 信息增益小于一定的阈值
• 结点下所有样本都属于同一个类别
• 性能在划分后没有提高或提高不多
后剪枝通过极小化决策树整体的损失函数实现。
设树T的叶结点个数为，t是树T的叶结点，该叶结点有
个样本点，
为叶结点t上的经验熵，
为参数，则决策树的损失函数可以定义为
C(T)表示模型与训练数据的拟合程度，|T|表示模型复杂度，控制两者之间的影响。
损失函数的极小化等价于正则化的极大似然估计。
决策树生成学习局部模型，决策树剪枝学习整体模型。
剪枝算法
输入：生成算法产生的整个树T，参数
输出：修剪后的子树
（1）计算每个结点的经验熵。
（2）递归的从叶结点向上回缩。计算回缩前后，整体树的损失函数值。如果损失函数值减少，则进行剪枝。
（3）返回（2）直到不能继续为止，得到损失函数最小的子树
只考虑两个树的损失函数的差，其计算可以在局部进行，所以剪枝算法可以使用动态规划实现。
CART算法
分类与回归树(classification and regression tree)，生成二叉树。
回归树使用平方误差最小，分类树使用基尼指数最小，进行特征选择。
1.回归树的生成
X和Y是输入和输出变量，并且Y是连续变量，给定训练数据集
假设已将输入空间划分为M个单元，并且每个单元
上有一个固定的输出值
，于是回归树模型可以表示为
单元上的
的最优值是
上的所有输入实例
对应的输出
的均值，即
用平方误差最小的准则求解每个单元上的最优输出值。
采用启发式方法，对输入空间进行划分。选择第j个变量和它取的值s，作为切分变量和切分点，并定义两个区域：
和
寻找最优切分变量j和最优切分点s，求解
其中和
找到最优对(j,s)，依此将输入空间划分为两个区域。
连续变量通过减少方差，来减少不确定性。
重复上述划分过程，直到满足停止条件，称为最小二乘回归树。
2.分类树的生成
分类树使用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
分类问题中，假设有K个类，样本点属于第k类的概率为，则概率分布的基尼指数定义
Gini(D) 反映从数据集 D 中随机抽取两个样本，其类别不一致的概率。使用基尼指数代替熵，计算更加简单。
对于二分类问题，若样本点属于第1类的概率p，则概率分布的基尼指数为
对于给定的样本集合D，其基尼指数为
是D中属于第k类的样本子集，K是类的个数。
样本集合D根据特征A是否取某一可能值a被分割为和
两部分，即
则在特征A的条件下，集合D的基尼指数定义
Gini(D)表示集合D的不确定性，Gini(D,A)表示经过A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性也越大。
参考：《统计学习方法》
