【协同过滤推荐研究综述】协同过滤推荐算法

　　[摘要]针对传统协同过滤算法的局限性，探讨目前的各种改进思路，主要结合聚类、关联规则、贝叶斯、神经网络、云模型、维数简化、对等网等技术进行改进，重点评述改进现状和存在的问题，并归纳推荐系统的评估方法，最后对协同过滤推荐的未来进行展望。
　　[关键词]电子商务推荐系统个性化协同过滤
　　[分类号]c354
　　
　　1　引言
　　
　　推荐系统是为满足电子商务发展和解决网络信息超载而产生的，其关键和核心是采用的推荐技术和推荐算法。目前主要推荐技术有：基于内容推荐、协同过滤推荐、基于关联规则推荐、基于效用推荐、基于知识推荐和组合推荐。其中，协同过滤推荐技术在个性化推荐系统中应用最广，该推荐算法主要有两类：基于用户的协同过滤推荐算法…和基于项目的协同过滤推荐算法。前者基于这样一个假设，即如果用户对一些项目的评分比较相似，则他们对其他项目的评分也比较相似，算法通常采用最近邻技术寻找邻居用户，然后加权求目标用户对该项目的评分；后者从项目角度出发，寻找与该项目相似的若干项目，然后加权求目标用户对该项目的评分。但随着电子商务系统规模的不断扩大，它有三方面的限制，即准确性、稀疏性和可扩展性。
　　本文针对传统协同过滤技术存在的局限性，总结协同过滤推荐的各种改进思路，并归纳了推荐系统的评估方法，预测未来发展方向。
　　
　　2　协同过滤推荐技术及改进算法
　　
　　各种改进的协同过滤技术都是建立在传统协同过滤技术基础之上的，下面先探讨传统协同过滤技术及优缺点，再深入分析各种改进算法。
　　
　　2.1
　　传统协同过滤算法
　　2.1.1协同过滤推荐算法原理　协同过滤推荐算法的原理是利用用户的历史喜好信息来计算用户之间的距离，然后利用目标用户的“最近邻居”对商品评价的加权评价值来预测目标用户对特定商品的喜好程度，系统根据此喜好程度来对目标用户进行推荐。
　　2.1.2
　　算法优点
　　协同过滤最大的优点是对推荐对象没有特殊的要求，能处理非结构化的复杂对象，它具有如下一些优点：
　　?能够过滤难以通过机器自动进行基于内容分析的信息。
　　?共享其他人的经验，能够过滤一些复杂的、难以表达的概念。
　　?有推荐新信息的能力。这也是协同过滤和基于内容过滤的一个较大的差别，能够跨类别推荐，重在发现而不是搜索。
　　?能够有效地使用其他相似用户的反馈信息，加快个性化学习的速度。
　　2.1.3算法缺点　基于用户的协同过滤推荐系统有众多优点，但随着电子商务用户、商品规模的剧增，该算法也存在以下缺点：
　　?稀疏性。在一个大型电子商务系统中，用户购买商品的总量占网站总商品量的1％左右，而参与评价的用户评价项目数少于总项目数的10％，造成了评分矩阵非常稀疏。这样一方面导致难以寻找最近邻，另一方面计算相似性非常耗时。
　　?冷开始。又称第一评价问题，或新项目问题，从一定角度可以看成是稀疏问题的极端情况。一方面，它很难向新用户提供个性化推荐服务；另一方面，在这种情况下，仅有少量评价数据不可能产生精确推荐。
　　?扩展性。面对日益增多的用户和项目，扩展性将会成为制约推荐系统发展的一个瓶颈问题。
　　
　　2.2协同过滤推荐改进算法
　　尽管协同过滤技术在电子商务推荐系统中的应用获得了很大的成功，但随着商品数量和用户人数的不断增加，基于协同过滤的推荐系统的发展面临着算法的可扩展性和推荐质量两个主要挑战。在这种情况下，众多的研究人员提出了基于协同过滤的改进算法，改进算法主要体现在与聚类、关联规则、贝叶斯、云模型、神经网络或免疫网络、维数简化以及对等网等技术的结合。
　　2.2.1结合聚类技术
　　?基于项目的聚类。O’Connor等对项目进行聚类，在对应的聚类中搜索目标用户的最近邻，算法虽然提高了可扩展性但是推荐质量并没有提高，原因是每个聚类中的用户数并不是随着聚类中项目数的减少而减少，所以这种方法在用户对多个聚类中的商品均有评分的情况下并不理想。邓爱林等根据用户对项目评分的相似性进行聚类，从而只需要在与目标项目最相似的若干个聚类中就能寻找到目标项目的大部分最近邻，结果表明该算法能够保证在尽量小的项目空间上查询到目标项目尽量多的最近邻，从而有效提高推荐系统的实时响应速度。但实验是在计算目标项目与聚类中心相似性的时间代价相对于最近邻查询可以忽略的条件下成立的，当聚类数目很大的时候是不能忽略的。翁小兰等基于项目特征聚类的协同过滤推荐算法，选取k个具有代表性项目属性形成项目特征矩阵，并利用特征矩阵进行未评分项的预评分，其关键是要选择合适的特征属性，该算法可解决数据稀疏性和新产品的冷启动问题。
　　?基于用户的聚类。Adomavicius等利用用户评分的相似性对用户进行聚类，当用户离线时预处理用户数据，在线时利用已有的用户聚类寻找目标用户的最近邻并产生推荐。算法在一定程度上提高了推荐质量，但当用户评价数据极端稀疏时该方法依靠用户评价聚类的可靠性不高。Ranshid等用Bisecting K-means聚类生成每个聚类的代理用户，基于目标用户的相似代理用户进行推荐。查文琴等¨¨将用户对项目的关注相似性和用户对项目的评分相似性进行线性组合，利用组合后的相似性对用户进行聚类，更好地反映了用户的兴趣，在一定程度上提高了在线推荐的实时响应速度和推荐的精度。其中要注意关注相似性和评分相似性之问平衡因子的确定。
　　?基于用户和项目的聚类。Kohrs等引入树的概念，用户或项目为其节点，对用户和项目分别进行层次聚类，其相似性由其所处的层次决定，最后加权求和预测评分。George等采用co，clustering算法构建了一个动态框架，有效解决了实时性问题，同时并行处理用户和项目，提高了系统的可扩展性。张娜等采用k划分对项目进行聚类，产生k个用户一项目子矩阵，然后在项目聚类基础上进行k划分客户聚类，最后在目标用户所在的几个矩阵中寻找最近邻。但这种算法在样本数比较大的时候，计算量及复杂度很大，难以保证系统的实时性。
　　聚类通常采用离线方式建立模型以保证其实时性，但由于时间滞后性可能导致推荐与用户兴趣不符，因此支持用户动态更新的增量机制将是改进其推荐质量的一个新思路。同时聚类最大的缺陷是无论用户或项目分在一个类之后就不能出现在其他类中(而实际上用户的兴趣是广泛的)，从而导致推荐的质量不高。
　　2.2.2结合关联规则
　　基于关联规则的推荐算法根据生成的关联规则模型和用户当前的购买行为向用户产生推荐。Sandvig等认为基于关联规则的协同过滤推荐系统的鲁棒性和扩展性较之基于模型、基于最近邻等系统具有更高推荐精度。其原因是基于关联规则的推荐系统可以有效避免恶意评分的注入。曾艳等指出Apriori算法处理大量候选项集时开销很大， 而FP-Growth算法在判断节点加入FP-tree时开销可能也会很大，在前两种算法的基础上构造了AFP-树，其便于存储和查询频繁模式，而且能同时使用两种约束来挖掘模式，但AFP-树构建复杂度高。哈进兵等在关联规则的基础上引入了项目加权的概念，在计算频繁集时裁剪掉权重较小的项目，不仅能够减小运算的复杂度，而且还能实现“跨类型”推荐。
　　通过离线生成关联规则虽然解决了实时性问题，但在一定程度上不能及时反映用户的兴趣变化，而关联规则的频繁生成会增加成本。所以，定期增量更新既可以适应用户变化，又可以节约成本。
　　2.2.3结合贝叶斯的协同过滤算法　Bayesian网络技术利用训练集创建相应的模型，但是由于用户和项目的不断增加导致需要定期重建模型，而训练模型的成本高，因此贝叶斯网络适用于用户兴趣变化较慢的环境。孟宪福等根据用户爱好对项目进行分类，实验表明随着评分数据的增加，数据稀疏度在一定程度上增加，但推荐精度却提高，这是因为同一用户的评分数量增加，可以更好地分析用户对特征的爱好，查找到更好的最近邻。赵永梅等采用动态贝叶斯网络，不断学习更新推荐模型，提高了模型的适应性，使得推荐结果更加满足客户的需求。李大学等利用改进的加权朴素贝叶斯方法统计、分析特征属性集与评分之间的关系来预测缺失数据，有效缓解了数据稀疏性问题。
　　2.2.4结合神经网络或免疫网络
　　?BP神经网络。张锋等利用BP神经网络能够有效地处理非完整信息的特点进行预评分以减少候选最近邻数据集的稀疏性，该算法避免了降维法和智能Agent法的缺点，提高了协同过滤推荐系统的推荐质量。张磊等利用两层面的多个BP神经网络协同工作，高层面BP网反向误差传播直至低层面多个人工神经网络进行网络权值修正，借助用户评价等特征前向给出项目推荐，其并行性提高了推荐速度。
　　?人工免疫网络。Acilar等利用aiNet描述数据结构，如空间分布、聚类交互等，能够有效缓解数据集稀疏性并提高数据集的扩展性。苏一丹等利用独特型人工免疫网络的自动浓度调节机制来维持推荐系统中用户邻居的多样性，并利用人工免疫网络的可并行计算特性，设计出并行分布式推荐算法，提高了算法的速度和精度。由于实验处理的数据相对于推荐系统处理的数据而言很小，所以在并行分布式计算环境下机群数量的选择很重要，并不是机器越多越好，要充分考虑硬件成本和通信成本。张建林等利用aiNet自身的克隆变异机制产生隐式评价来降低数据稀疏性，利用aiNet的克隆抑制、网络抑制机制减少数据维度来提高可扩展性，系统的响应时间和算法的收敛性值得进一步研究。
　　2.2.5结合云模型　云模型是李德毅院士提出的一种定性定量转换模型，能够实现定性概念与其数值表示之间的不确定性转换。张光卫等给出一种基于云模型的用户相似度比较方法，充分利用项目的分类信息，避免传统算法把用户的整体打分作为单个向量的弊端。张光卫等借鉴云模型中的云相似度量方法来实现基于知识层面的项目相似性度量，改善了传统基于向量的相似度比较方法必须严格匹配对象属性的不足，而且算法在一定程度上克服了用户评分数据极端稀疏的负面影响。张新香等借助云相似度量方法实现了知识层面的项目相似性的度量，充分发挥了基于项目的协同过滤和云模型的优势。但上述方法都不能有效计算用户对未评分项目的评分，没有很好地解决评分数据的稀疏性问题，从而得到的目标用户最近邻不够准确。针对上述问题，徐德智等利用云模型对项目进行评分预测，缓解了数据稀疏问题。
　　2.2.6结合维数简化Paterek等使用奇异值分解，将用户一评分矩阵分解得到与其最接近的低阶矩阵，提高了可扩展性，并有效缓解了同义性问题。孙小华等采用SVD方法来预测未打分项的预测值得到一个无缺失值的评分矩阵，然后用这个无缺失值的评分矩阵来求取实际未评分项目的预测值，提高了推荐质量。朱敏等将数据在高维向量空间模型中的表示，投影到低维的潜在语义空间中，选择最重要的特征作为原始矩阵的特征值。常富洋等利用SVD将用户基本信息与用户一评分矩阵组合形成的新矩阵分解降维，下一步工作是对用户基本信息的扩充。通过奇异值分解减少项目空间的维数，这种方法显著地提高推荐系统的伸缩能力，但降维会导致信息损失。
　　2.2.7结合对等网
　　钟瑞琼等将推荐系统建立在对等网络平台上，网络中的节点分为超级节点和普通节点，使得搜索只需要在少数的超级对等点之间进行，该结构可以有效地提高网络的可扩展性，大大提升搜索速度，并且可以满足推荐系统的实时性要求。Liu等构造了一种结合用户和项目属性的对等网机制，充分利用项目属性构造布尔矩阵来填充稀疏矩阵的空元素，提高系统的安全性和扩展性。
　　笔者概括了几种主流的协同过滤改进算法，随着电子商务的发展，研究者还会不断提出新的改进思路和方案以解决其在发展过程中产生的新问题。
　　
　　3　推荐效果评估
　　
　　上述各种改进的算法都有其自身的优缺点，到底哪种算法是最优的，目前并没有统一定论，主要是由于不同系统的任务是不一样的，而且评价指标缺乏标准化，因此很难比较。目前普遍认为最重要的指标是准确性，其次还有多样性、覆盖率等指标。
　　
　　3.1准确度
　　绝大多数推荐系统都利用准确度来评价推荐算法的好坏。针对不同的系统，主要有预测准确度、分类准确度、排序准确度等指标。
　　预测准确度衡量的是推荐算法的预测打分与用户实际打分的相似程度，在需要显示具体分值的系统中十分重要。其可以从整体上度量推荐算法的准确度，但在实际中用户只关心自己所感兴趣的产品的预测准确度和好坏产品的区分，预测准确度在这两点上并不能满足用户需求。通常采用平均绝对偏差来度量预测准确度，此外还有平均平方误差和标准平均绝对误差。平均平方误差在求和之前对系统预测打分与用户打分误差进行平方，其对平均平方误差的影响会比平均绝对误差更大。标准平均绝对误差在打分值的区间内作标准化，从而可以在不同的数据集上对算法的效果进行比较。
　　分类准确度是指判断一个产品用户是否喜欢的正确比例。其并不直接评价算法打分的相似程度，只要分类准确就认为是有效的，适合于只有二元选择的系统。分类准确度通常使用准确率、召回率以及F指标来度量，其中准确率是指推荐列表中用户喜欢的产品所占的比例，召回率是指推荐列表中用户喜欢的产品与系统中用户喜欢的所有产品的比率。准确率和召回率的定义依赖于用户喜欢和不喜欢的产品分类。但在用户表明喜好之前，系统无法知道用户是否喜欢某些未知的产品，所以召回率很难计算。为了更加全面地评价推荐算法的好坏，Pazzani提出了F指标同时使用准确率和召回率，应用范围很广。
　　排序准确度用于度量推荐算法产生的列表与用户对产品排序的符合程度，适合于对排列顺序要求严格的系统。用户喜欢的所有产品排序分的平均值可以度量系统的排序准确度。排序分越小，说明系统趋向于把用户喜欢的产品排在前面。平均排序分简单易用，可以用来度量不同算法对同一数据集的排序效果。
　　
　　3.2多样性与覆盖性
　　在实际应用中，衡量推荐效果的指标还有推荐列表的多样性、覆盖率等指标。周涛等提出利用推荐产品的平均海明距离对推荐产品的流行性以及不同推荐列表的多样性进行度量。覆盖率是指可以预测打分的产品占所有产品的比例。在推荐系统中，只有高覆盖率才有可能尽可能多地找到用户感兴趣的产品。
　　
　　4　结论与展望
　　
　　论文介绍了协同过滤推荐算法的主要思想及存在的问题，总结了近几年主流的改进思路，主要是通过缓解数据稀疏性和建立模型两种思路来改进。在数据丰富的情况下，各种推荐算法的推荐效果几乎没有什么差异，但在数据稀疏的情况下却产生很大的差异。其中聚类、维数简化通过缩小最近邻查询空间来缓解数据稀疏性，虽然可以提高系统的可扩展性，但难以保证推荐系统的质量。而基于关联规则、贝叶斯、神经网络等推荐系统在数据稀疏的情况下仍有好的推荐效果，主要是因为在离线建立模型时尽可能模拟真实的系统。但基于模型的推荐系统却难以利用最新数据，需要不断动态更新模型才能保证推荐的有效性。因此，以基于模型的算法为主而其他几类技术为辅构建推荐系统应该成为今后的主流。本文的不足之处是只是定性地对各种算法进行比较，下一步的工作是通过搭建平台，在各个数据集上测试各种算法，并利用各项指标综合评估各种算法。
　　

相关热词搜索：协同 综述 过滤 协同过滤推荐研究综述 协同过滤算法实现 java协同过滤算法