机器学习(二):决策树、随机森林和提升算法

持续更新中。。。


信息熵、联合熵、条件熵、相对熵、互信息的定义

熵的英文原文为entropy,用来表示随机变量的不确定性。

条件熵的推导:


什么是最大熵

熵是随机变量不确定性的度量,不确定性越大,熵值越大;若随机变量退化成定值,熵为0。
如果没有外界干扰,随机变量总是趋向于无序,在经过足够时间的稳定演化,它应该能够达到的最大程度的熵。

为了准确的估计随机变量的状态,我们一般习惯性最大化熵,认为在所有可能的概率模型(分布)的集合中,熵最大的模型是最好的模型(泛化能力最好)。换言之,在已知部分知识的前提下,关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断,其原则是承认已知事物(知识),且对未知事物不做任何假设,没有任何偏见。

例如,投掷一个骰子,如果问”每个面朝上的概率分别是多少”,你会说是等概率,即各点出现的概率均为1/6。因为对这个”一无所知”的色子,什么都不确定,而假定它每一个朝上概率均等则是最合理的做法。从投资的角度来看,这是风险最小的做法,而从信息论的角度讲,就是保留了最大的不确定性,也就是说让熵达到最大。


什么是决策树

决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构建决策树来进行分析的一种方式,是一种直观应用概率分析的一种图解法;决策树是一种预测模型,代表的是对象属性与对象值之间的映射关系;决策树是一种树形结构,其中每个内部节点表示一个属性的测试,每个分支表示一个测试输出,每个叶节点代表一种类别;决策树是一种非常常用的有监督的分类算法。

决策树的决策过程就是从根节点开始,测试待分类项中对应的特征属性,并按照其值选择输出分支,直到叶子节点,将叶子节点的存放的类别作为决策结果。

决策树分为两大类:分类树和回归树,前者用于分类标签值,后者用于预测连续值,常用算法有ID3、C4.5、CART等


决策树构建过程

决策树的构造就是确定各个特征属性之间的拓扑结构(树结构),关键步骤就是分裂属性。分裂属性是指在某个节点按照某一类特征属性的不同划分构建不同的分支,其目标就是让各个分裂子集尽可能的”纯”(让一个分裂子类中待分类的项尽可能的属于同一个类别)。

构建步骤:
1)开始,所有记录看做一个节点
2)遍历每个节点的每一种分割方式,找到最好的分割点
3)将数据分割为两个节点部分N1和N2
4)对N1和N2分别继续执行2-3步,直到每个节点中的项足够”纯”

特征属性类型:
1)根据特征属性的类型不同,在构建决策树的时候,采用不同的方式,具体如下:
2)属性是离散值,而且不要求生成的是二叉决策树,此时一个属性就是一个分支
3)属性是离散值,而且要求生成的是二叉决策树,此时使用属性划分的子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支
4)属性是连续值,可以确定一个值作为分裂点split_point,按照>split_point和<=split_point生成两个分支

构建停止条件:
决策树构建的过程是一个递归的过程,所以必须给定停止条件,常用有两种:
1)当每个子节点只有一种类型的时候停止构建
2)当前节点中记录数小于某个阈值,同时迭代次数达到给定值时,停止构建,并使用max(p(i))作为节点对应类型。
方式一可能会使树的节点过多,导致过拟合(Overfiting)等问题;比较常用的方式是使用方式二作为停止条件

决策树算法是一种贪心算法策略,只考虑在当前数据特征情况下的最好分割方式,不能进行回溯操作。


决策树的纯度

子集越纯,子集中待分类的项就越可能属于同一个类别。

决策树的构建是基于样本概率和纯度进行构建操作的,那么进行判断数据集是否”纯”可以通过三个公式进行判断,分别是Gini系数、熵(Entropy)、错误率,这三个公式值越大,表示数据越”不纯”;越小表示越”纯”;实践证明这三种公式效果差不多,一般情况使用熵公式。

根据熵公式计算出各个特征属性的量化纯度值后,使用 信息增益度 来选择出当前数据集的分割特征属性;
如果信息增益度的值越大,表示在该特征属性上会损失纯度越大,就越应该在决策树的上层。计算公式为:

Gain为A为特征对训练数据集D的信息增益,它为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D/A)之差.


ID3、C4.5、CART介绍

ID3算法是决策树的一个经典的构造算法,内部使用信息熵以及信息增益来进行构建;每次迭代选择信息增益最大的特征属性作为分割属性。

优点:
决策树构建速度快;实现简单;

缺点:
计算依赖于特征数目较多的特征,而属性值最多的属性并不一定最优
ID3算法不是递增算法
ID3算法是单变量决策树,对于特征属性之间的关系不会考虑
抗噪性差
只适合小规模数据集,需要将数据放到内存中

C4.5是基于ID3算法提出的;它使用信息增益率来取代ID3算法中的信息增益,在树的构造过程中会进行剪枝操作进行优化;能够自动完成对连续属性的离散化处理;C4.5算法在选中分割属性的时候选择信息增益率最大的属性。

优点:
产生的规则易于理解
准确率较高
实现简单

缺点:
对数据集需要进行多次顺序扫描和排序,所以效率较低
只适合小规模数据集,需要将数据放到内存中

ID3算法和C4.5算法总结
1)ID3和C4.5算法均只适合在小规模数据集上使用
2)ID3和C4.5算法都是单变量决策树
3)当属性值取值比较多的时候,最好考虑C4.5算法,ID3得出的效果会比较差
4)决策树分类一般情况只适合小数据量的情况(数据可以放内存)

CART(Classification And Regression Tree,分类回归树)算法使用基尼系数作为数据纯度量化指标,选择GINI增益率最大的作为当前数据集的分割属性;可用于分类和回归两类问题。


决策树优化策略

  • 剪枝优化
    决策树过渡拟合一般情况是由于节点太多导致的,剪枝优化对决策树的正确率影响是比较大的,也是最常用的一种优化方式。

  • K-Fold Cross Validation(K交叉验证)
    首先计算出整体的决策树T,叶子点个数为N,记i属于[1,N]。对每个i,使用K交叉验证方法计算决策树,并使决策树的叶子节点数量为i个(剪枝),计算错误率,得出平均错误率;使用最小错误率的i作为最优决策树的叶子点数量,并对原始决策树T进行裁剪。

  • Random Forest
    利用训练数据随机产生多个决策树,形成一个森林。然后使用这个森林对数据进行预测,选取最多结果作为预测结果。


随机森林如何处理缺失值

方法一(na.roughfix)简单粗暴,对于训练集,同一个class下的数据,如果是分类变量缺失,用众数补上,如果是连续型变量缺失,用中位数补。
方法二(rfImpute)这个方法计算量大,至于比方法一好坏不好判断。先用na.roughfix补上缺失值,然后构建森林并计算proximity matrix,再回头看缺失值,如果是分类变量,则用没有缺失的观测实例的proximity中的权重进行投票。如果是连续型变量,则用proximity矩阵进行加权平均的方法补缺失值。然后迭代4-6次,这个补缺失值的思想和KNN有些类似12。


随机森林如何评估特征重要性

衡量变量重要性的方法有两种,Decrease GINI 和 Decrease Accuracy:
1) Decrease GINI: 对于回归问题,直接使用argmax(VarVarLeftVarRight)作为评判标准,即当前节点训练集的方差Var减去左节点的方差VarLeft和右节点的方差VarRight。
2) Decrease Accuracy:对于一棵树Tb(x),我们用OOB样本可以得到测试误差1;然后随机改变OOB样本的第j列:保持其他列不变,对第j列进行随机的上下置换,得到误差2。至此,我们可以用误差1-误差2来刻画变量j的重要性。基本思想就是,如果一个变量j足够重要,那么改变它会极大的增加测试误差;反之,如果改变它测试误差没有增大,则说明该变量不是那么的重要。


怎么理解决策树、xgboost能处理缺失值而有的模型(svm)对缺失值比较敏感

解析链接:https://www.zhihu.com/question/58230411


说一下Adaboost,权值更新公式。当弱分类器是Gm时,每个样本的的权重是w1,w2…,请写出最终的决策公式



为什么xgboost要用泰勒展开,优势在哪里

xgboost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。
引用自:@AntZ


xgboost如何寻找最优特征是又放回还是无放回的呢

xgboost在训练的过程中给出各个特征的增益评分,最大增益的特征会被选出来作为分裂依据, 从而记忆了每个特征对在模型训练时的重要性 – 从根到叶子中间节点涉及某特征的次数作为该特征重要性排序.
xgboost属于boosting集成学习方法, 样本是不放回的, 因而每轮计算样本不重复. 另一方面, xgboost支持子采样, 也就是每轮计算可以不使用全部样本, 以减少过拟合. 进一步地, xgboost 还有列采样, 每轮计算按百分比随机采样一部分特征, 既提高计算速度又减少过拟合。
引用自:@AntZ


请具体说说Boosting和Bagging的区别

(1) Bagging之随机森林
  随机森林改变了决策树容易过拟合的问题,这主要是由两个操作所优化的:
  1)Boostrap从袋内有放回的抽取样本值
  2)每次随机抽取一定数量的特征(通常为sqr(n))。
  分类问题:采用Bagging投票的方式选择类别频次最高的
  回归问题:直接取每颗树结果的平均值。
常见参数 误差分析 优点 缺点
1、树最大深度
2、树的个数
3、节点上的最小样本数
4、特征数(sqr(n)) oob(out-of-bag)
将各个树的未采样样本作为预测样本统计误差作为误分率 可以并行计算
不需要特征选择
可以总结出特征重要性
可以处理缺失数据
不需要额外设计测试集 在回归上不能输出连续结果

(2)Boosting之AdaBoost
  Boosting的本质实际上是一个加法模型,通过改变训练样本权重学习多个分类器并进行一些线性组合。而Adaboost就是加法模型+指数损失函数+前项分布算法。Adaboost就是从弱分类器出发反复训练,在其中不断调整数据权重或者是概率分布,同时提高前一轮被弱分类器误分的样本的权值。最后用分类器进行投票表决(但是分类器的重要性不同)。

(3)Boosting之GBDT
  将基分类器变成二叉树,回归用二叉回归树,分类用二叉分类树。和上面的Adaboost相比,回归树的损失函数为平方损失,同样可以用指数损失函数定义分类问题。但是对于一般损失函数怎么计算呢GBDT(梯度提升决策树)是为了解决一般损失函数的优化问题,方法是用损失函数的负梯度在当前模型的值来模拟回归问题中残差的近似值。
  注:由于GBDT很容易出现过拟合的问题,所以推荐的GBDT深度不要超过6,而随机森林可以在15以上。

(4)Boosting之Xgboost
这个工具主要有以下几个特点:
支持线性分类器
可以自定义损失函数,并且可以用二阶偏导
加入了正则化项:叶节点数、每个叶节点输出score的L2-norm
支持特征抽样
在一定情况下支持并行,只有在建树的阶段才会用到,每个节点可以并行的寻找分裂特征。