《单源SimRank计算优化及其在协同过滤中的应用.pdf》由会员分享，可在线阅读，更多相关《单源SimRank计算优化及其在协同过滤中的应用.pdf（2页珍藏版）》请在三一文库上搜索。
1、单源单源 SimRankSimRank 计算优化及其在协同过滤中的应用计算优化及其在协同过滤中的应用 图作为一种表达对象与对象之间抽象关系的非线性数据结构,具有更加一般 化的表达能力,在我们现实生活中扮演者重要的角色。 近年来,随着互联网、 云计 算、 物联网等技术的高速发展,数据增长的规模正在以前所未有的速度增加,“大 数据”给各行各业带来了很大的机遇和挑战,同时图数据的规模也随着个性化推 荐、信息检索、社交网络分析等应用的蓬勃发展变得越来越大。随着图数据规模 的增大,人们发现庞大的图数据中蕴含着巨大的商业价值,基于图结构的各种互 联网应用在近些年来层出不穷,在这些应用中,最典型和最基本的一
2、类任务就是 计算对象和对象之间的相似度。 SimRank 是一种非常流行的基于图拓扑结构信息来衡量任意两个对象之间 相似程度的模型,其核心的思想为:一个对象应该与自身最相似,如果两个对象都 被相似的对象所引用,那么这两个对象也相似。 然而,由于 SimRank 定义的递归依 赖性,导致了 SimRank 计算的时空复杂度很大,图数据规模的增大在另一方面也 使得问题更加突出。 在本文中,我们主要针对单源节点 SimRank 的计算,即给定一 个查询顶点,返回该节点与所有其他节点间的相似度,提出并实现了一种称之为 ProbeWalk 的高度并行的算法。 我们的方法是基于随机游走模型改进并优化的,它
3、由离线索引过程和在线查 询过程组成。 通过两个过程的组合可以将传统的双向随机游走过程转化为单向随 机游走过程,索引阶段的处理需要消耗线性的时间和空间,而单源节点的查询阶 段只消耗常数时间和空间。我们将算法部署到流行的分布式计算平台 Spark 上, 结果表明了我们的算法具有较高的准确性和高效性。 更进一步,相似度度量是协同过滤中的重要组成部分,为了解决传统的相似 度度量方法在协同过滤中效果较差和 SimRank 不能直接应用于带权二部图的问 题,本文进一步将 SimRank+引入到协同过滤中,提出了一种基于两阶段蒙特卡 洛模拟的随机游走方法,使其能够在较大规模协同过滤问题中进行应用。实验表 明,基于 SimRank+的协同过滤在 MovieLens 数据集上的评分预测误差要优于 Pearson 相关系数和 Cosine 相似度度量方法。