基于高维稀疏数据聚类的协同过滤推荐算法

基于高维稀疏数据聚类的协同过滤推荐算法姚忠1,魏佳，吴跃（北京航空航天大学经济管理学院信息管理与信息系统系，北京100083）摘要针对协同过滤推荐算法面临数据高维稀疏特征时推荐效果较差的缺点，在现有高维稀疏数据聚类研究的基础上，利用评分数据稀疏差异度和项目类别构造集合差异度度量公式，用以在用户-项目评分矩阵上进行项目聚类。在此基础上进行项目相似性计算和最近邻居查询，然后对用户未评分的项目进行评分预测，进而产生推荐。实验证明本文提出的基于稀疏差异度和项目类别的项目聚类算法及在此基础上的协同过滤推荐结果优于传统的K-means聚类算法基础上的推荐效果。同全项目集协同过滤推荐相比较，在效率和推荐精度上也表现出一定的优越性。关键词推荐系统，协同过滤，项目聚类，项目类别评分,IBCRA中图分类号TP3111引言Internet推动了电子商务的飞速发展，网络作为一个全新的销售渠道、采购渠道和客户渠道，越来越受到企业和消费者的重视。实施电子商务系统对企业的服务提出了诸多新要求，包括商品质量的保证、送货及时性、商品选购舒适度、退货便利性等，其中最为突出的一个问题就是商品选购的个性化推荐[1]。推荐系统（RecommenderSystem）是解决信息过载的有效手段，也是电子商务服务提供商提供个性化服务重要的信息工具。电子商务推荐系统是提供“一对一”个性化服务的一种重要的信息技术，它利用电子商务网站向客户提供商品信息和建议，帮助用户决定应该购买什么产品，模拟销售人员帮助客户完成购买过程[2]。推荐系统和个性化推荐技术研究在国内外逐渐成为研究热点，并被广泛应用。Amazon、CDNOW、eBay、Levis、Moviefinder、Reel等众多国外知名电子商务网站，已经将推荐系统集成到运营系统中[3]。国内B2C网站虽然在个性化和自动化推荐方面存在差距[4]，但随着中国电子商务的蓬勃发展，推荐系统的理论研究正逐步深入，国内网站的推荐策略较原先的分类浏览和基于内容的检索等简单方式更加智能化，推荐技术逐步应用到网站中来。1.1相关文献推荐系统包括个性化推荐系统和非个性化推荐系统[31]。非个性化推荐系统向所有用户提供具有相同内容的推荐，如电子商务站点的畅销排行。个性化推荐系统则区分不同用户或用户群，根据他们的偏好定制推荐[7]。非个性化推荐系统原理简单，易于操作，但没有考虑到用户需求的差异性，推荐质量较差；个性化推荐系统算法和实现相对复杂，但推荐质量高。当前电子商务推荐系统的研究基本上集中在个性化电子商务推荐系统的研究领域。个性化电子商务推荐系统研究依赖用户在评分体系架构中的显式评分，并以此预测用户未评分项目的评分。其中，个性化推荐中使用的推荐算法是通过用户对项目的评分以及附加信息，对尚未评分项目进行评分预测，将评分最高的项目或项目组推荐给用户。推荐系统的1通信作者：姚忠，北航经管学院，副教授，博士，Email:[e-mail].个性化推荐服务，提高了客户对电子商务网站的忠诚度，为企业赢得了更多的发展机会[8]。用户偏好信息的获取是推荐算法的前提。用户信息的获取主要是通过用户对给定信息的评价，主要包括显式评价和隐式评价两类[9]。显示评价基于用户有意识地表达对项目的认可程度，通常使用特定区间的整数值来表达用户的偏好程度，用户数据库中的信息随着用户不断使用而随时更新；隐式评价不需要用户主动参与，推荐系统通过Agent、Web数据挖掘等技术自动跟踪并分析用户浏览记录、购物记录等行为来获取信息。当前，电子商务推荐系统的研究内容和研究方向主要包括推荐方法研究、实时性研究、推荐质量研究、多种数据多种方法的集成、数据挖掘在推荐系统中的应用、用户隐私保护研究等[10]。其中，推荐算法是电子商务推荐系统的核心，推荐系统其他研究内容绝大多数也是以推荐算法为研究出发点。在推荐算法中，主要的研究方向包括协同过滤推荐、基于内容的推荐、聚类技术、Bayesian网络技术、关联规则技术、基于图的Horting图技术等[10]。本文研究高维稀疏数据情况下的协同过滤推荐算法，因此下面主要介绍与此相关的研究。协同过滤推荐算法是目前最受欢迎的推荐技术[4]。Tapestry是最早提出的协同过滤推荐系统，目标用户需要明确指出与自己行为比较类似的其它用户[2][12]。协同过滤推荐算法在用户对项目做出评价的基础上，通过用户—项目评价矩阵发现用户的共同兴趣模式，预测用户之间的相似度，从而为目标用户做出个性化的推荐。协同过滤推荐主要有两种方法：基于用户的协同过滤（User-BasedCollaborativeFiltering）和基于项目的协同过滤（Item-BasedCollaborativeFiltering）。也有研究者提出将两者相结合的方法。协同过滤推荐算法冷启动问题研究，新项目往往是市场上最流行的商品，但执行协同过滤时却不可能将其作为推荐项目，因为没有人对它进行评比或购买，系统无法提供正确的推荐信息。Schein等[19]通过贝叶斯分类法来解决新项目推荐问题。欧立奇等[22]利用生成树算法划分项目矩阵并计算项目间相似度，根据用户对已有项目的评分和项目间相似性预测用户对新项目的评分。随着推荐技术的深入发展，大量文献对协同过滤推荐算法进行了改进。改进的协同过滤推荐算法主要研究内容是对相似性算法的改进。采用传统方法计算不同项目之间的相似性时，由于受到用户评分数据稀疏性的影响，难以保证推荐结果的准确性；由于用户对于所有评分为0的项目的喜好程度不可能完全相同，余弦相似性不能有效地在没有经过处理的用户—项目矩阵的基础上度量项目之间的相似性；传统的计算项目之间相似性的时候多数忽略了项目之间本身存在的固有关系—项目类别关系，即同属于某一个类别的项目之间应该有更高的相似性[11]。彭玉等[23]提出了一种基于项目的协同过滤推荐算法，通过计算项目的评分相似性和属性相似性，利用双向蕴涵谓词计算项目的相似性。邢春晓等[24]在相似性计算公式中引入了缩放系数α，以削弱被访问过很多次的资源在相似度计算中的影响。为提高推荐效果，姚忠等[10]在相似性公式中引入调和参数α，通过调和参数与项目类别数据的乘积来调节项目间的相似性，。集成语境信息的协同过滤推荐算法。传统的推荐技术都是基于用户×项目的二维空间，仅仅是建立在用户对项目的评价信息上来对未评分项目的评分预测从而进行个性化推荐，没有考虑另外的语境信息，而这些语境信息在一些应用中可能很重要。所谓语境信息就是指对人的行为或者事件的发展产生影响的上下文信息或者场景信息，如时间、地点等信息[18]。用户消费的语境信息在很大程度上会影响用户的偏好以及最终的购物决策。多维技术是从数据挖掘中发展起来的一种推荐技术，它扩展了传统的二维矩阵，引入了语境信息。与传统的二维推荐模型需要用全部数据进行预测不同，多维推荐模型在进行评分预测时只会用到与用户指定的语境信息相关的那些数据[18]。集成语境信息的技术通过建立集成语境信息的多维评分模型，通过选择最优的语境段用基于降维的方法将多维的模型降低到传统的两维推荐模型上，并在此基础上用协同过滤推荐算法进行评分的预测以及项目的推荐。数据稀疏性是造成推荐质量低的主要原因之一。为了提高推荐算法的推荐质量，许多研究人员都试图降低数据稀疏性带来的问题，从不同角度对用户和产品信息进行分析、处理、降低数据的稀疏程度。基于项目的协同过滤推荐、降维法、智能Agent方法可以在一定程度上缓解数据稀疏性问题。张峰，常会友[20]使用BP神经网络缓解协同过滤推荐算法的稀疏性问题，根据用户评分向量交集大小选择候选最近邻居集，采用BP神经网络预测用户对项目的评分。Huang等[21]将奇异值分解应用到协同过滤推荐算法，通过奇异值分解算法得到低维正交矩阵，较好地解决了数据稀疏性问题，但是推荐的准确性会有一定的下降。在采用神经网络模型进行聚类处理的总思路下，Aggarwal等[28]通过寻找基于对象属性信息的项目类间隐性联系化解数据稀疏性对高维数据聚类的影响。孙多等[30]阐述了单值分解、聚类等数据稀疏性解决技术。此外，应用聚类算法是解决用户—项目评分矩阵稀疏性的比较有效的方法。由于聚类算法能可用于发现数据库中未知的对象类，对象类的划分是考察个体或数据对象间的相似性，将满足相似性条件的个体或数据对象划分为一组，不满足相似性条件的个体或数据对象划分在不同的组[20]。因此，运用聚类算法将具有相似兴趣爱好的用户分配到相同的聚类中；聚类产生后，根据聚类中其它用户对商品的评价预测目标用户对该商品的评价。该方法存在的最大缺陷是如果目标用户处在聚类的边缘，则对该用户的推荐精度比较低[15]。为解决这一缺陷，O’Connor等人提出了对项目进行聚类，然后再对应聚类中搜索目标项目的最近邻居[16]。聚类技术经常同协同过滤推荐算法组合在一起，即基于聚类的协同过滤推荐算法。针对高维聚类协同过滤推荐算法在整个项目空间内搜索目标对象的最近邻居，将产生巨大的计算量，严重影响算法的效率。通过聚类技术，将搜索目标对象最近邻居的范围缩小到与目标对象相似性程度最高的几个聚类，可以有效减少计算量，提高实时响应能力。邓爱林等[8]提出了一种基于项目聚类的协同过滤推荐算法，根据用户对项目评分的相似性进行扩展，生成相应的聚类中心，在此基础上计算目标项目与聚类中心的相似性。张海燕等[25]提出了一种通过模糊聚类的方法将项目属性特征的相似性与基于项目的协同过滤推荐技术相结合的推荐算法，在对项目进行模糊聚类后得到项目在属性特征上的相似关系群。何光辉等[12]提出了一种改进的聚类邻居协同过滤推荐算法，利用聚类邻居方法构造邻居关系。高凤荣等[26]采用聚类方法对稀疏矩阵进行划分，通过对资源评分矩阵的划分缩小近邻搜索范围和需要预测的资源数目，减少数据稀疏性。孙多等[29]将Web日志挖掘技术引入到协同过滤推荐研究中，通过构建兴趣度对用户进行聚类。以上文献中没有考虑用户-项目评分矩阵中的稀疏差异度，而这一差异度对提高聚类效果有明显的作用[5]。本文针对推荐系统数据集高维稀疏的特征，将评分数据的稀疏差异度引入到项目聚类算法中，然后将稀疏差异度和项目类别构造集合差异度相结合，对用户—项目评分矩阵进行项目聚类，然后，在聚类后的集合内进行项目相似性计算和最近邻居查询，对用户未评分的项目进行评分预测，进而产生推荐。全文共分五小节。第一节简要阐述了电子商务推荐系统、推荐算法、聚类算法相关领域的研究现状，第二节具体提出了基于稀疏差异度和项目类别的项目聚类算法（IBCRA算法）。在分析了算法的基本思想，项目类别、稀疏差异度等重要概念和构造方法后，详细阐述了基于稀疏差异度和项目类别的项目聚类算法的步骤。然后，在基于稀疏差异度和项目类别的聚类算法的基础上，利用该算法进行项目聚类，在目标项目集中进行项目相似性计算和最近邻居查询，通过对目标用户未知项目的评分预测生成项目推荐列表。第三节设计了本文提出的基于项目聚类的协同过滤推荐算法的实验仿真和测试。实验使用MovieLens数据集，以平均绝对误差（MAE）为评价指标，首先使用基于稀疏差异度和项目类别的聚类算法对训练集上进行项目聚类，并在此基础上生成最近邻居列表，在测试集上验证算法的效率。第四节对当前商用的聚类算法进行了实验比较分析。结论部分总结了本文的研究成果、尚存在的不足和今后的研究方向。2算法设计基于项目聚类的协同过滤推荐算法主要分为四个过程：项目聚类算法；项目相似性计算；最近邻居查询；评分预测过程算法。下面按照这四个过程介绍。首先介绍项目聚类算法原理与流程，然后阐述项目相似性计算、最近邻居查询和评分预测三个主要环节。项目相似性计算通过相似性计算公式，在用户—项目评分数据集R上计算目标项目与邻居项目的相似性sim(i,j)。最近邻居查询通过相似性计算结果，搜索与目标项目相似程度最高的若干个邻居项目，构成目标项目的最近邻居项目集合Mj。最近邻居项目集合Mj的长度，即最近邻居项目集合元素个数，是由最近邻居查询个数决定的。最近邻居查询个数Knear是算法最重要的输入