本节书摘来华章计算机《大数据算法》一书中的第1章 ，第1.2节，王宏志 编著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1.2 大数据算法
这一节我们概述大数据算法。
1.2.1 大数据上求解问题的过程
首先我们看一看在大数据上问题求解的过程。我们面对的是一个计算问题，也就是说我们要用计算机来处理一个问题。
拿到一个计算问题之后，首先需要判定这个问题是否可以用计算机进行计算，如果学习过可计算性理论，就可以了解有许多问题计算机是无法计算的，比如判断一个程序是否有死循环，或者是否存在能够杀所有病毒的软件，这些问题都是计算机解决不了的。从“可计算”的角度来看，大数据上的判定问题和普通的判定问题是一样的，也就是说，如果还是用我们今天的电子计算机模型，即图灵机模型，在小数据上不可计算的问题，在大数据上肯定也不可计算。计算模型的计算能力是一样的，只不过是算得快慢的问题。
那么，大数据上的计算问题与传统的计算问题有什么本质区别呢？
第一个不同之处是数据量，就是说处理的数据量要比传统的数据量大。第二个不同之处是有资源约束，就是说数据量可能很大，但是能真正用来处理数据的资源是有限的，这个资源包括CPU、内存、磁盘、计算所消耗的能量。第三个不同之处是对计算时间存在约束，大数据有很强的实时性，最简单的一个例子是基于无线传感网的森林防火，如果能在几秒之内自动发现有火情发生，这个信息是非常有价值的，如果三天之后才发现火情，树都烧完了，这个信息就没有价值，所以说大数据上的计算问题需要有一个时间约束，即到底需要多长时间得到计算结果才是有价值的。判定能否在给定数据量的数据上，在计算资源存在约束的条件下，在时间约束内完成计算任务，是大数据上计算的可行性问题，需要计算复杂性理论来解决，然而，当前面向大数据上的计算复杂性理论研究还刚刚开始，有大量的问题需要解决。
注意：在本书中，有的算法可能很简单，寥寥几行就结束了，然而后面的分析却长达几页。这本书花更大的精力讲授算法分析，是因为在大数据上进行算法设计的时候，要先分析清楚这个算法是否适用于大数据的情况，然后才能使用。
本书讨论的主要内容是大数据上算法的设计与分析，即设计大数据上的算法并且加以分析。
特别值得说明的一点是，对于大数据上的算法，算法分析显得尤为重要，这是为什么呢？对于小数据上的算法可以通过实验的方法来测试性能，实验可以很快得到结果，但是在大数据上，实验就不是那么简单了，经常需要成千上万的机器才能够得出结果。为了避免耗费如此高的计算成本，大数据上的算法分析就十分重要了。
经过算法设计与分析，得到了算法。接着需要用计算机语言来实现算法，得到的是一些程序模块，下一步用这些程序模块构建软件系统。这些软件系统需要相应的平台来实现，比如常说的Hadoop、SparK都是实现软件系统的平台。
上面的叙述可以归纳为图1-1，从中可以看到，大数据算法与分析在整个大数据问题求解过程中扮演着一个核心的角色，因而本书将对此重点介绍。
1.2.2 大数据算法的定义
1.大数据算法是什么
根据大数据上的计算过程可以定义大数据算法的概念，如定义1-1所示。
定义1-1(大数据算法) 在给定的资源约束下，以大数据为输入，在给定时间约束内可以计算出给定问题结果的算法。
这个定义和传统的算法有一样的地方，首先大数据算法也是一个算法，有输入有输出；而且算法必须是可行的，也必须是机械执行的计算步骤。
补充知识：算法的定义
定义A-1(计算) 可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算。
定义A-2(算法) 算法是一个满足下列条件的计算：
1) 有穷性/终止性：有限步内必须停止；
2) 确定性：每一步都是严格定义和确定的动作；
3) 可行性：每一个动作都能够被精确地机械执行；
4) 输入：有一个满足给定约束条件的输入；
5) 输出：满足给定约束条件的结果。
第一个不同之处是，大数据算法是有资源约束的，这意味着资源不是无限的，可能在100KB数据上可行的算法在100MB的数据上不可行，最常见的一个错误是内存溢出。这意味着进行大数据处理的内存资源不足，因此在大数据算法的设计过程中，资源是一个必须考虑的约束。第二个不同之处是，大数据算法以大数据为输入，而不是以传统数据的小规模为输入。第三个不同之处是，大数据算法需要在时间约束之内产生结果，因为有些情况下过了时间约束大数据会失效，有些情况下超过时间约束的计算结果没有价值。
2.大数据算法可以不是什么
有了大数据作为输入和运行时间作为约束，大数据算法和传统算法就有了明确的区别。
第一，大数据算法可以不是精确算法。因为有些情况下，能够证明对于给定的数据输入规模和资源约束，确实不可能得到精确解。
第二，大数据算法可以不是内存算法。由于数据量很大，在很多情况下，把所有数据都放在内存中几乎不可能，因为对于现在的PC来说，内存的规模在GB级，对于高档一些的并行机和服务器来说内存也就是TB级，这个规模对于许多应用中的数据量是远远不够的，必须使用外存甚至于网络存储。因此，大数据算法可以不仅仅在内存中运行。
第三，大数据算法可以不是串行算法。有的时候，单独一台计算机难以处理大规模数据，需要多台机器协同并行计算，即并行算法。一个典型的例子是Google公司中的计算，为了支持搜索引擎，Google公司需要处理大规模来自互联网的数据，因而大数据里面的很多重要概念是Google提出的，例如并行平台MapReduce。Google公司的数据规模太大，再好的机器也无法独自处理，需要用成千上万台机器构成一个机群来并行处理。
第四，大数据算法可以不是仅在电子计算机上运行的算法。有时对于某些任务而言，让计算机处理很复杂，而让人做很简单。对于这些问题，可以让人和计算机一起来做，因此就有了人和计算机协同的算法。
而传统算法分析与设计课程中的算法，主要是内存算法、精确算法、串行算法且完全在电子计算机上执行，这和本书中的大数据算法不同。
3.大数据算法不仅仅是什么
下面从大数据概念出发，澄清一些大数据算法的片面观点。
第一，大数据算法不仅仅是基于MapReduce的算法。讲到大数据算法，可能有很多人就会想到MapReduce，MapReduce上的算法确实在很多情况下适用于大数据，而且更确切说MapReduce上的算法是一类很重要的大数据算法，但是大数据算法不仅是MapReduce上的算法。
第二，大数据算法不仅仅是云计算平台上的算法。说到大数据算法，很多人可能会想到云计算，云上的算法是不是大数据算法呢？云上的算法不全是大数据算法，有的算法不是面向大数据的，例如安全性相关的算法和计算密集型算法，而且大数据算法也不都是云上的算法，大数据算法有的可以是单机的，甚至可以是手机或者传感器这种计算能力很差的设备。
第三，大数据算法不仅仅是数据分析与挖掘中的算法。分析与挖掘是大数据中比较热的概念，也确实是大数据的重要方面。之所以用得比较多，是因为其商业价值比较明显。然而，大数据的应用除了需要分析与挖掘，还有获取、清洗、查询处理、可视化等方面，这些都需要大数据算法的支持。
第四，大数据算法不仅仅是数据库中的算法。提到大数据，自然会联想到这是和数据管理密切相关的。大数据算法是否等同于数据库中的算法呢？不完全是这样，虽然数据库中的算法是大数据算法的一个重要组成部分，今天进行大数据算法研究的多是数据库和数据管理研究领域的专家，但是不全是数据库领域的。当前研究大数据算法的专家，有的研究背景是数学理论和算法理论，还有的来自机器学习和各种大数据应用的研究领域。因此大数据算法不仅仅是数据库中的算法，还有专门为大数据设计的算法。
1.2.3 大数据的特点与大数据算法
大数据的特点决定了大数据算法的设计方法。正如前面所介绍的，大数据的特点通常用四个V来描述。这四个V里面和大数据算法密切相关的，有两个V。一个是数据量(Volume)大，也就是大数据算法必须处理足够大的数据量。另一个是速度(Velocity)，速度有两方面:①大数据的更新速度很快，相应的大数据算法也必须考虑更新算法的速度；②要求算法具有实时性，因此大数据算法要考虑到运算时间。对于另外两个V，我们假设大数据算法处理的数据已经是经过预处理的，其多样性(Variety)已经被屏蔽掉了。关于价值(Value)本书也不考虑，而假设数据或算法的价值是预先知道的。
1.2.4 大数据算法的难度
要设计一个大数据算法并不容易，因为大数据具有规模大、速度快的特点。大数据算法设计的难度主要体现在四个方面。
1.访问全部数据时间过长
有的时候算法访问全部数据时间太长，应用无法接受。特别是数据量达到PB级甚至更大的时候，即使有多台机器一起访问数据，也是很困难的。在这种情况下怎么办呢？只能放弃使用全部数据这种想法，而通过部分数据得到一个还算满意的结果，这个结果不一定是精确的，可能是不怎么精确的而基本满意，这就涉及一个“时间亚线性算法”的概念，即算法的时间复杂度低于数据量，算法运行过程中需要读取的数据量小于全部数据。
2.数据难以放入内存计算
第二个问题是数据量非常大，可能无法放进内存。一个策略是把数据放到磁盘上，基于磁盘上的数据来设计算法，这就是所谓的外存算法。学过数据结构与算法的学生对于外存算法可能不陌生，一些数据结构课程里讲过的外存排序，就是比较典型的外存算法，在数据库实现课程中讲过的一趟选择算法、两趟连接算法、嵌套循环连接算法也属于外存算法。这些外存算法的特点是以磁盘块为处理单位，其衡量标准不再是简单的CPU时间，而是磁盘的I/O。另外一个处理方法是不对全部的数据进行计算，而只向内存里放入小部分数据，仅使用内存中的小部分数据，就可以得到一个有质量保证的结果，这样的算法通常叫作“空间亚线性算法”，就是说执行这一类算法所需要的空间是小于数据本身的，即“空间亚线性”。
3.单个计算机难以保存全部数据，计算需要整体数据
在一些情况下，单个计算机难以保存或者在时间约束内处理全部数据，而计算需要整体数据，在这种情况下一个办法就是采取并行处理技术，即使用多台计算机协同工作。并行处理对应的算法是并行算法，大数据处理中常见的MapReduce就是一种大数据的编程模型，Hadoop是基于MapReduce编程模型的计算平台。
4.计算机计算能力不足或知识不足
还有一种情况是计算机的计算能力不足或者说计算所需要的知识不足。例如，判断一幅图片里是不是包含猫或者狗。这时候计算机并不知道什么是猫什么是狗，如果仅仅利用计算机而没有人的知识参与计算的话，这个问题会变得非常困难，可能要从大量的标注图像里进行学习。但如果可以让人来参与，这个问题就变得简单了。更难一点的问题，比如说两个相机哪个更好，这是一个比较主观的问题，计算机是无法判断的，怎么办呢？可以让人来参与，因此，有一类算法叫作“众包算法”，相当于把计算机难以计算但人计算相对容易的任务交给人来做，有的时候，众包算法的成本更低，算得更快。
上述是大数据算法的一些难点，针对这些难点，有一系列算法提出，包括时间亚线性算法、空间亚线性算法、外存算法、并行算法、众包算法，这些就是本书的主要内容。
1.2.5 大数据算法的应用
大数据算法在大数据的应用中将扮演什么样的角色呢？我们通过下面一些例子来看看大数据算法的应用。
1.预测中的大数据算法
如何利用大数据进行预测？一种可能的方法是从多个数据源(比如社交网络、互联网等)提取和预测主题相关的数据，然后根据预测主题建立统计模型，通过训练集学习得到模型中的参数，最后基于模型和参数进行预测。其中每一个步骤都涉及大数据算法问题。在数据获取阶段，因为从社交网络或者互联网上获取的数据量很大，所以从非结构化数据(如文本)提取出关键词或者结构化数据(例如元组、键值对)需要适用于大数据的信息提取算法；在特征选择过程中，发现预测结果和哪些因素相关需要关联规则挖掘或者主成分分析算法；在参数学习阶段，需要机器学习算法，如梯度下降等，尽管传统的机器学习有相应的算法，但是这些算法复杂度通常较高，不适合处理大数据，因此需要面向大数据的新的机器学习算法来完成任务。
2.推荐中的大数据算法
当前推荐已经成为一个热门的研究分支，有大量的推荐算法提出。由于当前商品信息和用户信息数据量都很大，例如淘宝，用户和商品的数量都达到了GB级以上，基于这样大规模的数据进行推荐需要能够处理大数据的推荐算法。例如为了减少处理数据量的SVD分解，基于以前有哪些用户购买这个商品和这些用户购买哪些商品的信息构成一个矩阵，这个矩阵规模非常大，以至于在进行推荐时无法使用，因而就需要SVD分解技术对这个矩阵分解，从而将矩阵变小。而基于这样大规模的稀疏矩阵上的推荐也需要相应的大规模矩阵操作算法。
3.商业情报分析中的大数据算法
商业情报分析首先要从互联网或者企业自身的数据仓库(例如沃尔玛PB级的数据仓库)上发现与需要分析的内容密切相关的内容，继而根据这些内容分析出有价值的商业情报，这一系列操作如果利用计算机自动完成，需要算法来解决。其中涉及的问题包括文本挖掘、机器学习，涉及的大数据算法包括分类算法、聚类分析、实体识别、时间序列分析、回归分析等，这些问题在统计学和计算机科学方面都有相关的方法提出，然而面向大数据，这些方法的性能和可扩展性难以满足要求，需要设计面向大数据的分析算法。
4.科学研究中的大数据算法
科学研究中涉及大量的统计计算，如利用回复分析发现统计量之间的相关性，利用序列分析发现演化规律。例如，美国能源部支持的项目中专门有一部分给大数据算法，在其公布的指南里包含相应的研究题目，包括如何从庞大的科学数据集合中提取有用的信息，如何发现相关数据间的关系（即相关规则发现），还包括大数据上的机器学习、数据流上的实时分析，以及数据缩减、高可控的拓展性的统计分析，这些都在科学研究中扮演重要的角色。
