0 引言

　　贊助商搜索(Sponsored Search)是互聯(lián)網(wǎng)廣告的一種投放形式，其廣告投放的目標(biāo)位置是搜索引擎返回的搜索結(jié)果頁面[1]。在贊助商搜索場景中，搜索引擎對用戶可能查詢的關(guān)鍵詞進(jìn)行競拍，廣告主根據(jù)自己的需求來競拍這些關(guān)鍵詞。目前廣告主的主要付費(fèi)方式為按點(diǎn)擊付費(fèi)，若單位點(diǎn)擊的付費(fèi)額記為CPC(Cost Per Click)，則搜索引擎的收益記為CTR×CPC，點(diǎn)擊率(Click Through Rate，CTR)表示用戶可能對廣告進(jìn)行點(diǎn)擊的概率。搜索引擎想獲得最大的收益就需要把CTR×CPC大的廣告展示在靠前的位置。因此，廣告的推薦是搜索廣告領(lǐng)域中的一個(gè)關(guān)鍵問題，具有很高的研究價(jià)值。

　　近年來，國內(nèi)外研究人員對搜索廣告推薦問題進(jìn)行了相關(guān)的研究。RENDLE S[2-3]提出了因子分解機(jī)模型，該模型利用參數(shù)的因子分解來對不同類別的特征之間的交互進(jìn)行建模，值得注意的是，很多用來訓(xùn)練的特征往往會(huì)被用戶視為隱私而不愿意被廣告推薦系統(tǒng)提取使用。ANASTASAKOS T[4]等將協(xié)同過濾應(yīng)用到了廣告推薦系統(tǒng)中。文中簡單地將展示廣告的頁面視為基本協(xié)同推薦系統(tǒng)中的“用戶”，將頁面上展示的廣告看成是相應(yīng)的“產(chǎn)品”，在某個(gè)頁面中廣告的點(diǎn)擊率看成是“用戶”對“產(chǎn)品”的評分，使用傳統(tǒng)的基于用戶的協(xié)同過濾方法進(jìn)行廣告的推薦取得了很好的效果，但該方法在面對稀疏矩陣時(shí)會(huì)出現(xiàn)預(yù)測質(zhì)量下降的問題。SHEN S[5]等提出了一種基于矩陣分解的個(gè)性化廣告推薦模型。該模型將廣告-查詢矩陣分解為表示廣告的廣告特征矩陣和表示查詢的查詢特征矩陣，此時(shí)廣告和查詢都被投影到了相應(yīng)的特征空間中，該模型在稀疏矩陣中取得了很好的推薦效果。

　　矩陣分解是一種基于模型的協(xié)同過濾方法，與基于鄰域的協(xié)同過濾方法相比，不再直接利用相似用戶或產(chǎn)品做出推薦。所以矩陣分解并不是基于鄰域的協(xié)同過濾的改進(jìn)，兩者是從不同方向來改進(jìn)推薦結(jié)果的。本文通過將兩者的優(yōu)勢結(jié)合提出了ASN-MF算法（An ad similarity network Aided Matrix Factorization Algorithm），該算法通過建立廣告相似性網(wǎng)絡(luò)得到廣告的相似性關(guān)系，將這樣的關(guān)系加入到矩陣分解的損失函數(shù)之中，使得廣告特征矩陣能夠朝著相似鄰居的方向進(jìn)化。本文提出了基于LDA模型的廣告相似性衡量方法，從語義層面衡量廣告的相似性，并構(gòu)建了廣告相似性網(wǎng)絡(luò)；通過將相似廣告信息加入到矩陣分解的損失函數(shù)中，將基于模型的協(xié)同過濾方法同基于鄰域的協(xié)同過濾方法結(jié)合起來，提高了推薦的質(zhì)量。

1 廣告相似性網(wǎng)絡(luò)的構(gòu)建

　　本文利用LDA(Latent Dirichlet Allocation)模型為廣告進(jìn)行主題建模，利用廣告的主題分布衡量廣告的主題相似性，進(jìn)而構(gòu)建廣告的相似性網(wǎng)絡(luò)。

　　1.1 LDA模型

　　LDA是一個(gè)三層產(chǎn)生式概率模型，包含詞、主題和文檔三層結(jié)構(gòu)[6]。給定一個(gè)文檔集合D，包含M 篇文檔和V個(gè)不同的詞匯。在集合D對應(yīng)的LDA模型中，假設(shè)主題個(gè)數(shù)為K，則LDA生成文檔的過程可以用圖1所示的貝葉斯網(wǎng)絡(luò)圖來表示。首先，LDA從參數(shù)為?茁的Dirichlet分布中抽取主題與單詞的關(guān)系?漬。LDA生成一篇文檔d時(shí)，從參數(shù)為?琢的Dirichlet分布中隨機(jī)選擇一個(gè)?轉(zhuǎn)維的向量?茲d，表示文檔d中的主題分布，根據(jù)這個(gè)分布對文檔d中的所有單詞，從參數(shù)為?茲d的多項(xiàng)式分布中隨機(jī)選擇zdn，代表當(dāng)前單詞選擇的主題，最后從參數(shù)為?漬Zdn的多項(xiàng)式分布中抽取出單詞wdn。

　　圖1中方框表示循環(huán)，右下角的M、N、K表示循環(huán)次數(shù)，其中，M是文檔集合中文檔的個(gè)數(shù)，N是文檔中單詞的個(gè)數(shù)，K是主題的個(gè)數(shù)。實(shí)心節(jié)點(diǎn)代表觀測變量，文中表示文檔中的單詞，空心節(jié)點(diǎn)表示隱含變量，箭頭表示依賴關(guān)系。?琢是一個(gè)K維的Dirichlet參數(shù)，?茁是一個(gè)K×V的參數(shù)矩陣。

　　LDA提取文檔集中隱含主題的過程就是根據(jù)上述文檔產(chǎn)生的過程，在文本的單詞作為可觀測變量的情況下，反推出其相應(yīng)的隱含變量，從而得到各文檔的主題概率分布?茲，進(jìn)而挖掘出文本中潛在的語義知識(shí)。

　　1.2 廣告相似性計(jì)算

　　利用傳統(tǒng)的文本相似度方法來衡量廣告之間的相似度，存在維度大的問題，本文利用LDA模型將廣告文本映射到主題空間，利用廣告的主題分布來計(jì)算兩個(gè)廣告之間的相似度，其維度控制在T維(T是主題的個(gè)數(shù))，能夠有效降低文本表示的維度。此外，從語義層面衡量廣告之間的相似性能夠更加貼近現(xiàn)實(shí)。

　　本文將廣告的描述詞集合作為廣告的描述文檔，利用1.1節(jié)介紹的LDA主題模型對廣告文檔進(jìn)行建模，得到廣告的主題概率分布矩陣：

　　對于兩個(gè)廣告a和b，本文通過計(jì)算向量之間的余弦夾角來衡量它們的相似性：

　　1.3 構(gòu)建廣告相似性網(wǎng)絡(luò)

　　本文利用廣告之間的相似度建立一個(gè)廣告相似性網(wǎng)絡(luò)，構(gòu)建過程如下：首先根據(jù)式(2)計(jì)算任意兩個(gè)廣告的相似度，據(jù)此生成了廣告相似性矩陣，這樣就可以以廣告為節(jié)點(diǎn)、以廣告之間的相似度為邊的權(quán)值，構(gòu)造出廣告的相似性網(wǎng)絡(luò)。然后通過一個(gè)相似性閾值u過濾網(wǎng)絡(luò)中關(guān)系較弱的邊，最終得到一個(gè)關(guān)系更緊密的廣告相似性網(wǎng)絡(luò)G=(A，E)，其中A表示網(wǎng)絡(luò)中的廣告節(jié)點(diǎn)集合，邊集E表示廣告之間的相似性關(guān)系。此外，本文用Fa∈A定義廣告a的鄰居集合，即與廣告a有邊相連的廣告的集合。廣告相似性網(wǎng)絡(luò)如圖2所示。

2 結(jié)合廣告相似性網(wǎng)絡(luò)的廣告推薦算法

　　2.1 搜索廣告推薦中的矩陣分解

　　矩陣分解的目標(biāo)是把一個(gè)原始矩陣分解為兩個(gè)特征矩陣相乘的形式，而原矩陣可以利用兩個(gè)特征矩陣近似重建。在搜索廣告推薦問題的背景下，本文用a={A1，A2，…，Am}表示廣告集，用q={Q1，Q2，…，Qn}表示查詢詞集，用在該查詢詞下廣告的點(diǎn)擊率表示廣告-查詢詞的相關(guān)度（查詢詞Qn下廣告Am的相關(guān)度表示為Rm，n），所有相關(guān)度R={Rm，n|Am∈a，Qn∈q}構(gòu)建了一個(gè)廣告-查詢詞相關(guān)度矩陣。本文利用矩陣分解方法將廣告-查詢詞相關(guān)度矩陣R∈Rm×n(m是廣告的數(shù)量，n是查詢詞的數(shù)量)分解為一個(gè)廣告特征矩陣A∈Rl×m和一個(gè)查詢詞特征矩陣Q∈Rl×n：

　　R≈ATQ(3)

　　其中l(wèi)是潛在特征向量的維度，每一個(gè)維度表示一種特征，利用這些特征向量來描述一個(gè)廣告或查詢詞。因此，結(jié)果來捕獲廣告a與查詢詞b之間的相關(guān)性，即考慮到所有潛在特征時(shí)，廣告a與查詢詞b的相關(guān)性。的值越大，說明廣告a與查詢詞b的相關(guān)性越大。

　　為了使廣告特征矩陣與查詢詞特征矩陣的乘積接近R，考慮到廣告-查詢詞相關(guān)度矩陣的稀疏，即R中的很大一部相關(guān)度缺失，定義下面的目標(biāo)函數(shù)：

　　其中Iij表示在廣告-查詢詞相關(guān)度矩陣中廣告i與查詢詞j之間的相關(guān)度，如果已存在，Iij就為1，否則為0。此外，為了避免過度擬合，為方程增加了正則化項(xiàng)：

　　其中W(W是一個(gè)X×Y的矩陣)是Frobenius范數(shù)，參數(shù)l控制著正規(guī)化程度。

　　2.2 結(jié)合廣告相似性網(wǎng)絡(luò)的矩陣分解

　　為了結(jié)合廣告相似性網(wǎng)絡(luò)信息，給矩陣分解目標(biāo)函數(shù)引入一個(gè)相似廣告正則化項(xiàng)，通過學(xué)習(xí)廣告相似性網(wǎng)絡(luò)中鄰居廣告來進(jìn)一步推斷廣告與一個(gè)查詢的相關(guān)度。

　　在廣告相似性網(wǎng)絡(luò)中，廣告與其鄰居廣告有著不同的相似度，因此不能平等地考慮所有鄰居廣告。為了解決相似度的差異性，在引入相似廣告正則化項(xiàng)時(shí)考慮到廣告與其鄰居之間的相似性：

　　其中a是一個(gè)常數(shù)用來控制正則化的程度。S(j，f)表示廣告aj與其鄰居af之間的相似性，這個(gè)相似性的值由在1.3中建立的廣告相似性網(wǎng)絡(luò)得到。

　　然后把它應(yīng)用到2.1節(jié)提出的搜索廣告矩陣分解推薦模型中，式(5)被改寫為：

　　本文使用隨機(jī)梯度下降方法進(jìn)行迭代訓(xùn)練，通過不斷更新特征矩陣，最終求得最優(yōu)解。

　　其中g(shù)為學(xué)習(xí)速率。

　　通過引入相似廣告正則化項(xiàng)，能夠使廣告特征矩陣向著鄰居的方向進(jìn)化，即在廣告相似度網(wǎng)絡(luò)中相似度較高的廣告會(huì)擁有相似的潛在特征向量。

　　2.3 結(jié)合廣告相似性網(wǎng)絡(luò)的廣告推薦算法

　　本節(jié)總結(jié)了ASN-MF算法的過程：

　　輸入：廣告集合a、查詢詞集合q、廣告-查詢詞相關(guān)度矩陣R、廣告描述文檔和相關(guān)參數(shù)。

　　輸出：廣告-查詢詞矩陣相關(guān)度。

　　(1)對廣告數(shù)據(jù)進(jìn)行基于LDA的建模，得到廣告的主題分布矩陣。

　　(2)根據(jù)式(2)計(jì)算廣告之間的相似度，構(gòu)建廣告相似性網(wǎng)絡(luò)G=(A，E)。

　　(3)根據(jù)式(7)將廣告相似性網(wǎng)絡(luò)融入矩陣分解方法，得到目標(biāo)函數(shù)l。

　　(4)利用隨機(jī)梯度下降的方法，求得廣告潛在特征矩陣A和查詢詞潛在特征矩陣Q。

　　(5)根據(jù)得到的潛在特征矩陣，采用式(3)進(jìn)行廣告和查詢詞的相關(guān)度預(yù)測，計(jì)算每個(gè)廣告與查詢詞的預(yù)測相關(guān)度。

3 實(shí)驗(yàn)

　　3.1 數(shù)據(jù)集

　　實(shí)驗(yàn)數(shù)據(jù)來自KDD Cup 2012-Track2中的數(shù)據(jù)集，該數(shù)據(jù)集是騰訊搜搜(SOSO)提供的搜索廣告點(diǎn)擊數(shù)據(jù)。此外，搜搜還提供了一個(gè)廣告描述文檔，本文用該文檔對廣告進(jìn)行LDA建模。

　　實(shí)驗(yàn)分別從數(shù)據(jù)集中抽取90%、80%、70%、60%作為訓(xùn)練數(shù)據(jù)集，分別記為訓(xùn)練集1、訓(xùn)練集2、訓(xùn)練集3和訓(xùn)練集4，在數(shù)據(jù)稀疏程度不同時(shí)比較算法的效果。抽樣后廣告和查詢詞數(shù)量的統(tǒng)計(jì)情況如表1所示。

　　3.2 實(shí)驗(yàn)結(jié)果

　　USN-TF模型研究的目的是提高搜索廣告推薦的準(zhǔn)確度，而推薦問題主要影響廣告的排序和展現(xiàn)，因此，本文使用曲線下面積(Area Under Curve，AUC)指標(biāo)來衡量算法的效果。

　　3.2.1 潛在特征向量的維度l的設(shè)定

　　以訓(xùn)練集2中的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，圖3表示在潛在特征向量的維度l取值不同時(shí)，ASN-MF模型預(yù)測準(zhǔn)確度的變化。從圖中可以看出，隨著隱含特征向量維度l的增加，AUC的值逐步提高；當(dāng)潛在特征向量的維度從0增加到8時(shí)，AUC的值提升明顯；當(dāng)因子分解維度在8～20之間時(shí)， AUC的值增長十分緩慢。由于隨著維度的增加，算法的計(jì)算效率會(huì)下降，為了權(quán)衡準(zhǔn)確度和時(shí)間效率，后面的實(shí)驗(yàn)中取l值為8。

　　3.2.2 預(yù)測質(zhì)量分析

　　為了檢驗(yàn)算法的有效性，本實(shí)驗(yàn)將ASN-MF與傳統(tǒng)的協(xié)同過濾方法（CF）和矩陣分解方法（MF）進(jìn)行對比，實(shí)驗(yàn)結(jié)果如圖4所示。

　　從圖4可以看出，在預(yù)測廣告的點(diǎn)擊率時(shí)本文提出的方法有更高的預(yù)測準(zhǔn)確度，具體來說，在4個(gè)訓(xùn)練數(shù)據(jù)集下，ASN-MF相較于CF和MF分別提高了5.7%~9.5%和3.5%~4.3%。這是因?yàn)閁SN-TF既具備矩陣分解模型在處理稀疏矩陣時(shí)的優(yōu)勢，又能夠進(jìn)一步利用鄰居廣告對分解出的廣告特征矩陣進(jìn)行進(jìn)一步的加工，使得預(yù)測的準(zhǔn)確度進(jìn)一步提高。本實(shí)驗(yàn)也證明了將矩陣分解與基于鄰居的協(xié)同過濾結(jié)合能夠提高預(yù)測的質(zhì)量。

　　從圖4還可以看出，在數(shù)據(jù)稀疏度逐漸增大的情況下，USN-TF相比于MF依舊保持了較高的準(zhǔn)確度，而CF表現(xiàn)相對較差。這是因?yàn)閁SN-TF和MF都是利用分解得到的兩個(gè)特征矩陣來還原原始的矩陣，對矩陣中不存在的元素可以根據(jù)其特征矩陣重新構(gòu)造出來。而傳統(tǒng)的基于鄰域的協(xié)同過濾方法在數(shù)據(jù)稀疏的情況下很難找到相似的鄰居，所以導(dǎo)致推薦的準(zhǔn)確度大幅下降。

4 結(jié)論

　　本文首先從廣告的語義層面出發(fā)，基于廣告的主題分布建立了廣告相似性網(wǎng)絡(luò)，然后討論了用矩陣分解方法進(jìn)行廣告推薦的過程，最后通過引入相似性網(wǎng)絡(luò)中的廣告的鄰居使訓(xùn)練出來的廣告特征矩陣帶有相似鄰居的性質(zhì)，在解決數(shù)據(jù)稀疏性問題的同時(shí)進(jìn)一步提高了推薦準(zhǔn)確度。實(shí)驗(yàn)表明，結(jié)合了鄰域的矩陣分解算法比單一算法擁有更高的推薦質(zhì)量。

　　參考文獻(xiàn)

　　[1] 周傲英，周敏奇，宮學(xué)慶.計(jì)算廣告：以數(shù)據(jù)為核心的Web綜合應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，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.