机器学习|【进阶版】机器学习之决策树知识与易错点总结（06）算法|决策树

- 欢迎订阅本专栏，持续更新中~
- - 本专栏前期文章介绍！
  - 机器学习配套资源推送
  - 进阶版机器学习文章更新~
  - 点击下方下载高清版学习知识图册
  - 决策树
  - - 决策树基本概念
    - 决策树的构造
    - ID3算法
    - C4.5算法
    - CART算法
    - 剪枝处理
    - 连续值与缺失值处理
  - 树形结构为什么不需要归一化
  - - 分类决策树和回归决策树的区别
    - 回归树
  - 代码实现参考
- 每文一语

欢迎订阅本专栏，持续更新中~ 本专栏包含大量代码项目，适用于毕业设计方向选取和实现、科研项目代码指导，每一篇文章都是通过原理讲解+代码实战进行思路构建的，如果有需要这方面的指导可以私信博主，获取相关资源及指导！
本专栏前期文章介绍！
机器学习算法知识、数据预处理、特征工程、模型评估——原理+案例+代码实战
机器学习之Python开源教程——专栏介绍及理论知识概述
机器学习框架及评估指标详解
Python监督学习之分类算法的概述
数据预处理之数据清理，数据集成，数据规约，数据变化和离散化
特征工程之One-Hot编码、label-encoding、自定义编码
卡方分箱、KS分箱、最优IV分箱、树结构分箱、自定义分箱
特征选取之单变量统计、基于模型选择、迭代选择
机器学习八大经典分类万能算法——代码+案例项目开源、可直接应用于毕设+科研项目
机器学习分类算法之朴素贝叶斯
【万字详解·附代码】机器学习分类算法之K近邻（KNN）
《全网最强》详解机器学习分类算法之决策树（附可视化和代码）
机器学习分类算法之支持向量机
机器学习分类算法之Logistic 回归（逻辑回归）
机器学习分类算法之随机森林（集成学习算法）
机器学习分类算法之XGBoost（集成学习算法）
机器学习分类算法之LightGBM（梯度提升框架）
机器学习自然语言、推荐算法等领域知识——代码案例开源、可直接应用于毕设+科研项目
【原理+代码】Python实现Topsis分析法（优劣解距离法）
机器学习推荐算法之关联规则（Apriori）——支持度；置信度；提升度
机器学习推荐算法之关联规则Apriori与FP-Growth算法详解
机器学习推荐算法之协同过滤（基于用户）【案例+代码】
机器学习推荐算法之协同过滤（基于物品）【案例+代码】
预测模型构建利器——基于logistic的列线图（R语言）
基于surprise模块快速搭建旅游产品推荐系统（代码+原理）
机器学习自然语言处理之英文NLTK（代码+原理）
机器学习之自然语言处理——中文分词jieba库详解（代码+原理）
机器学习之自然语言处理——基于TfidfVectorizer和CountVectorizer及word2vec构建词向量矩阵（代码+原理）
机器学习配套资源推送
专栏配套资源推荐——部分展示（有需要可去对应文章或者评论区查看，可做毕设、科研参考资料）
自然语言处理之文本分类及文本情感分析资源大全（含代码及其数据，可用于毕设参考！）
基于Word2Vec构建多种主题分类模型（贝叶斯、KNN、随机森林、决策树、支持向量机、SGD、逻辑回归、XGBoost…）
基于Word2Vec向量化的新闻分本分类.ipynb
智能词云算法（一键化展示不同类型的词云图）运行生成HTML文件
协同过滤推荐系统资源（基于用户-物品-Surprise）等案例操作代码及讲解
Python机器学习关联规则资源（apriori算法、fpgrowth算法）原理讲解
机器学习-推荐系统（基于用户）.ipynb
机器学习-推荐系统（基于物品）.ipynb
旅游消费数据集——包含用户id，用户评分、产品类别、产品名称等指标，可以作为推荐系统的数据集案例
进阶版机器学习文章更新~
【进阶版】机器学习之基本术语及模评估与选择概念总结（01）
【进阶版】机器学习之模型性能度量及比较检验和偏差与方差总结（02）
【进阶版】机器学习之特征工程介绍及优化方法引入（03）
【进阶版】机器学习之特征降维、超参数调优及检验方法（04）
【进阶版】机器学习之线性模型介绍及过拟合欠拟合解决方法岭回归、loss回归、elasticnet回归（05）
前期我们对机器学习的基础知识，从基础的概念到实用的代码实战演练，并且系统的了解了机器学习在分类算法上面的应用，同时也对机器学习的准备知识有了一个相当大的了解度，而且还拓展了一系列知识，如推荐算法、文本处理、图像处理。以及交叉学科的应用，那么前期你如果认真的了解了这些知识，并加以利用和实现，相信你已经对机器学习有了一个“量”的认识，接下来的，我将带你继续学习机器学习学习，并且全方位，系统性的了解和深入机器学习领域，达到一个“质”的变化。
点击下方下载高清版学习知识图册
机器学习Python算法知识点大全，包含sklearn中的机器学习模型和Python预处理的pandas和numpy知识点

文章图片

决策树
如果你还没有看之前的文章，建议看一下，之前的写的比较的详细，总的来说是比较的系统的包含代码和案例项目！
《全网最强》详解机器学习分类算法之决策树（附可视化和代码）
接下来我们回顾一下，简单的回顾之前的知识点
决策树基本概念顾名思义，决策树是基于树结构来进行决策的，在网上看到一个例子十分有趣，放在这里正好合适。现想象一位捉急的母亲想要给自己的女娃介绍一个男朋友，于是有了下面的对话：

女儿：多大年纪了？母亲：26。女儿：长的帅不帅？母亲：挺帅的。女儿：收入高不？母亲：不算很高，中等情况。女儿：是公务员不？母亲：是，在税务局上班呢。女儿：那好，我去见见。

这个女孩的挑剔过程就是一个典型的决策树，即相当于通过年龄、长相、收入和是否公务员将男童鞋分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么使用下图就能很好地表示女孩的决策逻辑（即一颗决策树）。

文章图片

在上图的决策树中，决策过程的每一次判定都是对某一属性的“测试”，决策最终结论则对应最终的判定结果。一般一颗决策树包含：一个根节点、若干个内部节点和若干个叶子节点，易知：

* 每个非叶节点表示一个特征属性测试。 * 每个分支代表这个特征属性在某个值域上的输出。 * 每个叶子节点存放一个类别。 * 每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集。

决策树的构造决策树的构造是一个递归的过程，有三种情形会导致递归返回：
(1) 当前结点包含的样本全属于同一类别，这时直接将该节点标记为叶节点，并设为相应的类别；
(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，这时将该节点标记为叶节点，并将其类别设为该节点所含样本最多的类别；
(3) 当前结点包含的样本集合为空，不能划分，这时也将该节点标记为叶节点，并将其类别设为父节点中所含样本最多的类别。算法的基本流程如下图所示：

文章图片

可以看出：决策树学习的关键在于如何选择划分属性，不同的划分属性得出不同的分支结构，从而影响整颗决策树的性能。属性划分的目标是让各个划分出来的子节点尽可能地“纯”，即属于同一类别。因此下面便是介绍量化纯度的具体方法，决策树最常用的算法有三种：ID3，C4.5和CART。
ID3算法 ID3算法使用信息增益为准则来选择划分属性，“信息熵”(information entropy)是度量样本结合纯度的常用指标，假定当前样本集合D中第k类样本所占比例为pk，则样本集合D的信息熵定义为：

文章图片

假定通过属性划分样本集D，产生了V个分支节点，v表示其中第v个分支节点，易知：分支节点包含的样本数越多，表示该分支节点的影响力越大。故可以计算出划分后相比原始数据集D获得的“信息增益”（information gain）。

文章图片

信息增益越大，表示使用该属性划分样本集D的效果越好，因此ID3算法在递归过程中，每次选择最大信息增益的属性作为当前的划分属性。
C4.5算法 ID3算法存在一个问题，就是偏向于取值数目较多的属性，例如：如果存在一个唯一标识，这样样本集D将会被划分为|D|个分支，每个分支只有一个样本，这样划分后的信息熵为零，十分纯净，但是对分类毫无用处。
因此C4.5算法使用了==“增益率”（gain ratio）来选择划分属性==，来避免这个问题带来的困扰。首先使用ID3算法计算出信息增益高于平均水平的候选属性，接着C4.5计算这些候选属性的增益率，增益率定义为：

文章图片

CART算法 CART决策树使用“基尼指数”（Gini index）来选择划分属性，基尼指数反映的是从样本集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小越好，基尼指数定义如下：

文章图片

【机器学习|【进阶版】机器学习之决策树知识与易错点总结（06）】进而，使用属性α划分后的基尼指数为：

文章图片

剪枝处理从决策树的构造流程中我们可以直观地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合（overfitting），即太依赖于训练样本。剪枝（pruning）则是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：

* 预剪枝（prepruning）：在构造的过程中先评估，再考虑是否分支。 * 后剪枝（post-pruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。

评估指的是性能度量，即决策树的泛化性能。之前提到：可以使用测试集作为学习器泛化性能的近似，因此可以将数据集划分为训练集和测试集。
预剪枝表示在构造数的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。
后剪枝则表示在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。

文章图片

文章图片

类似于这种可视化
Python也可以直接实现，去之前的文章看看！
上图分别表示不剪枝处理的决策树、预剪枝决策树和后剪枝决策树。预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。
而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。
连续值与缺失值处理对于连续值的属性，若每个取值作为一个分支则显得不可行，因此需要进行离散化处理，常用的方法为二分法，基本思想为：给定样本集D与连续属性α，二分法试图找到一个划分点t将样本集D在属性α上分为≤t与＞t。

* 首先将α的所有取值按升序排列，所有相邻属性的均值作为候选划分点（n-1个，n为α所有的取值数目）。 * 计算每一个划分点划分集合D（即划分为两个分支）后的信息增益。 * 选择最大信息增益的划分点作为最优划分点。

文章图片

现实中常会遇到不完整的样本，即某些属性值缺失。有时若简单采取剔除，则会造成大量的信息浪费，因此在属性值缺失的情况下需要解决两个问题：（1）如何选择划分属性。（2）给定划分属性，若某样本在该属性上缺失值，如何划分到具体的分支上。假定为样本集中的每一个样本都赋予一个权重，根节点中的权重初始化为1，则定义：

文章图片

对于（1）：通过在样本集D中选取在属性α上没有缺失值的样本子集，计算在该样本子集上的信息增益，最终的信息增益等于该样本子集划分后信息增益乘以样本子集占样本集的比重。即：

文章图片

对于（2）：若该样本子集在属性α上的值缺失，则将该样本以不同的权重（即每个分支所含样本比例）划入到所有分支节点中。该样本在分支节点中的权重变为：

文章图片

树形结构为什么不需要归一化
因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。
按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。
既然树形结构（如决策树、RF）不需要归一化，那为何非树形结构比如Adaboost、SVM、LR、Knn、KMeans之类则需要归一化。
对于线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。但是如果进行了归一化，那么等高线就是圆形的，促使SGD往原点迭代，从而导致需要的迭代次数较少。
分类决策树和回归决策树的区别 Classification And Regression Tree(CART)是决策树的一种，CART算法既可以用于创建分类树（Classification Tree），也可以用于创建回归树（Regression Tree），两者在建树的过程稍有差异。
回归树机器学习经典算法详解及Python实现–CART分类决策树、回归树和模型树
CART回归树是假设树为二叉树，通过不断将特征进行分裂。比如当前树结点是基于第j个特征值进行分裂的，设该特征值小于s的样本划分为左子树，大于s的样本划分为右子树。
CART回归树实质上就是在该特征维度对样本空间进行划分，在决策树模型中是使用启发式方法解决。典型CART回归树产生的目标函数为：