加载中…
个人资料
惠普中国研究院
惠普中国研究院
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,354,931
  • 关注人气:1,156
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

借三国,看IT——惠普透过早期投票占卜“火帖”

(2011-11-01 12:01:12)
标签:

特征向量

宋体

诸葛亮

预测

占卜

惠普研究院

三国

it

分类: 科技创新

 

编者按:惠普中国研究院实习生尹培风,借用“三国”中的桥段及人物生动详尽地阐述如何用Conformer-Maverick (CM)模型模拟用户的投票过程从而对火帖进行预测。这项研究使得用户可以更早的看到有潜力火的信息;而且这些信息的更新会很快,也使得商家可以选择合适的广告位投放广告从而最大化产品曝光率。

   

              借三国,看IT——惠普透过早期投票占卜“火帖”        

 
声音

“为神马热点、火帖都没有看过啊?”
“尼玛每次关注的都木有火,没有关注的都火了!有木有!”
“后知后觉什么的最讨厌了!” 
 
 
黄巾之乱

随着Web 2.0的揭幕,“以人为本”的理念成了各大网站吸引用户的主要理念。当今“天下”,如果你上网还只是停留在看新闻的阶段,那你就“奥特曼”了。比起之前的消极上网,如今用户更主动地将自己的所见所闻所感发布到网上,而且形式多样,文章类如博客,短消息类如微博,视频类如优酷等等。除了信息发布与分享,各类网站也提供了多样化的评价体系鼓励用户对别人的信息进行投(正负)票,如土豆网的“顶”与“挖”,优酷的“顶”和“踩”。
俗话说的好,“林子大了,什么鸟儿都有”。网站上用户发布的信息因为没有严格的审查标准而导致质量参差不齐。有的用户确实会分享一些有意义的东西,而一些人却如同“黄巾乱党”,肆意灌水、发布广告,扰乱“天下”。网站提供商当然希望将一些质量高的信息放在首页,将广告等垃圾信息屏蔽。因为数量众多,让管理员挨个审查每个新发布的信息无异于“三天造十万枝箭”,乃人力不可为也。因此,各网站充分利用评价规则上演一次“草船借箭”。简而言之,网站认为用户投(正)票比较多的信息即为质量较高的信息而把它们放在首页。如今点开一个网站,放在主页的一定是此类信息,如“热点”、“聚焦”、“热门”等等。 
                                                                                                                   借三国,看IT——惠普透过早期投票占卜“火帖”
 
             Figure 1 挖笑话程序截图。我们的分析和实验都是基于这款手机应用的数据

这样一种策略在解决“质量评测”问题的同时也带来一些问题。
1) 所谓的“热点”、“火帖”已被大部分人看过,这些内容对多数人而言已无意义;
2) 贫富差距扩大。突出显示热门信息会使其得票数更多(rich-get-richer [1]),使得后来质量较高的信息无法与之匹敌,造成“热点”列表更新缓慢;
3) 火帖等于过时。对于某些特殊情况,所谓的热门意味着过时。比如各大团购网每天会推出各种商品的团购价,其中不乏超值团购。而这些超值的一般都会有人数限制。因此,如果按照上述算法,系统将把参与人数多的同时也是即将关闭的团购放在首页。这显然是坑爹的。
综上所述,为了提高用户体验,一种方法是在帖子尚未火之前进行预测,这样一石二鸟:
1)对于用户,可以更早的看到有潜力火的信息;而且这些信息的更新会很快
2)对于商家,可以选择合适的广告位投放广告从而最大化产品曝光率

隆中对

黄巾之乱后,天下群雄并起,逐鹿中原,力求预测火帖。
一种方法是采用一些机器学习的方法通过发布的信息内容来判断其是否会火 [2]。通常的过程是将信息分解成一个个有意义的词,每一个词代表特征向量的一维,这样每个文本就表示成一个特征向量,即特征提取。使用一些历史数据来训练机器学习机,如SVM (支持向量机),来学会判断什么样的特征向量更容易火。对于新发布的信息,采用同样的特征提取方式将其转换为特征向量,训练好的学习机便可以对其进行预测了。这种方法被广泛用于文本分类和文本聚类。然而这种方法有很大的弱点。
1) 无法处理非文本信息,如图片、音频、视频等;
2) 短文本会造成特征向量稀疏,影响机器学习的精度;
3) 无法处理新词汇;
4)无法正确理解笑话。笑话是很特殊的文本,单从词的层面构建的特征向量无法正确抓住其本质特征。比如在Figure 2中的两个笑话,人去读很快就能判断出是暗喻房价高不可攀。但从单词角度去理解却会得到完全不同的特征向量。假如笑话一是训练数据,机器很难判断出笑话二会火因为两者的特征向量差距太远。

                                                                                                              借三国,看IT——惠普透过早期投票占卜“火帖”

                            Figure 2 词的层面无法捕捉笑话的真谛


另外一种方法是根据早期投票来判断是否会火。比如,两篇帖子,其中一篇前5票4正1负,而另一篇4负1正,则直观上讲第一篇比第二篇更有可能会火。我们定义了一个热度计算公式(见Figure 3)并对挖笑话上的各个笑话早期热度和最终热度进行了统计, 结果见Figure 4。

                                                                                                                   借三国,看IT——惠普透过早期投票占卜“火帖” 

Figure 3 热度测量公式。q是热度,pv是正票数,nv是负票数,epsilon是一个小于1的常数。                                      
                             借三国,看IT——惠普透过早期投票占卜“火帖”
  
                                    Figure 4 早期晚期热度统计

由统计结果可知,早期投票与最终投票结果确实有一定的联系,但单凭早期投票来预测火帖却差强人意。首先,不同的早期投票结果可能有相同甚至相反的最终投票;另外,如果两个发布的信息所得早期投票数相同,也无法预测哪一个会更火。
肿么办?

蜀魏争霸

通过分析发现,我们发现用户在投票时有两种情况:1)用户的投票与大众相同;2)用户的投票与大众相反。对于第一种情况的用户,我们称之为“诸葛亮”,因为这类用户的投正票的帖子总会火,投负票的帖子总不会火,如同“未卜先知”的诸葛亮。对于第二类用户,我们称之为“曹操”,因为其投票行为与第一类相反,如同三国演义中“过后方知”的曹操。当然为了“冲出亚洲,走向世界”,我们给这两类人取了比较洋气的名字,对于诸葛亮,我们称为Conformer,对于曹操,我们称为Maverick,这两类人的投票行为如Figure 5 所示。

                  借三国,看IT——惠普透过早期投票占卜“火帖”

                                 Figure 5 诸葛亮-曹操投票行为

那么,在“挖笑话”中,有多少“诸葛亮”,又有多少“曹操”呢?我们计算了用户的投票与笑话的最终热度的Pearson关系并做了统计。Pearson关系是测量两个随机变量关系的一个度量尺,范围为-1到1,对应于两个随机变量是负到正的相关度。在这里,我们用来测量一个用户是“诸葛亮”还是“曹操”。前者的投票与热度是正相关,Pearson关系为1;后者为负相关,对应的Pearson关系为-1。随机抽取的用户其Pearson关系分布如Figure 6所示。

                       借三国,看IT——惠普透过早期投票占卜“火帖”

                                       Figure 6 Pearson关系统计图

由图可知,用户并非单纯的“诸葛亮”或“曹操”,而是两者的一个混合。换言之,用户在投票时,有时是“诸葛亮”,有时是“曹操”,这中间有一个随机的过程。

                   借三国,看IT——惠普透过早期投票占卜“火帖”

                              Figure 7 既是诸葛亮又是曹操的投票过程

因此我们提出了一个Conformer-Maverick (CM)模型来模拟投票过程。如Figure 8所示,在投票时,用户会从Conformer(诸葛亮)和Maverick(曹操)两种个性中随机选择一种。被选中的性格与待投票的信息的热度一起产生一个介于0到1之间的参数p,该参数最终决定投票是正是负。从概率角度,用户会有p的概率投正票,1-p的概率投负票,即是一个参数为p的伯努利过程。


                  借三国,看IT——惠普透过早期投票占卜“火帖”

                                             Figure 8 CM模型

六出祁山

这一部分我们做了一系列实验对CM 模型的预测进行测评。实验中我们用简易CM(Naive CM)模型(NCM),协同过滤(Collaborative Filtering)的几种变形,即User-based CF(UCF)[3],Singular Value Decomposition (SVD),Biased Singular Value Decomposition(SVD++)[4]等作为对比方法。测量的标准是RMSE和NDCG。其中RMSE越小代表效果越好,NDCG则是越大代表预测越准确。

    

Figure 9显示了总体对比的结果,其中k是指也测火帖的数目。可以看出当k比较小时,我们的方法比其他方法都好;k增大后,CM 与SVD++不分伯仲。

      借三国,看IT——惠普透过早期投票占卜“火帖”
                                    
                                       Figure 9 总体比较

Figure 10显示了早期得票数n对预测的影响。随着n的增大,除CM外所有方法都有所改进,因为有更多证据来帮助预测。而n对CM的影响没有显著的规律。因为CM的预测很大程度上由投票人的个性所决定而非早期的投票数的多寡。投票的人个性越鲜明,即越是“诸葛亮”或者“曹操”,则CM 预测越精准。

    借三国,看IT——惠普透过早期投票占卜“火帖”

                            Figure 10 早期得票数对预测的影响

Figure 11显示了训练集-测试集的大小对预测的影响。实验中我们把数据分为N份,随机选取一份作为测试数据,其余的N-1份作为训练数据。明显的,N越大,训练数据越多,测试数据越小;N越小,训练数据越少,测试数据越多。由图可知,所有方法的预测随着N的增大而增大,因为有更多的数据来进行训练使得预测的准确度提高。

           借三国,看IT——惠普透过早期投票占卜“火帖”

                            Figure 11 训练-测试数据集大小对预测的影响

尘埃落定

在本文中我们提出了一个CM模型模拟用户的投票过程从而对火帖进行预测。经过一系列实验,该模型取得了较为理想的结果。在未来的工作中,我们准备将CM模型扩展为可以模拟多级评分(如1-5星)的模型而非单一的正负投票,这样可以应用到更多拥有不同评测体系的网站中去。

封神榜

[1] G. Szabo and B. o. A. Huberman. Predicting the popularity of online content. Communications of the Acm, 53(8):80-88, 2010.
[2] B. Yu, M. Chen, and L. Kwok. Toward predicting popularity of social marketing messages. Computer Science, 6589:317-324, 2011.
[3] J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl. An algorithmic framework for performing collaborative filtering. In SIGIR, pages 230-237, 1999.
[4] Y. Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In KDD, pages 426-434, 2008.

作者介绍:
尹培风是美国宾州州立大学的博士研究生,研究方向是数据挖掘。2011年暑期在惠普中国实验室实习。
 
 

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有