好友推荐:推荐结果优化

/ Algorithm / 没有评论 / 108浏览

好友推荐结果优化

最近在做个性化的好友推荐中遇到了一些业务上的需求,要求对推荐系统产出的推荐列表做些约束,需求总结如下:

  1. 推荐列表中男女用户比例大致相等
  2. 推荐列表中男女用户尽量交替出现

初看以上需求时,第一条可以很轻松得找到方法满足,但是要使推荐列表中男女用户尽量交替出现还是有点难度的,首先我们要量化“交替出现”即如何让“交替出现”更直观得使程序便于理解,所谓的“交替出现”无非是让推荐列表中男女排列更“混乱”,尽量避免诸如“00001111”,“1110000”或“0001110”之类的有序(0为女性,1为男性)

基于以上问题出发,定义推荐列表的男女性用户“混乱程度”为\(E\),假设某个用户的推荐列表中男女性排序为“001101”,则定义\(E\)计算方法如下: alt 设\(x_0\)为原始推荐列表中性别列表,\(x_1\)为原始推荐列表向前平移一个单位形成的列表,则推荐列表\(x_0\)的“混乱程度”为\((0-0)^2+(1-0)^2+(0-1)^2+(1-0)^2+(1-1)^2 = 3\),计算公式如下,其中\(x\)为推荐列表中性别集合 $$E = \sum_{i=2}^{|x|}(x_i-x_{i-1})^2$$
根据上述公式计算推荐列表的性别“混乱程度”会有一定的问题,推荐列表的长度会一定程度影响\(E\)值,比如以下两个列表\(x_3\)和\(x_4\)

根据上述公式计算,\(E_{x_3} = E_{x_4}\),但是很显然\(x_3\)排序要比\(x_4\)好,BTW,虽然我们对每个用户算出的推荐列表一定是等长的,但是为了让方法通用一点,我们引入推荐列表长度来改善我们性别“混乱”程度\(E\)的计算 $$E = \frac{1}{|x|} \sum_{i=2}^{|x|}(x_i-x_{i-1})^2$$
其实仔细琢磨你会发现,上面公式计算推荐列表中男女性别的“熵”还是有一点问题的,假如我们有\( x_5\)和\( x_6\)两个推荐列表如下:alt
很明显,根据上述公式计算有\(E_{x_5}=E_{x_6}=\frac{1}{6}\),但是根据我们的要求1,推荐列表\( x_6\)的结果要比\( x_5\)的优秀,所以我们下一步引入性别比例来计算推荐列表的“熵” $$E = \frac{1}{|x|} \sum_{i=2}^{|x|}(x_i-x_{i-1})^2 \times \frac{|x_{sex=1}| \times |x_{sex=0}|}{|x|} = \frac{|x_{sex=1}| \times |x_{sex=0}|}{|x|^2} \sum_{i=2}^{|x|}(x_i-x_{i-1})^2$$
在上式中\(|x_{sex=1}|\)为推荐列表中男性用户数量,\(|x_{sex=1}|\)为女性用户数量,所以,经过上述公式修正后,\(E_{x_5} = \frac{5}{36}\), \(E_{x_6} = \frac{9}{36}\)。