基于特征分析的微博用户兴趣发现算法*

赵岩露, 王晶, 沈奇威

（1 北京邮电大学网络与交换技术国家重点实验室, 北京 100876；2 东信北邮信息技术有限公司, 北京 100191）

1 引言

个性化推荐是一种广泛使用的Web个性化服务应用程序，它根据用户的兴趣和特点，对信息资源进行收集、整理和分类，向用户提供和推荐符合其兴趣偏好或需求的信息[1]。而个性化推荐的本质是如何描述和发现用户的兴趣[2]。

社交网络服务作为社会化媒体的出现，已经在用户的日常生活中占据很大的地位。腾讯微博，作为中国最大的微博网站之一，拥有超过2亿注册用户，每天产生超过4000万条消息。由于社交网络中用户的入度和出度的分布也是满足长尾分布的[3]，并且对于使用者来说用户比消息本身重要的多，因此如何给用户推荐其感兴趣的用户，并减少信息超载的风险就成了亟待解决的问题，也提供了寻求新的数据挖掘解决方案的机会[4]。

本文在腾讯微博的开放数据集基础上，分析用户的特征信息(包括用户的个人基本信息、用户的微博信息、用户的行为信息和用户的关注信息)，建立用户兴趣模型，发掘用户的相关用户列表，采用协同过滤的方法为用户推荐其可能感兴趣的明星用户，达到个性化推荐的效果。

2 兴趣模型研究现状综述

用户兴趣模型适用的场合很广泛，无论是电子商务、社交网络还是搜索引擎。

如何规划系统的动作, 也是构建用户模型过程中的一大难点[5,6]。

衡量一个用户兴趣模型好坏的主要因素是其表示用户兴趣的能力[7]。用户兴趣模型的计算方法主要采用协同过滤算法。学术界对协同过滤算法进行了深入研究，提出了很多方法，比如基于领域的方法、隐语义模型、基于图的随机游走算法等[3]。现有的协同过滤算法在计算推荐过程中将用户访问过的每个资源同等对待，这显然是不合理的。在微博数据中，要结合用户对每个用户的实际交互行为，考虑为用户间分配不同的权重。

在微博系统中，由于微博信息的不断更新增多，所以信息的数量级比用户的数量级大，考虑到计算时间和复杂度，就需要采用基于用户的协同过滤推荐算法[8]。

3 微博数据集描述

微博数据集描述如表1所示。

本文认为一个微博数据集的特征应包括用户的个人信息，微博信息，社交关系信息和行为信息这4个维度。其中个人信息反映用户的基本社会属性，微博信息反映用户微博的的内容，社交关系信息反映用户的社交圈，行为信息反映用户的互动情况。这4个维度能很好的反映微博用户的兴趣，本文的兴趣模型都是围绕这些特征而进行分析计算。

4 算法描述

4.1 核心算法

将用户的特征划分为相互独立的3个模型计算与其可能相关的用户：

(1) 个人信息相关度模型：定义根据用户的个人信息计算与其相关的用户的方法为calcUserProfile。

(2) 微博信息相关度模型：定义根据用户的微博内容信息计算与其相关的用户的方法为calcUserKey Word。

(3) 社交信息相关度模型：定义根据用户社交关系信息和行为信息计算与其相关的用户的方法为calcUser SNS。

图1 核心算法图

表1 微博数据集

采用这3个模型分别计算用户的相关用户列表，结合模型融合的技术和TOP-N算法得到最终的推荐明星列表。

核心算法思路如图1所示。

4.1.1 个人信息相关度模型

calcUserProfile采用统计的方法计算，计算方法如表2所示。系统中采用0.3作为阈值，与当前用户相关度权值超过0.3的用户按序组成与当前用户的相关用户列表，个人信息相关度如表2所示。

表2 个人信息相关度表

4.1.2 微博信息相关度模型

calcUserKeyWord采用向量空间模型计算。

当需要对未知用户和用户兴趣模型进行比较时，就通过计算未知用户的关键词权重向量V(v1，v2，…，vn)和用户兴趣度向量W(w1，w2，…，wn)之间的余弦相似度公式(1)来度量， Sim(V，W)越大，说明两个向量的匹配程度越高。

在微博信息相关度模型中，文本是用户，词组是用户的关键词信息。系统中采用0.05作为阈值，与当前用户相似度权值超过0.05的用户按序组成与当前用户的相关用户列表。

4.1.3 社交信息相关度模型

calcUserSNS采用图的模型计算。

如图2所示，令G(V，E)表示用户与用户间关系的无向图，其中V是所有用户顶点的集合，E是用户与用户之间的边，代表用户之间的相关程度。

图2 用户关系图模型

本文采用基于随机游走的PersonalRank算法来计算图中顶点之间的相关性。

假设要对用户A进行用户推荐，可以从用户A对应的节点VA开始在图上进行随机游走，游走到任何一个节点时，首先按照概率α决定是继续游走，还是停止这次游走并从VA节点开始重新游走。如果决定继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中用户的权重就是用户节点的访问概率。

上面的描述可以用公式(2)表示：

在社交信息相关度模型中， 系统采用系数α为0.8。对收敛后的用户节点的访问概率进行排序，即得到与当前用户相关的用户列表。

4.1.4 模型融合

单独采用以上的某个模型都不能很好的解决推荐问题，所以需要采用模型融合的技术，将各个模型的结果进行融合，从而得到最终的推荐结果。

在本文中，采用加权融合的方法，优先级为社交信息模型>微博信息模型>个人信息模型。为了避免过拟合的问题，利用最小二乘法[9]，计算出3个模型的线性加权系数依次为0.8、0.5、0.3。将各个模型的预测结果值乘以线性加权系数并排序即得到最终的相关用户列表。

4.1.5 产生推荐结果

对当前用户的相关用户列表，采用TOP-N算法进行明星用户推荐。Top-N推荐是针对单个用户产生的，它对每个人是不一样的：通过对你的相关用户列表进行统计，选择累积出现权值最高的且不在你的关注列表中的N个明星用户作为推荐结果。

4.2 冷启动问题

在推荐系统中，必须考虑系统冷启动的问题[10]，也就是用户的行为数据不足的情况下系统推荐的问题。聚类算法作为无意识的自动发现算法，能很好的解决系统的冷启动问题。本文采用改进的K-means算法，聚合出系统中明星的类别，为用户推荐主流类别的用户。

5 实验结果

5.1 评测指标

主要依据信息检索的常用指标，召回率、正确率和F-Measure[11]。正确率(Precision)定义为系统的推荐列表中用户喜欢的产品和所有被推荐产品的比率。召回率(Recall)定义为推荐列表中用户喜欢的产品与系统中用户喜欢的所有产品的比率。

为了同时考察正确率和召回率，Pazzani等把二者综合考虑提出了F指标[12]。F指标定义为：

其中，P为正确率，R为召回率。由于F指标把正确率和召回率统一到一个指标，因此得到了广泛的应用。

测试采用的方法为K重交叉验证法。该方法是最为普遍的计算推广误差的方法之一。

5.2 结果分析

实验结果如图3～5所示。

方法1：按照用户微博中提取出的关键字和明星的关键字直接进行相似度计算。由于本方法依赖用户和明星标签的规模，故随着样本用户集增大，召回率和正确率逐步增高，但是正确率仍旧在一个较低的范围之内。值得注意的是，其召回率在正常的范围内不断稳定增长。

方法2：采用分析提取用户好友列表的方法，将好友列表中用户关注的明星做统计计算。本方法受用户集增大而较大的影响，但是用户集规模到达一定地步之后，用户的关系网趋于稳定，影响幅度变得很小。同时，可以看出本方法的正确率始终保持在很高的规模，这样从侧面验证了微博中用户关注的重要意义。

方法3：采用本文提出的基于特征分析的兴趣发现方法。 兼顾了方法1和方法2的优点，结果显示其召回率不断提升，正确率也维持在一个满意的规模内。各项指标较前两种方法都有一定的提升。

方法4：采用聚类的方法解决冷启动问题。主要解决了召回率较低的问题，从系统内明星中进行聚类发掘，并根据用户反馈修正更新推荐结果，可以看到在保证正确率维持在原有规模的基础上，召回率较之前的3种方法有较大程度的提升。

总的来看，由3个图比较可见，改进后的算法(即方法4)能得到最大且稳定的召回率和正确率。

图3 推荐结果召回率曲线

6 结语

微博中的关系，只是整个社会科学中社会关系、人际关系的一部分，值得更深一步研究。

图4 推荐结果正确率曲线

图5 推荐结果F-Measure曲线

本文的创新之处在于对微博的数据特征进行了深入的分析，诠释了微博用户兴趣在微博系统中的表达形式。在实际系统中，采用提取用户的关注用户列表作为推荐新用户的主要依据，其优点是快速简单，但是缺点是没有充分考虑社交网络中用户的特征，而且在覆盖率和新颖度上都无法保证。在分析和采用实际推荐系统方法的基础上，围绕微博系统特征进行推理分析和计算，比较多种方法的优劣，提出改进后的算法。实验结果验证表明改进后的算法较之前的算法在各个指标上有显著提升。

[1] 林霜梅，汪更生，陈弈秋. 个性化推荐系统中的用户建模及特征选择[J]. 计算机工程，2007，33(17)：202-204+236.

[2] Jie Y. A short-term user Interest model for personalized recommendation[A]. Information Management and Engineering (ICIME)[C]. 2010 The 2nd IEEE International Conference.

[3] 项亮. 推荐系统实践[M]. 北京：人民邮电出版社，2012.

[4] KDD Cup 2012，ACM SIGKDD，knowledge discovery and data mining conference, August 12-16，Beijing，China[EB/OL]. http://www.kddcup2012.org/c/kddcup2012-track1.

[5] 周继恩，刘贵全，张春阳. 基于内部信念状态POMDP模型在用户兴趣获取中的应用[J]. 小型微型计算机系统，2004,25(11):91-95.

[6] Xu Z H，Lu R，Xiang L，Yang Q. Discovering user interest on Twitter with a modified author-Topic model[A]. 2011 IEEE/WIC/ACM International Conference[C].

[7] 郭新明，弋改珍. 基于向量空间模型的用户兴趣模型研究[J].咸阳师范学院学报. 2009，24(6)：53-55.

[8] 万里，廖建新，王纯. 基于社会网络信息流模型的协同过滤算法[J]. 吉林大学学报(工学版), 2011，41(1)：275-280.

[9] http://zh.wikipedia.org/wiki/最小二乘法.

[10] 佐凯. 基于云计算的微博推荐系统[D]. 南京：南京理工大学, 2012.

[11] 刘建国，周涛, 郭强. 个性化推荐系统评价方法综述[J]. 复杂系统与复杂性科学. 2009,6(3)：5-14.

[12] Pazzani M，Billsus D. Learning and revising user profiles：the identification of interesting web sites[J]．Machine Learning，1997，27：313-331.