（五）集成算法

集成学习是使用一系列学习器进行学习，并使用某种规则将学习结果进行整合，从而获得比单个学习器更好的学习效果。一般情况下，集成学习中的学习器都是同质的弱学习器。集成算法的典型代表是Boosting和Bagging，它们都是一类算法的统称。

Boosting主要特点是，使用一组弱分类器进行迭代更新，构造一个强分类器。在每轮迭代中会在训练集上产生一个新的弱分类器并且赋予其权重，同时重新设置训练样本的权重，最后对所有弱分类器投票评估最终的分类结果。该算法有两个值得深入探讨的地方：一是在每一轮迭代中如何改变训练数据的分布情况；二是如何将多个弱分类器组合成一个强分类器，使用策略不同，算法效果也不相同。

AdaBoost是“自适应增强”，相比传统的Boosting，这个算法“增强”体现在它设置了两种权重：一种是数据的权重，另一种是弱分类器的权重。弱分类器训练的目的在于通过改变样本分布，使得分类器聚集在那些很难区分的样本上，对容易错分的样本加强学习，增加错分样本的权重，这样做使得错分的样本在下一轮迭代中有更大的作用，这也是一种对错分样本的惩罚机制。这种设计有两个好处：一方面可以根据权重的分布情况，提供数据抽样的依据，另一方面可以利用权重提升弱分类器的决策能力，使得弱分类器也能达到强分类器的效果。Adaboost算法最大的优点是它不要预先知道分类器的错误率上限，最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，具有深挖分类器的能力；同时它能根据弱分类器的反馈，自适应的调整假定的错误率，执行效率高；并且该算法提供一种框架，框架内可以使用各种方法构建子分类器，不用对特征进行筛选，不存在过拟合现象。其缺点是会使难于分类的样本的权值呈指数增长，训练会过于偏向这类样本，导致算法易受“噪声”干扰。

GBDT是梯度提升决策树，也是典型的Boosting算法，它结合了梯度下降、决策树两种方法的优点，再采用集成的方式训练模型，得到更优的结果。GBDT算法要经过多轮的迭代，每轮迭代产生一个弱分类器，每个分类器在上一轮分类器残差基础上进行训练。它的主要思想是，基于之前建立的模型的损失函数的梯度下降方向建立下一个学习器。GBDT可以用更少的特征建立模型，性能优异，被广泛用于欺诈检测、交易风险评估、搜索结果排序、文本信息处理等领域。

Bagging算法的主要特点是采用随机、有放回的选择方式挑选训练集，然后“并行”构造弱学习器，最后通过结合的方式生成强学习器。Boosting算法中，各个弱学习器之间存在依赖关系，下一个弱学习器依赖上一个弱学习器的结果调整参数，是一种串行结构；但是在Bagging算法中，各个弱学习器之间没有依赖关系，各个弱学习器不需要依赖别人的结果，是一种并行结构。

随机森林（Random Forest）算法是Bagging算法的一种特殊改进版，它是由众多采用随机抽样获得的训练集生成的CART树的集成学习模式。它的随机性主要体现在两方面：一方面是随机选取数据；另一方面是随机选取特征。随机森林算法的优点主要有三个：首先集成过程中不同决策树可以并行训练生成，耗时短且效率高；第二随机森林算法通过投票的机制，避免了单棵决策树造成的过拟合问题；第三随机森林算法源于决策树，因此继承了决策树的众多优点。但同时随机森林算法也牺牲了模型的可解释性，是一种黑盒模型。

（六）kNN及降维算法

kNN算法是一种常用的监督学习，它以样本之间的距离作为分类依据。如果一个样本在特征空间中，将这个样本的特征与和它最相似（最邻近）的k个样本的特征进行比对，如果这k个样本中，大多数样本都属于某一个类别，则我们判断该样本也属于这个类别。

优点：

1、思想简单，易实现，复杂度低，既可以用来做分类也可以用来做回归

2、对异常数据点不敏感

3、适用于多分类问题、非线性分类，多分类很多情况下kNN比SVM的表现要好

缺点：

1、当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k个相邻样本中大容量类的样本占多数

2、计算量较大，耗时大，对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的k个最近邻点

3、可理解性差，无法给出像决策树那样的规则，无法给出数据内在含义

适用场景：

可用于文本分类、模式识别、聚类分析，多分类领域，手写体分类等，kNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。

kNN在数据维度变大时就失去了独特的优势，我们需要通过降维方法降低数据维度，达到去除冗余数据、简化数据维度的同时保留数据关键信息的目的。降维是一种无监督学习方法，常见的降维方法主要有PCA、LDA、流形学习等。

PCA（主成分分析法）算法是将一个高维向量x，通过一个特殊的特征向量矩阵U，投影到一个低维的向量空间中，并表征为一个低维向量y的过程。在这个过程中仅仅损失了一些次要信息。从本质上讲，PCA是一种空间映射的方法，将常规正交坐标系的变量通过矩阵变换操作映射到另一个正交坐标系中，也就是将数据投射到一个低维子空间实现降维。PCA算法以方差的大小衡量信息的量级，认为方差正比越高提供的信息量越大，其基本思想是通过线性变换尽可能地保留大方差的数据。PCA算法因其优秀的降维表现，简单、无须调参的特点而被成功应用于众多领域。

LDA（线性判别分析）算法是一种将高维的数据样本映射到低维向量空间，以达到抽取分类信息和压缩特征空间维数的方法。LDA在映射后能够保证数据样本在新的子空间内有最大的类间距离和最小的类内距离，即数据在该空间中的可分离性达到最佳。从几何角度看，PCA和LDA都是将数据投影到新的正交坐标轴上的方法，区别在于它们的降维目标不同，PCA是将样本投射到方差最大的相互正交方向上，以此保留最多的样本信息。LDA希望投影后类内方差最小，类间方差最大。

PCA和LDA只适用于线性样本数据，想要解决非线性样本数据降维可以采用流形学习的方法。流形学习理论认为高维数据实际是以一种低维的流形结构嵌入高维的空间中。由于数据内部特征的限制，一些高维数据会产生维度上的冗余，实际上只需要比较低的维度就能够完整表达那些数据。流形学习的目的是将高维数据映射回低维空间，以便更清楚地解释其本质，不同的距离计算方法形成了不同的流形学习算法。

（七）k均值算法

k均值算法（k-means）算法属于无监督学习中的聚类，首先选择k个初始点作为质心，然后为每个样本点找距其最近的质心，并将其分配给该质心所对应的簇，然后将每个簇的质心更新为该簇所有点的平均值，质心位置改变了，对样本点的划分也要随之改变，如此不断迭代，直到算法收敛到对所有样本点的分类都不再改变。

k均值算法可以通过SSE（误差平方和）来度量聚类效果，SSE值越小说明数据点越接近它们对应的质心，因为k由用户定义，最初难以知道设置为多少合适，故k均值算法容易收敛到局部最小值而不是全局最小值，可以采用这样的后处理来提高该算法的聚类质量：首先将SSE值最大的簇拆分成两个簇，具体方法可以是对该簇内的数据运行k均值算法，同时将k设置为2，为了保证总的簇数不变，我们还要将两个质心合并，我们可以选择合并两个最近的质心，或者合并两个使得SSE增幅最小的质心。

优点：

1.算法简单，容易实现，算法速度快

2.对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O(nkt)，趋于线性

3.当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好

缺点：

1.算法容易收敛到的是局部最优，因而对初始质心的选取敏感

2.选择能达到目标函数最优的k值是非常困难的

3.只有在凸形簇上效果较好

适用场景：

可适用于文档分类、客户分类、保险欺诈、犯罪分析等场景。

（八）Apriori及FP-growth

Apriori算法是一种挖掘关联规则的算法，用于挖掘其内含的、未知的却又实际存在的数据关系，其核心步骤是找出频繁项集，根据频繁项集生产关联规则：

该算法首先根据所给数据构建只有一个元素的项集，然后判断每个项集的支持度，去掉支持度不足的项集，再组合一元素项集构建二元素项集，再去掉支持度不足的项集，如此不断迭代，直到不存在拥有更多元素的频繁项集。之后是发现关联规则，关联规则产生于频繁项集，一个频繁项集可以生成多条可能的关联规则，我们利用分级法，先生成右边只有一个元素的关联规则，然后判断每条规则的可信度，去掉可信度不足的规则，再将可信度足够的规则拆分子集，生成右边有两个元素的关联规则，再去掉可信度不足的规则，如此不断迭代，直到不存在右侧有更多元素的关联规则

该算法的优点是简单、易理解、数据要求低，实现了在大数据集上可行的关联规则提取，应用于消费市场价格分析，入侵检测，移动通信等领域；缺点是在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素，在每次计算项集的支持度时，都对数据集中的全部记录进行了一遍扫描比较，数据集大时I/O开销大。

FP-growth（Frequent Pattern Tree, 频繁模式树）算法是将数据集存储在一个特定的称作FP树的结构之后发现的频繁项集或频繁项对，即常在一块出现的元素项的集合FP树。该算法比Apriori算法效率更高、速度更快，在整个算法执行过程中，只需遍历数据集两次，基本过程是：构建FP树，从FP数中挖掘频繁项集。该算法常被用来做输入联想，比如在百度搜索框里输入关键字，就会联想出相关内容。

（九）神经网络

人工神经网络由生物学中的神经元结构演化而来，神经元模型是神经网络的基本组成，它是一个包含输入、输出与计算功能的模型，每个神经元接受相邻神经元传递过来的输入信号，这些输入信号通过带权重的连接进行传递，将神经元接收到的总输入与神经元的阈值进行比较，最后通过“激活函数”处理产生神经元的输出。

感知机学习算法是一种适用于二分类的机器学习算法，由两层神经元组成，输入层接收外界信号后传递给输出层，输出层是神经元模型，它的工作原理与二值神经元模型MP非常类似，给每个属性制定一个权重w，对属性和权重的乘积求和，将这个值和阈值进行比较，可以判定正负样本。这个过程就是不断调整参数，找到决策分界的过程。

因为感知机没有办法解决异或问题，所以需要搭建多层神经网络增加适用性，多层神经网络比感知机增加了一个隐藏层，输入层只用于输入，隐藏层承载运算，最后由输出层汇总后输出。误差逆传播算法是用于解决多层神经网络中求解参数的计算量问题的方法，在算法中增加了一个误差项，这个误差项表示每一层的预期值与实际值之间的差距，逆向往前计算每一层的误差的过程，称为逆向过程。BP神经网络有更强的适应性及自主学习能力，能够逼近任何非线性函数。但同时，BP神经网络的黑盒性以及耗费成本较高等问题也是让多层神经网络在实际应用中受限的主要原因。

RBF（Radial Basis Function，径向基函数）神经网络是一种改良型的BP神经网络，在结构上RBF神经网络从输入空间到隐藏层空间的变换是非线性的，而从隐藏层空间到输出层空间的变换是线性的，RBF最大的特点在与每次运算时不需要更新网络中的所有参数，只需要更新相关联的参数。通过这种改变能极大地提升神经网络的运算效率，因此拥有更广阔的应用前景。

（十）深度学习（CNN、RNN、GAN）

典型的深度学习模型就是很深层的神经网络，增加隐层数不仅增加了拥有激活函数的神经元数目，还增加了激活函数嵌套的层数，使得模型复杂度有效增加，多隐层神经网络难以直接用BP等经典算法进行训练，因为误差在多隐层内逆传播时，往往会“发散”(diverge)而不能收敛到稳定状态。

无监督逐层训练是多隐层网络训练的有效手段，其基本思想是每次训练一层隐节点，训练时将上一层隐节点的输出作为输入，而本层隐节点的输出作为下一层隐节点的输入，这称为“预训练”；在预训练全部完成后，再对整个网络进行“微调”训练，如深度信念网络DBN中，每层都是一个受限玻尔兹曼机RBM，整个网络可视为若干个RBM堆叠而成。这种“预训练+微调”的做法可视为将大量参数分组，对每组先找到局部看来比较好的设置，然后再基于这些局部较优的结果联合起来进行全局寻优，这样就利用了模型大量参数所提供的自由度的同时，有效节省了训练开销。另一种节省训练开销的策略是“权共享”，即让一组神经元使用相同的连接权，如CNN。

CNN（卷积神经网络）可以自动从图像中学习和提取有效特征，一个典型的卷积神经网络结构为一系列阶段的组合，其中包括若干个卷积层、激活层、池化层以及全连接层。卷积层的目的是降低数据维度以及提取特征，激活层是为了将卷积层的输出结果变成非线性映射。通过非线性的激活函数处理，可以模拟任何函数，从而增强网络的表现力。池化层夹在连续的卷积层中间，用于压缩数据和参数的数量，也就是压缩图像的大小。最后的全连接层相当于一个多层感知机，在整个神经网络中起到分类器的作用。前面几层都是为了得到更优质的特征，最后的全连接层实现图像的分类。

RNN（循环神经网络）是一类用于处理序列数据的神经网络，广泛应用于自然语言处理中的语音识别、手写识别以及机器翻译等方面。对于RNN来说，隐藏层之间的节点有连接，且隐藏层的输入不仅包括输入层的输出，还包括上一时刻隐藏层的输出。当前样本的结果能够影响下一个样本的结果，甚至影响后面很多个样本的结果，从而使最终结果反映出序列的特征，这是RNN挖掘数据关联的一般思路。时间序列反向传播（BPTT）算法是我们最常用的训练RNN的方法，BPTT核心思想与BP相同，沿着需要优化的参数的负梯度方向不断寻找更优的点直至收敛，其针对时间序列数据做了特殊的改造。BPTT求解的前向传播的过程是依次按照时间的顺序计算，反向传播的过程是从最后的时间将积累的残差传递回来，最后使用梯度下降法求解，目标是使用梯度下降法迭代优化损失函数使其达到最小值。

RNN算法容易出现梯度消失的现象，导致无法处理长序列数据，因此在实际应用中，通常使用长短时记忆网络（LSTM）算法处理长序列数据。LSTM的设计初衷是为了解决神经网络中的长期依赖问题，让记住长期信息成为神经网络的默认行为。LSTM使用的解决方法是设计三个“门”来控制是丢弃还是增加信息，从而实现遗忘或记忆。遗忘门，负责控制长期状态的结果；输入门，负责将即时状态的结果输入至长期状态中；输出门，负责控制是否把长期状态作为当前的LSTM的输出。

GAN（生成对抗网络）是一种比较特殊的深度学习模型，由生成模型和判别模型两部分组成。其中生成模型用于生成接近原有样本的数据，判别模型用于判断它看到的数据到底是原来样本还是通过生成模型制造出来的数据，因为生成模型和判别模型通常都使用深度神经网络，因此他们也被称为生成网络及判别网络。GAN的目的是生成逼真的“假样本”。生成器专门用于生成看似真实的样本，判别器学习分辨生成样本和真实样本，两个网络相互博弈。模型训练时，首先我们为生成器输入一个随机噪声z，通过生成器得到生成数据G(z)。接下来将这些生成数据输入判别器中，由判别器D根据真实数据x与生成数据G(z)的数据分布情况输出一个概率值，表示D对于输入是真实数据还是生成数据的置信度，以此判断G的产生数据的性能好坏。生成器利用判别器的反馈信息来调整网络的参数，使生成数据获得更高的分数。经过一定量的交替迭代训练后，当最终判别器D不能区分真实数据x和生成数据G(z)时，就认为生成器G达到了最优。

相比于传统机器算法，GAN有三方面的优势：首先GAN模型的表现效果更好；第二GAN框架可以训练任何一种生成器网络；第三GAN适用于一个变量的随机发生概率不可计算的情况。由于这些优点，GAN目前已经应用在图像处理领域的众多场景中，例如提高图像分辨率、进行图像风格转换以及人脸合成等。