K近邻算法、决策树、随机森林、AdaBoost

博客地址:https://qianshuang.github.io

01、K近邻算法

算法原理

k近邻(k-Nearest Neighbor,kNN),应该是最简单的传统机器学习模型,给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例中的大多数属于哪个类别,就把该输入实例划分到这个类别。

k近邻算法没有显示的训练过程,在“训练阶段”仅仅是把样本保存起来,训练时间开销为零,待收到测试样本后在进行计算处理。

这个k实际上是一个超参数,k值的选择会对k近邻法的结果产生重大影响。如果选择较小的k值,意味着只有与输入实例较近的(相似的)训练实例才会对预测结果起作用,预测结果会对近邻的实例点非常敏感,如果近邻的实例点恰巧是噪声点,预测就会出错;如果选择较大的k值,就意味着与输入实例较远的(不相似的)训练实例也会对预测起作用,这样预测也会出错。在实际应用中,k值一般取一个比较小的数值,并且通常采用交叉验证法来选取最优的k值。如上图的k=5。

模型训练

代码地址:https://github.com/qianshuang/ml-exp

运行结果:

02、决策树

算法原理

决策树(Decision Tree),可以认为是if-then规则的集合,其主要优点是模型具有可读性,分类速度快。决策树学习通常包括3个步骤:特征选择、决策树的生成、决策树的修剪。

决策树的学习是一个递归的选择最优特征,然后根据该特征对训练数据进行分割的过程。为避免过拟合,还需要对生成的决策树进行剪枝。

在介绍决策树算法之前我们先说一下熵的概念:熵表示某一事件是否发生这种不确定性的度量,假设某一事件E发生的概率为p,那么p越小获得的信息量越大,p趋于0时获得的信息量趋于无穷大,p等于1时信息量为0。熵的计算公式如下:

举个栗子,假如一个盒子里面有100个小球,99个白色的,1个黑色的,那么从中拿出黑色球的概率是1%,一旦从中拿出黑色球,就会给我们带来巨大的信息量(你会想,居然还有黑色球),黑色球带给我们的信息熵为-log(1/100)=4.605,而拿到白色小球的信息熵为-log(99/100)=0.01(因为每次都能大概率拿到白色球,再拿出白色球我都不会感到惊讶)。因为我们有1/100的概率拿到黑色球,99/100的概率拿到白色球,所以这盒小球带给我们的信息熵为:-(1/100)log(1/100)-(99/100)log(99/100) = 0.056。

信息增益大的特征具有更强的分类能力,信息增益的计算公式如下:g(D,A) = H(D) - H(D|A)。D表示训练数据集,A表示某一特征,H(D)表示D的熵,H(D|A)表示特征A给定的条件下D的熵。由于H(D)取决于训练样本,所以是个定值,要使g(D,A)大,那么H(D|A)必须小,也就是特征A给定的条件下D的信息量小,亦即特征A给定的条件下D发生的概率尽量大,考虑极端情况,特征A给定,D发生的概率为1,这时候仅仅用特征A即可拟合样本数据。

下面我们看一下决策树的构建过程,考虑下面的数据表:

我们选择信息增益最大的特征作为最优特征:

最后比较各特征的信息增益值,由于特征A3(有自己的房子)最大,所以选择A3作为最优特征,然后由该特征的不同取值作为分支子节点,再对子节点递归的调用以上方法,构建整颗决策树。

以上算法就是传说中的ID3算法,如果将上面过程中的信息增益量换成信息增益比,就是传说中的C4.5算法。

模型训练

代码地址:https://github.com/qianshuang/ml-exp

运行结果:

03、随机森林

算法原理

集成学习(ensemble leaning)通过构建并结合多个学习器来完成学习任务,通过将多个学习器结合,常常可以获得比单一学习器显著优越的效果和泛化能力。集成学习中的基学习器可以是同质的,也可以是异质的。根据个体学习器的生成方式,目前的集成学习方法大致可分为三大类:一类是Bagging,个体学习器之间不存在强依赖关系,可以同时并行化训练和生成,最终结果通常通过投票机制产出,随机森林是这一类型的代表;另一类是Boosting,个体学习器之间存在强依赖关系,后一学习器依赖前一学习器的结果,,因此必须以序列化形式串行生成,我们下节会讲到的Adaboost和GBDT是这一类型的代表;其实还有第三类,叫Stacking,即将初级学习器的输出次级学习器的输入特征,深层神经网络甚至可以理解为Stacking集成学习的变种。

随机森林(Random Forest)是以决策树为基学习器构建的Bagging集成学习算法,其实现简单、计算开销小、并且在很多现实任务中表现出抢眼的效果。其主要通过样本扰动和属性扰动使得集成学习的泛化性显著提高。样本扰动是指通过对初始训练集采样构建每一棵决策树;属性扰动是指对基决策树的每个节点,分裂时从该节点的属性集合中随机选择k个属性(k一般去log(d,2),d为属性数量)。

模型训练

代码地址:https://github.com/qianshuang/ml-exp

运行结果:

04、AdaBoost

算法原理

AdaBoost(Adaptive Boosting)自适应Boosting算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器)。AdaBoost算法本身是通过改变数据分布(样本权重和分类器权重)来实现的,它根据每次训练过程中,每个样本的分类结果是否正确来确定样本输入到下一分类器的权重,然后根据上一分类器的准确率,来确定分类器的权重。

使用加权后选取的训练数据代替随机选取的训练样本,这样将训练的焦点集中在比较难分的训练数据样本上;将弱分类器联合起来,使用加权的投票机制代替平均投票机制,让分类效果好的弱分类器具有较大的权重,而分类效果差的分类器具有较小的权重。

下面我们通过一个实例来详细讨论一下AdaBoost的算法原理。考虑下面的数据分布,图中“+”和“-”表示两种类别,我们用水平或者垂直的直线作为基分类器(sk-learn库中,基分类器默认是决策树)。

算法开始前默认均匀分布D,且正负样本数量相等,共10个样本,故每个样本权值为0.1。

先进行第一次分类,这第一个分类器有3个点划分错误,根据误差表达式计算可得e1=(0.1+0.1+0.1)/1.0=0.3。

根据e1计算分类器权重(通过最小化损失函数推导而来):

。然后计算样本点权重:对于正确分类的7个点,权值不变,仍为0.1;对于错分的3个点,权值为:W0(1-e1)/e1=0.1(1-0.3)/0.3=0.2333。

再进行第二次分类,如图所示,有3个”-“分类错误,上轮分类过后权值之和为:0.17+0.23333=1.3990,所以分类误差e2=0.13/1.3990=0.2144,同样根据公式计算这第二个基分类器权重a2=0.6493,错分的3个点权值为0.1(1-0.2144)/0.2144=0.3664。

最后进行第三次分类,同上步骤可求得:e3=0.1365;a3=0.9223;D3=0.6326。

最终的强分类器即为三个弱分类器的叠加:

以上就是AdaBoost的算法原理,Adaboost实际上提供的是框架,我们可以使用各种方法构建基分类器,但是该算法对噪声点异常敏感,噪声点在迭代中可能会获得较高的权重,从而影响最终的强学习器的预测准确性。

从损失函数的角度看,AdaBoost的损失函数L(y,f(x)) = exp[-yf(x)],其中y取值1或-1(代表二分类的类别标签),f(x) = a1G1(x) + a2 * G2(x) + …,是AdaBoost的最终分类器表达式。

模型训练

代码地址 https://github.com/qianshuang/ml-exp

运行结果:

-End-

本文选自「MachineLearningAndDeepLearning」

更多资讯

关注AICUG

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180810B0TFKD00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券