基于二分网络双向扩散的个性化推荐方法
基于二分网络双向扩散的个性化推荐方法
【技术领域】
[0001] 本发明属于推荐系统领域，将网络传播的方法和目前备受关注的个性化推荐系统 相结合，具体是一种基于二分网络初始资源双向扩散的个性化推荐方法，可用于解决个性 化Top-N的推荐。
【背景技术】
[0002] 随着信息技术的快速发展，互联网时代的到来，人们的生活也发生了深刻而巨大 的变化。网络生活成为必不可少的部分，诸如网上商城，在线影院，网络书店等等，为人们的 生活带来了极大的便利，但与此同时，信息过载让人有些应接不暇，疲于在庞杂的信息当中 苦苦寻找对自己有用的信息，例如，Amazon的数百万本图书，Netflix的上十万部电影，豆 瓣、淘宝的形形色色商品更是不计其数，在这样规模的数量中找自己感兴趣的，无疑是个灾 难。在这个大数据到来的时代，有效而又高效的推荐系统研宄已经迫在眉睫。此外，除了电 子商务领域，推荐系统也被广泛应用在各行各业，像新闻推荐，旅游推荐，社交朋友推荐，甚 至论文评审推荐，招标项目推荐等等。
[0003] 传统的推荐方案只是给所有的用户提供近乎一模一样的推荐列表，且大多是司空 见惯的流行度很大的商品，无法根据用户个人身份、年龄和兴趣的差异来进行有目的针对 性的推荐，事实证明，在信息爆炸的时代，这样的推荐是十分低效的，不仅不能为商家获得 很好的销售业绩提供帮助，反而使得用户极其反感。由此，所谓个性化推荐应运而生，即充 分利用商家所掌握的巨大的用户历史数据，在此基础上进行分析过滤，深度挖掘个人的需 求和兴趣趋向，想用户所想，为不同的用户制定不同的推荐列表，用户通过自己的行为可以 改变推荐结果。
[0004] 优秀的个性化推荐系统为用户快速找到自己需要的合适信息提供了极大的方便， 同时让商家在众多的竞争者中脱颖而出，获得更大的点击量和销售额，据VentureBeat统 计，Amazon的个性推荐为其提高35%的销售业绩。个性化推荐系统在很多商业网站上已经 获得成功的应用，其中具有代表性的有Amzaon的电子商务推荐，Netflix和Movielens电影 推荐，Youtube和Hulu的视频推荐，Lastfm的音乐推荐，google的新闻推荐，Wanderfly的 旅游推荐，Facebook和Twitter的社交好友推荐以及国内的豆瓣电台，天猫商城，当当网， 优酷视频，人人网等等。Netflix还曾开出100万美元的巨奖来征集能够把他们网站上的推 荐结果提高10%的方法。
[0005] 自20世纪90年代以来，已经陆续有一些优秀的推荐系统方法被提出来，可以分为 以下几类：协同过滤系统；基于内容的推荐系统；混合的推荐系统；基于社交网络的推荐系 统。其中主要的思想都是根据用户或者物品的相似性来进行的推荐，通过牺牲推荐列表的 这样相同的物品有很大概率被推荐给众多不同的用户，以至于推荐列表很大的相似性，所 推荐的大部分物品又是流行商品。
[0006] 商品销售往往是具有"马太效应"的，即多的越多，少的越少，这就导致物品流行度 的分布成长尾式，处于流行度大的物品种类逐渐递减，数量上占大多数的不流行物品就被 称作长尾商品。理想的个性化推荐系统应该关注的不仅仅是推荐结果的正确性，同样重要 的还有其长尾挖掘的能力，即把不太惹人注目的商品恰到好处的推荐给需要的人群。如果 一个推荐系统通过推荐大量相似度很大的列表给用户，从而保证其正确率，显然是不符合 个性化需求的，用户也会很反感商家为什么给自己推荐这么多相似的东西，而那些不怎么 "招人喜欢"的商品则看起来很能保证销量。为了衡量这种冲突，用推荐结果的准确性，多样 性和新颖度来综合评价一个算法的好坏才是合理的。
[0007] 正是由于传统算法糟糕的多样性和新颖度指标，基于网络结构的推荐方法近些年 兴起，基于网络的算法不考虑用户和产品的内容特征，仅仅把其用户和物品看作抽象节点， 通过节点间信息的相互传递来确定用户节点对所有物品的联系，所有算法所利用的信息都 藏在用户和物品的选择关系之中。一种基于二分网络的推荐的混合算法（HPH)在"Solving theapparentdiversity-accuracydilemmaofrecommendersystems''(Proceedingsof theNationalAcademyofSciencesoftheUSA-PNAS107(10) ;4511_4515,2010)中被 Zhou等提出，这种方法尝试将两种特色鲜明的二分图推荐算法混合，通过调节两者重要性 的因子找到长尾挖掘和推荐准确性的折中方案。实验证明，恰到好处的为用户推荐一些不 流行的长尾商品能够得到比一味推荐流行度较大的方案更高的准确率，与此同时，推荐结 果的多样性和新颖度指标也会达到不错的效果。针对这种方法，有不少文献在其后给出一 些改进的方案来进一步优化推荐的结果。
[0008] 另一种基于二分网络的推荐方法由Liu等在"informationfilteringvia biasedheatconduction"（PhysicalreviewE84,037101，2011)中提出，这是一种在基 于二分网络的热传导算法基础上改进的方法（BHC)。基于二分网络的热传导算法（Heats) 是模拟初始资源分配的过程提出的推荐算法，该算法由于对流行的物品的影响进行了较大 程度的抑制，导致推荐结果过多的呈现出长尾物品，从而有很好的新颖度和糟糕的准确性， 这意味着推荐结果不能很好预测用户的需求，纵使良好的商品覆盖率，它并不能直接作为 推荐结果给用户。Liu在这个方法基础上通过调节流行物品影响因子来使原来的算法以牺 牲部分新颖度获得较好的准确性和多样性，设置合理的参数后，推荐结果有不错的效果。
[0009] 本发明是在借鉴先前研宄成果的基础上，对基于二分网络的热传导算法进行了完 善改进，在调节推荐结果的流行性分布过程中，对推荐系统三个重要指标都有了显著的提 高。该发明能够为用户提供了体验更好的推荐结果。
【发明内容】
[0010] 本发明的目的在于针对Heats方法推荐结果糟糕的准确率，提出一种基于二分网 络双向扩散的方法，在准确性、多样性和新颖度之间找到折中方案，以获得更好的推荐结 果，同时改善推荐系统中的冷启动问题，实现Top-N的推荐，即为每个用户提供一份含有N 个商品的推荐列表。为了方便叙述，这里假设本方法应用于电子购物网站，为用户推荐有可 能感兴趣的商品。
[0011] 本发明的技术方案是：将用户-物品之间的历史记录构造为简单二分网络，通过 用户节点和物品节点间的连线来表示该用户是否对该物品发生过购买行为。因为推荐算法 的根本目的是预测用户对未购买的物品的兴趣程度，在二分网络结构中，我们通过初始资 源的重新配置来估计目标用户对未购买物品的兴趣程度，类似于三步的随机游走的过程， 假设每个节点都有某种可分的资源，可以按一定比例分配给自己喜欢的其它节点对象，通 过相连节点资源的不断扩散，达到重新分配，从而建立没有直接联系节点间的关系。
[0012] (1)构造用户-物品的二进制矩阵A，只考虑购买关系，诸如购买次数、购买时间、 物品标签等等其它信息不纳入考虑范围。如果一个物品j曾经被用户i购买过，则au= 1 ; 否则％= 0。并由此建立用户-物品的二分网络，假设物品数量为n，用户数量为m;
[0013] (2)计算物品间二阶关联性：
[0014] 设初始状态下的二分网络的所有物品节点和用户节点所包含资源数量均为0 :
[0015] 2a)从物品节点集合0中选择某一物品节点为初始激活的物品节点，并拥有1个单 位的资源，其它所有物品和用户节点未激活，资源数量为〇 ;
[0016] 2b) 1个单位资源从初始激活的物品节点向与它相连的用户节点扩散，用户节点接 受的资源数量等于与它相连物品节点所拥有资源总量的平均数；
[0017] 2c)到达用户节点的资源再返回所有物品节点，物品节点接受的资源数量等于与 它相连用户节点所拥有资源总量的平均数；
[0018] 通过某一初始激活物品节点一用户节点一物品节点的扩散过程，这样原先资源数 量为0的物品节点得到一定数量资源，得到资源数量越多的物品节点，视为与初始激活的 物品节点越相似；依次选择不同的初始激活的物品节点，重复上面过程直到遍历完所有物 品节点集合0,即可得到物品-物品的二阶关联矩阵；
[0019] (3)计算用户间二阶关联性：
[0020] 设二分网络处于初始状态，初始状态下的二分网络的所有物品和用户节点所包含 的资源数量均为〇 :
[0021] 3a)从用户节点集合U中选择某一用户节点为初始激活的用户节点，并拥有1个单 位的资源，其它节点未激活，资源数量为〇 ;
[0022] 3b) 1个单位的资源从初始激活的用户节点向与它相连的物品节点扩散，物品节点 接受的资源数量等于与它相连用户节点所拥有资源总量的平均数；
[0023] 3c)到达物品节点的资源再返回所有用户节点，用户节点接受的资源数量等于与 它相连物品节点所拥有资源总量的平均数；
[0024] 通过某一初始激活用户节点一物品节点一用户节点的扩散过程，这样原先资源数 量为〇的用户节点得到一定数量资源，得到资源数量越多的用户节点，视为与初始激活的 用户节点越相似；依次选择不同的初始激活的用户节点，重复上面过程直到遍历完所有用 户节点集合U，即可得到用户-用户的二阶关联矩阵；
[0025] (4)完成资源双向扩散过程：
[0026] 设二分网络处于初始状态，所有节点资源数量为0 :
[0027] 4a)正向资源扩散过程：
[0028] 对于某一目标用户节点ut，设与其相连接的物品节点均为初始激活状态，并各自 拥有一个单位数量资源，其它节点未激活，资源量为〇;然后基于步骤（2)计算得到的物品 之间的关联性，将这些初始激活物品节点的资源按比例配给所有物品节点；
[0029] 4b)逆向资源扩散过程：
[0030] 选择某一物品节点〇t，经过正向扩散后，该物品节点得到数量为r的资源；设与〇t 相连接的所有用户节点被激活，并各自拥有数量为的等量资源，X是调优参数；然后基 于步骤（3)计算得到的用户之间的关联性，将所有激活的用户节点所拥有的资源按比例分 配给所有用户节点；用户节点ut得到的从物品节点〇t反馈回的资源数量表征用户ut对物 品〇t的感兴趣的程度；
[0031] 4c)依次选取集合0中其它物品节点，完成4b)的过程，直到遍历完所有物品节点， 得到用户ut对所有物品的感兴趣的程度列表；
[0032] 4d)依次选取集合U中其它用户节点，完成4a)~4c)的过程，直到遍历完所有用 户节点，得到所有用户对所有物品的感兴趣程度，用mXn的矩阵M记录下来；
[0033] (5)给出对应于每个用户的长度为N的物品推荐列表：N的大小依据实际需要确 定，表示为每个用户提供N个推荐物品，为每个用户推荐N个没有购买过的兴趣值排行靠前 的物品；
[0034] 本发明与现有技术相比具有如下优点：
[0035] 第一，准确性提高。在仅利用用户-物品购买与否的历史纪录情况下，不考虑进一 步的二阶冗杂信息剔除，本发明得到的推荐系统具有更高的推荐准确率，在预测用户需求 方面更加准确。
[0036] 第二，多样性和新颖度提高，较好的长尾商品挖掘能力。本发明在不损失准确率， 甚至有所提高的前提下，使得推荐结果有更好的多样性和新颖度，可以更高效将数量上占 绝大多数的不流行物品恰到好处的推荐给有需求的人群，改善了用户对推荐商品列表的体 验。
[0037] 第三，改善了推荐系统中的冷启动问题，在本算法过程中不仅用到物品-物品之 间的关联，还囊括了用户-用户的关联信息，这样新物品一旦被某个用户购买，会迅速推广 给其他用户，同时新用户一旦购买了某件物品，也可以迅速为其提供合适的推荐列表。
【附图说明】
[0038] 图1为本发明的流程示意图；
[0039] 图2为本发明用于MovieLens和Netflix的调节参数A选择；
[0040] 图3为本发明在10000X6000的Netflix数据集上得到推荐结果分布图；
[0041] 图4为本发明与现有的基于二分网络推荐系统方法的性能比较。
【具体实施方式】
[0042] 将本发明的流程思想通过矩阵运算，避免复杂的迭代过程，得到比较清晰明了的 具体实施方法。本发明的实现步骤如下：
[0043] 步骤1，根据用户的历史行为记录来构建用户-物品的二分网络，用户的历史行为 记录包括用户购买物品的记录或者用户对物品的评价记录：
[0044] 设用户节点11={111，112，...，11111}，1]1为用户的数目，物品节点0={〇 1，〇2，...，〇11}，11 为物品的数目，Re记录用户和物品之间的交互关系，只考虑用户是否购买或评价过物品的 一兀关系；
[0045] 构建用户-物品的二分网络的图模型，其中用户节点与用户节点之间无连接，物 品节点与物品节点之间也没有连接，只在发生过交互关系的用户节点与物品节点之间建立 连接，即在Re中有记录的<U，0>。用二元矩阵AmXn= (aij)mXn来存储该二分网络中的连接 信息，其中
[0047] <Ui，〇j>表示第i个用户节点与第j个物品；au是二元矩阵AmXl^i行第j列 的元素；
[0048] 步骤2,建立物品-物品及用户-用户的二阶关联矩阵：
[0049] 2a)计算物品-物品间的二阶关联矩阵：
[0051] 其中
，表示物品节点〇〇的出度，即流行度
，表示 用户节点％的出度，即用户活跃度；ala，alfi对应矩阵六^^中的元素；m表示用户的数量， 用来衡量物品〇a和〇e的关联程度；通过计算n个物品任意两个之间的关联程度，可得 到nXn维的物品关联矩阵WH;
[0052] 2b)计算用户-用户二阶关联矩阵：
[0054] 其中
，表示用户节点up的出度，即用户活跃度；
表示物品节点〇a的出度，即流行度；apa, 对应矩阵AmXn中的元素；n表示物品的数量； 用来衡量用户ujPuq的关联程度；通过计m个用户任意两个之间的关联程度，可得到 mXm维的物品关联矩阵WTH;
[0055] 步骤3,完成双向扩散过程：
[0056] 3a)完成正向扩散过程：
[0057] R=AmXnX(ffH)T
[0058] 矩阵R为mXn维的矩阵，记录经过资源重新分配后物品节点从用户节点得到的资 源数量；
[0059] 3b)完成逆向扩散过程：
[0060] M=R? (WTHXAmXn)A
[0061] 矩阵M为mXn维的矩阵，记录逆向扩散后，用户节点从物品节点拿回的资源数量。 某一物品节点〇1反馈回给某一用户节点ut的资源数量越多，表明物品〇t和用户ut关联性 越强，即用户ut越有可能对物品0t感兴趣。
[0062] A是为了调整正向过程和逆向过程的比重来优化推荐结果的性能指标而引进的 参数，Ae[0，1]，X的大小取决于矩阵AmXn的稀疏程度，可以通过在用户的历史行为记录 的数据上测试来选择其最佳的值； [0063] 步骤4,给出每个用户的长度为N的推荐列表：
[0064] 4a)将最终的用户-物品兴趣度矩阵M每行按从大到小排列，即按兴趣程度的大 小，为每个用户都整理出他的兴趣表；
[0065] 4b)为每个用户推荐N个没有购买过的兴趣值排行靠前的物品。
[0066] 本发明的效果可以通过以下仿真进一步说明：
[0067] 1.仿真条件
[0068] 本实例在Intel(R)Core(TM)2DuoCPU2. 33GHzWindows7 (x64)系统下， Matlab2012a运行平台上，完成本发明与现有Heats，HNBI，HPH，BHC推荐算法的仿真实验。
[0069] 2.仿真实验内容
[0070] 为了验证本发明的实际效果，实验中选择两个推荐系统中著名的数据集做测试， 并同几个现有经典的基于二分网络的推荐方法做了对比。实验数据集一是MovieLens数据 (http://www.grouplens.org/)，由1682个部电影和943个用户组成。数据集二是Netflix 数据（ http://www.netflixprize.com/)，本实验数据随机抽取了其中10000个用户和6000 部电影的记录。这两个数据集都是1到5的评分稀疏矩阵，本发明关注的是Top-N的推荐 问题，所以本实验将数据集中评分不小于3的评分项视为用户喜欢，设为1 ;评分小于3的 评分项视为用户不喜欢这部电影，设为〇,我们为用户提供他可能喜欢的推荐电影列表。这 样变为了二进制的数据集，原本很稀疏的数据将更加稀疏，Movielens的用户喜欢的历史记 录有82520条，稀疏度为5. 20 ?lOlNetflix的用户喜欢的历史记录有642604条，稀疏度 为1. 07 ? 10_2。实验中将数据集随机拆成90%的训练集和10%的测试集，采取五次随机交 叉验证实验，实验结果推荐列表长度为50(N= 50)，也就是为每个用户推荐50个商品。
[0071] 用来评价一个推荐系统好坏的指标是其准确性，多样性和新颖度。准确性用准确 率和召回率表示，多样性和新颖度有很多的衡量方法。本实验采取下面的方法。
[0072] 准确率（Precision)衡量推荐列表预测出用户的下一步的购买行为的成功率，其 中m是用户数量，N是推荐列表中包含物品数量^(N)表示用户i的推荐列表中预测正确 的商品个数（和测试集对照）表示用户的数量。
[0074] 召回率（Recall)衡量推荐列表成功预测出的商品数量在用户下一步购买物品数 量中的比例，其中T表示测试集中的记录为1的数量，即用户下一步购买的商品数量;m表 示用户的数量。
[0076]多样性（Diversity)衡量推荐列表中物品的多样性，高效的个性化推荐系统会尽 量提供广泛的选择。其中表示为用户i和用户j推荐的相同物品数量；衡量用户i， j推荐表单的差异度；m表示用户的数量。
[0079] 新颖度（Novelty)衡量推荐列表中物品的不流行度，高效的个性化推荐系统会尽 量推荐一些不常见的物品给用户，也称作用户的惊喜度。其中kia表示为用户i所推荐物 品a的流行度；m表示用户的数量。
[0081] 图2(a)是在MovieLens数据集上优化A的过程，可已看出，当A取0.2时，推荐 系统的准确性达到最好，但对应的多样性和新颖度却不是最高，说明推荐系统的几个指标 是存在一些冲突关系的。由于实验旨在测试本发明在准确性不降低的前提下，多样性和新 颖度方面的表现，因此将A=0.2作为系统的最佳值。
[0082] 图2(b)是在Netflix数据集上优化A的过程，同理，将A=0.2作为系统的最 佳值，A的值和MovieLens数据集上测试集上相同，这是因为两个数据集稀疏度都是在1(T2 级，而A的值是与数据的稀疏程度相关的。
[0083] 图3(a)画出了商品长尾分布的特性，流行的商品数量占极少数，大部分商品属于 不流行的，且随着流行度的增加，商品数量递减。流行的商品用户很容易从各种渠道了解， 而不流行的则很难为大众所知，因此个性化推荐的一个重要目标就是把处于长尾的不流行 的商品挖掘出来推荐给合适的用户。
[0084] 图3(b)给出基于物品间关联性做推荐的结果分布图，也就是Heats方法的结果。 从图中很容易看出，这样推荐策略更加侧重推荐不流行的商品，结果的新颖度会很好，但是 准确率就很难保证了。糟糕准确率的一个推荐算法根本不能作为实际应用。由于正向过程 是基于物品的关联程度扩散的，所以这个过程对新用户的推荐有优势。
[0085] 图3 (c)给出反向扩散结束后，根据矩阵TR做出的推荐物品分布图，与正向过程相 反，它更多推荐了比较流行的物品，相对而言准确性会好一些，但新颖度和多样性比较差。 由于反向过程是基于用户的关联程度扩散的，所以这个过程的对新物品的推荐有优势。
[0086] 图3(d)给出基于用户间关联性做推荐的结果分布图，可以看出这个算法是找一 个平衡点，但并不是性能的妥协。实验结果证明，融合后的推荐结果准确率比单个过程都要 好，且多样性和新颖度也非常不错，这是因为融合的过程不仅仅是找到流行物品和不流行 物品的平衡，同时将物品之间、用户之间的信息都囊括在内。然而，如果将传统KNN协同过 滤也做这样的融合却达不到这样的效果，基于物品和基于用户的KNN推荐算法关注的都是 准确率而非新颖度，融合后性能只会介于单个算法之间。这也是基于网络的推荐算法的根 本优势，它能够将已有的信息通过网络扩散，使不流行的物品也散播给尽可能多的用户，而 基于邻域思想的协同过滤方法将初始信息资源约束在小范围内传播。
[0087] 图4给出了本方法和现有性能出色的基于二分网络的推荐算法之间的比较，本方 法表示为HBT，与PNAS上提出的经典的HPH方法比较，在MovieLens上准确性提高了 2. 4%， 多样性提升4. 0%，新颖度也有6. 1 %的提高；在Netflix数据集上测试，准确性有6. 0%的 提高，多样性和新颖性指标分别提升了 6. 8 %，3. 1 %。实验结果充分说明了本发明用于个性 化推荐系统的出色性能。
[0088] 总之，本发明在基于二分网络搭建的推荐系统方法，将用户和物品分别看做网络 中的两列抽象节点，利用网络传播扩散的原理，通过正反向的信息扩散及融合过程，找到准 确性、多样性和新颖性之间的契合点，同时将物品间和用户间的关联信息充分利用，最终得 到一个性能较已有方法更好的推荐系统。总之，本发明表现出很好的长尾商品挖掘能力，可 以应用于Top-N的推荐。
【主权项】
1. 一种基于二分网络双向扩散的个性化推荐方法，所述方法包括下列步骤： (1) 根据用户的历史行为记录来构建用户-物品的二分网络，用户的历史行为记录包 括用户购买物品的记录或者用户对物品的评价记录： 设用户节点集合U = Iu1, U2, ...，um}，m为用户的数目，物品节点集合O = {〇1，〇2, ...，〇η}，η为物品的数目，Re记录用户和物品之间的交互关系，该交互关系与用户的 历史行为记录对应，只考虑用户是否购买或评价过物品的二元关系。 构建用户-物品的二分网络的图模型，其中用户节点与用户节点之间无连接，物品节 点与物品节点之间也没有连接，只在发生过交互关系的用户节点与物品节点之间建立连 接；如果用户节点与物品节点发生过交互关系，则在Re中生成记录<U，0> ;用二元矩阵Amxn=h j) m x n来表示该二分网络中的连接信息，其中< Ui, 〇j>表示第i个用户节点与第j个物品；a u是二元矩阵Amxn第i行第j列的元 素； (2) 计算 物品间>阶关联性： 假设二分网络的所有节点均可以储藏一定量的资源，初始状态下的所有网络节点所含 资源数量均为〇 : 2a)从物品节点集合O中选择某一物品节点为初始激活的物品节点，并拥有1个单位的 资源，其它节点未激活，资源数量为〇 ; 2b)单位资源从初始激活的物品节点向与它相连的用户节点扩散，用户节点接受的资 源数量等于它相连物品节点所拥有总量的平均数； 2c)到达用户节点的资源再返回所有物品节点，物品节点接受的资源数量等于它相连 用户节点所拥有总量的平均数； 通过某一初始激活物品节点一用户节点一物品节点的扩散过程，这样原先资源数量为 〇的物品节点得到一定数量资源，得到资源数量越多的物品节点，视为与初始激活的物品节 点越相似。依次选择不同的初始激活的物品节点，重复上面过程直到遍历完所有物品节点 集合〇,即可得到物品-物品的二阶关联矩阵； (3) 计算用户间二阶关联性： 设二分网络处于初始状态，所有节点资源数量均为0 : 3a)从用户节点集合U中选择某一用户节点为初始激活的用户节点，并拥有1个单位的 资源，其它节点未激活，资源数量为0 ; 3b) 1个单位的资源从初始激活的用户节点向与它相连的物品节点扩散，物品节点接受 的资源数量等于与它相连用户节点所拥有总量的平均数； 3c)到达物品节点的资源再返回所有用户节点，用户节点接受的资源数量等于它相连 物品节点所拥有总量的平均数； 通过某一初始激活用户节点一物品节点一用户节点的扩散过程，这样原先资源数量为 〇的用户节点得到一定数量资源，得到资源数量越多的用户节点，视为与初始激活的用户节 点越相似。依次选择不同的初始激活的用户节点，重复上面过程直到遍历完所有用户节点 集合U，即可得到用户-用户的二阶关联矩阵； (4) 完成资源双向扩散过程： 设二分网络处于初始状态，所有节点资源数量为O : 4a)正向资源扩散过程： 对于某一目标用户节点ut，设与其相连接的物品节点均为初始激活状态，并拥有一个 单位数量资源，其它节点未激活，资源量为〇 ;然后基于步骤（2)计算得到的物品之间的关 联性，将这些初始激活物品节点的资源按比例配给所有物品节点； 4b)逆向资源扩散过程： 选择某一物品节点〇t，经过正向扩散后，该物品节点得到数量为r的资源；设与〇t相连 接的用户节点被激活，并各自拥有数量为1^的资源，λ是调优参数；然后基于步骤（3)计 算得到的用户之间的关联性，将所有激活的用户节点所拥有的资源按比例分配给所有用户 节点；用户节点Ut得到从物品节点〇 t反馈回的资源数量，用来表征用户u t对物品〇 t的感 兴趣的程度； 4c)依次选取集合0中其它物品节点，完成4b)的过程，直到遍历完所有物品节点，得到 用户Ut对所有物品的感兴趣的程度列表； 4d)依次选取集合U中其它用户节点，完成4a)~4c)的过程，直到遍历完所有用户节 点，得到所有用户对所有物品的感兴趣程度，用mXn的矩阵M记录下来； (5) 给出对应于每个用户的长度为N的物品推荐列表：N的大小依据实际需要确定，表 示为每个用户提供N个推荐物品； 5a)将最终的用户-物品兴趣度矩阵M每行按从大到小排列，即按兴趣程度的大小，为 每个用户都整理出他的兴趣表； 5b)为每个用户推荐N个没有购买过的兴趣值排行靠前的物品。2. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中步骤（1)所述的二 分网络是根据用户购买行为来确定的，二分网络只关心抽象节点间有无连接关系，是个没 有权值的网络，很多现有用户历史数据集以1-5评分给出的，这时将大于2的评分项视为喜 欢，即有连接；不大于2的评分项视为无连接。将现有处理过的用户历史行为数据随机分割 为90%的训练集和用于测试系统性能的10%的测试集。3. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中，在步骤（2)、（3)中 分别采用如下的方法建立物品-物品及用户-用户的二阶关联矩阵： (1) 计算物品-物品间的二阶关联矩阵：其中，表示物品节点〇α的出度，即流行度；，表示用户 节点U1的出度，即用户活跃度；a la，alfi对应矩阵A mXn中的元素；m表示用户的数量，用 来衡量物品Oc^Pofi的关联程度；通过计算η个物品任意两个之间的关联程度，可得到nXn 维的物品关联矩阵Wh; (2) 计算用户-用户二阶关联矩阵：其4，表示用户节Aup的出度，即用户活跃度；表示 物品节点Oa的出度，即流行度；apa, aqa对应矩阵Amxn中的元素；η表示物品的数量； 用来衡量用户ujP u ,的关联程度；通过计m个用户任意两个之间的关联程度，可得到mXm 维的物品关联矩阵W?。4. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中，步骤（4)采用如下 的方法建立： (1) 完成正向扩散过程： R = AmxnX (Wh)T 矩阵R为mXn维的矩阵，记录经过资源重新分配后物品节点从用户节点得到的资源数 量； (2) 完成逆向扩散过程： M = R. (WraXAmxn) λ 矩阵M为mXn维的矩阵，记录逆向扩散后，用户节点从物品节点拿回的资源数量。某 一物品节点〇,反馈回给某一用户节点u t的资源数量越多，表明物品〇 t和用户u t关联性越 强，即用户Ut越有可能对物品〇 ,感兴趣。 λ是为了调整正向过程和逆向过程的比重来优化推荐结果的性能指标而引进的参数， λ e [〇，1]，λ的大小取决于矩阵Amxn的稀疏程度，可以通过在用户的历史行为记录的数 据上测试来选择其最佳的值。5. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中所述的调优参数λ 取值是根据推荐方法的各方面的性能折中选择的，衡量个性化推荐系统的性能指标用以下 方法确定： 准确率（Precision)衡量推荐列表预测出用户的下一步的购买行为的成功率，其中m是用户数量，N是推荐列表中包含物品数量Wi(N)表示用户i的推荐列表中预测正确的商 品个数（和测试集对照）表示用户的数量。召回率（Recall)衡量推荐列表成功预测出的商品数量在用户下一步购买物品数量中 的比例，其中T表示测试集中的记录为1的数量，即用户下一步购买的商品数量;m表示用 户的数量。多样性（Diversity)衡量推荐列表中物品的多样性，高效的个性化推荐系统会尽量提 供广泛的选择。其中％表示为用户i和用户j推荐的相同物品数量；H 量用户i，j推 荐表单的差异度；m表示用户的数量。新颖度（Novelty)衡量推荐列表中物品的不流行度，高效的个性化推荐系统会尽量推 荐一些不常见的物品给用户，也称作用户的惊喜度。其中kia表示为用户i所推荐物品α 的流行度；m表示用户的数量。
【专利摘要】本发明公开了一种基于二分网络双向扩散的个性化推荐方法，针对Top-N的个性化推荐，主要解决了推荐列表的准确性，多样性及新颖度几个主要算法性能指标的冲突。其实现步骤为：(1)构建用户-物品关联的二分图网络。假设每个目标用户节点都有某种可分的资源，可以按预定分配机制分配给其它节点对象；(2)建立物品-物品及用户-用户的二阶关联矩阵；(3)完成双向扩散过程，得到用户-物品的兴趣矩阵；(4)给出每个用户的长度为N的推荐列表，完成Top-N的推荐。本发明基于网络传播的思想，效果明显好于经典的协同过滤方法，更好的实现了个性化推荐系统所关注的长尾挖掘，可用于解决个性化推荐的Top-N问题。
【IPC分类】G06Q30/02
【公开号】CN104899763
【申请号】CN201510230210
【发明人】马文萍, 焦李成, 冯翔, 马晶晶, 侯彪, 王爽, 其他发明人请求不公开姓名
【申请人】西安电子科技大学
【公开日】2015年9月9日
【申请日】2015年5月7日
【技术领域】
[0001] 本发明属于推荐系统领域，将网络传播的方法和目前备受关注的个性化推荐系统 相结合，具体是一种基于二分网络初始资源双向扩散的个性化推荐方法，可用于解决个性 化Top-N的推荐。
【背景技术】
[0002] 随着信息技术的快速发展，互联网时代的到来，人们的生活也发生了深刻而巨大 的变化。网络生活成为必不可少的部分，诸如网上商城，在线影院，网络书店等等，为人们的 生活带来了极大的便利，但与此同时，信息过载让人有些应接不暇，疲于在庞杂的信息当中 苦苦寻找对自己有用的信息，例如，Amazon的数百万本图书，Netflix的上十万部电影，豆 瓣、淘宝的形形色色商品更是不计其数，在这样规模的数量中找自己感兴趣的，无疑是个灾 难。在这个大数据到来的时代，有效而又高效的推荐系统研宄已经迫在眉睫。此外，除了电 子商务领域，推荐系统也被广泛应用在各行各业，像新闻推荐，旅游推荐，社交朋友推荐，甚 至论文评审推荐，招标项目推荐等等。
[0003] 传统的推荐方案只是给所有的用户提供近乎一模一样的推荐列表，且大多是司空 见惯的流行度很大的商品，无法根据用户个人身份、年龄和兴趣的差异来进行有目的针对 性的推荐，事实证明，在信息爆炸的时代，这样的推荐是十分低效的，不仅不能为商家获得 很好的销售业绩提供帮助，反而使得用户极其反感。由此，所谓个性化推荐应运而生，即充 分利用商家所掌握的巨大的用户历史数据，在此基础上进行分析过滤，深度挖掘个人的需 求和兴趣趋向，想用户所想，为不同的用户制定不同的推荐列表，用户通过自己的行为可以 改变推荐结果。
[0004] 优秀的个性化推荐系统为用户快速找到自己需要的合适信息提供了极大的方便， 同时让商家在众多的竞争者中脱颖而出，获得更大的点击量和销售额，据VentureBeat统 计，Amazon的个性推荐为其提高35%的销售业绩。个性化推荐系统在很多商业网站上已经 获得成功的应用，其中具有代表性的有Amzaon的电子商务推荐，Netflix和Movielens电影 推荐，Youtube和Hulu的视频推荐，Lastfm的音乐推荐，google的新闻推荐，Wanderfly的 旅游推荐，Facebook和Twitter的社交好友推荐以及国内的豆瓣电台，天猫商城，当当网， 优酷视频，人人网等等。Netflix还曾开出100万美元的巨奖来征集能够把他们网站上的推 荐结果提高10%的方法。
[0005] 自20世纪90年代以来，已经陆续有一些优秀的推荐系统方法被提出来，可以分为 以下几类：协同过滤系统；基于内容的推荐系统；混合的推荐系统；基于社交网络的推荐系 统。其中主要的思想都是根据用户或者物品的相似性来进行的推荐，通过牺牲推荐列表的 这样相同的物品有很大概率被推荐给众多不同的用户，以至于推荐列表很大的相似性，所 推荐的大部分物品又是流行商品。
[0006] 商品销售往往是具有"马太效应"的，即多的越多，少的越少，这就导致物品流行度 的分布成长尾式，处于流行度大的物品种类逐渐递减，数量上占大多数的不流行物品就被 称作长尾商品。理想的个性化推荐系统应该关注的不仅仅是推荐结果的正确性，同样重要 的还有其长尾挖掘的能力，即把不太惹人注目的商品恰到好处的推荐给需要的人群。如果 一个推荐系统通过推荐大量相似度很大的列表给用户，从而保证其正确率，显然是不符合 个性化需求的，用户也会很反感商家为什么给自己推荐这么多相似的东西，而那些不怎么 "招人喜欢"的商品则看起来很能保证销量。为了衡量这种冲突，用推荐结果的准确性，多样 性和新颖度来综合评价一个算法的好坏才是合理的。
[0007] 正是由于传统算法糟糕的多样性和新颖度指标，基于网络结构的推荐方法近些年 兴起，基于网络的算法不考虑用户和产品的内容特征，仅仅把其用户和物品看作抽象节点， 通过节点间信息的相互传递来确定用户节点对所有物品的联系，所有算法所利用的信息都 藏在用户和物品的选择关系之中。一种基于二分网络的推荐的混合算法（HPH)在"Solving theapparentdiversity-accuracydilemmaofrecommendersystems''(Proceedingsof theNationalAcademyofSciencesoftheUSA-PNAS107(10) ;4511_4515,2010)中被 Zhou等提出，这种方法尝试将两种特色鲜明的二分图推荐算法混合，通过调节两者重要性 的因子找到长尾挖掘和推荐准确性的折中方案。实验证明，恰到好处的为用户推荐一些不 流行的长尾商品能够得到比一味推荐流行度较大的方案更高的准确率，与此同时，推荐结 果的多样性和新颖度指标也会达到不错的效果。针对这种方法，有不少文献在其后给出一 些改进的方案来进一步优化推荐的结果。
[0008] 另一种基于二分网络的推荐方法由Liu等在"informationfilteringvia biasedheatconduction"（PhysicalreviewE84,037101，2011)中提出，这是一种在基 于二分网络的热传导算法基础上改进的方法（BHC)。基于二分网络的热传导算法（Heats) 是模拟初始资源分配的过程提出的推荐算法，该算法由于对流行的物品的影响进行了较大 程度的抑制，导致推荐结果过多的呈现出长尾物品，从而有很好的新颖度和糟糕的准确性， 这意味着推荐结果不能很好预测用户的需求，纵使良好的商品覆盖率，它并不能直接作为 推荐结果给用户。Liu在这个方法基础上通过调节流行物品影响因子来使原来的算法以牺 牲部分新颖度获得较好的准确性和多样性，设置合理的参数后，推荐结果有不错的效果。
[0009] 本发明是在借鉴先前研宄成果的基础上，对基于二分网络的热传导算法进行了完 善改进，在调节推荐结果的流行性分布过程中，对推荐系统三个重要指标都有了显著的提 高。该发明能够为用户提供了体验更好的推荐结果。
【发明内容】
[0010] 本发明的目的在于针对Heats方法推荐结果糟糕的准确率，提出一种基于二分网 络双向扩散的方法，在准确性、多样性和新颖度之间找到折中方案，以获得更好的推荐结 果，同时改善推荐系统中的冷启动问题，实现Top-N的推荐，即为每个用户提供一份含有N 个商品的推荐列表。为了方便叙述，这里假设本方法应用于电子购物网站，为用户推荐有可 能感兴趣的商品。
[0011] 本发明的技术方案是：将用户-物品之间的历史记录构造为简单二分网络，通过 用户节点和物品节点间的连线来表示该用户是否对该物品发生过购买行为。因为推荐算法 的根本目的是预测用户对未购买的物品的兴趣程度，在二分网络结构中，我们通过初始资 源的重新配置来估计目标用户对未购买物品的兴趣程度，类似于三步的随机游走的过程， 假设每个节点都有某种可分的资源，可以按一定比例分配给自己喜欢的其它节点对象，通 过相连节点资源的不断扩散，达到重新分配，从而建立没有直接联系节点间的关系。
[0012] (1)构造用户-物品的二进制矩阵A，只考虑购买关系，诸如购买次数、购买时间、 物品标签等等其它信息不纳入考虑范围。如果一个物品j曾经被用户i购买过，则au= 1 ; 否则％= 0。并由此建立用户-物品的二分网络，假设物品数量为n，用户数量为m;
[0013] (2)计算物品间二阶关联性：
[0014] 设初始状态下的二分网络的所有物品节点和用户节点所包含资源数量均为0 :
[0015] 2a)从物品节点集合0中选择某一物品节点为初始激活的物品节点，并拥有1个单 位的资源，其它所有物品和用户节点未激活，资源数量为〇 ;
[0016] 2b) 1个单位资源从初始激活的物品节点向与它相连的用户节点扩散，用户节点接 受的资源数量等于与它相连物品节点所拥有资源总量的平均数；
[0017] 2c)到达用户节点的资源再返回所有物品节点，物品节点接受的资源数量等于与 它相连用户节点所拥有资源总量的平均数；
[0018] 通过某一初始激活物品节点一用户节点一物品节点的扩散过程，这样原先资源数 量为0的物品节点得到一定数量资源，得到资源数量越多的物品节点，视为与初始激活的 物品节点越相似；依次选择不同的初始激活的物品节点，重复上面过程直到遍历完所有物 品节点集合0,即可得到物品-物品的二阶关联矩阵；
[0019] (3)计算用户间二阶关联性：
[0020] 设二分网络处于初始状态，初始状态下的二分网络的所有物品和用户节点所包含 的资源数量均为〇 :
[0021] 3a)从用户节点集合U中选择某一用户节点为初始激活的用户节点，并拥有1个单 位的资源，其它节点未激活，资源数量为〇 ;
[0022] 3b) 1个单位的资源从初始激活的用户节点向与它相连的物品节点扩散，物品节点 接受的资源数量等于与它相连用户节点所拥有资源总量的平均数；
[0023] 3c)到达物品节点的资源再返回所有用户节点，用户节点接受的资源数量等于与 它相连物品节点所拥有资源总量的平均数；
[0024] 通过某一初始激活用户节点一物品节点一用户节点的扩散过程，这样原先资源数 量为〇的用户节点得到一定数量资源，得到资源数量越多的用户节点，视为与初始激活的 用户节点越相似；依次选择不同的初始激活的用户节点，重复上面过程直到遍历完所有用 户节点集合U，即可得到用户-用户的二阶关联矩阵；
[0025] (4)完成资源双向扩散过程：
[0026] 设二分网络处于初始状态，所有节点资源数量为0 :
[0027] 4a)正向资源扩散过程：
[0028] 对于某一目标用户节点ut，设与其相连接的物品节点均为初始激活状态，并各自 拥有一个单位数量资源，其它节点未激活，资源量为〇;然后基于步骤（2)计算得到的物品 之间的关联性，将这些初始激活物品节点的资源按比例配给所有物品节点；
[0029] 4b)逆向资源扩散过程：
[0030] 选择某一物品节点〇t，经过正向扩散后，该物品节点得到数量为r的资源；设与〇t 相连接的所有用户节点被激活，并各自拥有数量为的等量资源，X是调优参数；然后基 于步骤（3)计算得到的用户之间的关联性，将所有激活的用户节点所拥有的资源按比例分 配给所有用户节点；用户节点ut得到的从物品节点〇t反馈回的资源数量表征用户ut对物 品〇t的感兴趣的程度；
[0031] 4c)依次选取集合0中其它物品节点，完成4b)的过程，直到遍历完所有物品节点， 得到用户ut对所有物品的感兴趣的程度列表；
[0032] 4d)依次选取集合U中其它用户节点，完成4a)~4c)的过程，直到遍历完所有用 户节点，得到所有用户对所有物品的感兴趣程度，用mXn的矩阵M记录下来；
[0033] (5)给出对应于每个用户的长度为N的物品推荐列表：N的大小依据实际需要确 定，表示为每个用户提供N个推荐物品，为每个用户推荐N个没有购买过的兴趣值排行靠前 的物品；
[0034] 本发明与现有技术相比具有如下优点：
[0035] 第一，准确性提高。在仅利用用户-物品购买与否的历史纪录情况下，不考虑进一 步的二阶冗杂信息剔除，本发明得到的推荐系统具有更高的推荐准确率，在预测用户需求 方面更加准确。
[0036] 第二，多样性和新颖度提高，较好的长尾商品挖掘能力。本发明在不损失准确率， 甚至有所提高的前提下，使得推荐结果有更好的多样性和新颖度，可以更高效将数量上占 绝大多数的不流行物品恰到好处的推荐给有需求的人群，改善了用户对推荐商品列表的体 验。
[0037] 第三，改善了推荐系统中的冷启动问题，在本算法过程中不仅用到物品-物品之 间的关联，还囊括了用户-用户的关联信息，这样新物品一旦被某个用户购买，会迅速推广 给其他用户，同时新用户一旦购买了某件物品，也可以迅速为其提供合适的推荐列表。
【附图说明】
[0038] 图1为本发明的流程示意图；
[0039] 图2为本发明用于MovieLens和Netflix的调节参数A选择；
[0040] 图3为本发明在10000X6000的Netflix数据集上得到推荐结果分布图；
[0041] 图4为本发明与现有的基于二分网络推荐系统方法的性能比较。
【具体实施方式】
[0042] 将本发明的流程思想通过矩阵运算，避免复杂的迭代过程，得到比较清晰明了的 具体实施方法。本发明的实现步骤如下：
[0043] 步骤1，根据用户的历史行为记录来构建用户-物品的二分网络，用户的历史行为 记录包括用户购买物品的记录或者用户对物品的评价记录：
[0044] 设用户节点11={111，112，...，11111}，1]1为用户的数目，物品节点0={〇 1，〇2，...，〇11}，11 为物品的数目，Re记录用户和物品之间的交互关系，只考虑用户是否购买或评价过物品的 一兀关系；
[0045] 构建用户-物品的二分网络的图模型，其中用户节点与用户节点之间无连接，物 品节点与物品节点之间也没有连接，只在发生过交互关系的用户节点与物品节点之间建立 连接，即在Re中有记录的<U，0>。用二元矩阵AmXn= (aij)mXn来存储该二分网络中的连接 信息，其中
[0047] <Ui，〇j>表示第i个用户节点与第j个物品；au是二元矩阵AmXl^i行第j列 的元素；
[0048] 步骤2,建立物品-物品及用户-用户的二阶关联矩阵：
[0049] 2a)计算物品-物品间的二阶关联矩阵：
[0051] 其中
，表示物品节点〇〇的出度，即流行度
，表示 用户节点％的出度，即用户活跃度；ala，alfi对应矩阵六^^中的元素；m表示用户的数量， 用来衡量物品〇a和〇e的关联程度；通过计算n个物品任意两个之间的关联程度，可得 到nXn维的物品关联矩阵WH;
[0052] 2b)计算用户-用户二阶关联矩阵：
[0054] 其中
，表示用户节点up的出度，即用户活跃度；
表示物品节点〇a的出度，即流行度；apa, 对应矩阵AmXn中的元素；n表示物品的数量； 用来衡量用户ujPuq的关联程度；通过计m个用户任意两个之间的关联程度，可得到 mXm维的物品关联矩阵WTH;
[0055] 步骤3,完成双向扩散过程：
[0056] 3a)完成正向扩散过程：
[0057] R=AmXnX(ffH)T
[0058] 矩阵R为mXn维的矩阵，记录经过资源重新分配后物品节点从用户节点得到的资 源数量；
[0059] 3b)完成逆向扩散过程：
[0060] M=R? (WTHXAmXn)A
[0061] 矩阵M为mXn维的矩阵，记录逆向扩散后，用户节点从物品节点拿回的资源数量。 某一物品节点〇1反馈回给某一用户节点ut的资源数量越多，表明物品〇t和用户ut关联性 越强，即用户ut越有可能对物品0t感兴趣。
[0062] A是为了调整正向过程和逆向过程的比重来优化推荐结果的性能指标而引进的 参数，Ae[0，1]，X的大小取决于矩阵AmXn的稀疏程度，可以通过在用户的历史行为记录 的数据上测试来选择其最佳的值； [0063] 步骤4,给出每个用户的长度为N的推荐列表：
[0064] 4a)将最终的用户-物品兴趣度矩阵M每行按从大到小排列，即按兴趣程度的大 小，为每个用户都整理出他的兴趣表；
[0065] 4b)为每个用户推荐N个没有购买过的兴趣值排行靠前的物品。
[0066] 本发明的效果可以通过以下仿真进一步说明：
[0067] 1.仿真条件
[0068] 本实例在Intel(R)Core(TM)2DuoCPU2. 33GHzWindows7 (x64)系统下， Matlab2012a运行平台上，完成本发明与现有Heats，HNBI，HPH，BHC推荐算法的仿真实验。
[0069] 2.仿真实验内容
[0070] 为了验证本发明的实际效果，实验中选择两个推荐系统中著名的数据集做测试， 并同几个现有经典的基于二分网络的推荐方法做了对比。实验数据集一是MovieLens数据 (http://www.grouplens.org/)，由1682个部电影和943个用户组成。数据集二是Netflix 数据（ http://www.netflixprize.com/)，本实验数据随机抽取了其中10000个用户和6000 部电影的记录。这两个数据集都是1到5的评分稀疏矩阵，本发明关注的是Top-N的推荐 问题，所以本实验将数据集中评分不小于3的评分项视为用户喜欢，设为1 ;评分小于3的 评分项视为用户不喜欢这部电影，设为〇,我们为用户提供他可能喜欢的推荐电影列表。这 样变为了二进制的数据集，原本很稀疏的数据将更加稀疏，Movielens的用户喜欢的历史记 录有82520条，稀疏度为5. 20 ?lOlNetflix的用户喜欢的历史记录有642604条，稀疏度 为1. 07 ? 10_2。实验中将数据集随机拆成90%的训练集和10%的测试集，采取五次随机交 叉验证实验，实验结果推荐列表长度为50(N= 50)，也就是为每个用户推荐50个商品。
[0071] 用来评价一个推荐系统好坏的指标是其准确性，多样性和新颖度。准确性用准确 率和召回率表示，多样性和新颖度有很多的衡量方法。本实验采取下面的方法。
[0072] 准确率（Precision)衡量推荐列表预测出用户的下一步的购买行为的成功率，其 中m是用户数量，N是推荐列表中包含物品数量^(N)表示用户i的推荐列表中预测正确 的商品个数（和测试集对照）表示用户的数量。
[0074] 召回率（Recall)衡量推荐列表成功预测出的商品数量在用户下一步购买物品数 量中的比例，其中T表示测试集中的记录为1的数量，即用户下一步购买的商品数量;m表 示用户的数量。
[0076]多样性（Diversity)衡量推荐列表中物品的多样性，高效的个性化推荐系统会尽 量提供广泛的选择。其中表示为用户i和用户j推荐的相同物品数量；衡量用户i， j推荐表单的差异度；m表示用户的数量。
[0079] 新颖度（Novelty)衡量推荐列表中物品的不流行度，高效的个性化推荐系统会尽 量推荐一些不常见的物品给用户，也称作用户的惊喜度。其中kia表示为用户i所推荐物 品a的流行度；m表示用户的数量。
[0081] 图2(a)是在MovieLens数据集上优化A的过程，可已看出，当A取0.2时，推荐 系统的准确性达到最好，但对应的多样性和新颖度却不是最高，说明推荐系统的几个指标 是存在一些冲突关系的。由于实验旨在测试本发明在准确性不降低的前提下，多样性和新 颖度方面的表现，因此将A=0.2作为系统的最佳值。
[0082] 图2(b)是在Netflix数据集上优化A的过程，同理，将A=0.2作为系统的最 佳值，A的值和MovieLens数据集上测试集上相同，这是因为两个数据集稀疏度都是在1(T2 级，而A的值是与数据的稀疏程度相关的。
[0083] 图3(a)画出了商品长尾分布的特性，流行的商品数量占极少数，大部分商品属于 不流行的，且随着流行度的增加，商品数量递减。流行的商品用户很容易从各种渠道了解， 而不流行的则很难为大众所知，因此个性化推荐的一个重要目标就是把处于长尾的不流行 的商品挖掘出来推荐给合适的用户。
[0084] 图3(b)给出基于物品间关联性做推荐的结果分布图，也就是Heats方法的结果。 从图中很容易看出，这样推荐策略更加侧重推荐不流行的商品，结果的新颖度会很好，但是 准确率就很难保证了。糟糕准确率的一个推荐算法根本不能作为实际应用。由于正向过程 是基于物品的关联程度扩散的，所以这个过程对新用户的推荐有优势。
[0085] 图3 (c)给出反向扩散结束后，根据矩阵TR做出的推荐物品分布图，与正向过程相 反，它更多推荐了比较流行的物品，相对而言准确性会好一些，但新颖度和多样性比较差。 由于反向过程是基于用户的关联程度扩散的，所以这个过程的对新物品的推荐有优势。
[0086] 图3(d)给出基于用户间关联性做推荐的结果分布图，可以看出这个算法是找一 个平衡点，但并不是性能的妥协。实验结果证明，融合后的推荐结果准确率比单个过程都要 好，且多样性和新颖度也非常不错，这是因为融合的过程不仅仅是找到流行物品和不流行 物品的平衡，同时将物品之间、用户之间的信息都囊括在内。然而，如果将传统KNN协同过 滤也做这样的融合却达不到这样的效果，基于物品和基于用户的KNN推荐算法关注的都是 准确率而非新颖度，融合后性能只会介于单个算法之间。这也是基于网络的推荐算法的根 本优势，它能够将已有的信息通过网络扩散，使不流行的物品也散播给尽可能多的用户，而 基于邻域思想的协同过滤方法将初始信息资源约束在小范围内传播。
[0087] 图4给出了本方法和现有性能出色的基于二分网络的推荐算法之间的比较，本方 法表示为HBT，与PNAS上提出的经典的HPH方法比较，在MovieLens上准确性提高了 2. 4%， 多样性提升4. 0%，新颖度也有6. 1 %的提高；在Netflix数据集上测试，准确性有6. 0%的 提高，多样性和新颖性指标分别提升了 6. 8 %，3. 1 %。实验结果充分说明了本发明用于个性 化推荐系统的出色性能。
[0088] 总之，本发明在基于二分网络搭建的推荐系统方法，将用户和物品分别看做网络 中的两列抽象节点，利用网络传播扩散的原理，通过正反向的信息扩散及融合过程，找到准 确性、多样性和新颖性之间的契合点，同时将物品间和用户间的关联信息充分利用，最终得 到一个性能较已有方法更好的推荐系统。总之，本发明表现出很好的长尾商品挖掘能力，可 以应用于Top-N的推荐。
【主权项】
1. 一种基于二分网络双向扩散的个性化推荐方法，所述方法包括下列步骤： (1) 根据用户的历史行为记录来构建用户-物品的二分网络，用户的历史行为记录包 括用户购买物品的记录或者用户对物品的评价记录： 设用户节点集合U = Iu1, U2, ...，um}，m为用户的数目，物品节点集合O = {〇1，〇2, ...，〇η}，η为物品的数目，Re记录用户和物品之间的交互关系，该交互关系与用户的 历史行为记录对应，只考虑用户是否购买或评价过物品的二元关系。 构建用户-物品的二分网络的图模型，其中用户节点与用户节点之间无连接，物品节 点与物品节点之间也没有连接，只在发生过交互关系的用户节点与物品节点之间建立连 接；如果用户节点与物品节点发生过交互关系，则在Re中生成记录<U，0> ;用二元矩阵Amxn=h j) m x n来表示该二分网络中的连接信息，其中< Ui, 〇j>表示第i个用户节点与第j个物品；a u是二元矩阵Amxn第i行第j列的元 素； (2) 计算 物品间>阶关联性： 假设二分网络的所有节点均可以储藏一定量的资源，初始状态下的所有网络节点所含 资源数量均为〇 : 2a)从物品节点集合O中选择某一物品节点为初始激活的物品节点，并拥有1个单位的 资源，其它节点未激活，资源数量为〇 ; 2b)单位资源从初始激活的物品节点向与它相连的用户节点扩散，用户节点接受的资 源数量等于它相连物品节点所拥有总量的平均数； 2c)到达用户节点的资源再返回所有物品节点，物品节点接受的资源数量等于它相连 用户节点所拥有总量的平均数； 通过某一初始激活物品节点一用户节点一物品节点的扩散过程，这样原先资源数量为 〇的物品节点得到一定数量资源，得到资源数量越多的物品节点，视为与初始激活的物品节 点越相似。依次选择不同的初始激活的物品节点，重复上面过程直到遍历完所有物品节点 集合〇,即可得到物品-物品的二阶关联矩阵； (3) 计算用户间二阶关联性： 设二分网络处于初始状态，所有节点资源数量均为0 : 3a)从用户节点集合U中选择某一用户节点为初始激活的用户节点，并拥有1个单位的 资源，其它节点未激活，资源数量为0 ; 3b) 1个单位的资源从初始激活的用户节点向与它相连的物品节点扩散，物品节点接受 的资源数量等于与它相连用户节点所拥有总量的平均数； 3c)到达物品节点的资源再返回所有用户节点，用户节点接受的资源数量等于它相连 物品节点所拥有总量的平均数； 通过某一初始激活用户节点一物品节点一用户节点的扩散过程，这样原先资源数量为 〇的用户节点得到一定数量资源，得到资源数量越多的用户节点，视为与初始激活的用户节 点越相似。依次选择不同的初始激活的用户节点，重复上面过程直到遍历完所有用户节点 集合U，即可得到用户-用户的二阶关联矩阵； (4) 完成资源双向扩散过程： 设二分网络处于初始状态，所有节点资源数量为O : 4a)正向资源扩散过程： 对于某一目标用户节点ut，设与其相连接的物品节点均为初始激活状态，并拥有一个 单位数量资源，其它节点未激活，资源量为〇 ;然后基于步骤（2)计算得到的物品之间的关 联性，将这些初始激活物品节点的资源按比例配给所有物品节点； 4b)逆向资源扩散过程： 选择某一物品节点〇t，经过正向扩散后，该物品节点得到数量为r的资源；设与〇t相连 接的用户节点被激活，并各自拥有数量为1^的资源，λ是调优参数；然后基于步骤（3)计 算得到的用户之间的关联性，将所有激活的用户节点所拥有的资源按比例分配给所有用户 节点；用户节点Ut得到从物品节点〇 t反馈回的资源数量，用来表征用户u t对物品〇 t的感 兴趣的程度； 4c)依次选取集合0中其它物品节点，完成4b)的过程，直到遍历完所有物品节点，得到 用户Ut对所有物品的感兴趣的程度列表； 4d)依次选取集合U中其它用户节点，完成4a)~4c)的过程，直到遍历完所有用户节 点，得到所有用户对所有物品的感兴趣程度，用mXn的矩阵M记录下来； (5) 给出对应于每个用户的长度为N的物品推荐列表：N的大小依据实际需要确定，表 示为每个用户提供N个推荐物品； 5a)将最终的用户-物品兴趣度矩阵M每行按从大到小排列，即按兴趣程度的大小，为 每个用户都整理出他的兴趣表； 5b)为每个用户推荐N个没有购买过的兴趣值排行靠前的物品。2. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中步骤（1)所述的二 分网络是根据用户购买行为来确定的，二分网络只关心抽象节点间有无连接关系，是个没 有权值的网络，很多现有用户历史数据集以1-5评分给出的，这时将大于2的评分项视为喜 欢，即有连接；不大于2的评分项视为无连接。将现有处理过的用户历史行为数据随机分割 为90%的训练集和用于测试系统性能的10%的测试集。3. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中，在步骤（2)、（3)中 分别采用如下的方法建立物品-物品及用户-用户的二阶关联矩阵： (1) 计算物品-物品间的二阶关联矩阵：其中，表示物品节点〇α的出度，即流行度；，表示用户 节点U1的出度，即用户活跃度；a la，alfi对应矩阵A mXn中的元素；m表示用户的数量，用 来衡量物品Oc^Pofi的关联程度；通过计算η个物品任意两个之间的关联程度，可得到nXn 维的物品关联矩阵Wh; (2) 计算用户-用户二阶关联矩阵：其4，表示用户节Aup的出度，即用户活跃度；表示 物品节点Oa的出度，即流行度；apa, aqa对应矩阵Amxn中的元素；η表示物品的数量； 用来衡量用户ujP u ,的关联程度；通过计m个用户任意两个之间的关联程度，可得到mXm 维的物品关联矩阵W?。4. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中，步骤（4)采用如下 的方法建立： (1) 完成正向扩散过程： R = AmxnX (Wh)T 矩阵R为mXn维的矩阵，记录经过资源重新分配后物品节点从用户节点得到的资源数 量； (2) 完成逆向扩散过程： M = R. (WraXAmxn) λ 矩阵M为mXn维的矩阵，记录逆向扩散后，用户节点从物品节点拿回的资源数量。某 一物品节点〇,反馈回给某一用户节点u t的资源数量越多，表明物品〇 t和用户u t关联性越 强，即用户Ut越有可能对物品〇 ,感兴趣。 λ是为了调整正向过程和逆向过程的比重来优化推荐结果的性能指标而引进的参数， λ e [〇，1]，λ的大小取决于矩阵Amxn的稀疏程度，可以通过在用户的历史行为记录的数 据上测试来选择其最佳的值。5. 根据权利要求1所述的基于二分网络双向扩散的推荐方法，其中所述的调优参数λ 取值是根据推荐方法的各方面的性能折中选择的，衡量个性化推荐系统的性能指标用以下 方法确定： 准确率（Precision)衡量推荐列表预测出用户的下一步的购买行为的成功率，其中m是用户数量，N是推荐列表中包含物品数量Wi(N)表示用户i的推荐列表中预测正确的商 品个数（和测试集对照）表示用户的数量。召回率（Recall)衡量推荐列表成功预测出的商品数量在用户下一步购买物品数量中 的比例，其中T表示测试集中的记录为1的数量，即用户下一步购买的商品数量;m表示用 户的数量。多样性（Diversity)衡量推荐列表中物品的多样性，高效的个性化推荐系统会尽量提 供广泛的选择。其中％表示为用户i和用户j推荐的相同物品数量；H 量用户i，j推 荐表单的差异度；m表示用户的数量。新颖度（Novelty)衡量推荐列表中物品的不流行度，高效的个性化推荐系统会尽量推 荐一些不常见的物品给用户，也称作用户的惊喜度。其中kia表示为用户i所推荐物品α 的流行度；m表示用户的数量。
【专利摘要】本发明公开了一种基于二分网络双向扩散的个性化推荐方法，针对Top-N的个性化推荐，主要解决了推荐列表的准确性，多样性及新颖度几个主要算法性能指标的冲突。其实现步骤为：(1)构建用户-物品关联的二分图网络。假设每个目标用户节点都有某种可分的资源，可以按预定分配机制分配给其它节点对象；(2)建立物品-物品及用户-用户的二阶关联矩阵；(3)完成双向扩散过程，得到用户-物品的兴趣矩阵；(4)给出每个用户的长度为N的推荐列表，完成Top-N的推荐。本发明基于网络传播的思想，效果明显好于经典的协同过滤方法，更好的实现了个性化推荐系统所关注的长尾挖掘，可用于解决个性化推荐的Top-N问题。
【IPC分类】G06Q30/02
【公开号】CN104899763
【申请号】CN201510230210
【发明人】马文萍, 焦李成, 冯翔, 马晶晶, 侯彪, 王爽, 其他发明人请求不公开姓名
【申请人】西安电子科技大学
【公开日】2015年9月9日
【申请日】2015年5月7日
最新回复(0)