多聚类混合的加权协同过滤算法研究_谢虹铭.pdf

2023.7电脑编程技巧与维护1概述在高速发展的互联网大数据时代，信息超载问题（Information Overload）日益显现，过量的信息使得用户获取有效信息的难度增大。信息的消费者在信息超载的时代，面临庞大的数据量时，难以定位到有效的信息。信息的生产者在面临庞大的数据量时，往往难以快速地挖掘到用户的兴趣偏好和行为习惯，进而无法精准地分析出用户的需求，无法使自己的产品脱颖而出，这极大地降低了服务的质量与销售量。针对上述问题，推荐算法应运而生，推荐算法之一的协同过滤算法则是目前推荐算法中研究受众较多、较成熟的算法。但随着近些年来用户和物品资源的急剧增加，不可避免地导致传统的协同过滤算法推荐质量降低且系统开销增大。针对随之而来的问题，各位学者在协同过滤算法基础上进行改进。Leban等1提出结合K-Means聚类的协同过滤算法，用于对传统的协同过滤算法数据集进行先聚类后计算，对推荐质量和推荐性能得以改善；赵伟等2提出了一种新的改进的K-Means聚类协同过滤算法，在原有算法的基础上较好地优化了用户聚类问题；施天虎等3提出一种基于改进K-Means和优化评分的用户协同过滤算法；李艳娟等4提出了基于蜂群K-Means聚类模型的协同过滤推荐算法，根据用户属性信息，使用改进蜂群K-Means算法对用户聚类，在聚类簇中构建用户项目评分矩阵计算相似度，有效地提升了推荐质量和推荐效率。综合上述学者研究思路，结合Canopy聚类算法和K-Means聚类算法的特性，提出Canopy+K-Means混合聚类模型。（1）使用Slope One算法弥补评分矩阵中的缺失值，解决评分矩阵的稀疏性问题；其次，Canopy算法进行粗聚，类获得簇心作为K-Means算法的初始K值和聚类中心，在此基础上使用K-Means算法进行细聚类；再次，考虑用户兴趣偏好随时间发生变化，运用时间加权相似度计算方法进行相似矩阵计算；最后，采用MovieLens-1M数据集测试，实验数据显示改进后的算法推荐质量得以提升。2理论知识2.1协同过滤算法协同过滤算法是一种基于用户历史行为和偏好，预测用户可能感兴趣的商品或服务的推荐算法。协同过滤算法主要基于两个思想是用户的喜好更偏向于他们曾经喜欢或购买的物品，以及偏好相似的用户倾向于喜欢相似的物品。2.2K-Means 算法K-Means算法是一种以欧式距离（Euclidean Dis-tance）作为衡量数据对象间相似度指标的无监督的学习算法。如公式（1）所示：（1）其中，X、Y为两个向量样本；n为特征数。K-Means算法通过预先指定初始聚类个数与簇心，不断更新簇心的位置，划分新簇并降低各簇间的误差平方和，如公式（2）所示：（2）其中，C为簇心。如果x属于Ci这个簇，则计算两者的欧式距离，将所有样本点到其中心点距离算出来并加总，就是K-Means的目标函数。实现同一个簇中的样本差异小，就是最小化SSE。当SSE不再变化或目标多聚类混合的加权协同过滤算法研究谢虹铭，朱参世，朱军，侯礼灏（西京学院计算机学院，西安710000）摘要：协同过滤算法可根据用户的偏好，预测其感兴趣的项目，这项技术是目前商业领域中应用较为广泛且成功的。过去，使用协同过滤算法会因其数据的稀疏性及使用 K-Means 算法聚类时需要预先确定聚类个数等问题影响协同过滤算法的准确性。针对上述问题，提出了一种多聚类融合的协同过滤推荐算法。首先，构建用户-项目评分矩阵；其次，根据用户兴趣、偏好矩阵查找待估值项所对应的近邻用户，随后使用 Slope One 算法在对每一个簇内的稀疏矩阵进行填充，从而缓解数据稀疏性问题；再次，使用 Canopy 聚类算法进行粗聚类，将计算出的每个中心点作为 K-Means 算法的初始聚类点并进行K-Means 细聚类；最后，优化后的协同过滤算法最终被用来预测每个簇中填充后的评分矩阵，并采用带时间加权的相似度公式。最终实验数据显示，优化后能够有效提升算法的效率与推荐质量。关键词：协同过滤；Canopy 聚类；K-Means 聚类；Slope One 算法26DOI:10.16184/prg.2023.07.0282023.7电脑编程技巧与维护函数收敛时，聚类结束，得到最终结果。2.3Canopy 算法Canopy算法与传统聚类算法不同，它并不需要事先指定簇的个数，因此可以使用Canopy算法对数据集先进行“粗”聚类获得k值。Canopy算法作为一种快速聚类的算法，虽然无法得出精准的簇结果，但是能计算出最优的簇数5。Canopy算法具体过程如下：（1）将数据集向量化，选择两个距离参数为T1和T2，使T1的值大于T2，如图1所示，实线圆的半径值是T1，虚线圆的半径值是T2，两个距离参数的值可通过交叉校验确定。（2）在向量中任取一点O，快速计算O与所有Canopy间的距离（如果初始状态不存在Canopy，则把点O作为一个Canopy），若点O同一个Canopy的距离小于T1，则将点O加入到这个Canopy。（3）若点O与某个Canopy的距离小于T2，则需要把点O从向量中删除，此时认为点O与这个Canopy已经足够接近，它将不再作为其他Canopy的中心。（4）重复步骤（2）、（3），直到向量集合为空为止。Canopy算法示意图如图1所示：2.4SlopeOne 算法Slope One是一种基于评分的协同过滤算法6，具有简单、易懂、易于维护和执行、及时更新性等特点，可以有效地改善矩阵的稀疏性。且算法易于实现、计算速度快、可扩展性好。Slope One算法流程如下：输入：训练数据集转换为用户物品评分矩阵。（1）设定推荐商品数量的阈值为k。（2）计算物品之间的评分差的均值dev（ab），此为物品间的评分偏差，如公式（3）所示：（3）其中，rua、rub是用户u对物品a与物品b的评分；uP（a,b）为所有对物品a、b评过分的用户；N（a,b）为同时对物品a、b评分的用户数量。根据物品间的评分偏差和用户的历史评分，预测用户对未评分的物品的评分，如公式（4）所示：（4）其中，iQu为所有用户u评过分的物品。（3）将预测的评分填充进矩阵，解决推荐系统中矩阵稀疏性的问题，填充完整个矩阵之后，采用协同过滤算法来进一步提高推荐系统的效果和准确度。2.5基于时间加权的相似度传统的相似度计算方法忽略了时间对偏好的影响，而时间加权相似度计算方法考虑到用户喜好的时效性，即用户对较近期购买或关注的物品兴趣更大，使该计算方式能够提高推荐的精准度7。使用时间加权相似度的基本思路是设离当前时间越近的评分数据权重越大，离当前时间越远的权重越小。时间加权的相似度计算公式如公式（5）所示：（5）其中，wi为该时间点处的权重。根据用户对近期评价的物品兴趣度较大，对早期评价的物品兴趣度较小的规律，赋予权值时距离当今时间较近的时间点权重大，较远的时间点权重小。常见的时间加权方式有指数衰减、高斯分布等形式。在此使用指数衰减，其权重形式如公式（6）所示：wi=e-（ti-tn)（6）其中，为衰减系数；ti为第i个时间点的时间戳；tn为最后一个时间点的时间戳。当越小时，时间跨度较大的时间点所对应的权重越趋近于0，从而减小其对总相似度的贡献。si为第i个时间点处的相似度，一般使用皮尔逊系数表示，皮尔逊系数计算公式如公式（7）所示：（7）其中，Nu,v为用户u,v共同参与评分的集合；ru,i和rv,i为用户对同一个项目i的评分。ru和rv是用户对整体项目评分的均值。3Canopy+K-Means 的基于时间加权相似度的协同过滤算法为了优化传统推荐算法质量和效率不足的情况，采用Canopy+K-Means混合聚类并使用基于时间加权相似图1Canopy算法示意图小于T2，为当前簇的成员，不可能成为其他簇的成员大于T1不是当前簇成员当前簇质心T2T1大于T2小于T1，为当前簇的 成 员，也 可 成 为 其 他 簇的成员272023.7电脑编程技巧与维护度的协同过滤算法，设计步骤如下：（1）通过Slope One算法填充评分矩阵的缺失值，解决评分矩阵的稀疏性问题。（2）使用Canopy算法对原始数据集进行了粗聚类，从而快速获得聚类后的Canopy聚类点，再将Canopy聚类点作为K-Means聚类的首次聚类簇心，使得K-Means算法获取更精准的相似用户簇。（3）对于每个用户，使用基于时间加权的相似度公式，计算其与簇内其他用户的相似性，并取最相似的N个用户作为该用户的最近邻。（4）根据最近邻进行评分预测，使用评分预测公式（8）进行预测并呈现最终推荐。（8）4实验设计与结果分析4.1数据集实验数据集来源于MoivieLens-1M数据集，该数据集由用户对电影的评分和关于电影的元数据（例如，标题、类型和演员等）组成。在推荐系统、数据挖掘和机器学习等领域的研究中被广泛使用。4.2评估指标传统推荐算法在衡量推荐性能时，常使用MAE平均绝对误差与RMSE均方根误差算法作为评价标准，或评价指标。这两种算法的计算公式分别如公式（9）和公式（10）所示：（9）（10）4.3实验结果及分析使用以下几种协同过滤算法与该算法进行对比，基于用户的协同过滤算法（ICF）；使用K-Means聚类的基于用户的协同过滤算法（KICF）；使用SlopeOne填充稀疏矩阵后的K-Means_Item_CF（SKICF），以及在此使用的算法。使用MoiveLens-1M数据集在这4种方法上进行训练，通过比较4种算法在训练下得到不同的MAE、RMSE值来评估各算法推荐性能的优略，实验结果对比如表1所示。表1中展现出不同算法在不同最近邻数下的MAE值与RMSE值的结果对比，从中可以看出，此算法与叠加层层优化技术的传统的基于物品的协同过滤算法进行比较，不仅此算法整体上预测效果较好，并且一步步提升，每次增加了技术优化的相关算法也会比对应优化前的原始算法性能有所提升。由此可充分证明此算法具有良好的推荐质量和推荐效率。5结语旨在对传统协同过滤算法推荐过程中的用户聚类与相似度计算公式进行优化，以达到提高推荐质量及推荐精度的目的。通过文中算法混合聚类及时间加权优化相似度的方法，与传统协同过滤算法进行结合，成功地在实验中验证了文中算法的可行性，使得该算法在推荐效率上得到提高。在将来的研究中，将为优化推荐算法提供更优的策略。参考文献1LEBAN G,MRAMOR M,BRATKO I,et al.Simpleand effective visual models for gene expression cancerdiagnostics C/SIGKDD,Proceeding of the eleventhACM SIGKDD international conference on knowledgediscovery in data mining-KDD 05.2005.2赵伟,林楠,韩英,等.一种改进的K-means聚类的协同过滤算法J.安徽大学学报（自然科学版）,2016,40(2):32-36.3施天虎,徐洪珍.基于改进K-means和优化评分的协同过滤推荐算法J.江苏科技大学学报（自然科学版）,2021,35(6):72-77.4李艳娟,牛梦婷,李林辉.基于蜂群K-means聚类模型的协同过滤推荐算法J.计算机工程与科学,2019,41(6):1101-1109.5王林,贾钧琛.基于改进Canopy-K-means算法的并行化研究J.计算机测量与控制,2021,29(2):176-179.6王家华,谈国新,张文元,等.融合改进加权SlopeOne的协同过滤算法J.微电子学与计算机,2020,37(4):37-42.7刘乔,刘彬.基于时间加权的协同过滤推荐算法的改 进J.计 算 机 工 程 与 设 计,2016,37(7):1827-1830.ICFKICFSKICF此算法MAE/RMSEMAE/RMSEMAE/RMSEMAE/RMSEKNN=100.807/1.1120.832/1.0440.790/1.0170.792/1.021KNN=150