一种基于多样性的top－N 推荐算法＊

王 森

（重庆理工大学计算机科学与工程学院，重庆400054）

1 引言

推荐系统（Recommendation System）作为信息过滤的一种重要应用，已经成为各主流网站不可缺少的个性化信息服务形式。它能够帮助用户从大量的互联网商品中发现自己感兴趣的商品（包括电影、书籍、餐厅、交通等）。目前的推荐算法很多，而基于预测评分值的推荐算法（简称为预测算法）运用最为广泛。这类算法主要是利用用户对已知商品的评分值、用户的交易记录、商品的内容等信息预测出用户对未知商品的评分值，进而根据评分值大小对商品排序，选择预测值最大的前N个商品构成top－N推荐列表。因此，这类算法都致力于预测准确率的提高。但是，在实际的推荐过程中，准确率并不是增强用户对推荐商品满意度的唯一标准，推荐商品的多样性也是一种重要指标。比如电影推荐系统，可能它具有很好的评分预测功能，有很高的推荐准确率，但是它可能经常推荐同一种类型的影片给观众，仍然不能令用户满意。因此，一个好的推荐系统应该同时兼顾推荐的准确性和多样性，避免向用户推荐过于相似的商品。然而，准确性和多样性两个标准是相互制约的，准确性的增加必然会导致多样性的降低，而多样性的增加也会导致准确性的下降，如何在这两者之间找到平衡是一个亟待解决的问题。

本文提出了一种新的推荐方法，该方法是建立在预测推荐算法基础上的，首先利用预测算法估计出用户对未知商品的评分值，然后利用用户－评分效用矩阵对所有商品进行聚类，并为每个商品类别赋予相应的权重，最后从不同的商品类中挑选商品进入最终的推荐列表。挑选过程中同时考虑商品的预测评分值和商品所属类别的权重，这样能够保证在一定准确度损失的条件下，大大提高推荐列表的多样性。

2 相关研究

越来越多研究者意识到准确率已经不是衡量一个推荐系统优劣的唯一标准。McNee S M［1］首先提出了新颖性（Novelty）和新奇性（Serendipity）两个指标，旨在使用户能够发现一些尚未接触的、感兴趣的商品。这两个指标的实质就是多样性。Smith B［2］等真正将多样性作为度量指标引入到推荐系统中，并提出了一种贪心选择算法（Greedy Selection），最大化推荐列表中的商品多样性。该方法是建立在预测算法基础上的。不同的是，在构造推荐列表时，不仅要考虑商品的预测值，而且还要考虑该商品与当前列表中其它商品的相异程度。这是一个组合优化问题，作者采用贪心算法进行求解。但是，当推荐列表较大时，该方法每次选择都要考虑商品两两之间的相异度，时间复杂度较高。Hurley N 等［3］也 从 优 化 的 角 度 来 解 决 多 样 性 问题，将其建模为一个二次规划问题，使用一个控制因子参数来灵活控制多样性和准确度。该方法与Smith B提出的方法进行了比较，能够获得相近的推荐列表，然而该方法的时间复杂度更高。Zhang M［4］利用聚类算法来推荐多样性的问题，实验表明该方法时间复杂度较低，而且在保证多样性的同时推荐准确率没有明显降低。但是，该方法只是对用户感兴趣的商品进行聚类，对用户尚未接触到的商品领域不予考虑，只是实现了用户兴趣范围类的商品多样化。本文提出的算法也是以聚类算法为基础，在保证推荐准确性的同时，在全局范围内实现商品的多样性化。

3 基于多样性的top－N 推荐算法

3.1 多样性度量标准

在推荐系统中，商品多样性的测量方法研究较少，Hurley N 等人提出计算列表中商品两两之间相异度的平均值，形式化定义如下：

假设I是商品的集合，U是用户的集合，L（u）是用户u（u∈U）的推荐列表，那么L（u）的多样性D（L（u））为：其中，d（i，j）代表商品i和商品j的相异性：d（i，j）＝1－sim（i，j）（sim（i，j）表示商品i和商品j的相似性）。该方法从理论上是合理的，但是由于sim（i，j）是基于用户－评分矩阵计算的，大多数情况下该矩阵为稀疏矩阵［5］，矩阵中存在很多的空值，在计算商品相似性时，很多算法设置一些默认值来代替。这些默认值会对公式（1）中的计算准确率产生很大的影响。例如，将默认值设为0，那么利用余弦公式计算相似性时，相似性可能趋近于0，而相异性则趋近与1，而这个值和实际不符，主要原因是太多的0参与计算，这些默认值对最后的结果起主导作用。

因此，本文中，我们使用Z－Scores方法来计算多样性。如公式（2）所示：

其中，I是商品的集合，D（I）和D（L（u））分别代表商品集合I的多样性和用户u的推荐列表L（u）中商品的多样性。SD（I）为I中商品两两相异性值的标准差。

该计算方法与公式（1）不同，公式（1）是一种商品绝对多样性的计算方法，而ZD（L（u））是一种相对多样性的计算方法，它是列表L（u）相对于I的多样性，由于引入了相异性值标准差，而不仅仅是如公式（1）中的平均值，使得多样性的表示更加准确。该方法同样利用0作为空值的默认值，相似性计算也采用于余弦相似性。

3.2 推荐方法

本方法是在预测算法的基础上进行的，不同的是，在top－N推荐列表的生成阶段，除了考虑商品的预测值，还考虑了商品所属的类别，对列表的多样性进行调整，具体步骤如下：

（1）使用聚类算法将商品划分为N类（N为推荐列表的长度）。商品类C＝｛C1，C2，…，Cn｝，该步骤使用k－means算法实现（聚类数据直接使用用户－评分矩阵），该算法可以在离线阶段实现。

（2）对各商品类赋予相应的初始权重。对于不同的用户，各商品类的初始权重是不同的。我们将用户－商品类别的权重关系用矩阵CW来表示，如表1所示，矩阵中的元素代表了各商品类的初始权重。

Table 1 Product category weight matrix表1 商品类别权重矩阵

这些初始权重是根据初始的推荐列表来计算的，具体方法为：假设用户u的初始推荐列表为L（u）（这里L（u）为预测值最大的前N个商品），每个用户u的商品类初始权重由初始推荐列表L（u）来计算。如矩阵中的元素CWij表示在用户ui的初始推荐列表L（ui）中，属于类Cj的商品个数。当CW13＝5时，表示在用户u1的推荐列表中，有5个商品是属于C3的。

（3）权重调整，这也是本方法的核心。按照初始的推荐列表来对各商品类的权重进行分配，可能会导致某些类的权重很大，这些类中包含的商品可能非常满足用户的兴趣，而另外某些类的权重非常小，这些类中包含的商品可能是用户以前接触很少的。为了提高推荐的多样性，使用户有机会接触到小类中的商品，我们对初始的商品类权重进行调整，算法如下：

算法1 权重调整

输入：用户u的初始推荐列表topNu，商品聚类结果C。

输出：针对用户u的商品类别权重CWu。

该算法涉及到两个参数：（1）推荐列表的大小N。（2）商品类的数目K。对于特定用户u，首先根据预测算法的推荐列表topNu来初始化每个商品类Ci的权重CWui。接着设定阈值Threshold来对各个类权重进行调整。当类Ci的权重大于Threshold时，找出当前权重最小的类CWuc，将其权重加1，并将Ci的权值减1。这样反复地调整，直到所有类的权重都小于Threshold为止。可以看出，如果Threshold值很大，而各个类的初始权重都小于Threshold，这样就不需要调整，最后的推荐列表和预测算法产生的列表完全一致。相反，如果Threshold值很小，那么每一个类的权重都需要调整。最后，各个类的权重应该是趋于均匀化。最后，在构造推荐列表时，通过设定阈值Threshold来控制准确性和多样性的平衡。

当各商品类的权重调整完成后，可以生成用户u最终的推荐列表topNu＿New，在推荐的过程中，当选出推荐商品ik时，将其所属的商品类Ck的权重降低，以降低其同类商品被推荐的概率，来保证最后商品的多样性。生成过程如下：

算法2 用户u的推荐列表生成

输入：用户u的初始推荐列表topNu，商品初始权重矩阵CW（CWuk为用户u对应的商品类Ck的权重）；

输出：用户u最终的推荐列表topNu＿New。

在本文提出的推荐算法中，共分为两个阶段。第一阶段为离线阶段，主要用到k－means聚类算法，时间复杂度为O（INmn），其中，I为算法的迭代次数，N为聚类的类别数，m为商品数，n为用户数。由于迭代次数有限，而且N＜＜m，该步骤的时间复杂度为O（mn）。第二阶段为在线阶段，主要涉及到文中的算法1和算法2。算法1 为权重调整阶段，将权重较大的类别变小，权重较小的类别增大，其时间复杂度为O（N）。算法2通过扫描初始列表来生成新的推荐列表，最坏的情况下其时间复杂度为O（m）。因此，算法总的时间复杂度为O（mn）。该时间复杂度远小于其他算法，具有高度的可扩展性。

4 实验

4.1 数据集和评估方法

我们采用MovieLens站点提供的数据作为实验数据，该站点提供了用户对电影的评分（评分值为1～5五个等级），目前该站点的用户超过50 000人，用户评分的电影超过3 500部。我们选取实验数据集中包含6 000个用户和3 900部电影以及100 000个评分数据。

为了测量算法的准确度，我们选择Cremonesi P［6］提出的评估方法。该方法以信息检索领域常用的查全率作为基础，在此基础上作了相应的变化，具体如下：

（1）随机选择数据集中2%的评分数据集T；

（2）在T中选择评分值为5 的数据作为测试集T＊；

（3）在测试集中，如果评分值r（r∈T＊）是用户u对商品i的评分，随机选择用户u未评分的300个商品，并将商品i加入其中；

（4）对这301个商品利用预测算法进行评分，并从中选择分值最高的前300个商品作为top－300推荐列表，如果商品i在推荐列表中，将常量hits加1，否则hits的值不变。

最后的查全率定义如下：

4.2 实验结果

本文方法是在预测算法的基础上进行的，我们选择三种不同的预测算法进行比较，分别是基于项目的协同过滤算法（items－based）、基于用户的协同过滤算法（user－based）以及SVD 算法。实验观察了随着Threshold值的变化，查全率（Recall）和多样性（Z－scores）的变化情况，如图1和图2所示。

Figure 1 Change of Z－scores under different thresholds图1 不同Threshold 下Z－scores的变化情况

Figure 2 Change of recall under different thresholds图2 不同Threshold 下Recall的变化情况

从图1可以看出，随着Threshold减小，三种方法的Z－scores值都是不断增加的，而且相对于其它两种方法，SVD 方法增加的幅度最大。因为利用SVD 方法得到的初始列表的多样值小于0，也就是说在所有商品多样性的平均值之下，所以随着Threshold减小，它的增幅最大。另外，item－based和user－based方法得到的初始列表的多样值大于0，也就是说在整个商品数据集的多样性之上，所以它们的增幅较小。此外还能看出，随着Threshold值的不断减小，三种方法的Z－scores值最后趋于相等，因为此时我们的算法均使用到了相等数目的商品类，即从同样的商品类中挑选商品作为推荐列表，最后的多样性值近似相等。

从图2可以看出，随着Threshold不断减小，三种方法的Recall值也是不断减小的，这也客观说明 了Z－scores和Recall是 对 立 的。当Threshold取10时，Recall下降很少，而Z－scores有一定程度的提高。因此，对于不同的推荐系统，只要合理地设置Threshold值，就达到平衡多样性和准确性的目的。

此外，我们还与smyth B提出的BGS（Bounded Greedy Selection）算法进行了比较。BGS算法也是基于预测算法的，它首先根据预测值对商品进行排序，然后选择评分预测值最大的前M个商品（M＞N），最后根据贪心算法从M个商品中选择N个商品构成推荐列表。实验中N均取20，预测算法均选择SVD 算法。当M取不同的值时，我们观察了BGS和本文算法在查全率和多样性上的变化，如图3所示。

Figure 3 Comparison of different methods’recall under the same Z－scores图3 不同方法在相同Z－scores是下的Recall比较

从图3 可以看出，随着Z－scores值的不断增加，各种方法的Recall都是下降的。在相同的多样性下，本方法的查全率都优于BGS方法，而且由于本方法只用到了一些简单的聚类算法和权重调整，时间复杂度更小，可扩展性更强。对于数据集中商品类别多、推荐列表较大的系统，本方法更加适用。

5 结束语

本文提出了一种基于多样性的推荐算法，来保证推荐列表中商品尽可能地多样化，以满足用户广泛的兴趣。实验表明，该方法在增加商品多样化的同时，查全率下降较少，使得多样性和准确性这两个推荐时的对立属性在一定程度上达到平衡。此外本方法还有如下优点：

（1）用户可以根据自身需要改变权重阈值大小，进而改变参与排序的商品类的数目，以此来改变推荐列表的多样性水平。

（2）本方法相当于是在预测算法的基础上进行的二次调整，可以很好地与目前一些高效的预测算法进行无缝对接。

（3）本方法的时间复杂度较小，离线阶段使用基本的k－means算法，在线阶段的核心步骤就是权重初始化和权重调整，只需少量的迭代计算即可完成，保证推荐系统具有很好的可扩展性。

在以后的工作中，我们将进一步研究对于特定的用户和数据集，如何设计优化算法来自动求出最优的阈值（Threshold），使算法更加智能高效。

［1］ McNee S M，Riedl J，Konstan J A.Being accurate is not enough：How accuray metrics have hurt recommender systems［C］∥Proc of Conference on Human Factors in Computing Systems，2006：1097－1101.

［2］ Smyth B，McClave P.Similarity vs diversity［C］∥Proc of the 4th International Conference on Case－based Reasoning，2001：347－361.

［3］ Hurley N，Zhang M.Novelty and diversity intop－Nrecommendation analysis and evaluation［J］.ACM Transactions on Internet Technology，2011，10（4）：Article 14，doi＝10.1145/1944339.1944341.

［4］ Zhang M，Hurley N.Avoid monotony：Improving the diversity of recommendation lists［C］∥Proc of the 2nd ACM Conference on Recommender System，2009：123－130.

［5］ Desrosiers C，Karypis G.A comprehensive survey of neighborhood－based recommendation methods［M］∥Recommendation Systems Handbook，New York：Springer，2011：107－144.

［6］ Cremonsi P，Koren Y.Performance of recommendation algorithms ontop－Nrecommendation tasks［C］∥Proc of the 4th ACM Conference on Recommender Systems，2010：39－46.