MapReducer设计模式--相关性计数模式

相关性计数模式主要用来分析数据相关性的设计模式。比如根据大量用户超市购物车的商品列表就可以分析关联性，大多数用户购买了A商品的同时购买了C商品，我们可以通过分析挖掘，将商品A和C摆在一起，或者将A和C捆绑销售，提高用户的购买性

假设有如下数据：

2,3,1,4,5,2,3

1,2,5,2

4,5

1,3,4,1

3,1

4,2,1,5,5,3

每一行代表一个用户购物车所有商品的ID。

     用[1,2]  5(2+2+0+0+0+1=5)来表示,有5个用户同时购买商品2和商品1, 要实现这种统计，通常有2种模式： pairs 和 stripes 

   paris模式

paris模式思想相对简单，就是在Map阶段逐个列表读取2个商品ID为一对做为key，并且计数为1做为value，将Key和value 发送到Reduce中，相同的Key会发送到同一reduce中，因此，在reduce中对value值进行累加就完成计数。

伪代码如下：

class Mapper
    method Map(null, items [i1, i2,...] )
        for all item i in [i1, i2,...]
            for all item j in [i1, i2,...]
                Emit(pair [i j], count 1) //出现一次发送一次计数
 class Reducer
    method Reduce(pair [i j], counts [c1, c2,...])
        s = sum([c1, c2,...]) //统计出现的次数
        Emit(pair[i j], count s)

 Stripes模式

      stripes模式相对比较复杂，在map阶段逐个读取商品ID，并对这个商品ID进行累加计数。将商品ID以key，计数个数作为value，保存在MapWritable中。将商品ID以key，MapWriteable为value 发送到reduce中。在reudce中，对MapWritable中的商品ID，购买个数在次进行累加，将商品对及累计数发送出去,完成计数。

Map阶段输入数据：

2,3,1,4,5,2,3

1,2,5,2

4,5

1,3,4,1

3,1

4,2,1,5,5,3

Map 阶段输出格式: 商品ID，[商品ID，累计数]

     2,[1,1]

     2,[3,2]

     2,[4,1]

     2,[5,1]

           3,[1,1]

3,[2,1]

3,[4,1]

3,[5,1]

1,[2,1]

1,[3,1]

1,[4,1]

1,[5,1]

4,[2,1]

4,[3,1]

4,[5,1]

5,[2,1]

5,[3,1]

2,[3,1]    

1,[2,2]

1,[5,1]

2,[5,1]

5,[2,1]

4,[5,1]

1,[3,1]

1,[4,1]

3,[1,1]

3,[4,1]

4,[1,1]

3,[1,1]

4,[1,1]

4,[2,1]

4,[3,1]

4,[5,2]

2,[1,1]

2,[3,1]

2,[5,2]

1,[3,1]

1,[5,2]

5,[3,1]

5,[3,1]

    

Reduce阶段输出：

[1,2]                           3

[1,3]                           3

[1,4]                           2

[1,5]                           4

[2,1]                           2

[2,3]                           4

[2,4]                           1

[2,5]                           4

[3,1]                           3

[3,2]                           1

[3,4]                           2

[3,5]                           1

[4,1]                           2

[4,2]                           2

[4,3]                           2

[4,5]                           4

[5,2]                           2

[5,3]                           3

伪代码如下：
   

class Mapper
     method Map(null, items [i1, i2,...] )
        for all item i in [i1, i2,...]
             H = new AssociativeArray : item -> counter
             for all item j in [i1, i2,...]
                H{j} = H{j} + 1               //统计和item i同时出现的单词的计数
             Emit(item i, stripe H)
 class Reducer
    method Reduce(item i, stripes [H1, H2,...])
        H = new AssociativeArray : item -> counter
        H = merge-sum( [H1, H2,...] ) //按元素进行统计Element-wise sum
        for all item j in H.keys()
            Emit(pair [i j], H{j})

      pairs的map阶段输出的键由于是pair，因此类型多样，不利于conbiners排序，而stripes方法中map输出键为元素个数，减少了排序，且在combiners有更多的机会执行局部聚集，且高效利用内存。总的来说，在维度和数据很大的情况下，stripes性能更优。

但是从可拓展性上来说，Pairs 比Stripes 有更高的拓展性，因为Paris 产生的Key/Value 的大小总是很小的，所以Paris几乎不存在拓展性问题。但是对于Stripes就不同了。Stripes 产生的Key/Value 的大小依据整个文集的大小。当文集很大时，一个Key/Value 的Value就会非常的大，有可能一个Mapper无法处理。这样拓展性能问题就显而易见了。

此外，特别注意stripes算法中，map输出为MapWritable类型，不能使用MapHash类型中作为输出输入类型的键值对类型（否则会出现空指针异常错误），可选类型见api库的org.apache.hadoop.io，里面还罗列了许多继承了writeble的数据类型。

还有个问题需要注意,如上Reduce阶段输出：

        [1,2]                           3

        [2,1]                           2

这两个输出，其实是可以合并的，[1,2]     5，因为都是同时购买的商品，只是先后顺序不同，要解决这类问题有2种方法，

1、  在map阶段，对输入数据进行排序。

2、  在map输出阶段，比较输出元素大小，按由小到大的顺序输出