3.1.3 按形式及功能分类
1.回归算法
对于有监督的学习，如果数据的标签是连续值，那么此时根据样本特征对数据的预测为回归。常见的回归算法有普通最小二乘法、岭回归、LASSO、逻辑回归等。
普通最小二乘法是使残差的平方和最小，然后根据这个条件对各个参数求偏导，最后求得参数。在满足高斯马尔科夫的假设条件下，最小二乘法所得到的参数是线性无偏有效的。LASSO（Least Absolute Shrinkage and Selection Operator，最小绝对值收缩和选择算子）方法与岭回归类似，它们都是通过增加惩罚函数来判断、消除特征间的共线性。逻辑回归是一种对概率的回归，也可以用来分类，通常把回归结果大于0.5的作为一类，小于0.5的作为另一类。
2.基于实例的算法
基于实例的学习通过训练数据的样本或事例建模，这些样本或事例也被视为建模所必需的。这类模型通常会建一个样本数据库，比较新的数据和数据库里的数据，通过这种方式找到最佳匹配并做出预测。换句话说，这类算法在做预测时，一般会使用相似度准则，比对待预测的样本和原始样本之间的相似度，再做出预测。因此，基于实例的方法也被称为赢家通吃的方法（Winner-Take-All）和基于记忆的学习（Memory-Based Learning）。常用的基于实例的学习算法包括KNN、学习矢量量化算法（LVQ）、自组织映射算法（SOM）（如图3.7所示）等。
图3.7 自组织映射算法示意图
3.贝叶斯算法
贝叶斯算法是基于贝叶斯定理的一类算法。该算法用贝叶斯公式进行分类或回归，常用的算法有朴素贝叶斯算法、高斯朴素贝叶斯算法、多项式朴素贝叶斯算法、AODE算法、贝叶斯信念网络（BBN）和贝叶斯网络（BN）等。
如图3.8所示，贝叶斯分类算法利用概率统计知识进行分类，如朴素贝叶斯算法利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。为此出现了许多降低独立性假设的贝叶斯分类算法，如TAN算法，它是通过在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。
图3.8 贝叶斯算法示意图
4.决策树算法
如图3.9所示，如果我们要判断一根黄瓜的好坏，可能会根据瓜的根蒂和纹理等属性来判断。决策树算法的目标是根据数据属性的实际值，创建一个预测样本目标值的模型。训练时，树状的结构会不断分叉，直到做出最终的决策。也就是说，预测阶段模型会选择路径进行决策。决策树常被用于分类和回归。决策树一般速度快、结果准，因此也属于最受欢迎的机器学习算法之一。常用的决策树算法包括ID3、C4.5、CART、M5等。
图3.9 决策树算法示意图
5.人工神经网络/深度学习
人工神经网络是一类受生物神经网络的结构及功能启发而来的模型。它是一类常用于解决回归和分类等问题的模式匹配，不过，它实际上是一个含有成百上千种算法及各种问题变化的子集。常用的人工神经网络包括感知器神经网络、BP神经网络、径向基函数网络等。
深度学习算法是人工神经网络的升级版，深度学习与传统的神经网络的相同之处在于深度学习采用了与神经网络相似的分层结构，但深度学习能够克服神经网络训练中出现的容易过拟合、参数比较难确定、训练速度比较慢等问题。深度学习整体上是一个Layer-Wise的训练机制，而不是传统神经网络所采用的Back Propagation机制。
深度学习是充分利用廉价的计算力实现优化的算法，如图3.10所示，深度学习包括输入层、隐藏层和输出层。近年来，其得到广泛应用，尤其是在语音识别、图像识别领域。深度学习算法会搭建规模更大、结构更复杂的神经网络。很多深度学习方法都涉及半监督学习问题，这种问题的数据量一般极大，而且只有很少部分带有标签。常用的深度学习算法包括CNN、RNN、LSTM等。
图3.10 深度学习示意图
6.数据聚类算法
当对没有标签的数据进行归类时，使用的是聚类算法。这是一种无监督学习的算法，常见的有K-Means、GMM等算法。
K-Means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。K-Means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心；其次，对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；最后，重新计算每个簇的平均值。这个过程不断重复，直到各簇中心几乎不再变化。图3.11显示了对某一束花的花瓣用K-Means算法分成3个簇的示意图。
图3.11 K-Means算法示意图
K-Means算法对于每个样本的分类是非黑即白的，即每个样本只能属于其中的一类。而GMM算法在聚类的时候形成的是若干大小、参数不一的正态分布，每个样本对应每个正态分布的概率密度函数乘以相应的系数就是该样本属于该正态分布（该类）的比例。每个样本属于各类的比例之和为1。
7.集群算法
一组弱分类器，将它们集群起来，形成一个强分类器，这就是集群机器学习，如图3.12所示。比如Boosting是一种用来提高学习算法准确度的方法，这种方法通过构造一个预测函数系列，然后以一定的方式将它们组合成一个预测函数，达到把一个弱学习算法提升为强学习算法的目的。后来出现了调整权重而运作的AdaBoost算法，是Boosting家族中的一种算法，此算法解决了早期Boosting算法很多实践上的困难。AdaBoost算法在每次训练后，对训练失败的样本赋以较大的权重，也就是让学习算法在后续的学习中集中对比较难的样本进行学习，然后得到一个预测函数序列h1，…，ht，其中hj也有一定的权重，预测效果好的预测函数权重较大，反之较小。最终的预测函数H对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新示例进行判别。Boosting算法可以应用于任何的基础回归算法，无论是线性回归、神经网络，还是SVM方法，都可以有效地提高精度。
图3.12 集群算法示意图
Bagging又称为自举聚合，是与Boosting相似的技术。该技术的主要思想是给定一个弱学习算法和一个训练集，让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练例组成，初始训练例在某轮训练集中可以出现多次或根本不出现。训练之后可得到一个预测函数序列h1，…，ht，最终的预测函数H对分类问题采用投票方式，对回归问题采用简单平均。
Bagging与Boosting的区别在于Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boosting的训练集的选择不是独立的，各轮训练集的选择与前面各轮的学习结果有关，Bagging的各个预测函数没有权重，可以并行生成，而Boosting是有权重的，只能依次顺序生成；Boosting往往从一些弱的学习器开始，组合形成一个集成学习器，从而给出一个好的学习结果，而Bagging学习效果的好坏往往取决于集成学习器中每个学习器的相关性和各个学习器的学习效果。对于神经网络这类极为耗时的学习方法，Bagging可通过并行训练节省大量时间开销，如图3.13所示。
图3.13 Bagging算法示意图
8.强化学习
所谓强化学习就是智能系统从环境到行为映射的学习，以使奖励信号（强化信号）函数值最大。如图3.14所示，假设我们要预测股票未来的涨跌，有初始策略集Q，从Q中筛选策略，如果预测错了，就会得到一个负的反馈，环境会给我们一个负的奖励，告诉我们这是一个比较差的预测方式，因此我们会尝试换个策略，这样就不断地和环境进行交互尝试，最终找到一套策略，使得我们正确预测股票的涨跌（当然正确预测股票涨跌并不容易，这里的描述是一种理想的情况）。强化学习具有分数导向性，即学习的过程中要使得分最高，这种得分类似于监督学习里的标签，但是与监督学习中的标签不同的是，强化学习中的标签不是直接可以获得的，而是模型在不断的学习当中慢慢获得的，是模型自己得出的结论。然后模型再学习哪些数据能够对应上哪些标签。此类算法包括Q-Learning、Sarsa、Deep Q Network和Policy Gradients。
图3.14 强化学习示意图
9.关联规则算法
关联规则算法是从数据背后发现事物之间可能存在的关联或者联系的一种算法。规则的支持度和自信度越高，说明规则越强，关联规则挖掘就是挖掘出满足一定强度的规则。常见的算法有Apriori算法、FP-Growth算法。
Apriori算法是一种最有影响的挖掘关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
Apriori算法首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。之后使用第一步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
相比Apriori算法的固有缺陷，FP-Growth算法是一种不产生候选挖掘频繁项集的方法，它采用分而治之的策略。在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，然后将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，最后再对这些条件库分别进行挖掘，如图3.15所示。当原始数据量很大的时候，也可以结合划分的方法，使得一个FP-tree可以放入主存中。实验表明，FP-Growth对不同长度的规则都有很好的适应性，同时在效率上较Apriori算法有巨大的提高。
图3.15 FP-Growth算法示意图
10.核方法
核方法是解决非线性模式分析问题的一种有效途径，如图3.16所示为核方法示意图。其核心思想是：首先，通过某种非线性映射将原始数据嵌入合适的高维特征空间；然后，利用通用的线性学习器在这个新的空间中分析和处理模式。基于核的算法中最著名的莫过于支持向量机（SVM）了。
图3.16 核方法示意图
SVM是应用核函数把非线性问题转换成线性问题，使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题。常用的核函数有多项式核函数、径向基核函数和Sigmod核函数。
11.优化算法
优化算法，顾名思义就是求最优解的算法，又分为传统优化算法和智能优化算法。传统优化算法包括牛顿法、梯度下降（上升）法，以及规划问题中的单纯形表法、内点法等；智能优化算法包括遗传算法、蚁群算法、粒子群算法、模拟退火法等。
比如遗传算法是借鉴了进化生物学中的一些现象而发展起来的，生物在繁衍发展的过程中，会通过繁殖发生基因交叉、基因突变，适应度低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的。
遗传算法初始是一个较差解的解集种群，通过遗传交叉繁殖出下一代的解集种群。在交叉的过程中，有一定的概率发生基因突变。在下一代的解集种群中，通过适者生存的自然选择，淘汰那些较差的解（个体），只让较好的解（个体）繁殖后代，这样产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应环境。经过许多代的繁殖和自然选择后，就能得到接近真正最优解的解。
本节对算法做了一个总结和分类，接下来我们对几种经典和有特色的算法通过举例进行深入介绍。3.2节的傅里叶变换是基于数学分析的一种算法，用于对时间序列等信号进行分析，如去噪、趋势提取等；3.3节ReliefF是特征筛选算法，着重于对特征的重要性进行评价，如果说3.2节的傅里叶变换是对单一特征的分析，那么3.3节的ReliefF就是特征之间的比较；3.4节的高斯混合聚类是从概率统计的角度利用已有的特征进行聚类分析；3.5节的Chi-Merge算法则是连续数据的离散化的一种算法，是对特征的一种处理方法，为3.6节做准备；3.6节的粗糙集利用3.5节离散化后的数据进行基于规则的分类，3.6节与3.4节高斯混合聚类有一定可对比的意义，因为粗糙集是分类算法，高斯混合聚类是聚类算法，同时粗糙集基于逻辑规则，高斯混合聚类基于概率统计，两者各有千秋。