人工智能与大数据技术导论

第6章

机器学习算法

机器学习一直以来都是人工智能研究的核心领域。它主要通过各种算法使得机器能够从样本、数据和经验中学习规律，从而对新的样本做出识别或对未来做出预测。20世纪80年代开始的机器学习浪潮诞生了包括决策树学习、推导逻辑规划、聚类、强化学习和贝叶斯网络等非常多的机器学习算法，它们已经被广泛地应用在网络搜索、垃圾邮件过滤、推荐系统、网页搜索排序、广告投放、信用评价、欺诈检测等领域。而这几年来取得突破性进展而受到人们关注的深度学习，只是实现机器学习的其中一种技术手段。图6-1展示了产品、数据和算法的协同效应。

算法概述

最常见的机器学习就是学习y=f(x)的映射，针对新的x预测y，这叫作预测建模或预测分析。我们的目标就是让预测更加精确。我们不知道目标函数f是什么样的。如果知道，就可以直接使用它，而不需要再通过机器学习算法从数据中进行学习。机器学习算法可以描述为学习一个目标函数f，它能够最好地映射出输入变量x到输出变量y。预测建模的首要目标是减小模型误差或将预测精度做到最佳。我们从统计等不同领域借鉴了多种算法来达到这个目标。

当面对各种机器学习算法时，一个新手最常问的问题是“我该使用哪个算法”。要回答这个问题需要考虑很多因素：（1）数据的大小、质量和类型；（2）完成计算所需要的时间；（3）任务的紧迫程度：（4）你需要对数据做什么处理。在尝试不同算法之前，即使是一个经验丰富的数据科学家，也不可能告诉你哪种算法性能最好。本节列举的是最常用的几种。如果你是一个机器学习的新手，这几种是最好的学习起点。

6.1.1 线性回归

线性回归可能是统计和机器学习领域最广为人知的算法之一。通过线性回归找到一组特定的权值，称为系数B。通过最能符合输入变量x到输出变量y关系的等式所代表的线表达出来。线性回归的例子如图6-2所示。

例如， ${ \bf y } = { \bf b } _ { 0 } + { \bf b } _ { 1 } * { \bf x }$ 。我们针对输入的x来预测 $y _ { 0 }$ 线性回归学习算法的目标是找到 ${ \sf b } _ { 0 }$ 和 $\mathsf { b } _ { 1 }$

的值。不同的技巧可以用于线性回归模型，比如线性代数的普通最小二乘法以及梯度下降优化算法。线性回归已经有超过200年的历史，已经被广泛地研究。根据经验，这种算法可以很好地消除相似的数据，以及去除数据中的噪声，是快速且简便的首选算法。

6.1.2 逻辑回归

逻辑回归是另一种从统计领域借鉴而来的机器学习算法。与线性回归相同，逻辑回归的目的是找出每个输入变量对应的参数值。不同的是，预测输出所用的变换是一个被称作logistic函数的非线性函数。logistic函数像一个大S，它将所有值转换为0到1之间的数，如图6-3所示。这很有用，我们可以根据一些规则将logistic函数的输出转换为0或1（比如，当小于0.5时则为1），然后以此进行分类。

正是因为模型学习的这种方式，逻辑回归做出的预测可以被当作输入为0和1两个分类数据的概率值。这在一些需要给出预测合理性的问题中非常有用。就像线性回归，在需要移除与输出变量无关的特征以及相似特征方面，逻辑回归可以表现得很好。在处理二分类问题上，这是一个快速高效的模型。

第6章 机器学习算法

165

6.1.3线性判别分析

逻辑回归是一个处理二分类问题的传统分类算法。如果需要进行更多的分类，线性判别分析算法（LinearDiscriminant Analysis，LDA）是一个更好的线性分类方法。线性判别分析的例子如图6-4所示。对LDA的解释非常直接，它包括针对每一个类的输入数据的统计特性。对于单一输入变量来说，包括：

类内样本均值。

●总体样本变量。

通过计算每个类的判别值，并根据最大值来进行预测。这种方法假设数据服从高斯分布（钟形曲线），所以可以较好地提前去除离群值。这是针对分类模型预测问题的一种简单有效的方法。

人工智能与大数据技术导论

166

6.1.4 分类与回归树分析

决策树是机器学习预测建模的一类重要算法，可以用二叉树来解释决策树模型。这是根据算法和数据结构建立的二叉树，并不难理解。每个节点代表一个输入变量以及变量的分叉点(假设是数值变量）。如图6-5所示是决策树的例子。

树的叶节点包括用于预测的输出变量y。通过树的各分支到达叶节点，并输出对应叶节点的分类值。树可以进行快速的学习和预测。通常并不需要对数据做特殊的处理，就可以使用这个方法对多种问题得到准确的结果。

6.1.5 朴素贝叶斯

朴素贝叶斯（NaiveBayes）是一个简单但异常强大的预测建模算法。这个模型包括两种概率，它们可以通过训练数据直接计算得到：（1）每个类的概率；（2）给定x值的情况下，每个类的条件概率。根据贝叶斯定理（见图6-6），一旦完成计算，就可以使用概率模型针对新的数据进行预测。当你的数据为实数时，通常假设服从高斯分布（钟形曲线），这样可以很容易地预测这些概率。

第6章 机器学习算法

167

之所以被称作朴素贝叶斯，是因为我们假设每个输入变量都是独立的。这是一个强假设，在真实数据中几乎是不可能的。但对于很多复杂问题，这种方法非常有效。

6.1.6 K最近邻算法

K最近邻算法（KNN）是一个非常简单有效的算法。KNN的模型表示整个训练数据集。对于新数据点的预测是：寻找整个训练集中K个最相似的样本（邻居），并对这些样本的输出变量进行总结。对于回归问题，可能意味着平均输出变量。对于分类问题，则可能意味着类值的众数（最常出现的那个值）。诀窍是如何在数据样本中找出相似性。最简单的方法是，如果你的特征都是以相同的尺度（比如都是英寸）度量的，就可以直接计算它们互相之间的欧式距离。如图6-7所示为K最近邻算法的例子。

KNN需要大量空间来存储所有的数据。但只是在需要进行预测的时候才开始计算(学习)。你可以随时更新并组织训练样本以保证预测的准确性。在维数很高(很多输入变量)的情况下，这种通过距离或相近程度进行判断的方法可能失败。这会对算法的性能产生负面的影响，被称作维度灾难。建议只有当输入变量与输出预测变量最具有关联性的时候使用这种算法。

6.1.7 学习矢量量化

K最近邻算法的缺点是需要存储所有训练数据集。而学习矢量量化（LVQ）是一个人工神经网络算法，允许选择需要保留的训练样本个数，并且学习这些样本看起来应该具有何种模式。如图6-8所示为学习矢量量化的例子。

人工智能与大数据技术导论

168

LVQ可以表示为一组码本向量的集合。在开始的时候进行随机选择，通过多轮学习算法的迭代，最后得到与训练数据集最相配的结果。通过学习，码本向量可以像K最近邻算法那样进行预测。通过计算新数据样本与码本向量之间的距离找到最相似的邻居（最符合码本向量）。将最佳的分类值（或回归问题中的实数值）返回作为预测值。如果你将数据调整到相同的尺度，比如0和1，则可以得到最好的结果。如果你发现对于数据集，KNN有较好的效果，可以尝试一下LVQ来减少存储整个数据集对存储空间的依赖。

6.1.8 支持向量机

支持向量机（SVM）可能是最常用并且最常被谈到的机器学习算法。超平面是一条划分输入变量空间的线。在SVM中，选择一个超平面，它能最好地将输入变量空间划分为不同的类，要么是0，要么是1。在二维情况下，可以将它看作一根线，并假设所有输入点都被这根线完全分开。SVM通过学习算法找到最能完成类划分的超平面的一组参数。如图6-9所示为支持向量机的例子。

第6章 机器学习算法

169

超平面和最接近的数据点的距离看作一个差值，最好的超平面可以把所有数据划分为两个类，并且这个差值最大。只有这些点与超平面的定义和分类器的构造有关。这些点被称作支持向量，是它们定义了超平面。在实际使用中，优化算法被用于找到一组参数值使差值达到最大。SVM可能是一种最为强大的分类器。

6.1.9 Bagging 和随机森林

随机森林是一个常用并且最为强大的机器学习算法。它是一种集成机器学习算法，称作自举汇聚或Bagging。Bootstrap是一种强大的统计方法，用于数据样本的估算，比如均值。从数据中采集很多样本，计算均值，然后将所有均值再求平均，最终得到一个真实均值的较好的估计值。在Bagging中用了相似的方法。但是通常用决策树来代替对整个统计模型的估计。从训练集中采集多个样本，针对每个样本构造模型。当你需要对新的数据进行预测时，每个模型做一次预测，然后对预测值进行平均，得到真实输出的较好的预测值。如图6-10所示为随机森林的例子。

这里的不同在于在什么地方创建树，与决策树选择最优分叉点不同，随机森林通过加入随机性从而产生次优的分叉点。每个数据样本所创建的模型与其他的都不相同，但在唯一性和不同性方面仍然准确。结合这些预测结果可以更好地得到真实的输出估计值。如果在高方差的算法（比如决策树）中得到较好的结果，通常也可以通过Bagging这种算法得到更好的结果。

6.1.10 Boosting 和 AdaBoost

Boosting是一种集成方法，通过多种弱分类器创建一种强分类器。它首先通过训练数据建立一个模型，然后建立第二个模型来修正前一个模型的误差。在完成对训练集完美预测之前，模型和模型的最大数量都会不断添加。

人工智能与大数据技术导论

170

courtesv to Alexander thier hmo //sl ics uci edu/Classes/2012F-273a?action-dowmioad&uoname-10-ensembles. odf

AdaBoost 是第一种成功地针对二分类的Boosting算法，是理解Boosting最好的起点。现代的Boosting方法是建立在AdaBoost之上的，多数都是随机梯度Boosting机器。如图6-11所示是 AdaBoost的例子。

AdaBoost与短决策树一起使用。当第一棵树创建之后，每个训练样本的树的性能将用于决定针对这个训练样本下一棵树将给予多少关注。难于预测的训练数据给予较大的权值，反之容易预测的样本给予较小的权值。模型按顺序建立，每个训练样本权值的更新都会影响下一棵树的学习效果。完成决策树的建立之后，进行对新数据的预测，训练数据的精确性决定了每棵树的性能。因为重点关注修正算法的错误，所以移除数据中的离群值非常重要。

6.2 支持向量机算法

本节我们以著名的SVM算法切入，来感受一下一个成熟完备的机器学习算法是怎么运作的。SVM是机器学习最经典也是最实用的模型之一。这个算法从字面上不易理解，但没关系，学习新的算法时，我们最重要的是先理解这个算法的思想是什么。SVM的思想是找到一个“分割器”，将两种类别的样本点“切开”。

我们的核心目标是找到一条直线去分割平面上的两种点。这里首先介绍线性可分这个概念。像图6-12这样，可以用一条直线将两种类别的点分开的情形称为线性可分。而像图6-13这样的情形则为线性不可分。

我们先来看线性可分的情况。对于二维空间（平面）中线性可分的情形，我们只需找到一条直线，使得正值样本落在直线的一侧，负值样本落在直线的另一侧。对于线性可分的样本集来说，这样的直线是存在的，而且是不唯一的。比如图6-14中y=-x+2和y=-x+2.1都是满足条件的直线。

第6章 机器学习算法

171

推广到高维空间中，这条分割的“直线”不再是直线，而叫作超平面(hyperplane）。在三维空间中，超平面是二维的平面。在更高维空间中，超平面会更加抽象。为了方便描述这个超平面，我们需要知道如何用数学形式指代它，就像用 $\mathbf { y } = - \mathbf { x } + 2$ 表示图6-12的直线一样。

首先，我们要知道，在n维空间中，一个点的坐标需要n个数值来表示，即 $( \mathbf { x } 1 , \mathbf { x } 2 , . . . , \mathbf { x } \mathbf { n } )$ o我们可以把它简写为向量x，那么在n维空间中，超平面就可以用以下形式来表示：

$$
\mathbf { \Delta W } \circ \mathbf { \Delta x } + \mathbf { b } = 0
$$

其中，w和b是参数，就如同直线y=ax+b 中的a和 b一样，只不过这里的w是n维向量，b为实数。 $\mathrm { ~ w ~ } \bullet \mathrm { ~ x ~ } + \mathrm { b } > 0$ 和 $\mathrm { w } \cdot \mathrm { x } + \mathrm { b } < 0$ 分别对应超平面两侧的空间。对于一个未知标签的样本点x，我们只需看wx+b的正负，即可判别它是正值样本还是负值样本。这种分类模型叫作感知机（perceptron）。

让我们回到二维平面的例子。可以将图中两种点完全隔离的直线有无数条，那么其中是否存在一条最优的直线呢？

在图6-15中，直线a和b都能分离两种点，但当更多的点进来后，直线a将其中1个点错误地归类了，这是因为我们这条线画的“不够好”，离样本点太近，导致对新来的点划分不够精确。直线b做得更好，是因为它离两边的点都比较远，因此更容易将新来的点划分正确。于是我们想到，最“中间”的直线是最合适的。也就是说，我们应该找到离两侧样本点簇都尽可能远的直线。用专业术语来表示的话，就是让这个分类器的margin最大。

以上讨论的都是线性可分的情形。对于线性不可分的情况，SVM的解决方案是通过核函数进行空间变换，将低位空间投射到高位空间中去，使经过变换后的样本点实现线性可分。说起来可能有些玄幻，但这确实是可行的。

人工智能与大数据技术导论

172

如图6-16所示的平面中的点显然无法用直线分开。即使引入松弛因子也不行，因为这本质上就不是线性可分的问题。但设想我们会使用某种“魔法”，能让这些点漂浮到空间中去，并且外围的点飘得更高，内圈的点飘得略低，就像图6-17一样。这样我们就可以用一张纸将这个漂浮的空间切断，实现两种点的分离。将这张纸还原到原平面中去是一条曲线。

这个映射对应的规则是：

在实际应用中，上述的空间变换是通过核变换实现的。核变换的表达形式与上面的公式不太相同。虽然SVM从本质上来说一种线性分类器，但Kernel SVM将核变换与线性分类器结合，使得SVM可以解决非线性问题。可以处理非线性边界问题是SVM最大的优势之一。

6.3 逻辑回归算法

LogisticRegression（逻辑回归）是一种常见的分类模型。我们不要被名字所惑，逻辑回归是一个分类模型，也就是说，要使用这个模型，标签数据必须是离散型变量。最简单的离散型变量是二元离散型变量（binaryvariable），即变量只取两个值：0或者1。逻辑回归之所以带有“回归”二字，是因为它以线性回归为基础演化而来，与线性回归的表达形式相似。

让我们先回顾一下线性回归。线性回归用来刻画连续型变量y与若干变量 $^ { \mathrm { x 1 , x 2 , } }$ ..之间的线性关系，其基本形式为：

$$
\mathbf { y } = \mathbf { a } 0 + \mathbf { a } 1 \mathbf { x } 1 + \mathbf { a } 2 \mathbf { x } 2 + \ldots + \mathbf { a } \mathbf { m } \mathbf { x } \mathbf { m }\tag{1}
$$

逻辑回归在上面公式的基础上对右侧施加一个叫作sigmoid的函数：

$$
\mathbf { y } = \mathbf { f } ( \mathbf { a } 0 + \mathbf { a } 1 \mathbf { x } 1 + \mathbf { a } 2 \mathbf { x } 2 + \ldots + \mathbf { a } \mathbf { m } \mathbf { x } \mathbf { m } )\tag{2}
$$

$\phi ( z ) = 1 / ( 1 + e ^ { - z } )$ 的图像如图6-18所示。

第6章 机器学习算法

173