牛津通识读本：大数据 [7]
再以一张孩子在海边吃冰激凌的黑白照片为例。理想情况下，当我们压缩该图像时，我们希望照片中的孩子那部分保持清晰，为了实现这一点，我们可以牺牲背景细节的清晰度。美国加州大学洛杉矶分校亨利·萨穆利工程与应用科学学院的研究人42员开发了一种被称为数据扭曲压缩的新方法，使上述想法成为现实。对此细节感兴趣的读者请参阅本书末尾的“进一步阅读”部分。
我们已经看到了分布式数据文件系统如何用于存储大数据。由于存储问题持续得到改善，现在大数据可用于回答以往我们无法回答的问题。正如下面我们将在第四章中所看到的那样，一种被称为映射归约的算法，可用于处理海杜普分布式文件43系统中存储的数据。
第四章 大数据分析法
在讨论了如何收集和存储大数据之后，我们现在来看一看从数据中发现有用信息的技术，例如客户偏好或流行病传播速度等。随着数据集规模的增加，大数据分析法（相关技术的统称）的变化也日新月异，经典的统计方法为这种新范式提供了广阔的空间。
第三章介绍的海杜普提供了一种通过分布式文件系统存储大数据的方法。我们下面以映射归约（MapReduce）为例，来看一下大数据分析法。映射归约是一种分布式数据处理系统，它是海杜普生态系统核心功能的一部分。亚马逊、谷歌、脸书和许多其他组织，都在使用海杜普来存储和处理它们的数据。
映射归约
处理大数据的一种流行方法是将其分成小块，然后对它们分别进行处理。这基本上就是映射归约的工作方式。它将所需的计算或查询工作分配到众多计算机上来完成。通过去繁就简的例子来理解映射归约的工作方式非常值得尝试，实际情况也确实需要我们这样做，因为当我们手工操作时也需要依靠极为44简化的示例，但它仍可演示用于大数据的分析过程。通常情况下，会有成千上万的处理器用来并行处理海量数据，可贵的是，该过程具有可伸缩性。这种想法不仅非常巧妙，且易于遵循。
映射归约分析模型由多个部分组成：映射（map）组件、混洗（shuffle）过程和归约（reduce）组件。映射组件由用户编写，并对我们感兴趣的数据进行排序。混洗过程是映射归约的核心，它根据键值对数据进行分组。最后是归约组件，它也由用户提供，通过对组值的合并得到最终的结果，并将其发送到海杜普分布式文件系统（HDFS）进行存储。
假设我们在海杜普分布式文件系统中存储了以下键值对文件，并具有下列各项的统计信息：麻疹、寨卡病毒、肺结核和埃博拉病毒。疾病是关键字（键名），值表示每种疾病的病例数。我们感兴趣的其实是各种疾病的总数量。
文件1：
麻疹，3
寨卡，2；肺结核，1；麻疹，1
寨卡，3；埃博拉，2
文件2：
麻疹，4
寨卡，2；肺结核，1
文件3：
麻疹，3；寨卡，2
麻疹，4；寨卡，1；埃博拉，3
映射器可以让我们逐行分别读取各个输入文件，如图11所示。在读取数据之后，映射器将为每个不同的行返回键值对。45
图11 映射功能
在对文件进行分片（split）并获取相应的键值对之后，算法的下一步是由主程序对键值进行排序和混洗。上述疾病将会按字母顺序排序，其结果被存入适当的文件以供归约程序调用，如图12所示。
如图12所示，接下来，归约组件将映射和混洗阶段的结果组合起来，并将其（每种疾病）发送到各自独立的文件中。随后，算法中的归约步骤汇总各单位数据，并将汇总结果作为键值对发送至最终输出文件，该文件可以在分布式文件系统（DFS）中保存。
以上只是一个非常小的示例，实际上，映射归约方法可以帮助我们分析规模宏大的数据。例如，通过“爬网侠”数据平台，46一家非营利机构提供的免费互联网副本，我们可以使用映射归约编写的计算机程序来计算每个单词在互联网上出现的频次。
图12 混洗和归约功能
布隆过滤器
大数据挖掘的一种特别有用的方法是布隆过滤器，它是20世纪70年代开发的一种基于概率论的技术。正如我们将要看到的那样，布隆过滤器特别适合于那些将存储作为主要考量、数据可存为列表的应用程序。
布隆过滤器背后的基本思想是，基于数据元素列表来构建一个系统，用以回答“列表中是否有X？”的问题。对于大数据集来说，搜索整个集合可能会费时太多而不具有实用性，因此布隆过滤器被当成了新的解决方案。该方法基于概率，并非100%准确，算法对某个元素是否属于列表进行判断，虽然会存在一定的误差，但它确实是一种从数据中提取有用知识的快速、可靠和47利于有效存储的好方法。
布隆过滤器应用广泛。例如，它可用于检查特定的网络地址是否链接到恶意网站。在这种情况下，布隆过滤器充当的是已知恶意链接黑名单的角色，我们可以根据该黑名单快速准确地检查你刚刚单击的网络地址（URL）是否安全。新发现的恶意网址会被不断添加到黑名单中。由于现在有超过十亿个网站，而且每天都会有更多的网站诞生，因此跟踪恶意网站就成了一个应对大数据挑战的问题。
恶意电子邮件是类似的案例，它既可能是垃圾邮件，也可能包含恶意代码而具有钓鱼的企图。布隆过滤器为我们提供了一种甄别每个电子邮件地址的快速方法，如果发现地址存疑，就会及时发出警告。每个地址大约占用20个字节，对数目庞大的地址逐个存储和检查由于非常耗时而丧失实用价值，因为我们需要在极短的时间完成存储和检验的过程。通过使用布隆过滤器，可以显著减少存储的数据量。下面我们来构建一个小型的布隆过滤器，以了解它的工作原理。
假设我们有以下要标记为恶意电子邮件地址的列表：〈aaa@aaaa.com〉；〈bbb@nnnn.com〉；〈ccc@ff.com〉；〈dd@ggg. com〉。为了构建布隆过滤器，首先假定当前计算机上有10比特可用的内存。它就是所谓的位数组，起始值为空。对于一个位来说，只有两个状态，通常用0和1表示。因此，我们首先将位数组中的所有值都设置为0（表示空），而那些值为1的位，则意味着与其相关联的索引至少被分配过一次，这一点我们马上就能看到。
位数组的大小是固定的，无论我们添加多少内容，其大小都48将保持不变。我们给位数组建立索引，如图13所示。
图13 10位数组
现在，我们需要引入哈希函数。哈希函数是一种算法，旨在将给定列表中的每个元素映射到数组中的某个位置。通过此举，我们现在仅需要将映射的位置存储在数组中，而不是电子邮件地址本身，这样存储空间就得以减少。
出于演示的目的，我们只展示了使用2个哈希函数的情形，但通常情况下我们会使用17个或18个函数，所涉及的数组也会大很多。由于这些函数被设计为均匀地映射，因此每次将哈希算法应用于不同的地址时，每个索引都有相等的机会被映射到。
那么，首先我们使用哈希算法将每个电子邮件地址分配给数组中的某个索引。
如果要将“aaa@aaaa.com”添加到数组中，首先要传递给哈希函数1，该函数将返回数组索引或位置值。例如，假设哈希函数1返回了索引3，被再次应用于“aaa@aaaa.com”的哈希函数2返回了索引4，那么这两个位置的存储位值都会变成1。如果某个设置的值已经为1，则保留原值，不作改动。同理，添加“bbb@nnnn.com”可能会导致位置2和7被占用或位值被设置为1；而“ccc@ff.com”可能会返回位置4和7。最后，假定哈希函数应用于“dd@ggg.com”并返回了位置2和6。图14是上述结果的汇总。
实际的布隆过滤器数组如图15所示，被占用位置的值设置49为1。
图14 哈希函数结果汇总
图15 侦测恶意电子邮件地址的布隆过滤器
那么，我们如何能将此数组作为布隆过滤器使用呢？假设现在我们收到了一封电子邮件，并且希望检查该电邮地址是否在恶意电子邮件地址列表中。假定该地址映射到位置2和7，那么它们的值都是1。由于返回的所有值都等于1，因此它很可能在列表中，因此也就很可能是恶意邮件。我们不能肯定地说它一定在该列表中，因为位置2和7也可能是其他地址的映射结果，并且索引也可能被多次使用。正因为如此，对元素所进行的列表登录与否的侦测还具有误报的概率。但是，如果任何一个哈希函数都返回了值为0的数组索引（别忘了，通常会有17个或18个函数），那么我们就能肯定该地址不在列表中。
虽然其中涉及的数学知识很复杂，但是我们可以看出，数组越大，未被占用的空间就越多，因而误报的次数或错误匹配的机会就越少。显然，数组的大小由所使用的键及哈希函数的数量50来决定，但无论如何，它必须有足够大的数量以确保有充足的未被占用的空间，从而能使过滤器有效运行，并最大程度地减少误报的次数。
布隆过滤器反应速度很快，它可以非常有效地侦测欺诈性信用卡交易。过滤器会检查特定项目是否属于给定的列表或集合，异常交易会被标记为常规交易列表之外的行为。例如，如果你从未使用信用卡购买过登山装备，则布隆过滤器就会将购买攀岩绳的行为标记为“可疑”。另一方面，如果你确实购买过登山装备，则布隆过滤器就会将此次购买识别为“可接受”。当然事实也未必尽然，出错的概率依然存在。
布隆过滤器也可用于过滤垃圾邮件。垃圾邮件过滤器给我们提供了一个很好的范例，因为我们并不知道确切的所要查找的内容。通常情况下，我们寻找的只是模式，因此如果我们希望将包含“mouse”一词的电子邮件均视为垃圾邮件，那么我们同时就希望将包含诸如“m0use”和“mou$e”之类变体的邮件也当作垃圾邮件。事实上，我们希望将包含该词所有可能的可辨别变体的邮件都识别为垃圾邮件。过滤与给定单词不匹配的所有内容是非常容易的，因此我们将只允许“mouse”通过过滤器。
布隆过滤器还可用于提升网络查询结果排名算法的速度，这是致力于网站推广的人士颇为感兴趣的话题。
佩奇排名
当我们使用谷歌搜索时，返回的网站会依据其与搜索词的相关性进行排名。谷歌主要通过一种被称为“佩奇排名”（PageRank）的算法来实现排序。人们普遍认为，这个算法是以谷歌的创始人之一拉里·佩奇的姓氏来命名的。他与公司的联合创始人谢尔盖·布