本文是作者开发gorse过程中做的笔记,主要偏向于算法和思想,具体的实现见GitHubGoDoc,如有错误,恳请指正。

前言

近期在实验室学习推荐系统相关的内容,学习的最好方式就是自己实现各种算法,同时最近也偶然接触了GO语言,所以就尝试着用GO语言实现一个推荐系统引擎gorse(词义为“金雀花”)。目前比较流行的推荐系统相关的开源项目有LibRec1Suripse2,绝大多数采用Python、C++和Java实现,GO相比较于这些编程语言有以下优点:

  • 运行效率:GO语言运行效率比Java和Python高,然而不如C++ 。
  • 开发效率:编程效率媲美Python,高于C++,在运行效率和开发效率之间取得了很好的权衡。
  • 部署效率:一次编译成独立的二进制文件,比Python和Java都要容易使用。

推荐系统设计的内容非常多,本文主要关注采用协同过滤预测评分的方法,也就是Surprise框架的功能。Surprise中的一些设计非常实用,因此本文工作更像是Surprise框架的GO语言实现。由于GoDoc能够将源代码很好地展示出来,因此文中不再附上源代码。

数据结构

原始数据集

标准的协同过滤算法只需要一组用户-物品的评分记录,其中U为用户编号集合,I为物品编号集合。在矩阵分解方法中,使用表示所有用户对所有物品的评分情况。实际上用户通过只给了少数物品评分,所以更高效的方法是将存在的评分记录保存在一个表格中,表格每行是一个三元组:

训练数据集

算法对数据集的使用方法不只是按顺序将所有评分记录遍历一遍,因此需要一些额外的数据结构来帮助算法获取需要的信息。

  • 全局平均值:一些算法会给新用户或新产品全局平均分。
  • 内部编号映射:数据集中的用户编号和物品编号通常不是连续的。甚至是字符串,这会给编号相关的参数的保存造成困难,增加时间或者空间上的开销,所以将编号映射到连续的内部编号,用于计算过程。
  • 用户评分记录:例如KNN需要获取某用户的评分记录用于计算相似度。
  • 物品评分记录:和用户评分类似。

推荐算法

矩阵分解算法

  • SVD:SVD算法将每个用户i和每个物品j用相同维度的因子向量来表示,用户关于物品的评分为

其中为全局平均值,分别为用户偏差和物品偏差。模型训练采用随机梯度下降,每次迭代会遍历一次全部记录,对于一条记录,优化的目标函数为

模型中的因子需要随机初始化,然后使用更新公式优化参数,为学习率,为正则化参数

  • NMF:NMF算法就是在MF算法的基础上要求因子中的每个元素都是正数。为了能够维持正数的约束,首先将所有参数初始化为正数,然后在更新过程中保证更新后的结果也是正数。根据论文3中提到的算法,更新过程如下

这并不是我们熟知的梯度下降方法,关于收敛的证明可以参考论文4

  • SVD++:SVD++5算法在SVD算法的基础上结合了用户的隐式反馈——例如用户的点击行为、购买行为这些没没有具体评分的反馈,在单纯的评分数据集中可以将评分行为作为隐式反馈:

其中为每个物品的隐式反馈对应的因子,SVD++的更新公式为

K邻近算法

K邻近算法6分为基于用户和基于物品两种,基于用户的方法根据相似用户给物品的评分来预测,基于物品的方法根据被用户评过分的相似物品来预测评分。以下为基于用户的KNN算法,基于物品的KNN只需要将相关数据对换即可。

相似度计算

K邻近算法需要计算用户和用户或者物品和物品之间的相似度,给定两个用户的评分记录。在计算相似度之前需要获取共同的评分项

  • 余弦相似度:计算两者在评分空间中的余弦值
  • 平均平方差相似度:就是简单地计算两者在相同对象上的评分差值

为了统一相似度的性质,最终的相似度为

  • 皮尔逊相似度:就是在余弦相似度的基础上将评分减去用户所有评分的均值

评分预测

  • KNN:获取相似度最近的k个近邻,将相似度作为权重求均值
  • KNN去均值:在计算评分的时候减去用户的评分均值
  • KNN规范化:在计算评分的时候进行规范化
  • KNN基准化:在计算评分的时候减去基准模型中的偏差,基准模型即,也就是SVD模型去掉矩阵分解的部分

Slope One算法

Slope One算法7通过计算两个物品来自相同用户的得分差来进行预测,gorse中实现了简单的Slope One规则,论文中7还有其他更加复杂的规则。算法首先需要计算任意两个物品之间的得分差,计算之前需要找到同时完成对两个物品m和n进行打分的用户,计算平均得分差

当预测的时候,将用户的平均打分加上和评过分的物品平均差值

Co-Clustering算法

Co-Clustering算法8在协同过滤中结合了聚类的思想,将用户和物品分别进行聚类,预测方式如下:

其中,g为用户i所属的类,h为用户j所属的类,为属于g类用户对h类物品评分的均值,分别为用户i和物品j的评分均值,分别为g类用户和h类物品的评分均值。聚类方式和K均值算法类似,首先随机初始化,然后以最小化损失为目标重新调整分类即可。

评估验证

评分预测算法的目标是预测评分,所以可以对比测试集$D’$中的评分和预测的结果计算相应的误差。gorse实现了两种度量方法:

  • RMSE(根平均平方误差):
  • MAE(平均绝对误差):

交叉验证:交叉验证过程需要将数据集分割为训练数据集和测试数据集,使用训练数据集训练模型,然后将模型在测试数据集上的表现来评估模型的性能。gorse的交叉验证采用K折交叉验证,能够比较准确地反映模型的性能。

模型选择:模型选择的常用方法是网格搜索,调用网格搜索的时候提供每个参数备选的取值,然后使用遍历的方法搜索最佳参数组合。gorse中的网格搜索采用深度优先搜索,通常算法的参数是非常多的,导致网格搜索的工作量巨大,未来将考虑加入并行计算甚至分布式计算。

扩展内容

  • 脚本语言:LibRec提供了配置文件来实现调用二进制程序进行相关操作,然而推荐系统可以做的任务非常灵活,使用简单的配置文件会限制程序的灵活度。因此,可以考虑使用DSL来代替表达能力有限的配置文件,一个比较好的选项就是Lua。
  • 并行计算:GO语言中最引人注目的特性之一就是原生支持并行计算,充分利用多核处理器的并行计算能力可以加快算法运行速度。不过大部分提出的算法都是基于串行计算的,并不是所有的算法都能在保持等价的同时进行高效优化。即便如此,很多算法的部分过程都是可以改成并行计算的,例如KNN中计算邻近矩阵、Slope One中计算差异矩阵、SVD++中更新隐式因子,还有交叉验证和参数搜索也是非常适合使用并行计算实现。

  • 深度学习:作为机器学习应用领域的推荐系统自然免不了深度学习的介入,但是GO语言在深度学习方面的资源非常稀少。Tensorflow提供了go语言的包,但是并不支持Windows,会导致推荐系统引擎少了对于Windows的支持。

总结

推荐系统只有基于协同过滤的评分预测是远远不够的,未来可以考虑加入Top-N算法、基于内容的推荐算法等内容。单纯让算法能够运行是相对容易的,但是后续的性能优化是比较漫长的工作。

参考文献

  1. G. Guo, J. Zhang, Z. Sun and N. Yorke-Smith, LibRec: A Java Library for Recommender Systems, in Posters, Demos, Late-breaking Results and Workshop Proceedings of the 23rd Conference on User Modelling, Adaptation and Personalization (UMAP), 2015. 

  2. Hug, Nicolas. Surprise, a Python library for recommender systems. http://surpriselib.com, 2017. 

  3. Luo, Xin, et al. “An efficient non-negative matrix-factorization-based approach to collaborative filtering for recommender systems.” IEEE Transactions on Industrial Informatics 10.2 (2014): 1273-1284. 

  4. Lee, Daniel D., and H. Sebastian Seung. “Algorithms for non-negative matrix factorization.” Advances in neural information processing systems. 2001. 

  5. Koren, Yehuda. “Factorization meets the neighborhood: a multifaceted collaborative filtering model.” Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008. 

  6. Desrosiers, Christian, and George Karypis. “A comprehensive survey of neighborhood-based recommendation methods.” Recommender systems handbook. Springer, Boston, MA, 2011. 107-144. 

  7. Lemire, Daniel, and Anna Maclachlan. “Slope one predictors for online rating-based collaborative filtering.” Proceedings of the 2005 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2005.  2

  8. George, Thomas, and Srujana Merugu. “A scalable collaborative filtering framework based on co-clustering.” Data Mining, Fifth IEEE international conference on. IEEE, 2005.