基于协同过滤的推荐系统

我的毕业设计课题是《隐私保护的共享协同过滤算法研究》,主要研究如何实现在数据安全的前提下构建多方参与的共享协同过滤推荐系统。因为论文原稿是Markdown写的,所以就顺手搬上来了。原文比较长,在博客中分为三篇文章,本文讲述协同过滤推荐算法的基本原理,下一篇文章讨论利用局部敏感哈希改进推荐系统的实时性,再下一盘文章讨论利用现在比较热门的同态加密技术实现共享协同过滤。

推荐系统

如今我们以经进入了一个数据爆炸的时代,Web逐渐成为数据分享的平台,而用户则是产生数据的主体。如何有效利用用户产生的信息,如何让人们从海量数据中找到他们可能真正感兴趣的内容变得越来越难。在这种情况下,搜索引擎技术成为寻找目标信息的直接手段,但这并不能完全满足需求,因为在很多情况下,用户其实并不明确的知道自己的需求,或者其需求难以用搜索引擎支持的格式来描述,因此推荐系统应运而生。目前,推荐系统在很多大型电子商务和社会化站点都取得了很大的成功,这也进一步说明在海量数据的背景下,用户需要这种更加智能,更加理解用户个人偏好的发现机制。

推荐系统的分类

目前,个性化推荐系统按照如何利用数据源可以分为基于用户基本信息发现用户相关度的基于人口统计学推荐,基于推荐物品内容本身的基于内容推荐,以及根据用户对物品偏好发现用户或物品间相关性的基于协同过滤(Collaborative Filtering)的推荐。

基于协同过滤的推荐系统

曾经的内容提供者现在更加提倡用户参与和用户贡献,而基于协同过滤的推荐机制正好符合这种场景。基于协同过滤的推荐机制的核心原理其实很并不复杂,就是根据用户对物品的评价,发现用户或物品间潜在的相关性,然后基于这些相关性产生推荐结果。基于协同过滤的推荐又可以细分为3个子类:基于用户的推荐(User-based),基于项目的推荐(Item-based)和基于模型的推荐(Model-based)。基于协同过滤的推荐机制是目前应用最为广泛的推荐机制,他有几个显著的优点:其一,他不需要对用户或物品进行严格的建模,也不需要对对物品的描述进行深入理解,因此它是领域无关的;其二,这种推荐是开放的,可以公用他人经验协助用户发现潜在的兴趣偏好。

基于用户的协同过滤推荐算法的核心思想

基于用户的协同过滤的基本原理相对最为朴素,其根据计算目标用户的历史偏好向量与其他用户历史偏好向量的相关性,发现目标用户偏好相似的近邻用户群,在实际应用中通常采用“K-最近邻”算法,然后基于此近邻用户群的历史偏好信息,预测目标用户对未评价项目可能产生的评分,最终得到推荐结果。基于用户的协同过滤与基于人口统计学的推荐机制都在计算用户间的相似度,但不同的是基于人口统计学的推荐机制只考虑用户本身的特征,而协同过滤则基于用户的历史偏好数据,其基本假设是喜欢类似物品的用户存在可能相同或相似的选择偏好。

常用的向量相似度度量方式

常用的特征向量相似性通常使用包括相似系数,相关系数以及相异距离等方式度量,在实际应用中常用的手段包括但不限于欧式距离,余弦相似系数,修正的余弦相似系数,Jaccard相似系数,皮尔逊相关系数等。

  • 基于欧氏距离的相似度
    欧氏距离是欧式空间中的一种距离度量方式,向量间的欧式距离是一种$L_{d}$范式,当$d=2$时,欧氏距离为:
    $$dis(x,y)=L_{2}=\left | x-y \right |^{2}$$

  • 基于余弦相似系数的相似度
    余弦相似系数通过计算用户评分向量间的夹角的余弦值来度量向量间的相似性,即:
    $$sim(x,y)=cos(x,y)=\frac{x\cdot y}{\left | x \right |\left | y \right |}$$

  • 基于修正的余弦相似系数的相似度
    基于余弦相似系数的相似度会受到用户评分标准的影响,因此修正的余弦相似系数从用户评分向量中减去了用户对项目评分的平均值,修正后的相似度计算为:
    $$sim(x,y)=\frac{\sum_{c\in I_{xy}}(x_{c}-\bar{x})(y_{c}-\bar{y})}{\sqrt{\sum_{c\in I_{x}}(x-\bar{x})^{2}}\sqrt{\sum_{c\in I_{y}}(y-\bar{y})^{2}}}$$

  • 基于皮尔逊(Pearson)相关系数的相似度
    皮尔逊相关系数是判断两组数据与一直线拟合程度的一种度量,它在数据不是很规范(normalized)的时候会倾向于给出更好的结果,其相似度计算为:
    $$sim(x,y)=\rho (x,y)=\frac{\sum_{c\in I_{xy}}(x_{c}-\bar{x})(y_{c}-\bar{y})}{\sqrt{\sum_{c\in I_{xy}}(x-\bar{x})^{2}}\sqrt{\sum_{c\in I_{xy}}(y-\bar{y})^{2}}}$$

  • 基于Jaccard相似系数的相似度
    Jaccard相似系数用于计算两个集合间的相似性,通过计算集合的交集的模和并集的模的比值实现,既:
    $$sim(x,y)=\frac{x\cdot y}{\left | x \right |^{2}+\left | y \right |^{2}+x\cdot y}$$

不同的相似度度量方式对不同特征的评分数据都存在相对优势和劣势,本文使用皮尔逊相关系数作为实现。

伪代码实现

若以$M$表示用户-项目的历史评分矩阵,以$target$表示等待推荐的目标用户,近邻用户群尺寸为$k$,则基于用户的协同过滤的推荐系统的核心实现可以用以下Python伪代码表示:

users_size, items_size = M.shape
similarities = np.empty((users_size,))
for i, user_vec in emumerate(M):
    similarities[i] = pearsonr(user_vec, target)
similar_user_indexes = similarities.argsort()[0 - k:]
sum_of_similarities = 0
sum_o_similarities_with_weight = np.zeros((items_size,))
for similar_user_index in similar_user_indexes:
    similarity = similarities[similar_user_index]
    sum_of_similarities += similarity
    sum_o_similarities_with_weight += similarity * M[similar_user_index]
assert sum_of_similarities != 0
predict = sum_o_similarities_with_weight / sum_of_similarities

基于项目的协同过滤

基于项目的协同过滤推荐的基本原理与基于用户的协同过滤是类似的,但其计算的是物品见的相似度。基于项目的协同过滤与基于内容的推荐系统间的差别,与前文提及的基于用户的协同过滤和基于人口统计学的推荐系统间的差别也是类似的。基于项目的协同过滤机制实际上是基于用户的协同过滤的一种改良,因为在大部分Web站点中,物品数量是远远小于用户数量的,而物品的数量和物品间的相似度都相对稳定。因此其计算结果拥有更长的时效性。

基于模型的协同过滤

基于模型的协同过滤推荐就是基于样本的用户喜好信息,训练一个推荐模型,然后根据实时的用户喜好信息产生推荐结果。

传统基于协同过滤的推荐系统的弊端

基于协同过滤的推荐系统也存在一些弊端:其一,历史数据对于新用户或新物体存在冷启动问题;其二,产生推荐结果的过程需要对大量用户间的相关性进行计算,而实际与目标用户相似的近邻用户群容量却很小,因此计算效率低,实时性差;其三,推荐的准确行依赖于用户历史数据集的大小;其四,在绝大多数实现中,用户的历史偏好信息呈现为一个巨大的稀疏矩阵,而稀疏矩阵在最终计算过程中可能会产生少部分人的错误偏好对推荐准确度产生较大影响的问题。

本文的改进思路

传统的基于协同过滤的推荐系统的计算效率低的问题,在加入对性能损耗较大的数据隐私保护算法后会更加凸显。因此,针对弊端二,下一篇文章首先会尝试通过将局部敏感哈希与传统基于协同过滤的推荐系统相结合,在离线生成索引时排除绝大部分大概率不相关用户,减少参与计算的用户数量。其后,针对弊端三,为解决多方参与计算过程中用户及企业数据隐私的问题,再下一篇文章尝试通过将同态加密应用于基于协同过滤的推荐系统中,实现在保证数据隐私安全的情况下允许多个数据持有者参与推荐结果结算。

参考资料

探索推荐引擎内部的秘密

许可协议: CC BY-NC-SA 4.0
本文链接:https://blog.angelmsger.com/基于协同过滤的推荐系统/