• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

simrank算法

bigdata admin 2年前 (2017-08-04) 2050次浏览 0个评论 扫描二维码

1. SimRank 推荐算法的图论基础

SimRank 是基于图论的,如果用于推荐算法,则它假设用户和物品在空间中形成了一张图。而这张图是一个二部图。所谓二部图就是图中的节点可以分成两个子集,而图中任意一条边的两个端点分别来源于这两个子集。一个二部图的例子如下图。从图中也可以看出,二部图的子集内部没有边连接。对于我们的推荐算法中的 SimRank,则二部图中的两个子集可以是用户子集和物品子集。而用户和物品之间的一些评分数据则构成了我们的二部图的边。

2. SimRank 推荐算法思想

对于用户和物品构成的二部图,如何进行推荐呢?SimRank 算法的思想是,如果两个用户相似,则与这两个用户相关联的物品也类似;如果两个物品类似,则与这两个物品相关联的用户也类似。如果回到上面的二部图,假设上面的节点代表用户子集,而下面节点代表物品子集。如果用户 1 和 3 类似,那么我们可以说和它们分别相连的物品 2 和 4 也类似。

如果我们的二部图是G(V,E)G(V,E),其中 V 是节点集合,E 是边集合。则某一个子集内两个点的相似度s(a,b)s(a,b)可以用和相关联的另一个子集节点之间相似度表示。即:

$$ s(a,b) = \frac{C}{|I(a)||I(b)|}\sum\limits_{i=1}^{|I_(a)|}\sum\limits_{j=1}^{|I_(b)|}s(I_i(a),I_i(b))$$

其中 C 是一个常数,而I(a),I(b)I(a),I(b)分别代表和 a,b 相连的二部图另一个子集的节点集合。s(Ii(a),Ii(b))s(Ii(a),Ii(b))即为相连的二部图另一个子集节点之间的相似度。

一种特殊情况是,自己和自己的相似度,我们定义为 1。即s(a,a)=1s(a,a)=1。还有一种特殊情况是I(a),I(b)I(a),I(b)有一个为空,即 a,b 中某一个点没有相连的另一个子集中的点,此时s(a,b)=0s(a,b)=0,将这几种情况综合下,则二部图一个子集内两个点的相似度s(a,b)s(a,b)可以表示为:

\begin{align}

s(a,b)= \begin{cases} 1 & {a = b}\\ \frac{C}{|I(a)||I(b)|}\sum\limits_{i=1}^{|I_(a)|}\sum\limits_{j=1}^{|I_(b)|}s(I_i(a),I_i(b)) & {a \neq b, I(a) \neq \emptyset, I(a) \neq \emptyset}\\ 0 & {otherwise} \end{cases}

\end{align}

如果我们想用上式直接计算两个物品或者两个用户之间的相似度是比较困难的,一般需要通过迭代方式计算。对于ab,I(a),I(a)a≠b,I(a)≠∅,I(a)≠∅时,我们注意到:
s(a,b)=C|I(a)||I(b)|i=1|I(a)|j=1|I(b)|s(Ii(a),Ii(b))=C|I(a)||I(b)|i=1Nj=1Npias(a,b)pjbs(a,b)=C|I(a)||I(b)|∑i=1|I(a)|∑j=1|I(b)|s(Ii(a),Ii(b))=C|I(a)||I(b)|∑i=1N∑j=1Npias(a,b)pjb

其中 p 为二部图关联边的权重,而 N 为二部图节点数。

上面的式子可以继续转化为:

s(a,b)=Ci=1Nj=1N(piai=1Npia)s(a,b)(pjbj=1Npjb)s(a,b)=C∑i=1N∑j=1N(pia∑i=1Npia)s(a,b)(pjb∑j=1Npjb)

如果用矩阵表示,则相似度矩阵S=CWTSWS=CWTSW, 其中WW是将权重值 p 构成的矩阵PP归一化后的矩阵。

但是由于节点和自己的相似度为 1,即我们的矩阵 S 的对角线上的值都应该改为 1,那么我们可以去掉对角线上的值,再加上单位矩阵,得到对角线为 1 的相似度矩阵。即:

S=CWTSW+IDiag(diag(CWTSW))S=CWTSW+I−Diag(diag(CWTSW))

其中diag(CWTSW)diag(CWTSW)是矩阵CWTSWCWTSW的对角线元素构成的向量,而Diag(diag(CWTSW))Diag(diag(CWTSW))将这个向量构成对角矩阵。

只要我们对 S 矩阵按照上式进行若干轮迭代,当 S 矩阵的值基本稳定后我们就得到了二部图的相似度矩阵,进而可以利用用户与用户的相似度度量,物品与物品的相似度度量进行有针对性的推荐。

3. SimRank 算法流程

现在我们对 SimRank 算法流程做一个总结。

输入:二部图对应的转移矩阵 W,阻尼常数 C,最大迭代次数 k

输出:子集相似度矩阵 S:

1) 将相似度 S 的初始值设置为单位矩阵 I.

2) 对于 i=1,2…k:

a) temp=CWTSWtemp=CWTSW

b) S=temp+IDiag(diag(temp))S=temp+I−Diag(diag(temp))

以上基于普通的 SimRank 算法流程。当然,SimRank 算法有很多变种,所以你可能看到其他地方的 SimRank 算法描述或者迭代的过程和上面的有些不同,但是算法思想基本和上面相同。

SimRank 算法有很多改进变种,比较著名的一个改进是 SimRank++算法。

4. SimRank++算法原理

SimRank++算法对 SimRank 算法主要做了两点改进。第一点是考虑了边的权值,第二点是考虑了子集节点相似度的证据。

对于第一点边的权值,上面的 SimRank 算法,我们对于边的归一化权重,我们是用的比较笼统的关联的边数分之一来度量,并没有考虑不同的边可能有不同的权重度量,而 SimRank++算法则在构建转移矩阵 W 时会考虑不同的边的不同权重值这个因素。

对于第二点的节点相似度的证据。回顾回顾上面的 SimRank 算法,我们只要认为有边相连,则为相似。却没有考虑到如果共同相连的边越多,则意味着两个节点的相似度会越高。而 SimRank++算法利用共同相连的边数作为证据,在每一轮迭代过程中,对 SimRank 算法计算出来的节点相似度进行修正,即乘以对应的证据值得到当前轮迭代的的最终相似度值。

5. SimRank 系列算法的求解

由于 SimRank 算法涉及矩阵运算,如果用户和物品量非常大,则对应的计算量是非常大的。如果直接用我们第二节讲到了迭代方法去求解,所花的时间会很长。对于这个问题,除了传统的一些 SimRank 求解优化以外,常用的有两种方法来加快求解速度。

第一种是利用大数据平台并行化,即利用 Hadoop 的 MapReduce 或者 Spark 来将矩阵运算并行化,加速算法的求解。

第二种是利用蒙特卡罗法(Monte Carlo, MC)模拟,将两结点间 SimRank 的相似度表示为两个随机游走者分别从结点 a 和 b 出发到最后相遇的总时间的期望函数。用这种方法时间复杂度会大大降低,但是由于 MC 带有一定的随机性,因此求解得到的结果的精度可能不高。

6. SimRank 小结

作为基于图论的推荐算法,目前 SimRank 算法在广告推荐投放上使用很广泛。而图论作为一种非常好的建模工具,在很多算法领域都有广泛的应用,比如我之前讲到了谱聚类算法。同时,如果你理解了 SimRank,那么 Google 的 PageRank 对你来说就更容易理解了。


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明simrank 算法
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!