hadoop - mapreduce 条件概率

Question

如何使用映射器在我的 reducer 中进行概率聚合；

我正在尝试在 Hadoop 上为以下任务实现“ strip ”方法和“对”方法，但我想知道如何在多个映射器之间进行通信以及如何在内部进行面向概率的聚合我的 reducer 。

• 每对item的共现，Count(A, B)=# of transactions contains both A and B, and the conditional probability Prob(B|A)=Count(A,B)/Count(A ).
• 每个三元组项目的共现，Count (A,B,C) =# of transactions contains both A and B, and the conditional probability Prob(A|B,C)=Count(A,B, C)/计数(B,C)

• 每一行记录一次交易(一起购买的一组商品):输入数据集是具有以下格式的交易数据:

  25 52 164 240 274 328 368 448 538 561 630 687 730 775 825 83439 120 124 205 401 581 704 814 825 83435 249 674 712 733 759 854 95039 422 449 704 825 857 895 937 954 96415 229 262 283 294 352 381 708 738 766 853 883 966 97826 104 143 320 569 620 7987 185 214 350 529 658 682 782 809 849 883 947 970 979227 39071 192 208 272 279 280 300 333 496 529 530 597 618 674 675 720 855 914 932================================================ =====================================**

Answer 1

对您的问题的简短回答是，您不在映射器之间直接通信……这与 map-reduce 计算模式背道而驰。相反，您需要构建您的算法，以便您的 map 阶段输出的键值可以被您的 reducer 阶段以智能方式使用和聚合。

从您在问题中的背景信息可以清楚地了解到，计算您感兴趣的条件概率实际上只是一种计数练习。这里通常的模式是在一个 map-reduce pass 中进行所有计数，然后获取这些输出并在之后划分适当的数量(尝试将它们处理到 map-reduce pass 中会增加不必要的复杂性)

您实际上只需要一个数据结构来跟踪您要计数的事物。如果速度是必须的，您可以使用一组具有隐式索引的数组来完成此操作，但是根据单个 HashMap 进行说明很简单。因为我们不感兴趣

用于 hadoop 流的 python 映射器代码

import sys
output={}


for line in sys.stdin:
   temp=line.strip().split('\t')
   # we should sort the input so that all occurrences of items x and y appear with x before y
   temp.sort()
   # count the occurrences of all the single items
   for item in temp:
      if item in output:
         output[item]+=1
      else:
         output[item]=1


   #count the occurrences of each pair of items
   for i in range(len(temp)):
      for j in range(i+1,len(temp)):
         key=temp[i]+'-'+temp[j]
         if key in output:
            output[key]+=1
         else:
            output[key]=1
   #you can triple nest a loop if you want to count all of the occurrences of each 3 item pair, but be warned the number of combinations starts to get large quickly
   #for 100 items as in your example there would be 160K combinations


#this point of the program will be reached after all of the data has been streamed in through stdin
#output the keys and values of our output dictionary with a tab separating them
for data in output.items():
   print data[0]+'\t'+data[1]

#end mapper code

reducer 的代码现在与所有如此多产的字数统计示例相同。可以找到带有 map-reduce 流的 python 代码示例 here . map-reduce 程序的输出将是一行，其中的键描述了已计算的内容以及每个项目的出现次数以及所有对的键和出现次数，您可以从那里编写程序计算您感兴趣的条件概率。