基于链路预测的推荐方法研究
2017-06-19丁沂
丁 沂
（武汉软件工程职业学院 计算机学院，湖北 武汉 430205）
基于链路预测的推荐方法研究
丁 沂
（武汉软件工程职业学院 计算机学院，湖北 武汉 430205）
推荐系统在数字化环境中能够提供有价值的服务，并且在图书、电影和音乐等在线产业中取得了巨大的商业成功。大多数推荐系统采用协同过滤算法，通过分析用户和物品之间的交互行为推理用户的兴趣和偏好。协同过滤算法的推荐效果受到数据稀疏性问题的影响很大。为了解决这个问题，文章使用一种基于图的方法探索用户和物品之间的交互。文章采用二分网络链路预测的方法对用户进行物品推荐，并与协同过滤方法进行了比较，通过在豆瓣数据集上的实验结果表明，基于链路预测的方法比标准的协同过滤方法要好。
推荐系统；协同过滤；链路预测
近年来，通过向潜在的用户推荐商品、服务和信息，推荐系统在很多领域得到了广泛的应用。推荐系统中最关键部分是推荐算法。推荐算法通常利用用户和物品的属性或者用户和物品之间的交互（打分行为、浏览行为、购买行为等）预测用户对某个物品的偏好[1]。协同过滤算法是推荐系统中最成功也是被关注最多的算法，这个算法依赖用户和物品之间的交互数据进行推荐。标准的协同过滤算法首先找到目标用户的邻居，寻找邻居的方法并不是使用与目标用户属性相似的用户，而是使用与目标用户具有相似行为的用户，然后根据目标用户邻居的经验对目标用户进行推荐。尽管协同过滤算法在业界取得了巨大的成功，但是协同过滤算法的效果受到数据稀疏性的影响很大，因为没有足够的历史行为数据用来帮助找到目标用户的邻居。为了解决这个问题，人们使用一种基于图的算法来探索用户和物品之间的交互行为。从二分网络的观点来看，推荐问题可以看作为每个用户节点选择未观测到的边的过程。因此，可以使用二分网络链路预测的方法对推荐问题进行建模[2]。
1 链路预测
二分网络又叫二部图，是一种具有特殊结构特征的网络。一个简单的二分网络G(V,E)存在一对节点集合X和Y，并且满足E中任意一条连边一定恰有一个顶点在集合X中，另一个顶点在集合Y中。现实世界中很多复杂的系统具有二分结构，可以用二分网络进行建模。例如，新陈代谢网络可以视为是以化学物质和化学反应为两个分离集合的二分网络，合作网络可以看作以参与者和事件为两个分离集合的二分网络，互联网是以电脑和网络设备为两个分离集合的二分网络，开源社区是以开发者和软件项目为两个分离集合的二分网络，电子商务是以用户和商品为两个分离集合的二分网络，异性的性关系网络是以男性和女性为两个分离集合的二分网络，人类疾病网络是以身心机能失调表现和致病基因为两个分离集合的二分网络。二分网络具有很多网络不具备的性质。比如，二分网络都不包含长度为奇数的圈，因此，一个包括长度为奇数的圈的网络肯定不是一个二分网络；另外，二分网络都是可以二着色的并且二分网络的谱具有对称性等等。由于二分网络具有这些特征，因此针对一个节点规模为N的无向简单网络，可以以线性时间复杂性0(N)判断该网络是不是一个二分网络。
网络分析方法近年来广泛应用在复杂系统的研究中，例如，Internet，WWW、社会网络和基因网络。链路预测是网络建模中的一个重要问题，在社会网络、基因网络和引文网络中受到广泛关注。二分网络中的链路预测与推荐系统比较相似，二分网络的链路预测是指如何通过已知的网络节点及网络结构等信息，预测网络中尚未产生连边的两个节点之间产生连边的可能性，既包含对未知连边的预测，也包含对未来连边的预测[3]。应用社会网络链路预测中的三个连边权重指标，采用用户和物品交互图的建模方法对用户进行推荐。
在二分网络G中，用户和物品代表两种不同类型的节点，不同类型节点之间的连边代表用户和物品之间的交互。由于我们研究的是基于事务的协同过滤问题，二分网络中的连边是没有权重的，而且整个二分网络代表了输入数据的全部信息。基于二分网络G的拓扑结构，我们可以为二分网络中每一对未连接用户-物品节点对
在经典网络链路预测中有很多连边权重的度量指标，在二分网络中连边权重的度量指标相对较少。因此，修改了3个经典网络中的连边权重度量指标并应用在二分网络中。如表1所示，本文对于节点x，我们定义为节点x的邻居集合Nh。
表1 基于邻居的权重指标
这3个连边权重指标都是基于邻居的相似性度量指标。Common neighbors指标表示二分网络中两个节点共同邻居的数量；Jaccard指标和Common neighbors指标类似，不仅考虑了两个节点共同邻居的数量，还考虑到了两个节点各自的邻居数目；Delta指标考虑到了两个节点邻居数量不均衡的情况[5]。
2 实验
调查都使用豆瓣数据集为研究对象，数据集覆盖了4年内2 000多个用户对1 000多本图书的20 000多个交互事务。为了评价推荐的效果，采用top-N推荐，为每个用户推荐top-10本尚未购买的图书。将基于二分网络链路预测的推荐方法和标准协同过滤算法进行了对比。从实验结果可以看出，基于二分网络链路预测的方法要比标准的协同过滤方法好。
表2 实验结果
3 结语
本文运用网络结构和网络分析技术，采用二分网络链路预测方法对用户推荐它们感兴趣的物品，并与标准协同过滤算法进行了比较。未来将采用更多权重度量指标验证本方法的有效性。
[1]邓爱林，朱扬勇，施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报，2003（9）：1621-1628.
[2]孟祥武，胡勋，王立才，等.移动推荐系统及其应用[J].软件学报，2013（1）：91-108.
[3]王立才，孟祥武，张玉洁.上下文感知推荐系统[J].软件学报，2012（1）：1-20.
[4]项亮.推荐系统实践[M].北京：人民邮电出版社，2012.
[5]朱郁筱，吕琳媛.推荐系统评价指标综述[J].电子科技大学学报，2012（2）：163-175.
Research on recommendation method based on link prediction
Ding Yi
（Computing School of Wuhan Vocational College of Software and Engineering, Wuhan 430205, China）
The recommendation system in the digital environment can provide valuable services, and has achieved great commercial success in books, movies, music and other online industries. Most recommendation system adopt collaborative fi ltering algorithm, which reasons out users’ interests and preference through the interactive behavior between users and items. The recommendation effect of collaborative fi ltering algorithm has been greatly influenced by the data sparsity problem. Ιn order to solve this problem, this paper uses method on the basis of graph to explore the interaction between a user and item. This paper applies two network link prediction method to recommend items for users, and makes a comparison w ith the collaborative fi ltering method. According to the experimental results on the bean data set, it shows that the link prediction method is better than the standard collaborative fi ltering method
recommendation system; collaborative fi ltering; link prediction
武汉市市属高校产学研项目；项目编号：201310。
丁沂（1978－ ），男，湖北武汉，硕士，教师；研究方向信息检索，推荐系统。
