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