结合改进用户聚类与LFM 模型的协同过滤推荐算法

顾明星，张梦甜

（1.昆山市未成年人素质教育校外实践基地，江苏 昆山 215300；2.昆山市千灯中心小学校，江苏 昆山 215300）

随着互联网的快速发展，信息量呈爆炸式增长，人类进入了“信息过载”时代[1]，解决信息过载最有效的方法是搜索引擎和推荐算法[2]。传统协同过滤算法主要是寻找与目标用户有相似品味的用户，然后将相似用户喜欢的项目推荐给目标用户[3]。但是随着用户、物品数量增加，数据稀疏性问题使得传统协同过滤推荐算法在实际应用中面临推荐准确性较低的问题[4]。

为了提高推荐算法准确性，众多相关学者从多个角度出发，对协同过滤算法进行优化。例如文献[5]从用户相似性度量和评分预测2 个方面进行了修正，首先在相似度计算中引入用户评分均值差，其次在预测评分时引入用户评分均值，从而降低因用户评分尺度不同对推荐结果造成的影响。文献[6]提出将K-means与隐语义模型相结合的推荐算法，首先利用K-means算法对用户进行聚类得到目标用户所在的集合，其次重新构建评分矩阵，在新矩阵中利用隐语义模型预测用户评分。文献[7]提出了一种改进的LFM 矩阵分解推荐算法，通过在批量学习方法中引入冲量和中间动量并结合增量学习，提高了推荐算法的精度和寻优速率。文献[8]提出了一种线性加权的推荐算法，为了降低用户兴趣随时间变化的影响，引入TimeRBM 模型预测评分；同时，利用ItemAC 算法对项目属性聚类、相同簇内的项目属性值加权进行预测评分，最后将2 次评分融合得到最终评分。

上述改进算法能有效提高传统协同过滤算法的推荐质量，但未能充分利用已有数据信息。因此本文提出了一种混合推荐算法，在传统协同过滤推荐算法的基础上，挖掘影响评分相似度的多个因素来提高计算的精度，再利用用户属性信息进一步改善预测效果。算法的核心思想如下：①利用改进相似度公式的协同过滤算法预测目标用户对未评分项目的评分；②将改进的AP 聚类算法与隐语义模型相结合预测目标用户对未评分项目的评分；③将前2 步所得的预测评分进行合理的线性加权，为目标用户推荐前N个评分较高的项目。

1 相关工作

1.1 改进相似度的协同过滤算法（I_CF＊）

协同过滤推荐算法的步骤是：先利用已有数据，构建用户-项目评分矩阵，然后计算用户之间相似度并选取近邻集，最终进行评分预测并按照Top-N原则向用户推荐[9]。算法流程如图1 所示。

图1 协同过滤算法流程图

本文构建的用户-项目评分矩阵Cmn，User：｛u1，u2，…，um｝为具有m个用户的集合；Item：｛i1，i2，…，in｝为具有n个项目的集合；cij为用户i对项目j的实际评分，若未评分，则cij记为0。矩阵Cmn如下所示：

传统算法常用余弦相似性计算项目之间的相似度，余弦相似性将m个用户对项目i和项目j的评分视作2 个n维向量，物品i和j的相似度则为2 个向量的夹角余弦值[10]，如下所示：

式中：User为所有用户集合；cui和cuj分别为u对i和j的实际评分的数值。

余弦相似性只是简单根据用户评分数值计算物品相似度，未考虑以下3 个因素：①评分网站对用户打分的影响。例如有些网站的页面布局规整美观，用户更愿意打高分；而有些网站的页面布局差，用户更愿意打低分。②项目本身属性的影响。例如在电影评分项目中，电影质量较差的得分低，电影质量高的得分高。③用户自身打分习惯的影响。有些用户较宽容，普遍评分较高；有些则严格，普遍评分较低。

为了降低上述3种情况对项目相似度计算的影响，本文将对余弦相似性公式添加μ、bi、bu这3 个影响因子，改进公式如下所示：

式中：Uij为共同给i和j评分的用户集；μ为所有样本的平均分的数值，体现第一种影响因素；bi为i的平均分的数值，体现第二种影响因素；bu为用户u的评分均分的数值，体现第三种影响因素。

根据改进的余弦相似性，目标用户u对项目i的评分预测评分如下所示：

式中：pu，i为u对i的预测评分的数值；Gi为i的最近邻项目集合；为项目i的平均分的数值。

1.2 改进的AP 聚类算法（AP＊）

AP 聚类算法是一种基于数据点间“信息传递”的聚类算法[11]。首先，算法计算每一个数据点之间的相似度，构造相似度矩阵S；然后，根据相似度矩阵更新吸引度矩阵R和归属度矩阵A；最后，利用阻尼系数λ对矩阵R和矩阵A进行收敛直至最大迭代次数（一般取1 000）或聚类中心连续多次迭代不再发生改变（一般取50 次连续迭代）时终止计算[12]。

吸引度矩阵R的更新公式如下所示：

式中：Rt+1（i，k）为下一次迭代中点i和点k的吸引度值；S（i，k）为点i和点k的相似度值；At（i，j）为当前迭代中点i和点j的归属度值；Rt（i，j）为当前迭代中点i和点j的吸引度值。

归属度矩阵A的更新公式如下所示：

式中：At+1（i，k）为下一次迭代中点i和点k的归属度值；Rt+1（j，k）为下一次迭代中点j和点k的吸引度值。

根据阻尼系数λ对矩阵R和矩阵A进行收敛，公式如下所示：

式中：Rt（i，k）为当前迭代点i和k的吸引度值；At（i，k）为当前迭代中点i和k的归属度值。

原始AP 聚类算法中，在利用阻尼系数λ对矩阵R和矩阵A进行收敛的时候，若λ过大，会使原始算法收敛速度过慢，降低算法效率；反之λ过小则容易出现算法的震荡，聚类难以收敛。因此，本文对λ的取值进行如下改进。

定义聚类增量率aug为每次聚类数量增长的变化程度，公式如下所示：

式中：Iter，i、Iter，i－1和Iter，i－2分别为本次、前一次和前2 次簇的数量。

定义震荡频数e：当aug＞1 时，表示当前聚类的增量变大，算法出现震荡。设定算法每迭代l次后，计算aug＞1 的次数e，记作震荡频数。

为了避免由于震荡次数过多而导致的算法无法快速收敛的情况出现，在算法每迭代次时，对阻尼系数进行一次更新，公式如下所示：

式中：λ′为更新后的阻尼系数；λ为当前的阻尼系数；∂为λ的增长幅度，本文设置为0.01。

输入：用户-用户属性矩阵Q，阻尼系数λ=0.6，吸引度矩阵R和归属度矩阵A，迭代次数m=0，最大迭代次数t=1 000。

输出：F个聚类。

在矩阵Q中利用余弦相似性计算每个用户之间的相似度，得到用户相似度矩阵S；初始吸引度矩阵A和归属度矩阵R为0 矩阵；根据式（4）、式（5）更新矩阵R和A；根据式（6）、式（7）对矩阵R和A进行收敛，m=m+1；ifm=50 then；根据式（8）统计震荡频数e；根据式（9）更新阻尼系数λ；l=0；until达到最大迭代次数或聚类中心连续多次迭代不再发生改变；得到F个用户-用户属性簇并输出。

1.3 LFM 矩阵分解模型

LFM矩阵分解模型[13]本质是利用矩阵分解的方式得到用户与隐含用户特征、物品特征之间的关系，将用户评分矩阵Cmn分解为用户隐特征矩阵Pmf与项目隐特征矩阵Znf，并且两矩阵乘积会尽可能拟合现有评分数据，从而实现对未评分项目的预测。LFM 模型通过式（10）预测用户u对项目i的评分。

式中：Pu为矩阵P中用户u所在行；Zi为矩阵Z中项目i所在行。

最后优化损失函数得到P、Z矩阵：

2 结合改进用户聚类与LFM 模型的推荐算法（I_ALFM）

针对传统Item_CF 算法推荐准确性较低的现象，本文提出了一种结合协同过滤与用户属性聚类的混合推荐算法（I_ALFM）。算法从以下方面进行了改进：首先，算法利用I_CF*预测目标用户对未评分项目的评分；然后，在用户-属性矩阵中利用AP*对用户进行聚类获得目标用户所在簇，并在所在簇内使用LFM 预测目标用户对未评分项目的评分；最后，将2 次评分结果进行线性加权，将加权后的评分值作为目标用户对未评分项目的预测得分。评分线性加权公式如下所示：

本文算法步骤如下：①利用用户-项目评分信息和用户-属性信息构建用户-项目评分矩阵C、用户-属性矩阵Q；②在C中，利用I_CF*算法对目标用户未评分的项目进行预测，得到第一预测得分；③在Q中，利用AP*算法对用户进行聚类，得到目标用户所在簇s，将簇s映射至矩阵Q中，得到簇s对应的用户-项目评分矩阵Q′；④在矩阵Q′中利用LFM 模型对项目进行预测，得到目标用户对未评分项目的第二预测评分；⑤利用式（12），将第一和第二预测评分进行线性加权得到第三预测评分；⑥根据第三预测评分，将预测评分最高的N个项目推荐给用户。

具体流程如图2 所示。

图2 I_ALFM 算法流程图

3 实验结果及对比分析

3.1 数据集和评价指标

本文采用的是由GroupLens 提供的ml-100k 数据集[14]。数据集包含用户与电影共10 万条评分记录，以及用户属性信息。本文将80%的数据作为训练样本、20%的数据作为测试样本。

部分用户-项目评分数据如表1 所示。

表1 用户-项目评分数据

用户-用户属性数据（部分）如表2 所示。原始数据集中，性别列男性用M 表示，女性用F 表示，因聚类需要，将M 替换为1，F 替换为0。

表2 用户-用户属性矩阵数据

本文采用平均绝对误差作为实验的评价指标。平均绝对误差是计算数据中已有的评分和实验预测的评分之差来衡量算法的准确性，其值越小，则算法性能越好，公式如下所示：

3.2 实验结果及分析

实验1：用户属性特征聚类。实验选取性别、年龄和职业作为用户特征进行聚类，共划分为10 个聚类，结果如图3 所示。

图3 聚类结果

实验2：选取最优加权因子。分别取α=0.1，0.2，…，0.9，计算平均绝对误差来确定α和β的最优值。实验将I_ALFM 算法重复运行10 次，取10 次实验结果的平均值作为不同α值对应的平均绝对误差值，实验结果如图4 所示。

图4 权值α对算法平均绝对误差值的影响

由图4 可知，当α=0.4 时，平均绝对误差值为最小，表明此时算法的预测效果达到最优，故本文的最优线性加权因子为α=0.4，β=0.6。

实验3：算法对比实验。为了验证I_ALFM 算法在推荐准确性方面的优势，与基于项目的协同过滤推荐算法（I_CF），隐语义模型推荐算法（LFM）以及结合AP 与LFM 模型的推荐算法（AP_LFM）进行对比实验，结果如图5 所示。

图5 不同近邻数下各个算法的平均绝对误差值比较

由图5 可知，当最近邻数k＞30 时，算法的平均绝对误差值基本上趋于稳定，且在实验范围内的近邻数目下，I_ALFM 算法的平均绝对误差值要低于其他对比算法。当最近邻数为30～50 时，本文算法相比于I_CF，LFM 和AP_LFM 算法，分别降低了3.6%、2.2%和1.6%。

4 结束语

针对传统协同过滤算法推荐质量不足问题，提出了一种混合推荐算法I_ALFM，算法通过线性加权的方式，将协同过滤算法、AP 聚类和隐语义模型的算法相结合。在协同过滤算法中，本文对余弦相似度公式添加3 个影响因子，提高了相似度计算的准确性；在AP 聚类算法中，定义聚类增量率和震荡频数，根据震荡频数的变化动态地获取阻尼系数，提高了收敛效率。实验表明，所提的混合推荐算法能够挖掘隐含数据信息，提高推荐质量。