刘 旭，李玲娟

(南京邮电大学 计算机学院，江苏 南京 210023)

0 引 言

随着互联网的发展和进步，人们在享受网络 资源极大便利的同时，也受到信息超载的困扰，推荐系统是解决信息过载问题的主流方法。其中最著名的便是协同过滤推荐算法[1]。该算法有基于用户的和基于项目的两种类型，两者都基于用户的历史记录信息，前者结合与目标用户有类似偏好的其他用户兴趣，后者 基于项目间的相似性，把用户可能感兴趣的项目快速呈现。

尽管协同过滤推荐算法在个性化 推荐中有明显的优点：基于用户行为和项目相似性，不需要先验知识，在用户行为比较丰富的时候，推荐效果不错，但是有关用户兴趣随时间变化的事实被忽略了。在基于项目的协同过滤算法中，计算最近邻项目时，将不同时段的项目评分同等 对待，以致寻找到的目标项目的最近邻，有可能不是真正意义上的最近邻居，使推荐结果存在较大偏差。另外，基于项目的协同过滤算法搜索目标项目的最近邻居时，需要遍历整个项目空间，费时又费力[2]。

文中以基于项目的协同过滤算法为研究对象，设计了一种基于项目聚类和时间衰减的动态协同过滤算法(dynamic collaborative filtering algorithm based on item clustering and time decay，ITDCF)。首先根据用户的评分对项目进行聚类，接下来在计算相似度时引入时间衰减因子反映用户兴趣的变化，在预测评分时也考虑时间衰减。最后，生成Top-N推荐列表，提高了推荐的准确性和效率。

1 相关研究

1.1 协同过滤算法

协同过滤(collaborative filtering，CF)算法的基本思想是：基于过去的行为或现有用户组的意见来预测数据，并使用与当前用户或当前项目类似的邻居数据来生成推荐结果[3]。该算法的输入是用户-项目评分矩阵，输出数据一般分为两类：当前用户对项目偏好的预测值和Top-N的推荐项目列表。其基本步骤包括：数据的收集与处理、生成用户-项目评分矩阵、计算相似度、产生最近邻、预测评分和产生Top-N推荐[3]。

基于用户的协同过滤算法(UserCF)[4]的主要思想是：首先，输入评分数据集和当前用户ID，以查找出与当前用户有相似偏好的其他用户，这些用户被称为最近邻居；然后，利用邻居用户预测项目的评分；对所有项目的评分按照从大到小进行排序，将评分居前的N个项目推荐给当前用户。

基于项目的协同过滤算法(ItemCF)[4]的核心思想是：首先构建一个项目相似度矩阵来描述两个项目之间的相似性；找出与当前项目相似的k个最近邻项目，然后根据k个最近邻计算当前用户没有看到的每一项目i的用户评分；最后，将用户对所有项目的评分从大到小排序，向当前用户推荐所有项目中得分最高的前N项。

尽管UserCF算法在推荐领域得到了广泛的应用，但也面临着很多挑战。像电商网站，一方面，项目的数量比较稳定，但用户数目更新频率较高，当用户数量远大于项目数量时，计算用户间的相似性将越来越耗时并占用更多内存[5]。另一方面，基于用户的算法生成的推荐结果可解释性较差[6]。而ItemCF算法时间复杂度相对较低，并能根据用户的历史行为做出推荐解释，可以比较容易令用户信服。

1.2 基于项目的协同过滤算法

基于项目的协同过滤算法(ItemCF)的基本步骤是：处理数据、生成用户-项目评分矩阵、计算项目相似度、产生最近邻、预测评分和产生Top-N推荐。

该算法利用式(1)所示的余弦相似度计算两个项目之间的相似度。

(1)

其中，N(i)是评价了项目i的用户，N(j)是评价了项目j的用户，|N(i)|是评价了项目i的用户数，|N(j)|是评价了项目j的用户数，|N(i)∩N(j)|是同时评价了项目i和j的用户数。相似性的范围为[0,1]，值越接近1，越相似。

此外，基于所获取的k个最近邻项目后，用式(2)预测当前用户对目标项目的兴趣。

(2)

其中，N(u)是用户u评价过的项目集合，S(i,k)包含了和项目i最相似的k个项目，项目j属于和用户评价过的最相似的项目的集合，sim(i,j)是项目i和j的相似度，ruj是用户u对项目j的兴趣。根据数据集的类型，这里的ruj=1。

虽然ItemCF算法在项目数明显少于用户数的场合，相对于UserCF算法有一定的优势，但是如果项目过多，计算项目之间的相似度矩阵的代价偏高，而且算法也忽略了用户兴趣随时间变化对推荐效果产生的影响[7]。

2 ITDCF算法

文中为进一步提升ItemCF算法效率而设计的基于项目聚类和时间衰减的动态协同过滤推荐算法ITDCF包括：项目聚类、时间加权、产生最近邻、预测评分、产生推荐等步骤。

2.1 项目聚类

针对基于项目的协同过滤算法在寻找目标项目的最近邻居时，因需要遍历整个项目空间而导致耗时大的问题[7]，ITDCF算法先对项目进行聚类，选择评分数量达到一定标准的项目为初始簇类中心，可以认为这些初始中心就是最受用户喜欢的项目；然后遍历所有项目，计算其与初始中心的相似度，并归入相似度最高的簇中，从而使目标项目最近邻居的计算从全局空间转到簇内空间，大大降低了计算量，提升推荐的时效性。

项目聚类的具体处理过程如下：

输入：类簇的数目K和数据集合。

输出：K个簇。

步骤1：选择初始中心点。

根据构建的用户-项目评分矩阵R，从项目集合中检索所有n个项目，计算每个item的评分数量V。将所有的V值按降序排列，选择前K个V值大的项目作为初始的聚类中心，得到K个聚类簇{C1,C2,…,Ck}。

步骤2：利用余弦相似度公式计算item分别到初始化聚类中心的距离。

步骤3：按照与聚类中心距离最近(相似度最高)的原则，将各个item分配到最邻近的簇中，并记录下item与每个聚类中心的相似度。

步骤4：算法结束，输出聚类结果。

聚类时，以评价数量最多的K个item作为初始的聚类中心，减少了迭代次数，提高了算法效率。在这里，需要通过尝试来确定最优的K值。

采用余弦相似度公式，将项目间的相似度作为评判距离的标准，相似度越大则距离越近。采用余弦相似度公式还可以避免由于各属性衡量单位的差异性而导致的“相似不相同”问题[8]。

2.2 时间加权

考虑到用户兴趣会随着时间而改变[9]，ITDCF算法将时间信息加入到推荐算法中，以在特定时间向用户推荐其最感兴趣的项目。ITDCF算法对基于项目的协同过滤推荐算法的改进 有两个方面：计算相似度时加入时间衰减因子和预测评分时加入时间衰减因子。其中时间衰减函数选择的是艾宾浩斯曲线。

艾宾浩斯曲线是由德国心理学家艾宾浩斯发现的，描述了人类大脑忘记新事物的规律[10]。将之应用到推荐系统上就是，用户对越久远的项目越不感兴趣，在向用户进行推荐时，将他以前看到过的项目进行适当地降权。但是如果用户最近又对其中一个项目进行了操作，那么在推荐时就增加这类物品的权重。这样得到的最近邻项目更能符合用户的兴趣。

时间加权[11]的具体任务是：拟合艾宾浩斯曲线，编写加权函数。

随着时间的变化，人的兴趣会逐渐衰减，但衰减趋势为先快后慢[12]。所以指数函数在一定程度上更符合兴趣的衰减特性。拟合所依赖的带参数指数函数为：

Wt=AeBx+CeDx

(3)

艾宾浩斯遗忘曲线的最终拟合公式为：

(4)

其中，Tui表示用户u对项目i操作的时间，Tuj表示用户u对项目j操作的时间，单位为min。

2.3 产生最近邻

在加入时间权重后，认为项目i和j相似是因为在同一时间内，二者同时被多个用户选择过[13]。考虑到艾宾浩斯遗忘曲线对用户偏好的影响，用户选择时间间隔越短，项目间的相似度越高，文中采用余弦相似函数[14]来判断两个项目之间的相似度，得到计算项目i和j相似度的改进公式为：

(5)

其中，N(i)是评价了项目i的用户，N(j)是评价了项目j的用户，|N(i)|是评价了项目i的用户数，|N(j)|是评价了项目j的用户数，用户u属于同时评价了项目i和项目j的用户集合，新增的Wt为时间衰减函数。

因为在计算簇集的时候保存了每个项目和聚类中心的相似度，所以根据记录直接将目标项目划分到相似度最大的类簇中；再取类簇内与目标项目最为相似的前K个项目作为最近邻居。

2.4 预测评分

用户最近的行为比用户远期的行为更能反映用户当前的兴趣[15]。通过项目相似性预测用户对项目的兴趣，并考虑用户最近的行为。预测时采用如下公式：

(6)

其中，N(u)是用户u评价过的项目集合，S(i,k)包含了和项目i最相似的k个项目，项目j属于和用户评价过的最相似的项目的集合，t0表示当前时间，tuj代表用户u操作项目j的时间；对于时间衰减参数α，不同数据集中的值是不同的[16]，用户的兴趣变化越快，值越大。

最后，根据预测评分公式和得到的K个最近邻项目，预测用户的兴趣度，排序后得到Top-N推荐。

基于以上步骤，ITDCF算法的流程可归纳为图1。

图1 ITDCF算法的推荐流程

3 算法性能测试

3.1 实验数据集及划分

MovieLens数据集[17]是研究人员广泛使用的一种经典数据集，用于测量推荐算法的精度。

文中主要使用U.data文件，其中用户的评分值为1至5分，代表评价从低到高。timestamp是自1970年1月1日零点后到用户提交评价的时间的秒数。

3.2 实验环境

文中的实验硬件环境如下：Windows7；intel(R)Core(TM) i5-6200U CPU @2.30 GHz 2.40 GHz；4G内存；64位操作系统，基于x64的处理器。

实验在JetBrains PyCharm 5.0.3平台下运行；使用Python语言，环境为python3.6.3；Python包有：numpy、math、matplotlib.pyplot等。

3.3 实验方案

按照每个用户选择项目的时间先后对U.data的项目进行排序，然后将用户最后选择的项目作为测试集，并把这之前用户对项目的选择记录作为训练集。利用改进后的算法构建用户兴趣模型，向每个用户推荐N个物品，并且利用准确率、召回率和F1值对推荐算法的性能进行评价。

为了检验ITDCF算法的性能，文中将之与Popular算法和基于项目的协同过滤算法ItemCF进行对比，其中的Popular算法是按照物品的流行度高低向用户推荐当天最受欢迎物品的算法。

给定时间T，项目i最近的流行度pi(T)可以定义为：

(7)

其中，三元组(u,i,t)表示用户u在t时刻评价了项目i，Train是测试集数据集，α是时间衰减参数。

通过试验取最佳类簇数7；设定目标项目的最近邻项目的阈值参数从0增加到45，增加的间隔为5；进行10次实验；观察召回率、准确率和F1值的变化趋势。

召回率为推荐列表中预测的用户感兴趣的项目与系统中用户真喜欢的所有项目的百分比[18]。计算公式为：

(8)

其中，R(u,N)是给用户u提供的长度为N的推荐列表，T(u)是测试集中用户评价过的项目集合。

准确率为推荐列表中用户喜欢的项目在所有被推荐的项目中所占的百分比[18]，计算公式为：

(9)

其中，R(u,N)表示算法给用户u提供的长度为N的推荐项目列表，T(u)为测试集中用户喜欢的物品集合。

召回率Recall说明了推荐列表的覆盖性，Precision说明了推荐列表的准确率，都是衡量推荐性能的重要参数[18]。用F1值来拟合Precision与Recall，其中P为Precision，R为Recall。F1值越大，表明算法的推荐效果越好。计算公式如下：

(10)

3.4 实验结果分析

Popular算法、ItemCF算法和ITDCF算法在不同推荐项目数N值下的准确率、召回率和F1值分别如图2至图4所示。

图2 MovieLens数据集上各算法在不同N值下的准确率

图3 MovieLens数据集上各算法在不同N值下的召回率

图4 MovieLens数据集上各算法在不同N值下的F1值

由图2可以看出，对MovieLens数据集，ITDCF算法在不同推荐项目数下的准确率都更高，这是由于用户的兴趣随时间而改变，在计算相似度时考虑了用户对项目的遗忘，因此提高了预测项目评分的准确性。同时可以看出选择合适的推荐项目数N，可以获得最好的推荐效果。

由图3和图4可以看出，ITDCF算法的召回率和F1值在整体上也比Popular、ItemCF高。

4 结束语

以提高推荐的准确率为目标，基于协同过滤和流行度推荐的思想，引入聚类和进一步考虑兴趣随时间的变化因素，设计了一种基于项目聚类和时间衰减的动态协同过滤推荐算法。该算法根据评分数量选择初始簇类中心，减少了迭代次数，并缩小了寻找目标项目最近邻的候选集；通过在基于项目的协同推荐算法中加入时间衰减因子提高了推荐的精度。MovieLens数据集上对ITDCF算法、Popular算法和ItemCF算法的准确率、召回率和F1值的对比实验结果表明，ITDCF算法在推荐的准确性和效率方面有所提高。