上一次讲了《相似度计算方法：余弦相似度》中，提到了推荐系统中的基于用户的协同过滤算法，由于用户的行为数据，很适合用二分图的数据结构描述，因此很多图的算法可以在推荐系统中使用，专业人员称为 Graph based Model，基于图的模型，今天来看看基于图的推荐算法。
二分图
先来回顾下二分图这个数据结构
背书中
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图
通俗的讲
二分图就是在一个图中，将顶点集分成A和B，在这个图中，所有边的两个顶点都分别在顶点集A和B，顶点集A中的顶点不会连向顶点集A中的顶点，顶点集B中的顶点不会连向顶点集B中的顶点
灵魂画师上图了
二分图
看了图大家基本能回想起来二分图了，关于二分图还有匹配和求最大匹配的算法，以后在二分图的章节里面在说吧
用二分图描述用户行为数据
使用电商系统做为业务背景，顶点集A为用户顶点集，顶点集B为商品顶点集用新的图，顶点之间的边代表用户关注过商品，构成一个简单的用户关注商品的二分图
简单的用户关注商品的二分图
比如说A1顶点连着B1、B4、B5代表着用户A1关注过B1、B4、B5商品。
基于图的推荐算法
构建了简单的用户关注商品的二分图后，再来看看怎么在二分图上给用户进行个性化推荐，就拿A1用户做例子，用户顶点A1连着商品顶点B1、B4、B5，代表着用户A1关注过B1、B4、B5商品，没有关注商品B2、B3、B6、B7，要研究的问题就是给用户A1推荐商品B2、B3、B6、B7的时候，哪个最应该被推荐
给用户推荐商品的问题转化
有了二分图，给用户推荐商品的问题就可以转化一下，可以通过计算用户顶点和该顶点之间没有边的商品顶点之间的相关性，给A1用户推荐商品，就是计算A1顶点与B2、B3、B6、B7商品顶点之间的相关性，相关性越高，就越应该推荐给用户A1。
求A1顶点与B2、B3、B6、B7商品顶点之间的相关性
一般影响到图顶点相关性的因素主要有以下几点：
1.两个顶点之间的路径数；
2.两个顶点之间的路径长度；
3.两个顶点之间的路径经过的顶点。
而高相关性的两个顶点一般具有的特征是：
1.两个顶点之间的路径数比较多；
2.两个顶点之间的路径长度比较短；
3.两个顶点之间的路径不会经过出度比较大的顶点。
关键点是顶点之间的路径
求A1顶点与B2、B3、B6、B7商品顶点之间的路径
重新看图
1.A1顶点与B2顶点之间的路径
尴尬画这个图的时候没有考虑以后的内容。。A1与B2之间没有路径
2.A1顶点与B3顶点之间的路径
A1→B5→A6→B3
没看花眼的话就这么一条路径，那么A1与B3之间有1条路径，A1与B2之间没有路径，那么显然，A1与B3的相关性要高于A1与B2之间的相关性，推荐列表里面B3排在B2之前（四个都要推荐的情况下，也可以B2直接不推荐）
3.A1顶点与B6顶点之间的路径
a.A1→B1→A2→B6
b.A1→B5→A6→B6
A1顶点与B6顶点之间有两条路径a、b，那么显然A1与B6的相关性要高于A1与B3之间的相关性。
再来对比两条路径的长度，两条路径的长度都是4
再来对比他们经过的顶点，路径a经过顶点的出度为：3、2、2、3，路径b经过顶点的出度为：3、3、3、3，路径b经过的B5、A6顶点的出度大，所以对于A1与B6之间的相关性的共享，a路径要大，业务上也可以这么解释，给用户A1推荐商品B6的时候，路径b经过被更多人所喜爱的商品B5，与爱好面更大的用户A6，所以路径b推荐商品B6给A1的准确性没有路径a的高，可以这么理解
4.A1顶点与B7顶点之间的路径
A1顶点与B7顶点之间的路径就留给读者自己练习吧，其实是我图没有画好，眼睛看花了，算不下去了。。
随机游走算法
基于上面这三个因素，计算图的顶点之间的相关性，已经有很多算法被研究了出来，这里简单介绍下随机游走算法，算法原理就不展开说了，就背背书吧
随机游走算法背书中
给用户A1进行商品推荐，可以从用户顶点A1开始在用户关注商品的二分图上进行随机游走。走到任何一个节点上时，按照概率α决定继续游走，还是停止游走并从A1顶点开始重新游走。如果决定继续游走，那么就要从当前顶点指向的顶点中按照均匀分布随机选择一个顶点作为游走要经过的顶点。这样，经过多次随机游走后，每个商品顶点被访问到的概率会收敛到一个数上，顶点之间的相关性就可以用商品顶点被访问到的概率描述，公式如下：
随机游走算法公式
这个算法的实现大家自行百度吧。
基于图的推荐算法就为大家分享到这里，欢迎大家来交流，指出文中一些说错的地方，让我加深认识，愿大家没有bug，谢谢！
网友评论