0 引言

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

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

　　矩陣分解是一種基于模型的協(xié)同過(guò)濾方法，與基于鄰域的協(xié)同過(guò)濾方法相比,，不再直接利用相似用戶或產(chǎn)品做出推薦,。所以矩陣分解并不是基于鄰域的協(xié)同過(guò)濾的改進(jìn)，兩者是從不同方向來(lái)改進(jìn)推薦結(jié)果的。本文通過(guò)將兩者的優(yōu)勢(shì)結(jié)合提出了ASN-MF算法（An ad similarity network Aided Matrix Factorization Algorithm）,，該算法通過(guò)建立廣告相似性網(wǎng)絡(luò)得到廣告的相似性關(guān)系,，將這樣的關(guān)系加入到矩陣分解的損失函數(shù)之中，使得廣告特征矩陣能夠朝著相似鄰居的方向進(jìn)化,。本文提出了基于LDA模型的廣告相似性衡量方法,，從語(yǔ)義層面衡量廣告的相似性，并構(gòu)建了廣告相似性網(wǎng)絡(luò),；通過(guò)將相似廣告信息加入到矩陣分解的損失函數(shù)中,，將基于模型的協(xié)同過(guò)濾方法同基于鄰域的協(xié)同過(guò)濾方法結(jié)合起來(lái)，提高了推薦的質(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對(duì)應(yīng)的LDA模型中,，假設(shè)主題個(gè)數(shù)為K,，則LDA生成文檔的過(guò)程可以用圖1所示的貝葉斯網(wǎng)絡(luò)圖來(lái)表示。首先,，LDA從參數(shù)為?茁的Dirichlet分布中抽取主題與單詞的關(guān)系?漬,。LDA生成一篇文檔d時(shí)，從參數(shù)為?琢的Dirichlet分布中隨機(jī)選擇一個(gè)?轉(zhuǎn)維的向量?茲d,，表示文檔d中的主題分布,，根據(jù)這個(gè)分布對(duì)文檔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)代表觀測(cè)變量,，文中表示文檔中的單詞，空心節(jié)點(diǎn)表示隱含變量,，箭頭表示依賴關(guān)系,。?琢是一個(gè)K維的Dirichlet參數(shù)，?茁是一個(gè)K×V的參數(shù)矩陣,。

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

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

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

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

　　對(duì)于兩個(gè)廣告a和b，本文通過(guò)計(jì)算向量之間的余弦?jiàn)A角來(lái)衡量它們的相似性：

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

　　本文利用廣告之間的相似度建立一個(gè)廣告相似性網(wǎng)絡(luò),，構(gòu)建過(guò)程如下：首先根據(jù)式(2)計(jì)算任意兩個(gè)廣告的相似度,，據(jù)此生成了廣告相似性矩陣，這樣就可以以廣告為節(jié)點(diǎn),、以廣告之間的相似度為邊的權(quán)值,，構(gòu)造出廣告的相似性網(wǎng)絡(luò)。然后通過(guò)一個(gè)相似性閾值u過(guò)濾網(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è)特征矩陣近似重建,。在搜索廣告推薦問(wèn)題的背景下,，本文用a={A1，A2,，…,，Am}表示廣告集，用q={Q1,，Q2,，…，Qn}表示查詢?cè)~集,，用在該查詢?cè)~下廣告的點(diǎn)擊率表示廣告-查詢?cè)~的相關(guān)度（查詢?cè)~Qn下廣告Am的相關(guān)度表示為Rm,，n），所有相關(guān)度R={Rm,，n|Am∈a,，Qn∈q}構(gòu)建了一個(gè)廣告-查詢?cè)~相關(guān)度矩陣。本文利用矩陣分解方法將廣告-查詢?cè)~相關(guān)度矩陣R∈Rm×n(m是廣告的數(shù)量,，n是查詢?cè)~的數(shù)量)分解為一個(gè)廣告特征矩陣A∈Rl×m和一個(gè)查詢?cè)~特征矩陣Q∈Rl×n：

　　R≈ATQ(3)

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

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

　　其中Iij表示在廣告-查詢?cè)~相關(guān)度矩陣中廣告i與查詢?cè)~j之間的相關(guān)度,，如果已存在，Iij就為1,，否則為0,。此外，為了避免過(guò)度擬合,，為方程增加了正則化項(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),，通過(guò)學(xué)習(xí)廣告相似性網(wǎng)絡(luò)中鄰居廣告來(lái)進(jìn)一步推斷廣告與一個(gè)查詢的相關(guān)度。

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

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

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

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

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

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

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

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

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

　　輸出：廣告-查詢?cè)~矩陣相關(guān)度。

　　(1)對(duì)廣告數(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和查詢?cè)~潛在特征矩陣Q。

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

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

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

　　實(shí)驗(yàn)數(shù)據(jù)來(lái)自KDD Cup 2012-Track2中的數(shù)據(jù)集,，該數(shù)據(jù)集是騰訊搜搜(SOSO)提供的搜索廣告點(diǎn)擊數(shù)據(jù),。此外，搜搜還提供了一個(gè)廣告描述文檔,，本文用該文檔對(duì)廣告進(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í)比較算法的效果。抽樣后廣告和查詢?cè)~數(shù)量的統(tǒng)計(jì)情況如表1所示,。

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

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

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

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

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

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

　　從圖4可以看出，在預(yù)測(cè)廣告的點(diǎn)擊率時(shí)本文提出的方法有更高的預(yù)測(cè)準(zhǔn)確度,，具體來(lái)說(shuō),，在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)勢(shì),，又能夠進(jìn)一步利用鄰居廣告對(duì)分解出的廣告特征矩陣進(jìn)行進(jìn)一步的加工，使得預(yù)測(cè)的準(zhǔn)確度進(jìn)一步提高,。本實(shí)驗(yàn)也證明了將矩陣分解與基于鄰居的協(xié)同過(guò)濾結(jié)合能夠提高預(yù)測(cè)的質(zhì)量,。

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

4 結(jié)論

　　本文首先從廣告的語(yǔ)義層面出發(fā),，基于廣告的主題分布建立了廣告相似性網(wǎng)絡(luò),，然后討論了用矩陣分解方法進(jìn)行廣告推薦的過(guò)程，最后通過(guò)引入相似性網(wǎng)絡(luò)中的廣告的鄰居使訓(xùn)練出來(lái)的廣告特征矩陣帶有相似鄰居的性質(zhì),，在解決數(shù)據(jù)稀疏性問(wèn)題的同時(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.