本教程的知识点为：机器学习算法定位、 K-近邻算法 1.4 k值的选择 1 K值选择说明 1.6 案例：鸢尾花种类预测--数据集介绍 1 案例：鸢尾花种类预测 1.8 案例：鸢尾花种类预测—流程实现 1 再识K-近邻算法API 1.11 案例2：预测facebook签到位置 1 项目描述 线性回归 2.3 数学:求导 1 常见函数的导数 线性回归 2.5 梯度下降方法介绍 1 详解梯度下降算法 线性回归 2.6 线性回归api再介绍 小结 线性回归 2.9 正则化线性模型 1 Ridge Regression (岭回归，又名 Tikhonov regularization) 逻辑回归 3.3 案例：癌症分类预测-良／恶性乳腺癌肿瘤预测 1 背景介绍 决策树算法 4.2 决策树分类原理 1 熵 决策树算法 4.3 cart剪枝 1 为什么要剪枝 决策树算法 4.4 特征工程-特征提取 1 特征提取 决策树算法 4.5 决策树算法api 4.6 案例：泰坦尼克号乘客生存预测 集成学习基础 5.1 集成学习算法简介 1 什么是集成学习 2 复习：机器学习的两个核心任务 集成学习基础 5.3 otto案例介绍 -- Otto Group Product Classification Challenge 1.背景介绍 2.数据集介绍 3.评分标准 集成学习基础 5.5 GBDT介绍 1 Decision Tree：CART回归树 1.1 回归树生成算法（复习） 聚类算法 6.1 聚类算法简介 1 认识聚类算法 聚类算法 6.5 算法优化 1 Canopy算法配合初始聚类 聚类算法 6.7 案例：探究用户对物品类别的喜好细分 1 需求 第一章知识补充：再议数据分割 1 留出法 2 交叉验证法 KFold和StratifiedKFold 3 自助法 正规方程的另一种推导方式 1.损失表示方式 2.另一种推导方式 梯度下降法算法比较和进一步优化 1 算法比较 2 梯度下降优化算法 第二章知识补充： 多项式回归 1 多项式回归的一般形式 维灾难 1 什么是维灾难 2 维数灾难与过拟合 第三章补充内容：分类中解决类别不平衡问题 1 类别不平衡数据集基本介绍 向量与矩阵的范数 1.向量的范数 2.矩阵的范数 如何理解无偏估计？无偏估计有什么用？ 1.如何理解无偏估计

完整笔记资料代码：https://gitee.com/yinuo112/AI/tree/master/机器学习/嘿马机器学习（算法篇）/note.md

感兴趣的小伙伴可以自取哦~

全套教程部分目录：

部分文件图片：

决策树算法

学习目标

• 掌握决策树实现过程
• 知道信息熵的公式以及作用
• 知道信息增益、信息增益率和基尼指数的作用
• 知道id3,c4.5，cart算法的区别
• 了解cart剪枝的作用
• 知道特征提取的作用
• 应用DecisionTreeClassifier实现决策树分类

4.3 cart剪枝

学习目标

• 了解为什么要进行cart剪枝
• 知道常用的cart剪枝方法

1 为什么要剪枝

图片无法加载

• 图形描述

• 横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。

• 实线显示的是决策树在训练集上的精度，虚线显示的则是在一个独立的测试集上测量出来的精度。

• 随着树的增长，在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。

• 出现这种情况的原因：

• 原因1：噪声、样本冲突，即错误的样本数据。

• 原因2：特征即属性不能完全作为分类标准。
• 原因3：巧合的规律性，数据量不够大。

剪枝 (pruning)是决策树学习算法对付"过拟合"的主要手段。

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

如何判断决策树泛化性能是否提升呢？

• 可使用前面介绍的留出法，即预留一部分数据用作"验证集"以进行性 能评估。例如对下表的西瓜数据集，我们将其随机划分为两部分，其中编号为 {1，2，3，6， 7， 10， 14， 15， 16， 17} 的样例组成训练集，编号为 {4， 5， 8， 9， 11， 12， 13} 的样例组成验证集。

图片无法加载

假定咱们采用信息增益准则来划分属性选择，则上表中训练集将会生成一棵下面决策树。

为便于讨论，我们对圈中的部分结点做了编号。

图片无法加载

接下来，我们一起看一下，如何对这一棵树进行剪枝。

2 常用的减枝方法

决策树剪枝的基本策略有"预剪枝" (pre-pruning)和"后剪枝"(post- pruning) 。

• 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;
• 后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

2.1 预剪枝

首先，基于信息增益准则，我们会选取属性"脐部"来对训练集进行划分，并产生 3 个分支，如下图所示。然而，是否应该进行这个划分呢？预剪枝要对划分前后的泛化性能进行估计。

图片无法加载

在划分之前，所有样例集中在根结点。

• 若不进行划分，该结点将被标记为叶结点，其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为"好瓜"。
• 用前面表的验证集对这个单结点决策树进行评估。则编号为 {4，5，8} 的样例被分类正确。另外 4个样例分类错误，于是验证集精度为$\frac{3}{7}*100\% = 42.9\%$。

在用属性"脐部"划分之后，上图中的结点2、3、4分别包含编号为 {1，2，3， 14}、 {6，7， 15， 17}、 {10， 16} 的训练样例，因此这 3 个结点分别被标记为叶结点"好瓜"、 "好瓜"、 "坏瓜"。

图片无法加载

此时，验证集中编号为 {4， 5， 8，11， 12} 的样例被分类正确，验证集精度为$\frac{5}{7}*100\% = 71.4\% > 42.9\%$.

于是，用"脐部"进行划分得以确定。

然后，决策树算法应该对结点2进行划分，基于信息增益准则将挑选出划分属性"色泽"。然而，在使用"色泽"划分后，编号为 {5} 的验证集样本分类结果会由正确转为错误，使得验证集精度下降为 57.1%。于是，预剪枝策略将禁 止结点2被划分。

对结点3，最优划分属性为"根蒂"，划分后验证集精度仍为 71.4%. 这个 划分不能提升验证集精度，于是，预剪枝策略禁止结点3被划分。

对结点4，其所含训练样例己属于同一类，不再进行划分.

于是，基于预剪枝策略从上表数据所生成的决策树如上图所示，其验证集精度为 71.4%. 这是一棵仅有一层划分的决策树，亦称"决策树桩" (decision stump).

2.2后剪枝：

后剪枝先从训练集生成一棵完整决策树，继续使用上面的案例，从前面计算，我们知前面构造的决策树的验证集精度为42.9%。

图片无法加载

后剪枝首先考察结点6，若将其领衔的分支剪除则相当于把6替换为叶结点。替换后的叶结点包含编号为 {7， 15} 的训练样本，于是该叶结点的类别标记为"好瓜"，此时决策树的验证集精度提高至 57.1%。于是，后剪枝策略决定剪枝，如下图所示。

图片无法加载

然后考察结点5，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为 {6，7，15}的训练样例，叶结点类别标记为"好瓜'；此时决策树验证集精度仍为 57.1%. 于是，可以不进行剪枝.

对结点2，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号 为 {1， 2， 3， 14} 的训练样例，叶结点标记为"好瓜"此时决策树的验证集精度提高至 71.4%. 于是，后剪枝策略决定剪枝.

对结点3和1，若将其领衔的子树替换为叶结点，则所得决策树的验证集 精度分别为 71.4% 与 42.9%，均未得到提高，于是它们被保留。

最终，基于后剪枝策略所生成的决策树就如上图所示，其验证集精度为 71.4%。

对比两种剪枝方法，

• 后剪枝决策树通常比预剪枝决策树保留了更多的分支。
• 一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
• 但后剪枝过程是在生成完全决策树之后进行的。 并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多.

3 小结

• 剪枝原因【了解】

• 噪声、样本冲突，即错误的样本数据

• 特征即属性不能完全作为分类标准

• 巧合的规律性，数据量不够大。

• 常用剪枝方法【知道】

• 预剪枝

  • 在构建树的过程中，同时剪枝

    • 限制节点最小样本数
    • 指定数据高度
    • 指定熵值的最小值

• 后剪枝

  • 把一棵树，构建完成之后，再进行从下往上的剪枝