一种基于用户兴趣转移挖掘的流式推荐算法

陈建宗 刘永坚 解 庆 唐伶俐

(武汉理工大学计算机科学与技术学院 湖北 武汉 430070)

0 引 言

近年来，互联网规模和覆盖面的迅速增长带来了信息超载的问题，五花八门的信息从各个渠道涌入用户的视野中，使得用户难以从中发现对自己真正有价值的内容。不同于搜索引擎，个性化推荐系统通过“推送”的方式主动将用户感兴趣的信息和资源投送给用户，在很大程度上节省了用户主动去“拉取”未知信息并过滤出有效信息的成本，从而缓解了信息超载的问题。

虽然传统推荐算法在各个应用领域中已经取得了一定的成功，但是随着实际应用的不断发展，对推荐系统也提出了新的挑战。传统的推荐模型通常是静态模型，需要按照一定时间周期对模型进行定期更新，所以模型无法及时对外界变化做出相应的调整，进而导致模型的推荐质量在更新周期内不断下降。流数据中通常蕴含着丰富的信息，若推荐系统能及时捕捉到这些信息并加以利用，便能及时应对外界的变化，有效提高推荐结果的精准度和合理性。

同时，随着时间的迁移，历史数据的时间跨度变得越来越大，与最初相比，用户的兴趣偏好可能已经发生了很大的变化，然而传统的推荐系统通常认为用户的兴趣偏好是恒定不变的，依据“过时”的历史数据所做出的推荐不仅效果差，而且非常容易引起用户的反感。若推荐系统能够成功地捕捉并适应用户兴趣转移的现象，便能有效提高推荐的质量，推荐的结果也更容易给用户带来惊喜感，从而提高用户对于系统的忠诚度。

为了应对上述挑战，本文提出了一种改进的流式推荐模型streamGBMF(Stream Genre-based Matrix Factorization)。该模型根据资源的种类信息来构建资源的特征向量，打破了传统矩阵分解模型中用户和资源特征向量之间的全连接结构。同时，模型通过只对用户特征向量采取实时更新的方式，避免了传统增量矩阵分解模型中出现的整体拟合残差扩大的现象。为了使模型能够捕捉用户的兴趣转移现象，本文针对streamGBMF模型的特点，提出了两种新型的遗忘机制，能够有效区分用户的长期偏好和临时偏好，使模型能够在遗忘掉“过时”的用户历史数据的同时，保留用户的长期偏好特征。实验结果表明本文提出的方法有效提升了推荐效果。

1 相关工作

1.1 流式推荐系统

自Henzinger于1998年第一次提出流数据处理以来[1]，流数据处理逐渐成为了一个热门的研究领域。为使推荐系统能根据流数据中的信息实时更新模型参数，许多推荐系统研究采用了在线学习的方式。其中文献[2-4]将基于内存的推荐算法与增量更新策略相结合，此类增量更新策略主要是针对资源之间的相似度计算，然而其计算耗时与用户或资源的数量成正比，因此无法满足流数据环境下对算法时间复杂度的要求。

另一部分研究将传统矩阵分解模型与增量更新策略相结合。其中一种增量更新策略是面向特征矩阵的，如Huang等[5]基于线性变换的假设，将流数据按固定的时间段分成多个批次矩阵进行分解，最后通过线性方程将所有批次分解矩阵组合在一起，得到更新后的模型参数。但由于单个时间段内的流数据所构成的批次矩阵相比原始矩阵要更加稀疏，因此批次矩阵的分解效果并不理想，并且，该模型的更新延时取决于时间分割周期的大小和批次矩阵训练的耗时，因此其无法做到实时更新。另一种增量更新策略是面向特征向量的[6-7]，其核心思想是只更新与流数据相对应的用户和资源特征向量，而不相关的特征向量则维持不变。但是在传统矩阵分解模型中，用户特征向量和资源特征向量之间是全连接的，这种全连接结构在增量更新过程中会导致模型整体拟合残差不断扩大。

1.2 用户兴趣转移

随着用户审美的不断变化和外界难以预测的事件不断发生，使得用户的兴趣不断发生转移[8]，捕捉并且能够适应这些变化，是推荐系统改善推荐质量的关键[9]。其中最直接的方式就是“遗忘”掉过时的历史数据，现有的研究提出了很多遗忘机制，文献[10]提出了一种实例选择方法，其定义了一个固定大小的时间滑动窗口，模型在训练和预测时只考虑位于时间窗口内的数据，而位于窗口外的数据则会被直接丢弃，因此该方法不仅无法保留用户的长期偏好，还会加剧数据的稀疏性问题。Ding等[11]提出了一种实例权重方法，该方法根据数据生成时与当前的时间差，给予每一条数据一个指数型的时间衰减权重。但是同实例选择方法一样，实例权重方法在降低过时数据影响的同时，也会丢失用户长期偏好信息。为了解决这个问题，模型需要保存历史数据，由于历史数据量太大，无法都存储在主存储器中，“蓄水池”的技术被提了出来[12]。蓄水池中保存着历史数据的采样，在此基础上，Wang等[13]设计了一个新型高斯分类模型，从蓄水池和流数据中采样出信息量最大、最有用的数据。但是该模型将评分限制为二值类型，且把未观测的数据视为负样本，然而未观测的数据很大可能是因为用户从未接触过该资源，不完全等同于负样本。Chang等[14]假设用户和资源的特征向量服从布朗运动，其为每个特征向量设计了一个连续马尔科夫过程，但由于算法时间复杂度太高容易造成数据的积压问题。Sun等[15]指出在部分应用场景中，只有极少数人会对同一个资源进行多次评价，因此模型无法获得足够的信息来确定用户是否仍然喜欢或者不喜欢该资源，基于这个考虑，Sun提出对资源进行聚类，从而能够观察用户对于同一类资源的偏好是否发生了改变。然而，数据的稀疏性导致在聚类结果中部分并不相似的资源被分到了同一类别中，从而影响了最终的推荐结果。Matuszyk等[16]针对增量矩阵分解模型提出了五种不同的遗忘机制，但这些机制无法处理个体用户偏好的细微变化。

2 符号与概念预定义

2.1 符 号

为了便于后文理解，在介绍模型之前，本节中将对后文公式中的符号进行定义和说明。

•M,N：分别表示用户和资源的数量；

•K：表示高阶特征的维度；

•Uu(t),Vi(t)：分别表示用户u和资源i在时刻t的特征向量；

•R：所有观测评分的集合；

•KV(i)：表示资源i包含的种类信息集合；

•Ik：表示包含种类信息k的资源集合；

•tr：表示评分r生成的时间；

•τU(u),τU(u,k)：分别表示用户u最后一次评分的时间和用户u最后一次对包含种类信息k的资源评分的时间；

•Ttrain,Tpredict：分别表示在训练和预测阶段的衰减系数。

2.2 动态基线估计

评分是一种显性的用户反馈数据，评分的高低间接反映了用户对资源的兴趣偏好，但同时，评分也会受不同用户之间评价标准的差异所影响。例如，在一个评分取值范围为1至5分的评分系统内，对于一个高要求的用户，“3分”意味着一个中性的评价，而对于一个容易满足的用户来说却代表的是消极的评价。为了消除用户之间评价标准差异带来的影响，本文采用了Koren提出的动态基线估计方法[9]，用户u对资源i的动态基线估计被定义为：

bui(t)=μ+bu(t)+bi(t)

(1)

式中:μ代表所有观测评分的均值;bu(t)和bi(t)分别表示用户u和资源i的观测偏差值，bu(t)可理解为用户u评分的严苛程度，而bi(t)可理解为资源i受大众喜爱的程度。

本文在动态基线估计的基础上，将用户u对资源i进行评价时表达的偏好情绪定义为eui(t)：

eui(t)=rui(t)-bui(t)

(2)

当eui(t)大于0时，代表用户表达的是积极的情绪，即模型认为用户u喜欢资源i。动态基线估计是模型能够捕捉用户兴趣转移的重要一环，因为在消除用户之间评价标准的差异带来的影响后，模型能更准确地学习到用户的真实偏好。

3 模型设计

3.1 离线训练

在离线训练过程中，模型根据历史观测评分来训练模型参数。由于传统的矩阵分解模型是全连接的结构，因此在增量更新的过程中，局部的更新会导致整个模型的拟合残差不断扩大。为了避免这个问题，本文决定根据资源的种类信息来构建资源特征矩阵，这些资源的种类信息是由专家进行标注，且在实际生活中是非常常见的，例如电影领域中的“动作片”、“冒险片”，和音乐领域中的“流行乐”、“摇滚乐”等。另外，应用资源种类信息来构建模型能够使推荐结果具有良好的可解释性。

由于每一个资源的种类信息数量是有限的，因此构建的模型中每个资源都只与少数几个特征相关联，从而打破了传统矩阵分解模型的全连接结构：

(3)

通过式(3)构建得到的资源特征向量，其特征值Vik能反映出资源i在同样具有特征k的所有资源中的地位。之后，模型根据历史评分数据，通过最小化整体拟合误差训练得到用户特征矩阵，其目标函数表达式为：

(4)

式中:eui(tr)由式(2)计算得到，表示评分r生成时用户u对资源i所表达的情绪值。至此，模型已经完成了离线训练的过程，即根据历史数据训练得到用户和资源的特征矩阵。

3.2 在线学习

在本文模型的在线学习过程中，将系统接收到的流数据分为两种类型：用户反馈数据、新用户注册和新资源创建事件。

1) 用户反馈数据。当系统接收到一条新的评分数据rui时，模型需要根据该评分数据来实时更新模型参数，以从中获取用户最新的兴趣偏好。基于离线训练中的设定，资源的特征向量是根据其固有属性生成的，其值相比较于用户的特征向量要为稳定，因此模型并不需要像更新用户特征向量一样频繁对资源特征向量进行更新。本文将时间线按照固定的时长进行分段，资源特征向量在同一时间段内被视为恒定的值。时间分段粒度的设置应根据具体的应用场景来决定，在本文模型的实验中，其值被设为一天。基于以上考虑，模型通过下式对新的评分数据rui所对应的用户特征向量进行更新：

λ‖Uu‖2

(5)

由于模型只对相应的用户特征向量进行更新，因此，与该用户相连的其他资源特征向量不会受到更新的影响。同时，不同于传统面向特征向量的增量更新策略，本文模型在更新时将该用户所有的历史评分数据都纳入增量更新的考虑范围，因此，该用户历史评分的拟合误差也能得到有效控制。这两个特点使得本文模型在增量更新的过程中能够很好地避免模型整体拟合残差不断扩大的问题。

2) 新用户注册和新资源创建事件。在流数据的设定下，系统中不断有新用户注册和新资源被创建。对于每一个新的用户和资源，模型需要对相应的特征矩阵进行扩维，并对其特征向量进行初始化。一方面，模型假设新用户u的兴趣偏好符合大众的兴趣偏好，其特征向量的初始化如下：

(6)

另一方面，模型依然根据新资源的种类信息来初始化其特征向量：

(7)

式中：参数σ用来控制新用户和新资源的初始特征向量的分布，本文模型中将其值设为0.1。

3.3 遗忘机制

为了将用户的长期偏好与临时偏好进行区分，本文提出了两种新型的遗忘机制：奇异点移除法和时间衰减置信度法。值得注意的是，对于仅有少量数据的用户，为了避免丢失其中重要的信息，模型中设定了一个阈值，评分数量低于该阈值的用户不会受到遗忘机制的影响，本文实验中将此阈值设为10。

1) 奇异点移除法。奇异点移除法的思想是，在用户的历史评分数据中，若某个评分符合用户的日常兴趣偏好，则模型对该评分的拟合误差理应较小。反之，若模型对某个历史评分的预测误差显著大于其他的评分，则意味着该历史评分与用户平常的兴趣偏好不一致，属于用户的临时偏好或异常行为。基于以上思想，模型根据用户u的历史评分，计算出评分预测误差的标准差，记为sdU(u)。若某一历史评分rui满足式(8)，则会被标记为奇异点评分并被移除。

(8)

式中：参数α用来控制遗忘机制的灵敏度。值得一提的是，为了避免丢失流数据中的信息，模型只对历史数据中的奇异点评分进行移除。

2) 时间衰减置信度法。不同于奇异点移除法，时间衰减置信度法根据资源的种类信息将用户对于单个资源的兴趣转移问题转换为用户对于某一类资源的兴趣转移问题，并将用户兴趣转移问题分为以下两种情况：

(1) 当用户在不同时间点对同一类资源表达了不同的兴趣偏好时，该如何确定用户当前对这类资源的兴趣偏好。

(2) 当用户已经很长时间没有与某一类资源产生交互，该如何确定用户当前对这类资源的兴趣偏好。

对于第一种情况，显然模型需要学习的是用户最新表达的兴趣偏好，而以前的数据则被视为过时数据。因此，在模型训练的过程中，对于每一个评分r，根据tr与τU(u,k)的时间差，为其设置一个权重wtrain(r)：

(9)

式中：wtrain(r)的取值范围为(0,1]，对于时间越久远的评分，其权值越低。参数Ttrain是用来控制过时数据对模型影响的衰减参数。在此基础上，式(5)被扩展为：

Uu(t)TVi(t))2+λ‖Uu(t)‖2

(10)

对于用户兴趣转移的另外一种情况，其背后的逻辑是用户会持续与自己感兴趣的类型资源产生交互，直到对其不再感兴趣为止，反之，用户会尽量避免与他们不喜欢的类型资源产生交互。基于该假设，模型为用户特征向量的特征值Uuk(t)定义了一个置信度参数Confuk，代表模型对该特征值的把握性。若模型认为特征k是该用户的临时偏好，模型将通过降低置信度Confuk的值来降低特征k对于评分预测的影响：

ConfuKUuK(t))Vi(t)+bui(t)

(11)

为了验证上述假设中时间衰减置信度Confuk分别对于积极和消极偏好的影响，本文设计了三种不同的衰减策略进行比较。令Uuk(t)≥0代表用户u对包含特征k的资源持积极的兴趣偏好，反之则代表用户u对包含特征k的资源持消极的兴趣偏好。如表1所示，作为对照，策略A不衰减任何偏好特征的影响，而在策略B中，模型同时衰减积极和消极偏好特征的影响，最后在策略C中，模型只衰减积极偏好特征的影响。

表1 Confuk的设置策略

表1中：wpredict(u,k)的值由式(12)计算得到，参数Tpredict是用来控制置信度Confuk的衰减参数：

(12)

4 实验评估

为了评估模型的有效性，本文将模型与不同的遗忘机制相结合，并评估其模型性能。本文实验数据集采用公开电影评分数据集MovieLens 1M，数据集中包含2000年到2003年间6 040名用户对3 952部电影的1 000 209个评分，评分均为1至5分的整数，其中每名用户至少贡献了20个评分，且每部电影都被标记了至少一个种类信息。

4.1 对比模型

本文将提出的steamGBMF模型与一些具有代表性的算法进行比较：

• PMF[17]：Probabilistic Matrix Factorization是基于高斯观测噪声的概率线性模型。

• DA-PMF[6]：Dual-Averaging Method for PMF是一种面向特征向量的增量矩阵分解模型，其通过将当前特征向量与流数据中的特征相结合的方式来更新模型参数。

• timeSVD[9]：bias-SVD[18]的时间变种模型，可以捕捉用户评价标准随时间的变化现象。

4.2 实验设定

为了模拟流数据环境，本文将数据按时间顺序进行排序，并将排序后的数据按照下方两种实验设定进行分割：

1) T8：选择前80%的数据作为训练集，剩下20%的数据作为测试集。

2) T9：选择前90%的数据作为训练集，剩下10%的数据作为测试集。

基于上述实验设定，有部分用户的数据只存在于训练集中或只存在于测试集中，这虽然加大了模型预测的难度，但该现象也与现实中流数据设定的情况相符。本文通过均方根误差(RMSE)来评估模型的性能。为便于实验对比，对比模型中的公共参数将被赋予相同的值，因MovieLens 1M数据集中种类信息一共有18种，所以特征向量的维度K设为18，正则化系数λ被设为0.1，学习率η的值为0.01。

4.3 实验结果

各模型的对比实验结果如表2所示，在流数据的环境中，PMF表现一般，说明了静态模型在流数据环境下的劣势。通过对比timeSVD模型与streamGBMF模型，可以发现在去除了动态基线估计的影响后，本文流模型在性能上有所提升。通过对比DA-PMF模型与本文模型的实验结果，验证了本文流模型通过资源的种类信息来构建资源的特征矩阵，并在增量更新时采取只对用户特征向量进行训练的方式，在一定程度上避免了由全连接结构带来的拟合残差扩大的问题，取得了比传统增量矩阵分解模型更优的实验结果。

表2 模型性能对比(RMSE)

为了评估模型中遗忘机制带来的影响，将本文提出的两种遗忘机制与Sensitivity-based Forgetting[16]方法进行比较，Sensitivity-based Forgetting方法对于每一条新的数据，计算其对于用户的特征产生了多少变化，若新的数据大幅改变了原有的用户特征，则这条数据被认为与用户之前的偏好不相同，因此将被移除。此外，为了对照实验，本文将没有结合任何遗忘机制的实验结果加入进行对比，记为NoForgetting。由图1和图2所示，Sensitivity-based Forgetting方法的效果与NoForgetting相差无几，意味着该方法在移除奇异点的同时，也丢失了部分流数据中的重要信息。而本文提出的奇异点移除法(Outliers Discarding)的实验结果要优于Sensitivity-based Forgetting方法，证明了奇异点移除法中采取只移除历史数据中的奇异点的策略是有效的，该策略很好地保留了流数据中的用户兴趣转移信息。实验结果表明，本文提出的时间衰减置信度法(Time-decay Confidence)在T8和T9的实验设定下都取得了最优的实验结果，证明了该遗忘机制的优越性，表明该方法能使模型在捕捉用户兴趣转移现象的同时，有效保留了用户的长期偏好信息。

图1 T8设定下遗忘机制的实验对比

图2 T9设定下遗忘机制的实验对比

4.4 参数影响

在这一节中将对时间衰减置信度法中高阶参数的影响进行实验分析。

1)Ttrain的影响。Ttrain是模型训练过程中用来控制过时数据对于模型训练影响的衰减参数，其值越大，过时数据对于模型的影响越大。如图3所示，当Ttrain取值过低时，在训练过程中会过度忽略历史数据中的重要信息，导致推荐质量下降，而当其取值过大时，则会导致时间衰减的效果降低，使模型无法倾向于捕捉用户最新的兴趣偏好信息。实验结果表明，当Ttrain取值为700天时，模型取得了最优的实验结果。

图3 Ttrain参数的影响

2)Tpredict的影响。Tpredict是用来控制用户陈旧特征对于模型预测结果影响的衰减参数，其值越小，模型对于用户陈旧特征的真实性把握就越小。图4和图5展示了本文模型在T8和T9实验设定下，当Tpredict取不同值时的实验对比结果。其中对积极和消极的用户特征同时衰减的策略B取得了最优的实验结果，而仅对积极的用户特征衰减的策略C取得了次优的实验结果，这与本文中提出的假设“用户会持续避免与不喜欢的类型的资源接触”有一定出入。但与不作任何衰减的策略A相比，衰减策略B与衰减策略C均起到了一定的优化效果，且当Tpredict取值为60天时，取得了最优的实验结果。

图4 T8设定下预测策略的实验对比

图5 T9设定下预测策略的实验对比

5 结 语

本文提出了一种基于资源种类信息的流式推荐模型streamGBMF，避免了传统增量矩阵分解模型中存在的拟合残差扩大问题。并基于streamGBMF模型的特点，提出了两种改进的遗忘机制，可以有效区分用户的长期偏好与临时偏好，从而使模型能够更准确地把握用户的兴趣偏好。实验结果验证了本文算法的有效性。后续将研究矩阵预填充技术，用于改善评分矩阵稀疏性问题。