基于链路预测的推荐方法研究.docx

基于链路预测的推荐方法研究

丁沂

【摘要】推荐系统在数字化环境中能够提供有价值的服务,并且在图书、电影和音乐等在线产业中取得了巨大的商业成功.大多数推荐系统采用协同过滤算法,通过分析用户和物品之间的交互行为推理用户的兴趣和偏好.协同过滤算法的推荐效果受到数据稀疏性问题的影响很大.为了解决这个问题,文章使用一种基于图的方法探索用户和物品之间的交互.文章采用二分网络链路预测的方法对用户进行物品推荐,并与协同过滤方法进行了比较,通过在豆瓣数据集上的实验结果表明,基于链路预测的方法比标准的协同过滤方法要好.

【期刊名称】《无线互联科技》

【年(卷),期】2017(000)008

【总页数】2页(P99-100)

【关键词】推荐系统;协同过滤;链路预测

【作者】丁沂

【作者单位】武汉软件工程职业学院计算机学院,湖北武汉430205

【正文语种】中文

近年来，通过向潜在的用户推荐商品、服务和信息，推荐系统在很多领域得到了广泛的应用。推荐系统中最关键部分是推荐算法。推荐算法通常利用用户和物品的属性或者用户和物品之间的交互（打分行为、浏览行为、购买行为等）预测用户对某个物品的偏好[1]。协同过滤算法是推荐系统中最成功也是被关注最多的算法，这个算法依赖用户和物品之间的交互数据进行推荐。标准的协同过滤算法首先找到目标用户的邻居，寻找邻居的方法并不是使用与目标用户属性相似的用户，而是使用与目标用户具有相似行为的用户，然后根据目标用户邻居的经验对目标用户进行推荐。尽管协同过滤算法在业界取得了巨大的成功，但是协同过滤算法的效果受到数据稀疏性的影响很大，因为没有足够的历史行为数据用来帮助找到目标用户的邻居。为了解决这个问题，人们使用一种基于图的算法来探索用户和物品之间的交互行为。从二分网络的观点来看，推荐问题可以看作为每个用户节点选择未观测到的边的过程。因此，可以使用二分网络链路预测的方法对推荐问题进行建模[2]。

二分网络又叫二部图，是一种具有特殊结构特征的网络。一个简单的二分网络G(V,E)存在一对节点集合X和Y，并且满足E中任意一条连边一定恰有一个顶点在集合X中，另一个顶点在集合Y中。现实世界中很多复杂的系统具有二分结构，可以用二分网络进行建模。例如，新陈代谢网络可以视为是以化学物质和化学反应为两个分离集合的二分网络，合作网络可以看作以参与者和事件为两个分离集合的二分网络，互联网是以电脑和网络设备为两个分离集合的二分网络，开源社区是以开发者和软件项目为两个分离集合的二分网络，电子商务是以用户和商品为两个分离集合的二分网络，异性的性关系网络是以男性和女性为两个分离集合的二分网络，人类疾病网络是以身心机能失调表现和致病基因为两个分离集合的二分网络。二分网络具有很多网络不具备的性质。比如，二分网络都不包含长度为奇数的圈，因此，一个包括长度为奇数的圈的网络肯定不是一个二分网络；另外，二分网络都是可以二着色的并且二分网络的谱具有对称性等等。由于二分网络具有这些特征，因此针对一个节点规模为N的无向简单网络，可以以线性时间复杂性0(N)判断该网络是不是一个二分网络。

网络分析方法近年来广泛应用在复杂系统的研究中，例如，Internet，WWW、社会网络和基因网络。链路预测是网络建模中的一个重要问题，在社会网络、基因网络和引文网络中受到广泛关注。二分网络中的链路预测与推荐系统比较相似，二分网络的链路预测是指如何通过已知的网络节点及网络结构等信息，预测网络中尚未产生连边的两个节点之间产生连边的可能性，既包含对未知连边的预测，也包含对未来连边的预测[3]。应用社会网络链路预测中的三个连边权重指标，采用用户和物品交互图的建模方法对用户进行推荐。

在二分网络G中，用户和物品代表两种不同类型的节点，不同类型节点之间的连边代表用户和物品之间的交互。由于我们研究的是基于事务的协同过滤问题，二分网络中的连边是没有权重的，而且整个二分网络代表了输入数据的全部信息。基于二分网络G的拓扑结构，我们可以为二分网络中每一对未连接用户-物品节点对u，i计算相应的权重w(u，i)。这个权重可以作为该节点对的一个候选得分，用来评估节点u和节点i之间连边的概率，从而对用户进行推荐[4]。

在经典网络链路预测中有很多连边权重的度量指标，在二分网络中连边权重的度量指标相对较少。因此，修改了3个经典网络中的连边权重度量指标并应用在二分网络中。如表1所示，本文对于节点x，我们定义为节点x的邻居集合Nh。

这3个连边权重指标都是基于邻居的相似性度量指标。Commonneighbors指标表示二分网络中两个节点共同邻居的数量；Jaccard指标和Commonneighbors指标类似，不仅考虑了两个节点共同邻居的数量，还考虑到了两个节点各自的邻居数目；Delta指标考虑到了两个节点邻居数量不均