推荐算法综述_1

推荐算法综述苏芳芳2014-10-14电子商务推荐将电子商务系统的浏览者转变为购买者：浏览者经常没有购买欲望，电子商务推荐他们感兴趣的商品，从而完成购买过程。提高电子商务系统的交叉销售：推荐用户确实需要但是在购买过程中没有想到的商品列表。保留用户：提高推荐质量，让用户对该系统产生依赖。研究内容和方向推荐技术研究实时性研究推荐质量研究多种数据多种技术的集成数据挖掘技术的应用（关联规则挖掘、序列模式挖掘、聚类分析、贝叶斯分类）用户隐私保护研究推荐系统可视化研究（可视化研究和推荐结果解释研究）推荐算法主要算法协同过滤推荐算法基于内容的推荐算法基于图结构推荐基于关联规则推荐基于知识推荐混合推荐协同过滤推荐协同过滤推荐算法有：•基于用户的协同过滤推荐算法•基于项目的协同过滤推荐算法•基于降维的协同过滤推荐算法•基于聚类的协同过滤推荐算法基于用户的协同过滤推荐基于用户协同过滤推荐根据其他用户的观点产生对目标用户的推荐列表基于用户的协同过滤推荐算法步骤：1、数据表示：对用户已经购买过的商品进行建模2、最近邻查询：计算相似度，搜索当前用户的最近邻居3、推荐产生：根据最近邻对商品的评分预测当前用户对商品的评分，产生top-N商品基于用户的协同过滤推荐1、数据表示基于用户的协同过滤推荐2、最近邻查询计算当前用户和其他用户的相似度，选择相似度高的若干用户作为最近邻。相似度计算：余弦相似性修正的余弦相似性相关相似性（pearsoncorrelation）基于图结构的相似度基于用户的协同过滤推荐相似度计算方法•余弦相似性：•修正的余弦相似性：•相关相似性：基于用户的协同过滤推荐3、推荐产生计算用户u对项i的预测评分Pu,i:选择评分高的的若干项目推荐给用户u。基于项目的协同过滤推荐基于项目协同过滤推荐根据用户对相似项最近邻居的评分产生对目标用户的推荐列表基于项目的协同过滤推荐算法步骤：1、最近邻查询：搜索目标项的最近邻居2、推荐产生：根据用户对目标项最近邻居的评分预测用户对目标项的评分，产生top-N商品基于聚类的协同过滤推荐将整个用户空间根据用户的购买习惯和评分特点划分为若干个不同的聚类；根据每个聚类中用户对商品的评分信息生成一个虚拟用户，将所有虚拟用户对商品的评分作为新的搜索空间；查询当前用户在虚拟用户空间中的最近邻居，产生对应的推荐结果。查询效率高、实时响应快基于聚类的协同过滤推荐--划分聚类K-means聚类算法：1).随机选择k个用户作为种子节点,将k个用户对项的评分数据作为初始的聚类中心。2)对剩余的用户集合,计算每条用户与k个聚类中心的相似性,将每个用户分配到相似性最高的聚类中。3)对新生成的聚类,计算聚类中所有用户对项的平均评分,生成新的聚类中心。4)重复以上2到3步,直到聚类不再发生改变为止。基于聚类的协同过滤推荐虚拟用户集生成根据不同的聚类生成对应的聚类中心,聚类中心与聚类中其他用户的距离之和最小,代表该聚类中用户对商品的典型评分。将所有的聚类中心作为虚拟的用户集合。基于聚类的协同过滤推荐推荐产生在虚拟的用户集合上使用各种相似性度量方法搜索当前用户的若干最近邻居,然后根据最近邻居对商品的评分信息产生对应的推荐结果。最近邻搜索和推荐产生的方法跟协同过滤推荐算法类似,在此不再赘述。协同过滤优缺点及改进协同过滤优点：交叉推荐协同过滤缺点：冷启动基于内容的过滤协同过滤方法只考虑了用户评分数据,忽略了项目和用户本身的诸多特征,如电影的导演、演员和发布时间等,用户的地理位置、性别、年龄等.如何充分、合理的利用这些特征,获得更好的推荐效果,是基于内容推荐策略所要解决的主要问题。主要算法：文本推荐方法基于潜在语义分析的推荐自适应推荐文本推荐方法基于内容的推荐方法根据历史信息(如评价、分享、收藏过的文档)构造用户偏好文档，计算推荐项目与用户偏好文档的相似度,将最相似的项目推荐给用户。相比于多媒体信息(视频、音频、图片等)，文本类项目(新闻、网页、博客)的特征提取相对容易,因而基于内容的推荐方法在文本类推荐领域得到了广泛应用。基于潜在语义分析的推荐关键词的同义和多义现象往往导致文档相似度计算不准确。基本思想：采用文档-词矩阵奇异值分解的方法将文档和词语映射到同一个低维的潜在语义空间中计算各文档与用户查询之间的相似度,据此返回最相关的文档缺点：采用奇异值分解得到的潜在语义空间物理意义不明确，矩阵的奇异值分解计算量大。自适应推荐基于内容推荐的关键是构建和更新用户偏好文档。用户的兴趣会随时间动态变化。解决方法：采用贝叶斯分类、决策树、聚类、人工神经网络等机器学习方法。基于内容的推荐算法缺点：新用户问题、过拟合问题、多媒体信息特征难提取等。基于关联规则推荐算法关联规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同事购买了商品集Y。基于关联规则的推荐算法根据生成的关联规则推荐模型和用户的购买行为向用户产生推荐。关联规则推荐模型的建立离线进行，可以保证有效推荐算法的实时性要求。基于图结构的推荐算法1、用户-项目矩阵可建模为一个二部图(bipartitegraph),其中节点分别表示用户和项目,边表示用户对项目的评价。基于图结构的推荐算法2、计算资源分配矩阵W。项目j到项目i的资源分配权重wij计算如下:其中Dj表示节点j的度。基于图结构的推荐算法3、针对指定用户计算各项目的资源分配。令fi=(ai1,ai2,…,aim)表示用户i的对m个项目的初始资源分配，f′i表示用户i的对m个项目的最终资源分配,则有f′i=Wfi。4、根据f′i产生推荐列表。按f′i中从大到小的顺序排列生成一个推荐项目列表(用户已经偏好的项目除外)。基于知识的推荐算法协同过滤和基于内容的推荐算法各有优势。但在很多情况下这些方法并不是最好的选择。比较典型的是，我们并不会非常频繁的购买房屋、汽车或计算机。这样我们可能无法依赖购买记录。基于知识的推荐不需要评分数据，没有冷启动问题。基于知识的算法根据显示知识领域模型进行推理。基于知识的推荐算法用户必须指定需求，然后系统设法给出解决方案。如果找不到解决方案，用户必须修改需求。此外系统还要给出推荐物品的解释。“汽车的最高价是X，颜色应该是黑的”混合推荐算法混合推荐是为解决协同过滤、基于内容和基于图结构推荐算法各自问题而提出的，达到“相互取长补短”的推荐效果。例如，基于内容方法可以解决协同过滤中“新项目”问题,而协同过滤可降低基于内容算法面临的“过拟合”问题。混合推荐可以独立运用协同过滤、基于内容和基于图结构的推荐算法，将两者或多者产生的推荐结果进行融合，再将融合后的结果推荐给用户。问题和分析推荐算法缺点和挑战•数据的稀疏性•冷启动•可扩展性•实时性•特征提取•推荐结果解释•过拟合•托攻击问题•隐私问题•多种数据和多种推荐技术的有效集成•自动化推荐（根据用户行为，不一定要显示评分）数据的稀疏性数据稀疏性的解决办法：•降维技术----压缩矩阵（采用奇异值分解方法删除不重要的或噪音用户和项目）•采用潜在语义索引技术•将用户-项目矩阵转换成用户-类别矩阵•矩阵填充技术（BP神经网络、NaïveBayesian分类方法、基于内容的预测、基于项评分预测的IRPRec）冷启动协同过滤的缺点：冷启动冷启动问题的解决方法：基于内容的最近邻居查找技术可扩展性可扩展性解决方法：•降维•聚类•分类•SVD等降维技术、基于最近邻的KNN算法、新的最近邻度量—相似度支持度、基于模型的CF算法（如聚类协同过滤算法）数据集常用的数据集：•MovieLens•EachMovie•BookCrossing•JesterJoke•Netflix•UsenetNewsgroups•UCI知识库评价准则统计精度度量：平均绝对误差MAE、均方根误差RMSE------为用户估计特定项目的评分决策支持精度度量：查全率recall、查准率precise、ROC(ReceiverOperatingCharacteristic)--------为用户产生一个推荐项目列表推荐系统推荐系统实例：TYPESTRY/ACF/GroupLens/MovieLens/Ringo/VideoRecommender/FAB电子商务应用：Amazon.com/CDNow.com/CtoBeBay.com谢谢！