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

持续更新中。。。

决策树

相关链接


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

下面的截图截自宗成庆的《统计自然语言处理 》:

熵
联合熵与条件熵
互信息
相对熵
交叉熵
困惑度


什么是最大熵

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

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

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


什么是决策树

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

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

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


决策树构建过程

顾名思义,决策树就是用一棵树来表示我们的整个决策过程。这棵树可以是二叉树(比如 CART 只能是二叉树),也可以是多叉树(比如 ID3、C4.5 可以是多叉树或二叉树)。

根节点包含整个样本集,每个叶节都对应一个决策结果(注意,不同的叶节点可能对应同一个决策结果),每一个内部节点都对应一次决策过程或者说是一次属性测试。从根节点到每个叶节点的路径对应一个判定测试序列。

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

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

特征属性类型:
根据特征属性的类型不同,在构建决策树的时候,采用不同的方式,具体如下:
1)属性是离散值,而且不要求生成的是二叉决策树,此时一个属性就是一个分支
2)属性是离散值,而且要求生成的是二叉决策树,此时使用属性划分的子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支
3)属性是连续值,可以确定一个值作为分裂点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 使用 信息增益 作为选择特征的准则;C4.5 使用 信息增益率 作为选择特征的准则;CART 使用 Gini 系数 作为选择特征的准则。

1、ID3

ID3内部使用信息熵以及信息增益来进行构建;每次迭代选择信息增益最大的特征属性作为分割属性。

熵表示的是数据中包含的信息量大小。熵越小,数据的纯度越高,也就是说数据越趋于一致,这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大,则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说,用属性 a 来划分训练集,得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

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

缺点:

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

2、C4.5

C4.5 基于ID3算法提出;它克服了 ID3 仅仅能够处理离散属性的问题,以及信息增益偏向选择取值较多特征的问题,使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

C4.5 在树的构造过程中会进行剪枝操作进行优化,也能够自动完成对连续属性的离散化处理;C4.5 处理连续特征是先将特征取值排序,以连续两个值中间值作为划分标准。尝试每一种划分,并计算修正后的信息增益,选择信息增益最大的分裂点作为该属性的分裂点。

优点:

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

缺点:

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

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

3、CART

CART(Classification And Regression Tree,分类回归树) 的全称是分类与回归树。从这个名字中就应该知道,CART 既可以用于分类问题,也可以用于回归问题。

CART 与 ID3,C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说,无论是回归还是分类问题,无论特征是离散的还是连续的,无论属性取值有多个还是两个,内部节点只能根据属性值进行二分。

回归树中,使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值,是划分到该叶子节点的所有样本目标值的均值,这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分,还需要遍历所有属性,以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差,选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则,所以又叫做最小二乘回归树。

分类树种,使用 Gini 指数最小化准则来选择特征并进行划分;

Gini 指数表示集合的不确定性,或者是不纯度。基尼指数越大,集合不确定性越高,不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是,基尼指数是为了最小化误分类的概率。

4、信息增益 vs 信息增益比

之所以引入了信息增益比,是由于信息增益的一个缺点。那就是:信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项,解决了这个问题。

5、Gini 指数 vs 熵

既然这两个都可以表示数据的不确定性,不纯度。那么这两个有什么区别那?

  • Gini 指数的计算不需要对数运算,更加高效;
  • Gini 指数更偏向于连续属性,熵更偏向于离散属性。

剪枝

决策树算法很容易过拟合(overfitting),剪枝算法就是用来防止决策树过拟合,提高泛华性能的方法。

剪枝分为预剪枝与后剪枝。

  • 预剪枝是指在决策树的生成过程中,对每个节点在划分前先进行评估,若当前的划分不能带来泛化性能的提升,则停止划分,并将当前节点标记为叶节点。

  • 后剪枝是指先从训练集生成一颗完整的决策树,然后自底向上对非叶节点进行考察,若将该节点对应的子树替换为叶节点,能带来泛化性能的提升,则将该子树替换为叶节点。

那么怎么来判断是否带来泛化性能的提升那?最简单的就是留出法,即预留一部分数据作为验证集来进行性能评估。


决策树优化策略

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

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

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


决策树总结

决策树算法主要包括三个部分:特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。

  • 特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则:信息增益、信息增益比、Gini 指数;
  • 决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始,递归的生成决策树。相当于是不断选取局部最优特征,或将训练集分割为基本能够正确分类的子集;
  • 决策树的剪枝。决策树的剪枝是为了防止树的过拟合,增强其泛化能力。包括预剪枝和后剪枝。

随机森林如何处理缺失值

方法一(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要用泰勒展开,优势在哪里

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


xgboost如何寻找最优特征,是有放回还是无放回

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