引用本文
盈艳, 曹妍, 牟向伟. 基于项目评分预测的混合式协同过滤推荐* . 2015, 31(6): 27-32
Ying Yan, Cao Yan, Mu Xiangwei. A Hybrid Collaborative Filtering Recommender Based on Item Rating Prediction. New Technology of Library and Information Service, 2015, 31(6): 27-32  
Permissions
Copyright©2015, 《现代图书情报技术》编辑部
《现代图书情报技术》编辑部
基于项目评分预测的混合式协同过滤推荐*
盈艳, 曹妍, 牟向伟
大连海事大学交通运输管理学院 大连 116000
曹妍, ORCID: 0000-0002-8383-083X, E-mail:caoyan@dlmu.edu.cn。

作者简介：曹妍: 提出研究方向, 设计研究方法; 盈艳: 设计算法, 实验及分析, 论文撰写; 牟向伟: 收集数据, 论文修订。

基金:*本文系中国博士后科学基金资助项目“大数据环境下散杂货多式联运领域知识发现方法研究”(项目编号:2014M551063)、省社科联2014年度辽宁经济社会发展立项课题“辽宁冷链物流产业建设与发展研究”(项目编号:2014lslktzdian-11)和辽宁省教育厅科学技术研究项目“大数据环境下散杂货多式联运综合领域知识的表达与共享”(项目编号:L2014203)的研究成果之一
摘要
目的改进传统协同过滤推荐算法以缓解其存在的数据稀疏性问题, 进而提高评分预测的精度。方法提出整合K-means聚类和Slope One算法的混合式协同过滤推荐框架和KSUBCF算法。利用基于K-means聚类的Slope One算法预测填充矩阵中必要的未评分项, 利用基于用户的协同过滤推荐算法实现推荐。结果实验结果表明, 随着邻居数目的增加, 该算法比原Slope One算法在MAE(平均绝对误差)值上有8.8%-21%的下降, RMSE(均方根误差)值有17%-28.1%的下降。【局限】该算法仍然依赖用户-项目评分数据矩阵。结论该算法与其他传统协同过滤算法相比, MAE值分别有10%和43.8%的下降, RMSE值也有20.1%和37.4%的下降, 说明本文方法可以提高预测精度。
关键词: 混合式协同过滤; 项目评分; Slope One; 预测; MAE
中图分类号:G202
A Hybrid Collaborative Filtering Recommender Based on Item Rating Prediction
Ying Yan, Cao Yan, Mu Xiangwei
Transportation Management College, Dalian Maritime University, Dalian 116000, China
Abstract

[Objective] By improving the traditional collaborative filtering recommendation algorithm to alleviate the existing data sparseness problem, thus enhance the prediction precision. [Methods] This paper proposes a hybrid collaborative filtering recommender framework and KSUBCF algorithm integrated K-means clustering and Slope One algorithm. Firstly, this algorithm uses the Slope One algorithm based on K-means clustering to predict item default rating. And then, to implement recommendation by the collaborative filtering recommendation algorithm based on users. [Results] The experimental results show that with the increase of neighbors numbers, this algorithm is better than the original Slope One algorithm, which MAE value is reduced by 8.8% to 21% and RMSE value is reduced by 17% to 28.1%. [Limitations] This algorithm still relies on user-project score data matrix. [Conclusions] Compared with other traditional collaborative filtering algorithms, the decreases of the MAE value are 10% and 43.8% respectively and the decreases of the RMSE value are 20.1% and 37.4%. The proposed method can improve the prediction precision.

Keyword: Hybrid collaborative; filtering; Item rating; Slope One prediction; MAE
1 引言

近年来, 推荐系统已经被广泛应用到电子商务(如Amazon, 当当网等)和一些社会化站点(包括音乐, 电影和图书分享, 如豆瓣, Flickr等)。这也进一步说明在Web2.0环境下, 面对海量数据, 用户需要更加智能的, 能够将无用的信息进行过滤, 只留下他们需求信息的发现机制。作为传统推荐技术的一种, 协同过滤算法因其简单高效的特点, 在应用中获得更多青睐, 同时也得到许多研究者的关注。然而, 在实际系统中存在用户评分数据过于稀疏的问题, 很多研究人员针对该问题提出了改善方法, 主要包括: 设定缺省值、降维、图论方法、奇异值分解等[1]。Huang等[2]提出将评分矩阵转化为用户和物品的双向图, 并且使用一种称为扩展激活的特殊图搜索方法分析图。这种基于间接关系的方法在评分矩阵稀疏时能提高推荐质量, 但是当评分矩阵达到某种密度之后相比标准算法推荐质量也会有所下降。王洋等[3]提出基于径向基函数(RBF)神经网络的解决方法, 采用一种动态自适应的方法选择隐含层中心节点, 从而设计隐含层构建RBF神经网络用来预测评分矩阵中的空缺值填充到原始矩阵, 利用填充的矩阵计算用户相似度, 但是该方法需要建立复杂的神经网络模型。Zhang等[4]利用预测公式通过加入适当的权重和递归次数预测矩阵中的空缺值, 其中最重要的参数就是递归次数, 随着递归次数的增加计算代价也随之增加。

以上方法虽然在一定程度上缓解了稀疏性问题, 但是也存在其他问题, 主要表现在: 算法过程复杂实现困难, 增加资源消耗等。本文提出基于项目评分预测的混合式协同过滤推荐算法不仅能缓解稀疏性问题, 而且简单易实现。该方法整合K-means聚类和Slope One[5]两种算法, 试图有效缓解评分矩阵稀疏性问题。

2 相关研究

本研究是基于协同过滤推荐算法和Slope One推荐算法的相关研究成果, 已有研究成果总结如下。

2.1 协同过滤推荐技术

协同过滤推荐技术主要包括基于内存和基于模型两大类。其中, 基于内存的推荐包括基于用户的推荐和基于项目的推荐两种方法, 其核心思想都是根据用户评分矩阵计算用户间或项目间的相似度从而实现推荐。协同过滤推荐技术主要包括以下三个步骤:

(1) 构建用户-项目评分矩阵。收集用户在进行浏览或购买行为后的评价信息, 并对数据进行清洗、转换和录入后得到用户-项目评分矩阵, 如表1所示:

表1 用户-项目评分矩阵

其中, Rm, i表示用户Um对项目Ii的评分数据。Rm, i的取值范围可以是[1, 5], 也可以是其他范围。比如: Jester网的评分数据范围是[-10, 10]。通常用来表示用户对项目的喜好程度, 如果用户没有对项目进行评分, 则用空值或者零值表示。

(2) 寻找用户最近邻居集。采用相似性度量方法计算用户间相似度, 协同过滤推荐算法中度量相似度的方法有很多, 比较常用的有三种[6, 7, 8]: 余弦相似性、修正的余弦相似性和相关相似性。在协同过滤算法中针对不同的研究对象各种相似性度量会有不同的表现, 相关相似性度量方法适合User-based的协同过滤算法, 而修正的余弦相似性度量方法适合Item-based的协同过滤算法。总之, 这两种度量方法具有良好的推荐性能。根据用户间相似度矩阵选择目标用户的K个最相近邻居作为实现预测的集合, 或设定一个相似度阈值, 选择超过阈值的用户作为目标用户的邻居。

(3) 产生推荐。获得目标用户的最近邻居集合后, 将相似度作为权重可以得到目标用户对未评分项目的预测, 形成Top-N列表推荐给用户。

2.2 Slope One算法

Slope One推荐算法是由Lemire等[9]提出的一个Item-based推荐算法。该推荐算法认为, 平均值可以调和不同用户对物品的评分差异, 而且虽然是协同过滤算法的一种, 但不用计算用户间或项目间的相似度。Slope One算法因其简单高效易实现的特点被应用到许多推荐系统中, 如: Hitflip DVD推荐系统, inDiscover MP3推荐系统, Value Investing News 股票新闻网站, AllTheBests 购物推荐等[10]。Slope One算法通过两个步骤实现预测:

(1) 给出一个训练集和任意两个项目Ii和Ij, Ui, j表示同时评价过项目Ii和Ij的用户集合, 则项目Ii和Ij评分的平均偏差如下[11]:

(1)

其中, rx, i表示用户X对项目i的评分, 表示集合 中元素的个数。

(2) 目标用户u对目标项目i的预测评分如下:

(2)

其中, 表示与项目i同时被评价过的项目集合, 但该集合不包括项目i且 。

另外, Slope One算法一般有两种实现方式: 加权Slope One算法和双极Slope One算法。虽然该方法简单实用但是仍存在一些缺点: 忽略了用户间和项目间的相似性, 而且在数据稀疏时, 推荐效果不如传统协同过滤算法好。所以本文将整合K-means聚类算法和Slope One算法预测填充稀疏的评分矩阵, 再用协同过滤技术实现推荐。Wang等[12]提出将Slope One预测算法和基于用户的协同过滤算法合并, 但是没有考虑到项目间的相似性, 即使两用户很相似但如果他们分别喜欢不同类型的项目, 那么推荐效果也不乐观。因此, 将项目用K-means算法聚类后对每一类进行预测填充, 再结合协同过滤算法能够提高推荐的精确度。

3 混合式协同过滤推荐框架和KSUBCF算法
3.1 混合式协同过滤推荐框架

整合K-means聚类和Slope One算法的混合式协同过滤框架如图1所示。

图1 整合K-means聚类和Slope One算法的混合式协同过滤框架

该框架可大致分为上下两部分, 上面一部分是将整理好的用户-项目评分数据集进行基于欧式距离度量的K-means项目聚类, 从而得到k类用户-项目评分数据子集。下面一部分又分为两步, 第一步将各个评分数据子集中的未评分项采用Slope One算法进行预测填充, 组合成新的不再极度稀疏的用户-项目评分矩阵; 第二步就是结合基于用户的协同过滤推荐算法预测目标用户对测试集中目标项目的评分, 产生Top-N列表推荐给用户。

3.2 KSUBCF算法设计

根据以上分析并结合混合式协同过滤框架, 提出一种整合K-means聚类和Slope One算法的协同过滤算法KSUBCF。其具体实现步骤如下:

(1) K-means项目聚类。从用户-项目评分矩阵R（mxn）中抽取用户集合U、项目集合I, 用K-means聚类算法进行项目聚类, 但是由于用户评分矩阵是一个稀疏矩阵有许多未评分项, 计算两项目间距离时要求用户对这两个项目均有评分, 因此聚类过程中的欧氏距离度量公式需要改进, 即:

(3)

其中, 集合 , Ii, j表示同一用户对两个项目Ii和Ij的评分都不为0, value表示评分值, k指的是矩阵中的行, 即用户, 表示集合 所包含的元素数。

(2) 使用Slope One算法预测填充未评分项。由步骤(1)得到k类用户-项目评分数据子集, 对每一类执行以下操作:

For each 用户

For each 项目

If ( Ij not rated by ui)

用Slope One算法预测项目Ij的评分值Pi, j;

End if

End for

End for

(3) 将填充后的每一类按照原矩阵的列顺序组合成新的用户-项目评分矩阵 , 该矩阵存在以下特征, 即用户i对项目j的评分Ri, j如下:

(4)

ri, j: if user i rated item j

pi, j: if user i not rated item j

(4) 计算用户间的相似度。根据新的用户-项目评分矩阵 计算得到用户相似度矩阵, 执行如下操作:

For each用户uiU

For each用户ujU

用Pearson公式计算用户间相似度Sim(ui, uj), 得到用户

相似度矩阵S(m× m);

End for

End for

(5) 对目标用户u的邻居集合c中的元素按从大到小的顺序排序, 选择前K个组成目标用户的最近邻居集Neighboru。

(6) 根据协同过滤算法的评分预测规则预测用户对目标项目集的评分从而产生推荐。用户u对项目i的评分Pu, i可以通过最近邻居集合 得到, 计算方法如下:

(5)

其中, 是用户u对项目评分的平均值, rv, i为用户u的邻居v对项目i的评分, 表示用户u的最近邻居集合, Sim(u, v)是用户u和用户v的相似度。

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

本文实验数据采用GroupLens研究组(http://www. grouplens.org)提供的电影评分数据集ML-100K中的一个数据子集, 该数据集包括943个用户对1 682部电影的10万条评分记录。由于每条记录都是以< UserID, ItemID, Ratting> 三元组的形式表示, 为了便于计算和获得比较直观的实验结果, 将原始数据转换为如表1所示的矩阵形式, 若用户未对某电影评分则设值为0, 评分标准为1-5, 评分越高表明用户越喜欢该电影。通过计算得出该数据集的数据稀疏度为6.3%, 在实验过程中将数据集按照80%和20%的比例划分为训练集和测试集进行检验。

4.2 评估标准

实验采用的度量标准是MAE(Mean Absolute Error)和RMSE(Root Mean Square Error), MAE通过计算预测值与实际值的平均误差大小度量系统的推荐质量, RMSE是预测值与实际值偏差的平方和与观测次数n比值的平方根, 二者都是越小推荐质量越高。

4.3 实验结果及分析

(1) KSUBCF算法与Slope One算法比较

为了和该算法进行对比, 在实验中采用80%作为训练集的比例, K-means聚类时的k值取10。实验随机挑选100个用户的评分记录, 按照80%与20%比例构造训练数据集和测试数据集, 对测试数据集中每条评分记录进行预测, 求出其MAE值和RMSE值。选择10-60个目标用户的最近邻居, 每次递增10, 实验结果与测试集数据进行对比分析。测试结果如图2和图3所示:

图2 KSUBCF算法与Slope One算法的MAE值对比

图3 KSUBCF算法与原Slope One算法的 RMSE值对比

通过实验结果对比分析可以看出, 本文提出的KSUBCF算法的MAE值和RMSE值远小于原Slope One算法的MAE值和RMSE值, 尤其是当目标用户的最近邻居数目在20到60之间的时候对比更加明显, 随着邻居数目的增加MAE值有8.8%-21%不等的下降, RMSE值有17%-28.1%的下降, 说明本文提出的算法优于原Slope One算法。

(2) KSUBCF算法与传统协同过滤算法的比较

本组实验的目的是将KSUBCF算法与两种传统协同过滤算法UBCF和IBCF进行对比。

实验设置: 仍然采用上述实验的数据, 不过在进行相似度计算时基于用户的协同过滤算法(UBCF)采用的是Pearson相关相似性度量方法, 而基于项目的协同过滤算法(IBCF)采用的是修正的余弦相似性度量方法。本文提出的方法以及UBCF和IBCF算法在选择邻居用户时均采用基于前k项最近邻居的方法, 并设k值为40, 另外KSUBCF算法中项目聚类时阈值k取值为10, 前后两个k意义不同。实验结果如图4和图5所示:

图4 三种不同协同过滤算法间MAE值比较

图5 三种不同协同过滤算法间RMSE值比较

分析实验结果可知, 本文提出的KSUBCF算法的MAE值较UBCF和IBCF两种算法分别有10%和43.8%的下降, 而其RMSE值较UBCF和IBCF两种算法分别有20.1%和37.4%的下降, 说明本文提出的这种新的预测填充方法提高了预测精度。

5 结语

针对基于协同过滤的推荐系统中稀疏性问题, 最普遍的解决方法就是对稀疏的矩阵进行预测填充, 考虑到之前许多预测方法的复杂性原因, 本文提出的方法主要采用Slope One算法进行预测, 实验结果表明该方法简单易实现而且效果显著, 尤其在数据稀疏的情况下相较于传统推荐方法在预测精度方面有明显提高。在实验中发现, 虽然预测值与真实值的平均误差等较低, 但仍然存在少数差距较大的预测评分。很多学者开始研究基于本体的推荐方法[13, 14, 15], 这种方法不需要依赖用户评分数据, 克服了传统算法中存在的弊端。基于本体的推荐方法在一些领域中的应用将是下一步的研究内容。

参考文献
[1] 李聪, 梁昌勇, 杨善林. 电子商务协同过滤稀疏性研究: 一个分类视角[J]. 管理工程学报, 2011, 25(1): 94-101.
(Li Cong, Liang Changyong, Yang Shanlin. Sparsity Problem in Collaborative Filtering: A Classification[J]. Journal of Industrial Engineering and Engineering Management, 2011, 25(1): 94-101. ) [本文引用:1] [CJCR: 1.012]
[2] Huang Z, Chen H, Zeng D. Applying Associative Retrieval Techniques to Alleviate the Sparsity Problem in Collaborative Filtering[J]. ACM Transactions on Information Systems, 2004, 22(1): 116-142. [本文引用:1] [JCR: 1.07]
[3] 王洋, 骆力明. 一种解决协同过滤数据稀疏性问题的方法[J]. 首都师范大学学报: 自然科学版, 2012, 33(4): 1-5, 26. (Wang Yang, Luo Liming. In Collaborative Filtering a Method of Alleviating the Sparsity Problem [J]. Journal of Capital Normal University: Natural Science Edition, 2012, 33(4): 1-5, 26. ) [本文引用:1]
[4] Zhang J Y, Pu P. A Recursive Prediction Algorithm for Collaborative Filtering Recommender Systems [C]. In: Proceedings of the 2007 ACM Conference on Recommender systems, Minneapolis, MN, USA. 2007: 57-64. [本文引用:1]
[5] 林德军. 基于Slope One改进算法推荐模型的设计与实现[D]. 北京: 北京邮电大学, 2012.
(Lin Dejun. Design and Realization of the Recommendation Model Based on the Slope One Improved Algorithm [D]. Beijing: Beijing University of Posts and Telecommunications, 2012. ) [本文引用:1] [CJCR: 0.62]
[6] 邓爱林, 朱扬勇, 施伯乐. 基于项目评分预测的协同过滤推荐算法[J]. 软件学报, 2003, 14(9): 1621-1628.
(Deng Ailin, Zhu Yangyong, Shi Baile. A Collaborative Filtering Recommendation Algorithm Based on Item Rating Prediction[J]. Journal of Software, 2003, 14(9): 1621-1628. ) [本文引用:1] [CJCR: 2.181]
[7] 王鹏, 王晶晶, 俞能海. 基于核方法的User-Based协同过滤推荐算法[J]. 计算机研究与发展, 2013, 50(7): 1444-1451.
(Wang Peng, Wang Jingjing, Yu Nenghai. A Kernel and User-Based Collaborative Filtering Recommendation Algorithm[J]. Journal of Computer Research and Development, 2013, 50(7): 1444-1451. ) [本文引用:1]
[8] Ma H, King I, Lyu M R. Effective Missing Data Prediction for Collaborative Filtering [C]. In: Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2007: 39-46. [本文引用:1]
[9] Lemire D, Maclachlan A. Slope One Predictors for Online Rating-Based Collaborative Filtering [C]. In: Proceedings of the 2005 SIAM International Conference on Data Mining (SDM’05), Newport Beach, California, USA. 2005. [本文引用:1]
[10] 孙丽梅, 李晶皎, 孙焕良. 基于动态k近邻的SlopeOne协同过滤推荐算法[J]. 计算机科学与探索, 2011, 5(9): 857-864.
(Sun Limei, Li Jingjiao, Sun Huanliang. SlopeOne Collaborative Filtering Recommendation Algorithm Based on Dynamic k-Nearest-Neighborhood[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(9): 857-864. ) [本文引用:1]
[11] Zhang D J. An Item-based Collaborative Filtering Recommendation Algorithm Using Slope One Scheme Smoothing [C]. In: Proceedings of the 2nd International Symposium on Electronic Commerce and Security, Nanchang, China. IEEE, 2009: 215-217. [本文引用:1]
[12] Wang P, Ye H W. A Personalized Recommendation Algorithm Combining Slope One Scheme and User Based Collaborative
Filtering [C]Filtering [C]. In: Proceedings of the 2009 International Conference on Industrial and Information Systems, Haikou, China. IEEE, 2009: 152-154. [本文引用:1]
[13] 肖敏. 基于领域本体的电子商务推荐技术研究[D]. 武汉: 武汉理工大学, 2009.
(Xiao Min. Research on Electronic Commerence Recommendation Technology Based on Domain Ontology [D]. Wuhan: Wuhan University of Technology, 2009. ) [本文引用:1] [CJCR: 0.529]
[14] Chen Y J, Chu H C, Chen Y M, et al. Adapting Domain Ontology for Personalized Knowledge Search and Recommendation[J]. Information & Management, 2013, 50(6): 285-303. [本文引用:1]
[15] Cheng S T, Chou C L, Horng G J. The Adaptive Ontology- based Personalized Recommender System[J]. Wireless Personal Communications, 2013, 72(4): 1801-1826. [本文引用:1] [JCR: 0.428]