近邻的关联加权SlopeOne协同过滤算法

王竹婷，夏竹青，周艳玲

(合肥学院 计算机科学与技术系，合肥 230601)

近邻的关联加权SlopeOne协同过滤算法

王竹婷，夏竹青，周艳玲

(合肥学院 计算机科学与技术系，合肥 230601)

协同过滤是目前电子商务推荐系统中应用最为广泛的一类推荐算法。随着系统用户和项目数量的急剧增加，传统的协同过滤算法已经很难满足各类系统的需求。为提高算法处理大规模数据的能力，重点研究SlopeOne协同过滤推荐算法。将其与关联规则挖掘相结合，并选择近邻用户数据对目标用户的未知评分项进行评分预测，在movielens数据集上的测试结果表明，改进后的算法能够较为显著的提高推荐质量，适用于处理大规模数据。

协同过滤；SlopeOne; 关联规则

电子商务个性化推荐系统可以根据用户的网上浏览、购买或评分信息分析用户的兴趣爱好，并快速、准确的为用户提供个性化产品推荐。该系统一方面可以帮助在线商品销售商快速、准确锁定目标用户，增加线上商品的销售量；另一方面帮助用户解决因信息过载而造成的困扰，提高在线服务质量，增加客户的满意度。而协同过滤技术作为推荐系统中最为关键的技术之一，在个性化推荐系统中得到了广泛的应用。[1]

协同过滤算法通常分为基于模型和基于近邻的两大类，基于模型的协同过滤采用机器学习中的相关模型通过训练集数据产生预测模块，再通过该模块预测用户感兴趣的项目。[2]基于近邻的协同过滤又可细分为基于用户和基于项目的两类，两者都基于一个非常简单的思想，即兴趣相投的用户有较大的可能会喜爱同类型的项目，或相似的项目被同一用户同时喜爱的几率是比较高的。[3]该算法的关键步骤就是通过系统中的历史评分数据计算不同用户或项目之间的相似性，再根据近邻用户或目标用户已有的评分记录预测其他项目的评分，选择评分值高的推荐给目标用户。

SlopeOne[4]是Daniel Lemire教授在2005年提出的一种非常简单、高效的基于项目的协同过滤算法，[5]该算法依然是通过现有项目的评分值产生未知项目的预测评分，但无需计算项目之间的相似度，而是通过统计不同项目间的平均评分偏差，采用一元线性回归模型，根据目标用户现有评分值进行未知项目预测。该算法不仅运算速度极快，而且预测结果非常接近目前较为先进的高精度算法。

本文认为SlopeOne算法利用所有的历史评分数据进行预测，难免会引入噪声数据，从而增加预测产生的误差，拟将其与基于用户的近邻算法相结合，采用近邻用户数据进行评分预测；其次，经过实验测试得出在SlopeOne的三种算法模型中，加权SlopeOne算法的预测效果最优，但其权值选择过于简单，加权改进效果并不十分理想，本文认为关联规则挖掘中的置信度更能反映两项目间的关联关系，以置信度为权值则更为合适。实验结果证明，本文提出的改进算法可以得到更为精确的预测结果。

1 问题描述和相关工作

1.1问题定义假设一个推荐系统中有m个用户和n个推荐项目，用户集合为U={U1,U2,…,Um}，项

目集合为I={I1,I2,…,In}，系统中的历史评分数据采用用户-项目评分矩阵表示，如表1所示，Rij为用户i对项目j的评分值。如果用户未对某一项目评分，则用0表示。实际推荐系统中由于用户和项目数量十分庞大，而每位用户评分过的项目数量又非常有限，用户-项目矩阵中存在大量空缺值，协同过滤算法的任务是计算出空缺项的预测评分，以此为依据预测用户的喜好程度进行项目推荐。

表1 用户-项目评分矩阵

1.2SlopeOne算法SlopeOne算法分为三个步骤：首先利用历史评分数据，如上表所示，构建用户-项目矩阵；在用户-项目矩阵基础上，统计每两个项目被同一用户共同评分的次数和全部评分差值的总和，计算项目评分偏差的均值；最后根据每位用户现有评分值和项目评分偏差，利用一元线性回归模型，预测未知项目评分值。Daniel Lemire教授在给出SlopeOne基本算法时，同时给出了其两种改进型算法：加权SlopeOne和双极SlopeOne，算法介绍如下。

(1)SlopeOne。SlopeOne算法属于基于项目的评分预测算法，其采用一元线性回归模型f(v)=v+b预测评分，b为用户对两个项目评分偏差的均值，例如有两个用户U1和U2，同时给项目Ii评分，U1给了1分，U2给了2分，同时U1又对项目Ij评分为1.5，那么此时可以预测，用户U2给项目Ij的评分为2+0.5=2.5，其中2为已知用户U2对项目Ii的评分，b=1.5-1=0.5为项目Ii和项目Ij的评分偏差。当系统中某两个项目有多个用户同时给过评分时，b则为多个用户评分偏差的均值，具体算法细节如下所述。

对于给定的训练集χ，其中的任意两个项目Ii和Ij，找出共同评分过该两个项目的用户集Sij(χ)，则评分偏差均值devij计算方法如下，card(Sij(χ))为集合Sij(χ)中用户数量。

(1)

根据上述一元回归模型，Rai+devij为用户Ua对项目Ij的预测评分，当且仅当用户Ua只对项目Ii进行了评分。一般情况下，用户已有的评分项不只一项，那么此时，就要将多个预测结果的均值作为最终的预测评分，计算方法如下所示，Ra表示所有用户Ua评分过的项目。

(2)

(2)加权SlopeOne。直观上讲，两个项目同时被用户评分的次数越多，那么以这两个项目的评分偏差预测评分的结果越准确，加权SlopeOne则基于这样的思想，为每项预测评分增加了权值cij，cij即共同评分过项目Ii和Ij的用户数。

(3)

(4)

2 关联加权的SlopeOne

在加权SlopeOne算法中为每一项评分预测结果分配不同的权值是非常有必要的。因为，SlopeOne算法实则是根据不同项目评分之间的关联性进行预测，不同项目之间的关联强度也有所差别，简单的采用共同评分项的数量作为权值去衡量这种关联性虽然较基本模型有所改进，但这种衡量方式难免有失偏颇。本文认为将关联规则分析引入该模型用于改善加权系数应该能够得到更为准确的预测效果。

2.1关联规则关联规则最早被零售行业用于进行购物篮分析，从中找出哪些商品被用户同时购买的可能性较大，将其捆绑销售可以极大的增加商品的销售量。[6]本文采用关联规则基本原理，针对待推荐项目挖掘一阶和二阶频繁项集，并计算所有二阶频繁项集的置信度，以置信度为加权SlopeOne算法的权值，计算方法如下。

(5)

公式(5)中，P(Ii)表示项目Ii出现的概率，也叫项目的Ii支持度，当支持度高于事先设定的阈值时，我们称该项目为一阶频繁项集；P(Ii∩Ij)为项目Ii和Ij同时出现的概率，也称为该二阶项集的支持度，同样当该支持度高于给定的阈值时，称之为二阶频繁项集。confij为项目Ii对项目Ij的置信度，即项目Ii出现时项目Ij同时出现的概率。

关联规则原理中的支持度和置信度往往能够较为准确的反映不同项目之间的关联程度，在使用SlopeOne算法进行评分预测之前，首先进行关联规则挖掘，可除去关联性较弱的噪声数据，并采用置信度confij取代公式(3)中的权值cij，以项目间的关联强度为权值，预测的准确性会比原方法有所提高。

2.2用户相似度SlopeOne算法将所有用户的评分不经过任何筛选全部用于做预测难免会增加其预测误差。本文将借鉴基于用户的协同过滤算法，首先计算用户相似度，再选择近邻用户的评分数据进行预测。传统的用户相似性度量方法主要包括Pearson相关系数和余弦相似性，考虑到Pearson相关系数要求两个向量之间必须线性相关，而实际两用户的评分数据很难保证线性相关；余弦相似性则通过衡量两用户评分向量的夹角余弦作为用户相似度值，但未考虑到不同用户的评分尺度问题。因此，本文采用修正的余弦相似性，计算方法如下。

(6)

2.3基于近邻的关联加权SlopeOne算法公式(6)可以通过用户评分数据计算出目标用户与其他所有用户间的相似度值，选择一个合适的阈值，将相似度大于该阈值的用户作为近邻用户，再采用近邻用户已有项目的评分数据通过关联加权SlopeOne算法预测目标用户的未知评分项。

3 实验结果

3.1数据集实验采用Minnesota大学GroupLens项目研究小组提供的movielens数据集，选取其中的m100k为本实验的测试数据集，该数据集包含943位用户对1682部电影的100 000个评分项，评分值在1-5之间，其中1为用户给予的最低评分，表示用户非常不喜欢该电影，5为最高评分，表示用户非常喜欢该电影。每位用户至少有20部电影的评分记录，除此之外，还包括一些简单的用户信息，如年龄、性别、职业等。本次实验只需处理用户编号、电影编号和评分值这三部分信息。采用五折交叉法对改进前后的算法进行对比分析。

3.2评价指标本文拟采用平均绝对偏差(Mean Absolute Error, MAE)为评估算法推荐效果优劣的指标，其计算方法如公式(7)所示，pij是由训练集数据计算产生的预测评分，qij是测试集中用户的实际评分，Ni是测试集中所提供的用户i的评分数量，MAEi是用户i对Ni个项目预测评分的平均绝对偏差，公式(8)中M是全体用户总数，MAE则是全体用户的平均绝对偏差。该公式就是通过计算用户预测评分与实际评分的差值来评价算法推荐效果的。如果MAE值越小，表明算法的预测结果越接近实际评分，推荐效果越理想。

(7)

(8)

3.3实验结果及分析正如本文第一部分所介绍，Daniel Lemire教授为SlopeOne算法设计了三种模型，分别为SlopeOne、加权SlopeOne和双极加权SlopeOne。我们首先设计实验验证该三种算法在movielens数据集上的测试结果。实验采用5折交叉法，即将数据集随机分成5等份，选择其中的4份做训练集、1

份做测试集，执行5次，将5次实验得到的平均MAE值作为算法的最终测试结果。如表2所示。无论是单次测试结果还是平均值，都表明加权SlopeOne算法的预测结果与实际值最接近。

表2 三种SlopeOne模型的测试结果

为验证本文所提出的改进策略具有的有效性，在相同的数据集下，将改进后的基于近邻的关联加权SlopeOne与加权SlopeOne进行对比分析。由于传统的加权SlopeOne算法在进行预测评分时选用用户共同评分的项目数量作为权值，方法略显简单。本文引入关联规则挖掘中的置信度作为权值，更能够准确

的反映出不同项目间的关联关系，而基于余弦相似度的近邻用户的选择可以过滤掉一部分噪声数据，进一步提高预测的的精确度。如表3所示，实验测试结果表明关联加权和基于近邻的改进策略均可以一定程度上提高协同过滤算法预测的准确性。

表3 本文算法与加权SlopeOne测试结果

4 结束语

SlopeOne算法是一种基于项目的协同过滤算法，其突出特点是算法简单，计算速度快，而且相比传统的推荐协同过滤算法，该算法的推荐质量较高，适用于进行大规模数据处理，尤其当推荐系统中用户数量远远大于项目数量时，无需计算用户间的相似度，实际应用时可以较大程度上提高算法的推荐速度。本文首先介绍了3种SlopeOne算法模型，并通过真实数据集分别测试这3种模型，得出加权SlopeOne算法的推荐精度最高，分析加权SlopeOne存在的不足之处，引入关联规则加以改进，同时，参考基于用户的协同过滤算法，选择近邻用户数据进行预测评分。实验结果证明，两种改进策略均能一定程度上提高算法的推荐效果。在实际推荐系统中，我们建议当项目数量远大于用户数量时，采用基于近邻的加权SlopeOne算法，用户相似度和关联规则的提取可以离线完成，无需消耗在线资源；当用户数量远大于项目数量时，则无需选择近邻用户，直接采用关联加权SlopeOne即可得到较为满意的推荐效果。

[1] Adomavicius G，Tuzhilin A. Toward the Next Gneration of Recommender Systems: a Survey of the State-of-the-art and Possible Extensions[J]. IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

[2] Hofmann T.Latent Semantic Models for Collaborative Filtering[J]. ACM Transactions on Information Systems,2004,22(1):89-115.

[3] Choi K, Suh Y.A New Similarity Function for Selecting Neighbors for Each Target Item Incollaborative Filtering[J]. Knowledge-Based Systems, 2013,37 :146-153.

[4] Lemire D，Maclachlan A.Slope One Predictors for Online Rating-Based Collaborative Filtering[C]// SIAM International Conference on Data Mining,2005:471-480.

[5] 张玉连; 郇思思; 梁顺攀;融合机器学习的加权Slope One算法[J]. 小型微型计算机系统,2016,6(6):1174-1178.

[6] Leung C W, Chan S C,Chung F .An Empirical Study of a Cross-level Association Rule Mining Approach to Cold-start Recommendations[J]. Knowledge-Based Systems,2008,21(7):515-529.

AnImprovedSlopeOneCollaborativeFilteringRecommendationAlgorithmBasedonNearNeighborsandAssociationRules

WANG Zhu-ting，XIA Zhu-qing，ZHOU Yan-ling

(Department of Computer Science and Technology ,Hefei University, Hefei 230601, China)

Collaborative filtering is one of the most widely used Recommendation algorithms in E-commerce Recommender Systems. As the number of users and projects increase rapidly, the traditional collaborative filtering algorithm has been difficult to meet the needs of various systems. To improve the ability of processing large-scale data, we pay more attention on study of SlopeOne collaborative filtering recommendation algorithm. Combining SlopeOne with association rules, and then selecting the nearest neighbor data to predict the unknown scoring items of target users. The test of the results on the movielens dataset show that the improved algorithm can significantly improve the recommendation quality, and is suitable for dealing with large-scale data.

collaborative filtering; SlopeOne; association rules

2017-06-26

2017-09-21

安徽省教育厅自然科学资助项目(KJ2016A609)，安徽省创新创业训练计划项目(201511059266)，合肥学院科研发展基金资助项目(14KY11ZR)，合肥学院重点建设学科(2016xk05)资助。

王竹婷(1984— )，女，安徽马鞍山人，合肥学院计算机科学与技术系助理实验师。

TP301.6

A

2096-2371(2017)05-0089-04

[责任编辑：张永军]