引言

随着互联网的普及，中国的互联网用户数量已经在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协同滤波具有时间上的优势。但该方法同样存在采用传统相似性度量的缺陷，其只能获取传统方法的特点，并且伴随数据规模的变大，会面临着数据稀疏性问题、冷启动问题、系统扩展性差等问题。因此，寻找一种适应性更好的相似性度量也成为了协同滤波的一个研究热点。

核函数是模式识别中常用的一种非线性分类技巧。其中，最出名的应用是在1995年由Vapnik等提出的支持向量机(Support vector machine, SVM)^[2]。核函数通过一个非线性变换将输入空间映射到高维特征空间，然后在线性空间使用线性计算算法。因此，核函数的出现使得线性不可分问题变成某些高维特征空间的线性可分问题，从而降低了问题的复杂性。但面对不同的场合，核函数的性能差异很大，并且核函数的选择也没有很好的理论依据。因此，将多个单核函数组合成灵活性更强的多核学习(Multiple kernel Learning, MKL)^{[3, 4]}, 成为了一个新的研究热点。近年来的理论学习，例如Boosting的多核组合模型学习方法，基于半定规划(Semi definite programming, SDP)的多核学习方法，简单多核学习方法(Simple KML)等，都证明了多核学习模型能够相比于单核模型能够提升分类的精准度。在多核学习中，比较常用的是多个单核函数的凸组合，其形式如：$K = \sum\limits_{j = 1}^M {{\beta _j}{K_j}} , \beta \ge 0, {\rm{ }}\sum\limits_{j = 1}^M {{\beta _j}=1} {\rm{ }} $。除此之外，还包含了直接求和核^[3]，加权求和核^[3]等。因此，多核学习模型的问题转化成了如何去寻找核函数最优系数的问题。

1 核函数原理与设计 1.1 核函数原理

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

Mercer条件   对于任意的对称函数K(x, x′)，它是某个特征空间中的内积运算的充分必要条件是，对于任意的φ(x)≠0且$\smallint {\varphi ^2}\left( x \right){\rm{d}}x < \infty $，满足

$ \iint {K\left( {x,x} \right)\varphi \left( x \right)\varphi \left( {x'} \right){\text{d}}x{\text{d}}x'} > 0 $

(1)

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

1.2 核函数设计

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

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

$ {\rm{PCC}}\left( {x,y} \right) = \frac{{\sum\limits_{p \in I} {\left( {{r_{x,p}} - {{\bar r}_x}} \right)\left( {{r_{y,p}} - {{\bar r}_y}} \right)} }}{{\sqrt {\sum\limits_{p \in I} {{{\left( {{r_{x,p}} - {{\bar r}_x}} \right)}^2}} } \sqrt {\sum\limits_{p \in I} {{{\left( {{r_{y,p}} - {{\bar r}_y}} \right)}^2}} } }} $

(2)

式中r_{x, p}，r_{y, p}表示用户p对项x, 项y的评分。$ {\bar r_x}$和$ {\bar r_y}$表示项x和项y上用户集评分的平均值。

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

$ {\rm{COS}}\left( {x,y} \right) = \frac{{{\mathit{\boldsymbol{r}}_x} \cdot {\mathit{\boldsymbol{r}}_y}}}{{\left\| {{\mathit{\boldsymbol{r}}_x}} \right\| \cdot \left\| {{\mathit{\boldsymbol{r}}_y}} \right\|}} $

(3)

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

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

$ {\rm{JACCARD}}\left( {x,y} \right) = \frac{{X \cap Y}}{{X \cap Y}} $

(4)

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

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

$ K\left( {\mathit{\boldsymbol{x}},\mathit{\boldsymbol{x'}}} \right) = \exp \left( { - \frac{{{{\left\| {x - x'} \right\|}^2}}}{{2{\sigma ^2}}}} \right) $

(5)

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

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

$ \begin{array}{*{20}{c}} {{\rm{dis}}\left( {x,y} \right) = R \times a\cos \left( {\sin {x_{{\rm{lat}}}}\sin {y_{{\rm{lat}}}} + } \right.}\\ {\left. {\cos {x_{{\rm{lat}}}}\cos {y_{{\rm{lat}}}}\cos \left( {{x_{\ln g}} - {y_{\ln g}}} \right)} \right)} \end{array} $

(6)

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

$ {\rm{LOC}}\left( {x,y} \right) = \exp \left( { - \frac{{{\rm{dis}}\left( {x,y} \right)}}{l}} \right) $

(7)

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

2 多核学习方法 2.1 合成核方法

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

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

$ \begin{array}{*{20}{c}} {{\rm{sim}}\left( {x,y} \right) = \sum\limits_{i = 0}^3 {{w_i}{\rm{si}}{{\rm{m}}_i}\left( {x,y} \right)} }\\ {{\rm{s}}.\;{\rm{t}}.\;\;\;\;\;\sum\limits_{i = 0}^3 {{w_i}} = 1,{w_i} \ge 0} \end{array} $

(8)

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

2.2 合成核的学习方法

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

$ P\left( {i,u} \right) = \frac{{\sum\limits_{j \in S{N_i}} {{\rm{sim}}\left( {i,j} \right)} \times {r_{j,u}}}}{{\sum\limits_{j \in S{N_i}} {{\rm{sim}}\left( {i,j} \right)} }} $

(9)

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

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

$ {\rm{loss}}\left( {v,u} \right) = \frac{1}{2}{\left( {P\left( {v,u} \right) - y\left( {v,u} \right)} \right)^2} $

(10)

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

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

(1) 损失函数的梯度形式：$ \left( {P\left( {v, u} \right) - y\left( {v, u} \right)} \right){\rm{ }}\frac{{\partial P\left( {v, u} \right)}}{{\partial w}}$，由于y(v, u)是常数，P(v, u)可以通过式(9)求出，因此，只需要考虑P(v, u)/w的情况。

(2) 形式化解：$\frac{{\partial P\left( {v, u} \right)}}{{\partial \mathit{\boldsymbol{w}}}}{\rm{ }} = \partial \left\{ {\frac{{\sum\limits_{i = 0}^3 {{w_i}} \sum\limits_{j \in S{N_v}} {{r_{j, u}}{\rm{si}}{{\rm{m}}_i}\left( {v, j} \right)} }}{{\sum\limits_{i = 0}^3 {{w_i}} \sum\limits_{j \in S{N_v}} {{\rm{si}}{{\rm{m}}_i}\left( {v, j} \right)} }}} \right\}{\rm{ }}/\partial \mathit{\boldsymbol{ w}} $

(3) 简化过程，令$ {a_i} = \sum\limits_{j \in S{N_v}} {{r_{j, u}}{\rm{si}}{{\rm{m}}_i}\left( {v, j} \right)} , {b_i} = \sum\limits_{j \in S{N_v}} {{\rm{si}}{{\rm{m}}_i}\left( {v, j} \right)} $，因此，整体过程可以简化为向量的形式。梯度公式为$ \frac{{\partial P\left( {v, u} \right)}}{{\partial \mathit{\boldsymbol{w}}}}{\rm{ }} = \partial \left\{ {\frac{{\mathit{\boldsymbol{a}}{\mathit{\boldsymbol{}}^{\rm{T}}}\mathit{\boldsymbol{w}}}}{{\mathit{\boldsymbol{b}}{^{\rm{T}}}\mathit{\boldsymbol{w}}}}} \right\}/\partial \mathit{\boldsymbol{w}}$，其中a，b，w均为列向量。

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

$ \frac{{\partial P\left( {v,u} \right)}}{{\partial \mathit{\boldsymbol{w}}}} = \frac{{{\mathit{\boldsymbol{b}}^{\rm{T}}}\mathit{\boldsymbol{wa}} - {\mathit{\boldsymbol{a}}^{\rm{T}}}\mathit{\boldsymbol{wb}}}}{{{{\left( {{\mathit{\boldsymbol{b}}^{\rm{T}}}\mathit{\boldsymbol{w}}} \right)}^2}}} $

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

$ \frac{{\partial {\rm{loss}}\left( {v,u} \right)}}{{\partial \mathit{\boldsymbol{w}}}} = \left( {P\left( {v,u} \right) - y\left( {v,u} \right)} \right)\frac{{{\mathit{\boldsymbol{b}}^{\rm{T}}}\mathit{\boldsymbol{wa}} - {\mathit{\boldsymbol{a}}^{\rm{T}}}\mathit{\boldsymbol{wb}}}}{{{{\left( {{\mathit{\boldsymbol{b}}^{\rm{T}}}\mathit{\boldsymbol{w}}} \right)}^2}}} $

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

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

输出：推荐用户-项目对

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

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

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

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

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

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

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

3 实验结果分析 3.1 数据集

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

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

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

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

3.2 推荐评分标准

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

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

$ {\rm{Precision}} = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FP}}}} $

(11)

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

$ {\rm{Recall}} = \frac{{{\rm{TP}}}}{{{\rm{TP}} + {\rm{FN}}}} $

(12)

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

$ {F_1} = 2 \times \frac{{{\rm{Precision}} \times {\rm{Recall}}}}{{{\rm{Precision}} + {\rm{Recall}}}} $

(13)

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

3.3 实验结果

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

$ {\rm{MAE}} = \frac{1}{n}\sum\limits_{i = 1}^n {\left| {{f_i} - {y_i}} \right|} $

(14)

式中：f_i表示预测值，y_i代表观察值。

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

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

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

4 结束语

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