我有由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 条记录,其中每条记录是按位置排序的一对值(位置和非重复计数)。