基于组合优化理论的协同过滤推荐算法

杨丽丽+袁浩浩

摘 要： 针对传统推荐系统中的协同过滤推荐算法无法解决数据间的高度稀疏问题，采用余弦相似性度量运算的物品相似性误差较高，导致系统推荐质量降低，提出基于局部组合优化的协同过滤推荐算法，其改进了物品间相似性的运算，为了解决数据稀疏性问题，选择目标的近邻对象时利用局部优化方法选择推荐群，降低了预测的误差，确保误差值收敛到某固定值，并采用基于内容的方法调整协同过滤预测存在的异常预测结果。实验结果表明，所提算法抑制了数据稀疏性的不利影响，提高了协同过滤预测评分的准确度。

关键词： 局部； 组合优化理论； 协同过滤； 推荐算法； 稀疏问题； 評分精度

中图分类号： TN911.1?34； TP391 文献标识码： A 文章编号： 1004?373X（2018）01?0139?04

Abstract： The collaborative filtering recommended algorithm in the traditional recommended system can′t solve the high sparsity among data. The cosine similarity measurement used to calculate the similarity of objects has big error， which may cause the low recommendation quality of the system. Therefore， a collaborative filtering algorithm based on local combinatorial optimization is proposed to improve the calculation of similarity among items. In order to reduce the data sparsity， the local combinatorial optimization method is adopted to select the recommended group for the object near the selected objective to reduce the prediction error and guarantee the error converging to a fixed value. The content?based method is used to adjust the abnormal prediction results of collaborative filtering prediction. The experimental results show that the algorithm can suppress the adverse effects of data sparsity， and improve the scoring accuracy of collaborative filtering prediction.

Keywords： local； combinatorial optimization theory； collaborative filtering； recommended algorithm； sparse problem； scoring accuracy

0 引 言

随着互联网、信息技术的快速发展，信息呈现爆炸式增长，用户从海量信息中快速、准确检索到有价值资源的难度逐渐增加。因此，个性化推荐系统的发展逐渐引起人们的关注[1]。

个性化推荐系统中应用性最高的推荐技术是协同过滤推荐算法，其基于用户以往的行为偏好，获取用户间的相似度，将同目标用户兴趣最相似的用户作为临近邻居集，分析邻居用户的行为偏好，获取预测目标用户对物品的偏好情况。传统推荐算法无法解决数据间的高度稀疏问题，采用余弦相似性度量运算的物品相似性误差较高，导致预测的误差大幅度增加。

为了解决该问题，本文提出基于局部组合优化的协同过滤推荐算法，以提高协同过滤预测评分的准确度。

1 基于组合优化的协同过滤推荐算法

1.1 问题的提出

数据稀疏性问题广泛存在于个性化推荐系统中，电子商务网站中包含了海量的用户和商品，用户无法对全部的物品实施准确评价。若采用传统协同过滤算法，通过相似性度量获取物品间的相似性[2]，能够完成用户对物品偏好度的评分，但是该种算法会受到高度稀疏数据集的干扰，使得推荐质量大大降低。针对传统算法无法处理数据稀疏性问题，可采用改进相似度运算方法对其实施改进。相似性的两个改进方法，公式如下：

[sim（i，j）=min（Ui?Uj，γ）γ×cos（i，j）] （1）

[sim（i，j）=max（Ui?Uj，γ）γ×cos（i，j）] （2）

式中：[γ]参数用于描述调节参数，基于实际数据集明确该参数的取值范围；[cos（i，j）]是余弦相似性，对向量而言，式（1），式（2）中主要为物品间关系，可转化为向量表示。

采用式（1）和式（2）描述的两种改进相似性运算方法可提高评分预测的准确度，然而在数据高度稀疏时，这两种改进算法的优化效果不明显。因此，面向上述分析问题，本文基于局部组合优化的协同过滤推荐算法，先对项目间的相似性运算实施优化，再采用局部优化方法选择对象当成推荐群，并通过基于内容的方法调整协同过滤预测评分包含的部分异常[3]，提升推荐系统的质量。

1.2 优化物品间相似性运算公式

如果数据存在高度稀疏性特征，在传统协同过滤算法对物品相似性实施运算的过程中，两个物品被同时评分的用户数量大大降低，使得物品相似性运算存在显著的随机特征。为了减少该种随机特征产生的干扰，本文采用物品的评分相似性同物品的特征属性相似性的线性加权方法运算物品间的相似性，如式（3）所示：endprint

[sim′（i，j）=θsim（i，j）+（1-θ）simT（i，j）] （3）

式中：[θ]是常量；[simT（i，j）]用于描述物品的特征属性相似性。

1.3 局部优化选择近邻对象

传统协同过滤过程是在全部推荐物品群内，采用[k]个相似性最高的物品，若采用的相邻个数[k]过高，则会使得推荐结果精度降低，无法提高推荐系统的质量。本文提出的基于局部优化选择的组合推荐算法，设置最小阈值[δ，]通过局部优化方法选择预测目标[4]，确保近邻集中物品数量最小化。采取的局部优化运算公式如下：

[sgi，j*sim′（i，j）>δ] （4）

式中：[δ]是常量，设置的相似度阈值如果过高，会使得覆盖率过低；[sgij]描述重要性权重因子，其靠近存在更多一致评分物品的对等者。真实状态中出现两个用户评分混合的现象较少，为了解决相似性度量存在的随机特征的不利影响，用[I=Ii?Ij]描述物品[Ii]以及[Ij]被共同评分的用户集，用[λ]描述阈值，采用式（5）对比分析阈值同项目[Ii]以及[Ij]被共同评分的用户数[ni，j]：

[sgi，j=ni，jλ，ni，j<λ1，其他] （5）

式中：[ni，j=I]，因为当共同评分物品数量高于50时，预测的误差向平稳趋势靠近。

该方法通过局部的相似性使得总体预测误差MAE大大降低，并且确保预测误差收敛于某固定值。

1.4 基于内容调整异常预测评分

系统过滤预测评分时，如果数据呈现高度稀疏状态，则将导致用户对项目的评分数大大降低，出现预测评分异常，导致系统预测误差的大幅度上升[5]。因此，本文通过基于内容的方法对异常预测评分进行调整，详细的过程如下：

1） 基于内容的预测过程

基于内容的预测方法采用式（6）获取项目[i]对于物品特征[t]的权重：

[wi，t=1，项目i有属性特征t0，项目i没有属性特征t] （6）

采用式（7），用0～1的值描述用户对于项目的某种物品特征的兴趣度：

[wu，t=r（t）tar（u）tb*11+ct] （7）

式中：[r（t）]是用户[u]对具有特征[t]的全部项目总的评分；[r（u）]是用户[u]全部评分的总和；[ta]表示用户[u]对存在特征[t]的项目进行评价的数量；[tb]表示用户[u]评价的全部项目数；[wu，t]表示用户[u]对物品特征[t]的感兴趣度；约束因子[11+ct]用于降低热门项目特征的权重[6]，[ct]用于描述特征[t]在全部特征中所占的权重。

式（6）能得到各项目的特征权重向量[V，]式（7）能够运算各用户的历史兴趣特征权重，得到用户特征权重向量[U。]则依据内容的评分预测表达式为：

[R′i，j=hj*5*sim（ui，vj）] （8）

式中：[sim（ui，vj）]是采用余弦相似性公式運算得到的；[hj]表示当前项目[j]被评分的用户数的权重。根据式（9）计算[hj，]从而得到基于内容预测的准确度。

[hj=njη，nj>η1，其他] （9）

式中：[η]是常量；[nj]用于描述项目[j]被评分的用户数量。

2） 调整评分预测方法

协同过滤算法自身存在的缺陷，会使得用户对项目的评分数量较少，预测的分数会大大减小，容易产生异常的预测评分现象[7]。面对该现象，本文提出新的评分预测表达式：

[Ru，t=σ*R′u，n+（1-σ）Ru，n，Ru，n<βRt+n∈S（Jj）sim（t，n）*（Ru，n-Rn）n∈S（Jj）sim（t，n），others] （10）

分析上述描述的协同过滤预测评分过程可得，协同过滤预测获取的异常结果为[Ru，n<β，][Ru，n]为特征值，通过基于内容的预测[R′u，n]对该异常结果实施调整，其中[β]是常量。

3） 拉普拉斯平滑方法

概率统计过程中的拉普拉斯平滑也就是加平滑，用于处理数学系数在统计领域中的零概率问题。数据集中包括小规模的项目特征，基于项目特征矩阵进行特征的余弦相似性运算时，会产生大量的零值关系，此时基于相似性属性，能够看出两种项目间相互独立。但是实际预测过程中，无法获取两个项目间的不确定关系[8]。因此，采用拉普拉斯平滑方法进行改进，项目特征属性运算相似性表达式为：

[simt（i，j）=ti?tj+1ti?tj+k] （11）

式中：[ti，][tj]是用于描述项目[i，j]的特征向量；[k]是相关联项目的数量，本文设置其值是10。

基于式（11）可以看出，在拉普拉斯方法运算原始项目属性矩阵过程中，无需进行繁琐的操作，就能够高效率地运算出项目间的相似性，具有较高的运算效率。

2 实验结果与分析

2.1 实验数据

本文实验分析的数据集是MovieLens，将该数据集中的832个用户对1 489部电影的8 000条评分记录作为实验数据集。同时将实验数据集中的75%当成训练集，其余的25%当成测试集。实验数据集内存在16种全部电影的特征输入，如爱情、剧情、恐怖等。通过预测评分和用户实际评分间的偏差，也就是通过平均绝对误差MAE（Mean Absolute Error）对本文算法预测评分的准确度进行检测。

2.2 实验结果分析

2.2.1 参数[β]的最优取值

过高稀疏性的数据会导致训练集内用户评分的项目记录过低，存在共同评分项目的用户数十分少，用户间的相似度很小，使得协同过滤预测分数中存在异常评分。本文算法采用基于内容的方法对异常评分进行调整，实验设置本文算法的预测评分score<[β]时产生异常评分。在数据集MovieLens中，1～5分用于描述不同用户可选择的评分区域，1用于描述很差，5用于描述很好。用户采用差异分数描述自身对已看电影的偏好程度。实验设置[β]取[0.0，0.20，0.40，0.60，0.80，0.85，0.90，1.10，1.30，1.50]，设置邻居个数为[N=20，]实验结果用图1描述。endprint

分析图1可得，如果[β]值是0.9，则当预测评分低于0.9时，采用基于内容的推荐法调整异常预测评分，本文算法可有效减少预测的误差。

2.2.2 异常预测评分结果的数目

实验采用本文算法预测不同的测试数据集的评分score，其中，[k]为预测用户相关系数，异常预测评分结果（score<0.9与score≤0）的数量，用表1和图2描述。

图2 5个MovieLens 100K的数据集内异常的预测评分结果个数

Fig. 2 Number of abnormal prediction scores of 100K

5 MovieLens datasets

分析表1和图2能够得出，本文算法预测评分低于0.9的异常结果在总体检测过程中存在的平均次数是97.2次，预测评分不高于0的异常结果的平均出现次数是61.6次。说明本文算法可有效预测出异常评分结果，为后续的预测评分优化提供有利基础，提升总体协同过滤推荐的准确度。

2.2.3 不同算法的MAE值对比

实验对比分析本文算法、线性组合LCCF算法和填充伪评分CBCF算法的MAE值[9]，结果用表2和图3描述。分析表2和图3可得，当[N]值低于10时，各种算法的预测质量将大大降低；而当[N]值高于10时，各算法的预测质量逐步提升。但是本文算法的MAE值低于其他两种算法，可有效增强预测的精度，降低数据稀疏性产生的不利干扰，并且随着[N]值的不断提升，本文算法的预测准确度趋于稳定。

3 结 论

本文针对传统协同过滤推荐算法无法解决数据间的高度稀疏问题，存在预测评分精度低的问题，提出基于局部组合优化的协同过滤推荐算法，实现协同过滤预测评分精度的提高。

参考文献

[1] 田保军，胡培培，杜晓娟，等.Hadoop下基于聚类协同过滤推荐算法优化的研究[J].计算机工程与科学，2016，38（8）：1615?1624.

TIAN Baojun， HU Peipei， DU Xiaojuan， et al. Optimization of the collaborative filtering recommendation algorithm based on clustering under Hadoop [J]. Computer engineering and science， 2016， 38（8）： 1615?1624.

[2] 张学钱，林世平，郭昆.协同过滤推荐算法对比分析与优化应用[J].计算机系统应用，2015，24（5）：100?105.

ZHANG Xueqian， LIN Shiping， GUO Kun. Collaborative filte?ring recommendation algorithm analysis and optimization applications [J]. Computer systems & applications， 2015， 24（5）： 100?105.

[3] 祝晓斌，蔡强，白璐，等.一种基于标签和协同过滤的并行推荐算法[J].高技术通讯，2015，25（3）：307?312.

ZHU Xiaobin， CAI Qiang， BAI Lu， et al. A parallel recommendation algorithm based on tagging and collaborative filte?ring [J]. Chinese high technology letters， 2015， 25（3）： 307?312.

[4] 刘涛.基于二叉树偏码匿名乱序的云平台协同计算研究[J].科技通报，2016，32（7）：167?171.

LIU Tao. Cloud platform collaborative computing research based on binary tree partial code anonymous out?of?order [J]. Bulletin of science and technology， 2016， 32（7）： 167?171.

[5] 王兴茂，张兴明，邬江兴.基于一跳信任模型的协同过滤推荐算法[J].通信学报，2015（6）：193?200.

WANG Xingmao， ZHANG Xingming， WU Jiangxing. Collabo?rative filtering recommendation algorithm based on one?jump trust model [J]. Journal on communications， 2015（6）： 193?200.

[6] 马胡双，石永革，高胜保.基于特征增益与多级优化的协同过滤个性化推荐算法[J].科学技术与工程，2016，16（21）：272?277.

MA Hushuang， SHI Yongge， GAO Shengbao. A recommendation algorithm based on collaborative filtering by feature augmentation and cascade tactics [J]. Science technology and engineering， 2016， 16（21）： 272?277.

[7] 周国强，金礼仁，张文聪，等.基于用户影响力和个性的协同过滤推荐算法[J].计算机应用，2016，36（z1）：63?66.

ZHOU Guoqiang， JIN Liren， ZHANG Wencong， et al. Colla?borative filtering recommendation algorithm based on user inf?luence [J]. Journal of computer applications， 2016， 36（z1）： 63?66.

[8] WANG Jianian， XIAN Xiaobing. Multi?node cooperative transmission of data collection protocols for wireless sensor networks [J]. Computer simulation， 2014， 31（9）： 339?342.

[9] 赵伟，李俊锋，韩英，等.Hadoop云平台下的基于用户协同过滤算法研究[J].计算机测量与控制，2015，23（6）：2082?2085.

ZHAO Wei， LI Junfeng， HAN Ying， et al. Research on user?based collaborative filtering algorithm on Hadoop platform [J]. Computer measurement & control， 2015， 23（6）： 2082?2085.