基于模糊聚类的多视图协同过滤推荐算法

黄巧文,周宽久,费 铮,崔云鹏

(1.北京商业机械研究所 信息化研究部,北京 100070;2.大连理工大学 软件学院,辽宁 大连 116081)

0 引 言

随着移动互联网的发展及大数据时代的到来,信息呈现出爆炸式增长。面对信息的泛滥和超载,人们往往会无所适从,在信息面前会面临各种选择问题,如信息的获取方式、信息的真伪鉴别等。于是,为了帮助用户获取其感兴趣且有价值的信息,推荐系统应运而生。现如今,推荐技术已经成功在电子商务、社交网络等领域中得到了广泛应用,它旨在根据用户在系统中的自然行为和历史数据,挖掘用户的兴趣点,从而向用户推荐其感兴趣的项目,如资讯、商品和广告等。

推荐算法是推荐系统中的核心部分,常用的推荐算法包括基于内容的推荐算法[1]、基于知识的推荐算法[2]和基于协同过滤的推荐算法[3]等。其中,基于协同过滤的推荐算法因其简单、高效的特点而被广泛应用。在实际应用中,协同过滤算法根据其作用的对象又可分为基于用户的协同过滤(UBCF)和基于项目的协同过滤(IBCF)。以IBCF算法为例,其核心思想是先通过用户的历史行为信息构建用户—项目的评分矩阵,然后挖掘相似性较大的项目,并得出目标用户对项目的预测评分,最后将预测评分进行排序,形成TOP-N推荐结果。

聚类[4]作为一种无监督机器学习方法,在推荐领域常被用于挖掘用户或项目的相似性,以提升推荐效率。由此,针对协同过滤算法的不足,大量的学者提出了一系列的改进措施。李华等[5]提出了基于模糊聚类的协同过滤推荐算法,该算法将模糊聚类算法作用于项目评分矩阵,一定程度上提高了推荐的实时性和准确性。肖文强等[6]提出了基于谱聚类的用户协同过滤推荐算法(Collaborative Filtering Recommendation Algorithm based on User Spectral Clustering,SC-CF+),该算法利用谱聚类将用户进行聚类,降低了用户空间的维度,同时在相似性度量中引入了项目的时间和流行度等因素提高了推荐结果的召回率。考虑到矩阵分解的有效性,Ifada等[7]基于非负矩阵分解(NMF)、奇异值分解(SVD)、主成分分析(PCA)三种矩阵分解方法和K-means、模糊C均值聚类两种聚类方法的6种组合研究了不同矩阵分解方法在基于聚类的协同过滤推荐算法中的差异性。为了降低数据稀疏性的影响,苏庆等[8]着重优化了项目的相似度计算方式,通过引入时间差因子和冷门、热门项目权重以改进修正的余弦相似度,并结合模糊C均值聚类算法提出了基于改进模糊划分的协同过滤推荐算法(Collaborative Filtering Recommendation Algorithm Based on Improved Fuzzy Partition Clustering,GIFP-CCF+)。为了解决推荐系统数据稀疏及冷启动问题,王岩等[9]基于蜂群算法降低了K-means++算法聚类中心的敏感度,从而缓解了数据稀疏问题,提高了推荐质量;贾俊杰等[10]通过融合用户间的显、隐式信任值将信任机制引入到模糊C均值聚类算法中,提出了基于用户模糊聚类的综合信任推荐算法。刘军等[11]在解决冷启动问题的基础上,提出一种增强评分矩阵的协同过滤推荐算法,该算法综合考虑用户购买意愿力、用户兴趣便宜因素以及时间因素等为用户提供精准推荐。上述算法均为单一聚类算法在推荐系统上的优化,为了进一步增强聚类算法在推荐系统中的性能,Zarzour等[12]又基于集成聚类技术,将多种聚类算法集成到推荐系统中,集合期望最大化和超图划分算法提高了预测精度。最近,王英博等[13]提出了基于子空间聚类的协同过滤推荐算法(Subspace Clustering based User Collaborative Filtering Recommendation Algorithm,SCUCF),该算法通过利用子空间聚类来构建用户邻居树,结合改进的相似性度量方法提高了寻找相似用户的准确性。总之,大部分的改进算法都致力于改进相似性度量方式、改进邻域划分以及降低数据稀疏性带来的影响等措施来提高算法的性能,而忽略了推荐系统中用户行为的复杂性和多样性。

基于“村镇社区新型商贸连锁综合服务平台研究及示范”的国家重点研发计划,针对课题中新零售精准会员推荐系统中具有多源异构特点的用户行为,提出基于模糊聚类的多视图协同过滤推荐算法。首先,为挖掘用户的关键行为信息,将用户在系统中的多种行为数据整合为多视图数据[14],并基于此提出基于多视图融合的项目相似性度量方法和用户偏好预测方法。然后,为了在优化项目邻域划分的同时自动学习用户的多种行为偏好之间的差异性,结合最大熵方法[15]提出基于质心约束的多视图熵加权模糊聚类算法(Centroid Constraints Based Multi-View Entropy Weighted Fuzzy Clustering,C_MVEWFC)。此外,考虑到C_MVEWFC算法的非线性表达能力较弱的问题,基于核映射技术提出基于质心约束的多视图加权核模糊聚类算法(Centroid Constraints Based Multi-View Entropy Weighted Kernel Fuzzy Clustering,C_MVWKFC)。最后,结合上述改进的项目相似性度量方法和用户偏好预测方法,基于C_MVEWFC算法和C_MVWKFC算法提出对应的协同过滤推荐算法MVFC-CF和MVKFC-CF,算法的执行流程如图1所示。为公平比较算法的推荐效果,在公开数据集上与较为先进的基于聚类的协同过滤推荐算法进行实验验证。

图1 MVFC-CF算法和MVKFC-CF算法的执行流程

1 相关理论

1.1 协同过滤推荐算法

假定J个用户、K个项目的评分矩阵定义为R=[rjk]J·K,rjk表示第j个用户对第k个项目的评分,则列向量r.k表示项目k的受欢迎程度。因此,项目之间的相似性就是评分矩阵R中列向量之间的相关性。通常来讲,可以通过余弦相似度、Pearson相关系数、Jaccard系数等来刻画该相关性,式(1)为余弦相似度的计算公式。

(1)

由式(1)可得项目k与其余所有项目之间的相似性。

在进行项目的评分预测时,传统方法首先在项目空间中计算并搜寻项目的邻域,然后结合项目之间的相似度和用户—项目评分矩阵可得如下的评分预测[16]:

(2)

从式(1)可看出,传统协同过滤算法在计算项目的相似性时是在全局范围内进行搜索的,这在大规模推荐系统显然不适用。而聚类算法的引入,缩小了近邻项目的搜索范围,使得协同过滤算法在寻找近邻项目时只需聚焦于同一类簇下,这给传统的协同过滤算法创造了新的发展空间。

1.2 模糊划分聚类算法

Fuzzy C-Means(FCM)聚类算法[17]是最为经典的模糊聚类算法,它旨在通过划分的方式将数据分割成类间相似度较小、类内相似度较大的类簇。给定待聚类的M×N维数据X={x1,x2,…,xm}M×N,FCM的目标函数如下:

(3)

其中,U=[umk]M×K为模糊划分矩阵,umk表示第m个样本属于第k个类的程度;ck则表示第k个类的聚类中心向量;α为大于1的模糊因子。

显然,传统的FCM算法原理较为简单,难以处理复杂多变的数据。近年来,随着信息技术的发展,数据往往呈现出多源异构的特点。为了提高对此类数据的聚类精确度,大量的多视图聚类算法[18-19]层出不穷,同时这些算法被广泛应用在数据挖掘等领域。然而,推荐系统中的多视图聚类算法为了简便大多数是先在单视图聚类的基础上进行拆分,再寻求融合之法;没有考虑到多个视图之间既存在关联性也存在差异性,忽略了多个视图对于最终推荐结果的差异化贡献。

1.3 多视图行为的项目相似性度量与偏好预测

该部分基于推荐系统中复杂多样的用户行为数据,结合行为之间的差异性,提出新的偏好预测方法和项目相似性度量方法。

1.3.1 项目相似性度量

用户在项目上的不同行为可看作是不同的视图(角度)上对项目的偏好,张量Z={X1,X2,…,Xv}囊括了用户的V种行为数据,对于其中一个视图来讲Xv=[xni]N×I代表用户的行为矩阵,例如评分、点击历史、购买历史等;xni∈[0,1]表示用户n对项目i的局部偏好。因此,用户对项目的全局偏好程度Q=[qni]N×I定义为:

(4)

式中,ωvni表示在第v个视图中用户n和项目i之间的行为权重;xvni表示在第v个视图中用户n对项目i的行为偏好。本方法在用户对项目的偏好程度的评估上融合了用户对项目的多种行为信息,而这多种行为信息的重要程度则由Ω(Ω=[ωvni]V×N×I)决定,因而这种评估方式更具客观性和准确性。

在项目相似性的计算上,考虑到不同用户对不同项目偏好的标准和程度上的差异,结合修正的余弦相似度和式(4),引入新的融合多种行为信息的项目相似性度量方法,如式(5)所示。

(5)

sij=gij×oij,oij∈[0,1]

(6)

其中,oij在计算时已经过归一化处理。

1.3.2 用户偏好预测

结合式(5)、式(6),项目的偏好预测公式如式(7)所示:

(7)

2 多视图协同过滤推荐算法

为了提高推荐结果的准确性,本节首先提出C_MVEWFC算法,该算法能够实现上述行为权重的自动优化以及多视图的协同过滤;然后,在此基础上引入核函数,进一步提出C_MVWKFC算法以提高算法对非线性数据的聚类性能。

2.1 基于质心约束的多视图熵加权模糊聚类算法

给定项目行为的多视图数据集Z={X1,X2,…,Xv},C_MVEWFC算法的任务是融合V个视图将数据划分为K个类簇,该算法的目标函数如式(8)所示。

F(M,C,Ω)=

(8)

式中,M=[μik]I×K为隶属度矩阵,即模糊划分矩阵;μik表示第i个样本(项目)属于第k个类的程度;C=[cvkn]V×K×N为三维的聚类中心矩阵,cvkn代表第v个视图中第k个聚类中心的第n个属性(该文指用户偏好);Ω=[ωvin]V×I×N为三维的权重矩阵,ωvin为第v个视图中第n个用户对第i个项目的偏好权重;α为模糊因子,β和γ是两个正标量。

在目标函数F中,第一项是对FCM算法的改进,主要用于融合多个视图的数据来学习全局隶属度矩阵M,从而进行数据划分;第二项为聚类中心(质心)的正则化项,通过最大化类间聚类中心的距离来进一步优化类簇的划分;第三项为权重的正则化熵项,用于最优化权重ωvin的分布;β和γ则分别控制着后两项的重要程度。因此,算法的目标是通过最小化目标函数(8)得到多视图数据的最优划分,该文采用Picard迭代法[20],通过迭代求解M、C、Ω逐步将式(8)进行最小化。

首先,固定C和Ω求解M。使用拉格朗日乘数法将带有约束的F(M)最小化问题转化为如式(9)所示的无约束最小化问题。

(9)

(10)

(11)

结合式(10)和式(11)即可得到全局模糊隶属度的更新公式,如式(12)所示。

(12)

其次,固定M和Ω求解C。此时,目标函数的最小化问题转化为式(13)的最小化问题。

(13)

这里令dL(C)/dcvkn=0,可得:

(14)

通过求解式(14)可得到各视图聚类中心的迭代公式,如式(15)所示。

(15)

最后,固定M和C求解Ω。同样地,借助于拉格朗日乘数法,将带有约束的F(Ω)的最小化问题转化为式(16)所示的无约束最小化问题。

(16)

γlogωvin+γ+θin=0

(17)

(18)

求解式(17)和式(18)得到权重的迭代公式,如式(19)所示。

(19)

结合以上公式,C_MVEWFC算法的执行流程如算法1所示。

算法1:C_MVEWFC算法

输入:多视图数据Z,项目个数I,视图个数V,类簇个数K,迭代收敛阈值ε,最大迭代次数tmax,以及参数α,β,γ

输出:隶属度矩阵M=[μik]I×K

1.初始化每个视图随机生成K个聚类中心cvkn,设定行为权重ωvin为1/V,设置迭代计数器t=1;

2.fort

3.通过式(12)更新隶属度矩阵M;

4.通过式(15)更新聚类中心矩阵C;

5.通过式(19)更新权重矩阵Ω;

6.利用式(8)计算目标函数F的值;

7.if|F(t)-F(t-1)|<εthen//目标函数收敛

8.break;

9.end if

10.t++;

11.end for

2.2 基于质心约束的多视图加权核模糊聚类算法

为了提高C_MVEWFC算法对非线性多视图数据的划分精度,借鉴核聚类算法[21]的思想并结合高斯核函数进一步提出基于核函数的C_MVWKFC算法,该算法的目标函数如式(20)所示。

Fψ(M,C,Ω)=

(20)

其中,ω(x)表示将x从低维的特征空间映射到高维的核空间,而核空间中向量的内积则可由核函数ψ(a,b)=φ(a)Tφ(b)得出,该文采用的高斯核函数如式(21)所示。

(21)

式中,a和b代表参与运算的变量。根据高斯核函数的运算规则,式(20)可以进一步改写为:

Fψ(M,C,Ω)=

(22)

与C_MVEWFC算法一样,C_MVWKFC算法的目标是通过最小化目标函数来得到最优的划分矩阵M。在目标函数的求解上同样采用Picard迭代法,式(23)、式(24)及式(25)分别为得出的隶属度更新公式、聚类中心更新公式和权重更新公式。

(23)

cvkn=

(24)

(25)

结合以上公式,C_MVWKFC算法的执行流程如算法2所示。

算法2:C_MVWKFC算法

输入:多视图数据Z,项目个数I,视图个数V,类簇个数K,迭代收敛阈值ε,最大迭代次数tmax,核参数σ,以及参数α,β,γ

输出:隶属度矩阵M=[μik]I×K

1.初始化每个视图随机生成K个聚类中心cvkn,设定行为权重ωvin为1/V,设置迭代计数器t=1;

2.fort

3.通过式(23)更新隶属度矩阵M;

4.通过式(24)更新聚类中心矩阵C;

5.通过式(25)更新权重矩阵Ω;

6.利用式(22)计算目标函数Fψ的值;

8.break;

9.end if

10.t++;

11.end for

2.3 计算复杂度分析

对于C_MVEWFC算法,假设待聚类的用户行为数据包含V种行为、N个用户、I个项目以及K个类别,则该算法在一个迭代周期内计算隶属度的时间复杂度为O(VIK2N),计算聚类中心的时间复杂度为O(VIK2N),计算权重的时间复杂度为O(V2IKN)。因此,C_MVEWFC算法执行一次的时间复杂度为O(tV2IK2N),其中t为算法的迭代次数;同样地,C_MVWKFC算法的时间复杂度亦为O(tV2IK2N)。在实际的应用中,用户的数量N和项目的数量I要远大于行为的种类V和项目的类别K,故可认为文中的两个聚类算法的时间复杂度接近于O(IN)。此外,根据式(4)和式(6)可知,偏好矩阵和相似度矩阵的计算复杂度分别为O(VIN)和O(I2)。

3 实验分析与讨论

3.1 实验数据与目的

如表1所示,采用两种公开数据来验证算法的效果,其中一个是阿里巴巴的淘宝用户行为数据集UserBehavior[22],该数据集记录了一段时间内部分用户对商品的消费行为,包括点击、购买、收藏、加购物车等。在实验数据的构造上,将用户的上述4种行为数据看作为4种不同的视图,先从原始数据中抽取了500名用户在行为密度较高的7 800个商品上的行为数据作为实验数据集,然后从项目的维度将以上数据集划分成两部分,即训练集和测试集,分别占整个实验数据集的80%和20%。

表1 实验数据构成

由该数据的构造可知,点击行为表达出了用户对项目的第一印象,也是用户对项目偏好与否的第一行为反馈。故在该数据集上的实验目的就是通过学习训练集中用户与项目之间的不同行为来预测测试集中用户对项目的点击行为。

参与实验的另一个数据集是MovieLens-1M[23],该数据集是由GroupLens团队从MovieLens网站(https://movielens.org)上收集的,包含了2000年加入MovieLens的6 040人对约3 900部电影的100万条匿名评分。该数据集在实验中用于验证引入核函数的MVKFC-CF算法相较于MVFC-CF算法的非线性数据处理能力。为了保证该数据集在算法上的可用性,这里首先分别将用户对电影的评分、电影上映时间与评分时间差作为两个不同的视图,两个视图均能从不同的角度反映出用户对电影的喜好程度;其次利用Sigmoid激活函数将评分与时间差的真实值均分别进行非线性变换,以得出非线性的多视图数据集。在训练集和测试集的划分比例上,与UserBehavior数据集保持一致。

3.2 评价指标与参数设定

为了更加合理、公平地评估文中算法的性能,选用平均绝对误差MAE[24]和推荐结果TOP命中率THR[25]作为算法性能的评价指标,并同基于改进的kmeans聚类的协同过滤推荐算法Kmeans-CF[16]、基于模糊C均值聚类的协同过滤推荐算法FCM-CF[8]、SC-CF+[6]、GIFP-CCF+[8]、SCUCF[13]等进行比较。MAE和THR的公式分别定义如下:

(26)

(27)

算法涉及到的超参有模糊因子α,核参数σ,正则化参数β和γ,实验中采用网格搜索法来寻找参数的最优值,表2列出了这些参数的搜索范围。

表2 算法参数的寻优范围

3.3 实验结果与分析

3.3.1 UserBehavior数据的实验结果

首先,针对参与对比实验的所有算法利用训练数据集寻找最佳聚类参数,并通过比较MAE和THR值的变化情况来确定最终的参数取值,如文中α的取值为2.0,β的取值为10-5,γ的取值为10-4,σ的取值为22。然后,为了实验的公平性,在测试集上验证各算法的实际推荐效果和泛化性能,这里每种算法的评价指标均取在测试集上执行100遍的均值。表3列出了上述5种算法和文中算法在UserBehavior数据集上的MAE值和THR值,以及两指标的标准差。从表中可知,相较于其他算法Kmeans-CF和FCM-CF的推荐效果最差。一方面这是因为传统的聚类算法难以处理多视图数据,导致在寻找邻域项目时准确度不高;另一方面,传统协同过滤算法在用户的偏好预测上只能参考用户的单一行为,难以挖掘到多种行为之间的联系。

表3 算法效果对比

虽然SC-CF+、GIFP-CCF+、SCUCF等三个算法都从项目相似性度量、项目邻域划分等不同的角度进行了改进,但仍然忽略了推荐系统中多种行为的关联性和差异性,故而在面对多视图数据时推荐效果差强人意。而引入多视图概念的MVFC-CF算法通过自动加权的方式自动地学习用户的关键行为,同时采用多视图聚类的方式优化了项目邻域的划分,进而与SCUCF算法相比在MAE上从0.622 9降低到0.603 4,在THR上从0.128 2提升到0.143 6。此外,由于核函数的引入,MVKFC-CF算法的精度得到进一步提升,相比于MVFC-CF算法在MAE指标上相对降低了3.1%,在THR指标上相对提升了5.92%。

聚类数K与数据集本身强相关,该参数是决定最终类簇紧密程度的重要影响因素,而在与聚类结合的协同过滤算法中,该参数的取值会直接影响到最终的推荐效果。为了确定文中数据集最优的聚类数目,这里用K={5,10,15,20,25,30} 6个不同大小的聚类数来测试聚类数K对算法的影响。实验中,固定各算法的最优聚类参数不变,将聚类数目由最初5个逐渐增加至30个,观察各算法的评价指标的变化情况。图2(a)(b)分别展示了以上7种算法在测试集上不同K值下的MAE和THR的变化趋势。由图2可知,随着聚类数量的逐渐增加,所有算法的预测精度都呈现出越来越好的趋势。这是因为聚类数越大最终得到的项目邻域就越细化,那么找到相近邻居的概率就越高,因此推荐结果就越精准。从图中可进一步观察到,对于本数据集而言,当聚类数达到25至30时大部分算法均趋于稳定,因此在测试中文中算法的K值设定为25。从算法的表现上来看,MVKFC-CF相比较新的SCUCF算法在MAE上从0.622 9降低到0.584 7,在THR上从0.128 2提升到0.152 1。整体来看,MVFC-CF算法和MVKFC-CF算法相较于其他算法在不同的K值下均表现出了更好的性能,这再次验证了文中算法的有效性。

图2 算法在UserBehavior数据集上不同K值下MAE和THR的变化曲线

3.3.2 MovieLens-1M数据的实验结果

MVKFC-CF算法通过引入核映射技术以提高MVFC-CF算法的非线性数据处理能力,从而提高协同过滤的准确性。为了验证MVKFC-CF算法的推荐效果,实验中首先设定K={5,10,15,20,25,30},σ=22,然后对比在不同聚类数下的MVFC-CF算法和MVKFC-CF算法对该数据集的处理能力,实验结果如图3所示。

图3 MVFC-CF和MVKFC-CF在MovieLens-1M数据集上的MAE和THR

由图3可知,当聚类数目较小时两算法的差距并不大,而随着聚类数目的增大,MVKFC-CF算法的优势就愈加明显,当聚类数为15时,文中算法在MovieLens-1M数据集上的推荐效果达到最佳,此时MVKFC-CF算法与MVKFC-CF算法的MAE指标绝对差距为0.06,THR的绝对差距为1.6百分点。实验的评价指标表明,MVKFC-CF算法对于非线性数据的处理能力更强,推荐结果更加精准。

4 结束语

提出了两种基于多视图聚类的协同过滤推荐算法,不仅考虑到了多种行为之间的潜在联系,还考虑到了数据的非线性特点。在多视图行为的构造上,利用推荐系统中用户对项目的多样性行为构建多视图行为矩阵,同时引入多视图融合的权重系数来平衡多种行为之间的差异性和关联性。在相似性评估上,结合用户与项目之间的同现矩阵,提出新的相似性度量方法和偏好预测方法。

在项目邻域划分的优化上,基于多视图模糊聚类的思想,提出了MVFC-CF算法,利用最大熵方法来自动调节行为权重的分布。进一步地,在MVFC-CF算法的基础上引入核函数,提出MVKFC-CF算法以增强算法对非线性数据的处理能力。实验表明,该算法在推荐结果的准确性上相较于其他基于聚类的较为先进的协同过滤算法均有不同程度的提高。即便如此,算法仍有不足之处,下一步将通过引入上下文信息和弥补缺失行为的角度,进一步提高算法的推荐效果。