基于可变网格聚类的协同过滤算法

基于可变网格聚类的协同过滤推荐算法

Summary：针对传统的相似度计量方法根据用户评分信息矩阵来计算物品或者用户相似度，需要考虑所有用户反馈的历史信息，提出一种改进的协同过滤推荐算法。首先，将所有物品度的平均值作为一个阈值，选出高密度阈值物品。其次，使用可变网格的聚类方法将有共同兴趣是用户聚为同一类。最后，在类内用推荐算法对用户进行物品推荐。实验结果表明新算法在一定程度上提高了推荐系统的推荐精度和质量。Keys：可变网格；协同过滤；推荐算法；相似性度量1引言

在电子商务迅猛发展的今天，几乎所有的电子商务网站，如京东，淘宝，拼多多，美团等都使用了推荐系统，这些推荐系统都从不同角度为客户提供了个性化推荐信息。虽然最近已经发明了多种推荐技术，但是协同过滤依然是推荐系统中应用最为成功的推荐系统之一。如何快速准确的从海量数据中过滤掉无用信息，筛选出有用的信息推荐给用户成为学者和各大电子商务网站研发的重点。然而随着电子商务数据的指数级的增加，用户-项目评分矩阵愈加稀疏，冷启动，可扩展性开始显现，导致推荐质量下降。

为了解决协同过滤中以上问题，国内外研究学者们提出了很多改进方法和解决方案。文献[1]提出一种基于半监督学习模型的协同过滤推荐算法.半监督学习可以同时利用有标签和无标签数据，根据有标签数据的监督信息来给无标签数据打上伪标签，通过对无标签数据的预测，有效缓解数据的稀疏性，但可伸缩性能不足。文献[2]针对用户项目评分表的稀疏性,使得用户相似度计算误差较大的情况,采用一种基于用户与项目特征兴趣的相似度算法。该算法使用余弦相似度方法,由用户与项目特征兴趣矩阵计算得到改进后的用户相似度，提高了推荐质量。王茜等人[3]提出一种改进的聚类方法,该方法通过应用自构建聚类算法减少了商品的维度,然后直接在聚类上运行推荐算法。该算法提高了推荐算法的效率，但推荐质量有所下降。针对以上存在的问题，本文提出用可变网格的k-means聚类算法与Top-N协同过滤推荐算法相结合的新算法。有效缓解用户评分数据稀疏性导致的冷启动问题，克服传统相似性度量方法的不足，本文通过实验表明，结合新的聚类算法的Top-N协同过滤推荐算法得到的推荐结果准确性上有了进一步提高。基于可变网格的用户聚类算法

用户的特征影响用户的行为，用户的特征包括如：性别，学历，身高，年龄，职业等。例如在某电影推荐网上，大多数男性会选择动作片或战争片，女性大多会选择家庭片或爱情片，小孩子多会选择动漫片等。但是很多推荐网站会忽略用户特征这一推荐维度。本节对含有K个特征的N个用户进行有效聚类。

基于可变网格的聚类算法VGOk-means的具体过程为：首先将含N个用户的数据集D的每一维用快速排序法进行升序排序，再等深划分各维数据，计算相邻区间段的相似度ρ并与相似度阈值v进行比较，如果ρ>v，则相邻区间段进行合并，否则不合并，遍历所有区间段，得到合并后的结果。然后计算合并后网格的密度并将结果记录到集合c中，根据网格密度，计算网格密度阈值，并将大于密度阈值的网格密度结果放入集合d中，对d中的网格用k-means聚类方法进行网格聚类，结果放入集合e中，得到k个最优聚类结果。在基于可变网格的用户聚类算法中，局部地使用了k-means算法，与k-means算法相比，避免了随机选取中心点而产生局部最优解的可能，得到了更准确的聚类结果。基于可变网格聚类的协同过滤推荐算法本文提出一种可变网格K-means聚类算法的Top-N协同过滤推荐算法。算法的基本思想为：首先，把用户之间的相似度视为距离，利用可变网格K-means聚类算法根据样本点之间的距离，将项目矩阵H中的用户聚类成若干个簇类。然后，当需要为某一个目标用户进行推荐时，计算该目标用户与各个聚类中心的距离，从而确定该目标用户所属的簇类。最后，在簇内应用Top-N推荐算法为目标用户进行推荐。基于以上推荐流程的分析，给出基于可变网格的协同过滤推荐算法，具体算法如下所示。RVM-CF(基于可变网格的协同过滤推荐算法)输入：用户特征矩阵{u1，u2，…，un}，商品项目属性矩阵{I1，I2，…，In}，期望的推荐集数N；输出：Top-N项目推荐集Begin1.利用VGOk-means聚类方法对用户特征集进行聚类，得到最优的k个聚类簇;2.在k个聚类簇中计算用户u，v之间的相似度，统计出相似度最大的k个用户作为目标用户的最近邻居集KNNv；3.对项目属性矩阵利用VGOk-means聚类方法聚类，将项目划分为k个簇,4.在k个簇中计算项目i，j之间的相似度psim(i,j)，选出i在项目簇Pk中相似度最大的k个项目组成项目集KNNi；5.计算最近邻居的评分情况，并对簇中目标用户原本未评分项目分别进行预测；6.将所得评分进行降序排列，挑选出前N个高评分项目推荐给目标用户，即生成Top-N项目推荐集。本节提出的基于可变网格的协同过滤推荐算法通过改进相似性计算方法，解决了新用户或新项目存在的冷启动问题；同时改进的算法增强了用户和项目之间的关联关系，缩小了查找空间，能够较为准确的获得真正相似的近邻用户，因此得到的评分预测也更加准确。4实验分析4.1数据集本文的实验数据集采用的是美国明尼苏达大学提供的Movielens公开数据集（）。该数据集中包含943个用户对1682部电影的10万条评分记录，并且每个用户至少对20部电影进行评分，每条数据都按照用户ID、电影ID、评分和时间戳四个变量排列，样本的排列是无序的。在实验过程中将数据的80%作为训练集，20%作为测试集进行检验。实验环境：window10的64位操作系统。采用R语言编程。试验中计算机的硬件配置为：12GB内存，500G硬盘，处理器是Intel(R)Core(TM)i5。4.2评估标准本文采用的评估标准是用平均绝对误差和均方误差来评价推荐质量。用召回率作为评价精度的指标。对目标用户ui推荐N个物品，记为N(i)。在实验中取N为10。令目标用户ui在测试集上喜欢的项目集合为T(i)，召回率的计算方法如下：4.3实验结果与分析本文中分别将所有用户聚成2、3、4、5、6个簇，并且可变网格聚类迭代步骤分别设为5、10、…、45步。表4-1是改进的算法在聚类数分别为2、3、4、5、6时得到的推荐召回率。由表可以看出，当用户类簇为2时，迭代次数为10左右时，推荐效果是最佳的。召回率达到了0.11598.比协同过滤推荐算法提升了2%。很显然，将用户聚为2或3个簇时，改进的RVM-CF算法比Top-N推荐算法精度更高。表4-1RVM-CF算法在各聚类情况下推荐结果的召回率Step=5Step=10Step=15Step=20Step=25Step=30Step=35Step=40Step=45CF0.11361K=20.115020.115980.115970.115970.115950.115960.115960.115960.11596K=30.114810.115470.115360.114870.115000.114940.114840.114740.11474K=40.112350.113860.113680.113730.113720.113630.113650.113640.11363K=50.112420.113460.113320.113210.113250.113270.113070.113370.11297K=60.111960.112850.112050.111820.111560.111780.111480.111380.111885总结本文利用可变网格的协同过滤推荐算法分别对用户、项目进行聚类分析，针对用户数据采用基于用户相似性的推荐算法进行最终预测，提高推荐的动态性和准确性。本文提出的算法在召回率上比传统的协同过滤推荐算法提升了2%.证明了提出算法的正确性，提高了推荐质量。Reference：[1]崔莹莹,陈卓,王红霞.基于半监督学习模型的协同过滤推荐算法[J].