[Spark好友推荐]

好友推荐概念     


目前大量的社交网站上，它们都有一个共同的特性，就是可以在好友关系的基础上推荐更多的联系人。例如，QQ的“你可能认识的人”特性允许用户查看它们可能联系的人。基本思想就是：如果tom是jack的好友，而tom又是
peter的好友，也就是说，tom是jack和peter的共同好友，但是jack和peter可能并不认识你。那么社交网络系统可能就会推荐jack与peter
联系，又或者推荐peter与jack
联系。简单通俗的说，如果两个人有一组共同好友，但是两人又不是好友关系，那么推荐系统就会基于他们之间的好友关系推荐他们相互认识。

       所有用户之间的好友关系可以表示为一个图，对于一个简单的案例，可以使用下图进行表示。



在这里，图是一个有序对G=(V,E)，其中：

       V：是由人（社交网络中的用户）构成的衣一个有限集合。

G：是V上的二元关系，称为边集，其中的元素称为一个好友关系。

好友推荐问题可以表述为：对于每一个用户P，其好友列表P1,P2,…P20，表示用户P一共有20个好友。即P:{ P1,P2,…P20}

好友推荐样本数据

假设输入记录是一个按照用户ID排序的列表，输入的没有行数据分别代表用户ID(如用户ID表示为P)，其后面的数据表示该用户的好友列表，则好友关系可表示为：

       P,P1 P2 … Pn,其中P1<P2<…Pn.

其样本数据如下所示：
P1,P2 P3 P4 P5 P6 P7 P2,P1 P3 P4 P3,P1 P2 P4 P5 P4,P1 P2 P3 P5,P1 P3 P7 P6,P1
P7,P2
Spark代码实现
/** * Spark共同好友推荐 **/ object FriendRecommendation { def main(args:
Array[String]): Unit = { if (args.length < 2) { println("Usage:
FriendRecommendation <input-path> <output-path>") sys.exit(1) } val inputPath:
String = args(0) val outputPath: String = args(1) val sparkConf: SparkConf =
new SparkConf() .setMaster("local[1]") .setAppName("FriendRecommendation") val
sc: SparkContext = SparkContext.getOrCreate(sparkConf) val records: RDD[String]
= sc.textFile(inputPath) //计算两两之间的可能好友关系 val pairs: RDD[(String, (String,
String))] = records.flatMap(line => { val tokens: Array[String] =
line.split(",") val person: String = tokens(0) val friends: List[String] =
tokens(1).split("\\s+").toList val mapperOutput: List[(String, (String,
String))] = friends.map(directFriend => (person, (directFriend, "-1"))) val
result: List[List[(String, (String, String))]] = for { fi <- friends fj <-
friends possibleFriend1 = (fj, person) possibleFriend2 = (fi, person) if fi !=
fj } yield { (fi, possibleFriend1) :: (fj, possibleFriend2) :: List() }
mapperOutput ::: result.flatten }) //合并同一个键对应的共同好友 val combineValue:
RDD[(String, List[(String, String)])] = pairs.combineByKey( (v: (String,
String)) => List(v), (c: List[(String, String)], v: (String, String)) => c :+
v, (c1: List[(String, String)], c2: List[(String, String)]) => c1 ::: c2 )
//这里是测试，可以使用collect()生成集合后进行打印 pairs.collect().foreach(println);
combineValue.foreach(println) //共同好友个数计算及好友推荐 val result: RDD[(String,
Map[String, List[String]])] = combineValue.mapValues(values => { val
mutualFriends: mutable.HashMap[String, List[String]] = new
collection.mutable.HashMap[String, List[String]].empty values.foreach(f = t2 =>
{ val toUser: String = t2._1 val mutualFriend: String = t2._2 val
alreadyFriend: Boolean = mutualFriend == "-1" if
(mutualFriends.contains(toUser)) { if (alreadyFriend) {
mutualFriends.put(toUser, List.empty) } else if
(mutualFriends.get(toUser).isDefined && mutualFriends.get(toUser).get.size > 0
&& !mutualFriends(toUser).contains(mutualFriend)) { val existingList:
List[String] = mutualFriends.get(toUser).get mutualFriends.put(toUser,
mutualFriend :: existingList) } } else { if (alreadyFriend) {
mutualFriends.put(toUser, List.empty) } else { mutualFriends.put(toUser,
List(mutualFriend)) } } }) mutualFriends.filter(_._2.nonEmpty).toMap })
//result.saveAsTextFile(outputPath) //打印结果 result.foreach(f => { val friends =
if (f._2.isEmpty) "" else { val items = f._2.map(tuple => (tuple._1, "(" +
tuple._2.size + ": " + tuple._2.mkString("[", ",", "]") + ")")).map(g => "" +
g._1 + " " + g._2) items.toList.mkString(",") } println(s"${f._1}: ${friends}")
}) sc.stop() } }
运行结果

可能推荐的好友关系
(P1,(P2,-1)) (P1,(P3,-1)) (P1,(P4,-1)) (P1,(P5,-1)) (P1,(P6,-1)) (P1,(P7,-1))
(P2,(P3,P1)) (P3,(P2,P1)) (P2,(P4,P1)) (P4,(P2,P1)) (P2,(P5,P1)) (P5,(P2,P1))
(P2,(P6,P1)) (P6,(P2,P1)) (P2,(P7,P1)) (P7,(P2,P1)) (P3,(P2,P1)) (P2,(P3,P1))
(P3,(P4,P1)) (P4,(P3,P1)) (P3,(P5,P1)) (P5,(P3,P1)) (P3,(P6,P1)) (P6,(P3,P1))
(P3,(P7,P1)) (P7,(P3,P1)) (P4,(P2,P1)) (P2,(P4,P1)) (P4,(P3,P1)) (P3,(P4,P1))
(P4,(P5,P1)) (P5,(P4,P1)) (P4,(P6,P1)) (P6,(P4,P1)) (P4,(P7,P1)) (P7,(P4,P1))
(P5,(P2,P1)) (P2,(P5,P1)) (P5,(P3,P1)) (P3,(P5,P1)) (P5,(P4,P1)) (P4,(P5,P1))
(P5,(P6,P1)) (P6,(P5,P1)) (P5,(P7,P1)) (P7,(P5,P1)) (P6,(P2,P1)) (P2,(P6,P1))
(P6,(P3,P1)) (P3,(P6,P1)) (P6,(P4,P1)) (P4,(P6,P1)) (P6,(P5,P1)) (P5,(P6,P1))
(P6,(P7,P1)) (P7,(P6,P1)) (P7,(P2,P1)) (P2,(P7,P1)) (P7,(P3,P1)) (P3,(P7,P1))
(P7,(P4,P1)) (P4,(P7,P1)) (P7,(P5,P1)) (P5,(P7,P1)) (P7,(P6,P1)) (P6,(P7,P1))
(P2,(P1,-1)) (P2,(P3,-1)) (P2,(P4,-1)) (P1,(P3,P2)) (P3,(P1,P2)) (P1,(P4,P2))
(P4,(P1,P2)) (P3,(P1,P2)) (P1,(P3,P2)) (P3,(P4,P2)) (P4,(P3,P2)) (P4,(P1,P2))
(P1,(P4,P2)) (P4,(P3,P2)) (P3,(P4,P2)) (P3,(P1,-1)) (P3,(P2,-1)) (P3,(P4,-1))
(P3,(P5,-1)) (P1,(P2,P3)) (P2,(P1,P3)) (P1,(P4,P3)) (P4,(P1,P3)) (P1,(P5,P3))
(P5,(P1,P3)) (P2,(P1,P3)) (P1,(P2,P3)) (P2,(P4,P3)) (P4,(P2,P3)) (P2,(P5,P3))
(P5,(P2,P3)) (P4,(P1,P3)) (P1,(P4,P3)) (P4,(P2,P3)) (P2,(P4,P3)) (P4,(P5,P3))
(P5,(P4,P3)) (P5,(P1,P3)) (P1,(P5,P3)) (P5,(P2,P3)) (P2,(P5,P3)) (P5,(P4,P3))
(P4,(P5,P3)) (P4,(P1,-1)) (P4,(P2,-1)) (P4,(P3,-1)) (P1,(P2,P4)) (P2,(P1,P4))
(P1,(P3,P4)) (P3,(P1,P4)) (P2,(P1,P4)) (P1,(P2,P4)) (P2,(P3,P4)) (P3,(P2,P4))
(P3,(P1,P4)) (P1,(P3,P4)) (P3,(P2,P4)) (P2,(P3,P4)) (P5,(P1,-1)) (P5,(P3,-1))
(P5,(P7,-1)) (P1,(P3,P5)) (P3,(P1,P5)) (P1,(P7,P5)) (P7,(P1,P5)) (P3,(P1,P5))
(P1,(P3,P5)) (P3,(P7,P5)) (P7,(P3,P5)) (P7,(P1,P5)) (P1,(P7,P5)) (P7,(P3,P5))
(P3,(P7,P5)) (P6,(P1,-1)) (P7,(P2,-1))
合并推荐好友关系
(P6,List((P2,P1), (P3,P1), (P4,P1), (P5,P1), (P2,P1), (P3,P1), (P4,P1),
(P5,P1), (P7,P1), (P7,P1), (P1,-1))) (P5,List((P2,P1), (P3,P1), (P4,P1),
(P2,P1), (P3,P1), (P4,P1), (P6,P1), (P7,P1), (P6,P1), (P7,P1), (P1,P3),
(P2,P3), (P4,P3), (P1,P3), (P2,P3), (P4,P3), (P1,-1), (P3,-1), (P7,-1)))
(P2,List((P3,P1), (P4,P1), (P5,P1), (P6,P1), (P7,P1), (P3,P1), (P4,P1),
(P5,P1), (P6,P1), (P7,P1), (P1,-1), (P3,-1), (P4,-1), (P1,P3), (P1,P3),
(P4,P3), (P5,P3), (P4,P3), (P5,P3), (P1,P4), (P1,P4), (P3,P4), (P3,P4)))
(P1,List((P2,-1), (P3,-1), (P4,-1), (P5,-1), (P6,-1), (P7,-1), (P3,P2),
(P4,P2), (P3,P2), (P4,P2), (P2,P3), (P4,P3), (P5,P3), (P2,P3), (P4,P3),
(P5,P3), (P2,P4), (P3,P4), (P2,P4), (P3,P4), (P3,P5), (P7,P5), (P3,P5),
(P7,P5))) (P7,List((P2,P1), (P3,P1), (P4,P1), (P5,P1), (P6,P1), (P2,P1),
(P3,P1), (P4,P1), (P5,P1), (P6,P1), (P1,P5), (P3,P5), (P1,P5), (P3,P5),
(P2,-1))) (P3,List((P2,P1), (P2,P1), (P4,P1), (P5,P1), (P6,P1), (P7,P1),
(P4,P1), (P5,P1), (P6,P1), (P7,P1), (P1,P2), (P1,P2), (P4,P2), (P4,P2),
(P1,-1), (P2,-1), (P4,-1), (P5,-1), (P1,P4), (P2,P4), (P1,P4), (P2,P4),
(P1,P5), (P1,P5), (P7,P5), (P7,P5))) (P4,List((P2,P1), (P3,P1), (P2,P1),
(P3,P1), (P5,P1), (P6,P1), (P7,P1), (P5,P1), (P6,P1), (P7,P1), (P1,P2),
(P3,P2), (P1,P2), (P3,P2), (P1,P3), (P2,P3), (P1,P3), (P2,P3), (P5,P3),
(P5,P3), (P1,-1), (P2,-1), (P3,-1)))
好友推荐结果
P6: P3 (1: [P1]),P5 (1: [P1]),P2 (1: [P1]),P7 (1: [P1]),P4 (1: [P1]) P5: P4
(2: [P3,P1]),P6 (1: [P1]),P2 (2: [P3,P1]) P2: P7 (1: [P1]),P6 (1: [P1]),P5 (2:
[P3,P1]) P1: P7: P3 (2: [P5,P1]),P5 (1: [P1]),P1 (1: [P5]),P4 (1: [P1]),P6 (1:
[P1]) P3: P7 (2: [P5,P1]),P6 (1: [P1]) P4: P7 (1: [P1]),P6 (1: [P1]),P5 (2:
[P3,P1])
推荐结果解读

数输出结果采用以下格式输出：

     <USER>:P(N:[U1,U2,...,Un])

其中：

      P是推荐给好友USER的一个好友。

      N是他们之间的共同好友数。

      U1,U2,...,Un是共同好友的ID。

从输出的结果中我们可以看出，用户P1没有任何好友推荐，因为P1y与所有用户都已经是好友了。

结论


基于Spark的好友推荐算法，我们可以在一个庞大的社交网络系统中，运用好友关系的大数据能够快速计算共同好友，并给好友推荐其他的好友。同理，好友推荐算法也衍生到商品推荐及电影推荐。



 

• « 上一篇：春招面经来了！
• » 下一篇：【OpenCV-Python】 直方图均衡化