数据工程师必掌握的算法：蓄水池算法

nemon

　　引言：众所周知，想要面试一个统计学家和软件工程师的合体——数据工程师——是件很难的事情。我在面试中常使用的方法是：提出即需要算法设计，又需要一些概率论知识的问题，来考察面试者的功底。下面就是在硅谷非常流行的例子：


　　“给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。”


　　当面对这样一个问题的时候，我们首先应该做的是：镇静。你的面试官并没有玩你，相反他可能特别想雇你。他可能正在为无尽的分析请求烦恼，他的 ETL 流水线已经不在工作，已有的机器学习模型也不再适合。他正想要你这样一个聪明人进来帮忙，他希望你答出来。


　　第二件要做的事情是：不要在没有深入思考的情况下盲目作答。假设你的面试官读过 Daniel Tunkelang 的关于数据工程师的面试建议，那么这个面试题很可能就是他工作中实际遇到的问题。所以如果像下面一样随便回答，很可能会令你的面试官失望。


　　“我会首先将输入存到一个列表中，统计出数据流中数据的个数，在读取结束之后随机选取一个”（大哥， 你没看见题目已经说了，数据流长度很大或者未知么，不怕你的内存装不下？）


　　第三件要做的事情是：从小例子开始分析。大部分的人都更容易解决具体问题（而不是抽象问题），最开始你设计的小例子可能和最后的问题之间相去甚远，但是却能启发你对问题的理解，给你灵感。


　　蓄水池算法


　　如前面所说，对这个问题我们首先从最简单的例子出发：数据流只有一个数据。我们接收数据，发现数据流结束了，直接返回该数据，该数据返回的概率为1。看来很简单，那么我们试试难一点的情况：假设数据流里有两个数据。


　　我们读到了第一个数据，这次我们不能直接返回该数据，因为数据流没有结束。我们继续读取第二个数据，发现数据流结束了。因此我们只要保证以相同的概率返回第一个或者第二个数据就可以满足题目要求。因此我们生成一个 0 到 1 的随机数R,如果R小于 0.5 我们就返回第一个数据，如果R大于 0.5，返回第二个数据。


　　接着我们继续分析有三个数据的数据流的情况。为了方便，我们按顺序给流中的数据命名为1、2、3。我们陆续收到了数据1、2 和前面的例子一样，我们只能保存一个数据，所以必须淘汰 1 和 2 中的一个。应该如何淘汰呢？不妨和上面例子一样，我们按照二分之一的概率淘汰一个，例如我们淘汰了 1. 继续读取流中的数据3，发现数据流结束了，我们知道在长度为 3 的数据流中，如果返回数据 3 的概率为1/3 那么才有可能保证选择的正确性。也就是说，目前我们手里有1,3 两个数据，我们通过一次随机选择，以1/3 的概率留下数据3，以2/3 的概率留下数据 1. 那么数据 1 被最终留下的概率是多少呢？


数据 1 被留下：（1/2）*(2/3) = 1/3
数据 2 被留下概率：（1/2）*(2/3) = 1/3
数据 3 被留下概率：1/3
　　这个方法可以满足题目要求，所有数据被留下返回的概率一样！


　　因此，我们做一下推论：假设当前正要读取第n个数据，则我们以1/n的概率留下该数据，否则留下前n-1 个数据中的一个。以这种方法选择，所有数据流中数据被选择的概率一样。简短的证明：假设n-1 时候成立，即前n-1 个数据被返回的概率都是1/n-1,当前正在读取第n个数据，以1/n的概率返回它。那么前n-1 个数据中数据被返回的概率为：(1/(n-1))*((n-1)/n)= 1/n，假设成立。


　　这就是所谓的蓄水池抽样算法。它在分析一些大数据集的时候非常有用。你可以在这里找到 Greg 写的关于蓄水池抽样的算法介绍。本文后面会介绍一下在 Cloudera ML 中使用的两种：分布式蓄水池抽样和加权分布式蓄水池抽样。


　　（注：Cloudera ML 是基于 hadoop 的数据分析和挖掘开源项目）


　　蓄水池抽样在 Cloudera ML 上的应用


　　分布式蓄水池抽样是 Greg 讨论的第一种算法。可以从前面的讨论中发现，基本的蓄水池抽样要求对数据流进行顺序读取。要进行容量为k的分布式蓄水池抽样（前面讨论的容量都为1）我们使用 mapreduce 模拟 sql 中的 ORDER BY RAND (随机抽取)。对于集合中的每一个元素，都产生一个0-1 的随机数，之后选取随机值最大的前k个元素。这种方法在对大数据集进行分层抽样的时候非常管用。这里每一个分层都都是一些分类变量如性别，年龄，地理信息等的组合。注意如果输入的数据集分布极端的不均匀，那么抽样可能不能覆盖到所有的层级。为了对每种分类的组合进行抽样，cloudera ML 提供了 sample 命令，它可以操作纯文本或者 hive 中的表。


　　第二个算法更加好玩：加权分布式蓄水池抽样。这里集合中的数据是有权重的，算法希望数据被抽样选中的概率和该数据的权重成比例。实际上这个问题之前并不一定有解，直到 2005 年 pavlos efraimidis 和 paul spirakis 的论文《weighted random sampling with a reservoir》。他们的解法既简单又优雅，基本思想和上面的分布式蓄水池抽样一致：对于每个数据计算一个0-1 的值R，并求r的n次方根作为该数据的新的R值。这里的n就是该数据的权重。最终算法返回前k个R值最高的数据然后返回。根据计算规则，权重越大的数据计算所得的R值越接近1，所以越有可能被返回。


　　在 cloudera ML 项目中，为了更好地使用k-means++算法（K-均值++算法），我们会首先使用加权的蓄水池抽样算法对输入数据进行抽样。ksketch 命令会为k-means++算法进行初始化–在输入数据上进行迭代操作，选择样本抽样。每次选取过程，数据被选入样本的概率和该数据与当前样本中最短距离节点的距离成比例。通过使用加权的蓄水池抽样算法，只需扫描数据一遍就能决定样本组成（一般方法需要首先遍历一次以计算出聚类的总代价，之后第二次遍历根据第一次的计算结果进行样本选择）。


　　要读的一些书目


　　很多有趣的算法都不止对写分布式文件系统或者搜索引擎的工程师有用，它们有时对于大规模数据分析和一些统计问题也特别有帮助。接下来，我会再写几篇关于算法博客。但在这之前我的说，高德纳老爷子的书常读常新，大家先去看看《计算机程序设计艺术》上面的算法吧~
[size=14.40000057220459px]
[size=14.40000057220459px]

英文原文：hadoop-stratified-randosampling-algorithm

　　译者：bruce-accumulate