推荐算法之好友推荐

学习地址： http://my.oschina.net/u/176897/blog/99761

写点自己的理解，大牛请直接略过。

好友推荐里有推荐一些你可能认识的人，其中二度人脉是其中一种。
比如： 何炅和谢娜 在微博上相互关注，那用二度人脉的方法就是找和谢娜相互关注的人（如 张杰，海涛，某人）， 这时候[张杰，海涛，某人]就是何炅的二度人脉，排除掉何炅已经相互关注的张杰，剩下[张杰和某人]，于是何炅发现忘记关注海涛了，接着互粉了。

在hadoop上计算用户们的二度人脉采用两步：<key,value> <key,[values]>表示

1.
   第一个map输入互粉的 <a,b> , <a, c> , <a,d> , <b, c> , <b,d>
   reduce阶段: 得到<a, [b, d, c]> <b, [c, d]>
   输出(2=二度人脉，1=互粉) <b+d,2> <b+c,2> <c+d, 2> <a+b, 1> <a+d, 1> <a+c, 1>
<c+d, 2> <b+c, 1> <b+d, 1>

2. map输入上一个阶段输出。
   reduce阶段:开始累加二度的值，出现是互粉的则为非二度。
   <b+d, [2,1]> 其实b和d 已经互粉。
   <b+c, [2,1]>
   <c+d, [2,2]> c和d是二度人脉，出现值为2，出现的越高表示他们月有可能相互认识。越值得推荐给对方。

按照微博的用户数量估计一下数据量。
1. 1亿的用户，平均有100个互粉用户，则有100亿的数据奔向reduce阶段。
（假设其中有1万的用户，他们有1000个互粉，则reduce输出可能达到1w*1000*1000=100亿的数据量输出，容易发生数据倾斜的情况。）总的有可能会有 1亿*100*100 = 1万亿的输出数据， 存储空间需要20T左右（未压缩），

2. 第二个阶段的数据量由第一个阶段决定。但是第二阶段需要启动更多reduce去算完这1万亿的数据，所以这个阶段会和第一个阶段一样耗时。

希望有跑过这个量级的朋友分享一下经验。