lea*_*ner 6 hadoop mapreduce cluster-analysis data-mining mahout
我正在使用Mahout群集,我有大型群集,每个群集拥有大约10万用户,每个用户有5个功能.在下一步中,我需要计算pearson相关性以找出群集用户之间的相似性.
目前我有一个python脚本,它对我做同样的事情,但正如预期的那样,它需要长时间的计算,不再是一个可行的选择
我查看了Mahout,因为它提供了使用Pearson,Tanimoto,loglikelyhood度量来查找UserSimilarity的功能,我无法找到的是开发这些相似性度量的Mapreduce版本的方法.
是否有任何资源可以举例并解释如何开发UserSimilarity的mapreduce版本,或者使用hadoop流和相同的java类是否有意义.
编辑
即使我在群集中拥有100k用户,我也很少需要计算100k*100k矩阵.大多数时候它将是一个10k*100k的矩阵.然而,我有大约500个这样的集群,所以计算500个10k*100k集群的时间相当长,这就是我寻找更好的方法和触发讨论的原因
根据定义,成对用户相似性在MapReduce中无法表示.
如果你还记得那map是什么,那就是它读取一个键值对.它不是读取两个键值对.
根据定义map,您无法计算成对比较.
如果您意识到map和reduce是线性过程,那么这应该是显而易见的.成对相似性是一个二次任务.它不能工作.
也就是说,除非你滥用 mapreduce.您可以爆你的数据空间大小二次.如果您首先生成所有n*n对,则可以再次使用MapReduce处理这些对.但这是对它的滥用(虽然有些人似乎正是如此).
首先,有时您可以将问题重写为实际上是线性的,例如通过反转数据.或者通过做一些巧妙的修剪,以便实际上它是二次的,在实际数据中它通常保持线性(因为你可以在生成期间或之前丢弃很多理论上的二次数据).
其次,请注意Mahout构建在Hadoop平台上,但并不仅仅通过MapReduce来解决所有问题.很多Hadoop的东西都不只是"map + reduce".例如TeraSort - 因为排序不是线性问题(它还涉及比较元素!),MapReduce无法解决它.但是您可以使用Hadoop for TeraSort,通过编写分布式排序,使用广义中值中值方法来估计分位数,根据这些分位数分配数据,然后对O(n log n)各个节点上的各个桶(in )进行排序.复杂性仍然是超线性的,但运行时间远低于单个节点.
我很确定Hadoop会为您提供MapReduce之外的几个选项.您可能希望更仔细地了解Mahout解决此类非线性问题的方法.它不会尝试或假装MapReduce一切.Apache Hama也使用称为"批量同步处理"的概括来超越MapReduce.Hadoop(和Yarn)一般都允许这样的事情.但API显然比经典的Mapper和Reducer API更难.
或者你采取滥用的方式(这可能不是 Mahout所做的).滥用map reduce实际上相当简单.因为输出大小没有约束.因此,如果您不关心内存,可以执行以下操作:
假设您知道所有密钥,例如因为它们编号为1到n.然后你可以使用
map(K, V) -> [ (1, (K, V)), (2, (K, V)), (3, (K, V)), ..., (n, (K, V)) ]
(显然创建了二次大小的数据集!),在reducer中,每个键现在都有一个数据集的完整副本和一个要关注的ID.
因此,每个对象的reducers 再次读取完整的数据集,计算n个相似度,然后输出它们.
Boom,你映射减少了问题.这是愚蠢和低效的,但它的工作正在进行中.
更智能的版本将直接将数据集加载到系统中作为所谓的"辅助数据".它确实如此:
map (K,V) -> [ (K_1, sim(V, aux_obj1)), (K_2, sim(V, aux_obj2)),
(K_3, sim(V, aux_obj3)), ... (K_n, sim(V, aux_objn)) ]
这并不像滥用MapReduce那么糟糕(它只是你的二次结果矩阵的并行计算的规范方式),因为它至少对它的作用是诚实的:使用大量的辅助数据.它也可以工作 - 只要辅助数据适合您的工作记忆.它不再是一个合适的mapreduce,因为它使用的辅助数据实际上不能被视为函数的参数化.
鉴于您显然可以将数据加载到内存中(即使在python中),最后一个选项可能是您最简单的方法.您甚至可以将辅助内存分解为块,并将这些数据库片段计算为单独的作业.
不过,它不是MapReduce.这是一个二次问题,根据定义,它不能是MapReduce.这些问题可以在Hadoop上解决(参见Mahout),但是你需要的不仅仅是MapReduce.
首先,请分享更多关于您真正计划的事情.变得更快的关键想法是做得更少.如果您可以保存计算,那么您总是更快.
100k用户和5个属性(双值？)不是很多.所以也许你的python实现效率太低.经过编译和优化的语言可能会使您的速度提高1-2个数量级.我在10分钟内完成了110k对象的8个属性的成对相似性; 所以你的问题在这个时候也应该是可以解决的.100k用户和5个属性还没有真正的"hadoop大数据".与快速低级实现相比,您可能最终为Hadoop开销支付的费用高于您的支出.
优化Pearson相关性:您可以在这里做几件事.请注意您最终如何重新计算标准偏差等内容？如果预处理数据并将每条记录标准化为平均值0和标准差1,则Pearson相关性简化为协方差(因为stddev为1).因为均值为0,Covariance变得公正E(x*y) = 1/5 \sum x_i * y_i.如果您感兴趣的话,可能会通过使用空间索引来加速此功能,例如,每个都只有前十个相似的对象.我想你可以很容易地将它添加到ELKI并在那里使用空间索引结构.这通常会减少运行时间的另一个数量级,这意味着您应该在单个CPU上处理1分钟的处理时间.