第 3 章 关于推荐系统冷启动问题的研究
推荐系统需要根据用户的历史行为和兴趣预测其未来的行为和兴趣,尤其是
协同过滤推荐算法,需要从用户历史行为数据出发,建立起用户和项目的特征矩
阵从而进行推荐。如何在缺失大量评分数据的情况下设计推荐系统,并使用户对
推荐结果满意,从而愿意使用该系统,就是冷启动问题12。
本章研究了协同过滤算法中的冷启动问题,并提出一种基于项目分类和空缺
值填充的协同过滤改进算法,并应用 MovieLens 数据集,在 Spark 平台完成了该
算法的并行化实现。
3.1 冷启动问题的提出
目前,协同过滤是应用最广泛、最成功的推荐算法。基于矩阵分解的协同过
滤算法可以解决评分矩阵稀疏性的问题,但是当一个新用户没有在评分矩阵中对
任何一个项目进行过评分,则无法应用协同过滤算法对该用户进行推荐,或一个
新项目没有被任何用户评分,则该项目无法被推荐给其他用户,这就是协同过滤
算法的冷启动问题34。
冷启动问题主要分为三类:
• 用户冷启动
用户冷启动问题是指如何给没有对任何一个项目进行过评分的新用户进行
推荐的问题。新用户没有历史行为数据,也就无法根据其历史行为预测行为和兴
趣。
• 项目冷启动
项目冷启动问题是指如何将一个没有被任何用户评分过的项目推荐给其他
用户的问题。
• 系统冷启动
系统冷启动问题主要解决的是如何在一个新开发的网站或平台(还没有用户,
也没有用户行为信息,只有一些物品信息)上进行个性化推荐系统的搭建。
冷启动问题是协同过滤算法中被广泛关注的一个重点问题,它的存在严重影
响着传统的协同过滤推荐系统的推荐结果。目前针对冷启动问题,提出了一些解
决方法,主要分为两大类5:一类是利用利用已有的评分数据、不考虑内容信息的
方法,另一类是结合新用户或新项目的内容属性信息的方法。不考虑内容信息的
常见方法有随机推荐法、平均值法、众数法、信息熵法等。最简单最直观的随机
推荐法的准确率不高,主要依靠用户反馈修正用户对项目的偏好信息,冒险度较
高,容易令用户失去对平台的信任。平均值法6选用所有项目的均值来填充未评
价项目的预测值,填充原始评分矩阵再应用协同过滤方法进行推荐,但实际上新
用户对项目的喜好程度等于其他用户对此项目的评分均值的可能性非常小,而且
均值法抹杀了个人的兴趣爱好会上下波动的个体差异性。众数法7采用所有用户
对所有项目的评分中最多出现的评分值作为未评分项目的预测值,从统计学角度
来说,预测准确的概率会高于不准确的概率,但是如果被预测项目是用户喜欢的,
而评价过该项目的用户大多数人都打了 1 分,那么这 1 分的预测值就不仅是不准
确,而是错误的预测。香农用信息熵来描述信源的不确定度,信息熵法则是通过
信息熵增益选择分类属性,实质上也是一种均值预测法,只不过不是用所有项目
评分的均值,而是信息熵较大的几个项目的评分的均值。但是信息熵大的项目的
评价不一定就能代表用户喜好,且在计算上会花费大量时间,效率不高。考虑内
容信息的方法主要有原始矩阵扩充8、构建概率统计模型910、与机器学习相结合
等。本章的目标是在满足用户个性化需求的基础上处理冷启动问题,因此考虑的
也是结合用户以及项目的内容信息的方法。原始矩阵扩充的方法是利用用户的人
口统计信息以及项目的特征信息增加到原始评分矩阵的行和列中,使原矩阵得以
扩充,在应用协同过滤算法产生推荐。但此方法不适合高维数据系统,因为少量
的特征信息难以有效描述大量的用户及项目的偏好情况。构建概率统计模型的方
法用内容信息替代评分信息的概率分布,并在此基础上应用 Hofmann 的 EM 迭
代算法进行推荐,然而搜集概率信息需要较大代价,因此该方法的实际应用不多。
与机器学习相结合的方法,关键在于利用机器学习找到内容信息与评分之间的内
在联系,是目前冷启动问题研究中比较先进的发展方向。本章提出的基于项目分
类和空缺值填充的协同过滤改进算法也属于利用机器学习并考虑内容信息的解
决方案。
3.2 相关技术
3.2.1 朴素贝叶斯分类器及相关技术
贝叶斯算法是统计学中运用概率统计知识来进行分类的算法,由贝叶斯定力
发展而来,该算法的分类方法简单,准确率高,速度快,因此得到了广泛的应用。
贝叶斯分类算法的核心是贝叶斯公式,该公式计算的是在给定的Y 之后 X
的条件概率,也就是在观察到Y的情况下,有多大的概率会观察到 X 。通常情况
下观察到 X 的概率叫做先验概率 ( )p X ,而在观察到Y的情况下观察到 X 的这个
概率被称为后验概率,表示为 ( | )p X Y ,计算公式如下:
( | ) ( | ) ( ) / ( )P X Y p X Y p X p Y (3.1)
朴素贝叶斯分类器是一种基于贝叶斯算法的概率分类器,用来将数据样本映
射到某个类别集合。为了简化计算模型,它假设实例变量的各个属性之间相互条
件独立,也就是说,在给定实例类标记时,观察到的联合概率是各个单独属性值
概率的乘积,数学表达形式如下:
1 2 i( , , , | c ) ( )m jP a a a P a c… (3.2)
在这个假定下,变量的其中一种属性的取值或缺失与其他属性的取值或缺
失之间没有关联,分类器会单独考虑每种属性对分类判断的影响,而不考虑已
经存在或缺失的其他属性。因此,我们可以应用朴素贝叶斯分类器来进行项目
特征和用户群体的划分。以项目特征分类为例,对协同过滤推荐模型中项目的
分类方法如下:
假设有一个新的实例项目 x ,并将它的属性特征描述为特征向量
1 2
{ , , }
n
a a a…… ,该向量中的每一个元素表示一个属性特征值。用 1 2 m{C ,C , C }……
表示已知的 m 个类别的分类集合,先验概率表示为 ( | c )iP x ,从训练数据集中求
得,后验概率表示为 (c | )iP x ,通过贝叶斯公式计算得到:
( | c ) (c )
(c | )
( )
i i
i
P x P
P x
P x
(3.3)
对象的最大后验概率通过比较得到,最大后验概率所在的类即可被判定为对
象最终所属的类,计算公式如下:
*
1 2 i i
( ) arg max ( , , , | c ) (c )
m
C x P a a a P … (3.4)
代入式(3.2),可得朴素贝叶斯分类器的计算公式:
*
i
( ) arg max (c ) ( )
j
C x P P a c (3.5)
依据朴素贝叶斯分类器的构造原理及步骤,分类器算法设计如下:
输入:项目集合 1 2 n{i , , ,i }I i …… ,项目的属性特征向量 1 2{ , , , }na a a……
输出:项目分类结果(每一个项目都会被添加一个类别标签
i
c )
(1) 读入训练数据集,对属性值做格式预处理;
(2) 从训练数据集中提取项目集合 I 和项目属性特征向量 1 2{ , , }na a a…… ,
并计算项目的先验分布概率 i( | )iP I c ;
(3) 根据训练数据计算类别先验概率,根据贝叶斯公式计算某一类别项
目的后验概率 1 n( | , )iP c I I ……, ,某属性值类别计算概率公式如下:
i
1
1 1
( | ) arg max ( ) ( | ), ,
m
i
i n n i i
P P P a cc I i I i c
…… (3.6)
(4) 将项目在所有类别下的醉大后验概率所在的类作为项目所属的类,
并保存分类结果和最大后验概率值。
图 3.1
经过实验发现,即使属性之间不满足独立性条件时,朴素贝叶斯分类器仍然
能够取得显著的效果。
在推荐系统中,用户和项目都具有多样化的属性,直接用评分数据计算会对
预测结果产生偏差,因此,有必要对不同属性的用户和项目进行合理分类。本章
应用朴素贝叶斯分类器将项目按照一定的属性类别进行分类,再进行协同过滤系
统的预测推荐。
3.2.2 矩阵空缺值填充技术
数据填充技术11是指对于因为各种原因引起的数据丢失或数据空缺,应用一
定的规则进行有效填充。矩阵空缺值填充,即代填充的数据模型含有空缺值的矩
阵,如推荐系统冷启动问题中所描述的极度稀疏的评分矩阵,评分数据的缺失严
重影响推荐结果。进行数据填充处理后的结果可能有利有弊,因为填充后的数据
模型看似完整,但若填充方法不合理,可能会对结果产生负面的影响。
在协同过滤算法中,用户-项目评分矩阵存储着原始评分数据,然而,由于种
种现实原因,只有少数的项目被用户进行过评分,导致了评分矩阵非常稀疏12,
这种元素缺失的问题使得推荐结果受到严重影响。该现象也引起了很多研究者的
关注,目前已有的用语解决协同过滤稀疏矩阵的填充技术包括固定值填充、均值
填充等,以及利用算法自身步骤中出现的中间数据来进行填充。邓爱林等人利用
项目之间的相似性对未评分的项目进行预测,得到初步的预测评分,并在此基础
上再计算目标用户的最近邻居13。余志虎等人提出了一种基于云模型数据填充的
算法,利用用户相似性来计算评分矩阵中目标用户的缺失评分14。徐翔等人使用
不同填充方法来对稀疏的评分矩阵进行填充,比较不同方法产生的结果,分别为
各填充方法选取最有效的相似度优化方案15;彭石通过挖掘项目之间的相似性以
及用户兴趣管理,提出了一种综合的项目相似性度量方法,进而对评分矩阵进行
预测填充16。
本章应用的空缺值填充技术基于这样的假设:经过朴素贝叶斯分类器分类后
的项目,同一类别中项目在相似度上要高于不同类别中的项目。因此,在对基于
项目的协同过滤算法中进行相似度计算时,直接选取同一类中的项目,而非所有
项目,并从计算过的同类项目中选取最近邻。
3.2.3 基于矩阵分解的交替最小二乘算法
基于矩阵分解的协同过滤算法属于基于模型的协同过滤算法,上一章已经进
行过初步的介绍。目前较为常用的矩阵分解算法主要包括 SVD(奇异值分解法)
以及 ALS(交替最小二乘法)。这两者的算法原理都是将原始的评分数据映射到
低维空间中,然后计算项目之间的相似度,并对未被评分过的项目进行评分预测。
也有人对基于 SVD 的推荐方法提出了改进,提出了 SVD++方法1718,SVD++在
SVD 的基础上引入了隐式反馈,除了使用评分数据,还使用用户和项目的浏览
数据等作为新的参数。然而,SVD 的计算过程的时间复杂度高,虽然可以利用梯
度下降等机器学习方法来进行近似计算,但实际应用还是较为困难。基于 ALS 的
矩阵分解推荐方法是 Pan R, Zhou Y 等人在 Netflix Prize 比赛中提出的一种新的
矩阵分解方法19。ALS 算法以全局的角度训练模型,将用户和项目用一组低维度
隐语义因子表达,来预测用户对未使用过的项目的评分。该算法可以有效解决协
同过滤中的数据稀疏性问题,且可以很好地扩展到分布式计算中。接下来对基于
矩阵分解的 ALS 算法进行详细描述。
对于m n 的用户-项目评分矩阵 R,希望找到一个低秩的矩阵 X 来逼近评分
矩阵 R,如公式(3.7)所示。
TR X UV (3.7)
其中 m dU C , n dV C , d表示特征值的个数,一般 min( , )d r r m n, ,
r表示矩阵 R的秩,Simon Funk 将损失函数定义为:
22
. .
( , )
T
ij ij ij ij i jij
L U V R X R U V (3.8)
为了防止过拟合,给上式添加二阶正则化项,则式(3.8)可以改写为:
2 22
. . . .2 2
,
T
ij i j i jij
L U V R U V U V (3.9)
固定V ,对 iU 求导,
(U,V)
0
i
L
U
,得到下面求解 .iU 的公式,
1
. .
( )
T
i i ui ui ui ui
U RV V V n I
1,i m (3.10)
在上式中, .iR 表示用户 i对项目的评分向量, uiV 表示由用户 i评价过的项目
的特征向量组成的特征矩阵。 I 为一个d d 的单位矩阵。
ui
n 表示用户 i评价过的项目数量。同理,固定U 对 iV 求导,得到下面求解 .jV
的公式,
1
. .
( )
T T
j j mj mj mj mj
V R U U U n I
1,j n (3.11)
在上式中, . jR 表示给项目 j评过分的用户的评分向量, mjU 表示由为项目 j
评过分的用户的特征向量组成的特征矩阵。 mjn 表示为项目 j评过分的用户数量。
用 0 均值,偏差为 0.01 的高斯随机数初始化矩阵V ,然后用式(3.10)更新U ,
再用式(3.11)更新V ,直到算法的均方根误差(RMSE 值)收敛或迭代次数足够多
而结束为止。
在基于矩阵分解的交替最小二乘算法中,输入是用户评分矩阵 R,特征值的
个数 d,输出是 R的逼近矩阵 X ,算法流程图如图 3.2。
图 3.2
3.3 解决冷启动问题的协同过滤改进算法
3.3.1 算法总体思想
本文在传统的基于用户的协同过滤算法中引入项目分类设计和空缺值填充
技术,也即在计算用户相似度之前,先对项目进行合理分类,计算同个类型中项
目之间的项目相似度,并以相似项目为依据来预测评分矩阵中空缺元素的评分。
填充后的评分矩阵的稀疏度将大大降低,此时再应用这个稀疏度较小的评分矩阵
来计算产生推荐结果。
3.3.2 算法流程描述
1) 贝叶斯分类器设计算法
以项目特征分类为例,将朴素贝叶斯分类器作为对协同过滤推荐模型中项目
的分类方法。
依据朴素贝叶斯分类器的构造原理及步骤,分类器算法设计如下:
输入:项目集合 1 2 n{i , , i }I i …… ,项目的属性特征向量 1 2 n{N , , }N N……
输出:项目分类结果(每一个项目都会被添加一个类别标签)
(1) 读入训练数据集,对属性值做格式预处理;
(2) 从训练集中提取项目集 I 和项目特征 1 2 n{N , , }N N…… 计算项目的先验分
布概率 i(a | c)P ;
(3) 根据训练数据计算类别条件概率;
(4) 根据 2、3 的结果计算某一类别项目的后验概率 1 n(c | , a )P a …… ,某
属性值计算类别后验概率分布的公式如下:
1 1 n i
1
(C c | A a A a ) aP(C ) (A | C c)
n
n
i
P c P
……
(5) 将项目在所有类别下的后验概率最大值作为项目所属的类,并保存分类
结果和最大后验概率值。
2) 空缺值填充
在上一步中我们得到了项目的朴素贝叶斯分类。根据前面对项目的分类结果,
使得项目按一定的属性相关规则归类,在同一类中的项目就具有这样的特性:那
同一类中的项目在属性上具有相似相关性,目标项目的相邻用户在同一类中的相
似度更高。因此,用同类项目中的相似项目的评分作为依据来填充评分矩阵,能
够反映用户偏好,比固定值填充、平均值填充等机械性的填充技术更合适。
先计算目标项目与同类项目的相似度:
u, u,
1
2 2
u, u,
1 1
( ) ( )
( , )
( ) ( )
m
i i j j
u
m m
i i j j
u u
R R R R
sim i j
R R R R
其中 [1, ]u m 是同类项目集合中所有对项目 ,i j共同评分的用户集合。
按计算出的相似度大小排序并选出前 k个项目作为目标项目 i的最近邻居,
存储到集合 J中,计算用户u对目标项目 i的预测评分:
,
u,
( ) ( , )
| ( , ) |
u j j
J
i i
J
R R sim i j
P R
sim i j
3) 解决冷启动问题的协同过滤改进算法
得到了填充后的评分矩阵后,即可以用传统的基于用户的协同过滤算法的思
路来产生推荐。
余弦相似度计算:
a, b,
1
2 2
a, b,
1 1
( , )
( ) ( )
t
i i
i
t t
i i
i i
R R
sim a b
R R
根据计算结果选取近邻集合 L并计算用户对项目的预测评分:
,
a ,
( ) ( , )
| ( , ) |
b i b
L
i a
L
R R sim a b
P R
sim a b
将这些产生了预测评分的项目归于集合中并形成推荐。
3.3.4协同过滤改进算法的并行化实现
上述算法在 Spark 上实现的伪代码如下所示,
输入:
输出:
用户-电影评分数据集
推荐集合
val conf = new SparkConf().setAppName(“ColdStart”)
val sc = new SparkContext(conf)
//初始化 Spark 集群的环境配置
//贝叶斯分类
// rating =
//
//
// user_list
//
val item_sim = new scala.collection.mutable.HashMap[(String, String),
Double]()
val pred_rating = new scala.collection.mutable.ArrayBuffer[(String, String,
Double)
val neighbors = new scala.collection.mutable.HashSet[String]()
//最近邻节点,由分类得到
val s = vec1.zip(vec2).map{ case (f1, f2) => f1 * f2 }.sum
//相似度计算
val pred_rating_rdd = sc.parallelize(pred_rating)
3.4 实验及分析
3.4.1 实验环境
1) 环境说明
本文搭建的 Spark 集群采用的是实验室的三台普通 PC,包括 1 个 Master 节
点和 2 个 Slave 节点,三个节点均为 Ubuntu14.10 系统,节点之间局域网连接。
具体情况如下表 1 所示:
表 1 节点具体说明
主机名 IP 地址 作用
SparkMaster 192.168.1.110 NameNode,
JobTracker
SparkWorker1 192.168.1.113 DataNode,
TaskTracker
SparkWorker2 192.168.1.101 DataNode,
TaskTracker
2) 软件安装
Java JDK 用的是 jdk-7u75-linux-i586.gz,hadoop 版本为 hadoop-2.6.0.tar.gz,
安装过程中最重要的一点就是配置 SSH 实现无密码远程登陆与管理。搭建好
Hadoop 集群之后,在此基础上进行 Spark 的安装,其版本为 Spark1.2.0,开发环
境 IntelliJIDEA 14.0.3,对应的 Scala 为 scala-sdk-2.10.4。所有软件在三台机器上
安装并配置好后即可启动 Spark 分布式集群。
3.4.2实验数据集
本实验使用的是 MovieLens 数据集20错误!未找到引用源。,包括 943 个用户
对 1682 部电影的 100000 条评分记录,评分值都是 1 到 5 的整数值。从该数据集
中随机抽取 80%的评分数据作为训练集,剩下的作为测试集,即训练集 80000 条
数据,测试集 20000 条数据。为了度量该数据集的稀疏性,我们定义稀疏度未被
评分过的数据占总数据的比值。本文所用数据集的稀疏度为:
943 1682-100000
100%=93.7%
943 1682
3.4.3 实验分析
1) 准确度
本实验将平均绝对误差(MAE)用于评分预测的评价标准,通过计算与
实际用户评分的偏差来计算预测的准确性。假设 n个项目预测评分向量为
1 2
{ , , , }
n
p p p… ,对应的实际评分集合为 1 2{ , , , }nr r r… ,则MAE的计算公式为:
1
| |
n
i i
i
p r
MAE
n
通常情况下,MAE的值越小,代表预测评分与实际评分的误差值越小,推
荐准确度越高,算法性能越好。
2) 结果分析
为了对本章实现的算法(记为 PCF)的有效性进行实验验证与对比,将其与
传统的基于项目的协同过滤的推荐算法(记为 ICF)和基于空缺值均值填充的推
荐算法(记为 MCF)进行比较,以平均绝对误差(MAE)作为衡量标准。
图 3.3 几种推荐算法的准确度比较
图 3.3 是几种推荐算法在 MovieLens 数据集下的平均绝对误差(MAE)的
比较结果。可以看出,这几种方法的MAE值都随着用户最近邻个数 k的增加而减
小,同时本章提出的改进算法的MAE值低于其他几种算法,说明该算法生成的
预测评分与真实评分之间的偏差更小,即评分的准确度更高。不过随着 k逐渐增
大,几种算法的偏差值逐渐趋近。综上所述,本章提出的协同过滤改进算法在稀
疏矩阵下有良好的的表现,能够有效解决推荐系统的冷启动问题。
3.5 本章小结
本章对推荐系统的冷启动问题进行了研究,提出了一种基于贝叶斯分类和矩
阵空缺值填充的协同过滤改进算法,并应用于高度稀疏的 MovieLens 数据集,在
Spark 平台完成了该算法的并行化实现。实验结果表明该算法的准确度优于传统
的协同过滤算法和基于空缺值均值填充的推荐算法,可有效解决推荐系统中的冷
启动问题。
1 Schein A I, Popescul A, Ungar L H, et al. Methods and metrics for cold-start
recommendations[C] // Proceedings of the, International ACM SIGIR Conference on Research
and Development in Information Retrieval. 2002:253-260.
2 Guo H. SOAP: Live Recommendations through Social Agents[J]. Delos Workshop on Filtering
& Collaborative Filtering, 1998.
3 Schein A I, Popescul A, Ungar L H, et al. Methods and metrics for cold-start
recommendations[C] // Proceedings of the, International ACM SIGIR Conference on Research
and Development in Information Retrieval. 2002:253-260.
4 Guo H. SOAP: Live Recommendations through Social Agents[J]. Delos Workshop on Filtering
& Collaborative Filtering, 1998.
5 孙冬婷 ,何涛 , 张福海 . 推荐系统中的冷启动问题研究综述 [J]. 计算机与现代化 ,
0.7
0.75
0.8
0.85
0.9
0.95
1
5 10 15 20 25 30
M
A
E
The number of nearest neighbors k
ICF UCF MCF PCF
2012(05):59-63.
6 郭艳红.推荐系统的协同过滤算法与应用研究[D]. 大连: 大连理工大学,2008.
7 . D . 2005.
8 Balabanovic M, Shoham Y. Fab: Content-based, collaborative recommendation [J]. Communications of the
ACM, 1997 40 3 66-72.
9 Hofmann T Puzicha J. Latent class models for collaborative filtering C IJCAI’ 99. 1999 688-
693.
10 D Pennock E Horvitz S Lawrence et al. Collaborative filtering by personality diagnosis A
hybrid memory-and model-based approach C UAI’ 00. 2000 473-480.
11 Shan H, Kattge J, Reich P, et al. Gap Filling in the Plant Kingdom—Trait Prediction Using
Hierarchical Probabilistic Matrix Factorization[J]. ar Xiv preprint ar Xiv:1206.6439, 2012.
12 张光卫,李德毅,李鹏. 基于云模型的协同过滤推荐算法 [J]. 软件学报,2007,
18( 10) : 2403 -2411.
13 邓爱林,朱扬勇,施伯乐. 基于项目评分预测的协同过虑推荐算法[J]. 软件学报,
2003,14( 9) : 1621 – 1628.
14 余志虎,戚玉峰. 一种基于云模型数据填充的算法 [J]. 计算机技术与发展,2010,
20( 12) : 35 - 37.
15 徐翔,王煦法. 协同过滤算法中的相似度优化方法 [J]. 计算机工程,2010,36( 6) :
52 - 57.
16彭石. 基于用户兴趣和项目特性的协同过滤推荐算法研究[D].中南大学,2012.
17 Van Vleck E S. Continuous Matrix Factorizations[M]//Numerical Algebra, Matrix Theory,
Differential-Algebraic Equations and Control Theory. Springer International Publishing, 2015: 299-
318.
18 Benzi K, Kalofolias V, Bresson X, et al. Song Recommendation with Non-Negative Matrix
Factorization and Graph Total Variation[J]. arXiv preprint arXiv:1601.01892, 2016.
19 Pan R, Zhou Y, Cao B, et al. One-class collaborative filtering[C]//Data Mining, 2008. ICDM’08.
Eighth IEEE International Conference on. IEEE, 2008: 502-511.
20 康钟荣. 基于项目分类与预测填充的协同过滤推荐算法研究[D]. 北京化工大学, 2013.