二、传统大数据算法
算法设计与分析是计算科学的重要主题，进行大数据计算，算法设计与分析是必不可少的步骤，可以说算法设计是大数据项目落地的关键之一。大数据算法按挖掘任务细分，主要有分类分析、聚类分析、关联分析等算法。其中分类就是按照一定的标准把数据对象划归成不同类别；聚类是在没有给定划分类的情况下根据数据信息的相似度进行数据聚集的一种方法；关联分析就是对大量的数据进行分析，从中发现满足一定支持度和可信度的数据项之间的联系规则。
（一）分类算法
1．分类算法综述
分类是大数据分析中的一个重要课题。分类的目的是学会一个分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。
2．主要分类算法介绍
主要使用的分类算法有决策树、逻辑回归、神经网络、支持向量机、朴素贝叶斯分类、判别分析、K近邻算法，等等，下面将逐一介绍。
（1）决策树
决策树方法是利用信息论中的信息增益寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点，再根据该属性字段的不同取值建立树的分支，在每个分支子集中重复建立树的下层结点和分支的一个过程。
构造决策树的具体过程为：首先寻找初始分裂，以决定哪个属性域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。量化的标准是计算每个分裂的多样性指标。其次，重复第一步，直至每个叶节点内的记录都属于同一类且增长到一棵完整的树。
常用的决策树算法有ID3、C4.5、CART算法等。这些算法主要以信息论为基础，以信息熵、信息增益率或基尼系统为衡量标准，从而实现对数据的归纳分类。
（2）逻辑回归
逻辑回归就是这样的一个过程：面对一个回归或者分类问题，建立代价函数，然后通过优化方法迭代求解出最优的模型参数，然后测试验证我们这个求解的模型的好坏。Logistic回归虽然名字里带“回归”，但是它实际上是一种分类方法，主要用于二分类问题，是一种强分类器。
Logistic回归算法基于Sigmoid函数，Sigmoid函数定义如下：1/（1+exp（-z）），其函数值域范围为（0，1），可以用来做分类器。
逻辑回归的一般步骤是：寻找h函数（即预测函数）、构造J函数（损失函数）、想办法使得J函数最小并求得回归参数（θ），参数的求解过程可以由最优化算法来完成。在最优化算法中，最常用的就是梯度上升算法，而梯度上升算法可以简化为随机梯度上升算法。
（3）神经网络
神经网络是分类技术中重要方法之一。人工神经网络是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型，在这种模型中，大量的节点（或称“神经元”）之间相互联接构成网络，即“神经网络”，以达到处理信息的目的。神经网络通常需要进行训练，训练的过程就是网络进行学习的过程。训练改变了网络节点的连接权值使其具有分类的功能，经过训练的网络就可用于对象的识别。
神经网络的优势在于：可以任意精度逼近任意函数；神经网络方法本身属于非线性模型，能够适应各种复杂的数据关系；神经网络具备很强的学习能力，使它能比很多分类算法更好地适应数据空间的变化；神经网络借鉴人脑的物理结构和机理，能够模拟人脑的某些功能，具备“智能”的特点。用于分类常见的神经网络模型包括：BP（Back Propagation）神经网络、RBF（Radical Basis Function）神经网络等。
人工神经网络作为另一种处理非线性、不确定性的有力工具，目前还存在许多局限性：首先，网络本身的黑箱式内部知识表达，使其不能利用初始经验进行学习，易于陷入局部极小值。其次，就本质而言，人工神经网络就是用静态网络处理连续时间动态系统的控制问题。这就不可避免地带来了差分模型定阶及网络规模随阶次迅速增加的复杂性问题。再次，人工神经网络的泛化能力在相当程度上决定了控制系统的鲁棒性。全局逼近的泛化能力受大量局部极值与缓慢学习速度制约，局部逼近则受存储容量与实时性的而严重限制。
（4）支持向量机
支持向量机（Support Vector Machine）是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中有许多特有的优势，并能推广应用到函数拟合等其他机器学习问题中。
支持向量机是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
支持向量机将向量映射到一个更高维的空间里，在这个空间里建有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。因此最大化几何间隔成了我们训练阶段的目标。实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去。线性不可分映射到高维空间，可能会导致维度大小高到可怕的程度，导致计算复杂。核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，避免了直接在高维空间中的复杂计算。
（5）朴素贝叶斯分类
朴素贝叶斯分类基于贝叶斯定理，假设一个属性值对给定类的影响独立于其他属性的值。设X是类标号未知的数据样本。设H为某种假定，如，数据样本X属于某特定的类C。因此我们希望确定P（H ｜X），即给定观测数据样本X，假定H成立的概率（后验概率）。
贝叶斯定理（公式）：
朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。
（6）判别分析
判别分析是一种在已知研究对象用某种方法已经分成若干类的情况下，确定新的样品属于哪一类的多元统计分析方法，其原理是利用已知对象的某些观测指标和所属类别，根据判别准则建立一个或多个判别函数，用研究对象的大量资料确定判别函数中特定系数，并计算判别指标，然后用总结出判别规则确定未知对象属于哪一类。当描述研究对象的性质特征不全或不能直接测量数据确定研究对象所属类别时，可以通过判别分析进行归类。判别分析，根据采用的判别准则的不同主要有以下几种：
①最大似然法：用于自变量均为分类变量，该方法建立在独立事件概率乘法定理的基础上，根据训练样本信息求得自变量各种组合情况下样品被封为任何一类的概率。当新样本进入时，计算它被分到每一类中去的条件概率（似然值），概率最大的那一类就是最终评定的归类。
②距离判别：其基本思想是由训练样本得出每个分类的重心坐标，然后对新样本求出它们离各个类别重心的距离远近，从而归入离得最近的类。最常用的距离是马氏距离。距离判别的特点是直观、简单，适合于对自变量均为连续变量的情况下进行分类，且它对变量的分布类型无严格要求，特别是并不严格要求总体协方差阵相等。
③Fisher判别：也称典则判别，是根据线性Fisher函数值进行判别，通常用于两种判别问题，使用此准则要求各组变量的均值有显著性差异。该方法的基本思想是投影，即将原来在R维空间的自变量组合投影到维度较低的D维空间去，然后在D维空间中再进行分类。投影的原则是使得每一类的差异尽可能小，而不同类间投影的离差尽可能大。
④Bayes判别：许多时候用户对各类别的比例分布情况有一定的先验信息，比如客户对投递广告的反应绝大多数都是无回音，如果进行判别，自然也应当是无回音的居多。此时，Bayes判别恰好适用。Bayes判别就是根据总体的先验概率，使误判的平均损失达到最小。其最大优势是可以用于多组判别问题。但是适用此方法必须满足三个假设条件，即各种变量必须服从多元正态分布、各组协方差矩阵必须相等、各组变量均值均有显著性差异。
（7）K近邻算法
K近邻法是有监督学习方法，原理很简单，假设我们有一堆分好类的样本数据，分好类表示每个样本都一个对应的已知类标签，当来一个测试样本要我们判断它的类别时，就分别计算到每个样本的距离，然后选取离测试样本最近的前K个样本的标签累计投票，得票数最多的那个标签就为测试样本的标签。
K近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K个近邻中出现最多的那个类别。K近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K个训练样本点为止，并且把测试样本点x归为这最近的K个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。
在大样本集和高维样本分类中（如文本分类），KNN方法的缺陷凸显。表现在以下几个方面：KNN分类算法是懒散的分类算法，对于分类所需的计算均推迟至分类进行，故在其分类器中存储有大量的样本向量。在未知类别样本需要分类时，在计算所存储样本和未知类别样本的距离时，高维样本或大样本集所需要的时间和空间的复杂度均较高。
（二）聚类算法
1．聚类算法综述
聚类算法是多元统计分析中研究“物以类聚”的一种方法，用于对事物的类别面貌尚不清楚，甚至在事前连总共有几类都不能确定的情况下进行分类的场合。
聚类算法把分类对象按一定规则分成组或类，这些组或类不是事先给定的而是根据数据特征而定的，它同分类的根本区别在于：分类是开始知道所根据的特征，而聚类是要准确地找到数据特征，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。聚类也可作为特征和分类算法的预处理步骤，其应用范围涉及商务、生物、地理、WEB文档分类、仿真等诸多领域。
2．数据的相似性度量
聚类算法按照样本点之间的亲疏远近程度进行分类。刻画聚类样本点之间的亲疏远近程度主要的方法是利用距离度量的方法，常用的距离度量方法有欧几里德距离、余弦距离和马氏距离等。
3．主要聚类方法
目前聚类算法主要分为基于层次的聚类方法和基于划分的聚类方法。
图3 聚类算法概述——层次法示例
（1）基于层次的聚类方法
层次聚类算法，它是通过将数据组织为若干组并形成一个相应的树来进行聚类的。根据层次是自底向上还是自顶而下形成，层次聚类算法可以进一步分为凝聚型的聚类算法和分裂型的聚类算法。两种基本的层次聚类方法。
凝聚的层次聚类（AGNES算法）是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者达到某个终结条件。大部分的层次聚类方法都属于这一类，它们在簇间的相似度的定义有点不一样。
分裂的层次聚类（DIANA算法）是一种自顶向下的策略，它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直到满足其他的一个终结条件，例如满足了某个期望的簇数目，又或者两个最近的簇之间的距离达到了阈值。
（2）基于划分的聚类方法
给定一个数据库包含Np 个数据对象以及数目K的即将生成的簇，一个划分类的算法将对象分为K个划分，其中，这里的每个划分分别代表一个簇，并且K < = Np。其中的K需要人为指定。它一般从一个初始划分开始，然后通过重复的控制策略，使某个准则函数最优化。因此，它可以被看作一个优化问题，而优化问题往往是NP难问题。基于划分的聚类方法的优缺点跟层次的聚类方法的优缺点刚刚相反，层次聚类算法的优点恰恰是划分聚类方法的缺点，反之亦然。根据它们之间的优缺点，实践中往往会更趋向于使用划分的聚类方法。
基于划分的聚类算法有许多，下面介绍几种常见的基于划分的聚类算法。
图4 聚类算法概述——划分法示例
①K - means
k - means算法是最为经典的基于划分的聚类方法，是十大经典大数据分析算法之一。k - means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近它们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
该算法的最大优势在于简洁和快速，对于处理大数据集，该算法是相对可伸缩和高效率的。算法的缺点是簇的数目必须人为的指定，并且对初值敏感，对于不同的初值，可能会导致不同结果，而且不适合于发现非凸面形状的簇或者大小差别很大的簇，它对于“噪声”和孤立点数据是敏感的。该算法的关键在于初始中心的选择和距离公式。
②模糊C均值算法
模糊聚类算法作为无监督机器学习的主要技术之一，是用模糊理论对重要数据分析和建模的方法，建立了样本类属的不确定性描述，能比较客观地反映现实世界，它已经有效地应用在大规模数据分析、大数据分析、矢量量化、图像分割、模式识别等领域，具有重要的理论与实际应用价值，随着应用的深入发展，模糊聚类算法的研究不断丰富。在众多模糊聚类算法中，模糊C -均值（FCM）算法应用最广泛且较成功，它通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对样本数据进行分类的目的。它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进，普通C均值算法对于数据的划分是硬性的，而FCM则是一种柔性的模糊划分。
所以，该算法的隶属函数是一个软隶属函数，即一个数据点可能属于多个簇，而它的权重是一个恒定的常数。模糊C均值算法可以很好地处理临界数据点，它和K - means算法一样，需要人为的指定簇的数目。该算法的缺点是可能会产生重合聚类，需要人为指定簇的个数，收敛于局部最优以及初始条件对聚类结果影响很大。
③EM算法
EM（Expectation - Maximization Algorithm）最大期望算法是在概率模型中寻找参数最大似然估计或者最大后验估计算法，其中概率模型依赖于无法观测的隐藏变量。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。
EM是一个软隶属函数而且权重是一个常数。EM算法的特点有它会收敛到局部极值，但不保证收敛到全局最优。而且对初值很敏感，通常需要一个好的、快速的初始化过程。EM算法适应于缺失数据不太多以及数据维数低时，因为如果数据集的维数太高的话，E步的计算很费时。最大期望经常用在机器学习和计算机视觉的数据聚类领域。
④KHM算法
KHM（The K-Harmonic Means Algorithm）算法是基于中心的迭代过程，它采用所有数据点到每个聚类中心的和平均值的和作为目标函数。KHM算法的权重是个变量，它把距离中心点远的数据点赋以高的权重，这样可以让质心能够很好的覆盖整个数据集。KHM算法对初始值不敏感，适合处理大数据集，然而KHM算法容易陷入局部最优及簇个数需要预先指定的问题。综合上来说它胜过K-means、FCM和EM算法。
（3）非迭代的划分的聚类方法
另外的一种聚类算法就是非迭代的划分的聚类方法，最常用的非迭代的算法是MacQueen的K - means算法。该算法的思想是，给定一个数据集，找到指定数量的聚类中心，然后把数据集聚类到相应的簇。该算法对初始值敏感，为了解决这个问题，可以打乱数据集中数据点的顺序。一般情况下来说，迭代的算法要比非迭代的算法要高效的多。
4．其他的聚类方法
（1）最近邻聚类算法
最近邻聚类算法（Nearest Neighbor Clustering Algorithm）是一个用于处理多密度数据集的聚类算法，其主要思想可概括为：对于数据集中每个点，找出距离其最近的K个邻近点，形成一个集合。然后考虑数据集中的任意两个点，若对应于这两个对的K个邻近点集合交集部分的点数超过一个阈值，则将这两个点归于一类。SNN算法的优点是可以对不同密度和形状的数据集进行聚类，能处理高维数据集和自动识别簇的数目。缺点是在多密度聚类和处理孤立点或噪声方面SNN算法精度都不高，并且该算法对参数是敏感的。
（2）谱聚类
谱聚类算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵，并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLSI设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。谱聚类算法建立在谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
（3）MeanShift算法
MeanShift（均值漂移）是一种非参数概率密度估计的方法，一种最优的寻找概率密度极大值的梯度上升法，在解决计算机视觉底层过程中表现出了良好的鲁棒性和较高的处理速度。MeanShift算法一般指的是一个迭代的步骤，即先算出当前点的漂移均值，移动该点到其漂移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。
5．各类聚类算法比较
基于上述的分析，下面对常用聚类算法的性能从可伸缩性、发现聚类的形状、对“噪声”的敏感性、对数据输入顺序的敏感性、高维性和是否是硬聚类六个方面进行比较，如表2所示。
表2 聚类算法比较
（三）关联分析
1．关联分析综述
所谓关联，反映的是一个事件和其他事件之间依赖或关联的知识。关联规则挖掘是大数据分析中最活跃的研究方法之一。最早是由Agrawal等人提出的称为Apriori的关联规则挖掘算法。最初提出的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频繁项集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。
关联分析几个基本概念：
（1）关联规则A - > B的支持度support = P（AB），指事件A与事件B同时发生的概率。
（2）关联规则A - > B的置信度confidence = P（B ｜ A）= P（AB）/ P（A），指发生事件A的基础上发生事件B的概率。
（3）如果事件A中包含k个元素，那么称这个事件A为k项集，并且把满足最小支持度阈值的事件称为频繁k项集。
2．Apriori关联规则算法介绍
Apriori算法过程分为两个步骤：第一步通过迭代，找出事务数据库所有的频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小置信度的规则。具体做法是：首先，找出频繁“1项集”的集合，该集合记作L1；然后利用L1来产生候选项集C2，再对C2中的项进行判定挖掘出L2，即频繁“2项集”；不断如此循环下去，直到不能找到频繁“k项集”为止。其中每找出一层Lk都需要进行一次数据库扫描。
经典的关联规则数据挖掘算法Apriori算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。
（四）总结
上述的数据分析算法属于传统的数据挖掘方法，在实际应用中都取得了非常好的效果，例如逻辑回归在消费者信用评分中的应用是金融领域数据分析最成功的应用案例之一。在当今大数据时代，这些传统的数据挖掘算法也面临数据量和运算效率的挑战，因为传统的数据挖掘都是假设数据在内存中存储，在面对大数据时，这些算法存在着单位时间内处理量小、面对大量的数据时处理时间较长、难以达到预期性能等缺陷。目前这些算法也在更新换代，逐步完善来适应大数据时代的要求，例如开发K - means聚类算法的并行策略等。