决策树是机器学习中的一个预测模型，它表示对象属性和对象值之间的一种映射。树中的每一个非叶子节点（决策点）表示对象属性的判断条件，其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果。
决策树
构建决策树
决策树的构建分为两个阶段：
-
训练阶段（构造决策树）
-
分类阶段（获得分类 / 决策结果）
构建决策树的基本思想是，随着树深度的增加，节点的熵迅速地降低；熵降低的速度越快越好，越快树的高度越矮。
构建决策树的基本步骤
- 将所有数据看作一个节点；
- 遍历每个特征的每一种分割方式，找到最好的分割点；
- 分割成多个节点
到
；
- 对
评价分割点的好坏
如果一个分割点可以将当前的所有节点分为两类，使得每一类都 纯度 很高，也就是同一类的数据较多，那么就是一个好分割点。
于是，我们需要量化“纯度”这个指标。
量化纯度
如果一个特征被分为 类，则每一类的比例
。这个特征节点会有
个分支。
有三种方法来度量纯度：
-
Gini 系数
-
熵（一般选择）
这里
底数可以取
或
。
熵代表_混乱程度_，混乱程度越大，熵越大（即越不纯）。
-
错误率
这三个_值越大，表示纯度越低_。
然后有纯度差的概念，也就是 信息增益 Information Gain。信息增益表示当以一个属性作为节点进行分裂后，它未分裂时的纯度与各个分支的纯度之和的差值。
其中， 代表不纯度（i.e. 上面三个公式之一），
代表分割的节点数（一般
），
表示子节点中的记录数。
即，当前节点的不纯度减去子节点不纯度的加权平均数，权重由子节点记录数与当前节点记录数的比例决定。
常用算法
ID3 算法
ID3 算法的核心思想是以_信息增益_度量属性选择，选择分裂后信息增益最大的属性进行分裂。
算法步骤
-
设 D 为父节点，则 D 的熵为
（即，数据集中 y 的各个分类的占比为 P）
-
对 D 的每个属性 A，计算 A 对 D 划分的期望信息
（即，一个属性中各个分类的熵乘以这个属性的占比）
-
信息增益即为两者差值
（这里信息增益即，以 A 属性为节点，熵值下降了多少）
ID3 算法就是在每次需要分裂时，计算每个属性的增益，然后选择增益最大的属性进行分裂。但 ID3 算法倾向于选择多属性，这种属性可能对分类没有太大作用，比如，假设一个属性有 10 种分类，每个分类中都只有一个数据，那么它的每个分类都很纯，信息增益会很大，但这个属性本身对决策没有帮助。C4.5 算法可以避免这个问题。
C4.5 算法
C4.5 算法是 ID3 算法的优化，引入_信息增益率_的概念，用它替代信息增益作为选择属性的度量依据。
算法步骤
-
定义分裂信息
-
计算属性的信息增益（这一步与 ID3 中一致）
-
增益率为
C4.5 算法选择增益率最大的属性。
CART 算法
区别于前两个算法，CART 算法基于 Gini 系数。
CART 算法计算以一个属性为节点的分支的_评价函数_（类似损失函数，越小越好）：
其中 为叶子节点中分类出的数据个数，
为熵值（这里是 Gini 系数，即
）
连续值离散化
对于连续值（比如 ），需要把它划分成离散的范围（比如
）。可以用 贪婪算法 选取分界点。
剪枝
决策树_过度拟合_是因为节点过多（即决策树太高，分支太多），所以需要裁剪枝叶。
裁剪策略
-
预剪枝：在决策树构造时进行剪枝。当一个节点包含的样本数小于阈值，则不再划分。
-
后剪枝（常用方案）：生成决策树后再剪枝
其中，
是评价函数（见 CART 算法），
决定了叶子节点个数对最终的评价函数
的影响大小。叶子节点个数越多，损失越大。
当一个分支需要被裁剪时，或者用单一叶子节点代替整个子树，叶节点的分类为子树中的主要分类；或者用一个子树替代另一个子树。
但是后剪枝有一个主要问题，就是计算效率比较低（毕竟被裁剪的树枝也都被计算了一遍）。
随机森林
随机森林有两个步骤：
- Bootstraping 有放回采样（随机样本，随机特征）
- Bagging 有放回采样
个样本共同建立分类器
即，随机森林需要构造多颗决策树，将测试样本放入这些决策树得到结果，如果是分类，则取众数；如果是回归，则取平均值。其中需要选择随机的样本和特征构造决策树（避免干扰样本每次都被使用）。