0 概述

随着采用多标准评分系统的各类电商平台、社交网络、新闻娱乐网站等普及, 多标准协同过滤技术应运而生, 它根据用户对不同方面的评级而挖掘用户或商品的内在联系, 进而进行协同过滤推荐。有效整合这些多标准评分, 从而为用户提供更准确的个性化推荐, 以此提升用户体验, 增加平台收益, 这不仅是商家努力追求的效果, 也是学者们广泛关注的热点学术问题^[1]。其中, 多标准评分中的数据稀疏性以及评分的有效聚合成为多标准协同过滤亟待解决的重要问题^[2]。

针对多标准评分矩阵数据稀疏性问题, 文献[3-5]均采用主成分分析(Principal Component Analysis, PCA)方法对高维度稀疏评分矩阵进行降维处理。总体上说, 目前的解决方案过于单一, 特别对于较低维度的多标准评分矩阵尚缺乏有效的解决方案。

针对多标准评分的有效聚合问题, 研究人员展开一系列研究。文献[6]提出一种多标准协同过滤框架, 采用平均权重聚合各标准相似度, 并选择最小相似度为总体相似度。文献[7-8]针对各标准预测评分使用多元线性回归进行拟合得到总体预测评分, 而文献[9-10]则采用了支持向量回归方法进行拟合。文献[11-12]使用传统粒子群优化(Particle Swarm Optimization, PSO)算法、遗传算法等单一启发式算法来聚合各标准相似度或预测评分。基于传统PSO算法的聚合策略虽然能在一定程度上提高评分预测的准确性, 却未克服PSO算法早熟收敛、全局寻优能力较差以及收敛速度慢等缺点。

针对上述问题, 本文提出一种基于矩阵填充与改进PSO算法的多标准协同过滤模型MFIP_MCCF。采用矩阵填充模型解决评分数据稀疏性问题, 在不损失任何原有信息的基础上对缺失值进行预测填充, 同时通过改进PSO算法提高总体评分预测的准确性以及推荐列表的有效性。

1 多标准协同过滤

传统的协同过滤算法仅在二维空间对评分矩阵进行处理, 每个用户只会为项目提供一个总体评分R₀, 用单一指标来表达用户对项目的评价, 即Rating(u, i)=R₀。而在多标准协同过滤中, 用户除了要给出对项目的总体评价R₀外, 还提供对项目不同方面的评分, 即Rating(u, i)=(R₀, R₁, …, R_k)(k∈Criterion)。

对不同标准评分进行分离, 使用余弦相似度进行相似度计算, 将得到不同标准下的相似度, 即:

$ s\left( {\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}} \right) = \frac{{\sum\limits_{i \in {I_{u,v}}} {\left( {{r_{u,i}} - \overline {{r_u}} } \right)} \left( {{r_{v,i}} - \overline {{r_v}} } \right)}}{{\sqrt {\sum\limits_{i \in {I_{u,v}}} {{{\left( {{r_{u,i}} - \overline {{r_u}} } \right)}^2}} } \sqrt {\sum\limits_{i \in {I_{u,v}}} {{{\left( {{r_{v,i}} - \overline {{r_v}} } \right)}^2}} } }} $

(1)

其中, u和v分别代表用户u和v在每个维度下对所有项目的评分, r_{u, i}和r_{v, i}表示用户u和v对项目i的评分, $\overline {{r_u}} $和$\overline {{r_v}} $表示用户u和v的评分均值。

在得到每个标准的相似度后, 可以求得每个标准下的预测评分, 计算公式为:

$ {r_{u,i}} = \overline {{r_u}} + \frac{{\sum\limits_{v \in N(u)} s (\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}})\left( {{r_{v,i}} - \overline {{r_v}} } \right)}}{{\sum\limits_{v \in N(u)} s (\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}})}} $

(2)

对每个标准的预测评分进行聚合得到总体评分, 计算公式为:

$ ratin{g^{{\rm{total}}}}(u,i) = \sum\limits_{c \in (1,2, \cdots ,k)} {{w_c}} \cdot ratin{g^c}(u,i) $

(3)

其中, w_i是不同标准预测评分对总体评分的权重, c代表每个标准。

最后, 依据总体评分产生推荐列表。

2 矩阵填充模型

目前针对多标准协同过滤的数据稀疏性问题, 多少工作均采取降维处理方式。通过降维能去除大量弱效用数据, 在一定程度上缓解数据稀疏性对相似性计算的影响。但当数据维度较低时, 过度降维会损失原有信息, 特别是会损失那些能体现样本差异的重要数据, 对相似度计算的准确性造成影响。本文在最大程度保留低维矩阵中真实信息的基础上, 引入可靠因子, 采用矩阵填充模型来对缺失评分值进行预测, 以降低稀疏性对相似度的影响。

矩阵填充模型框架如图 1所示, 其工作原理为:首先使用混合相似度填充矩阵, 其次引入可靠因子重新计算相似度以预测各标准评分, 最后使用多元线性回归聚合各标准评分以得到预测评分。

2.1 矩阵填充

Jaccard系数是用于比较有限样本集之间相似性与差异性的常用指标。假设u和v分别代表不同用户在不同标准下对所有项目的评分, 则Jaccard系数定义如下:

$ J(u,v) = \frac{{|u \cap v|}}{{|u \cup v|}} $

(4)

文献[13]指出:Jaccard系数完善了传统相似度只考虑用户评分而忽略了其他信息量的弊端, 适合于对稀疏度较高的数据集的计算。本文使用Jaccard系数改进式(1), 得:

$ {s^\prime }(\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}) = (1 - \alpha )s(\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}) + \alpha J(\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}) $

(5)

其中, α为改进相似度的权重。这样, 一方面可以充分利用评分矩阵中的原始信息, 另一方面可以突显用户间共同评分的作用。

利用改进相似度计算预测评分, 可以对评分矩阵中的缺失项进行填充。

2.2 可靠因子

评分矩阵中的填充项实际上是模型预测的结果, 而这种结果显然会存在误差。为了降低误差对相似度计算的影响, 本文引入可靠因子^[14]对填充评分和原始的真实评分进行区分, 以达到完全信任真实评分, 部分信任预测评分的目的, 从而使用户相似度更接近真实。

定义1(可靠因子γ) 在矩阵填充中用于定义真实评分和填充评分可靠程度的参数因子。

引入可靠因子γ的改进相似度计算公式如下:

$ sim(\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}) = \frac{{\sum\limits_{i \in {I_{u,v}}} {\left( {{r_{u,i}} - \overline {{r_u}} } \right)} \left( {{r_{v,i}} - \overline {{r_v}} } \right){\gamma ^n}}}{{\sqrt {\sum\limits_{i \in {I_{u,v}}} {\left( {{r_{u,i}} - \overline {{r_u}} } \right)} {\gamma ^n}} \sqrt {\sum\limits_{i \in {I_{u,v}}} {\left( {{r_{v,i}} - {{\bar r}_v}} \right)} {\gamma ^n}} }} $

(6)

$ n = \left\{ \begin{array}{l} 1,{r_{u,i}}\;或\;{r_{v,i}}\;为填充评分\\ 0,{r_{u,i}}\;和\;{r_{v,i}}\;为真实评分 \end{array} \right. $

(7)

根据式(2)计算各标准填充评分。

3 基于改进PSO算法的多标准协同过滤

针对各标准评分聚合问题, 学者们已提出了一些相关策略, 但存在的主要问题有:把多标准评分与总体评分之间看作是简单的线性关系, 难以实现复杂映射; 传统启发式算法计算出的各标准权重存在较大误差。

本文在矩阵填充模型基础上, 提出一种基于改进PSO算法的多标准协同过滤框架, 如图 2所示, 其工作原理为:首先基于矩阵填充模型对评分矩阵进行预测, 其次用改进PSO算法对评分矩阵进行权重训练, 最后根据权重聚合各标准预测评分, 得到总体评分并产生推荐。

3.1 改进的PSO算法聚合策略

PSO算法^[15]将一个优化问题看成是空中觅食的鸟群, 试图从个体最佳适应度找到全局最佳适应度。本文将“食物”当作是多标准协同过滤中各标准权重系数的最优解, “鸟”则是在解空间中进行搜索的一个“粒子”, 每个“粒子”由所有标准的权重组成, 即每个粒子的长度大小为标准数目大小, 每个权重相当于二进制中一位。该算法通过以下规则更新每个时间戳的每个粒子的速度和位置^[14]:

$ v_{id}^{t + 1} = w \cdot v_{id}^t + {c_1} \cdot {r_1} \cdot \left( {p_{pd}^t - x_{id}^t} \right) + {c_2} \cdot {r_2} \cdot \left( {p_{gd}^t - x_{id}^t} \right) $

(8)

$ p_i^{t + 1} = p_i^t + v_i^{t + 1} $

(9)

其中, i=1, 2, …, n, d=1, 2, …, D, w为惯性权重, c₁、c₂为学习因子, r₁、r₂为0~1的随机数, p_pd^t为粒子i在第t次迭代时的最优位置, x_id^t为粒子i在第t次迭代时的当前位置, p_gd^t为种群全局最好位置。

为了克服PSO算法早熟收敛、全局寻优能力较差以及收敛速度慢等问题, 本文对该算法进行以下3点改进和优化:

1) 在全局最优粒子进化处引入高斯算子, 对粒子群速度更新方法进行扰动。文献[16]指出:高斯扰动可以增加种群的多样性, 保证粒子的自我学习能力, 防止其陷入局部最优, 避免早熟。为了突出高斯分布函数对算法收敛性起到积极作用, 本文将迭代数目与高斯算子相结合, 对每次迭代后全局最优粒子进行改进。当越接近最大迭代值时, 当前迭代数与最大迭代数目值越接近1, 高斯扰动算子影响就越大, 其进化模式如下:

$ \begin{array}{l} v_{id}^{t + 1} = w \cdot v_{id}^t + {c_1} \cdot {r_1} \cdot \left( {p_{pd}^t - x_{id}^t} \right) + \\ \;\;\;\;\;\;\;\;{c_2} \cdot {r_2} \cdot \left( {p_{gd}^t + Gauss_{id}^t - x_{id}^t} \right) \end{array} $

(10)

$ Guass_{id}^t = Gaussian\left( {\mu ,{\sigma ^2}} \right) \cdot t/IterNum $

(11)

其中, t为当前迭代数, IterNum为最大迭代数, Gauss_id^t为第t次迭代时对全局最优值的扰动项, Gaussian(μ, σ²)为服从高斯分布(μ, σ²)的随机数(μ=0, σ=|x_id^t|)。

2) 本文对惯性权重w、学习因子c₁和c₂进行动态调整。惯性权重w对粒子寻优搜索能力及其收敛速度均有重要影响。当w较大时, 全局搜索能力比局部搜索能力强, 有利于算法扩展; 当w较小时, 局部搜索能力比全局搜索能力强, 有利于算法收敛。为了增强算法收敛速度, 将w设置为一个随迭代次数增加而减少的函数, 算式如下:

$ w = c \cdot \exp ( - 0.5 \cdot t/IerNum) $

(12)

其中, c为常数, 取经验值为0.8。

在算法搜索的过程中, c₁、c₂的取值会对粒子的最优解以及整个群体产生影响。为了避免粒子陷入局部最优解, 文献[17]指出:通过学习因子的异步变化方法, 可以让粒子在搜索过程中减少自我认知成分、增加社会认知成分, 使得粒子能够快速收敛于全局最优解。基于此思想, 本文根据式(13)和式(14)对学习因子c₁、c₂进行调整。随着当前迭代次数逼近最大迭代数, t/IterNum越接近1, 则粒子自我认知成分越少, 社会认知成分越大。

$ {c_1} = {c_{1\max }} - \left( {{c_{1\max }} - {c_{1\min }}} \right) \cdot t/IterNum $

(13)

$ {c_2} = {c_{2\max }} + \left( {{c_{2\max }} - {c_{2\min }}} \right) \cdot t/IterNum $

(14)

其中, c_1max、c_1min分别为c₁的最大值与最小值, c_2max、c_2min分别为c₂的最大值与最小值。

3) 利用遗传算法中的交叉、变异算子对整个子代进行更新。在每次种群迭代完全时, 将种群看成一个个体, 每个个体由多个染色体组成, 每个粒子(即所有标准的权重)看作是一个染色体, 进行交叉变异操作, 交叉变异后产生的染色体与式(9)~式(11)寻优粒子作比较, 以选出最符合全局最优的粒子, 使得粒子逃离局部最优, 交叉变异方式如下所示:

$ Gpop = Cross\left( {{p_i},{p_j},pci,pc} \right) $

(15)

$ Gpop' = Mutation(pop{\rm{,}}i{\rm{,}}pmi,pm) $

(16)

其中, pc、pm为设置的交叉、变异概率, 分别设置为经验值0.7和0.1, p_i、p_j为在pc交叉概率下种群中随机选择的2个粒子, pci为选择2个粒子的交叉的随机位置, pop为每次迭代后的种群, i为pm交叉概率下在pop种群中随机选择pmi位置进行变异。

对于使用PSO算法解决的特定问题, 需要有一个合适的适应度函数, 本文选择的适应度函数为:

$ Fitness = \frac{{\sum\limits_{i = 0}^N {\left| {{P_i} - {Q_i}} \right|} }}{N} $

(17)

其中, N代表训练集中的评论数, P_i代表用户的真实评分, Q_i代表用户的预测评分。

综上, 改进的算法流程描述如下:

步骤1  初始化惯性权重w、学习因子c₁和c₂的范围、最大迭代数IterNum、粒子种群数N、种群pop以及交叉变异概率pc和pm。

步骤2  计算种群中各个粒子的适应度值Fitness、个体最优解p_pd和全局最优解p_gd。

步骤3  根据式(12)~式(14)对惯性权重w、学习因子c₁和c₂进行自适应调整。

步骤4  根据式(9)~式(11)在约束条件下, 进行迭代, 更新粒子的飞行速度和位置。

步骤5  根据式(13)和式(14)在约束条件下, 对种群交叉变异操作, 寻找全局最优解。

步骤6  当达到最大迭代次数, 算法停止。

3.2 推荐列表生成

根据改进PSO算法训练得到各标准权重w₁, w₂, …, w_c, 再通过式(3)得到总体预测评分。最后, 向用户推荐预测评分靠前的N个项目, 生成TopN推荐列表。

4 实验与结果分析 4.1 数据集

本文在Yahoo!Movies网站上爬取了电影评分数据集, 为避免噪声数据影响, 首先对数据集进行清洗, 提取出341个用户对501部电影进行评分的记录, 总共为12 022条, 数据集示例如表 1所示。其中, 每条评分记录包含总体评分和4个不同标准的评分, 用户评分范围为[-1, 5], -1表示用户没有对项目进行评分(缺失值)。最后, 将提取的数据集划分为80%训练集和20%测试集。

数据集的稀疏率为:

$ \begin{array}{l} Sparsity = 1 - \frac{{numRatings \times 100\% }}{{numUsers \times numItems}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1 - \frac{{12\;022 \times 100\% }}{{341 \times 501}} = 92.96\% \end{array} $

4.2 评价指标

为了对模型的评分预测准确性进行评估, 本文采用平均绝对误差(Mean Absolute Error, MAE)作为评价指标, 其计算公式为:

$ {M_{{\rm{MAE}}}} = \frac{{\sum\limits_{i = 1}^N {\left| {{P_i} - {Q_i}} \right|} }}{N} $

(18)

其中, P_i代表用户的真实评分, Q_i代表用户的预测评分, N为总体项目数。

为了对推荐效果进行评估, 本文采用了F-Measure作为评价指标。F-Measure是准确率P和召回率R的加权调和平均值, 准确率为在TopN推荐结果中被正确做出推荐的项目比例, 召回率为全部测试集中被正确做出推荐的项目比例, 计算公式为:

$ F - Measure = \frac{{2PR}}{{P + R}} $

(19)

$ P = \frac{{\left| {test \cap TopN} \right|}}{N} $

(20)

$ R = \frac{{\left| {test \cap TopN} \right|}}{{\left| {test} \right|}} $

(21)

其中, test表示测试集, TopN表示推荐项目的集合。

4.3 实验结果

为验证MFIP_MCCF模型的有效性, 本文选取7种模型进行对比实验:基于用户的传统协同过滤(SCF)模型, 多标准平均权重(MCAW)^[6]模型, 多标准线性回归(MCLR)^[8]模型, 基于PCA的多标准协同过滤(PCA_MCCF, 保留95%原始信息)^[3]模型, 矩阵填充多标准协同过滤(RMF_MCCF)^[18]模型, 基于标准粒子群算法聚合策略(P_MCCF)^[9]模型, 基于遗传算子改进粒子群算法聚合策略(GIP_MCCF)^[12]模型。各模型相关属性如表 2所示。

4.3.1 矩阵填充模型参数选择

为了选取矩阵填充模型中的Jaccard系数权重α以及可靠因子γ, 本文首先进行参数选择实验。

在每个标准上利用传统协同过滤方法进行实验, 结果表明, 当|TopN|=6时, 评分预测的误差最小。在此基础上, 设置Jaccard系数权重α为不同取值, 分别计算对应的MAE值, 其结果如图 3所示。实验结果表明, 当α=0.1时, 评分预测的误差最小, 因此本文选择α=0.1。

本文采用同样的对比方法确定可靠因子γ。首先利用α求得模型混合相似度, 并求解预测评分以进行矩阵填充; 其次在[0, 1]范围内对γ设置不同取值, 计算系统MAE值, 其结果如图 4所示。实验结果表明, 当γ=0.45时, 系统误差最小, 为0.893 71, 因此本文选择γ=0.45。

4.3.2 对比实验

基于上节所选参数值, 对本文模型与其他7种模型的评分预测误差MAE进行对比, 实验结果如图 5所示。

由图 5可以看出:

1) 多标准协同过滤模型全部优于传统的单评级协同过滤模型(SCF)。

2) MCLR模型优于MCAW模型, 表明基于线性回归的聚合策略优于平均聚合策略。

3) 当|TopN|>10时, RMF_MCCF模型明显优于PCA_MCCF模型, 表明当数据维度较低时, 相比降维方法, 矩阵填充方法评分预测效果较好, 较适合解决数据稀疏性问题。

4) P_MCCF模型优于RMF_MCCF模型, 表明PSO算法较适合用于度量总体评分与多标准评分之间复杂的映射关系。

5) 当|TopN|>6时, 相比于GIP_MCCF和P_MCCF模型, MFIP_MCCF模型评分预测效果较好, 且误差较稳定, 表明对PSO算法的优化和改进有较好的效果。

本文对P_MCCF、GIP_MCCF和MFIP_MCCF 3种模型的推荐效果进行比较评估, 将推荐产生TopN列表的准确率、召回率以及F-Measure值进行比较, 结果如图 6所示。

从图 6可以看出, 相比于P_MCCF和GIP_MCCF模型, MFIP_MCCF模型的准确率、召回率以及F-Measure值较高, 表明本文模型能够推荐出更符合用户偏好的列表, 特别是当推荐项目为20时, 推荐效果最优。

5 结束语

本文提出一种基于矩阵填充与改进PSO算法的多标准协同过滤模型。该模型能有效缓解低维数据的稀疏性, 提高粒子群算法的局部搜索能力, 并克服算法早熟现象, 使得训练的各标准权重接近真实值, 产生符合用户偏好的推荐列表。实验结果表明, 相比于P_MCCF和GIP_MCCF模型, MFIP_MCCF模型的准确率、召回率以及F-Measure值均较高。下一步将改进推荐排序算法, 以生成更具个性化的推荐列表。