基于KL散度的ALS推荐算法

韩远达

摘要：针对传统协同过滤推荐算法在稀疏数据上推荐准确度低的问题，提出一种基于KL散度的ALS推荐算法KL-ALS。传统ALS算法计算物品相似度时只考虑了用户之间的共同评分项，得到的相似性与真实值会有一定的误差，而采用KL散度计算物品相似度时，对用户评论的数量不做任何限制，不依赖于用户共同评分项。KL-ALS算法首先将ALS算法计算物品相似度和KL散度计算的物品相似度按照一定权重混合，产生总体相似度，进而采用ALS算法训练模型，能够更加准确地度量物品间的相似度，改善推荐效果。实验选取亚马逊智能产品评论数据集，与传统的基于ALS的协同过滤推荐算法和基于物品的协同过滤推荐算法（Item-CF）进行对比，实验结果表明KL-ALS推荐算法能有效提高推荐的准确度和性能。

关键词：KL散度;ALS算法;推荐算法;相似度;协同过滤

中图分类号：TP399      文献标识码：A

文章编号：1009-3044（2022）12-0004-03

开放科学（资源服务）标识码（OSID）：

近几年来，网络中的数据呈现爆炸性增长的趋势，人们渐渐由信息缺乏时期进入了信息超载时期，存储、分析、处理这些数据往往需要利用大数据技术。对于平台来说，如何使自己的产品信息在大量的信息中凸显出来，被用户所关注，正变成一个日益重要的问题。而推荐系统[1]可以很好地解决这个问题，它可以将平台海量数据加以处理利用，以便用于预测用户的兴趣。

1 相关研究

推荐系统通过分析数据源中用户对不同物品的评价和历史偏好之间的联系规律[2]，帮助用户从网络中的大量信息中搜索现在和将来可能会喜欢的信息资源，从而进一步向用户提供相应的推荐服务。而推荐算法是推荐系统中的核心部分，目前常用的推荐算法按照数据源不同可以分为基于人口统计学的推荐算法、基于内容的推荐算法和协同过滤推荐算法[3]。基于人口统计学的推荐算法主要根据用户的身份信息的相似性进行推荐，例如：性别、年龄、职业等信息，这种推荐较为粗糙，精确度一般不高。基于内容的推荐算法是给用户推荐与其曾经喜爱的物品相似的物品，主要基于物品自身的属性，广泛应用于文本领域的推荐。协同过滤推荐算法是目前推荐领域应用较多的算法，它可以通过基于统计的机器学习算法得到不错的推荐效果，但仍然存在数据稀疏性等问题[4]。针对该问题，本文提出一种基于KL散度的ALS推荐算法KL-ALS，在Spark平台[5]上进行实验，达到提高推荐的准确度和推荐性能目的。

2 基于KL散度的ALS推荐算法KL-ALS

2.1KL散度

KL散度基于概率分布，能够度量几何距离[6]（如余弦距离、欧氏距离）难以衡量的数据对象是它最显著的突破之一。假设区间D为连续区间，[ρi]和[ρj]分別为两个不同的概率密度函数，则离散型随机变量的KL距离如公式（1）所示。

[D（ρi||ρj）=x∈Dρi（x）log2ρi（x）ρj（x）]                    （1）

连续型随机变量的 KL 距离如公式（2）所示。

[D（ρi||ρj）=Dρi（x）log2ρi（x）ρj（x）]                  （2）

其中，[ρi（x）>0且ρj（x）>0]，且保证[0log20ρ=0]。

基于KL散度进行相似度的计算主要分为平滑处理、对称性修正、距离到相似度的转换三个步骤，下面详细讨论实现过程。

（1）平滑处理

为确保KL散度对智能产品数据的适用性，即保证[ρ（x）>0]，需对[ρ（x）]平滑处理，如公式（3）所示。其中[0<δ<1]，在平滑处理后，当[δ]值趋于0，误差趋于0。

[ρ（x）=ρ（x）+δ]                         （3）

（2）对称性修正

由公式（1）可知，KL散度具有完全非对称性，即[D（ρi||ρj）≠D（ρj||ρi）]。所以在计算两个物品之间的距离时需进行对称性修正，对KL散度修正为KL距离[Ds（i，j）]，并用公式（4）进行两个物品之间KL距离的计算。

[Ds（i，j）=（D（ρi||ρj）+D（ρj||ρi））/2]                   （4）

（3）距离到相似度的转换

由公式（1）的离散型随机变量的KL距离，得到的基于KL距离的物品相似度计算方法如公式（5）所示。

[KL（i，j）=simKL（i，j）=11+Ds（i，j）]              （5）

由上式可知，KL距离越小，两个物品之间相似度越高，KL距离越大，相似度越低。

2.2基于矩阵分解的ALS算法

ALS隐语义模型依据隐含特征获取用户的偏好特征，将某类偏好特征对应的物品进行推荐。根据奇异值原理，一个用户评分矩阵[R（m×n）]可以分解为用户特征矩阵[U（m×k）]、物品特征矩阵[V（k×n）]，矩阵[R（m×n）]可以用[UTV]的乘积近似表示。时间复杂度由[Ο（mn）]降为[Ο（（m+n）×k）]，节省存储空间的同时能够有效缓解矩阵稀疏性问题[7]。ALS处理过程如下。

（1）生成随机的[U0]。本文选取随机数方式初始化[U0]矩阵。

（2）固定[U0]，求解[V0]。此时，损失函数如公式（6）所示。

[f（U，V）=minU，V（u，i）∈k（Ru，i-（U（0）u）TVi）2+λ（U（0）u2+Vi2）]（6）

其中，[f（U，V）]函数只有一个变量[Vi]，[U0]是已知常量，对向量[Vi]求偏导[?f（U，V）?Vi=0]得到公式（7）。

[Vi=（UUT+λE）-1URTi]                       （7）

其中，E为单位矩阵，[Ri]为物品[i]的历史评分向量，[i∈1，n]，按照公式（7）求得[V1，V2，V3...Vn]，得到[V（0）]。

（3）固定[V（0）]，此时[V（0）]是已知常量，求解[U1]，求解过程类似步骤（2），损失函数变为公式（8）。

[f（U，V）=minU，V（u，i）∈k（Ru，i-（Uu）TV0i）2+λ（Uu2+V（0）i2）]   （8）

其中，[Uu]为变量，对向量[Uu]求偏导[?f（U，V）?Uu=0]，得到公式（9）。

[Uu=（VVT+λE）-1VRTu]                         （9）

其中，[Ru]表示物品[i]的历史评分向量，[i∈1，m]，按照公式（9）求得[U1，U2，U3...Un]，从而得到[U（0）]。

（4）反复迭代（2）、（3）步，终止条件为：算法误差值收敛或迭代次数达到预先设定次数。求得最终[U、V]特征矩阵后，通过公式（10）预测评分。

[R=UTuVi]                                  （10）

最后，可根据余弦相似度计算公式得到任意两个物品之间的相似性，公式如（11）所示。

[simCi，j=u∈UijRui*Ruju∈UijR2ui×u∈UijR2uj]                  （11）

其中，[simCi，j]為物品[i]和[j]的相似度，[Uij]为参与评分所有用户的集合;[Rui]为用户[u]对物品[i]的评分，[Ruj]为用户[u]对物品[j]的评分。

2.3 KL-ALS算法

由于评分数据中用户与物品间的交互信息是不完整的，部分用户未对相关物品给出评价，此时数据矩阵是稀疏的，随着数据量的增大，这种稀疏性会越来越明显[8]。ALS算法能将用户-物品-评分矩阵分解为低阶的用户特征矩阵和物品特征矩阵，通过得到的物品特征矩阵可以计算出每两个物品之间的余弦相似度，进而实现对物品的推荐，而这种相似度计算通常只考虑用户之间的共同评分项，用KL散度计算物品相似性能够充分利用数据集内所有物品的信息。通过融合以上两种相似度计算方法可以更加准确地计算出物品之间的相似度，进而实现对物品的推荐。因此，本文提出的KL-ALS算法将这两种物品相似度按一定权重混合得到具有两者优点的混合相似度，如公式（12）所示。

[simmix（i，j）=λsimC（i，j）+（1-λ）simKL（i，j）]     （12）

其中[simmix（i，j）]表示相似度加权后的最终相似度，[simC（i，j）]为利用余弦相似度计算得到的物品相似度，[simKL]为利用KL距离计算得到的物品相似度。l表示调节参数，可以动态调节[simmix（i，j）]的权重。特别的是，当系统新生产一个物品信息数据时，可以仅使用[simKL]来表示[simmix（i，j）]。本文提出的KL-ALS推荐算法基于topN推荐，通过分析数据集中用户评分数据信息，为用户推荐N个自身喜欢的产品。

3实验及分析

推荐算法的提升离不开大数据处理技术的运用，于是海量数据处理技术随着并行计算思想的发展变得越来越能适应推荐系统的需要[9]。Spark是一种基于内存进行计算的分布式批处理引擎，它兼具延迟小和支持迭代计算的优势，并且开发效率更高，容错性也更好[10]，因此经常应用于复杂的推荐场景中。

3.1实验环境配置

针对本文提出的KL-ALS算法，按如表1所示的环境下进行实验，以验证该算法的推荐性能。

3.2实验数据

本实验使用修正后的亚马逊智能产品评论数据集（Consumer Reviews of Amazon Products），包含235位用户对1521个产品的34655条评分记录。每一条评分记录包括用户id、产品id、产品名字、评分数据、评分时间戳、标签等。用户id为1-235的连续整数，产品id为1-1521的连续整数，评分数字为1～5的连续整数，数值越大表示评分越高。本实验按照8：2划分训练集与测试集。

3.3评价指标

准确率[（precision）]和召回率[（Recall）]是[topN]推荐的两种主要评价指标[11]，数值越大、性能越好。计算如公式（13）、（14）所示。

[Precision（N）=1Uu∈ULN（u）N]             （13）

[RecallN=1Uu∈ULN（u）L（u）]                 （14）

其中，[U]是測试集中所有用户的集合;[LN（u）]是针对用户[u]的[topN]推荐结果中，用户[u]喜欢的产品;[L（u）]是测试集中用户[u]评分过的所有产品。公式（13）和公式（14）都与[TopN]推荐个数[N]相关。

此外，F1值[12]通过统计[topN]推荐结果中含有至少[N]个相关产品的用户所占比例，评价推荐算法推荐相关产品的能力，数值越大、性能越好。计算方法如公式（15）所示。

[F1=2×Precision×RecallPrecision+Recall]                       （15）

3.4 实验设计与结果分析

实验1：确定参数[λ]的最佳取值

调节参数[λ]变化下，最终相似度[simmix（i，j）]的F1值变化情况，实验结果如表2所示。

由表2可知，当[λ]为0.7时，[simmix（i，j）]的F1值达到最优。

实验2：推荐个数变化下三种算法各项指标对比

验证本文推荐算法（KL-ALS）的有效性，将其与传统ALS协同过滤推荐算法和基于物品的协同过滤推荐（Item-CF）进行比较。根据实验1中取得的最佳参数的值，得出实验结果。

由图1的三组图可以看出，随着推荐个数N的增加，基于物品的协同过滤推荐算法（ItemCF）、基于ALS的协同过滤推荐算法（ALS）以及基于KL散度的ALS推荐算法（KL-ALS），准确率均呈降低趋势，召回率和F1值有明显提高。然而，KL-ALS推荐算法相比于传统ALS推荐算法和ItemCF推荐算法，在Precision、Recall和F1值三个指标上的提升较为明显，进一步验证了本文提出的混合推荐算法具有更好的推荐效果。

4结束语

文中提出了一种基于KL散度的ALS推荐算法（KL-ALS），在分布式大数据处理平台Spark进行实验。该算法将ALS算法计算的物品相似度和KL散度计算的物品相似度按照一定权重混合产生总体相似度，进而通过ALS算法训练模型，在亚马逊智能产品评价数据集验证其有效性。实验表明，本文提出的基于KL散度的ALS推荐算法（KL-ALS）优于其他类似方法，有效提高了整体的推荐质量。

参考文献：

[1] 朱扬勇，孙婧.推荐系统研究进展[J].计算机科学与探索，2015，9（5）：513-525.

[2] Kimball A，Michels-Slettvet S，Bisciglia C.Cluster computing for web-scale data processing[J].ACM SIGCSE Bulletin，2008，40（1）：116-120.

[3] Ghemawat S，Gobioff H，Leung S T.The Google file system[C]//Proceedings of the nineteenth ACM symposium on Operating systems principles - SOSP '03.October 19-22，2003.Bolton Landing， N Y， USA. New York： ACM Press，2003：29-43.

[4] 许海玲，吴潇，李晓东，等.互联网推荐系统比较研究[J].软件学报，2009，20（2）：350-362.

[5] 李现伟.基于Spark的推荐系统的研究[D].杭州：浙江理工大学，2017.

[6] Lee Y，Lee Y.Toward scalable Internet traffic measurement and analysis with Hadoop[J].ACM SIGCOMM Computer Communication Review，2013，43（1）：5-13.

[7] 李改，李磊.基于矩阵分解的协同过滤算法[J].计算机工程与应用，2011，47（30）：4-7.

[8] 张玉叶.基于协同过滤的电影推荐系统的设计与实现[J].电脑知识与技术，2019，15（6）：70-73.

[9] 胡俊，胡贤德，程家兴.基于Spark的大数据混合计算模型[J].计算机系统应用，2015，24（4）：214-218.

[10] 陈恒.一种基于Spark的大规模语义数据分布式推理框架[J].计算机科学，2016，43（S2）：93-96.

[11] Bobadilla J，Ortega F，Hernando A，et al.A collaborative filtering approach to mitigate the new user cold start problem[J].Knowledge-Based Systems，2012，26：225-238.

[12] Patra B K，Launonen R， Ollikainen V， et al. Exploiting bhattacharyya similarity measure to diminish user cold-start problem in sparse data[C]//Discovery Science，2014：252-263.

【通联编辑：唐一东】