基于时序变化与用户聚类的提高总体多样性的方法

Aggregate Diversity Improvement Method Based on Time Series Change and User Clustering

摘要: 针对传统协同过滤算法数据稀疏性、相似度计算片面、多样性不足等问题，本文提出一种基于时序变化与用户聚类的提高总体多样性的方法(Aggregate diversity improvement method based on time series change and user clustering, ADI-TC, n = 3)。通过加入时间因子对预测评分进行加权提高用户评分实时性；采用奇异值分解法(Singular Value Decomposition, SVD)进行数据填充缓解数据稀疏性问题；根据用户偏好对用户进行聚类，结合用户评分和类别相似度计算用户综合相似度；通过跨类选取近邻的方式提高协同用户多样性进而提高推荐结果多样性。在MovieLens数据集实验表明本文方法相对于传统基于用户的协同过滤算法，在最近邻数为20时，MAE下降4.5%，总体多样性可以提高2%。说明本文提出的方法能在保证推荐准确性的前提下提高总体多样性。

Abstract: Aiming at the problems of traditional collaborative filtering algorithms, such as data sparsity, partial similarity calculation and insufficient diversity, this paper proposes an aggregate diversity improvement method based on time series change and user clustering (ADI-TC, n = 3) to improve the aggregate diversity. By adding time factor, the prediction rating is weighted to improve the real-time performance of user rating. Singular Value Decomposition (SVD) is used for data filling to alleviate the problem of data sparsity. Users were clustered according to their preferences, and user comprehensive similarity was calculated by combining user rating and category similarity. The nearest neighbor across classes methods were selected to improve the diversity of collaborative users and improve the diversity of recommendation results. Experiments on the Movielens data set show that compared with the traditional user-based collaborative filtering algorithm, the MAE of the proposed method decreases by 4.5% when the nearest neighbor number is 20, and the aggregate diversity can be improved by 2%. It shows that the method proposed in this paper can improve the aggregate diversity while ensuring the accuracy of recommendations.

1. 引言

近年来推荐系统已经发展得非常成熟，很多学者教授已经针对推荐算法的准确性做了各方面的改进，各大互联网公司也都有在应用它，但现有的推荐算法大多以提高推荐列表的准确性为目的。然而，推荐列表的高准确性并不一定意味着高水平的用户满意度，也不一定能提高商品的销量 [1] [2]。一方面那些被少部分用户购买的、目标用户会喜欢的项目难以被推荐 [3]；另一方面，产生的推荐列表中的项目与用户过去的行为太相似，从而不能迎合用户的广泛喜好 [1] [4]。Fleder D等人 [5] 的研究表明，推荐系统的使用反而会降低销售的多样性，不利于商业模型。提高推荐列表的多样性有助于解决以上问题。

多样性的提高可以增加商品的曝光率、提高推荐系统对商品长尾的发掘能力。多样性和准确性本身就存在一定的矛盾，一个指标的提高必然会导致另一个指标的降低。这种情况下，如何在尽可能地提高多样性的情况下依然保证系统足够的准确性，就成为了一个热门的研究内容。

2. 研究背景

随着互联网的发展以及网上购物的兴起，个性化推荐算法的研究更是越来越深入，推荐多样性和准确性的结合才能使得用户对购物平台一直保持新鲜感。为了提高推荐的质量，避免推荐结果冗余化，推荐多样性的概念开始出现，它要求推荐列表中的项不仅要满足用户的兴趣，而且项与项之间还要尽可能不相似。多样化推荐能够为用户产生更个性化的结果。推荐系统的多样性包含两个层次——总体多样性和个体多样性。总体多样性是从推荐结果总体考虑，计算所有用户推荐列表的商品覆盖率，即推荐列表中总体数量占所有项目的比例。个体多样性关注是否能够将不同领域的物品推荐给用户，个体多样性的研究旨在避免向个体用户推荐过于近似的物品，从而提高用户的体验，增加用户的满意度。

目前很多学者开始了多样化推荐的研究。刘慧婷等人 [6] 提出一种基于物品推荐期望的Top-N推荐方法，在向用户进行推荐时，可以通过控制全体物品的推荐期望，达到提高推荐总体多样性的目的。邓明通等人 [7] 提出基于用户偏好和动态兴趣的多样性推荐方法，有效缓解了用户冷启动问题，并能在保证准确率的前提下提高推荐结果的多样性。张立毅等人 [8] 提出一种能够在寻优精度和多样性之间权衡的个性化的多样性优化方法，采用一种依据用户历史偏好和项目类别专家评分的推荐技术，然后依据用户多样化偏好程度进行后过滤技术，实验表明该方法能够有效地提高推荐列表的多样性。赵鹏等人 [9] 提出了一个新的针对新颖性和多样性推荐的矩阵分解模型，该模型可以同时优化新颖性、多样性和准确性三个目标，实验结果表明，在准确性、系统多样性、个体多样性和新颖性方面，所提模型均具有卓越的性能。

上述研究虽然都提高了推荐多样性，但解决稀疏性对于推荐质量的影响还有很大的提高空间，并且没有考虑时间因子和用户类别偏好对用户相似度计算的影响。因此本文提出一种基于时序变化与用户聚类的提高总体多样性的方法，用时间因子对用户评分进行加权，用以提高推荐的准确性和多样性；根据用户喜好对其聚类，结合用户评分和类别相似度计算用户综合相似度。方法使用了SVD填充和跨类选取近邻的操作，缓解数据稀疏性以及提高推荐多样性。

3. 基于时序变化与用户聚类的提高总体多样性的方法

本文提出的基于时序变化与用户聚类的提高总体多样性的方法引入优化的时间因子函数加权修正用户评分，解决用户兴趣随时间变化的问题，用以提高推荐质量；使用SVD对用户–项目评分矩阵进行填充，缓解了稀疏性问题；根据用户兴趣偏好利用谱聚类方法对用户进行聚类，提高类内相似度；用改进的综合相似度计算方法对聚类结果进行类内和类外的综合选择，提高推荐多样性。本文方法流程图如图1所示。

Figure 1. Flow chart of the methods this paper

图1. ADI-TC，n = 3流程图

3.1. 时间因子

用户对事物的兴趣在时间变化过程中会发生改变，若是忽略这点做推荐会导致推荐的结果具有片面性。张凯辉等人 [10] 认为用户的兴趣变化与遗忘规律相近，因此采用艾宾浩斯遗忘规律作为时间因子的计算方法。周静等人 [11] 使用logistic权重函数作为时间因子函数，对评分实现加权，降低时间过久的数据评分权重，增加近期数据评分权重。本文引用logistic权重函数 [12] 对用户评分进行加权，解决推荐中实时性的问题，定义如公式(1)所示。

$f\left(t_{ui}\right)=\{\begin{array}{l}1t_{\max }=t_{\min }\\ \frac{1}{1+\exp \left[-\left(\frac{t_{ui}-t_{\min }}{t_{\max }-t_{\min }}\right)\right]}{t}_{\max }\ne t_{\min }\end{array}$ (1)

其中， $t_{ui}$ 表示用户u对项目i的评分时间， $t_{\min }$ 表示用户u的最早评分时间， $t_{\max }$ 表示用户u的最新评分时间，即早期的评分权重会更小，对预测的贡献也就越小。由此可见， $f\left(t_{ui}\right)$ 取值范围为[0.5, 1]，用户对项目的评分时间越接近用户最新评分时间，权重越接近1，本次评分对预测的贡献越大。

3.2. 基于SVD的矩阵分解

在推荐系统技术中，协同过滤算法一直占据着主导地位。协同过滤算法是通过过滤目标用户的次要信息，并利用其他相关用户回馈的有用信息来计算用户之间的相似度，以此对目标用户进行推荐 [13]。数据稀疏性是协同过滤推荐算法面临的主要挑战，为解决稀疏性问题，各学者提出了各种方法。本文采用SVD对矩阵进行降维以及矩阵的填充，从而解决矩阵稀疏的问题。SVD是一种常用的矩阵分解技术，是特征值分解在任意矩阵上的推广，并不要求要分解的矩阵为方阵。假设矩阵A是一个m × n的矩阵，那么定义矩阵A的SVD如公式(2)所示：

$A=U\Sigma V^{\text{T}}$ (2)

其中， $W$ 是一个m × m的矩阵； $\Sigma$ 是一个m × n的对角矩阵，主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值； $V$ 是一个n × n的矩阵。 $U$ 和 $V$ 都是酉矩阵，即满足 $U^{\text{T}}U=I$， $V^{\text{T}}V=I$。

3.3. 谱聚类

聚类被引入到个性化推荐算法中，将类似用户聚集到相同簇中，直接在每簇内进行最近邻的查询，大大降低了搜索范围和计算量。本文中聚类算法一方面综合评分和类别相似度得到综合相似度，凸显用户的兴趣偏好以提升最终的推荐精度；另一方面，聚类便于后续跨类取用户近邻的操作，有利于提升系统推荐的多样性。

谱聚类算法(Spectral Clustering Algorithm)是近年来出现的一类性能优越的聚类算法，与传统的K-means聚类算法和层次聚类算法相比，谱聚类能在各种不规则数据空间上执行，并且容易收敛到全局最优。基于谱聚类的算法易于实现、速度快、具有良好的可解释性。谱聚类能对任意形状的数据进行聚类，是基于图论中谱图理论基础 [14] [15]，将聚类问题转化为图的优化划分问题。主要步骤如下：

步骤1：使用高斯核函数对引进的用户–类别矩阵进行处理，获得相似矩阵S；

步骤2：构建相似矩阵S的邻接矩阵W和度矩阵D，其中邻接矩阵和度矩阵都是对称矩阵；

步骤3：构建拉普拉斯矩阵 $L$， $L=W-D$ ；

步骤4：采用基于权重的规范化割(normalized cut, Ncut)聚类切图方式 [16] 将图分割为k个子图，将图的切割转换成求解拉普拉斯矩阵特征值(向量)的问题，并计算其各自对应的特征向量，特征向量组成特征矩阵；

步骤5：将由k个特征向量组成的特征矩阵行标准化；

步骤6：取标准化后的矩阵的每一行作为一个k维的样本子集，通过K均值聚类对新样本集进行聚类，聚类数为k₂；

步骤7：获得最终的簇划分 $C=\left(c_1,c_2,c_3,\cdots ,c_{k_2}\right)$。

3.4. 综合相似度

根据聚类结果，从与目标用户相同簇和不同簇中的用户中挑选邻居，本文使用改进的相似度方法，将用户评分相似度与用户类别相似度进行加权求和得出综合相似度，计算公式如下(3)所示。

$sim\left(u,v\right)=\lambda rsim\left(u,v\right)+\left(1-\lambda \right)csim\left(u,v\right)$ (3)

其中， $rsim\left(u,v\right)$ 为用户评分相似度， $csim\left(u,v\right)$ 为用户类别相似度，均采用Pearson相似度。λ为权重系数，用于调整用户评分相似度在整个用户相似度中所占权重，取值范围在[0, 1]。

3.5. 预测评分

在推荐系统中对用户进行推荐时，利用用户综合相似度计算出目标用户的最近邻居，改善了传统算法只依赖用户评分相似度而不考虑用户类别的问题，提高了协同用户多样性进而提高推荐多样性。

目标用户 对项目 的预测评分公式如(4)所示

$r_{ui}={\bar{r}}_u+\frac{{\displaystyle {\sum }_{v\in N_u}sim\left(u,v\right)}\times \left(r_{vi}-{\bar{r}}_v\right)}{{\displaystyle {\sum }_{v\in N_u}sim\left(u,v\right)}}$ (4)

其中， $r_{ui}$ 表示用户u对项目i的预测评分， $N_u$ 表示用户u的邻居集和， ${\bar{r}}_v$ 表示用户v的平均评分。

4. 实验与讨论

4.1. 数据集

实验中采用美国明尼苏达大学GroupLens项目组提供的MovieLens数据集 [17]，其中包括943个用户对1682部电影的10万条评分数据，电影类别总共有18种，评分标准为1到5之间的整数。数据集中用户对某一电影的评分值越大说明用户越喜欢这部电影。为了评估方法性能，将数据集的80%作为训练集，其余的20%作为测试集。

4.2. 评价指标

本文用平均绝对误差(MAE)作为准确性的评价指标、Coverage作为总体多样性的评价指标。其公式如(5) (6)所示：

$\text{MAE}=\frac{{\displaystyle {\sum }_{u,i\in T}\left|r_{ui}-{r^{\prime }}_{ui}\right|}}{T}$ (5)

$\text{Coverage}=\frac{\left|{\displaystyle {\cup }_{u\in U}R\left(u\right)}\right|}{\left|I\right|}$ (6)

其中，u为用户，i为项目， $r_{ui}$ 为实际评分， ${r^{\prime }}_{ui}$ 为预测评分。 $R\left(u\right)$ 是根据用户在训练集上的行为给用户作出的推荐列表；T是用户在测试集上的行为列表；I为所有的项目集合；U为用户集合。

4.3. 实验结果与分析

4.3.1. 权重系数λ对推荐结果的影响分析

文章使用用户评分和类别的综合相似度进行相似度计算，两者之间的权重系数λ是一个非常重要的参数。为了获取最佳权重系数，该方法选取最近邻个数k = 30，聚类数分别为4、5、6、7、8。随着λ的变化MAE的变化如图2所示。

Figure 2. MAE corresponding to different weight coefficients

图2. 随不同权重系数对应的MAE值

可以看出，虽然聚类数不同，但MAE的变化趋势大致相同，随着λ的增大，MAE先减小后增大，说明只考虑用户评分相似度，忽略用户类别相似度会使推荐准确性下降。当λ在[0.1, 0.8]范围内时，MAE随λ的增大而减小；当λ在[0.8, 0.9]范围内时，MAE随λ的增大而增大，说明文章方法的最佳权重系数λ为0.8。

4.3.2. 聚类数对推荐结果的影响分析

在确定了权重系数λ为0.8后，根据龚敏等人 [18] 和顾明星等人 [19] 的研究情况，该方法选取最近邻个数为k = 30，λ = 0.8，聚类数为[5, 12]之间的整数，然后在对应不同的聚类数下计算不同用户近邻数下的MAE。实验结果如图3所示。

Figure 3. MAE corresponding to different cluster numbers

图3. 随不同聚类数对应的MAE值

可以看出，MAE随聚类数的增加先减少后增大。当聚类个数较少时，聚类结果比较模糊，同一类别中用户偏好的项目差别较大，难以精确反映用户对类别的偏好；而当聚类数较多时，个别类包含的用户数量较少，甚至出现一个类别中只有一名用户的情况，无法在类内寻找足够多的“邻居”，因此聚类个数的多少对推荐准确度有很大影响，必须通过实验寻找一个相对合适的聚类数目。通过图3可以看到，当聚类数为7时MAE最低，说明该实验聚类数设定为7。

4.3.3. 跨类数n对推荐结果的影响分析

跨类数是指选取近邻数时在非用户类中每类选取的近邻数。该方法是通过跨类选取近邻的方式在保证准确性的前提下尽量提高多样性的，上述实验都是为了保证方法的准确性，下面的实验就是要进行跨类数的选取。该方法选取λ = 0.8，聚类数为7，最近邻个数为k = 20、25、30、35、40。随着n的变化MAE和Coverage的变化分别如图4和图5所示。

Figure 4. MAE corresponding to different cross-class numbers

图4. 不同跨类数对应的MAE值

Figure 5. MAE corresponding to different weight coefficients

图5. 随不同权重系数对应的MAE值

可以看出，结合MAE与Coverage的实验结果图，选择MAE最小且Coverage最大所对应的跨类数，应该取跨类数n为3。

4.3.4. 实验对比结果

为了验证本文提出的方法能有效提高推荐质量，选取基于用户的协同过滤算法 [20] (A user-based collaborative filtering algorithm, UBCF)、基于谱聚类的推荐方法 [14] (The recommended method based on spectral clustering, RM-SC)、基于时间因子和SVD填充的推荐方法 [21] [22] (Recommended methods based on time factors and SVD population, RM-TSVD)和基于时序变化与用户聚类的提高总体多样性的方法(n = 0) (aggregate diversity improvement method based on time series change and user clustering, ADI-TC, n = 0)作为本文的对比方法。选取λ = 0.8，聚类数为7，n = 3，近邻数k = 20、25、30、35、40。MAE和Coverage对比结果分别如图6和图7所示。

Figure 6. MAE comparison of different methods

图6. 不同方法的MAE对比

Figure 7. Coverage comparison of different methods

图7. 不同方法的Coverage对比

可以看出，总体上五种方法的MAE随着近邻数的增大而减小，文章方法准确度最高。从整体上看MAE和Coverage的变化趋势，RM-SC相比于其他方法变化的并不明显，说明推荐使用聚类算法时，给用户进行推荐只能在同一类中搜索邻居，搜索范围有限，当近邻数较少时前者可以搜索到相似度最高的几名用户做邻居，而一旦近邻数增多，由于矩阵的稀疏性问题导致搜索结果并不准确，预测准确度反而不如不用聚类的算法可靠。

另外，RM-SC比UBCF的MAE小，说明根据用户偏好进行谱聚类可以有效提高推荐准确性；RM-TSVD也比UBCF的MAE小，说明加入时间因子和进行SVD填充可以有效缓解数据稀疏性进而提高推荐准确性；但RM-SC和RM-TSVD两种方法得出的Coverage都大致小于UBCF的Coverage，说明一些经过优化的推荐方法虽然可以增加推荐准确性，但会在一定程度上牺牲推荐的总体多样性。

综上所述，ADI-TC，n = 3对比其他方法，MAE最小且Coverage增加，说明该方法在MAE最小的情况下选定的跨类数n不仅可以保证推荐准确性而且还可以有效地提高推荐总体多样性。因此，该方法可以提高推荐系统的推荐质量，更能提高用户满意度，实验验证了方法的有效性。

5. 结论

本文提出结合时序变化与SVD填充并且根据用户兴趣对其聚类相结合的推荐方法。通过加入时间因子函数对预测评分进行加权；采用SVD进行数据填充；根据用户偏好对用户进行聚类；通过跨类选取近邻的方式提高推荐列表的总体多样性。实验证明本文提出的方法能在保证推荐准确性的前提下提高总体多样性，有一定的实际意义。

但本文提出的方法仅提高了推荐的总体多样性，并未涉及个体多样性，同时对于时序变化对推荐多样性的影响也未作深入探讨，下一步将对这两方面作进一步研究。