对分网络与推荐系统

对分网络与推荐系统

对分网络即bipartite network，是一个属于复杂网络研究的对象。在这篇文章里，作者第一次把它引入到推荐系统的应用当中。依我来看，这是一种非正统的推荐方法，又是去年新发表的文章，兼且我对作者的思路也有一些了解，所以想拿出来介绍一下。所谓正统的推荐方法，可以参考这里的概述。发展到现在，比较成熟常用的推荐方法主要可分类为：1、contented-based；2、collaborative filtering；3、hybrid method。又有以：基于个人历史的推荐、基于社会化的推荐、基于产品的推荐这样的分法。无一例外地，以描述用户的兴趣为出发点，通过不同的搜索策略，最后落脚于对用户未来兴趣的预测。与以往不同的是，这篇文章从开始就以网络模型为研究的基本对象，而非网络中的节点，出发点在于网络特性的研究，在解决了对分网络加权映射的问题之后，有点生产副产品意味地把方法应用在推荐系统上。作者是我的校友，在学期间我也曾经听过他的几次报告，他属于典型的具有理科思维的人。其物理背景加上一个研究复杂系统、复杂网络的团队，造就了作者喜欢从模型的高度，而非从具体某个问题出发思考的习惯。所以我觉得这篇文章对于冲淡以往已成定势的推荐系统思维方式，是有好处的。什么是对分网络如果我们把网络理解为描述现实世界对象间某种关系的数学模型，对分网络就是描述这样的一种特殊的关系：对象可以分为两个集合，如X与Y，关系（即网络的边）仅仅存在于不同集合的节点之间，同一个集合内的节点不存在直接连接，而是通过另一个集合而产生间接关联。这是一种具有广泛意义的模型，如不同作者通过共同撰写的文章所形成的合作关系；化学物质与化学反应所组成的新陈代谢网络；豆瓣上不同的读者因看一样的书而形成的阅读同好网络；amazon上不同用户因购买共同的商品所构成的购买兴趣网络等等。对分网络的单模态映射与赋权要使得对分网络具有应用价值，通常要得到同一个集合内元素之间存在的关系，研究上这叫作对X（或Y）的单模态映射（one-mode projection）。这种映射的结果不单可以实现数据的压缩，并可同时得到极具意义的同一集合内各节点之间的关系。例如，得到“阅读同好网络”中各个用户之间的兴趣相似度或是书籍之间的相似度，自然要比原始的对分网络更有价值。怎样给节点的连接边加权是单模态映射及其应用中关键的问题，因为边的权值意味着两个节点关系的密切程度。比较常见的映射方法可参看图1：对于集合X中的节点x(i)与x(j)，如果它们共同地连接了n个Y集中的节点，则x(i)与x(j)的连接权值为n。但这种方法存在着很多的问题，例如：x(i)与x(j)的连接权值随着n的增加而呈线性增长的趋势，但这并非一种符合现实的描述方式，其实我们可以设想两个作者共同合作的文章数从1增长到2，其意义当然是比从100增长到101要更大，所以有人提出要采用双曲正切函数而非线性函数来对n进行映射。这些方法我在这里都不再赘述，只介绍作者在文中提出的比较好的一个解决方案：资源－分配过程，来处理这个赋权的问题。                                                                图1，对分网络的单模态映射                        资源－分配过程（resource-allocation process）见图2，（a）是一个对分网络，上面的三个节点构成一个集合，下面的四个节点构成另一个集合。设上面三个节点的初始资源值为x, y, z，第一步这些资源根据连接关系流动到另一个集合中（b），流动过程中某节点的资源根据它的“出度”（即从该节点出发的边）而被稀释，如x有三个“出边”，则每一个终点都得到了x/3。在资源分配到下面四个节点后，第二步，把资源再流回原来的集合，遵循的原则与第一步是一致的。这样就得到了原集合最终的资源分配，这个分配是通过两个集合之间的共同连接关系所实现的再分配，携带了这个网络的拓扑结构信息。对比原资源与最终的资源值，我们可以得到一个矩阵的映射关系，见图3。这就是资源－分配过程的结果，得到一个从原始资源到最终资源的映射结果。矩阵中w(i, j)所代表的意义为：对于i来说，j有多大的价值。这实质上实现了给节点i与节点j的连接赋权这么一个任务。                                                                图2，资源－分配过程                                                                                        图3，资源－分配过程后的映射矩阵                        个性化推荐到目前为止，我们都只是解决了对分网络中权值分配这么一个问题，最后我们关注的是这么一个问题的解决对于推荐系统有些什么帮助。根据上面介绍的模型与流程，可以开始把数学抽象与实际问题结合起来了。现在我们考虑用户看电影这么一个网络，以用户作为一个集合U{u(1), u(2), u(3), … , u(m)}，电影条目作为一个集合O{o(1), o(2), o(3), … , o(n)}，根据某个用户看过某部电影的关系，我们可以连接两个集合中的对应节点（如果系统记录的是打分关系而非看过关系，可以对打分的分值进行分段处理，较大的分值有连接，较小的无连接），这样就形成了一个用户~电影的对分网络。下一步，要通过单模态映射来实现对用户的推荐。假设现在要对用户u(i)进行推荐，该用户看过电影的集合为Oi{o(j), o(j+1), o(j+2), …}，如果不考虑电影之间的差别，可以给每一个Oi中的电影都赋予一个初始的资源值1，不在Oi中的电影则资源值为0。接下来根据上一节介绍的资源－分配过程，让O中的资源从O流向U，再从U流回O。这样我们可以得到一个从原始O的资源值到最终O的资源值的一个映射矩阵，就像图3那个矩阵一样。不同的是，现在每一个O都有一个初始的资源值，而不是一个抽象的符号，所以我们可以计算得到每一个O节点的资源值。最后把所有O节点根据资源值的大小进行排序，把资源值高的并且未为U(i)所看过的电影推荐给他。即完成对一个用户的推荐。讨论这种方法来自于复杂网络的研究（用于推荐时作者称该方法为Network-Based Inference, NBI），在某些方面却与协同过滤（CF）有着异曲同工之妙，都是利用一个同好网络进行社会化的推荐。相比而言，CF的原理更为直接，从矢量计算的角度来理解显得很简单明了。NBI本质上也利用用户之间的共同兴趣对条目进行划分，但其基础是网络的动力学，看起来并不那么地直观（但喜欢动态变化的人会觉得这个很优美）。据作者对一个标准数据集的测试结果声称，NBI在预测性能上相比于CF存在着优势。

2008-10-12 23:53:42: 张沈鹏 (yying)

2008-10-12 23:56:48: 张沈鹏 (yying)

2008-10-12 23:59:34: scallet (清明 新坟与烈酒)

2008-10-13 00:05:24: 张沈鹏 (yying)

2008-10-13 00:06:33: 张沈鹏 (yying)

2008-10-13 00:20:47: 张沈鹏 (yying)

2008-10-13 09:01:33: Once (攻城师，伪球迷)

2008-11-13 14:50:57: NullPointer (绿荫下那嘹亮的花束唱起洁白的歌)

2008-11-13 15:07:15: NullPointer (绿荫下那嘹亮的花束唱起洁白的歌)

2008-11-13 16:20:08: Once (攻城师，伪球迷)

2008-11-13 18:12:14: 叫我F

2008-11-28 17:27:20: Shakey

2010-04-02 15:23:47: 咚咚咚 (相信思想和技术的力量)

2010-04-02 15:50:59: Once (攻城师，伪球迷)

2010-04-09 10:12:07: 暴君祥子

2010-04-13 13:13:36: wewe (每天都满满的阳光)

2010-04-13 13:55:55: Once (攻城师，伪球迷)

2010-04-14 10:21:51: wewe (每天都满满的阳光)

2010-04-14 10:33:03: Once (攻城师，伪球迷)