基于稀疏约束非负矩阵分解的推荐算法

刘 煜,陈 震,刘奇龙

(贵州师范大学 数学科学学院，贵州 贵阳 550025)

0 引言

随着互联网的高速发展，用户可以轻松的获取网络信息。近年来，电子商务的发展尤为迅速，个性化推荐也逐渐出现在人们的视线当中。推荐系统[1-3]是利用电子商务网站向客户提供商品信息和建议，帮助用户决定应该购买什么产品，个性化推荐是根据用户的兴趣特点和购买行为，向用户推荐其所感兴趣的信息和商品。随着电子商务规模的不断扩大，网络上数据的爆炸式增长导致了越来越严重的信息过载现象。为了帮助用户从海量的网络数据中快速定位自己最有可能感兴趣的信息，推荐系统应运而生。推荐系统是减轻信息过载影响和实现个性化服务的最有效方法之一，它已经渗透到了我们生活的方方面面，比如爱奇艺的电影推荐、网易云的音乐推荐、淘宝的商品推荐、美团的餐厅推荐、抖音的短视频推荐等等。现在最常用的推荐算法有基于内容的推荐[4-5]、协同过滤推荐[6-12]和各种混合推荐。协同过滤算法作为一种传统的推荐技术，由于其简单高效的优点，越来越受到人们的青睐。算法的核心是通过挖掘用户的历史行为数据来发现用户的偏好，根据不同的偏好将用户分组，并将同组的其他用户的偏好推荐给用户。为了提高查找最近邻用户的准确性，一些文献使用K-means聚类算法[12]。该算法首先根据用户数据本身的特点对用户数据进行分类，然后使用协同过滤算法进行推荐，这种方法提高了推荐效果。但对于数据较少的新用户或不活跃用户，仍然无法降低用户群划分的难度和提高最近邻集查找的准确率。然而，协同过滤算法在实际应用中仍然面临着数据稀疏性和可扩展性等挑战。许多学者对算法提出了多种改进方法。近年来，非负矩阵分解[13-17]等技术逐渐被人发现，由于它自身的一些性质(良好的扩展性、稀疏性等)可以解决处理大量数据并快速准确的显示结果，被学者广泛关注和使用。

本文将从用户和项目之间的评分构建用户偏好相似度，准确找到用户与用户之间的联系和用户对项目的兴趣，形成项目子矩阵(目标用户)，再利用带有向量1-范数和向量2-范数约束条件的非负矩阵分解得到未评分项目的预测评分矩阵，最后将得到的子矩阵聚类[18]整合形成我们需要的预测评分，根据最后的预测评分排序推荐给目标用户。

1 相关工作

1.1 构建用户偏好相似度

Pearson相似度[18]表达式如下:

1.2 非负矩阵分解(NMF)

非负矩阵分解是对给定一个非负矩阵Q，寻找2个非负矩阵W和H，使得下列目标函数最小

W表示非负的基矩阵，H表示非负的系数矩阵。矩阵Q中列向量可以表示为：

算法描述：

NMF是一个带有约束的非线性优化问题，问题可以简单描述为：在约束条件W≥0,H≥0下，找到最优矩阵W和H，使得目标函数最小。Lee等[19]利用了最速下降法给出更新迭代规则，直到算法收敛时，W和H有最优解。

NMF:Step1:任意给定非负矩阵W和H初始值;Step2:更新迭代矩阵W和H,更新迭代规则为: Wik←Wik(VHT)ik(WHHT)ik, Hkj←Hkj(WTV)kj(WTWH)kjStep3:重复Step2,直到算法收敛。

1.3 非负矩阵分解的稀疏算法(SNMF)

稀疏性：稀疏意味着大多数元素取值接近于0，而只有少数元素取非零的值。

迄今为止，文献中已经提出并使用了许多稀疏性度量[20-22]，这些度量是从Rn到R的映射，它量化了一个向量被压缩到几个分量中，最稀疏的向量(只有1个分量非零)的稀疏度为1，而所有元素绝对值相等的向量的稀疏度为0。

接着将使用基于L1范数和L2范数之间关系的稀疏性度量：

(1)

其中n是x的维数。因为

所以0≤sparseness(x)≤1，当且仅当x仅包含1个非零向量，结果为1，当且仅当所有分量绝对值相等时，结果为0。

另一种定义：

目标是使NMF寻找具有所需稀疏度的解决方案。第一个要回答的问题是：到底什么应该是稀疏的？基矩阵W还是系数矩阵H？这是一个无法给出一般答案的问题，这完全取决于所讨论的具体应用。所以要约束哪个(或者两者都约束，或者都不约束)由实验者来选择。例如，分析疾病模式的医生可能会假设大多数疾病是罕见的(因此是稀疏的)，但是每种疾病都会导致大量的症状。假设症状构成它的矩阵的行，列表示不同的个体，在这种情况下，应该是“系数”是稀疏的，“基向量”是不受约束的；另一方面，当试图从图像数据库中学习有用的特征时，要求W和H都是稀疏的可能是有意义的，这意味着任何给定的对象都存在于少数图像中，并且只影响图像的小部分。

在此，介绍一种度量稀疏度的方法，即利用向量2-范数约束基矩阵W，和向量1-范数约束系数矩阵H。得到如下的目标函数：

文[23]对上述模型提出了非负矩阵分解的稀疏算法(SNMF)。

SNMF:Step1:任意给定非负矩阵W和H以及非负数的初始值;Step2:更新迭代矩阵W和H,更新迭代规则为:Wik←Wik(VHT)ik(WHHT)ik-βWikWia←Wia∑WiaHkj←Hkj(WTV)kj(WTWH)kj+λStep3:重复Step2,直到算法收敛。

文[23]中并没有给出SNMF收敛性证明，下面给出SNMF的收敛性证明。

引理1 设K(ht)是一个对角矩阵：

则函数

(2)

证明当h=ht时，G(h,ht)=G(h,h)=F(h)。若引理1成立，则必须证明：在h≠ht条件下，G(h,ht)≥F(h)成立。

F(h)在ht处的展开式为：

(3)

联立(2)和(3)两式，若要证明G(h,ht)≥F(h)成立，即证明不等式：

(h-ht)T[K(ht)-WTW](h-ht)≥0成立。

而为了证明半正定矩阵，我们考虑矩阵Mab(ht)，这个矩阵是对称矩阵K-WTW重新调整后的元素，也即：

此时，当且仅当矩阵M满足半正定时，K-WTW才是半正定的。

≥0

由以上证明，可以看出G(h,ht)≥F(h)成立，所以引理1中的函数G(h,ht)是函数F(h)的辅助函数。引理1得到证明。

根据上述引理证明，由于公式(2)是一个辅助函数，在这个更新规则下，F是不递增的。通过互换W和H的角色，在W的更新规则下，F同样可以显示为非递增。

2 基于SNMF的K-means算法(SNMF-K)

文[12]基于SNMF算法[20]和聚类算法给出算法过程，利用向量1-范数和向量2-范数来稀疏约束非负矩阵，并对分解得到的基矩阵W进行聚类，在此基础上，本节基于SNMF算法和K-means算法设计带有向量1-范数和向量2-范数稀疏约束非负矩阵分解的K-means算法有所改进，简称SNMF-K算法。

SNMF-K: 输入:数据集C,目标用户id,预设的聚类数目k,预设输出的电影个数y。输出:目标用户的推荐电影名称及个数。1)将输入数据集C构造成用户-项目的评分矩阵Vm×n,如表1,其中,每一列为一个数据样本,m表示m个项目,n表示有n个用户。2)调用SNMF算法[23]得到稀疏约束NMF后的系数矩阵H。3)在矩阵Hk×n中随机选取k个中心点进行聚类,计算欧氏距离,选定新的聚类中心,直到中心不再改变,得到聚类结果C∗=(C1,C2,…,Ck)。4)确定用户id所属的类别,计算用户id与所属类的其它用户的相似度关系。通过读取评分矩阵,得到前y的相似度值和用户id矩阵,获取前y名相似度矩阵,读取电影数据,定义好推荐电影的空集和前y名相似度所有电影,可以得到最相似用户的评分矩阵。接着获取此用户评价为5分的最高的电影评分矩阵,从而得到电影名。最后追加电影名到先前定义好的空集中,去重,防止y个最相似用户推荐的电影有重复。5)输出目标用户id的y个推荐电影名称。

该算法的优势在于调用SNMF算法后，对系数矩阵H进行聚类，可以快速得到最相似用户的评分矩阵，并且快速计算得到结果。

表1 用户-项目评分矩阵

3 实验结果与分析

3.1 实验数据的选取

实验数据是从Movielens电影评分数据集[24]中选取两组数据集，这两组数据集是个性化推荐系统研究者的最常用的数据集。数据包括用户个数、电影数目和相对应用户的评分。评分表示用户对电影的喜爱程度，评分越高，喜爱程度越高。

3.2 改进后的推荐算法的评价指标

推荐系统中对推荐算法的误差评价指标有很多种，都是计算真实值和预测值之间的误差，评价指标的数值越小，预测值就越准确。本文采取3种基本的指标：均方误差(MSE)、平方绝对值误差(MAE)和均方根误差(RMSE)。具体公式如下：

均方误差(MSE)：

平方绝对值误差(MAE)：

均方根误差(RMSE)：

均方根误差是均方误差的算术平方根。换句话说，是观测值与真值(或模拟值)偏差(而不是观测值与其平均值之间的偏差)的平方与观测次数T比值的平方根。在实际测量中，观测次数T总是有限的，真值只能用最佳值来代替。标准误差对一组测量中的特大或特小误差反映非常敏感，所以，标准误差能够很好地反映出测量的精密度。因此，标准差是用来衡量一组数自身的离散程度，而均方根误差是用来衡量观测值同真值之间的偏差。

对K-means算法与SNMF-K算法的聚类结果进行对比分析，用分类准确率来对聚类结果进行评价，分类准确率公式为：

式中：k为聚类的个数，i为正确聚类时对应类别中样本的个数，n为样本总数。显然，CA的值越大，表明聚类结果越好。其中RMSE越小表示模型推荐更加准确，性能更好。相反RMSE越大表示推荐与真实情况差距越大，性能越差。

通过对两组数据集对比的算法包括基于非负矩阵分解的推荐算法(NMF)、基于稀疏约束的非负矩阵分解的算法(SNMF)和SNMF-K算法。

第1组实验：

第1组数据包括943个用户、1 682部电影以及用户对看过的电影的评分。评分由1～5组成，并且利用公式(1)可得到该数据集的稀疏度为0.94。第一组数据集对比实验结果见图1。从图1中可看出，对于所取数据算法SNMF-K比NMF和SNMF具有较小的误差。

图1 第1组数据集对比实验结果

表2是迭代次数K值为90时，测试两种推荐算法的性能的差异。由表2看出，迭代次数K值为10的条件下，SNMF-K算法在原来的基础上，误差减少了3.4%。当K值达到90左右时，算法的推荐性能最佳。

表2 第1组数据不同K值对两种算法RMSE的影响

第2组实验：

第2组数据包括1 024个用户、2 316部电影以及用户对看过的电影的评分。评分由1～5组成，并且利用公式(1)可得到该数据集的稀疏度为0.96。第2组数据集对比实验结果见图2，图2表明算法SNMF-K比NMF和SNMF具有较小的误差。

图2 第2组数据集对比实验结果

表3是迭代次数K值为100时，测试两种推荐算法的性能的差异。由表3看出，迭代次数K值为10的条件下，SNMF-K算法在原来的基础上，误差减少了3.2%。当K值达到100左右时，算法的推荐性能最佳。

表3 第2组数据不同K值对两种算法RMSE的影响

通过两组实验结果，可以看出，提出的SNMF-K算法在3个指标都优于其他两种算法。实验表明所提出的算法具有良好的性能。

4 结论

本文提出了非负矩阵分解的稀疏模型。该模型通过稀疏得到的用户评分矩阵，利用用户偏好相似度对用户进行聚类，从而最后获得相似度矩阵，改进后的算法在误差上至少减少了3.2%，优化了最后的推荐性能。