0 引言

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

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

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

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

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

　　1.1 LDA模型

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

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

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

　　1.2 廣告相似性計算

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

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

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

　　1.3 構建廣告相似性網(wǎng)絡

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

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

　　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是廣告的數(shù)量，n是查詢詞的數(shù)量)分解為一個廣告特征矩陣A∈Rl×m和一個查詢詞特征矩陣Q∈Rl×n：

　　R≈ATQ(3)

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

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

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

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

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

　　為了結合廣告相似性網(wǎng)絡信息，給矩陣分解目標函數(shù)引入一個相似廣告正則化項，通過學習廣告相似性網(wǎng)絡中鄰居廣告來進一步推斷廣告與一個查詢的相關度。

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

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

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

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

　　其中g為學習速率。

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

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

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

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

　　輸出：廣告-查詢詞矩陣相關度。

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

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

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

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

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

3 實驗

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

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

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

　　3.2 實驗結果

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

　　3.2.1 潛在特征向量的維度l的設定

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

　　3.2.2 預測質(zhì)量分析

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

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

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

4 結論

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

　　參考文獻

　　[1] 周傲英，周敏奇，宮學慶.計算廣告：以數(shù)據(jù)為核心的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.