正在进行安全检测...
发布时间：2024-01-14 14:07:05 来源：文档文库
小
中
大
字号：
算法分析数字技术与应用基于SVD与层次聚类的协同过滤推荐算法实现*徐泽兵王忠(四川大学电气信息学院,四川成都610065摘要:在如今这个信息爆炸的时代,我们要面对“信息过载”这一难题;以个性化推荐技术为核心的推荐系统有效的解决这一问题,其中协同过滤算法是目前应用最广泛也是最成熟的个性化推荐技术。基于此,本文提出一种基于SVD与层次聚类中的BIRCH算法来实现协同过滤算法。该算法在MovieLens数据集上的实验数据表明该算法有效的提高了推荐的质量。关键词:个性化推荐；SVD；BIRCH算法中图分类号:TP312文献标识码:A文章编号:1007-9416(201801-0130-02最近几年,协同过滤算法[1]是比较成功并具有代表性的推荐算法,目前协同过滤算法大致分为两类:一是基于内存的协同过滤算法;二是基于模型的协同过滤算法。本文针对数据的稀疏性、可扩展性等问题提出了基于奇异值分解与BIRCH层次聚类算法[2]的协同过滤算法。并且使用物理学上的能量守恒定律来确定SVD在降维时保存尽可能多的信息。使用BIRCH聚类算法缩小查询最近邻时的范围。实验表明,本文算法能够提高推荐质量。其中N(u代表用户u的最近邻集合。2基于SVD与BIRCH层次聚类的协同过滤算法在本节中将对本文提出的改进算法进行详细叙述,本算法的主要思想为:首先,通过奇异值分解对原始的用户评分矩阵进行预处理:构造出用户相关矩阵;其次,利用BIRCH算法进行归类,形成K个用户簇;之后根据目标用户确定目标簇并确定最近邻;最后实现top-N推荐。以下将详细叙述该算法的过程:2.1构造用户相关矩阵SVD分解是属于矩阵分解技术,其本质是将一个原始矩阵分解为三个矩阵相乘的形式,如式3-1所示:Rmn=UmmmnVnn(3-11传统的基于用户的协同过滤算法在传统的基于用户的协同过滤算法中,我们完成推荐的过程一般分为下面几个步骤:第一:构建评分矩阵:第二:计算相似度,确定K个最近邻;第三:完成预测评分,实现推荐。因此我们完成的推荐的第一步就是对数据进行初始化,构建评分矩阵。在利用SVD进行降维时,所选择的降维维数k很重要,在本文中我们将保存原始矩阵的多少能量定义为能量阈值s。我们确定了s的值之后,就可以反向确定维度值k。此能量阈值的值为对角矩阵的前k个奇异值的能量除以全部奇异值的能量的结果。确定k值之后,我们就可以将对角矩阵只保留前k个奇异值形成新的对角矩阵k,从Umm中取前k列变成Umk,从Vnn中取前k行变成Vkn,其中k远远小于m和n的值,这样就达到了降维的目的。经过上面的一系列矩阵分解降维处理之后,我们得到了用户特征矩阵,后面的分析都是基于此矩阵。1.1数据初始化将用户集U(u1,u2,u3,...,um及评分项目集合V(v1,v2,v3,...,vn构造出一个评分矩阵Rmn,其中u1,u2,u3,...,um代表有m个用户,v1,v2,v3,...,vn代表有n个项目,Ri,j表示用户ui对项目vj的评分值。1.2获取最近邻集合基于用户的协同过滤算法完成推荐功能的第二步是为目标用户找到最近邻的集合,最近邻集合的确定是通过计算相似度来确认的,皮尔森相关系数在计算相似度时更加的准确,设sim(u,v来表示用户u与v之间的相似度,公式如下:i2.2使用BIRCH算法对用户矩阵进行分类在经过上一节的SVD处理之后我们得到用户特征矩阵,为了更加高效的获取到目标用户的最近邻,使用BIRCH算法对该矩阵进行聚类。主要思想是:利用树结构帮助我们进行快速的聚类,一般把其称作聚类特征树(CFTree。该树的任一节点都是由若干个聚类特征(CF组成的。流程如下为:(1在内存中构建CF树;(2以CF树叶元项对应的子簇为基础,实现数据点的聚类;(rIU,Vu,iru(rv,irvIU,Vsim(u,v=(ru,iru2(rv,irv2(2-1iiIU,V其中ru,i代表用户u对项目i的评分,ru代表用户u对其所有评过分的项目的评分平均值。1.3评分预测当我们求出目标用户的前N个相似的用户之后,那么就可以对目标用户未评分的项目进行预测评分了,公式2-2如下:2.3改进算法的描述综合第二节的传统协同过滤算法以及本节前面对SVD以及BIRCH算法的描述,我们可以对本文改进算法进行简要描述:输入:用户-项目评分矩阵,目标用户;输出:对目标用户进行Top-N推荐。ru,i=vN(usim(u,v(rr|sim(u,v|(2-2v,ivvN(u收稿日期:2018-01-10*基金项目:四川省科技攻关项目(项目编号:2015FZ0061。作者简介:徐泽兵(1992—,男,汉族,安徽六安人,硕士研究生,研究方向:算法研究。130
数字技术与应用算法分析图1各算法的MAE值与近邻个数的关系(1对用户-项目矩阵进行SVD降维处理,根据公式得到用户特征矩阵;(2对用户特征矩阵进行BIRCH聚类,然后确定和目标用户相似的簇;(3根据皮尔森相关系数确定最近邻集合;(4对目标用户未评分的项目进行评分;(5根据预测评分结果实现Top-N推荐。在对用户-项目矩阵进行奇异值分解时,选择适当的降维维数很重要,过低会损失过多的信息量,过高的话失去降维的意义。通过实验当选择k为17时,MAE的值最低,推荐的性能最好。为了验证改进算法的性能,我们将该算法与knn算法以及基于SVD的推荐算法进行比较,在取不同的近邻个数的情况下各算法的推荐性能:由图1所示,当我们的近邻个数达到一定数目后,我们的改进算法推荐效果更加高效。3实验结果及分析本文采用的数据实验集为MovieLens数据集。该数据集中的信息包含了一共943个用户对于1682部电影的十万条评分。评分值是1至5的整数,数字越高代表评分越高。4结语本文提出的基于SVD与BIRCH层次聚类的协同过滤算法的优势有:第一,SVD对原始矩阵进行降维处理,有效的解决了数据稀疏 