Hadoop Mapreduce为大数据计算不同的矢量元素



我有由integer/real数字向量组成的数据n-length。数据通常为 GB 级别,矢量的特征大小超过 100。我想计算每个矢量特征的不同元素。例如,如果我有这样的数据:

1.13211 22.33 1.00 ... 311.66
1.13211 44.44 4.52 ... 311.66
1.55555 22.33 5.11 ... 311.66

我希望结果像(2,2,3,...,1)只有一个向量。由于向量的第一个特征中有 2 个不同的值,第二个特征中有 2 个不同的值,依此类推。

我认为使用 mapreduce 执行此操作的方法是,从映射器发送值("$val$+{feature_vector_num}",1)。例如,像(1.13211+1,1) or (2.33+2,1).在化简器中,只需将它们相加,可能是第二个映射器和化简器来包装上一步的所有化简器结果。

问题是,如果我有大小为 N 的数据,使用我的解决方案,发送到化简器的大小将是 |V| * N在最坏的情况下,(|V|是特征向量的长度),这也是同时的化简器数和键数。因此,对于大数据来说,这是一个相当糟糕的解决方案。

你有什么疑问吗?谢谢

在不考虑任何实现细节(MapReduce与否)的情况下,我将分两步完成,每个功能都有一个哈希表(可能在 Redis 中)。

第一步将列出所有值和相应的计数。

然后第二个将运行每个向量,并查看该元素在 hastable 中是否唯一。如果你有一些错误的余地,并且想要一个轻微的内存占用,我什至会使用布隆过滤器。

这两个步骤是微不足道的并行的。

我同意 lejlot 的观点,即使用其他方式(例如哈希映射等内存算法)而不是 m/r 可以更优化地解决 1GB 问题。

但是,如果您的问题大 2-3+ 个数量级,或者您只想使用 m/r 练习,以下是可能的解决方案之一:

第 1 阶段

映射

参数:

    输入
  • 键:无关紧要(对于文本输入格式,我认为它是可写的表示文件中的位置,但您可以只使用可写)
  • 输入值:单行,矢量分量由空格分隔 (1.13211 22.33 1.00 ...311.66)
  • 输出键:一对<不可写、双可写>其中,IntWritable保存组件的索引,DoubleWritable保存组件的值。谷歌的hadoop示例,特别是SecondarySort.java它演示了如何实现一对IntWritable。您只需要使用 DoubleWwrite 作为第二个组件重写它。
  • 输出值:无关紧要,可以使用空可写

映射器功能

  • 标记化值
  • 对于每个令牌,发出 <IntWriable、DoubleWwriteable> 键(您可以为此创建自定义可写对类)和 NullWwrite 值

还原剂

框架将使用<IntWritable,DoubleWwriteable>对作为键调用您的化简器,每个键变体仅一次,有效地进行重复数据删除。例如,<1、1.13211>密钥将只出现一次。

参数

  • 输入键:对<不可写,双可写>
  • 输入值:不相关(可写或空可写)
  • 输出键:可写(组件索引)
  • 输出值:可写(计数对应于索引)

减速机设置

  • 初始化大小等于向量维度的 int[] 计数器数组。

减速机功能

  • 从 key.getFirst() 获取索引
  • 索引
  • 的增量计数:计数器 [索引]++

减速机清理

  • 对于计数器中的每个计数,数组发出,数组的索引作为键,计数器的值。

第 2 阶段

这个是微不足道的,只有在第一阶段有多个减速器时才需要。在这种情况下,上面计算的计数是部分的。您需要将多个减速器的输出组合成一个输出。您需要设置一个单化简器作业,其中化简器将仅累积相应索引的计数。

映射

无手术

还原剂

参数

  • 输入键:可写(位置)
  • 输入值:不可写(部分计数)
  • 输出键:可写(位置)
  • 输出值:不可写(总数)

减速机功能

  • 对于每个输入键
    • 整数计数器 = 0
    • 遍历值
      • 计数器 += 值
    • 发出输入键(作为
    • 键)和计数器(作为值)

生成的输出文件 "part-r-00000" 应有 N 条记录,其中每条记录是按位置排序的一对值(位置和非重复计数)。

相关内容

  • 没有找到相关文章

最新更新