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

6.6.3 集成算法之 Boosting

6.6.2小节讲解了Bagging及其代表算法随机森林。本节我们来介绍集成算法的另一大思想：Boosting。前文提到，Boosting和Bagging最大的区别是Boosting的一轮轮训练是依次进行的，而不是像Bagging一样是相互独立的。其核心过程可以用图6-28来描述。

Boosting的核心策略是一步步修正模型，使之逐渐逼近真实的映射关系。每一个弱分类器是建立在前一个的基础上进行的，受到前一个分类器效果的反馈加以改进，使得当前的分类器比前一轮做得更好。Boosting的代表算法有Adaboost、GBDT和Xgboost。后两者和RandomForest是机器学习竞赛中效果最出色的模型，在工业界中也极其受欢迎。

Adaboost

Adaboost主要用于分类，其核心思路是在每一个弱分类器之后对预测值和真实值进行比较，然后将分类错误的样本点在下一个分类器中赋予更高的权重，使得在下一次训练中不容易再被分错。其算法如下：

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

End

184

聚类算法

我们童年的学习是从认知开始的，通过看卡片和实物认识了各类事物，并且对具有类似特征的事物进行归纳和总结。这个过程在机器学习中被称为“聚类”，是把彼此类似的对象组成一类的分析过程。聚类学习是一种无监督式学习，在这个过程中，从获得具体的样本向量到得出聚类结果，人们是不用进行干预的，这就是“无监督”一词的由来。

在机器学习中，无监督式学习一直是我们追求的方向，而其中的聚类算法更是发现隐藏数据结构与知识的有效手段。目前，如谷歌新闻等很多应用都将聚类算法作为主要的实现手段，它们能利用大量的未标注数据构建强大的主题聚类。聚类与分类的不同在于，聚类所要求划分的类是未知的。聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。

从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入许多著名的统计分析软件包中，如SPSS、SAS等。

从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督式学习过程。与分类不同，无监督式学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式学习。

聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用的方法不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。

从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合做进一步的分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。

本节从简单高效的K均值聚类开始，依次介绍均值漂移聚类、基于密度的聚类、利用高斯混合和最大期望方法聚类、层次聚类和适用于结构化数据的图团体检测。我们不仅会分析基本的实现概念，同时还会给出每种算法的优缺点以明确实际的应用场景。

6.7.1 K均值聚类

聚类是一种包括数据点分组的机器学习技术。给定一组数据点，我们可以用聚类算法将每个数据点分到特定的组中。理论上，属于同一组的数据点应该有相似的属性或特征，而属于不同组的数据点应该有不同的属性和/或特征。聚类是一种无监督式学习的方法，是一种在许多领域常用的统计数据分析技术。K均值（K-Means）可能是最知名的聚类算法，K-Means是将n个数据样本划分成k个聚类的算法，使得同一聚类中的样本相似度较高，不同聚类样本的相似度较低。K-Means是很多入门级数据科学和机器学习课程的内容，在代码中很容易理解和实

第6章 机器学习算法

185

现。请看图6-29的例子。

K-Means的工作原理为：对于将含有n个样本组成的样本集分成k类的任务，按照如下步骤进行：

（1）从n个样本中随机选取k个点作为初始聚类中心。

(2)计算每个样本到各个聚类中心的相似度，并划分到相似度最高的聚类中心。

(3)重新计算每个聚类的均值，将其作为新的聚类中心。

(4）重复步骤（2）和（3），直到所有聚类中心不再改变为止。

可以看到，K-Means算法是一个反复迭代求解的过程。K是需要预先设定好的超参数。K-Means的优势在于速度快，因为我们真正做的是计算点和组中心之间的距离，只需要非常少的计算。因此，它具有线性复杂度O(n)。另一方面，K-Means有一些缺点。首先，你必须选择有多少组/类。理想情况下，我们希望聚类算法能够解决分多少类的问题。K-Means也从随机选择的聚类中心开始，所以它可能在不同的算法中产生不同的聚类结果。因此，结果可能不可重复并缺乏一致性。其他聚类方法更加一致。K-Medians是与K-Means有关的另一个聚类算法，除了不是用均值而是用组的中值向量来重新计算组中心。这种方法对异常值不敏感(因为使用中值），但对于较大的数据集要慢得多，因为在计算中值向量时，每次迭代都需要进行排序。

6.7.2 均值漂移聚类

均值漂移聚类是基于滑动窗口的算法，它试图找到数据点的密集区域。这是一个基于质心的算法，意味着它的目标是定位每个组/类的中心点，通过将中心点的候选点更新为滑动窗口内点的均值来完成。然后，在后处理阶段对这些候选窗口进行过滤以消除近似重复，形成最终的中心点集及其相应的组。请看图6-30的例子。

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

186

为了解释均值漂移，我们将考虑二维空间中的一组点，如图5-28所示。我们从一个以C点（随机选择）为中心，以半径r为核心的圆形滑动窗口开始。均值漂移是一种爬山算法，它包括在每一步中迭代地向更高密度区域移动，直到收敛。在每次迭代中，滑动窗口通过将中心点移向窗口内点的均值（因此而得名）来移向更高密度区域。滑动窗口内的密度与其内部点的数量成正比。自然，通过向窗口内点的均值移动，会逐渐移向点密度更高的区域。我们继续按照均值移动滑动窗口，直到没有区域在核内可以容纳更多的点。我们一直移动这个圆直到密度不再增加（即窗口中的点数）。这是通过许多滑动窗口完成的，直到所有的点位于一个窗口内。当多个滑动窗口重叠时，保留包含最多点的窗口。然后根据数据点所在的滑动窗口进行聚类。

与K-Means聚类相比，这种方法不需要选择簇数量，因为均值漂移自动发现这一点。这是一个巨大的优势。它的缺点是窗口大小/半径的选择可能是不重要的。

6.7.3 基于密度的聚类方法

DBSCAN是一种基于密度的聚类算法，类似于均值漂移，但具有一些显著的优点。请看图6-31的例子。

第6章 机器学习算法

187

DBSCAN从一个没有被访问过的任意起始数据点开始。这个点的邻域是用距离ε（ε距离内的所有点都是邻域点）提取的。如果在这个邻域内有足够数量的点（根据minPoints），则聚类过程开始，并且当前数据点成为新簇的第一个点。否则，该点将会被标记为噪声(稍后这个噪声点可能仍会成为聚类的一部分）。在这两种情况下，该点都被标记为“已访问”。对于新簇中的第一个点，其ε距离邻域内的点也成为该簇的一部分。这个使所有ε邻域内的点都属于同一个簇的过程将对所有刚刚添加到簇中的新点进行重复。重复步骤，直到簇中所有的点都被确定，即簇的ε邻域内的所有点都被访问和标记过。一旦我们完成了当前的簇，一个新的未访问点将被检索和处理，导致发现另一个簇或噪声。重复这个过程，直到所有的点被标记为已访问。由于所有点都已经被访问，因此每个点都属于某个簇或噪声。

DBSCAN与其他聚类算法相比有很多优点。首先，它根本不需要固定数量的簇，也会将异常值识别为噪声，而不像均值漂移，即使数据点非常不同，也会简单地将它们分入簇中。另外，它能够很好地找到任意大小和任意形状的簇。DBSCAN的主要缺点是当簇的密度不同时，表现不如其他聚类算法。这是因为当密度变化时，用于识别邻域点的距离阈值ε和minPoints的设置将会随着簇而变化。这个缺点也会在非常高维度的数据中出现，因为距离阈值ε再次变得难以估计。

6.7.4用高斯混合模型的最大期望聚类

K-Means的一个主要缺点是它对于聚类中心均值的简单使用。通过图6-30，我们可以明白为什么这不是最佳方法。在图5-32的左侧，可以非常清楚地看到有两个具有不同半径的圆形簇，以相同的均值作为中心。K-Means不能处理这种情况，因为这些簇的均值是非常接近的。K-Means在簇不是圆形的情况下也失败了，同样是由于使用均值作为聚类中心。

高斯混合模型（GMMs）比K-Means给了我们更多的灵活性。对于GMMs，我们假设数据点是高斯分布的，相对于使用均值假设它们是圆形的，这是一个限制较少的假设。这样，我们有两个参数来描述簇的形状：均值和标准差。以二维为例，这意味着，这些簇可以采取任何类型的椭圆形（因为我们在x和y方向都有标准差）。因此，每个高斯分布被分配给单个簇。为了找到每个簇的高斯参数（例如均值和标准差），我们将用一个叫作最大期望（EM）的优化算法。请看图6-33的图表，这是一个高斯适用于簇的例子。然后我们可以使用GMMs继续进行最大期望聚类的过程。

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

188

我们首先选择簇的数量（如K-Means所做的），并随机初始化每个簇的高斯分布参数。也可以通过快速查看数据来尝试为初始参数提供一个好的猜测。但是请注意，正如图6-33中所看到的，这不是100%必要的。给定每个簇的高斯分布，计算每个数据点属于一个特定簇的概率。一个点越靠近高斯的中心，它就越可能属于该簇。这应该是很直观的，因为对于高斯分布，我们假设大部分数据更靠近簇的中心。基于这些概率，计算一组新的高斯分布参数，使得簇内的数据点的概率最大化。我们使用数据点位置的加权和来计算这些新参数，其中权重是数据点属于该特定簇的概率。为了用可视化的方式解释它，我们可以看一下图6-33，特别是黄色的簇，以此为例。分布在第一次迭代时随即开始，我们可以看到大部分黄点都分布在右侧。当我们计算一个概率加权和时，即使中心附近有一些点，但它们大部分都在右侧。因此，分布的均值自然会接近这些点。我们也可以看到大部分点分布在“从右上到左下”。因此改变标准差来创建更适合这些点的椭圆，以便最大化概率加权和。

重复步骤直到收敛，其中分布在迭代中的变化不大。

使用GMMs有两个关键的优势。首先，GMMs比K-Means在簇协方差方面更灵活，因为标准差参数，簇可以呈现任何椭圆形状，而不是被限制为圆形。K-Means实际上是GMM的一个特殊情况，这种情况下，每个簇的协方差在所有维度都接近0。其次，因为GMMs使用概率，所以每个数据点可以有很多簇。因此，如果一个数据点在两个重叠的簇的中间，我们可以简单地通过说它百分之X属于类1，百分之Y属于类2来定义它的类，即GMMs支持混合资格。

6.7.5 凝聚层次聚类

层次聚类算法实际上分为两类：自上而下或自下而上。自下而上的算法首先将每个数据点视为一个单一的簇，然后连续地合并（或聚合）两个簇，直到所有的簇都合并成一个包含所有数据点的簇。因此，自下而上层次聚类被称为凝聚式层次聚类或HAC。这个簇的层次用树（或树状图）表示。树的根是收集所有样本的唯一簇，叶是仅仅具有一个样本的簇。在进入算法步骤前，请看图6-34的例子。

第6章 机器学习算法

189

我们首先将每个数据点视为一个单一的簇，即如果我们的数据集中有X个数据点，那么我们就有X个簇。然后，选择一个测量两个簇之间距离的距离度量标准。作为例子，我们将用averagelinkage，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。在每次迭代中，我们将两个簇合并成一个。这两个要合并的簇应具有最小的averagelinkage。即根据我们选择的距离度量标准，这两个簇之间的距离最小，因此是最相似的，应该合并在一起。重复步骤，直到到达树根，即我们只有一个包含所有数据点的簇。这样，只需要选择何时停止合并簇，即何时停止构建树，来选择最终需要多少个簇。

层次聚类不需要我们指定簇的数量，甚至可以选择哪个数量的簇看起来最好，因为我们正在构建一棵树。另外，该算法对于距离度量标准的选择并不敏感，它们都同样表现得很好，而对于其他聚类算法，距离度量标准的选择是至关重要的。层次聚类方法的一个特别好的例子是，当基础数据具有层次结构，并且想要恢复层次时，其他聚类算法不能做到这一点。与K-Means和GMMs的线性复杂度不同，层次聚类的这些优点是以较低的效率为代价的，因为它具有O(n3）的时间复杂度。

6.7.6 图团体检测

当数据可以被表示为一个网络或图（graph）时，我们可以使用图团体检测（GraphCommunityDetection）方法完成聚类。在这个算法中，图团体（graph community）通常被定义为一种顶点（vertice）的子集，其中的顶点相对于网络的其他部分要连接得更加紧密。

也许最直观的案例就是社交网络。其中的顶点表示人，连接顶点的边表示他们是朋友或互粉的用户。但是，若要将一个系统建模成一个网络，我们就必须要找到一种有效连接各个不同组件的方式。将图论用于聚类的一些创新应用包括：对图像数据的特征提取、分析基因调控网络（Gene RegulatoryNetworks，GRNs）等。图6-35展示了最近浏览过的8个网站，根据它

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

190

们在维基百科页面中的链接进行了连接。

这些顶点的颜色表示它们的团体关系，大小是根据它们的中心度（centrality）确定的。这些聚类在现实生活中也很有意义，其中黄色顶点通常是参考/搜索网站，蓝色顶点全部是在线发布网站（文章、微博或代码）。假设我们已经将该网络聚类成了一些团体，就可以使用该模块性分数来评估聚类的质量。分数更高表示我们将该网络分割成了“准确的”团体，而低分则表示我们的聚类更接近随机，如图6-36所示。

模块性可以使用以下公式进行计算：

$$
M = \frac { 1 } { 2 L } \sum _ { i , j = 1 } ^ { N } \left( A _ { i j } - \frac { k _ { i } k _ { j } } { 2 L } \right) \delta c _ { i } , c _ { j }
$$

其中L代表网络中边的数量， $\mathrm { k _ { i } }$ 和 $\mathrm { k _ { j } }$ 是指每个顶点的degree，可以通过将每一行和每一列的项加起来而得到。两者相乘再除以2L表示当该网络是随机分配的时候，顶点i和之间的预期边数。整体而言，括号中的项表示该网络的真实结构和随机组合时的预期结构之间的差。研究它的值可以发现，当 $\mathrm { A _ { i j } = 1 }$ 且 $( \mathrm { k } _ { \mathrm { i } } \mathrm { k } _ { \mathrm { j } } ) / 2 \mathrm { L }$ 很小时，其返回的值最高。这意味着，当在定点i和j之间存在一个“非预期”的边时，得到的值更高。最后的 $\mathrm { \delta c _ { i } , \ c _ { j } }$ 就是大名鼎鼎的克罗内克δ函数（Kronecker-Delta Function）。下面是其Python解释。

第6章 机器学习算法

191

通过以上公式可以计算图的模块性，且模块性越高，该网络聚类成不同团体的程度就越好。因此，通过最优化方法寻找最大模块性就能发现聚类该网络的最佳方法。

组合学（Combinatorics）告诉我们，对于一个仅有8个顶点的网络，存在4140种不同的聚类方式。16个顶点的网络的聚类方式将超过100亿种。32个顶点的网络的可能聚类方式更是将超过128septillion（10^21）种。如果你的网络有80个顶点，那么其可聚类的方式的数量已经超过了可观测宇宙中的原子数量。

因此，我们必须求助于一种启发式的方法，该方法在评估可以产生最高模块性分数的聚类上效果良好，而且并不需要尝试每一种可能性。这是一种被称为Fast-GreedyModularity-Maximization（快速贪婪模块性最大化）的算法，这种算法在一定程度上类似于前面描述的Agglomerative Hierarchical Clustering Algorithm(集聚层次聚类算法)。只是Mod-Max并不根据距离（distance）来融合团体，而是根据模块性的改变来对团体进行融合。下面介绍其工作方式。首先初始分配每个顶点到其自己的团体，然后计算整个网络的模块性M。

（1）要求每个团体对（communitypair）至少被一条单边链接，如果有两个团体融合到了一起，该算法就计算由此造成的模块性改变△M。

(2)取△M出现了最大增长的团体对，然后融合。然后为这个聚类计算新的模块性M，并记录下来。

重复（1）和（2）。每次都融合团体对，这样最后可以得到△M的最大增益，然后记录新的聚类模式及其相应的模块性分数M。当所有的顶点都被分组成一个巨型聚类时，就可以停止了。然后该算法会检查这个过程中的记录，找到其中返回最高M值的聚类模式。这就是返回的团体结构。

团体检测是现在图论中一个热门的研究领域，它的局限性主要体现在会忽略一些小的集群，且只适用于结构化的图模型。但这一类算法在典型的结构化数据中和现实网状数据中都有非常好的性能。

6.8 机器学习算法总结

机器学习领域有一条“没有免费的午餐”的定理。简单解释一下，就是没有任何一种算法能够适用于所有问题，特别是在监督式学习中。例如，你不能说神经网络就一定比决策树好，反之亦然。要判断算法的优劣，数据集的大小和结构等众多因素都至关重要。所以，你应该针对问题尝试不同的算法。然后使用保留的测试集对性能进行评估，以选出较好的算法。

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

192

第7章

深度学习

2017年5月，谷歌用深度学习算法再次引起了全世界对人工智能的关注。在与谷歌开发的围棋程序的对弈中，柯洁以0:3完败。这个胜利的背后是包括谷歌在内的科技巨头近年来在深度学习领域的大力投入。深度学习近年来取得了前所未有的突破，由此掀起了人工智能新一轮的发展热潮。深度学习本质上就是用深度神经网络处理海量数据。深度神经网络有卷积神经网络（Convolutional Neural Networks，CNN）和循环神经网络（Recurrent Neural Networks，RNN）两种典型的结构。

神经网络始于20世纪40年代，其构想来源于对人类大脑的理解，它试图模仿人类大脑神经元之间的传递来处理信息。早期的浅层神经网络很难刻画出数据之间的复杂关系，20世纪80年代兴起的深度神经网络又由于各种原因一直无法对数据进行有效训练。直到2006年，GeottreyHinton等人给出了训练深度神经网络的新思路，之后的短短几年时间，深度学习颠覆了语音识别、图像识别、文本理解等众多领域的算法设计思路。再加上用于训练神经网络的芯片性能得到了极大提升以及互联网时代爆炸的数据量，才有了深度神经网络在训练效果上的极大提升，深度学习技术才有如今被大规模商业化的可能。

7.1 走进深度学习

如图7-1所示，传统的机器学习方式是先把数据预处理成各种特征，然后对特征进行分类，分类的效果高度取决于特征选取的好坏，因此把大部分时间花在寻找合适的特征上。而深度学习是把大量数据输入一个非常复杂的模型，让模型自己探索有意义的中间表达。深度学习的优势在于让神经网络自己学习如何抓取特征，因此可以把它看作一个特征学习器。值得注意的是，深度学习需要海量的数据喂养，如果训练数据少，深度学习的性能并不见得就比传统的机器学习方法好。