缺失数据建模的改进型ALS在线推荐算法

邢玉莹,,

(江南大学 数字媒体学院,江苏 无锡 214122)

0 概述

随着信息技术的快速发展,推荐系统成为解决信息过载问题的重要工具之一。其中,个性化推荐[1]作为现代推荐系统的主流,在实际中被广泛应用,其根据用户行为来为用户提供个性化服务,以满足各类用户的不同需求。

协同过滤推荐算法是应用最广泛的推荐算法之一,它使用用户对物品的评分矩阵来训练推荐模型,然后进行预测并向用户推荐其感兴趣的事物或产品[2]。随着推荐系统数据量的不断增多,矩阵分解方法[3]成为获取用户特征和物品特征的重要技术,其核心设计思想是将高维评分矩阵分解成低维用户特征矩阵与物品特征矩阵的乘积。在已有研究中,基于矩阵分解的协同过滤算法是面向用户评分[4]的,但用户评分的来源和可靠性存在局限性,在很多场景中无法获得准确的用户评分[5]。

多数推荐系统收集到的数据是用户正向选择行为的记录,如购买记录、浏览历史等隐式反馈信息。用户在信息系统中无意留下的大量隐式反馈信息很容易被获得。但与用户评分相比,隐式反馈信息存在2个主要缺陷:只包含用户正倾向信息而缺乏负倾向信息,这类问题称为单类问题[6];存在数据噪声,如用户购买某物品作为礼物但用户自己不一定喜欢该物品。此外,隐式数据是用户日常行为的记录,数据稀疏性导致其存在大量缺失数据,在训练时,矩阵分解方法无法充分提取用户和物品特征。

针对以上问题,目前较流行的处理方法是将缺失数据都作为负样本并设置较小的权重,将其加入基于权值的模型中,并采用带权的交替最小二乘(weighted Alternating Least Square,wALS)矩阵分解方法进行离线批量训练[6-7]。但是,数据缺失并不是随机产生的[8-9],其针对每个用户成为负样本的概率不同,设置统一的权重不适合实际推荐场景。此外,用户的兴趣往往随时间变化而变化,推荐系统的时效性对用户的满意度有极大影响,为了更好地服务用户,实时更新推荐模型非常重要[10]。而利用观测数据和全部缺失数据并采用矩阵分解来训练推荐模型,会大幅降低训练效率,导致矩阵分解技术与在线学习算法的结合较难实现。

为解决上述问题,本文提出一种缺失数据建模的改进型交替最小二乘在线推荐算法NeALS,其依据物品相似度启发式地为用户选择正样本,并构建用户近邻评分矩阵代替原始矩阵进行模型训练,以减小数据噪声。此外,该算法根据物品流行度构建流行置信度函数,采用加权法对缺失数据建模,并处理缺失数据中的负样本。为及时获取用户兴趣的动态变化,本文将基于元素的改进型ALS算法与在线学习算法相结合,以提高在线学习效率。

1 相关工作

定义Rm×n为具有m个用户、n个物品的二元隐式反馈矩阵。Rui∈R,Rui=1表示用户u选择了物品i,Rui=0表示用户u对物品i没有行为记录。Pm×k和Qn×k分别表示用户和物品的特征矩阵。其中,k是特征因子的个数。pu∈P和qi∈Q分别为用户和物品的特征向量。

1.1 基于隐式反馈的矩阵分解推荐算法

矩阵分解算法的设计思路是用户行为受多种因素的影响,且不同因素的影响程度不同[11]。因此,用户u对物品i的偏好可定义为:

由于隐式反馈存在单类问题,因此传统基于矩阵分解的推荐模型不能直接应用于隐式反馈的推荐场景中。解决单类问题的总体思路是引入负样本,将缺失数据都作为负样本并为其设置较小的权重。

文献[7]提出基本带权潜在因子模型的损失函数为:

其中,wui是样本实例的置信度,λ是正则系数。

确定加权矩阵的构成后,wALS是优化矩阵分解模型的常用方法。然而,引入负样本将导致wALS训练负担的增加,其时间复杂度为O((m+n)k3+mnk2),严重影响训练效率。为降低时间复杂度,文献[12]提出随机块坐标下降法(Randomized block coordinate descent,Rcd),文献[13]提出基于元素的交替最小二乘(element-wise Alternating Least Square,eALS)矩阵分解算法,该算法交替更新模型参数中的每个坐标元素,直至其达到联合最优值。

以上方法均认为用户有过正向行为的物品为用户喜欢的物品,忽略了隐式反馈中存在的数据噪声。隐式反馈不能明确反映用户对物品的偏好程度,其对用户历史反馈不进行区分,由此导致矩阵分解时特征提取不明确。本文提出的NeALS算法根据物品相似度来为用户选择正样本,对与用户相关的物品和不相关的物品进行区分,并依据物品的流行度构建流行置信度函数,然后对缺失数据进行建模,以适应实际隐式反馈推荐场景。

1.2 基于隐式反馈的在线推荐模型

传统推荐算法(如timeSVD++)通过结合时间信息来提高预测准确率,但这类算法仍使用离线批量训练的模式[14-15]。由于隐式反馈是系统自动记录下的用户行为,其会连续不断地产生,因此使用离线批量训练将无法及时利用用户最近的反馈信息。这些用户最近的反馈信息具有较大的研究价值,它们反映了用户近一段时间的兴趣,因此,其会影响推荐结果。

为及时获取用户兴趣的变化,避免“新用户”(这里指没有任何反馈信息的用户)的冷启动问题,文献[16]在微博推荐场景下提出RMFX模型,对基于隐式反馈数据流构建实时推荐模型进行进一步研究。文献[12]提出适用于在线更新的Rcd算法。文献[13]将基于元素的最小二乘矩阵分解方法与在线学习算法进行结合。

但以上在线模型对用户新反馈信息和历史反馈信息没有进行区分,这在一定程度上限制了在线学习的效果。为此,本文对新用户反馈信息进行加强学习,同时,对缺失数据的置信度作实时更新,以达到提高在线学习效果的目的。

2 改进型ALS在线推荐算法

2.1 近邻评分矩阵构建

由于隐式反馈是用户日常行为的记录,仅依靠用户行为对用户的偏好进行预测较困难。比如,某用户购买了一件物品作为赠送他人的礼物,但该物品并非用户自己所喜欢的,又或者用户购买后发现该物品并不令人满意。在这种情况下,用户的隐式反馈不一定能反映出其真实的喜好,即存在数据噪声。

为解决上述问题,本文利用物品的相似度来启发式地区分与用户相关的物品和不相关的物品[17],将与用户选择过的物品相似度都较高的物品作为正样本,构建近邻评分矩阵S代替原始矩阵R,从而在使用矩阵分解方法训练模型时,有效减小数据噪声的影响。构建近邻评分矩阵的具体步骤如下:

1)使用余弦相似度来计算物品i和物品j的相似度:

2)计算用户u对物品i的评分:

sui=RuSimi

(4)

其中,Sim是n×n维的物品相似矩阵。

3)为每个用户选择评分在前ρ个的物品添加在其近邻评分矩阵S中。

目前,多数推荐系统会定期计算物品相似度,因此,不会导致计算成本增加。构建近邻评分矩阵的时间复杂度为O(mn)。

2.2 流行置信度定义与ALS算法改进

缺失数据包括负样本和潜在正样本,因此,使用加权法对缺失数据建模的关键步骤是如何区分负样本和潜在正样本。

对缺失数据每个样本实例赋予不同的权值时,会消耗大量的存储空间。为解决该问题,wALS方法和Rcd方法为每个缺失数据设置相同的权重,然而,针对同一用户,在实际推荐场景中不同物品被称为负样本的概率不同。

在推荐系统中存在流行偏置问题,即推荐系统往往会向用户推荐流行产品,物品越流行,被推荐的次数越多[18-19]。因此,用户获取物品受物品流行度的影响,即用户更容易获取流行的物品。针对流行度偏置问题,本文认为,如果一个物品流行度高,但是用户并没有对其发生正向行为,则该物品对此用户成为负样本的概率较大。依据物品的流行度构建不同物品在加权矩阵分解推荐模型中的置信度函数如下:

其中,fi是R中物品i的频数,其表示i的流行度。流行度不为0的物品成为负样本的概率与流行度正相关。对于新物品,则设置统一权重。

结合上文构建的近邻评分矩阵,基于物品流行度加权的隐式反馈推荐模型损失函数为:

其中,wui是正样本的置信度,wui=sui。因为隐式反馈矩阵是一个二元矩阵,已有研究认为所有能观察到的隐式反馈都可以作为正样本,而没有区分与用户相关的物品和不相关的物品。本文结合近邻评分矩阵为用户选择正样本,并根据用户对物品的评分来对其设置不同权重。

为提高矩阵分解的训练效率,采用eALS算法对式(6)关于puf求导,并令一阶导数等于0,计算得:

(7)

(8)

将式(8)进一步优化为:

使用以上优化方法可将式(7)改写为:

(11)

同理,有:

(12)

其中,Si表示所有选择物品S的用户集合向量。

缺失数据建模的改进型ALS算法伪代码如下:

算法1缺失数据建模的改进型ALS算法

输入近邻评分矩阵S,潜在特征维度k,正则化系数λ

输出用户特征矩阵P,物品特征矩阵Q

1.初始化P,Q;对(u,i)∈S,wui=sui;//对每个物品i,根//据式(5)计算w0(i)

3.计算Cq和Cp;

4.while没有达到终止条件 do

5.for u=1 to m do

6.for f=1 to k do

8.更新puf=式(11);

10.end for

11.end for

12.更新Cp;

13.for i=1 to n do

14.for f=1 to k do

16.根据式(12)更新qif;

18.end for

19.end for

20.更新Cq;

21.end while

22.输出P和Q

该算法在一次迭代中,更新Cp和Cq的时间复杂度分别为O(mk2)和O(nk2)。更新一次用户u的特征向量pu的时间复杂度为O(|Su|k+k2),更新m个用户特征向量的时间复杂度为O(|S|k+mk2),其中,|S|是矩阵S中非零元素的个数。同理,更新n个物品特征向量的时间复杂度为O(|S|k+nk2)。因此,算法完成一次迭代的总时间复杂度为O(|S|k+(n+m)k2),与wALS算法相比,降低了k倍。该算法的效率受近邻评分矩阵S中所选择正样本的数量影响,而eALS和Rcd算法的时间复杂度为O(|R|k+(n+m)k2),其与原始矩阵的样本数量相关。因此,相比eALS算法和Rcd算法,缺失数据建模的改进型ALS算法的效率是否提高,取决于|S|和|R|的大小。

2.3 在线推荐模型

缺失数据建模的改进型ALS算法仍采用离线批量训练的模式,这种模式存在训练效率低且信息利用不及时的局限性。为此,本文将缺失数据建模的改进型ALS算法扩展为在线模型,提出一种缺失数据建模的改进型ALS在线推荐算法NeALS,算法框架如图1所示。

图1 NeALS算法框架

与离线批量训练模式不同,在线训练模式无需一次性重复训练一批样本,而是随着用户新的反馈数据来实时更新推荐模型。新反馈以数据流的形式进入推荐系统后,算法更新用户u和物品i对应的用户特征向量pu和物品特征向量qi。新反馈只会影响用户u和物品i,并不会影响整个用户和物品特征矩阵。

在用户的反馈中包含2种情况:1)反映用户新兴趣的反馈,这类反馈反映出用户近期喜好,对于推荐系统具有很高的价值;2)用户习惯行为的反馈,推荐系统已经从历史反馈中充分学习到用户和物品特征,需要弱化学习[10]。对于反映用户新兴趣的反馈应加强学习,给予比历史反馈更高的权重wnew。据此,本文提出的NeALS算法伪代码如下。

算法2NeALS算法

输出更新后的P、Q

1.顺序读取隐式反馈(u,i)

2.if u是一个新用户 do 随机初始化pu;

3.if i是一个新物品 do 随机初始化qi;

4.if (u,i)∈S do wui=sui;

5.else

6.sui=1;

7.wui=wnew;

8.end if

10.根据式(11)更新pu;

11.更新 Cp;

12.根据式(12)更新qi;

13.更新 Cq;

14.直至没有新的隐式反馈数据

15.输出P,Q

NeALS算法更新一次pu的时间复杂度为O(k2+|Su|k),更新一次qi的时间复杂度为O(k2+|Si|k),更新Cp和Cq的时间复杂度为O(k2)。因此,算法完成一次在线学习的时间复杂度为O(k2+(|Su|+|Si|)k)。

3 实验结果与分析

本节通过离线实验和在线实验分析各参数对算法推荐结果的影响,并将本文算法与其他基于隐式反馈的推荐算法进行比较。

3.1 数据集

本次实验数据来自MovieLens-1M数据集,该数据集包含6 040个用户和3 706部电影,共1 000 209条评价记录,其中,用户至少对20部电影有评分,电影评分为1分～5分。为将该数据集转换成隐式反馈数据集,将有评分的数据值均设为1,没有评分的数据值设为0。

实验分为离线实验和在线实验,根据用户浏览电影的记录按照时间顺序从小到大排序数据集。离线实验采用离线批量训练的模式,分别选择前30%、50%、70%的数据作为训练集,其余数据作为测试集,分析训练集数据量的大小对推荐结果的影响。在线实验选择前70%的数据作为训练集,后30%的数据作为测试集,根据实际中的推荐系统场景模拟动态数据流。首先,使用训练集离线训练推荐模型,为每个用户生成一个Top-N的推荐列表;然后,将测试集中的数据以数据流的形式输入,更新推荐模型并重排推荐列表;最终,由测试得到的相关数值来分析推荐算法的性能。

3.2 评价标准

本实验评价标准采用Top-N推荐中常用的2个指标:命中率(HR)和归一化折扣累计利润(NDCG)。HR是指系统每次向用户推荐N个物品,用户选择的物品占推荐物品的比例。NDCG反映用户喜欢的物品在推荐列表中的位置准确性。各算法的评价结果为执行5次实验结果的平均值。

3.3 离线实验

本文根据文献[12]经验地设置潜在特征维数为50,迭代次数为25,正则系数为0.01。在NeALS算法中,近邻评分矩阵的正样本数ρ的大小是重要影响因素。

表1所示为不同的基于隐式反馈的推荐算法在训练集为30%、50%和70%下得到的Top-30的HR值和NDCG值。NeALS算法为每个用户选择不同数量的正样本构建近邻评分矩阵,ρ的取值分别为50、100、500,流行度不为0的物品设置负样本权重正相关于流行度,流行度为0的物品设置负样本权重w0=0.2。wALS算法和Rcd算法的正样本权重w1=1,将缺失数据都看作负样本进行训练,负样本的权重为w0=0.2。eALS算法正样本权重w1=1,流行度不为0的物品设置负样本权重正相关于流行度。

表1 不同基于隐式反馈的推荐算法推荐效果对比

由表1可以看出:

1)随着为每个用户选择的正样本数量的增加,HR和NDCG均逐渐降低。这说明引入一些用户可能不感兴趣的伪正样本,导致在使用矩阵分解训练模型时提取出了错误的特征信息。

2)在不同大小的训练集中,使用ALS模型比使用Rcd模型在矩阵稀疏的情况下效果更好。

3)在离线实验中,无论训练集数据大小如何变化,根据物品相似度为每个用户选择50个正样本构成近邻评分矩阵,应用NeALS算法进行模型训练,其推荐效果明显优于其他对比方法。因此,在线实验中选取ρ=50。

本文NeALS算法较其他算法的推荐效果有所提高,原因是NeALS算法使用近邻评分矩阵代替原始矩阵训练模型,能够合理区分出与用户相关和不相关的物品。此外,根据流行度对缺失数据进行加权,同时将新物品也一同加入模型中训练,更适合基于隐式反馈的推荐场景。

3.4 在线实验

在线实验将测试集中的用户反馈以数据流的形式输入系统,平均每10 000次连续推荐进行一次推荐效果评价。本次实验研究新反馈的权重对推荐效果的影响,由于wALS算法的时间复杂度较高,不适合应用于在线推荐,因此本次实验只对比NeALS算法和Rcd算法、eALS算法在在线模式下Top-30的推荐效果。

3.4.1 参数分析

由于用户新反馈中包含用户新的兴趣,因此这类反馈对系统而言具有比历史数据更高的价值。图2所示为新反馈的权重对在线学习算法结果的影响。由图2可以看出,当wnew设置为1时,新的反馈数据和历史反馈数据具有相同的权值。随着wnew的增加,NeALS算法和Rcd算法、eALS算法的NDCG均逐步提高。Rcd算法在wnew=2处NDCG达到最大值,NeALS算法和eALS算法在wnew=8时达到最好的推荐效果。对新反馈的加强学习在一定程度上强化了用户的短期兴趣。但随着wnew的继续增加,3种算法的NDCG均呈下降趋势。因此,可以得出结论:平衡用户近期兴趣和历史兴趣对推荐系统十分重要。但无论wnew取何值,本文NeALS算法的推荐效果均优于eALS算法和Rcd算法。

图2 新反馈的权重wnew对3种在线推荐算法的影响

3.4.2 算法性能分析

在流入样本数相同时,Rcd算法选择wnew=2作为新反馈的权重,eALS算法和NeALS算法选择wnew=8作为新反馈的权重。图3所示为3种算法的在线推荐结果对比。

图3 3种算法Top-30在线推荐结果对比

流入样本数为0时,是算法在离线批量训练时得到的结果。由图3可以看出:

1)在线模型比离线模型在推荐效果上更有优势。在线训练能够及时捕获用户的兴趣变化,而离线训练存在信息利用不及时的局限性。此外,对于一个没有任何历史记录的新用户,若采用离线模型,推荐给他的物品几乎是随机的。而在线模型中,当捕捉到用户第一个行为记录时,就会有效地提高推荐效果,随着用户反馈的增加,推荐效果会进一步提高。因此,在线模型在一定程度上能够改善离线模型的冷启动问题。

2)eALS算法在开始有样本流入时HR和NDCG先下降再上升。NeALS算法和Rcd算法均随着流入样本数的增加,HR和NDCG先上升最后达到平稳,达到平稳后,随着流入样本数的增加,2种算法推荐效果均没有特别明显的变化。这是因为电影更新速度较慢且用户的兴趣变化不大,当一个用户看过很多电影后,其之后的选择可能不会有太大变化。

3)NeALS算法取得了比eALS算法和Rcd算法更好的在线推荐效果,这说明结合物品近邻信息能够在一定程度上减小原始数据中的数据噪声,且构造流行置信度函数对缺失数据建模,可以有效提高推荐的精确度。

4 结束语

本文建立一种基于快速矩阵分解和隐式反馈的在线推荐模型。针对隐式反馈存在数据噪声的问题,使用物品相似度信息启发式地选择与用户相关度较高的物品作为正样本,并构造近邻评分矩阵代替原始数据矩阵进行模型训练。同时,提出缺失数据建模的改进型ALS算法,根据物品流行度构建流行置信度函数并作为缺失数据的权值。在此基础上,结合基于元素的优化思想对ALS算法进行改进,最终提出基于隐式反馈的在线推荐算法NeALS。在真实数据集MovieLens上进行的离线和在线实验结果表明,NeALS算法能够有效提高推荐的精确度和效率。下一步将考虑不引入负样本,而直接对用户的行为进行建模,并将改进后的算法应用于电子商务中。