QPSO与FCM融合的协同过滤推荐算法

来源:用户上传      作者:

　　摘要： 针对以往的推荐算法中存在的“冷启动”和“数据稀疏性”问题提出了一种QPSO（Quantum behaved Particle Swarm Optimization）聚类与协同过滤相结合的推荐算法。该算法首先用QPSO 聚类产生中心聚点来解决模糊C均值聚类中初始聚类中心选择问题，并引入罚函数的思想来确立目标函数，再联合项目隶属度矩阵和稀疏的用户项目评分矩阵构造出用户项目簇矩阵。最后使用协同过滤算法对用户项目簇矩阵进行处理，得到目标用户的推荐项目集合。使用平均绝对误差和综合评价指标F对该算法进行验证，实验结果表明，该算法不仅解决了传统FCM（Fuzzy c-means）算法初始中心选择问题，还解决了协同过滤推荐中存在的数据稀疏和冷启动问题，推荐精度也得到了极大提高。
　　关键词： 量子粒子群算法;模糊C均值聚类;协同过滤;视频推荐
　　中图分类号：TP3        文献标识码：A
　　文章编号：1009-3044（2019）18-0284-04
　　Abstract： Aiming at the "cold start" and "data sparsity" problems in the previous recommendation algorithms， a recommendation algorithm combining QPSO clustering and collaborative filtering is proposed. Firstly， the algorithm uses QPSO clustering to generate the central clustering point to solve the initial clustering center selection problem in fuzzy C-means clustering， And introduce the idea of penalty function to establish the objective function .Then joint project membership matrix and the sparse user project scoring matrix construct the user project cluster matrix. Finally， the collaborative clustering algorithm is used to process the user project cluster matrix to obtain the recommended project set of the target user. The algorithm is validated by MAE（mean absolute error）and comprehensive evaluation index F. The experimental results show that the algorithm not only solves the initial center selection problem of traditional FCM（Fuzzy c-means）algorithm， but also solves the problem of data sparseness and cold start in collaborative filtering recommendation. The recommendation accuracy is also greatly improved.
　　Key words： QPSO algorithm; FCM; Collaborative filtering; recommended algorithm
　　1 引言
　　互聯网中充斥着各种各样的信息，用户信息在获取信息的过程中，往往存在以下几个问题：用户在潜意识中更倾向于被动接受而不是主动挖掘新的信息;用户对于自己想要主动获取的信息并不能完整的进行描述;总之用户在庞大的信息量下能发挥的主观能动性是非常有限的，这时就需要借助推荐算法。推荐算法的出现一方面可以提高用户体验，另一方面也为商家对于产品和信息的推广助力。
　　目前的推荐算法主要分为三类：基于人口的统计学推荐主要利用已有的用户统计信息粗略的进行推荐;基于内容的推荐算法根据用户之前的浏览记录，推荐元数据中含有与之前记录中具有相似标签的项目，不存在冷启动和数据稀疏性问题，但是需要对文件进行建模和特征提取并且只关注到了项目之间的相似性而忽略了用户行为。协同过滤基本原理就是“物以类聚”即把相似的内容推荐给同一用户;“人以群分”给具有相似爱好的用户推荐同一类内容，能够从大数据中挖掘用户的潜在喜好。
　　针对数据稀疏性问题，主要解决方案分为三类，缺失值填充法[1]，对未评分项目设定缺省值来填充用户项目矩阵，填充的数据容易忽略特殊性;降维法[2]，通过降低用户-项目矩阵的维度，因为需要摒弃一些用户和项目数据，推荐精准率受损;聚类法;聚类技术通过对项目或用户进行聚类来缩小最近邻居的查询范围。目前，基于聚类的协同过滤，Sarwar等人[3][4]以目标用户所在的类簇作为其最近邻居集 ，然后在邻居集上进行推荐。Rashid等人[5]首先通过聚类技术生成目标用户最相似的代理用户，然后利用代理用户寻找目标用户的最近邻居。邓爱林等人[6]以目标项目最相似性的若干个聚类中心寻找目标项目的最近邻居集。张海燕等人[7]引入了项目属性特征信息进行模糊聚类。葛林涛等人[8]依据不同的聚类有效性函数确定合理的聚类区间，并在此区间寻找最佳聚类数。
　　针对以往FCM算法存在对初始值敏感且容易陷入局部最优的缺点，引入了量子粒子群算法，结合量子粒子群算法中罚函数思想把这两个算法的迭代寻优过程转化为解决QPSO算法用于解决非线性约束优化的问题，利用产生的目标函数得到项目聚类结果，将得到的聚类结果作为被推荐用户的相似用户群进行协同过滤。 　　2 基本定义
　　2.1 QPSO算法
　　粒子群优化算法是在1995年由Eberhart和Kennedy[9]提出，受到鸟群觅食行为的启发，利用个体在群体中的信息共享与借鉴，达到群体最优的效果。优化问题的每个解都可以抽象为一个粒子，定义粒子[i]的位置向量为[Xi=（xi1，xi2，...，xin）]，速度向量为[Vi=（vi1，vi2，...，vin）]，粒子的迭代形式如式1和式2所示：
　　其中[n]表示优化问题的维度;[Pbesti]表示粒子[i]此刻历史最佳位置，[Gbest]表示群体历史最佳位置;[ω]是惯性权重因子，用于调节全局和局部的搜索能力所占比重;[c1]，[c2]表示学习因子，分别负责调节粒子向[Pbesti]和[Gbest]的步长;[r1]，[r2]为概率随机因子。
　　QPSO基于量子学中量子势场的原理，粒子处于量子束缚态时可以出现在空间中的任何点，因此可以建立一个吸引势场来束缚粒子，这就解决了PSO算法中粒子收敛时只能以轨道形式出现，收敛速度较慢，已陷入局部最优无法确认全局最优等缺点。处于量子束缚态的粒子参数较少，只有位置向量而没有速度向量，粒子的速度由个体的经验和群体的经验动态调整，并且在搜索能力上优于已开发的PSO算法。主要按照以下三个公式进行进化：
　　其中M表示粒子总数，D表示粒子的维数;[Pi（t）] ，[Pgj（t）]分别表示第[i]个粒子[t]次迭代时的个体最佳位置和全局最优位置;[mbest]表示所有粒子个体最好位置的平均位置[fij（t+1）=radf（）]，[uij（t+1）=radf（）];函数[radf（）]是[0，1]服从均匀分布的随机数，[Rand（t+1）=-1，radf（）≤0.5+1，radf（）>0.5];[α]稱作收缩-扩张系数，用于表达算法的收敛性，一般采用固定取值和线性减小取值。[α]的表达式如式8所示：
　　2.2 FCM算法描述
　　1973年由Bezdek[10]提出，FCM把[n]个向量[Xi（i=1，2，...n）]分为[c]组，[ci]表示第[i]类的中心;用隶属度[uij]来表示特征点[xj]属于第[i]个聚类的程度，在[0，1]取值。根据求得的聚类中心计算个体与聚类中心的距离，使得评价指标的价值函数取最优值。本文选用第[i]个数据中心与第[j]个数据点间的欧几里得距离[dij=ci-xj]做为衡量相似性的标准。将数据集的隶属度归一化后的总和为1，如式9所示：
　　2.3 量子粒子群聚类算法
　　FCM算法是一种依靠梯度下降的局部搜索算法，具有运算简单高速的优点，但是也存在过于依赖聚类中心的初始值和容易陷入局部最优的缺点，本文中引入QPSO来快速确定初始聚类中心并且利用QPSO优秀的全局寻优能力来防止FCM算法容易陷入局部最优的现象。
　　（1）目标函数的确定
　　模糊聚类问题本质上是一个非线性约束优化问题，约束函数的连续性和可导性较差因此采用随机性方法[11]。本文采用罚函数[12]的思想将约束问题通过序列无序最小化技术转化为无约束问题，广义的目标函数形式如式14：
　　（2）算法的实现过程
　　种群由M个粒子构成，每个粒子[Xi=Vij（j=1，2，...，c）]表示一种聚类结果，[Vij]表示粒子[i]的第[j]个中心坐标，[c]表示聚类数目。
　　1使用QPSO进行随机初始化，生成包含M个粒子的粒子群，初始化粒子历史最优位置和全局最优位置;
　　2使用FCM算法中的式13计算项目隶属度矩阵，并根据式17计算粒子的适应值;
　　3根据式6，7更新粒子的最优位置和群体的最优位置，根据式3计算[mbest]，根据式4计算粒子的吸引子，根据式5更新粒子的位置;
　　4重复3，直到达到规定的目标函数值或者最大迭代次数。
　　3 推荐流程
　　3.1 概念与定义
　　基于用户的协同过滤算法的基本思想是：寻找与该用户具有相似偏好的用户，给该用户推荐相似用户喜欢且该用户没有进行评价过的物品。目前衡量物品相似度主要有欧氏距离，余弦相似性，和皮尔逊相关系数。由于实际应用数值存在不同用户的取值范围差异过大，初始值缺失等情况，能够较好地拟合不同用户的数据，文采用了皮尔逊相关系数来进行用户相似度的计算以便能够较好地拟合不同用户的数据;
　　3.2 推荐流程
　　（1）根据所需要评价的项目属性构造出稀疏的项目属性矩阵用A表示。
　　（2）对项目属性矩阵执行1.3描述的QPSO-FCM算法使项目分为C个聚类簇，[C=（C1，C2，...Cc）];根据公式13计算出项目隶属度矩阵S，[S=（ST1，ST2，....，STc）T]，[Si=（Si1，Si2，...，Sic）]，[Sij]表示项目[i]对于项目簇[j]的隶属程度。
　　（3）对隶属度矩阵[S]进行预处理，每行的最大值作为该项目的最终隶属簇 ，如式20所示：
　　（4）根据式（21）计算用户项目簇矩阵U-S*，其中[ri，k]表示用户[ui]对项目[Ik]的评分值，[Iu]表示项目簇[Cj]中用户[ui]评价过的项目集合。
　　（4）根据式18计算用户的相似度，选取Top-K用户作为目标用户的最近邻居集合，使用式19对项目进行评分预测，推荐评分Top-N的项目给该用户。
　　4 仿真与验证
　　4.1 数据来源与评价标准
　　实验数据集由movielens网站提供的1M数据
　　集ml-latest-small.zip对算法进行验证，该数据集拥有270，000个用户对45，000部电影的26，000，000个评分和750，000个电影属性标签。数据集中包含的Movie.CSV文件为生成项目属性矩阵提供原始数据，Rating.CSV为生成用户-项目评分矩阵提供原始数据。数据稀疏度表示为： 　　P表示用户评分数量，U表示用户数量，I表示项目数量。本次时延数据集的稀疏度为0.9979。根据试验需要将20%的数据作为测试集，80%作为训练集。
　　本文对推荐结果采用的评价标准为：（1）统计精度度量方法，平均绝对偏差（MAE）[13]（2）决策支持精度度量方法，常用的召回率（Recall）[14]准确率（Precision）[15]等。在视频推荐系统中MAE表示预测的用户评分与实际用户评分的偏差度;Recall表示命中的数目与测试集的大小的比例，Precision表示推荐命中的数目与Top-N数目的比例，用公式表示如下。
　　4.2 实验结果
　　本文仿真采用数据集中电影所属类别作为项目属性，根据文献[16]中提出的方法确定本文的最佳聚类数[c=30]，在此基础上实现了基于QPSO模糊聚类的协同过滤推荐算法，与其他算法运行结果对比如下：
　　4.3 结果分析
　　从实验结果的MAE来看，本文提出的算法相比于傳统的聚类算法，在最近邻个数相同的情况下可以得到较优的推荐结果，且在最近邻居个数不同的情况下能够保持推荐质量的稳定性，很好的解决传统算法存在的冷启动和数据稀疏的问题。同时证明了相比于其他聚类算法FCM与QPSO结合更能发挥出QPSO算法的优势。观察综合指标F的仿真结果可发现本文提出的算法推荐效果较好，达到了预期目的。
　　5 结束语
　　推荐算法的使用已经成为互联网应用提高用户体验，获得更多用户群体的主要手段之一。考虑实际推荐情景中存在的“冷启动”，“数据稀疏”这两大问题，本文提出一种全新的高效的推荐算法。首先使用QPSO算法与FCM算法结合，引入罚函数的思想来确立QPSO-FCM联合算法的目标函数，来解决传统的FCM算法中初始聚类中心划分的问题，稀疏的用户-项目矩阵与项目属性矩阵进过一系列计算最终得到项目-项目簇隶属矩阵与稀疏度远低与原始数据的用户-项目簇矩阵;根据用户-项目簇矩阵使用协同过滤算法中的相似度计算公式算出该用户的top-N相似用户，再根据项目-项目簇隶属矩阵选择项目进行推荐。该算法在时间复杂度和推荐结果精度上远优于传统推荐算法。
　　使用MAE和综合指标F作为评价标准，本文提出的算法得到了较好的结果。但是在最佳聚类数目的选择上需要进一步的改进和大量的实验数据验证来得到更加严谨的结果，进而发挥该算法的最大优势，同时在其他类型数据上的推荐效果有待进一步验证。
　　参考文献：
　　[1] Sarwar B M. Sparsity， scalability， and distribution in recommender systems[M]. University of Minnesota， 2001.
　　[2] O’Connor M， Herlocker J. Clustering items for collaborative filtering[C]//Proceedings of the ACM SIGIR workshop on recommender systems. UC Berkeley， 1999， 128.
　　[3] Good N， Schafer J B， Konstan J A， et al. Combining collaborative filtering with personal agents for better recommendations[C]//AAAI/IAAI. 1999： 439-446.
　　[4] Sarwar B M， Konstan J A， Borchers A， et al. Using filtering agents to improve prediction quality in the grouplens research collaborative filtering system[C]//Proceedings of the 1998 ACM conference on Computer supported cooperative work. ACM， 1998： 345-354.
　　[5] Rashid A M， Albert I， Cosley D， et al. Getting to know you： learning new user preferences in recommender systems[C]//Proceedings of the 7th international conference on Intelligent user interfaces. ACM， 2002： 127-134.
　　[6] 邓爱林， 左子叶， 朱扬勇. 基于项目聚类的协同过滤推荐算法[J]. 小型微型计算机系统， 2004， 25（9）： 1665-1670.
　　[7] 张海燕，丁峰，姜丽红.基于模糊聚类的协同过滤推荐方法[J].计算机仿真，2005（08）：144-147.
　　[8] 葛林涛， 徐桂琼. 基于模糊 C 均值聚类有效性的协同过滤算法[J]. 计算机技术与发展， 2016 （01）： 22-26， 32.
　　[9] Eberhart R， Kennedy J. A new optimizer using particle swarm theory[C]//Micro Machine and Human Science， 1995. MHS'95.， Proceedings of the Sixth International Symposium on. IEEE， 1995： 39-43.
　　[10] Bezdek J C， Ehrlich R， Full W. FCM： The fuzzy c-means clustering algorithm[J]. Computers & Geosciences， 1984， 10（2-3）： 191-203.
　　[11] Fogel D B. An introduction to simulated evolutionary optimization[J]. IEEE Trans Neural Netw， 1994， 5（1）：3-14.
　　[12] Yeniay ?. Penalty function methods for constrained optimization with genetic algorithms[J]. Mathematical and computational Applications， 2005， 10（1）： 45-56.
　　[13] 邓爱林， 朱扬勇， 施伯乐. 基于项目评分预测的协同过滤推荐算法[J]. 软件学报， 2003， 14（9）：1621-1628.
　　[14] Chedrawy Z， Abidi S S R. An adaptive personalized recommendation strategy featuring context sensitive content adaptation[C]// International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems. Springer-Verlag， 2006：61-70.
　　[15] Goldberg K， Roeder T， Gupta D， et al. Eigentaste： A Constant Time Collaborative Filtering Algorithm[J]. Information Retrieval， 2001， 4（2）：133-151.
　　[16] 于剑， 程乾生. 模糊聚类方法中的最佳聚类数的搜索范围[J]. 中国科学：技术科学， 2002， 32（2）：274-280.
　　【通联编辑：代影】
转载注明来源:https://www.xzbu.com/8/view-14949926.htm