基于多核学习的协同滤波算法

宋恺涛 彭甫镕 陆建峰

(南京理工大学计算机科学与工程学院, 南京, 210094)

引 言

随着互联网的普及，中国的互联网用户数量已经在2015年超过了9.7亿。互联网的快速发展，促使了移动端电子商务的快速发展。越来越多快捷方便的基于移动端的O2O(Online to offline)电子商务应用出现。个性化推荐系统的出现为移动互联网的信息过载提供了帮助。个性化推荐系统帮助移动端用户快速寻找并向其推荐感兴趣的商品、服务。因此，对个性化推荐技术的研究，也成为了当前的一个研究热点。

协同滤波[1]是目前推荐系统中主流的一种个性化推荐算法。1992年，Xerox公司在针对Palo Alto研究中心的信息重载问题中设计了Tapestry，该系统首次引入了协同滤波的概念。1994年，GroupLens提出后，协同滤波得到大幅度发展，许多电子商务网站都开始采用协同滤波算法为用户提供个性化推荐服务。基于协同滤波的推荐算法，相比于常规的基于关联规则、基于内容等推荐算法而言，拥有自动分析兴趣的优点，能够体现个性化推荐的优点，结果直观，易解释。协同滤波可以分为基于用户(User-based)的协同滤波和基于物品(Item-based)的协同滤波。基于用户的协同滤波通过分析不同用户来进行推荐，该算法能够挖掘用户的潜在兴趣。但是在目前的应用场景下，用户的数量规模日益庞大，使得基于用户分析兴趣的性能逐渐下降。Item-based协同滤波算法是对用户的评分数据进行分析。该算法通过采用常规相似性度量来分析项目的最近邻居，向预测评分值较高的用户推荐相似项。传统的协同滤波推荐算法，只需要用户对项目的评分表就可以进行推荐。在基于移动端的电子商务系统中，通常还能够利用到用户的地理位置信息。Item-based协同滤波算法能够不需要其他用户的行为特征就可以进行个性化推荐。而且，对于多数数据集，用户数量都是远大于项目的数量，这使得Item-based协同滤波具有时间上的优势。但该方法同样存在采用传统相似性度量的缺陷，其只能获取传统方法的特点，并且伴随数据规模的变大，会面临着数据稀疏性问题、冷启动问题、系统扩展性差等问题。因此，寻找一种适应性更好的相似性度量也成为了协同滤波的一个研究热点。

1 核函数原理与设计

1.1 核函数原理

假设X是一个非空集合，H为一个内积空间，φ为X到X的映射。如果函数K：X×X→R，满足对于∀x,x′∈X有K(x,x′)=<φ(x),φ(x′)>，则称K为核函数。因此，核函数可以看作是内积概念的一个推广。根据Hilbert-Schmidt原理[5]，任何满足Mercer条件[6]的运算，都可以作为核函数的内积。

∬K(x,x′)φ(x)φ(x′)dxdx′>0

(1)

Mercer条件是帮助核函数检验其是否定义了一个特征空间的充分条件。其中，满足Mercer条件的核函数为容许核。容许核函数满足部分闭包性质。容许核的正系数线性组合同样也是容许核。

1.2 核函数设计

在基于项目的协同过滤推荐算法中，首先要计算项与项之间的相似度来寻找目标项的最相似的邻居集合。通常，相似性度量方法[7]，需要保证其度量值越大，相似程度越高的性质。核函数通常可以作为样本在特征空间的相似性度量，因此，可以作为协同滤波算法的相似性度量方法。利用协同滤波算法中常用的传统相似性度量方法和项目的地理位置信息，分别设计了皮尔逊核、余弦核，Jaccard核和径向基核。

皮尔逊相关系数(Pearson correlation coefficient，PCC)[8]常用于度量两个向量之间的线性相关性。假设项x和项y的共同评分项为I，使用皮尔逊相关系数分析项之间的相似度公式为

(2)

余弦相关性(Cosine similarity)[8]将两个向量的夹角余弦值来衡量向量之间的相似性。把n用户对于项的评分看做一个n维向量，使用余弦相似度的公式

(3)

式中rx和ry表示项x与项y的评分向量。‖·‖表示向量的模。

Jaccard[8]相关系数是两项的交集与并集的比值，相似度公式为

(4)

式中X与Y分别表示项x与项y的评分集。

径向基核[9，10](Radial basis function kernel)，又称为RBF核，是一种常用核函数，通常定义为空间中任一点x到某一点到某一中心xc之间欧氏距离的单调函数

(5)

式中‖x-x′‖2是两个特征之间的欧拉距离平方根，σ是自由参数。

在带有地理位置信息的数据集上，通常可以获取项的经纬度，项x与项y的直接地理位置距离[10]的公式如下

dis(x,y)=R×acos(sinxlatsinylat+

cosxlatcosylatcos(xlng-ylng))

(6)

式中xlat，xlng，ylat，ylng分别表示项x与项y的纬度与经度。由于不满足其度量值越大，相似度越高的性质，将项与项之间的直接地理位置距离以径向基核的形式表示

(7)

式中dis(x,y)是式(4)所描述的项x与项y的直接地理位置距离，l是自由参数。

2 多核学习方法

2.1 合成核方法

在多核学习中，最优核通常是采用多个基本核函数的线性组合方式。图1为一个多核线性组合的示意图。

图1 多核函数线性组合过程Fig.1 Linear combination of multiple kernel function

本文采用了加权求和核[11，12]的方法，将皮尔逊核、余弦核、Jaccard核和径向基核等进行线性组合。其形式如下

(8)

式中simi对应某种类型的核函数，wi分别对应各个核函数的核系数,并确保各个核系数之和等于1，且每个核系数都大于等于0。

2.2 合成核的学习方法

度量用户偏好商品i的概率采用评分加权推荐公式[13]来计算。该方法考虑了相似邻居集的评分尺度的影响。公式如下

(9)

式中：SNi表示项i的K个最近邻居集合；sim(i,j)是式(8)所设计的多核线性组合模型；rj,u是用户u在项目j上的评分值。

本文采用随机梯度下降[14]作为学习方法。随机梯度下降是一种常用的最小化损失函数方法。随机梯度下降通过对单样本的损失误差求解梯度，从而更新参数。其一次梯度迭代下降的时间复杂度较低。评估协同滤波算法的损失函数可以使用最小二乘误差[15]。在本文中，其最小二乘误差表示如下

(10)

式中：P(v,u)为式(9)中的评分方式；y(v,u)为观察值。

损失函数的梯度求解主要是对式(10)进行梯度求解，其求解过程如下：

(4)对于向量w的求导结果为

(5)因此整体损失函数的梯度值为

本文所采用的随机梯度下降的学习方法，梯度的求解采用了损失函数梯度求解方法。因此基于多核学习的推荐系统算法过程如下：

输入：评分表，测试集和初始多核系数w

输出：推荐用户-项目对

(1) 遍历项目-用户对(v,u)，对于当前项目v，确定其邻居集SN

(2) 对于当前的项目-用户对。采用章节3.2.1中的方法，求解梯度η，采用随机梯度的方法更新多核系数w。随机梯度的更新公式为：w(n+1)=wn-αη，其中α为步长。

(3) 重复迭代(1)～(2)，直到损失函数变化趋于稳定，获取多核系数w，换到第(4)步

(4)遍历训练集，采用训练得到的多核方程，重新计算每个项目的邻居集。

(5)对于当前项目v，采用式(9)计算一定范围内的每个用户的期望评分，并选出评分前N高个用户，进行推荐。

(6)将推荐集合与测试集合进行比较，评测推荐系统的性能。

由于每次更新核系数后，项目的邻居集都会变化，使得直接在整体集上求单个项目的邻居集的时间复杂度大。因此，本文预先处理单个项目在多个常规相似性度量上的邻居集，从而在新参数w下寻找项目的邻居集时只需要在常规相似性度量上的邻居集合中搜索。而计算各个核函数的过程同样需要一定时间复杂度。因此，在搜索常规度量邻居集合的同时，将项目与邻居集的相似性度量值保存，方便在多核学习过程中直接使用，避免重复计算。

3 实验结果分析

3.1 数据集

为了验证本文所提出的方法，实验中使用大众点评数据集和Foursquare两个真实数据集进行验证。

大众点评数据集选用了某地区店铺的用户评价信息以及店铺地理位置。用户对店铺的喜好采用评分形式。数据集仅有0.148 9%的用户-店铺对有评分项。

表1 大众点评数据集信息

Foursquare数据集选用了新加坡地区2010年8月到2011年7月用户的签到数据。将用户是否有签到行为作为评分项。由于Foursquare数据集是属于二进制数据集，因此，各个核的效果在Foursquare数据集上会出现较大波动。

表2 Foursquare数据集信息

本文将数据集按照4∶1的比例划分训练集和测试集，进行5-折交叉验证。

3.2 推荐评分标准

在获取最优多核系数w后，将采用式(9)计算评分，进行Top-N推荐。对于推荐性能的评价，在推荐系统中，通常会选用F1值(F1Score)[16]作为标准，因为F1值可以同时顾及二分类推荐模型中准确率(Precision)和召回率(Recall)。

准确率：推荐命中的个数占推荐商品总的个数比率。

(11)

召回率：用户所喜欢的商品最终被推荐出来的比率。

(12)

F1值是准确率和召回率的调和平均数，公式为

(13)

图2 核系数目标损失函数下降 Fig．2 Descent of kernel factor cost function

式中：TP表示推荐集合中正类的个数，FP表示推荐集合中负类的个数；FN表示没有在推荐集合中的正类个数。

3.3 实验结果

在实验中，采用平均绝对误差(Mean absolute difference, MAE)[17]来评估多核学习过程中的损失情况。平均绝对误差是指所有单样本的观察值与算术预测值的绝对偏差之和的平均值,其公式为

(14)

式中：fi表示预测值，yi代表观察值。

由于数据集的规模较大，计算整体损失函数的时间较多。因此，在核系数学习过程中，采用批次处理的方法，进行梯度上的更新。在本文的实验中，设置迭代计算间隔次数为1 000次，步长α为0.00 002。观察图2，在60次左右的损失函数计算后，即大约60 000次左右的学习迭代，整体损失函数下降逐渐趋于稳定。将最后趋于稳定的核系数作为多核方程进行协同滤波推荐。

本文将基于多核学习的协同滤波算法与采用常规相似性度量方法，包括了Jaccard核、余弦核、径向基核这3种方法，以及平均加权常规相似性度量方法的协同滤波算法进行比较。进行Top-N推荐时，选择不同的Top-N系数，Top-N的范围设置在10%～25%，采用式(11)的F1值作为评分标准。

图3 大众点评数据集实验结果 图4 Foursquare实验结果

大众点评的数据集的最近邻个数设置为30,径向基核的参数l设置为1。通过观察图3，在大众点评数据集上，基于多核学习的协同滤波算法相比于采用传统相似性度量方法的协同滤波算法，F1值提升了3.973%。观察图4，受限于Foursquare数据集的二进制数据，使得在Top-N较小时，效果不是很明显，在Top-N大于20%的时候，基于多核学习的协同滤波算法相比于采用传统相似性度量方法的协同滤波算法的推荐性能有了整体的提升，平均F1值相比于采用传统相似性度量方法的协同滤波算法提升了6.523%。说明了基于多核学习的协同滤波算法拥有更好的推荐性能。

4 结束语

本文提出了一种基于多核学习的协同滤波算法，并给出学习方法的推导。该方法相比于采用传统相似性度量的协同滤波算法而言，具有选择最优核的能力，能够自动学习核系数来提升性能，并体现各个核函数对实验结果的影响。在大众点评数据集和Foursquare数据集上的实验表明，本文所提出的基于多核学习的协同滤波算法提升了推荐性能，具有有效性。但是，核系数的初始化选择以及核函数的组合，对实验结果会有很大的影响。如何针对于数据集，选择核系数与核函数，仍是多核学习中的难点。

参考文献:

[1] Badrul Sarwar． Item-based collaborative filtering recommendation algorithms[C]∥Proceedings of the 10thInternational Conference on World Wide Web. New York：WWW10, 2001:285-295．

[2] Suykens J K． Least squares support vector machine classifiers[J]. Neural Processing Letters,1993,9(3):293-300.

[3] 汪洪桥．多核学习方法[J].自动化学报,2010,36(8):1037-1050．

Wang Hongqiao. On multiple kernel learning methods[J].Acta Automatic Sinica,2010,36(8): 1037-1050．

[4] Meirom E A．Nuc-MKL:A convex approach to non linear multiple kernel learning[J]. AISTATS, 2016, 51:610-619．

[5] Li Liyan． Gene networks identification using independence measurement based on the Hilbert space[D].Hangzhou:Hangzhou Dianzi University, 2014．

[6] Lyu Siwei． Mercer kernels for object recognition with local features[J]. CVPR,2005,2:1063-6919．

[7] Liu Haifeng． A new user similarity model toimprove the accuracy of collaborative filtring[J]. Knowledge-Based Systems, 2014,56: 156-166．

[8] Ekstrand M D, Riedl J T, Konstan J A.Collaborative filtering recommender system [J]. Foundations and Trends in Human-Computer Interaction,2010,4(2):81-173．

[9] Chung Kai-Min． Radius margin bounds for support vector machines with the RBF kernel[J]. Neural Computation,2003,15(11):2643-2681．

[10] 奚吉,赵力,左加阔.基于改进多核学习的语音情感识别算法[J].数据采集与处理,2014,29(5):730-734．

Xi Ji, Zhao Li, Zuo Jiahuo. Speech emotion recognition based on modified multiple kernel learning algorithm[J]. Journal of Data Acquisition and Processing, 2014, 29(5):730-734.

[11] 王国胜.核函数的性质及其构造方法[J].计算机科学,2006,33(6):172-178．

Wang Guosheng. Properties and construction methods of kernel in support vector machine[J]. Computer Science,2006,33(6):172-178．

[12] Lu Yanting． Research and application of clustering and hierarchical classification algorithms based on multiple kernel learning[D]. Nanjing:Nanjing University of Science and Technology, 2013.

[13] 王付强,基于位置的非对称相似性度量的协同过滤推荐算法[J].计算机应用,2016,36(1):171-174．

Wang Fuqiang. Location-based asymmetric similarity for collaborative filtering recommendation algorithm[J]. Journal of Computer Applications, 2016, 36(1):171-174．

[14] Léon Bottou． Large-scale machine learning with stochastic gradient descent[C]∥19th International Conference on Computational Statistics.Paris: Proceedings of COMPSTAT,2010:177-186．

[15] York D． Least squares fitting of a straight line with correlated errors [J]. Earth and Planetary Science Letters,1968,5:320-324．

[16] Yang Yiming． A re-examination of text categorization methods[C]∥the 22nd Annual International ACM SIGIR Conference. USA:SIGIR，1999:42-49．

[17] Vassiliadis S. The sum-absolute-difference motion estimation accelerator[C]∥Proceedings of the 24thEuromicro Conference. Germany: Euromicro Conference,1998:559-566．