0 引言

　　赞助商搜索(Sponsored Search)是互联网广告的一种投放形式，其广告投放的目标位置是搜索引擎返回的搜索结果页面[1]。在赞助商搜索场景中，搜索引擎对用户可能查询的关键词进行竞拍，广告主根据自己的需求来竞拍这些关键词。目前广告主的主要付费方式为按点击付费，若单位点击的付费额记为CPC(Cost Per Click)，则搜索引擎的收益记为CTR×CPC，点击率(Click Through Rate，CTR)表示用户可能对广告进行点击的概率。搜索引擎想获得最大的收益就需要把CTR×CPC大的广告展示在靠前的位置。因此，广告的推荐是搜索广告领域中的一个关键问题，具有很高的研究价值。

　　近年来，国内外研究人员对搜索广告推荐问题进行了相关的研究。RENDLE S[2-3]提出了因子分解机模型，该模型利用参数的因子分解来对不同类别的特征之间的交互进行建模，值得注意的是，很多用来训练的特征往往会被用户视为隐私而不愿意被广告推荐系统提取使用。ANASTASAKOS T[4]等将协同过滤应用到了广告推荐系统中。文中简单地将展示广告的页面视为基本协同推荐系统中的“用户”，将页面上展示的广告看成是相应的“产品”，在某个页面中广告的点击率看成是“用户”对“产品”的评分，使用传统的基于用户的协同过滤方法进行广告的推荐取得了很好的效果，但该方法在面对稀疏矩阵时会出现预测质量下降的问题。SHEN S[5]等提出了一种基于矩阵分解的个性化广告推荐模型。该模型将广告-查询矩阵分解为表示广告的广告特征矩阵和表示查询的查询特征矩阵，此时广告和查询都被投影到了相应的特征空间中，该模型在稀疏矩阵中取得了很好的推荐效果。

　　矩阵分解是一种基于模型的协同过滤方法，与基于邻域的协同过滤方法相比，不再直接利用相似用户或产品做出推荐。所以矩阵分解并不是基于邻域的协同过滤的改进，两者是从不同方向来改进推荐结果的。本文通过将两者的优势结合提出了ASN-MF算法（An ad similarity network Aided Matrix Factorization Algorithm），该算法通过建立广告相似性网络得到广告的相似性关系，将这样的关系加入到矩阵分解的损失函数之中，使得广告特征矩阵能够朝着相似邻居的方向进化。本文提出了基于LDA模型的广告相似性衡量方法，从语义层面衡量广告的相似性，并构建了广告相似性网络；通过将相似广告信息加入到矩阵分解的损失函数中，将基于模型的协同过滤方法同基于邻域的协同过滤方法结合起来，提高了推荐的质量。

1 广告相似性网络的构建

　　本文利用LDA(Latent Dirichlet Allocation)模型为广告进行主题建模，利用广告的主题分布衡量广告的主题相似性，进而构建广告的相似性网络。

1.1 LDA模型

　　LDA是一个三层产生式概率模型，包含词、主题和文档三层结构[6]。给定一个文档集合D，包含M 篇文档和V个不同的词汇。在集合D对应的LDA模型中，假设主题个数为K，则LDA生成文档的过程可以用图1所示的贝叶斯网络图来表示。首先，LDA从参数为?茁的Dirichlet分布中抽取主题与单词的关系?渍。LDA生成一篇文档d时，从参数为?琢的Dirichlet分布中随机选择一个?转维的向量?兹d，表示文档d中的主题分布，根据这个分布对文档d中的所有单词，从参数为?兹d的多项式分布中随机选择zdn，代表当前单词选择的主题，最后从参数为?渍Zdn的多项式分布中抽取出单词wdn。

　　图1中方框表示循环，右下角的M、N、K表示循环次数，其中，M是文档集合中文档的个数，N是文档中单词的个数，K是主题的个数。实心节点代表观测变量，文中表示文档中的单词，空心节点表示隐含变量，箭头表示依赖关系。?琢是一个K维的Dirichlet参数，?茁是一个K×V的参数矩阵。

　　LDA提取文档集中隐含主题的过程就是根据上述文档产生的过程，在文本的单词作为可观测变量的情况下，反推出其相应的隐含变量，从而得到各文档的主题概率分布?兹，进而挖掘出文本中潜在的语义知识。

　1.2 广告相似性计算

　　利用传统的文本相似度方法来衡量广告之间的相似度，存在维度大的问题，本文利用LDA模型将广告文本映射到主题空间，利用广告的主题分布来计算两个广告之间的相似度，其维度控制在T维(T是主题的个数)，能够有效降低文本表示的维度。此外，从语义层面衡量广告之间的相似性能够更加贴近现实。

　　本文将广告的描述词集合作为广告的描述文档，利用1.1节介绍的LDA主题模型对广告文档进行建模，得到广告的主题概率分布矩阵：

　　对于两个广告a和b，本文通过计算向量之间的余弦夹角来衡量它们的相似性：

1.3 构建广告相似性网络

　　本文利用广告之间的相似度建立一个广告相似性网络，构建过程如下：首先根据式(2)计算任意两个广告的相似度，据此生成了广告相似性矩阵，这样就可以以广告为节点、以广告之间的相似度为边的权值，构造出广告的相似性网络。然后通过一个相似性阈值u过滤网络中关系较弱的边，最终得到一个关系更紧密的广告相似性网络G=(A，E)，其中A表示网络中的广告节点集合，边集E表示广告之间的相似性关系。此外，本文用Fa∈A定义广告a的邻居集合，即与广告a有边相连的广告的集合。广告相似性网络如图2所示。

2 结合广告相似性网络的广告推荐算法

　　2.1 搜索广告推荐中的矩阵分解

　　矩阵分解的目标是把一个原始矩阵分解为两个特征矩阵相乘的形式，而原矩阵可以利用两个特征矩阵近似重建。在搜索广告推荐问题的背景下，本文用a={A1，A2，…，Am}表示广告集，用q={Q1，Q2，…，Qn}表示查询词集，用在该查询词下广告的点击率表示广告-查询词的相关度（查询词Qn下广告Am的相关度表示为Rm，n），所有相关度R={Rm，n|Am∈a，Qn∈q}构建了一个广告-查询词相关度矩阵。本文利用矩阵分解方法将广告-查询词相关度矩阵R∈Rm×n(m是广告的数量，n是查询词的数量)分解为一个广告特征矩阵A∈Rl×m和一个查询词特征矩阵Q∈Rl×n：

　　R≈ATQ(3)

　　其中l是潜在特征向量的维度，每一个维度表示一种特征，利用这些特征向量来描述一个广告或查询词。因此，结果来捕获广告a与查询词b之间的相关性，即考虑到所有潜在特征时，广告a与查询词b的相关性。的值越大，说明广告a与查询词b的相关性越大。

　　为了使广告特征矩阵与查询词特征矩阵的乘积接近R，考虑到广告-查询词相关度矩阵的稀疏，即R中的很大一部相关度缺失，定义下面的目标函数：

　　其中Iij表示在广告-查询词相关度矩阵中广告i与查询词j之间的相关度，如果已存在，Iij就为1，否则为0。此外，为了避免过度拟合，为方程增加了正则化项：

　　其中W(W是一个X×Y的矩阵)是Frobenius范数，参数l控制着正规化程度。

2.2 结合广告相似性网络的矩阵分解

　　为了结合广告相似性网络信息，给矩阵分解目标函数引入一个相似广告正则化项，通过学习广告相似性网络中邻居广告来进一步推断广告与一个查询的相关度。

　　在广告相似性网络中，广告与其邻居广告有着不同的相似度，因此不能平等地考虑所有邻居广告。为了解决相似度的差异性，在引入相似广告正则化项时考虑到广告与其邻居之间的相似性：

　　其中a是一个常数用来控制正则化的程度。S(j，f)表示广告aj与其邻居af之间的相似性，这个相似性的值由在1.3中建立的广告相似性网络得到。

　　然后把它应用到2.1节提出的搜索广告矩阵分解推荐模型中，式(5)被改写为：

　　本文使用随机梯度下降方法进行迭代训练，通过不断更新特征矩阵，最终求得最优解。

　　其中g为学习速率。

　　通过引入相似广告正则化项，能够使广告特征矩阵向着邻居的方向进化，即在广告相似度网络中相似度较高的广告会拥有相似的潜在特征向量。

2.3 结合广告相似性网络的广告推荐算法

　　本节总结了ASN-MF算法的过程：

　　输入：广告集合a、查询词集合q、广告-查询词相关度矩阵R、广告描述文档和相关参数。

　　输出：广告-查询词矩阵相关度。

　　(1)对广告数据进行基于LDA的建模，得到广告的主题分布矩阵。

　　(2)根据式(2)计算广告之间的相似度，构建广告相似性网络G=(A，E)。

　　(3)根据式(7)将广告相似性网络融入矩阵分解方法，得到目标函数l。

　　(4)利用随机梯度下降的方法，求得广告潜在特征矩阵A和查询词潜在特征矩阵Q。

　　(5)根据得到的潜在特征矩阵，采用式(3)进行广告和查询词的相关度预测，计算每个广告与查询词的预测相关度。

3 实验

3.1 数据集

　　实验数据来自KDD Cup 2012-Track2中的数据集，该数据集是腾讯搜搜(SOSO)提供的搜索广告点击数据。此外，搜搜还提供了一个广告描述文档，本文用该文档对广告进行LDA建模。

　　实验分别从数据集中抽取90%、80%、70%、60%作为训练数据集，分别记为训练集1、训练集2、训练集3和训练集4，在数据稀疏程度不同时比较算法的效果。抽样后广告和查询词数量的统计情况如表1所示。

　3.2 实验结果

　　USN-TF模型研究的目的是提高搜索广告推荐的准确度，而推荐问题主要影响广告的排序和展现，因此，本文使用曲线下面积(Area Under Curve，AUC)指标来衡量算法的效果。

　　3.2.1 潜在特征向量的维度l的设定

　　以训练集2中的数据作为实验数据，图3表示在潜在特征向量的维度l取值不同时，ASN-MF模型预测准确度的变化。从图中可以看出，随着隐含特征向量维度l的增加，AUC的值逐步提高；当潜在特征向量的维度从0增加到8时，AUC的值提升明显；当因子分解维度在8～20之间时， AUC的值增长十分缓慢。由于随着维度的增加，算法的计算效率会下降，为了权衡准确度和时间效率，后面的实验中取l值为8。

　　3.2.2 预测质量分析

　　为了检验算法的有效性，本实验将ASN-MF与传统的协同过滤方法（CF）和矩阵分解方法（MF）进行对比，实验结果如图4所示。

　　从图4可以看出，在预测广告的点击率时本文提出的方法有更高的预测准确度，具体来说，在4个训练数据集下，ASN-MF相较于CF和MF分别提高了5.7%~9.5%和3.5%~4.3%。这是因为USN-TF既具备矩阵分解模型在处理稀疏矩阵时的优势，又能够进一步利用邻居广告对分解出的广告特征矩阵进行进一步的加工，使得预测的准确度进一步提高。本实验也证明了将矩阵分解与基于邻居的协同过滤结合能够提高预测的质量。

　　从图4还可以看出，在数据稀疏度逐渐增大的情况下，USN-TF相比于MF依旧保持了较高的准确度，而CF表现相对较差。这是因为USN-TF和MF都是利用分解得到的两个特征矩阵来还原原始的矩阵，对矩阵中不存在的元素可以根据其特征矩阵重新构造出来。而传统的基于邻域的协同过滤方法在数据稀疏的情况下很难找到相似的邻居，所以导致推荐的准确度大幅下降。

4 结论

　　本文首先从广告的语义层面出发，基于广告的主题分布建立了广告相似性网络，然后讨论了用矩阵分解方法进行广告推荐的过程，最后通过引入相似性网络中的广告的邻居使训练出来的广告特征矩阵带有相似邻居的性质，在解决数据稀疏性问题的同时进一步提高了推荐准确度。实验表明，结合了邻域的矩阵分解算法比单一算法拥有更高的推荐质量。

参考文献

　　[1] 周傲英，周敏奇，宫学庆.计算广告：以数据为核心的Web综合应用[J].计算机学报，2011，34(10)：1805-1819.

　　[2] RENDLE S.Factorization machines[C].Proceedings of the 10th IEEE International Conference on Data Mining.Sydney，NSW：IEEE Press，2010：995-1000.

　　[3] RENDLE S.Social network and click-through prediction with factorization machines[J].KDD Cup，2012.

　　[4] ANASTASAKOS T，HILLARD D，KSHETRAMADE S，et al.A collaborative filtering approach to ad recommendation using the query-ad click graph[C].Proceedings of the 18th ACM Conference on Information and knowledge Management.Hong Kong，China：ACM，2009：1927-1930.

　　[5] SHEN S，HU B，CHEN W，et al.Personalized click model through collaborative filtering[C].5th ACM International Conference on Web Search and Data Mining，Seattle，WA，United states: Association for Computing Machinery，2012：323-332.

　　[6] BLEI D M，NG A Y，JORDAN M I.Latent dirichlet allocation[J].The Journal of machine learning research，2003(3)：993-1022.