下载文档原格式
协同过滤算法流程协同过滤算法是推荐系统中常用的一种算法，主要用于个性化推荐。
协同过滤算法基于用户的历史行为数据，通过分析用户与物品之间的关联关系，来预测用户对未知物品的喜好程度。
下面将介绍协同过滤算法的流程。
首先，协同过滤算法可以分为两种：基于用户的协同过滤算法和基于物品的协同过滤算法。
基于用户的协同过滤算法是通过计算用户之间的相似度来进行推荐，而基于物品的协同过滤算法是通过计算物品之间的相似度来进行推荐。
协同过滤算法的流程大致分为以下几个步骤：1. 数据准备：首先需要收集用户的历史行为数据，包括用户对物品的评分、点击、购买等信息。
这些数据将作为算法的输入。
2. 相似度计算：接下来需要计算用户之间或物品之间的相似度。
对于基于用户的协同过滤算法，可以使用余弦相似度、皮尔逊相关系数等方法来计算用户之间的相似度；对于基于物品的协同过滤算法，可以使用余弦相似度、Jaccard相似度等方法来计算物品之间的相似度。
3. 预测评分：根据用户的历史行为数据和相似度计算结果，可以预测用户对未知物品的评分。
对于基于用户的协同过滤算法，可以通过加权平均的方式来预测用户对物品的评分；对于基于物品的协同过滤算法，可以通过加权平均的方式来预测用户对物品的评分。
4. 推荐结果生成：最后根据预测的评分，可以为用户生成个性化的推荐结果。
可以根据预测的评分进行排序，推荐给用户评分最高的物品。
总的来说，协同过滤算法的流程主要包括数据准备、相似度计算、预测评分和推荐结果生成四个步骤。
通过这些步骤，可以实现个性化的推荐，提升用户的使用体验。
协同过滤算法是推荐系统中的重要算法之一，对于提高推荐的准确性和用户满意度具有重要作用。
协同过滤方法协同过滤方法是一种常用的推荐算法，它基于用户的历史行为数据，通过计算用户之间的相似度，来预测用户对未知物品的喜好程度。
这种方法的优点在于能够利用用户的历史行为数据，不需要对物品进行特征提取，因此适用于各种类型的物品推荐。
协同过滤方法主要分为两种：基于用户的协同过滤和基于物品的协同过滤。
基于用户的协同过滤是通过计算用户之间的相似度来预测用户对未知物品的喜好程度。
具体来说，对于一个用户u，我们可以找到与其历史行为最相似的k个用户，然后将这k个用户对未知物品的评分进行加权平均，得到用户u对该物品的预测评分。
基于物品的协同过滤则是通过计算物品之间的相似度来预测用户对未知物品的喜好程度。
具体来说，对于一个用户u，我们可以找到其历史行为中评分最高的k个物品，然后将这k个物品与未知物品的相似度进行加权平均，得到用户u对该物品的预测评分。
协同过滤方法的实现需要解决两个问题：相似度计算和预测评分。
相似度计算可以使用余弦相似度、皮尔逊相关系数等方法。
预测评分可以使用加权平均、加权SVD等方法。
此外，协同过滤方法还需要解决冷启动问题和稀疏性问题。
冷启动问题是指对于新用户或新物品，没有足够的历史行为数据进行推荐。
解决冷启动问题的方法包括基于内容的推荐、基于社交网络的推荐等。
稀疏性问题是指用户历史行为数据中存在大量缺失值，导致相似度计算和预测评分不准确。
解决稀疏性问题的方法包括基于邻域的方法、基于矩阵分解的方法等。
协同过滤方法是一种常用的推荐算法，它能够利用用户的历史行为数据进行推荐，不需要对物品进行特征提取，适用于各种类型的物品推荐。
协同过滤方法的实现需要解决相似度计算、预测评分、冷启动问题和稀疏性问题等一系列问题。
协同过滤算法简介协同过滤算法是一种常见的推荐算法，它的核心思想是基于用户的历史行为数据，找到具有相似行为模式的用户或物品，通过计算它们之间的相似度，进行推荐。
协同过滤算法不需要事先建立物品或者用户的特征向量，可以适用于不同领域的推荐问题。
1. 基于用户的协同过滤算法基于用户的协同过滤算法，也叫做用户-用户协同过滤算法，它的核心思想是寻找和目标用户相似的其他用户，将这些用户喜欢的物品推荐给目标用户。
这种算法的实现过程通常包括以下步骤：（1）找到和目标用户兴趣相似的其他用户。
（2）将这些用户喜欢的物品进行统计和分析，找到这些物品中目标用户还没有看过的物品。
（3）将这些物品推荐给目标用户。
基于用户的协同过滤算法有一个优点，就是它很容易实现。
但是，这种算法也有一些缺点。
首先，当用户数目非常大时，时间和空间复杂度可能会很高。
其次，由于用户的兴趣爱好可能非常多样化，因此很难找到和目标用户相似的其他用户。
2. 基于物品的协同过滤算法基于物品的协同过滤算法，也叫做物品-物品协同过滤算法，它的核心思想是寻找和目标物品相似的其他物品，并将这些物品推荐给目标用户。
这种算法的实现过程通常包括以下步骤：（1）找到和目标物品相似的其他物品。
（2）将这些物品推荐给目标用户。
基于物品的协同过滤算法的优点是它会同时考虑很多用户的行为数据，而不是仅仅只考虑一个用户的数据。
这种算法的缺点是它相比于基于用户的算法来说较为复杂，并且对于新物品的评估可能会非常困难。
3. 混合协同过滤算法混合协同过滤算法是基于用户的协同过滤算法和基于物品的协同过滤算法的结合。
这种算法的主要思想是将基于用户的协同过滤算法和基于物品的协同过滤算法的结果进行加权平均，从而得到更加准确的推荐结果。
混合协同过滤算法的优点是它能够同时考虑基于物品的协同过滤算法和基于用户的协同过滤算法的结果，从而得到更加准确的推荐结果。
但是，这种算法的缺点也很明显，它需要消耗更多的计算资源，并且需要更多的存储空间。
协同过滤算法简介协同过滤算法是一种常见的推荐系统算法，它通过分析用户的行为数据，找出用户之间的相似性，然后根据用户的历史行为来推荐给其可能感兴趣的物品。
在互联网时代，随着信息爆炸式增长和商业模式的变革，推荐系统成为各大互联网平台的核心功能之一。
一、协同过滤算法的基本原理协同过滤算法基于用户的历史行为数据，通过对用户行为数据的分析，找出用户之间的相似性，然后根据用户的历史行为来推荐给其可能感兴趣的物品。
这种算法的核心在于利用用户之间的相似性来进行推荐，从而实现个性化推荐的目的。
二、协同过滤算法的分类根据数据来源和处理方式的不同，协同过滤算法可以分为基于用户的协同过滤和基于物品的协同过滤两种类型。
基于用户的协同过滤算法是根据用户对物品的评价来计算用户之间的相似性，从而进行推荐；而基于物品的协同过滤算法则是根据物品的特征来计算物品之间的相似性，从而进行推荐。
另外，协同过滤算法还可以分为基于邻域的协同过滤和基于模型的协同过滤两种类型。
基于邻域的协同过滤算法是通过寻找用户或物品的邻居来进行推荐，而基于模型的协同过滤算法则是通过构建模型来进行推荐。
三、协同过滤算法的优缺点协同过滤算法的优点在于它能够实现个性化推荐，能够为用户提供符合其个性化需求的推荐结果。
此外，协同过滤算法还可以根据用户的行为数据进行实时推荐，能够快速响应用户的需求。
然而，协同过滤算法也存在一些缺点，例如对数据稀疏性和冷启动问题的处理能力有限，同时还存在着推荐结果的过度依赖用户行为数据，容易出现推荐的局限性等问题。
四、协同过滤算法的应用协同过滤算法在各大互联网平台上都有着广泛的应用，例如在电商平台上，协同过滤算法能够根据用户的历史购买记录推荐给其可能感兴趣的商品；在社交媒体平台上，协同过滤算法能够根据用户的好友关系和兴趣爱好进行推荐；在音乐和视频平台上，协同过滤算法能够根据用户的播放历史推荐给其可能喜欢的歌曲和视频等。
此外，协同过滤算法还被广泛应用于在线广告推荐、新闻推荐和人才招聘等领域。
推荐系统中的协同过滤算法原理及实现步骤协同过滤算法是一种常用于推荐系统的算法，通过利用用户行为数据和物品属性信息来预测用户对物品的偏好，并推荐给他们可能感兴趣的物品。
本文将介绍协同过滤算法的原理和实现步骤。
一、协同过滤算法原理协同过滤算法基于相似性原理来进行推荐，可以分为两种类型：基于用户的协同过滤和基于物品的协同过滤。
1. 基于用户的协同过滤基于用户的协同过滤算法计算用户之间的相似性，然后根据相似用户的行为来推荐物品。
其核心原理是：如果两个用户在过去的行为中有相似的偏好和兴趣，那么他们在未来的行为中可能也会有相似的偏好和兴趣。
2. 基于物品的协同过滤基于物品的协同过滤算法计算物品之间的相似性，然后根据用户对相似物品的偏好来推荐物品。
其核心原理是：如果一个用户对某个物品有兴趣，那么他可能对与该物品相似的其他物品也有兴趣。
二、协同过滤算法实现步骤协同过滤算法的实现步骤可以分为以下几个步骤：1. 数据预处理在实施协同过滤算法之前，需要对用户行为数据进行预处理。
预处理的目的是清洗数据、处理缺失值和离群值，以及将数据转换为适合算法处理的格式。
2. 计算用户相似度或物品相似度对于基于用户的协同过滤，需要计算用户之间的相似性；对于基于物品的协同过滤，需要计算物品之间的相似性。
相似性可以使用余弦相似度、皮尔逊相关系数等方法进行计算。
3. 预测评分通过用户相似度或物品相似度，预测用户对未评分物品的评分。
对于基于用户的协同过滤，可以根据相似用户的评分加权平均来进行预测；对于基于物品的协同过滤，可以根据用户对相似物品的评分加权平均来进行预测。
4. 推荐物品根据预测的评分，为用户推荐可能感兴趣的物品。
可以根据预测评分的降序排序，选取Top N的物品作为推荐结果。
5. 评估算法效果为了评估协同过滤算法的效果，可以使用常见的评测指标，如准确率、召回率、覆盖率等。
三、总结协同过滤算法是一种常用的推荐算法，可以根据用户行为数据和物品属性信息进行预测和推荐。
协同过滤算法的实现协同过滤算法是一种利用用户行为数据进行推荐的算法，通过分析用户的历史行为，提供个性化推荐给用户。
协同过滤算法一般分为基于用户的协同过滤算法和基于物品的协同过滤算法。
基于用户的协同过滤算法是指根据用户的历史行为数据，找寻与之相似的用户，推荐这些相似用户喜欢的物品给用户。
算法的实现流程如下：1. 建立用户-物品矩阵用户-物品矩阵是一个 $m \times n$ 的稀疏矩阵，其中 $m$ 表示用户的数量，$n$ 表示物品的数量。
矩阵中的每一个元素 $a_{ij}$ 表示用户 $i$ 对物品 $j$ 的打分情况，如果用户 $i$ 对物品 $j$ 打过分，则矩阵中该元素会有具体的分数值，否则为$\varnothing$。
2. 计算用户之间的相似度计算用户之间的相似度一般采用余弦相似度或者皮尔逊相似度。
这里以余弦相似度为例，余弦相似度的计算公式如下：$$sim(i,j) = \frac{\sum_{u \in U} r_{ui} * r_{uj}}{\sqrt{\sum_{u \in U} r_{ui}^2} * \sqrt{\sum_{u \in U} r_{uj}^2}}$$其中，$sim(i,j)$ 表示用户 $i$ 和用户 $j$ 之间的相似度，$r_{ui}$ 表示用户$u$ 对物品 $i$ 的打分情况，$U$ 表示与用户 $i$ 喜欢的物品相似的其他用户。
3. 找出相似用户找出与当前用户相似度最高的 $k$ 个用户作为该用户的邻居用户。
4. 生成推荐物品列表根据当前用户的邻居用户的历史行为数据，生成该用户的推荐物品列表。
推荐物品的计算方法如下：基于物品的协同过滤算法是将物品分类，根据用户对某一类物品的评分情况，推荐该类物品中其他用户评分高的物品给用户。
算法实现流程如下：3. 基于用户历史行为进行推荐$$P(u,i) = \sum_{j \in N(i)} sim(i,j) * r_{u,j} $$。
协同过滤算法范文协同过滤算法是一种基于用户行为和兴趣相似性的推荐算法。
它通过分析大量用户行为数据和物品属性，将用户与他人的行为和喜好进行比较，来实现个性化推荐，提高用户满意度和购买率。
下面将详细介绍协同过滤算法的原理、分类和应用。
一、协同过滤算法原理具体而言，协同过滤算法可以分为两种类型：基于用户的协同过滤和基于物品的协同过滤。
1. 基于用户的协同过滤（User-Based Collaborative Filtering）基于用户的协同过滤算法是根据用户之间的行为相似性进行推荐。
算法的步骤包括：1）计算用户之间的相似度，常用的相似度度量方法有皮尔逊相关系数和余弦相似度。
2）根据用户相似度和其他用户的行为数据，预测目标用户对尚未产生行为的物品的评分或喜好程度。
3）将预测出的评分或喜好程度进行排序，为目标用户生成推荐列表。
2. 基于物品的协同过滤（Item-Based Collaborative Filtering）基于物品的协同过滤算法是根据物品之间的关联性进行推荐。
算法的步骤包括：1）计算物品之间的相似度，常用的相似度度量方法有余弦相似度和Jaccard相似度。
2）根据用户的历史行为和物品相似度，预测用户对尚未产生行为的物品的评分或喜好程度。
3）将预测出的评分或喜好程度进行排序，为目标用户生成推荐列表。
二、协同过滤算法分类除了基于用户和物品的协同过滤算法，还有一些其他的协同过滤算法，如基于模型的协同过滤、混合协同过滤等。
1. 基于模型的协同过滤（Model-Based Collaborative Filtering）基于模型的协同过滤算法是通过建立数学模型来预测用户对物品的评分或喜好程度。
常用的模型包括矩阵分解模型和概率图模型。
-矩阵分解模型：将用户-物品的评分矩阵分解为用户-因子矩阵和因子-物品矩阵，通过计算两个矩阵的乘积来预测用户对尚未产生行为的物品的评分。
-概率图模型：利用概率图模型来描述用户行为和物品属性之间的关系，通过概率推理来预测用户对物品的喜好程度。
机器学习技术中的协同过滤算法详解协同过滤算法是机器学习中一种常用的推荐系统技术。
它通过分析用户的行为和偏好，找出与用户兴趣相似的其他用户或物品，从而进行个性化推荐。
本文将详细解析协同过滤算法的原理、应用和优缺点。
协同过滤算法的原理协同过滤算法主要基于两种思路：用户协同和物品协同。
用户协同指根据用户的相似性进行推荐，即找出与目标用户相似的其他用户，并将这些用户喜欢的物品推荐给目标用户。
物品协同则是根据物品的相似性进行推荐，即找出与目标物品相似的其他物品，并推荐给用户。
在实际应用中，协同过滤算法通常基于用户的评分数据或行为数据进行计算。
算法会对用户或物品进行特征提取和相似度计算，以确定相似性。
常用的相似度计算方法包括余弦相似度和皮尔逊相关系数等。
通过相似度计算，可以建立用户与用户之间或物品与物品之间的关联关系。
协同过滤算法的应用协同过滤算法在推荐系统中有广泛的应用。
例如，电商网站可以利用协同过滤算法来为用户推荐商品，音乐和视频平台可以通过该算法为用户推荐喜欢的音乐和影视作品。
此外，社交媒体平台也可以利用协同过滤算法为用户推荐朋友和关注的内容。
协同过滤算法的优缺点协同过滤算法具有以下优点：1. 个性化推荐：协同过滤算法可以根据用户的行为和偏好进行个性化推荐，提高用户体验。
2. 隐性信息发现：协同过滤算法可以从用户的行为中发现隐藏的用户兴趣和关联关系，挖掘潜在的推荐物品。
3. 灵活性和扩展性：协同过滤算法可以根据用户和物品的数量和特征进行灵活的扩展，适用于不同规模和特性的推荐系统。
然而，协同过滤算法也存在一些缺点：1. 数据稀疏性：当用户的行为数据较稀疏时，难以准确计算用户之间或物品之间的相似性，从而影响推荐的准确性。
2. 冷启动问题：对于新用户或新物品，缺乏足够的行为数据来进行准确的推荐，导致冷启动问题。
3. 推荐瀑布效应：协同过滤算法容易向热门物品偏好，导致推荐效果不够多样化，忽略了长尾物品的推荐。
CollaborativeFiltering（协同过滤）算法详解基本思想基于⽤户的协同过滤算法是通过⽤户的历史⾏为数据发现⽤户对商品或内容的喜欢(如商品购买，收藏，内容评论或分享)，并对这些喜好进⾏度量和打分。
根据不同⽤户对相同商品或内容的态度和偏好程度计算⽤户之间的关系。
在有相同喜好的⽤户间进⾏商品推荐。
简单的说就是如果A,B两个⽤户都购买了x、y、z三本图书，并且给出了5星的好评。
那么A和B就属于同⼀类⽤户。
可以将A看过的图书w也推荐给⽤户B。
基于⽤户协同过滤算法的原理图所以，协同过滤算法主要分为两个步骤：1、寻找相似的⽤户集合；2、寻找集合中⽤户喜欢的且⽬标⽤户没有的进⾏推荐。
具体实现⼀、寻找⽤户间的相似度1、Jaccard公式Jaccard系数主要⽤于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此⽆法衡量差异具体值的⼤⼩，只能获得“是否相同”这个结果，所以Jaccard系数只关⼼个体间共同具有的特征是否⼀致这个问题。
如果⽐较X与Y的Jaccard相似系数，只⽐较xn和yn中相同的个数。
Jaccard公式2、⽪尔逊相关系数⽪尔逊相关系统是⽐欧⼏⾥德距离更加复杂的可以判断⼈们兴趣相似度的⼀种⽅法。
它在数据不是很规范时，会倾向于给出更好的结果。
假定有两个变量X、Y，那么两变量间的⽪尔逊相关系数可通过以下公式计算：公式⼀：⽪尔逊相关系数公式⼀公式⼆：⽪尔逊相关系数公式⼆公式三：⽪尔逊相关系数公式三公式四：⽪尔逊相关系数公式四上述四个公式等价，其中E是数学期望，cov表⽰协⽅差，N表⽰变量取值的个数。
3、欧⼏⾥德距离假定两个⽤户X、Y，均为n维向量，表⽰⽤户对n个商品的评分，那么X与Y的欧⼏⾥德距离就是：多维欧⼏⾥德距离公式数值越⼩则代表相似度越⾼，但是对于不同的n，计算出来的距离不便于控制，所以需要进⾏如下转换：相似度公式使得结果分布在(0,1]上，数值越⼤，相似度越⾼。
小型微型计算机系统Journal of C hinese C om puter S ystem s2010年5月第5期V ol 131N o .52010 收稿日期:2009202218 基金项目:国家自然科学基金项目(60775037)资助;国家“八六三”高技术研究发展计划项目(2009AA 01Z 132)资助. 作者简介:刘 淇,男,1986年生,硕士研究生,研究方向为数据挖掘、推荐系统、社会网络;陈恩红,男,1968年生,博士,教授,博士生导师,研究方向为语义W eb 、机器学习与数据挖掘、网络信息处理、约束满足问题.结合二部图投影与排序的协同过滤刘 淇,陈恩红(中国科学技术大学计算机科学与技术学院,安徽合肥230027)E 2m ail:cheneh @ustc .edu .cn摘 要:协同过滤是推荐系统中应用最为广泛的方法.提出一类基于二部图一维投影与排序相结合的协同过滤算法,文中采用结构相似进行二部图投影并利用随机游走对节点排序.该方法不仅可以防止冷启动,具有较高准确度,且可扩展性良好.另外,该算法可以避免低覆盖率造成的推荐不准确.算法可以有两类不同的实现,分别是基于项协同过滤的项排序算法和基于用户协同过滤的用户排序算法,在标准数据集M ovieL ens 上的测试表明了算法的有效性.关键词:协同过滤;二部图投影;结构相似;排序;随机游走中图分类号:TP 311 文献标识码:A 文章编号:100021220(2010)0520835205Coll abora ti ve F ilter i n g Through Co m b i n i n g B i partite Graph Projecti on and Rank i n gL I U Q i,CH EN En 2hong(School of Computer Science and Technology U niversity of Science and Technology of C hina,Hefei 230027,China )Abstract:C ollaborative F iltering is the m ost w idely used app roach in recomm ender system s .This paper p roposes a novel collaborative filtering app roach through com bining bipartite graph p rojection and ranking .In our app roach bi partite graph is p rojected based onstructural si m ilarity and random w alk is used to rank the nodes .This m ethod can not only deal w ith "cold start p roblem "to get high p recision but also have good scalability .M oreover,our m ethod can generate the rank based on the si m ilarity bet w een all user 2item pairs,thus m aking it avoids inaccuracy caused by low coverage rate .The algorithm is tested in both the item 2collaborative 2based item ranking w ay and the user 2collaborative 2based user ranking w ay .The experi m ental results obtained on a benchm ark dataset M ovielens clearly show the effectiveness of our p roposed app roach .Key words:collaborative filtering;bipartite graph p rojection;structural si m ilarity;ranking;random w alk1 引 言推荐系统根据用户与系统的交互历史以及用户的个人信息等构建用户的兴趣模型,去预测用户可能感兴趣的产品或项.推荐系统大致可以分为三类[1]:基于协同过滤的方法(collaborative filtering )[2,4],基于内容的方法(content 2based filtering )[5,8]和将二者结合的混合推荐算法(hybrid recom 2m endation )[6,7].其中,基于协同过滤(C F )的方法在保持较好推荐效果的同时,其实现和维护代价都比较低,因而得到了最广泛的应用.例如,M ovieL ens 系统[3,9]利用C F 做电影推荐,Am azon .com[2]利用C F 推荐书籍,CD 等产品,还有为用户推荐新闻和电影的G roupL ens [4]等等.协同过滤又可以分为基于用户的协同过滤和基于项的协同过滤,前者认为给定用户会喜欢那些与他们有相似喜好的用户所喜爱的项,而后者则认为给定的项会被那些喜欢与它们相似的项的用户所喜欢[2,4].推荐的准确性是推荐系统是否有效的一个重要评判标准,然而在实际应用中还要综合考虑算法的时空复杂性,随着项和用户数目的增加导致算法实现的可扩展性等等问题.例如,因为实际系统中的用户数往往比项数有更高的数量级,所以基于用户的协同过滤算法会面临扩展瓶颈.而在一个项数目更高的系统中,如果使用基于项的协同过滤算法也会面临同样的问题.更多的情况下,同一个系统中项的数目与用户数目是时高时低的,这就需要一种可以随时应变的协同过滤算法,当项数目过高时就采用基于用户的协同过滤,而当用户数目过高时就采用基于项的协同过滤.本文提出一类基于二部图投影和排序的协同过滤算法框架(B i partite G raph P rojection and R anking,B G PR )并提出基于此框架的一个具体实现.在B G PR 中,首先用二部图表示用户对项的喜好关系,二部图的两类顶点分别表示用户和项,通过对二部图进行一维投影就可以将其转化成一个表示用户间或项之间相似关系的图.再根据特定的排序算法对投影图中的节点进行排序.不用预测用户对项的可能打分,就可以产生推荐序列.而且,B G PR 算法既可以实现基于项的协同过滤又可以实现基于用户的协同过滤,即分别将项作为投影图中的节点为给定用户对所有项进行排序的方法和将用户作为投影图中节点为给定项进行用户排序的方法.本文主要贡献在于:提出基于B G PR 的协同过滤算法框架,因为可以采用不同的二部图投影方案和对节点的排序方法,所以基于此框架有可以有许多不同的协同过滤算法实现. 提出一个具体的B G PR算法实现,其中利用结构相似作为二部图投影时的连边权重学习方法,然后将待推荐对象在投影图上进行带重启动的随机游走(RW R,random2w alk w ith restart),根据待推荐对象停留在每个节点的概率对图中的节点进行排序.通过在一个推荐系统的通用数据集M ovieL ens[9](由M innesota大学的G roupL ens研究小组提供)上的实验结果验证了B G PR算法比其它优秀算法有更高的推荐准确度.2 相关工作近十年来,已经有大量基于协同过滤的推荐系统出现在科研或实际应用中.一部分学者提出了一种启发式的、根据用户以往的所有评价去推荐的M em ory2based方法.这种方法的一般思路是先为每个用户寻找相似的用户,再根据相似用户对给定项的打分和用户相似度进行项的排序[1],然而,M em o2 ry2based方法不能很好地应对数据稀疏的情况而且其可扩展性往往比较差.而另有一部分学者研究了利用已有的用户评价数据建立一个模型,然后根据此模型进行评价预测的M od2 el2based方法,例如到目前为止已经有人提出了基于贝叶斯网络的方法[11],基于最大熵的方法[10]等等,但是M odel2based 方法经常需要花费大量时间建立和更新模型,而且其模型经常不能像M em ory2based方法一样覆盖所有的用户和项.近来,也有学者提出基于图中顶点相似计算的方法来进行协同推荐[15,17,19].在其它领域中,[12]总结和比较了大量的计算图中结点相似的方法用来进行连边预测.[13]也提出了一种新的度量网络中顶点结构相似的方法.在图结构中,经常用随机游走(R andom w alk)对节点间的相似度进行衡量[15,16,19],该方法以两个节点间的平均首达时间(AC T,average comm ute ti m e)为标准.但A C T的问题在于它对图中远离节点i,j的部分有很强的依赖,即使节点是紧密相连的时候也是一样,所以经常会造成计算得到的相似度与实际相似度有较大偏差.[22]利用每次游走有限步作为抵消该依赖的一种方法.另一种抵消方法是,让从节点i到节点j的游走周期性"重启动",即每一步以一定的概率c返回i 重新走步,这样几乎不会走到图中偏远的部分.随机重启也是进行网页排序的PageR ank算法[14]的基本思想.[18]用带重启动的随机游走(RW R,random w alk w ith restart)来发现已知多媒体对象中各个媒体属性间的关联,而[21]则用RW R来发现情感与音乐属性的关联从而进行音乐推荐.类似地, [17]也将PageR ank算法的思想用到推荐系统中.实际应用中,推荐算法不仅要求较高的预测准确度,还要具备良好的扩展性,但是目前的推荐算法都有其不足之处.例如,基于聚类的方法往往不能有效地覆盖所有的项或者用户,而基于图的方法虽然可以为所有的用户2项对产生相似排序,但往往消耗大量的空间资源,可扩展性较差,而且其推荐准确度也有待提高[15,19].基于上述分析,本文提出了基于二部图投影和对投影后得到的关联图中节点进行排序的B G PR推荐算法.下面,通过基于结构相似进行二部图投影和RW R进行节点排序的一个具体实现,详细介绍B G PR算法框架.3 BGPR算法描述协同过滤是为给定用户推荐其可能感兴趣的项,但也可以将给定的项推荐给可能对其感兴趣的用户.对于前者,B G2PR将投影得到由项组成的关联图,然后用给定用户的用户向量在相应的项关联矩阵上进行RW R,从而得到所有项的排序,排名靠前即得分较高的项将被推荐给用户(Item-R ank,因为实验中使用的item为电影,所以又称M ovie-R ank).而对于后者,B G PR将投影得到用户组成的关联图,然后用给定项的项向量在相应的用户关联矩阵上进行RW R,得到所有用户的排序,该项将被推荐给得分较高的用户(U ser-R ank).本文,I表示项的集合,U表示用户的集合;n,m分别表示项和用户的个数.3.1 二部图投影将用户与项之间的关系表示为一个二部图G=〈X,E〉,其中顶点集X=U∪I,用户Up如果对项Iq表现出兴趣,则为Up与Iq建立一条连边.然后,将该二部图分别在两个维度(用户,项)上进行投影,得到对应的一维投影图.投影后节点i与j间的连边权重σ(i,j)表示节点i与j的相似度.用矩阵CC表示投影图对应的关联矩阵,CC i,j=σ(i,j).投影的过程会造成原二部图信息的损失,因此如何计算σ(i,j)使其能最好地揭示出节点i,j在原二部图中的相似情况不仅是投影过程中的关键也是对节点正确排序的重要保证.本文选择利用结构相似的计算方法来求解σ以及CC.实验中选择下面四种结构相似计算方法: σunnor m(i,j)=|Γi∩Γj|(1) σjacca rd(i,j)=|Γi∩Γj||Γi∪Γj|(2) σcosine(i,j)=|Γi∩Γj||Γi|3|Γj|(3) σm in(i,j)=|Γi∩Γj|m in(|Γi|,|Γj|)(4)其中,Γi为投影前节点i的邻居节点集合.σ(i,j)可以分别由公式(1)(2)(3)(4)得到.图1(b),1(c)就是二部图1 (a)根据公式(1)得到的两个投影.这里的每个投影图就是项或者用户组成的关联图.相应地,可以得到关联图对应的矩阵CC,其中当i≠j时,CCi,j=σ(i,j),且CCi,i=0.为了与RW R相结合,再对CC以列为单位进行归一化得到随机矩阵C,C可以视为关联图的关联矩阵, C i,j表示节点i对于节点j的关联系数,即对节点j而言节点i 的重要程度.这样,关联图中所有节点对间的关联程度都可以用C中相应的元素表示.可以看到CC是一个对称矩阵,而C 则不再具有这个性质.例如,图1(b)对应的用户关联矩阵C就可以表示为:CU=00.2000.2730.2220.1670.1430.12500.0910.1110.1670.1430.3750.20000.3330.3330.2860.2500.2000.27300.1670.2860.1250.2000.1820.11100.1430.1250.2000.1820.2220.1670638 小 型 微 型 计 算 机 系 统 2010年3.2 排序算法B G PR 算法的目标是通过排序的方式估计用户与项之间的关系.B G PR 用向量表示查询节点,向量中的每一维都代表关联图中的一个节点,其值则表示相应节点与该查询节点的亲和度.B G PR 采用带重启动的随机游走(RW R )来预测一个节点(或向量)Y 对查询节点(或向量)X 的重要性或关联程度.考虑从节点向量X 开始的随机游走,每走一步保证两件事情:首先,如果一个节点Z 与节点P 联系紧密,而X 又是与P 相关联的,则通过P,X 与Z 也会建立一定的联系.其次,由于X 是通过间接的方式与Z 建立联系的,所以相比较P 与Z,X 与P,X 与Z 的联系强度会有一定的"衰减".图1 用户与项组成的二部图(a ),以及它在用户维与项维的两个投影(b )(c )F ig .1 A bi partite graph about users and item s (a ),w ithits t w o p rojections on users (b ),item s (c )或者说,X 游走到P 以后会以一定的概率沿P 走向与P有联系的节点.而除此之外,它还有可能返回节点X 重新走步,来消除远端依赖[12].定义steady 2state 概率S X (Y )表示从节点X 开始的随机游走到达节点Y 的概率.那么S X (Y )就表示了Y 相对于X 的亲密程度.定义O q 为查询对象,它可以是一个用户或一个项,如果O q 是一个用户,B G PR 算法要得到与它关系最紧密的项,而如果O q 是项,B G PR 算法得到与它关系最紧密的用户.这里若关联图或关联矩阵C 由k 个节点组成,则O q 对应的stead 2y 2state 概率向量S q =(S q (1),…,S q (k ))即为所求.定义归一化向量V O q 是根据O q 在训练集中的记录而建立的节点向量,在归一化V O q 之前向量V ′oq 第j 维的元素对应于:V ′O q j=1 if O q is user and O q ra ted I j ,or if O q is item and U j ra ted O q0 other w ise(5)由3.1和3.2本文设计的推荐算法B G PR 如图2所示.在推荐算法B G PR 中,可调参数c 为随机游走重启动的概率,(12c )为衰减因子,用来衡量信息的衰减程度.实际应用中,平均情况下,t =20时,S O q 即可收敛[17].考虑一个简单的例子,如果根据结构相似公式(1)进行二部图投影然后对图1(a )中的用户U 6做推荐预测.U 6的节点向量V u 6=(0,0,0.5,0.5,0),运行B G PR 算法,得到一个关于项的steady 2state 概率向量S U 6=(0.002357,0.001176,0.496886,0.496674,0.002903).此时I 5最有可能推荐给U 6.作为验证,再对I 5做用户推荐预测,则其节点向量V I 5=(0.333,0,0.333,0.333,0,0),再次运行B G PR 算法,得到一个关于用户的steady 2state 概率向量S I 5=(0.331319,0.001089,0.332028,0.331414,0.001391,0.001755),与前边的结果相符,此时可以发现I 5最有可能被推荐给U 6.输入:表示用户与项之间关系的二部图G,待推荐对象O q ,参数c 输出:对O q 的推荐序列1.根据公式(1)(2)(3)或(4)得到G 的一维投影图对应的关联图,若O q ∈U ,则投影得到关于项的关联图,若O q ∈I,则投影得到关于用户的关联图2.令关联图对应的矩阵CC 对角线的元素为0,再以列为单位将其归一化,得到关联矩阵C3.由(5)得到向量V ′O q ,并对其归一化得到向量V O q4.t =0,初始化S O q =V O q5.w hile (S O q 不收敛‖t <M AX -LOO P )6.{7. S O q =(1-c )3C 3S O q +c 3V O q 8. t ++9.}10.按照大小将S O q 中的元素排序11.若S O q (j )排名靠前且V O q (j )=0,则将S O q (j )对应的项(用户)推荐给O q ,得到O q 的推荐序列图2 推荐算法B G PR 流程Fig .2 Flow chart of B G PR algorithm4 实 验M ovieL ens[3,9]是一个进行电影推荐的网站,G roupL ens小组从中整理出了适用于各种推荐场景的一个标准数据集.在本文使用的数据集中,对用户进行了处理,只考虑那些对超过20部电影打分的用户,总共包含943个用户(m =943)对1,682部电影(n =1,682)的评分,共约100,000个评分.实验中使用数据集的方法与[15,17,19]中类似:对于参数训练部分(主要是对参数c 的测试),将整个数据集分成训练集与测试集两部分,而测试部分则使用五对数据集进行52交叉测试,每次用80%的评分数据做训练集20%的评分数据作为测试集.4.1 评价标准本文采用DOA (degree of agreem ent )[20]为标准对实验结果进行评价.根据使用对象的不同将其扩展为用户的DOA(U -DOA )和项的DOA (I -DOA ),其思想是:对于U -DOA ,先定义NW ui =n /(L ui ∪T ui ),其中n 为所有项的个数,L u i 为用户U i 在训练集中评价过的项集合,T ui 为U i 在测试集中评价的项集合.check -order U i (I j ,I k )=1, if (p redict -rank Ij ≥p redict -rank Ik )0, other w ise从而对于用户U i ,其DOA 得分定义如下:DOA U i =∑(j ∈T U i ,k ∈NW U i)check -order (I j ,I k )|T U i |3|NW U i |(6)I -DOA 的定义与U -DOA 类似,这里不再赘述.通过定义可以看出,随机预测的DOA 值大约为50%,而理想情况下7385期 刘 淇等:结合二部图投影与排序的协同过滤 的DOA 值为100%.并且,实验中以所有用户(项)的DOA 取平均作为总体的效果评价.U -DOA =∑U i DOA U i |U |或I -DOA =∑I iDOA Ii |I |4.2 参数选择及实验结果图3 随着c 的变化各个方法的表现Fig .3 B G PR perfor m anceunder different c在PageR ank 算法中重启动概率c经常取为0.15,而在实验中,通过各个方法对c 在(0,1)之间变化时的表现情况可以发现,c 越接近于1,B G PR 算法的推荐效果越好.其实这一方面与所用的关联图的半径有关[18],一方面与数据的性质有关,在当前的M ovieL ens 数据集中,项(用户)的相似度绝大部分比例依赖于项(用户)间的直接路径数.图3显示了随着c 的变化,几种二部图投影方法对应的B G PR 算法的表现.接下来的实验中若无特殊说明,选择c =0.99.表1 M ovie -R ank 52交叉测试结果Table 1 M ovie -R ank perfor m ance on 52fold cross validationM ETHOD SPL IT 1SPL IT 2SPL IT 3SPL IT 4SPL IT 5M EAN M ovie -Rank DOA (%)U nnor m89.0589.1289.2989.0988.8889.09Jaccard 90.2990.3790.6490.3890.1790.37Cosine 90.5790.6891.0290.6790.5390.69M in80.9880.4081.6580.3480.1680.71表1、表2显示了不同的结构相似对应的M ovie -R ank 和U ser -R ank 方法在进行52交叉测试时的表现.表3显示了使用M ovieL ens 作为数据集的不同推荐算法的效果比较,这些算法的具体细节和实现可以参见[15,17,19].这里B G PR 算法选择基于M ovie -R ank 的C osine 结构相似(M R -C osine )为代表与其他算法进行比较,其中的ItemR ank[17]与本文基于公式(1)的M ovie -R ank 实现方法类似.表2 U ser -R ank 52交叉测试结果Table 2 U ser -R ank perfor m ance on 52fold cross validationM ETHOD SPL IT 1SPL IT 2SPL IT 3SPL IT 4SPL IT 5M EANU ser -Rank DOA (%)U nnor m 75.5281.1580.9979.9476.4078.80Jaccard 74.0680.7581.1180.5676.8678.67Cosine 74.3581.0481.6080.9477.3479.05M in 67.9475.5676.9175.4772.4273.66对于其中的每个算法,给出了其52交叉测试后的平均实验结果,以及与传统的M axF 算法的表现差异比较.M axF 算法简单地将项按被浏览次数进行降序排序,每次都将其没有评价过且排序最靠前的项推荐给给定用户[17].M axF 算法也是比较的基准算法.4.3 讨 论首先,由表1、2可以发现在同一个数据集中,将二部图投影得到电影之间的关联图然后对电影排序(M ovie -R ank )的推荐效果明显优于建立用户之间的关联图然后对用户排序(U ser -R ank )的结果,其实这与M ovieL ens 数据集的性质有关.M ovieL ens 数据集对用户进行了处理只保留了至少评价了20部电影的用户,以保证每个用户的兴趣都可以得到确切的反映,而数据集中的电影却没有经过相似处理.对用户的处理可以让一般的推荐算法防止"冷启动"问题但是B G PR 算法采用了RW R 做为距离评判标准,可以有效地防止"冷启动"问题.而且对用户的预处理使得B G PR 构造的用户关联图过于稠密(数据显示用户关联图对应的用户关联矩阵中非零元素的比例在[0.922,0.934]区间,而此比例在项关联图中仅为[0.625,0.642]),从而降低了用户与用户间的区分度,造成了对用户排序(U ser -R ank )的不准确.图4显示了电影度数的幂律分布情况,图中电影度数服从λ=0.8的幂律分布(p (k )～k 2λ),这说明M ovieL ens 数据集的电影网络可以反映实际情况中的电影度数分布,同时根据这种实际数据所得到的电影关联图可以有效地反映电影间的相似情况,即M ovie -R ank 算法的优秀推荐效果在实际应用中也可以得到.总之,利用RW R 可以有效地防止"冷启动"问题,而且根据实际数据构造的关联图可以与RW R 紧密融合,使得B G PR 算法有巨大的实用价值.表3 不同算法效果比较Table 3 C om parison bet w een different algorithm sA lgorithm DOA (%)D ifference w ith M axF (%)M ovie -RankM AXF 84.070CT 84.09+0.02PCA C T 84.0420.03O ne 2w ay 84.08+0.01Return 72.63211.44L +87.23+3.16Item Rank 87.76+3.69Katz85.83+1.76BGPR (M R -Cosine )90.69+6.62在计算效率方面,给定关联矩阵C 时,B G PR 只要经过较少次数的迭代就可在O (n 2)或O (m 2)时间里得到一次推荐,图4 电影度数的幂律分布Fig .4 Pow er 2law distributionof M ovies ′degree而L +或者C T 算法只能一次得到所有推荐,所以只能定时更新推荐而无法做到实时更新推荐.但B G PR 算法的一个问题在于,如果关联矩阵C 中有一个节点发生了更新,则整个关联矩阵都需要更新,这将消耗O (n 2)或O (m 2)的时间,所以可以选择定时更新关联矩阵C 而实时更新节点向量的方法,以得到更好的推荐效果.838 小 型 微 型 计 算 机 系 统 2010年最后是算法的空间复杂度和可扩展性.当基于项过滤对项进行排序时,关联矩阵C的大小与用户数无关,这是一个很有用的性质.因为一般的应用中,用户数目比项的数目有更高的数量级[17],而且一般用户可能只对少数的一些项感兴趣,可以将用户的兴趣直接用链表的形式表现出来,从而节省巨大的空间资源.如果用ku表示每个用户平均感兴趣的项个数,那么此时算法的空间复杂度为O(n2+m3ku),即使用户数目不断增加,用户对项的兴趣也不断增加,B G PR算法都可以有效地应用.当有新的项时,B GPR和Item R ank只需要O (n)的空间消耗,其L+与C T等则需要O(m+n).而当增加一个新用户时Item R ank和B G PR需要O(ku)的空间,而L+, C T等算法却需要O(m+n)的空间,问题在于在一般的应用中mµnµku.而基于用户过滤的用户排序,虽然空间消耗可能要高于对项排序的方法,但仍然小于L+与C T等方法,这里不再赘述.5 结 论本文展示了一种基于二部图投影与排序相结合的协同过滤推荐算法B G PR,它可以预测每个用户可能喜欢的项,也可以将项推荐给那些可能喜欢它的用户.更重要的是B GPR是一个协同过滤的框架算法,基于不同的二部图投影和排序方案可以产生不同的推荐算法.文中采用结构相似进行二部图投影再利用带重启动的随机游走(RW R)对图中的节点进行排序从而产生推荐序列,通过带重启动的随机游走可以使得投影图的节点相似信息得到扩散从而防止"冷启动"问题而且提高了推荐准确度.通过在同一个数据集上与其它的一些优秀算法的比较证实了B G PR不仅有更高的推荐准确度,同时保持较低的时空复杂度,较好的可扩展性,而且可以适用于不同情况的针对海量数据的实际推荐应用中.由结构相似得到的投影图可以用来描述原二部图所隐含的节点间的信息.但是这类相似计算方法是对称性的,认为σ(i,j)等于σ(j,i),即节点i,j视对方是同等重要的.其次,结构相似简单地视节点i,j的所有邻居节点对i,j的相似程度有相同的影响,然而,假设节点s,t∈Γi ∩Γj,且ΓsµΓt,则显然邻居节点t应当比邻居结点s更能说明节点i,j相似.由于结构相似存在着以上种种缺点和不足,使其不能完全地反映原二部图所隐含的节点间的相似信息.为了更准确地挖掘原二部图的信息,寻找新的二部图投影方案将是未来工作的主要努力方向.References:[1]Gedi m iinas A dom avicus,A lexander Tuzhilin.Tow ard the nextgeneration of recomm ender system s:a survey of the state2of2the2art and possible extensions[J].IEEE Transactions on Know ledge andD ata Engineering,June2005,17(6):7342749.[2]L inden G,Sm ith B,York J.Am recomm endations:i2tem2to2item collaborative filtering[J].IEEE Internet Com puting, 2003,7(1):76280.[3]M iller B N,A lbert I,L am S K,et al.M ovieL ens unp lugged:ex2periences w ith an occasionally connected recomm ender system[C].Proceeding of Int′l Conf.Intelligent U ser Interfaces,M iam i, USA:2003,2632266.[4]Resnick P,Iacovou N,Suchak M,et al.G roup lens:an open ar2chitecture for collaborative filtering of netnew s[C].Proceeding ofthe CSCW C onference,Chapel H ill,N C:1994,1752186.[5]Ki m J W,L ee B H,Shaw M J,et al.App lication of decision2treeinduction techniques to personalized advertisem ents on Internet storefronts[J].International Journal of E lectronic C omm erce,2001,5(3):45262.[6]B alabanovic M,Shoham Y.Fab:content2based,collaborative rec2omm endation[J].Comm.A CM,1997,40(3):66272.[7]PazzaniM.A fram ew ork for collaborative,content2based,and de2m ographic filtering[J].A rtificial Intelligence R ev.,D ec.1999,13:3932408.[8]Souvik D ebnath,N iloy Ganguly,Pabitra M itra.Feature w eightingin content based recomm endation system using social net w ork anal2 ysis[C].Proceedings of WWW,B eijing,China:Ap ril,2008,pages104121042.[9]htt p://www.m ovielens.um .[10]Pavlov D,Pennock D.A m axi m um entropy app roach to collabora2tive filtering in dynam ic,sparse,high2di m ensional dom ains[C].Proceedings of16th A nn.C onf.N eural Infor m ation ProcessingSystem s(N IPS′02),Canada:2002,144121448.[11]B reese J S,Hecker m an D,Kadie C.Em p irical analysis of p redic2tive algorithm s for collaborative filtering[C].Proceedings of the14th Conference on U ncertainty in A rtificial Intelligence,M adison:1998,43252.[12]D avid L iben2N ow ell,Jon Kleinberg.The link2p rediction p roblemfor social net w orks[J].Journal of the Am erican Society for Infor2 m ation Science and Technology,2007,58:101921031.[13]L eichtE A,Petter Hol m e,N ewm an M E J.V ertex si m ilarity innet w orks[J].Physical Review E,2006,73:026120.[14]B rin S,Page L.The anatom y of a large2scale hypertextual W ebsearch engine[J].Com puter N et w orks and ISDN System s,1998,30(127):1072117.[15]Fouss F,Pirotte A,Sarens M.R andom2w alk com putation of si m i2larities bet w een nodes of a graph,w ith app lication to collaborativerecomm endation[J].IEEE T ransactions on Know ledge and D ataEngineering,2007,19(3):3552369.[16]L uh Yen,M arco Saerens,Am in M antrach,et al.a fam ily of dis2si m ilarity m easures bet w een nodes generalizing both shortest2pathand the comm ute2ti m e distances[C].Proceedings of the ACMS I GKDD International Conference on Know ledge D iscovery andD ata M ining(KDD),L as V egas,USA:2008,7852793.[17]M arco Gori,A ugusto Pucol.A random2w alk based scoring algo2rithm w ith app lication to recomm ender system s for large2scale e2 comm erce[C].Proceedings of W EB KDD′06,Philadelphia,U SA:2006,1272146.[18]Pan J Y,Yang H J,Faloutsos C,et al.A utom atic m ulti m ediacross2m odal correlation discovery[C].Proceedings of A CM Intl.Conference on Know ledge D iscovery and D ata M ining(KDD′04),Seattle USA:2004,6532658.[19]Fouss F,Pirotte A,R enders J M,etal.A novel w ay of com putingdissi m ilarities bet w een nodes of a graph,w ith app lication to collab2 orative filtering[C].Proceedings of IEEE/W IC/ACM Interna2tional Joint Conference on W eb Intelligence,C om p iegne,France:2005,5502556.[20]S iegel S,Castellan J.N onparam etric statistics for the behavioralsciences[M].N ew York,USA:M cG raw2H ill College,1988. [21]Kuo F F,Chiang M F,Shan M K,et al.Em otion2based m usicrecomm endation by association discovery from fil m m usic[C].Proceedings of the13th A nnual A CM International Conference onM ulti m edia.S ingapore:2005,5072510.[22]Sarkar P,M oore A.A tractable app roach to finding closest trun2cated2comm ute2ti m e neighbors in large graphs[C].Proceedingsof UA I.V ancouver,BC,Canada:2007.9385期 刘 淇等:结合二部图投影与排序的协同过滤 。
