机器学习浅析（中）

上篇介绍了k-近邻算法，接下来介绍其他几类分类算法。

决策树ID3算法

相对上篇介绍的k-近邻算法，决策树有一个很明显的优点那就是可以解释数据的内在含义，而且其构建的数据形式也非常容易理解。决策树原理就是从混乱的数据中提取规则，通过数学信息论原理不断的将数据混乱度进行缩减量化直至趋于稳定，最后构建一套稳定的规则，当有新的数据输入时，我们可以根据这个规则，对新数据的特征进行抽茧剥丝，最后得出分类结果。

决策实例

上面讲的决策树原理比较复杂，接下来用实际例子来进行说明，

1.png

图 1 是一棵结构简单的决策树，用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性：是否拥有房产，是否结婚，平均月收入。每一个内部节点都表示一个属性条件判断，叶子节点表示贷款用户是否具有偿还能力。例如：用户甲没有房产，没有结婚，月收入 5K。通过决策树的根节点判断，用户甲符合右边分支 (拥有房产为“否”)；再判断是否结婚，用户甲符合左边分支 (是否结婚为否)；然后判断月收入是否大于 4k，用户甲符合左边分支 (月收入大于 4K)，该用户落在“可以偿还”的叶子节点上。所以预测用户甲具备偿还贷款能力。

决策树构建

理解了决策树是什么之后，接下来就是我们的重点，如何构建我们的决策树？在学这个算法的时候，不经意之间让我对数学有了一个新的认识，自然界有很多感觉上的东西是可以通过数学原理来对其进行量化，并被我们了解和认识，让我们感受到了数学的魅力。而决策树就是一个很好的例子，它就是把生活中随处可见的问题用数学方式量化来进行解决。
接下来回到正题，如何搭建决策树？首先我们要讲两个重要的数学概念，信息增益和熵。什么是信息增益？在开始划分数据之前之后信息发生的变化就称作信息增益。而熵是物理学和信息论的一个概念，物理学成为混乱度，在信息论里面，集合信息的度量方式成为香农熵或简称熵。这两个数学概念对于特征的选取来说非常的重要。

接下来讲一下特征选择。选择一个合适的特征对于决策树的构建很重要，作为判断节点，它可以快加快分类的速度，减少决策树的深度。决策树的目标就是把数据集按对应的类标签进行分类。最理想的情况是，通过特征的选择能把不同类别的数据集贴上对应类标签。

• 信息增益

信息熵表示的是不确定度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
假设在样本数据集 D 中，混有 c 种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的节点。在数据集中，可以计算出该数据中的信息熵：

作用前的信息熵.png

其中 D 表示训练数据集，c 表示数据类别数，Pi 表示类别 i 样本数量占所有样本的比例。
对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵的为 Info(D)，计算如下：

作用后的信息熵.png

其中 k 表示样本 D 被分为 k 个部分。
信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下：

信息熵减少的值.png

对于决策树节点最合适的特征选择，就是 Gain(A) 值最大的特征。
挑选好最合适的特征之后，接下来就开始在整个数据集的基础上对其进行分类，每分类一次就就挑选新的特征对数据集重复进行以上的操作，直到某个小数据集内部数据的数据类别全部相同，或者没有可以继续分类的特征了，那么我们就得到了一颗决策树，当需要处理新样本的时候，我们按照决策树对特征的使用顺序和新样本的各个特征值，逐步对这个样本进行分类，直到决策树的叶子节点处，最后这个叶子节点数据集的数据类别就是我们根据决策树算法所推断出来的新样本的数据类别。

朴素贝叶斯算法

朴素贝叶斯分类法是贝叶斯分类中最简单的一种分类方法，在讲解朴素贝叶斯分类之前，我们需要了解一下它的数学基础——贝叶斯定理。这个定理解决了现实生活里经常遇到的问题：已知某条件概率，如何得到两个事件交换后的概率，也就是在已知P(A|B)的情况下如何求得P(B|A)。这里先解释什么是条件概率：
表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。其基本求解公式为：

条件概率

贝叶斯定理之所以有用，是因为我们在生活中经常遇到这种情况：我们可以很容易直接得出P(A|B)，P(B|A)则很难直接得出，但我们更关心P(B|A)，贝叶斯定理就为我们打通从P(A|B)获得P(B|A)的道路。下图即为贝叶斯定理：

贝叶斯定理
朴素贝叶斯分类的正式定义如下：
数学原理推导.jpg
上面这张图能很好的用数学原理对朴素贝叶斯进行解释，接下来讲完数学原理之后，我们用实际例子来对其进行说明。某个医院早上收了六个门诊病人，如下表：
案例.jpg

现在又来了第七个病人，是一个打喷嚏的建筑工人。请问他患上感冒的概率有多大？
根据贝叶斯定理：

贝叶斯定理
可得： 推导公式1.jpg 假定"打喷嚏"和"建筑工人"这两个特征是独立的，因此，上面的等式就变成了 推导公式2.jpg 这是可以计算的。 推导公式3.jpg 因此，这个打喷嚏的建筑工人，有66%的概率是得了感冒。同理，可以计算这个病人患上过敏或脑震荡的概率。比较这几个概率，就可以知道他最可能得什么病。这就是贝叶斯分类器的基本方法：在统计资料的基础上，依据某些特征，计算各个类别的概率，从而实现分类。
上述变量是属于离散随机变量，用条件概率处理是没什么问题。但是如果是连续变量，就不适宜按照某个特定值计算概率。处理技巧是将连续值变为离散值，把连续变量划分为相应的区间，计算区间概率，同样再利用上面的原理进行概率的计算。但是有些特征既是连续变量，又因为样本太少，不能用区间划分，这种情况该怎么办呢？这时，可以假设数据符合正态分布，通过样本计算出均值和方差，也就是得到正态分布的密度函数。有了密度函数，就可以把值代入，算出某一点的密度函数的值。以上就是朴素贝叶斯算法对于不同数据变量利用数学来进行分类的原理。

Logistic回归算法

Logistic回归算法虽然名字里面带有回归，但本质上仍和前面的算法一样，还是属于分类判别算法，只是里面涉及到回归公式。这里先用一个简单的概念来定义回归：假设现在有一些数据点，我们用一条直线对这些点进行拟合（该线成为最佳拟合直线），这个过程从就称作回归。logistic回归进行分类的主要思想是：根据现有数据对分类边界线建立回归公式，以此进行分类。这里的“回归”一词源于最佳拟合，表示要找到最佳拟合参数集。
前面讲的是logistics回归的定义。接下来讲它的数学原理，虽说整个算法起到分类的作用，但其实本质是里面的数学函数原理在起一个类似分类的作用，对所有的输入结果，都能对其预测出类别。例如，在两个类的情况下，函数能够输出0或1,那么就起到分类的作用。类似的函数包括海维赛德阶跃函数，也称作单位阶跃函数，但是它存在一个问题，该函数在跳跃点上从0瞬间跳跃到1，这个瞬间跳跃过程有时很难处理。还有另外一个函数也具备相同跳跃的性质，不过它在数学上更易处理这就是Sigmoid函数。

Sigmoid函数具体的计算公式如下： Sigmoid函数表达式.jpg zigmoid函数的图像是什么样的？ Sigmoid函数图像.jpg
我们可以看到Sigmoid函数是一个阶跃函数，不管输入什么样的值，输出的值都在0到1之间，当横坐标数据刻度足够大时，Sigmoid函数看起来就像一个阶跃函数。因此为了实现Logistic回归分类器，我们可以在每个特征上都乘以一个回归系数，然后把所有的结果值相加，把这个总和代入Sigmoid函数中，进而得到一个范围在0-1之间的数值。任何大雨0.5的数据被分为1类，小于0.5即被归入0类。所以，Logistic回归也可以被看成是一种概率估计。
变成函数之后，现在的问题变成了，最佳回归系数是多少？在《机器学习实战》这本书里面对回归系数的讲解中并没有涉及到太多数学原理上的知识，只是从算法的层面直接把概念词抛出来，告诉我们求导最佳回归系数的方法。比如说我们要求最佳回归系数，那么就需要用到最优化的一些理论知识。比如说梯度上升算法，还有它的简化版随机梯度上升算法。作者并没有用到概率论和统计学方面的知识来进行解释。然后我看了一下其他网站关于Logistic回归算法的讲解，大多涉及到数学原理讲解，比如说最优化方面的最小二乘法和最大似然估计。

接下来我们讲Logistic回归算法里面的数学原理。

Logistic回归常规步骤

• 寻找h函数（即预测函数）
• 构造J函数（损失函数）
• 想办法使得J函数最小并求得回归参数（θ）

构造预测函数h(x)

1. Logistic函数（或称为Sigmoid函数），函数形式为：

   
   Sigmoid函数表达式
   Sigmoid图像表达式
   对于线性边界的情况，边界形式如下： 图1
   其中，训练数据为向量 ： 线性方程
   最佳参数： 最佳参数
   构造预测函数为： 目标函数
   函数h(x)的值有特殊的含义，它表示结果取1的概率，因此对于输入x分类结果为类别1和类别0的概率分别为：
   P(y=1│x;θ)=h_θ (x)
   P(y=0│x;θ)=1-h_θ (x)

构造损失函数J（m个样本，每个样本具有n个特征）

Cost函数和J函数如下，它们是基于最大似然估计推导得到的。

损失函数

损失函数详细推导过程

1，求代价函数
概率综合起来写成：

代价函数
取似然函数为： i似然函数
对数似然函数为： 图2
最大似然估计就是求使l(θ)取最大值时的θ，其实这里可以使用梯度上升法求解，求得的θ就是要求的最佳参数。
在Andrew Ng的课程中将J(θ)取为下式，即： 最佳参数值

2，梯度下降法求解最小值

梯度下降法求导过程

θ更新过程可以写成：

最佳参数

这就是最优化的数学原理推导，当我们求得最佳参数之后，我们就构建了一个Logistic回归分类器，然后我们就可以利用这个算法来进行分类。该算法的优点是计算代价不高，易于理解和实现，缺点就是欠拟合，分类精度可能不高。

支持向量机SVM算法

SVM算法原理

这个算法原理我感觉我偏笑的文章中对其概括的很好：SVM通过N-1维的分隔超平面线性分开N维的数据，距离分隔超平面最近的点被叫做支持向量，我们利用SMO（SVM实现方法之一）最大化支持向量到分隔面的距离，这样当新样本点进来时，其被分类正确的概率也就更大。我们计算样本点到分隔超平面的函数间隔，函数间隔为正，分类正确，为负则分类错误。函数间隔的绝对值除以||w||就是几何间隔，几何间隔始终为正，可以理解为样本点到分隔超平面的几何距离。若数据不是线性可分的，那我们引入核函数的概念，从某个特征空间到另一个特征空间的映射是通过核函数来实现的，我们利用核函数将数据从低维空间映射到高维空间，低维空间的非线性问题在高维空间往往会成为线性问题，再利用N-1维分割超平面对数据分类。
那在上面的简述中什么是分隔超平面？如果数据的N维的，分隔超平面就是N-1维的，比如给出的数据点分布在二维平面之中，那分割超平面就是一条直线，如果数据点分布在三维空间之中，那分割超平面就是个平面，更高维同理。
不过上面是用数学原理来进行解释，涉及到的数学概念太多，有点不大好懂，我们先用通俗易懂的语言来解释支持向量机究竟是如何工作的？

支持向量机工作原理

支持向量机的基础概念可以通过一个简单的例子来解释。让我们想象两个类别：红色和蓝色，我们的数据有两个特征：x 和 y。我们想要一个分类器，给定一对（x，y）坐标，输出仅限于红色或蓝色。我们将已标记的训练数据列在下图中：

图1
支持向量机会接受这些数据点，并输出一个超平面（在二维的图中，就是一条线）以将两类分割开来。这条线就是判定边界：将红色和蓝色分割开。 图2
但是，最好的超平面是什么样的？对于 SVM 来说，它是最大化两个类别边距的那种方式，换句话说：超平面（在本例中是一条线）对每个类别最近的元素距离最远。因为隔得越远，数据越有可能不混在一起，我们的分类的可能性也会越高。 图3
这里有一个视频解释可以告诉你最佳的超平面是如何找到的。youtube.com/watch?v=3liCbRZPrZA
线性数据 上面的例子很简单，因为那些数据是线性可分的——我们可以通过画一条直线来简单地分割红色和蓝色。然而，大多数情况下事情没有那么简单。看看下面的例子： 图4

很明显，你无法找出一个线性决策边界（一条直线分开两个类别）。然而，两种向量的位置分得很开，看起来应该可以轻易地分开它们。

这个时候我们需要引入第三个维度。迄今为止，我们有两个维度：x 和 y。让我们加入维度 z，并且让它以直观的方式出现：z = x² + y²（没错，圆形的方程式）

于是我们就有了一个三维空间，看看这个空间，他就像这样：

图5
支持向量机将会如何区分它？很简单：
图6
太棒了！请注意，现在我们处于三维空间，超平面是 z 某个刻度上（比如 z=1）一个平行于 x 轴的平面。它在二维上的投影是这样： 图7
于是，我们的决策边界就成了半径为 1 的圆形，通过 SVM 我们将其成功分成了两个类别。网址里面的的视频用 3D 形式展现了一个类似的分类效果：https://www.youtube.com/watch?v=3liCbRZPrZA

核函数技巧

在以上例子中，我们找到了一种通过将空间巧妙地映射到更高维度来分类非线性数据的方法。然而事实证明，这种转换可能会带来很大的计算成本：可能会出现很多新的维度，每一个都可能带来复杂的计算。为数据集中的所有向量做这种操作会带来大量的工作，所以寻找一个更简单的方法非常重要。

还好，我们已经找到了诀窍：SVM 其实并不需要真正的向量，它可以用它们的数量积（点积）来进行分类。这意味着我们可以避免耗费计算资源的境地了。我们需要这样做：

想象一个我们需要的新空间：
z = x² + y²
找到新空间中点积的形式：
a · b = xa· xb + ya· yb + za· zb
a · b = xa· xb + ya· yb + (xa² + ya²) · (xb² + yb²)
让 SVM 处理新的点积结果——这就是核函数
这就是核函数的技巧，它可以减少大量的计算资源需求。通常，内核是线性的，所以我们得到了一个线性分类器。但如果使用非线性内核（如上例），我们可以在完全不改变数据的情况下得到一个非线性分类器：我们只需改变点积为我们想要的空间，SVM 就会对它忠实地进行分类。

注意，核函数技巧实际上并不是 SVM 的一部分。它可以与其他线性分类器共同使用，如逻辑回归等。支持向量机只负责找到决策边界。

以上就是支持向量机的基础。总结来说就是：
支持向量机能让你分类线性可分的数据；
如果线性不可分，你可以使用 kernel 技巧；
然而，对文本分类而言最好只用线性 kernel。
相比于神经网络这样更先进的算法，支持向量机有两大主要优势：更高的速度、用更少的样本（千以内）取得更好的表现。这使得该算法非常适合文本分类问题。

AdaBoost元算法

AdaBoost算法是一种集成学习（ensemble learning）方法。集成学习是机器学习中的一类方法，它对多个机器学习模型进行组合形成一个精度更高的模型，参与组合的模型称为弱学习器（weak learner）。在预测时使用这些弱学习器模型联合起来进行预测；训练时需要用训练样本集依次训练出这些弱学习器。典型的集成学习算法是随机森林和boosting算法，而AdaBoost算法是boosting算法的一种实现版本。

接下来讲一下它的运行过程，其运行过程如下：
训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。其中，错误率ε的定义为：

alpha的计算公式如下： alpha计算公式.png

AdaBoost算法的流程如图4所示：

图4.jpg

计算出alpha值之后，可以对权重向量D进行更新，以使得那些正确分类的样本的权重降低而错分样本的权重升高。D的计算方法如下。
如果某个样本被正确分类，那么该样本的权重更改为：

正确分类权重

而如果某个样本被错分，那么该样本的权重更改为：

错误分类权重

在计算出D之后，AdaBoost又开始进入下一轮迭代。AdaBoost算法会不断地重复训练和调整权重的过程，直到训练错误率为0或者弱分类器的数目达到用户的指定值为止。
以上就是算法的大致过程，不过具体详细的数学推导，我自己也看的有点稀里糊涂，在此就不详细列出来了，有兴趣的可以自己去网上搜索。AdaBoost算法的数学原理在我看来有点小小的困难，但大致是怎么回事基本是清楚了，就是每个分类器都有它的识别错误率，但是我们可以利用多个分类器，对错误率进行降低，从而得到的最终结果错误率肯定要远远小于单个分类器，正好应了一句古话，三个臭皮匠抵的一个诸葛亮。

在下一篇文章中我会讲到监督学习方式包含的回归算法以及无监督学习方式和它相关的一些算法，还有机器学习实践常用到的一些其他工具，它们可以应用于前三部分的算法上。比如说PCA降维工具，还有SVD简化数据工具。讲完之后我会开始学习深度学习，进入下一个知识点。

SVM支持向量机参考文章：
https://bit.ly/2AVZlsK
https://bit.ly/2Hpjey3
https://bit.ly/2DqKMyX
https://bit.ly/2DrmlSe
https://bit.ly/2U5xZrd
Adaboost算法参考文章
https://bit.ly/2MrWIUg
https://bit.ly/2FQBNZu