融合用户兴趣分布变化和特征差异的协同过滤推荐算法

2019-02-13 01:36毕孝儒
计算机时代 2019年1期

毕孝儒

摘  要: 针对传统协同过滤算法没有考虑由时间引起的用户兴趣分布变化、致使其推荐精度不高的问题,提出了融合用户兴趣分布变化和特征差异的协同过滤推荐算法。采用窗方法估计用户在整个项目空间上的兴趣分布,设计时间遗忘曲线因子用以确定用户兴趣分布变化函数,最后结合兴趣分布变化相对熵和用户特征差异计算用户相似程度并进行项目推荐。实验结果表明,该算法能够有效追踪用户对项目兴趣变化,提高了数据稀疏情况下的推荐精度。

关键词: 协同推荐; 兴趣分布变化; 相对熵; 特征差异

中图分类号:TP311          文献标志码:A     文章编号:1006-8228(2019)01-71-04

Abstract: Aiming at the problem that traditional collaborative filtering recommendation algorithm failed to consider user interest change of distribution to cause poor recommending precision, a collaborative filtering recommendation algorithm combined with user interest change of distribution and characteristic difference is proposed in this paper. Window estimation method is applied to get user interest distribution in total item space, and the factor of time forgetting curve is designed to define the function of user interest change of distribution. Finally, by combining Kullback-Leibler divergence of user interest change of distribution and characteristic difference, user similarity is calculated to finish the item recommendation. Experimental result shows that the algorithm can effectively trace the interest change of distribution and raise the recommendation precision.

Key words: collaborative filtering recommendation; user interest change of distribution; Kullback-Leibler divergence; characteristic difference

0 引言

隨着云计算和大数据技术的快速发展,互联网上海量数据资源导致的信息过载问题日益突出。作为解决该问题的有效方法,推荐技术随之诞生。其中,协同过滤推荐技术作为主流推荐技术,已经成功应用到各个行业,比如:亚马逊、天猫、淘宝等电子商城的个性化购物推荐、旅游行业景点精准推荐、餐饮行业的餐饮商家推荐等。目前,随着数据规模急剧增加,协同过滤推荐技术存在冷启动、数据稀疏性等问题[1]。

针对以上问题,郝雅娴[2]提出了K-近邻矩阵分解推荐系统算法,其通过将高维的稀疏评分矩阵降维,挖掘原始数据中用户和项目的潜在特征,来补全矩阵中的缺失值,以预测用户对未评分项目的实际评分,虽然该算法缓解了数据稀疏性问题,但也存在计算量大的不足。Deshpande[3]、Degemmis[4]通过矩阵填充技术解决冷启动和数据稀疏问题,但该技术在填充缺失数据的同时也引入了新误差。王鹏[5]在估计用户在项目空间兴趣分布的基础上计算用户相似度,实现对目标用户推荐,较好地解决了评分矩阵稀疏性问题,但该方法存在以下两点不足,一是未考虑时间引起的用户兴趣分布变化,二是在计算用户相似性时未引入用户特征差异性。

本文提出了融合用户兴趣分布变化和特征差异的协同过滤推荐算法(Collaborative Filtering Recommendation Algorithm of Combined with User Interest Change of Distribution and Characteristic Difference,ICD-CF)。实验结果表明,该算法能够有效追踪用户对项目兴趣变化,提高了数据稀疏情况下的推荐精度。

1 基于用户的协同过滤推荐算法

1.1 用户评分数据

推荐系统中存储的用户评分数据中一般包括用户id、项目id和用户对项目的评分信息。设有m个用户和n个项目,表示用户集,表示项目集,则用户评分数据可采用一个m×n阶的用户-项目评分矩阵表示。

1.2 用户相似性计算

具有代表性的相似性度量方法有Pearson相关系数和修正余弦相似性。设为用户Ui评过分的项目集合,为用户Ui产生的评分均值。则Pearson相关系数计算用户Ui与Uj相似性方法如式⑴所示:

修正余弦相似性计算用户相似性方法如式⑵所示:

1.3 评分预测

根据用户间的相似度可以获取目标用户的最近邻居集合,并将其相似性作为权重预测目标用户对未评分项目的评分,故目标用户ui对项目i的评分预测如式⑶所示:

式⑶中,为用户ut的评分均值,为用户ut的K最近邻居集。

2 融合用户兴趣分布变化和特征差异的协同过滤推荐算法

2.1 用户兴趣分布估计

在传统的用户相似算法中,仅考虑由共同评分的那些项目,而实际上,用户对于尚未评分的哪些项目也有自己的喜好。因而,若能估计用户在整个项目空间上的兴趣密度分布,再计算两用户兴趣分布的相似性更为符合实际情况。考虑到用户兴趣的多模性(即有多个局部极大值),ICD-CF算法采用统计学中的密度估计方法进行用户兴趣分布估计[5]。设是独立分布样本一组采样值,则任意一个采样值x的密度函数f(x)的核密度估计定义为:

式⑷中,为核函数,h为核函数的窗宽。常用的核函数有三角核函数、均匀核函数、高斯核函数等,本文中选用应用广泛的高斯函数作为核函数,如式⑸所示:

则用高斯核估计用户u兴趣分布Qu公式为:

其中,是项目i,j之间的距离。

2.2 用户兴趣分布变化函数

德国心理学家EBBINGHAUS H研究并揭示了人类记忆的遗忘规律,指出人类记忆的遗忘过程呈现先快后慢的变化规律。在记忆过后的初始阶段遗忘速度是最快的,而后逐步减慢,最后以非常缓慢的速度衰减。本文根据人类遗忘曲线和用户兴趣分布自身特点,提出了一种指数型遗忘因子如下:

其中,t是用户对某一感兴趣商品访问的时间间隔,,α为衰减因子,其值越大,衰减速率越大,本文中定义α=0.8,可根据实际情况调整。由式⑺可知,该函数的值域为[1,1/e],单调递减,符合人类记忆遗忘曲线特性。当访问时间间隔t逐渐增大时,函数值会非线性随之减小,表示兴趣衰减度随之增大。

ICD-CF算法将遗忘因子引入到用户兴趣分布估计函数,则得到用户兴趣分布随时间变化函数为:

式⑻表明,用户兴趣分布是时间间隔t的函数,将随着时间间隔的变化而动态变化。因此能够准确追踪用户对项目兴趣分布变化。

2.3 用户相似性计算

ICD-CF算法采用相对熵计算用户相似性[5]。设、分别为t时间间隔用户兴趣分布变化,则用户Ui、Uj散度定义为:

由于KL散度不具有对称性,因而一般采用式⑽计算用户间兴趣变化相似度:

同时,考虑到用户各个特征(性别、年龄、学历背景、职业等)对其兴趣分布变化的持久影响。算法引入了用户Ui与Uj的特征相似度:

其中,ai,j为用户Ui的第j个属性的取值。设为双向蕴涵运算,即用户Ui与Uj的第j个属性相同时值为1,否则为0。上式表明两用户属性相似度取值在[0,1]之间,即取值越接近1,表明两用户属性相似度越高,否则相似度越低。

综上分析,ICD-CF算法将用户兴趣变化相似度与特征相似度相结合,形成最终的用户相似性度量方法如下:

其中,为调节因子。该用户相似度计算方法不仅考虑了用户兴趣分布变化,而且嵌入了用户特征之间相似度。

2.4 算法描述

输入:用户-项目评分矩阵;

输出:用户Ui对项目Ij的预测评分。

step 1 依据式⑹估计所有用户兴趣在项目空间上的分布;

step 2 根據式⑺确定遗忘因子;

step 3 依据式⑻计算每一用户兴趣分布变化;

step 4 根据式⑼计算两用户间兴趣变化相似度;

step 5 依据式⑾计算两用户间特征相似度;

step 6 根据式⑿计算两用户之间最终相似度;

step 7 采用式⑶做出预测。

3 实验与分析

3.1 用户实验数据集

实验采用GroupLens研究小组提供的MovieLens数据集(http://movieslens.umn.edu),它包括943个用户对1682个项目(影片)的10万条投票记录。其中用户特征有年龄、性别和职业三个。实验把数据集按70%和30%的比例划分为训练集和测试集。

3.2 评价指标

实验将正确率(Accurany_rate)和平均绝对误差(Mean Absolute Error,MAE)作为算法性能评价标准。设预测的用户评分集为,对应实际评分集为,则MAE计算公式如式⒀所示:

3.3 实验环境

实验硬件环境为Intel inside CORE-i5系列CPU、2.2GHz主频、2GB内存;实验软件环境为Windows7操作系统、Microsoft Visual Studio 2010集成环境、SQL Server 2010数据库。

3.4 不同核函数下窗宽估计

实验分析了不同核函数下窗宽对用户兴趣分布估计影响,令,对每一个h取值测试其Accurany_rate与MAE。核函数分别选择高斯函数、三角函数和均匀函数。实验结果如图1、图2。

由图1、图2实验结果可知,在窗宽h=0.3时,ICD-CF算法的推荐准确率高且MAE较低。因此,后续实验中核函数的窗宽设置为0.4。

实验利用人工蜂群算法,分别对式⑿中的两个参数λ进行了寻优实验,其适应度函数为式⒀,得到最优参数值λ=0.63。

在同等数据集下,实验将基于修正余弦(Cosine)相似度的协同过滤算法,基于Pearson相似度的协同过滤算法,基于核方法的协同过滤(KU-CF)算法,以及ICD-CF算法进行了实验比较,由图⑶、⑷可以看出,在不同邻居数目下,ICD-CF算法较其他三种算法有较高的推荐准确率和较低的MAE,这表明DUID-CF算法有更高的推荐精度。

4 结束语

本文在考虑用户评分时间因素的基础上,提出了融合用户兴趣分布变化和特征差异的协同过滤推荐算法。通过设计时间遗忘曲线因子,确定了用户兴趣分布变化函数;最后结合兴趣分布变化相对熵和用户特征差异计算用户相似程度进行项目推荐。实验结果显示,该算法能够有效追踪用户对项目兴趣变化,提高了数据稀疏情况下的推荐精度。

参考文献(References):

[1] HERLOCKER J. Clustering items for  collaborative filtering[C]//Proceedings of ACM SIGIR Workshop on Recommender Systems, New York, USA, ACM Press,1999:1-4

[2] 郝雅娴,孙艳蕊.K-近邻矩阵分解推荐系统算法[J],小型微型计算机系统,2018.4(24):755-758

[3] Deshpande M,Karypis G. Item-Based top-N recommen-dation algorithms. ACM Trans on InformatioSystems,2004.22(1):147-177

[4] Degemmis M,Lops P,Semeraro G. A content-collaborative recommender that exploits wordnet-based user profiles for neighborhood formation. Journal  of User Modeling and User-Adapted Interaction,2007.17(3):217-255

[5] 王鹏,王晶晶,俞能海.基于核方法的User-Based协同过滤推荐算法.计算机研究与发展,2013.50(7):1444-1451