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.