基于柯西分布量子粒子群的混合推荐方法

摘要

本发明公开了一种基于柯西分布量子粒子群的混合推荐方法。包括以下几个步骤：构建用户对项目的评分矩阵；构建用户综合相似度矩阵和项目综合相似度矩阵，求得用户和项目的最近邻居集合；求得基于用户推荐的第一项目预测评分值，基于项目推荐的第二项目预测评分值，和最终项目预测评分值；采用柯西分布量子粒子群算法搜索用户评分与内容的权值w1、项目评分与内容的权值w2、用户最近邻居阈值w3、项目最近邻居阈值w4、混合推荐权值w5这5个参数的最优值，得到更新后的最终项目预测评分值；根据更新后的最终项目预测评分值，将项目进行降序排列，选出排在前N位的项目推荐给用户。本发明能够快速寻找最佳的推荐参数组合，提高推荐的准确度。

说明书

技术领域

本发明涉及一种推荐方法，尤其是一种能够快速寻找最佳的推荐参数组合、提高推荐准确度的基于柯西分布量子粒子群的混合推荐方法。>

背景技术

推荐系统中处于核心和基础地位的环节是推荐算法，算法一方面关系着推荐系统的性能，另一方面还决定了系统的实现方式和整体架构设计，研究人员需按照实际的推荐问题选择合适的算法设计对应的推荐架构。所以，目前有关推荐系统的研究工作也大多围绕着推荐算法的研究与改进而进行，而且已经有很多有效的改进算法被提出。现在的推荐系统中主流的推荐算法主要包括基于规则的推荐算法、基于内容的推荐算法、基于网络结构的推荐算法、基于协同过滤的以及把两种或两种以上的推荐算法结合起来的混合推荐算法。其中，协同过滤算法是应用最成功和最广泛的推荐算法。每种推荐算法都有其各自的优缺点和适用的范围，随着人们对推荐系统性能的要求日渐提高，在实际应用中，推荐系统往往不能只依靠某一单一的算法进行推荐，而是将几种推荐算法进行优势结合，取长补短进行混合推荐。>

在推荐系统被普遍应用的同时，算法的缺陷也开始表现出来，常见的诸如：数据稀疏性、用户和项目的冷启动以及忽略用户兴趣随时间变化等问题。>

发明内容

本发明的目的是提供一种具有高推荐准确度的基于柯西分布量子粒子群的混合推荐方法。>

本发明是通过以下技术方案实现的：>

基于柯西分布量子粒子群的混合推荐方法，包括以下几个步骤：>

步骤一：构建用户对项目的评分矩阵，评分矩阵包括用户编号、项目编号以及用户评分；>

步骤二：构建用户综合相似度矩阵和项目综合相似度矩阵，求得用户和项目的最近邻居集合；>

建立相似度计算方程：>

$\mathrm{Sim}(u,v)=\frac{{\Sigma }_{c\in C_{\mathrm{uv}}}(R_{\mathrm{ui}}-\overline{R_u})(R_{\mathrm{vi}}-\overline{R_v})\times \mathrm{WT}(v,i)}{\sqrt{{\Sigma }_{c\in C_u}{(R_{\mathrm{ui}}-\overline{R_u})}^2}\sqrt{{\Sigma }_{c\in C_v}{(R_{\mathrm{vi}}-\overline{R_v})}^2}}\times \omega (u,v)$

C_u,v表示用户u和用户v各自评分项目集合的并集，C_u代表用户u评分过的项目集合，C_v代表用户v评分过的项目集合，代表用户u对所有评价过的项目评分的均值，代表用户v对所有评价过的项目评分的均值，ω(u,v)为相似权重值，WT(v,i)为时间因子，>

$\omega (u,v)=\frac{I_{\mathrm{uv}}}{\max \left(I_{\mathrm{uv}}\right)},v\in U$

I_uv＝{I_uv||R_ui-R_vi|＜＝τ},i∈C_uv代表用户u和v共同评分且评分差不高于阈值τ的项目数，即评分相似的项目数，max(I_uv)为用户u与所有其他用户之间相似项目数的最大值，ω(u,v)为用户u和v之间的相似权重值，ω(u,v)的取值范围为[0,1]，>

时间因子WT(v,i)为：>

$\mathrm{WT}(v,i)=1-\frac{|t_{\mathrm{ui}}-t_{\mathrm{vi}}|}{\max \left(\right|t_{\mathrm{ui}}-t_{\mathrm{vi}}\left|\right)},u,v\in U$

t_ui为用户u对项目i的评分时间，t_vi为用户v对项目i的评分时间，集合U为所有对项目i评过分的用户组成的集合，WT(v,i)为用户v对项目i评分的时间因子，WT(v,i)的取值范围为[0,1]，>

分别求得用户评分相似度矩阵URsim、用户内容相似度矩阵UCsim、项目评分相似度矩阵IRsim以及项目内容相似度矩阵ICsim，>

得到用户综合相似度矩阵：>

Usim＝w1×URsim+(1-w1)×UCsim>

项目综合相似度矩阵：>

Isim＝w2×IRsim+(1-w2)×ICsim>

w1为用户评分与内容的权值，w2为项目评分与内容的权值，>

设定用户最近邻居阈值为w₃，项目最近邻居阈值为w₄，选择用户和项目的最近邻居集合；>

步骤三：求得基于用户推荐的第一项目预测评分值为：>

$U{P}_{\mathrm{ui}}=\overline{R_u}+\frac{{\Sigma }_{i\in C_{\mathrm{uv}}}\mathrm{Usim}(u,v)\times (R_{\mathrm{vi}}-\overline{R_v})}{{\Sigma }_{i\in C_{\mathrm{uv}}}\left|\mathrm{Usim}(u,v)\right|}$

基于项目推荐的第二项目预测评分值为：>

$I{P}_{\mathrm{ui}}=\overline{R_i}+\frac{{\Sigma }_{i\in C_{\mathrm{uv}}}\mathrm{Isim}(u,v)\times (R_{\mathrm{vi}}-\overline{R_i})}{{\Sigma }_{i\in C_{\mathrm{uv}}}\left|\mathrm{Isim}(u,v)\right|}$

最终项目预测评分值为：>

P_u,i＝w₅×UP_ui+(1-w₅)×IP_ui

其中，Usim(u,v)＞＝w₃，Isim(u,v)＞＝w₄，w₅为混合推荐权值；>

步骤四：采用柯西分布量子粒子群算法搜索用户评分与内容的权值w1、项目评分与内容的权值w2、用户最近邻居阈值w₃、项目最近邻居阈值w₄、混合推荐权值w₅这5个参数的最优值，得到更新后的最终项目预测评分值；>

步骤五：根据更新后的最终项目预测评分值，将项目进行降序排列，选出排在前N位的项目推荐给用户。>

本发明基于柯西分布量子粒子群的混合推荐方法还可以包括：>

步骤四包括以下几个步骤：>

步骤4.1：初始化种群规模为n，第i个粒子位置向量表示为X_i＝(X_i1,X_i2,X_i3,X_i4,X_i5)，X_i1对应用户评分与内容的权值w1，X_i2对应项目评分与内容的权值w2，X_i3对应用户最近邻居阈值w₃，X_i4对应项目最近邻居阈值w₄，X_i5对应混合推荐权值w₅，最大迭代次数为pe；>

步骤4.2：将初始种群粒子带入最终项目预测评分值，把得到的最终项目预测评分值的平均绝对误差MAE作为每个粒子的第一适应度值f(X_i)；>

步骤4.3：更新粒子位置为：>

$X_{\mathrm{id}}(t+1)=q_{\mathrm{id}}\left(t\right)\pm \beta |\mathrm{mbest}\left(t\right)-X_{\mathrm{id}}\left(t\right)|\ln \left(\frac{1}{\mu }\right)$

其中，$\beta =a-(a-b)\times \frac{\mathrm{MaxTimes}-t}{\mathrm{MaxTimes}+0.5}$

$\left(\begin{array}{c}\mathrm{mbest}\left(t\right)=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_i\left(t\right)\\ =[\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_{i1}\left(t\right),\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_{i2}\left(t\right),...,\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_{\mathrm{iD}}\left(t\right)]\end{array}\right)$

q_id(t)＝(c₁p_id(t)+c₂p_gd(t))/(c₁+c₂)c₁～C(0,1)，c₂～C(0,1)>

X_i＝(X_i1,X_i2,...,X_iD)，i＝1,2,...,n，X_i为第i个粒子的位置，n为种群规模，mbest(t)为第t次迭代时的粒子平均值，表示群体中平均最佳位置，μ服从[0,l]上的均匀分布，p_i(t)为第i个粒子的个体最优位置，p_g(t)为全局的最优位置，β为收缩扩张系数；>

步骤4.4：计算粒子在当前位置的第二适应度值；>

步骤4.5：如果粒子在当前位置的第二适应度值比个体最优值小，则更新个体最优值和最优位置，否则，保持原来的个体最优值和最优位置不变；>

步骤4.6：如果第t+1代种群中粒子的最小适应度值比第t代的全局最优值小，则更新全局最优值和最优位置，否则，保持原来的全局最优值和最优位置不变；>

步骤4.7：如果满足最大迭代次数，则输出最终的全局最优适应度值以及全局最优位置，得到用户评分与内容的权值w1、项目评分与内容的权值w2、用户最近邻居阈值w₃、项目最近邻居阈值w₄、混合推荐权值w₅这5个参数的最优值；如果没有满足最大迭代次数，则重复步骤4.3～步骤4.7。>

本发明的有益效果：>

本发明能够使用户和项目的相似性计算更加准确；能够反映用户兴趣随时间变化的特性；能够快速寻找最佳的推荐参数组合，提高推荐的准确度；能够有效缓解数据稀疏性及冷启动问题。>

附图说明

图1为本发明方法的混合推荐模型。>

图2为本发明整个过程的流程图。>

图3为柯西分布量子粒子群优化过程的详细流程图。>

具体实施方式

下面根据附图对本发明的具体实施例做进一步说明。>

一种基于柯西分布量子粒子群的混合推荐算法，涉及到推荐算法中相似度计算方法的改进、代表用户兴趣随时间变化特性的时间因子的引入以及算法中的组合参数选取等方面。该算法在协同过滤算法的基础上融合用户和项目的特征属性信息，并在此基础上对相似度的计算方法进行了改进、引入了反映用户兴趣变化的时间因子，使其能够在用户-项目评分矩阵极度稀疏的情况下，根据用户和项目的特征信息进行推荐，能够有效缓解数据稀疏性和冷启动的问题。除此之外，算法采用柯西分布量子粒子群算法对算法中所涉及的参数进行最优组合搜索，能够快速而准确地找到最优的参数组合，以提高推荐的准确度。>

本发明的实现主要包括两个阶段：混合推荐模型的构建和基于柯西分布量子粒子群的参数搜索。>

1)混合推荐模型的构建。如图1所示，将用户和项目的特征属性信息加入到协同过滤算法中，构建一种混合推荐模型，使其能够在用户-项目评分矩阵极其稀疏的情况下，利用用户和项目的特征属性信息进行相似度的计算，能够有效缓解数据稀疏性和冷启动的问题。该阶段主要分如下四步来进行：>

①构建用户-项目评分矩阵。用户对项目的评价信息可以有多种表示方式，可以用二进制 0、1表示用户喜欢或不喜欢项目，也可用整数值1至5表示用户对项目的评分级别。>

②构建用户、项目的相似度矩阵，寻找用户和项目的最近邻居集合。>

首先，根据公式(1)分别计算用户评分相似度矩阵URsim、用户内容相似度矩阵UCsim、项目评分相似度矩阵IRsim以及项目内容相似度矩阵ICsim。>

$\mathrm{Sim}(u,v)=\frac{{\Sigma }_{c\in C_{\mathrm{uv}}}(R_{\mathrm{ui}}-\overline{R_u})(R_{\mathrm{vi}}-\overline{R_v})\times \mathrm{WT}(v,i)}{\sqrt{{\Sigma }_{c\in C_u}{(R_{\mathrm{ui}}-\overline{R_u})}^2}\sqrt{{\Sigma }_{c\in C_v}{(R_{\mathrm{vi}}-\overline{R_v})}^2}}\times \omega (u,v)---\left(1\right)$

$\omega (u,v)=\frac{I_{\mathrm{uv}}}{\max \left(I_{\mathrm{uv}}\right)},v\in U---\left(2\right)$

$\mathrm{WT}(v,i)=1-\frac{|t_{\mathrm{ui}}-t_{\mathrm{vi}}|}{\max \left(\right|t_{\mathrm{ui}}-t_{\mathrm{vi}}\left|\right)},u,v\in U---\left(3\right)$

公式(1)中，C_u,v表示用户u和v各自评分项目集合的并集，C_u和C_v代表用户u和v各自评分过的项目集合，和分别代表用户u和v对所有评价过的项目评分的均值。>

在公式(2)中，I_uv＝{I_uv||R_ui-R_vi|＜＝τ},i∈C_uv代表用户u和v共同评分且评分差不高于阈值τ的项目数，即评分相似的项目数，这里，τ的取值根据具体的推荐场合而定；max(I_uv)为用户u与所有其他用户之间相似项目数的最大值；ω(u,v)为用户u和v之间的相似权重值，它的取值范围为[0,1]，取值越大表示用户间就越是相近。该权重值引入之后，只有用户共同评分且评分相近的项目比较多的时候，才更有可能变成更相近的用户，而那些评分相似，但是参与共同评分的项目过少的用户之间成为相似用户的机会降低了，符合实际的情况。>

在公式(3)中，t_ui、t_vi分别为目标用户u和用户v对项目i的评分时间；集合U为所有对项目i评过分的用户组成的集合；WT(v,i)为用户v对项目i评分的时间因子，它的取值范围为[0,1]。时间因子的引入，使相似度的计算能够考虑到用户兴趣随时间变化的特性，依照用户评价项目的时间不同，为每个用户分配不同的权重，当用户v的评分时间与目标用户u的评分时间越接近时获得的时间因子越大。>

其次，用户和项目综合相似度通过如下公式(4)和(5)计算得到：>

Usim＝w1×URsim+(1-w1)×UCsim (4)>

Isim＝w2×IRsim+(1-w2)×ICsim (5)>

其中，w1为用户评分与内容的权值，w2为项目评分与内容的权值。>

然后，依据具体的选择策略选择用户和项目的最近邻居。本文中设定用户最近邻居阈值为w3，项目最近邻居阈值为w4。>

③得到用户和项目最近邻居矩阵后，按照公式(6)和(7)分别得到基于用户推荐的项目预测评分值UP_ui和基于项目推荐的项目预测评分值IP_ui，最后，利用公式(8)得到最终的预测评分结果P_u,i。>

$U{P}_{\mathrm{ui}}=\overline{R_u}+\frac{{\Sigma }_{i\in C_{\mathrm{uv}}}\mathrm{Usim}(u,v)\times (R_{\mathrm{vi}}-\overline{R_v})}{{\Sigma }_{i\in C_{\mathrm{uv}}}\left|\mathrm{Usim}(u,v)\right|}---\left(6\right)$

$I{P}_{\mathrm{ui}}=\overline{R_i}+\frac{{\Sigma }_{i\in C_{\mathrm{uv}}}\mathrm{Isim}(u,v)\times (R_{\mathrm{vi}}-\overline{R_i})}{{\Sigma }_{i\in C_{\mathrm{uv}}}\left|\mathrm{Isim}(u,v)\right|}---\left(7\right)$

P_u,i＝w₅×UP_ui+(1-w₅)×IP_ui (8)>

其中，Usim(u,v)＞＝w₃，Isim(u,v)＞＝w₄，表示只有相似度大于w₃的用户才有可能变成目标用户的最近邻居，只有相似度大于w₄的项目才能成为目标项目的最近邻居。w₅为混合推荐权值。>

④根据得到的最终预测评分结果，将项目进行降序排列，选出排在前N位的项目推荐给用户，即进行Top N推荐。>

2)采用柯西分布量子粒子群算法搜索混合推荐模型中的最优参数组合。混合推荐模型中涉及项目评分和内容权值w₁、用户评分和内容权值w₂、用户最近邻居阈值w₃和项目最近邻居阈值w₄、基于用户推荐和基于项目推荐权值w₅，共5个参数，如果人为选取，计算量将非常大。采用柯西分布量子粒子群算法对参数进行搜索将更快速更有效。该阶段主要通过以下几个步骤实现，如图3所示：>

①设初始化种群规模为n，第i个粒子位置向量表示为X_i＝(X_i1,X_i2,X_i3,X_i4,X_i5)，五个坐标分别对应w₁，w₂，w₃，w₄，w₅，最大迭代次数为pe；>

②将初始种群粒子带入混合推荐模型中，计算预测评分，如图2所示，把得到的预测值的平均绝对误差MAE作为每个粒子的适应度值f(X_i)；>

③按照公式$X_{\mathrm{id}}(t+1)=q_{\mathrm{id}}\left(t\right)\pm \beta |\mathrm{mbest}\left(t\right)-X_{\mathrm{id}}\left(t\right)|\ln \left(\frac{1}{\mu }\right)$更新粒子位置；>

其中，$\beta =a-(a-b)\times \frac{\mathrm{MaxTimes}-t}{\mathrm{MaxTimes}+0.5}$

$\left(\begin{array}{c}\mathrm{mbest}\left(t\right)=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_i\left(t\right)\\ =[\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_{i1}\left(t\right),\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_{i2}\left(t\right),...,\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{p}_{\mathrm{iD}}\left(t\right)]\end{array}\right)$

q_id(t)＝(c₁p_id(t)+c₂p_gd(t))/(c₁+c₂)c₁～C(0,1)，c₂～C(0,1)>

X_i＝(X_i1,X_i2,...,X_iD)，i＝1,2,...,n，X_i为第i个粒子的位置，n为种群规模；mbest(t)为第t次迭代时的粒子平均值，表示群体中平均最佳位置；μ服从[0,l]上的均匀分布；p_i(t)为第i个粒子的个体最优位置，p_g(t)为全局的最优位置；β被称为收缩扩张系数，是量子粒子群优化算法重要参数。>

④重新计算粒子在新位置的适应度值；>

⑤判断是否更新个体最优值和最优位置：>

如果当前粒子的适应度值比个体最优小，则更新个体最优值和最优位置，否则，保持原来的值和位置不变；>

⑥判断是否更新全局最优值和最优位置：>

如果第t+1代种群中粒子的最小适应度值比第t代的全局最优值小，则更新全局最优值和最优位置，如若不然，保持原来的值和位置不变；>

⑦判断是否满足最大迭代次数：>

如果满足，则算法结束，输出最终的全局最优适应度值以及全局最优位置；如若不然，输出第t代的最优适应度值以及全局最优位置；并返回到③继续迭代。>

由于柯西分布量子粒子群算法在更新粒子位置时同时考虑个体最优位置和全局最优位置，并且以柯西分布两翼概率特性的特点，可以有效扩大粒子的全局搜索范围，使它比高斯分布产生的随机数分布区域更大，因而柯西分步有更大的概率快速跳出局部最优点，避免出现早熟现象。因此，本发明能更加快速而准确地找到具有最佳推荐效果的参数组合，提高推荐的准确度。>

下面将本发明应用于Movie Lens数据集，具体说明。>

Movie Lens是一个经典的电影评分数据集，共有943个用户对1682部电影共10万条的电影评分信息。除了这些，Movie Lens数据集还囊括了用户和电影的内容信息数据。>

现将数据集中的相应数据进行编码约束如下：>

(1)用户评分数据中包括用户编号、项目编号以及用户评分。这里，用户评分值的变化区间为1～5，1为最低评分，5为最高评分。>

(2)用户特征数据中包括用户编号、年龄、性别、职业以及地址邮编。其中用户年龄分成5段：0～20岁，21～30岁，31～40岁，41～50岁，51岁及以上，分别用1、2、3、4、5表示。用户性别表示为：男：1，女：0。用户职业分为教师、学生、医生、律师和程序员等21类职业，依次用数字1、2、3、…、21表示，其中不属于任何类型的职业定义为其它，假设其它归为一类职业，否则推荐算法无法进行。所在地按用户邮编首字母编码，首字母一样代表所在的区域位置一样。>

(3)项目特征数据中包括电影的编号和种类。电影种类包含动作、剧情、恐怖和喜剧等19类，有些影片同时属于很多个种类，所以实验过程中某电影若属于当前类别时对应单元格置1，否则置0。>

对本发明中的一些参数设置如下：初始种群随机生成，规模为20，种群中个体位置变化的范围为[0,1]，最大迭代次数为30次。>

在以上条件下，利用公式(1)计算用户评分相似度矩阵URsim、用户内容相似度矩阵UCsim、电影评分相似度矩阵IRsim以及电影内容相似度矩阵ICsim；利用公式(4)和(5)计算用户和电影综合相似度矩阵；利用公式(6)、(7)和(8)得到目标用户对电影的最终预测评分；最后根据预测评分值，对电影进行降序排列，为用户选出前N项进行推荐。>