文章目录
- 决策树
- 决策树一句话概括
- 什么是决策树？
- 信息熵 H(X)
- 条件熵H(Y|X)
- 例：求信息熵，条件熵
- 决策树构建过程
- 如何选择划分方式呢？
- （决策树分割属性选择）如何选择最优的特征呢？
- 纯度的判断标准
- 信息增益-纯度变化了多少
- 停止条件
- 决策树的评估
- 举例
- 1. 对数据特征进行分割
- 2. 通过信息增益找到分割特征
- 求Gain(D,婚姻)
- 求Gain(D,房产)
- 建立决策树的主要算法
- 1. ID3
- ID3优缺点
- 2. C4.5
- C4.5优缺点
- 3. CART
- ID3、C4.5、CART分类树算法总结
- 分类树和回归树的区别
- 决策树优化策略
- 剪枝优化
- 随机森林
- 决策树的剪枝
- 剪枝举例
- 前剪枝
- 后剪枝
- 使用决策树实现特征选择
- 决策树学习通常包含以下三个步骤：
- 决策树种类
- 决策树算法(贪心算法)
- 决策树学习过程
- 决策树优缺点
- 决策树面试题
- 什么是决策树？
- 和其他模型比，它的优点？
- 为什么需要剪枝：
- 决策树剪枝：
- 决策树能否有非数值型变量？
- 讲解决策树的建树过程
- 决策树如何防止过拟合？前剪枝和后剪枝过程是怎样的？剪枝条件都是什么
- 树形结构为什么不需要归一化?
- 既然树形结构（如决策树、RF）不需要归一化，那为何非树形结构比如Adaboost、SVM、LR、Knn、KMeans之类则需要归一化。
- 归一化的拓展
- 参考：
决策树
决策树一句话概括
通过信息增益，采用递归的方式生成树（找出最合适的节点顺序以及叶子对应的类标签）
什么是决策树？
决策树是一种分类与回归方法，主要用于分类，决策树模型呈现树形结构，是基于输入特征对实例进行分类的模型。决策树其实是定义在特征空间与类空间上的条件概率分布！
信息熵 H(X)
一个系统越是有序，信息熵就越低，一个系统越是混乱，信息熵就越高，所以信息熵被认为是一个系统有序程度的度量。比如一个数据集中的样本都属于同一类，那么这时信息熵=0
信息熵就是用来描述系统信息量的不确定度。
高信息熵：表示随机变量X是均匀分布的，各种取值情况是等概率出现的。
低信息熵：表示随机变量X各种取值不是等概率出现。可能出现有的事件概率很大，有的事件概率很小。
条件熵H(Y|X)
给定条件X的情况下，随机变量Y的信息熵就叫做条件熵
事件(X,Y)发生所包含的熵，减去事件X单独发生的熵，即为在事件X发生的前提下，Y发生“新”带来的熵，这个也就是条件熵本身的概念。
例：求信息熵，条件熵
- 求X的信息熵
- 当专业(X)为数学的时候，Y的信息熵的值为:H(Y|X=数学)
3. 当专业(X)为英语的时候，Y的信息熵的值为:H(Y|X=数学)
4. 当专业(X)为IT的时候，Y的信息熵的值为:H(Y|X=数学)
所以
- 求条件熵
给定条件X的情况下，所有不同x值情况下Y的信息熵的平均值叫做条件熵
决策树构建过程
决策树构建目标就是让各个分裂子集尽可能的’纯’，也就是让一个分裂子数据集中待分类的项尽可能的属于同一个类别。
- 将所有的特征看成一个一个的节点；
- 遍历当前特征的每一种分割方式，找到最好的分割点；将数据划分为不同的子节点；计算划分之后所有子节点的**'纯度’信息**；
- 使用第二步遍历所有特征，选择出最优的特征以及该特征的最优的划分方式；得出最终的子节点: N1、N2…Nm,
- 对子节点N1、N2…Nm分别继续执行2-3步，直到每个最终的子节点都足够**‘纯’**。
如何选择划分方式呢？
在上文提到了两个关键性的事情，叫做 最优的划分方式 和 选择最优特征，这里我们就要讨论的是划分方式。众所周知，数据分为离散的和连续的，显然我们对他们的处理有些不同。
- 属性是离散值，而且不要求生成的是二叉决策树，此时一个属性就是一个分支
- 属性是离散值，而且要求生成的是二叉决策树，此时使用属性划分的子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支
- 属性是连续值，可以确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支
（决策树分割属性选择）如何选择最优的特征呢？
之前我们说了划分方式，那么我们如何选择最优的特征呢。答案是比较纯度。
决策树算法是一种“贪心”算法策略，只考虑在当前数据特征情况下的最好分割方式，不能进行回溯操作。
在某种意义上的局部最优解，也就是说我只保证在当前分裂的时候，能够使数据最纯就好。
而对于整体的数据集而言，通过查看每个特征属性划分后的纯度变化进行比较，选择能让数据集变得更纯的特征属性进行分割。之后重复上述步骤直到满足条件。
纯度的判断标准
基尼系数:
信息熵:
误差率:
信息增益-纯度变化了多少
在剪枝和判断的时候需要一个种体现变化的系数，于是出现了如下公式来作为C4.5和ID3的判别标准
这个公式表达了以A属性划分后，信息量增加的量，或者说指代的是纯度变纯了多少。
信息熵-条件熵
D目标属性，A为某一个待划分的特征属性；Gain为A为特征对训练数据集D的信息增益
停止条件
决策树构建的过程是不断递归的过程，就像 (是) while 循环一样，必须有跳出循环的条件。以下是两个停止条件。
- 每个子节点只有一种类型时停止条件。（容易过拟合）
- 节点中样本数小于某个阈值的时候，或者迭代次数达到给定值的时候，停止构建。
决策树的评估
决策树的损失函数(该值越小，算法效果越好)
举例
1. 对数据特征进行分割
- 拥有房产（是、否）
- 婚姻状态（单身、已婚、离婚）
- 年收入（80、97.5）
只保留80和97.5
因为 如果选择67.5,它将60和75分开了，但是60和75的Y都是否，标签相同，最好还是分到一个类中
2. 通过信息增益找到分割特征
首先，计算按照拥有房产这个特征进行划分的信息增益，使用信息熵进行纯度的计算：
计算原始数据的信息熵：
计算按拥有房产划分后的结果集的条件熵H(D|A)：
- 当特征A=有房产的时候，标签D的信息熵的值为:H(D|A=有房产)
- 当特征A=无房产的时候，标签D的信息熵的值为:H(D|A=无房产)
- 得到按拥有房产划分后的结果集的条件熵H(D|A)：
计算信息增益度Gain(房产)：
同理可以计算Gain(D,婚姻)=0.205
Gain(D,年收入=97.5)=0.395
Gain(D,年收入=80)=0.116
按照Gain越大，分割后的纯度越高，因此第一个分割的特征属性为年收入，并按照97.5进行划分。
左子树的结果集够纯，因此不需要继续划分。
接下来，对右子树年收入<97.5的数据，继续选择特征进行划分，且不再考虑收入这个特征，注意需要重新计算Gain(D,婚姻)，Gain(D,房产)，方法如上下
求Gain(D,婚姻)
H(D|A=已婚)=0
H(D|A=单身)=0
Gain(D,婚姻)= 0.97-0.4=0.57
求Gain(D,房产)
H(D|A=有房产)=0
Gain(D,房产) = 0.97-0.776=0.194
选取婚姻作为分割属性
当构建好一个判断模型后，新来一个用户后，可以根据构建好的模型直接进行判断，比如新用户特性为：无房产、单身、年收入55K，那么根据判断得出该用户无法进行债务偿还。这种决策对于借贷业务有比较好的指导意义。
建立决策树的主要算法
1. ID3
ID3算法是决策树的一个经典的构造算法，内部使用信息熵以及信息增益来进行构建；每次迭代选择信息增益最大的特征属性作为分割属性
- ID3算法只支持离散的特征属性，不支持连续的特征属性
- ID3算法构建的是多叉树
ID3优缺点
优点：决策树构建速度快；实现简单
缺点：
- 计算依赖于特征数目较多的特征，而属性值最多的属性并不一定最优 。
- ID3算法不是递增算法，ID3算法是单变量决策树，对于特征属性之间的关系不会考虑。
- 抗噪性差。
- 只适合小规模数据集，需要将数据放到内存中。
2. C4.5
在ID3算法的基础上，进行算法优化提出的一种算法(C4.5)；
现在C4.5已经是特别经典的一种决策树构造算法；
使用信息增益率来取代ID3算法中的信息增益，在树的构造过程中会进行剪枝操作进行优化；
能够自动完成对连续属性的离散化处理；
C4.5构建的是多分支的决策树；
C4.5算法在选中分割属性的时候选择信息增益率最大的属性，涉及到的公式为：
C4.5优缺点
优点：
产生的规则易于理解
准确率较高
实现简单
缺点：
对数据集需要进行多次顺序扫描和排序，所以效率较低
只适合小规模数据集，需要将数据放到内存中
3. CART
使用基尼系数(分类树)作为数据纯度的量化指标来构建的决策树算法就叫做CART(Classification And Regression Tree，分类回归树)算法。
CART算法使用GINI增益率作为分割属性选择的标准，选择GINI增益率最大的作为当前数据集的分割属性；
可用于分类和回归两类问题。
强调备注：CART构建是二叉树。
ID3、C4.5、CART分类树算法总结
- ID3、C4.5和CART算法均只适合在小规模数据集上使用
- ID3、C4.5和CART算法都是单变量决策树
- 当属性值取值比较多的时候，最好考虑C4.5算法，ID3得出的效果会比较差
- 决策树分类一般情况只适合小数据量的情况(数据可以放内存)
- CART算法是三种算法中最常用的一种决策树构建算法(sklearn中仅支持CART)。
- 三种算法的区别仅仅只是对于当前树的评价标准不同而已，ID3使用信息增益、C4.5使用信息增益率、CART使用基尼系数。（不是主要区别）
- CART算法构建的一定是二叉树，ID3和C4.5构建的不一定是二叉树。(主要区别)
算法 | 支持模型 | 树结构 | 划分特征选择 | 连续值处理 | 缺失值处理 | 剪枝 | 特征属性多次使用 |
ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 | 不支持 |
C4.5 | 分类 | 多叉树 | 信息增益率 | 支持 | 支持 | 支持 | 不支持 |
CART | 分类、回归 | 二叉树 | 基尼系数、均方差 | 支持 | 支持 | 支持 | 支持 |
分类树和回归树的区别
分类树采用信息增益、信息增益率、基尼系数来评价树的效果，都是基于概率值进行判断的；
而分类树的叶子节点的预测值一般为叶子节点中概率最大的类别作为当前叶子的预测值。
在回归树中，叶子节点的预测值一般为叶子节点中所有值的均值来作为当前叶子节点的预测值。
所以在回归树中一般采用MSE或者MAE作为树的评价指标，即均方差。
一般情况下，只会使用CART算法构建回归树
决策树优化策略
剪枝优化
决策树过渡拟合一般情况是由于节点太多导致的，剪枝优化对决策树的正确率影响是比较大的，也是最常用的一种优化方式。
随机森林
利用训练数据随机产生多个决策树，形成一个森林。然后使用这个森林对数据进行预测，选取最多结果作为预测结果。
决策树的剪枝
决策树的剪枝是决策树算法中最基本、最有用的一种优化方案，主要分为两大类：
前置剪枝：在决策树的生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。
后置剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
后剪枝总体思路(交叉验证)：
由完全树T0开始，剪枝部分节点得到T1，在此剪枝得到T2…直到仅剩树根的树Tk
在验证数据集上对这k+1个树进行评价，选择最优树Ta（损失函数最小的树）
剪枝举例
采用信息增益准则生成决策树
前剪枝
（1）若根结点“脐部”不进行划分，被标记为叶结点，其类别标记为训练样例数最多的类别，假设标记为“好瓜”。用验证集进行评估，编号{4,5,8}被正确分类，{9,11,12,13}被错误分类，精度为42.9%。用属性“脐部”划分后，{4,5,8,11,12}被正确分类，验证集精度为71.4%。因此，用“脐部”划分得以确定。
（2） 对②进行划分，基于信息增益准则挑选出”色泽“，{5}会被错分，划分后验证集精度下降，于是将禁止结点②被划分。
（3） 对③，最优划分属性为”根蒂“，划分前后精度一样，禁止划分。
（4） 对④，其所含训练样例已属于同一类，不再进行划分。
优点：降低过拟合风险，显著减少了训练和测试的时间开销
缺点：基于”贪心“，有欠拟合风险。有些分支当前划分虽然不能提升泛化性能，但在其基础上进行后续划分却有可能导致性能显著提高。
后剪枝
先从训练集生成一颗完整的决策树。图中决策树的验证集精度为42.9%。
（1）首先考虑结点⑥，剪枝后的叶结点包含编号{7,15}的训练样本，于是，该叶结点的类别标记为”好瓜“，此时验证集精度提高至57.1%。因此决定剪枝。
（2）考察结点⑤，替换后的叶结点包含{6,7,15}，标记为”好瓜“，验证集精度仍为57.1%，可以不进行剪枝。
（3）对结点②，替换后的叶结点包括{1,2,3,14}，标记为”好瓜”，此时验证集精度提高至71.4%，于是，决定剪枝。
（4）对结点③和①，替换后精度均未得到提高，于是得以保留。
后剪枝决策树通常比预剪枝决策树保留更多的分支。一般情况下，后剪枝决策树欠拟合风险很小，但其训练时间开销较大。
使用决策树实现特征选择
因为决策树在构建过程中，每次选择划分特征的目的—让数据具有更加好的区分能力，
也就是说我们每次选择的特征是具有明显区分能力的特征，
可以认为这些被选择的特征对y的取值有更大的影响，
因此决策树可以用于特征选择。
决策树学习通常包含以下三个步骤：
- 选择特征
- 决策树生成
- 剪枝
决策树的特质之一就是它们需要的数据准备工作非常少。特别是，完全不需要进行特征缩放或集中。
决策树种类
分类树–对离散变量做决策树
回归树–对连续变量做决策树
决策树算法(贪心算法)
- 有监督的学习
- 非参数学习算法
- 自顶向下递归方式构造决策树
- 在每一步选择中都采取在当前状态下最好/优的选择
决策树学习的算法通常是一个递归地选择最优特征, 并根据该特征对训练数据进行分割, 使得各个子数据集有一个最好的分类的过程.
在决策树算法中,ID3基于信息增益作为属性选择的度量, C4.5基于信息增益率作为属性选择的度量, CART基于Gini增益率作为属性选择的度量
决策树学习过程
- 特征选择: 从众多的特征中选择一个特征作为当前节点分裂的标准, 选择特征的评估标准：ID3（通过信息增益选择特征）、C4.5（通过信息增益率选择特征）、CART（通过Gini增益率**选择特征）
- 决策树生成: 根据特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止,决策树停止生长
- 决策树剪枝: 缩小树结构规模, 缓解过拟合,
决策树优缺点
优点:
- 速度快: 计算量相对较小, 且容易转化成分类规则.
- 模型具有可解释性，容易向业务部门人员描述.
- 决策树可处理数值型和非数值型数据
缺点:
- 对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征
- 容易过拟合
- 忽略属性之间的相关性
决策树面试题
什么是决策树？
决策树是一种分类和回归的基本模型，可从三个角度来理解它，即：
- 一棵树
- if-then规则的集合，该集合是决策树上的所有从根节点到叶节点的路径的集合
- 定义在特征空间与类空间上的条件概率分布
和其他模型比，它的优点？
主要的优点有两个：
- 模型具有可解释性，容易向业务部门人员描述。
- 分类速度快
为什么需要剪枝：
使用ID3 C4.5决策树算法中，会递归的生成决策树，知道不能继续下去为止，
因此会产生过拟合，构造出复杂的决策树，所以需要剪枝降低过拟合。
决策树剪枝：
将已生成的决策树进行简化的过程称为剪枝，
从已生成的树上剪掉一些子树和叶子节点，并将其父节点作为新的叶节点，从而简化模型。
决策树能否有非数值型变量？
可以
讲解决策树的建树过程
自上而下，对样本数据进行树形分类的过程。每个内部节点表示一个特征，叶节点表示一个类别。从顶部根节点开始，所有的样本聚在一起。经过根节点的划分，样本被分到不同的子节点，再根据子节点的特征进一步划分，直至所有样本被归到某一个类别（叶节点）中。
决策树如何防止过拟合？前剪枝和后剪枝过程是怎样的？剪枝条件都是什么
通过剪枝防止过拟合。
前剪枝是指在决策树生成的过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分，并将当前节点标记为叶子节点；此时可能存在不同类别的样本同时存于同个节点中，按照多数投票的原则判断节点所属类别
预剪枝对于何时停止决策树的生长：
（1）当树达到一定深度
（2）当到达当前节点的样本数量小于某个阈值
（3）计算每次分裂对测试集的准确度提升，小于某个阈值时停止
后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶子节点进行考察，若该节点对应的子树替换成叶子结点能带来泛化性能提升，则将该子树替换为叶子节点。
树形结构为什么不需要归一化?
因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。 按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。
既然树形结构（如决策树、RF）不需要归一化，那为何非树形结构比如Adaboost、SVM、LR、Knn、KMeans之类则需要归一化。
对于线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。 但是如果进行了归一化，那么等高线就是圆形的，促使SGD往原点迭代，从而导致需要的迭代次数较少。归一化之后加快了梯度下降求最优解的速度，并有可能提高精度。
归一化的拓展
- 概率模型不需要归一化，因为这种模型不关心变量的取值，而是关心变量的分布和变量之间的条件概率。
决策树（概率模型）、随机森林（基学习器是决策树）、朴素贝叶斯（概率模型）不需要归一化
- SVM、线性回归之类的最优化问题需要归一化。归一化之后加快了梯度下降求最优解的速度，并有可能提高精度。
是否归一化主要在于是否关心变量取值 - 神经网络需要标准化处理，一般变量的取值在-1到1之间，这样做是弱化某些变量的值较大而对某些产生影响。一般神经网络中的隐藏层采用tanh激活函数比sigmoid要好，因为取值[-1, 1]，均值为0（需要）
- 在k近邻算法中，如果不对解释变量进行标准化，那么具有小数量级的解释变量的影响就会微乎其微（需要）
参考：
https://github.com/zhengjingwei/machine-learning-interview
http://www.woshipm.com/ai/1083031.html