hadoop - 如何使用Map/Reduce挑选随机(小)数据样本？

我想写一个map/reduce作业，根据行级条件从大型数据集中选择一些随机样本。我想减少中间键的数量。

伪代码:

for each row
  if row matches condition
    put the row.id in the bucket if the bucket is not already large enough

你做过这样的事情吗？有没有众所周知的算法？

包含连续行的样本也足够好。

谢谢。

最佳答案

Karl的方法效果很好，但是我们可以大大减少映射器产生的数据量。

令K为所需的样本数。我们假定它足够小，可以容纳在您的一个节点上的内存中。我们将为每个匹配的行分配一个随机值，然后对selection algorithm进行修改以找到K个最小值。

在每个映射器的设置部分，创建一个priority queue； Fibonnacci heap是一个不错的选择。我们将使用浮点数作为优先级；如果您有大量数据，则 double 可能更合适，以避免产生联系。对于符合条件的每一行，将该行插入优先级队列，并在0和1之间随机选择一个浮点数作为优先级。如果您的队列中的物品多于K，请删除值(value)最高的物品(这与标准Fibonnacci堆的术语相反)。

最后，在映射器的末尾，发出队列中的所有内容。对于发出的每个项目，将优先级用作FloatWritable，并将对应行的某种表示形式用作值(行ID，或者可能是整个行的内容)作为键。每个映射器将仅发出K个值(如果该映射器中的匹配行少于K个，则发出的值将更少)。

在您的单个化简器中，Hadoop将自动按照从低到高的顺序扫描 key 。发出与您看到的前K个键(最低的K个)相对应的行，然后退出。

之所以可行，是因为每个匹配的行具有K个最小浮点值之一的相同概率。我们跟踪每个映射器的K个最小浮点数，以确保我们不会错过任何一个，然后将它们发送给化简器以找到K个最小的整体。

关于hadoop - 如何使用Map/Reduce挑选随机(小)数据样本？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2514061/