靳巖欽，張 敏，劉奕群，馬少平

(清華大學(xué) 智能技術(shù)與系統(tǒng)國家重點實驗室100084 北京)

近年來，搜索引擎的商業(yè)模式已經(jīng)逐漸轉(zhuǎn)化為搜索廣告，即搜索引擎針對用戶提交的查詢內(nèi)容，將相應(yīng)的廣告顯示在搜索結(jié)果頁面中，根據(jù)用戶對這些廣告的訪問和點擊情況，向廣告商收取相應(yīng)的費用［1］.因而用戶對廣告的實際點擊情況，直接影響搜索引擎的收入.于是搜索引擎投放廣告的點擊率分析已經(jīng)成為近年來研究的熱點.

現(xiàn)有的搜索廣告投放過程中并不區(qū)分用戶的意圖，只依靠關(guān)鍵詞匹配進行“普遍撒網(wǎng)”，實際點擊率很低，產(chǎn)生了很多無效廣告投放.而單純增加投放廣告的數(shù)量會嚴重影響普通用戶的使用體驗，甚至使用戶放棄用該搜索引擎.因此準確預(yù)測用戶的查詢是否具有廣告點擊意圖，從而有針對性地選擇投放內(nèi)容相關(guān)的廣告，具有很好的研究意義與應(yīng)用價值.

本文探討了從用戶查詢的廣告點擊意圖預(yù)測方法，首先介紹相關(guān)研究工作;然后分別提出兩種用戶查詢的廣告點擊意圖的預(yù)測模型，并基于大規(guī)模真實用戶查詢點擊日志給出相應(yīng)實驗結(jié)果;接下來通過廣告點擊曲線擬合模型分析方法的可行性;最后給出結(jié)論與未來工作.

1 相關(guān)工作

當(dāng)前提高廣告點擊率的工作主要面向上下文廣告和搜索廣告這兩種類型.

在上下文廣告方面，一些大公司在相關(guān)研究上起到主導(dǎo)作用.Yahoo!的研發(fā)人員提出了一系列提高上下文廣告投放相關(guān)性的方法，如B.Ribeiro-Neto 等［2］比較了若干種基于關(guān)鍵詞的頁面與廣告的匹配算法;A.Broder 等［3］利用海量數(shù)據(jù)和熱門廣告詞，建立了針對網(wǎng)頁以及廣告的分類體系，并利用相關(guān)類別改進廣告分類效果;隨后在文獻［4］中探討了根據(jù)用戶點擊反饋提高上下文廣告投放效果.A.Anagnostopoulos 等［5］研究了上下文廣告投放過程中的實時性和效率問題.但是這些工作都沒有涉及查詢的廣告點擊意圖預(yù)測.

在搜索廣告方面，K.Debmbsczynski 等［6］利用引發(fā)投放某個廣告的所有查詢的內(nèi)容來構(gòu)建廣告的標題和主題，并根據(jù)搜索結(jié)果頁面的特征(廣告的排名和搜索結(jié)果頁的編號)以及廣告URL，建立模型，預(yù)測新廣告的點擊率.M.Regelsonl等［7］發(fā)現(xiàn)不同的詞項(term)在引發(fā)廣告點擊的可能性上具有特定的差別.例如“數(shù)碼相機”和“人腦結(jié)構(gòu)”的廣告意圖是不同的，前者引發(fā)廣告點擊的可能性高于后者.因此，在論文中提出通過詞項的點擊率來反映這種固有的差別.A.Ashkan等［7］意識到更好地理解用戶查詢的意圖有助于提供個性化的搜索結(jié)果并且提高用戶滿意度，他們利用歷史點擊信息、查詢自身的特征以及搜索結(jié)果頁的內(nèi)容分析預(yù)測用戶查詢的商業(yè)意圖，研究表明將這3 組特征結(jié)合起來可以有效檢測出用戶的查詢意圖.在國內(nèi)，陳磊等［9］統(tǒng)計了各大商用搜索引擎搜索廣告方面的統(tǒng)計數(shù)據(jù)，研究了大量真實用戶和搜索廣告的實際交互行為.王家卓等［10］研究了在搜索結(jié)果頁面放置廣告對用戶體驗的影響，廣告鏈接的實際收效，以及不同關(guān)鍵詞或位置的廣告對用戶的吸引力等問題.

實時性也是廣告點擊意圖預(yù)測中一個必須考慮的因素.為了達到提高廣告點擊率的目的，必須在用戶提交查詢時對查詢意圖做出預(yù)測，這也是當(dāng)前廣告投放遇到的挑戰(zhàn).如上所述，基于查詢詞項的廣告點擊預(yù)測是目前最主要的預(yù)測方法.

本文采用國內(nèi)著名商用搜索引擎1 個月(2009年11月)的用戶查詢點擊日志進行分析，包括超過200 000 000 條用戶查詢及相應(yīng)的點擊信息.在處理搜索日志的時候，只考慮發(fā)生了點擊(包括點擊廣告或點擊返回的網(wǎng)頁結(jié)果)的查詢，而不考慮無點擊的查詢.

2 基于查詢詞內(nèi)容匹配的點擊預(yù)測模型

2.1 基本思想

搜索引擎根據(jù)用戶查詢詞與廣告的關(guān)鍵詞匹配的程度及相應(yīng)競價來決定以什么順序展示哪些廣告.因此對于如何預(yù)測哪些關(guān)鍵詞引發(fā)廣告點擊的可能性比較大，一個直觀的思路是:從搜索日志中挑出所有引發(fā)了廣告點擊的用戶查詢，統(tǒng)計每個詞項在這些查詢中的頻度，按照頻度的降序?qū)υ~項進行排序，詞項的位置代表了它引發(fā)廣告點擊的可能性.

然而，這種方法忽略了一個很重要的問題:某些詞項不僅在引發(fā)了廣告點擊的查詢中出現(xiàn)頻度很高，在沒有引發(fā)廣告點擊的查詢中也會大量出現(xiàn).可見一個詞項引發(fā)廣告點擊的可能性是個相對量.因此本文將查詢分為兩類:引發(fā)過廣告點擊的和從未發(fā)生過廣告點擊的.對所有詞項，根據(jù)它們在兩類查詢中的頻度進行排名，以及根據(jù)在兩個排名位置的比較，來判斷詞項的廣告點擊意圖.

更進一步地，本文的目的是預(yù)測用戶提交給搜索引擎的完整查詢的廣告意圖.因而需要根據(jù)每個term 的廣告意圖，通過一定的映射關(guān)系，計算出完整查詢的廣告意圖.

2.2 模型描述

設(shè)S 為所有查詢構(gòu)成的集合，對其中的查詢進行中文分詞，得到所有出現(xiàn)在S 中的詞項的集合T.將全體查詢分為兩個部分S1和S2，其中:S1為引發(fā)了廣告點擊的查詢集合，S2為未引發(fā)廣告點擊的查詢集合.

對Si，統(tǒng)計T 中的每個詞項在其中出現(xiàn)的頻度，并且按照頻度的高低排名，形成詞表Li.| L1|=| L2|=| T|.對于T 中的每個詞項t，獲取它在L1和L2中的排名rank(t，L1)和rank(t，L2)，計算兩個排名的比值v(t)=rank(t，L1)/rank(t，L2)，并且根據(jù)這個比值的大小，對T 中的所有詞項按降序排列，得到詞表L3.其格式如表1 所示.

表1 查詢詞信息包含內(nèi)容格式

在基于查詢詞內(nèi)容匹配的預(yù)測算法中，本文只需要前兩項的信息，即詞項和排名比值.

給定任意用戶查詢Q，進行中文分詞，得到一個詞項集合s，并定義一個映射g 即

這樣，就獲得由若干詞項組成的完整查詢Q的廣告點擊傾向性的量化度量.如果g(Q)大于某閾值，則判定Q 具有引發(fā)廣告點擊的傾向，反之則沒有.在實驗分析中可以看到，映射g 對預(yù)測算法的性能有一定影響.

2.3 實驗結(jié)果分析

令S 為2009年11月所有查詢構(gòu)成的集合，T為在S 中出現(xiàn)過的所有詞項構(gòu)成的集合，為了去除噪聲以及過于稀疏數(shù)據(jù)的影響，除去那些稀有的詞項或者發(fā)生廣告點擊次數(shù)過少的詞項(實驗中設(shè)為點擊次數(shù)＜10).以后討論中所用到的L3均如此.

本文對真實搜索引擎任意一天(為保證開放測試，選取非2009年11月的日期，例如2009年12月15日)的查詢進行驗證，預(yù)測這些查詢是否可能引發(fā)廣告點擊，并根據(jù)實際發(fā)生的廣告點擊情況進行預(yù)測的精度與召回率等性能評價.測試集含有約7 000 000 條不同的查詢，忽略當(dāng)天點擊次數(shù)＜10 的查詢，一共包括約35 000 條引發(fā)了廣告點擊的查詢.

為了保證判斷的準確性，要求t1，t2，…，tn中必須有2/3 的詞項出現(xiàn)在L3中，即某些包含過多稀有查詢詞項的查詢會直接被忽略.由于廣告商購買的都是一些比較常見的詞項，因此這樣做并不會影響對于用戶查詢意圖的判斷.在模型描述中已經(jīng)提到，g 為用來將詞項的廣告點擊意圖映射到完整查詢的廣告意圖的函數(shù)，不同的g 函數(shù)會影響預(yù)測算法的效果.圖1 給出使用不同映射函數(shù)得到的預(yù)測效果對比，表2 給出使用不同映射方法得到的最優(yōu)預(yù)測精度.其中映射g 分別為

如果不加預(yù)測而對于每個用戶提交的查詢都投放廣告，那么精度=1.000 0，召回率=0.005 0，f1-度量值=0.010 0，結(jié)果劣于采用預(yù)測算法的情況.基于查詢內(nèi)容匹配的模型對于非稀有查詢的意圖預(yù)測還是比較有效的.采用映射函數(shù)g(avg)，能夠使得廣告投放的精度從3.0% 提高到36.8%，f1-度量值從0.060 提升到0.408.本文在更多日期上的預(yù)測實驗表明各映射函數(shù)對應(yīng)的閾值基本穩(wěn)定.其中g(shù)(avg)函數(shù)一般取閾值為3.

圖1 基于詞表內(nèi)容匹配的廣告點擊預(yù)測效果

表2 基于詞表內(nèi)容匹配的廣告點擊最優(yōu)預(yù)測結(jié)果對比

3 基于樸素貝葉斯分類的預(yù)測模型

3.1 模型設(shè)計

對用戶所提交查詢的意圖進行預(yù)測實際上也可以看做一個分類問題.由此本文提出基于詞項歷史點擊信息對用戶查詢意圖進行分類的樸素貝葉斯預(yù)測模型.所有查詢被分為兩類:不含有廣告點擊意圖和含有廣告點擊意圖，分別表示為C1和C2.分別計算每類查詢出現(xiàn)的先驗概率P(Ci)，通過分別統(tǒng)計在所有查詢中具有和不具有廣告點擊意圖的查詢的比例來估計;每個詞項的條件概率P(t| Ci):可以通過統(tǒng)計t 出現(xiàn)在C1和C2類查詢中的頻度估計.將查詢描述為其對應(yīng)的詞項的集合.假設(shè)各詞項獨立，計算P(C1| q)和P(C2| q)，并考慮到P(q)是一個常數(shù)，因此有

如果p1＞p2，則q 屬于C1，不含有廣告點擊意圖，這時應(yīng)減少投放廣告的數(shù)量甚至不投放廣告;如果p1＜p2，則q 屬于C2，q 更可能含有廣告點擊意圖，應(yīng)投放相關(guān)的廣告.

3.2 實驗結(jié)果分析

采用與上述同樣的數(shù)據(jù)集，對樸素貝葉斯預(yù)測模型效果進行驗證，如表3 所示.

表3 基于樸素貝葉斯的廣告點擊預(yù)測效果

表3 中列出了應(yīng)用11月的數(shù)據(jù)訓(xùn)練而成的貝葉斯分類器對于12月部分查詢數(shù)據(jù)進行測試的結(jié)果.其中“2009年12月數(shù)據(jù)隨機采樣(10%比例)”為從2009年12月的所有查詢中按照10%的概率隨機抽取一部分查詢作為測試集.預(yù)測的綜合效果(f1-measure)雖然比不預(yù)測有很大提高，但是并沒有達到與基于詞表匹配的模型預(yù)測性能.

4 廣告點擊曲線擬合模型

為了驗證使用基于歷史數(shù)據(jù)是否能夠?qū)π碌膹V告點擊意圖進行有效預(yù)測，本文進行了廣告點擊的曲線擬合，即考察詞表與相對排序關(guān)系的穩(wěn)定性，如圖2 所示.

圖2 2009年11月和12月的查詢詞項廣告點擊數(shù)據(jù)擬合曲線

圖2(a)是11月數(shù)據(jù)的擬合結(jié)果.曲線解析表達式為f(x)=axb，a=114.5，b=－0.439 9，擬合誤差SSE=1.4e+004，R2=0.910 6.其中SSE 為誤差平方和，值越小說明擬合的誤差越小;R2為決定系數(shù)，常用來衡量曲線對真實數(shù)據(jù)點的近似程度，R2=1 則為精確匹配實際情況。圖2(b)為12月數(shù)據(jù)的擬合結(jié)果，擬合誤差SSE=2.047e +004，R2=0.902，擬合系數(shù)a=129.7，b=－0.443 2.擬合結(jié)果說明對于不同的兩個月的真實用戶查詢點擊日志，擬合所得到的參數(shù)具有一致性，分布平穩(wěn)，且rank(t，L1)/rank(t，L2)隨排名的降低而迅速減少，因此驗證了所提出方法的可行性.首先，過濾低頻不會對結(jié)果造成很大影響;其次，數(shù)據(jù)穩(wěn)定，所以可以用以前的數(shù)據(jù)預(yù)測進行分析從而預(yù)測未來的點擊情況.

5 結(jié)論

1)提出了基于查詢詞內(nèi)容匹配的點擊和基于樸素貝葉斯分類的兩種預(yù)測模型;

2)通過實驗驗證，表明兩種模型均能改進廣告投放效果，其中第1 種模型效果更佳;

3)通過對不同月份的查詢詞項的分布進行了曲線擬合，驗證了所提出預(yù)測方法的可行性.該方法可適用于用戶查詢廣告點擊意圖的在線預(yù)測.

［1］FAIN D C，PEDERSEN J O.Sponsored search:a brief history［J］.Bulletin of the American Society for Information Science and Technology，2006，32(2):12－13.

［2］RIBEIRO-NETO B，CRISTO M，GOLGHER P B，et al.Impedance coupling in content-targeted advertising［C］//Proceedings of the 28th Annual International ACM SIGIR conference on Research and Development in Information Retrieval.New York，NY:ACM，2005:496－503.

［3］BRODER A，F(xiàn)ONTOURA M，JOSIFOVSKI V，et al.A semantic approach to contextual advertising［C］//Proceedings of the 30th Annual International ACM SIGIR conference on Research and Development in Information Retrieval.New York，NY:ACM，2007:559－566.

［4］CHAKRABARTI D，AGARWAL D，JOSIFOVSKI V.Contextual advertising by combining relevance with click feedback［C］//Proceedings of the 17thInternational Conference on World Wide Web.New York，NY:ACM，2008:417－426.

［5］ANAGNOSTOPOULOS A，BRODER A，GABRILOVICH E，et al.Just-in-time contextual advertising［C］//Proceedings of the 16th ACM conference on Conference on Information and Knowledge Management.New York，NY:ACM，2007，331－340.

［6］DEBMBSCZYNSKI K，KOTLOWSKI W，WEISS D.Predicting ads click-through rate with decision rules［C］//Proceedings of the Workshop on Target and Ranking for Online Advertising.New York，NY:ACM，2008:578－586.

［7］ASHKAN A，CLARKE C L A，AGICHTEIN E，et al.Characterizing query intent from sponsored search clickthrough data［C］//Proceedings of the Workshop on Information Retrieval and Advertising.Singapore:SIGIR－IR，2008:15－22.

［8］REGELSON M，F(xiàn)AIN D C.Predicting click-through rate using keyword clusters［C］//Proceedings of Second Workshop on Sponsored Search Auctions.New York，NY:ACM，2006:1－7.

［9］陳磊，劉奕群，茹立云，等.基于用戶日志挖掘的搜索引擎廣告效果分析［J］.中文信息學(xué)報，2008，22(6)，92－97.

［10］王家卓，劉奕群，馬少平，等.基于用戶行為分析的競價廣告效果分析［J］.計算機研究與發(fā)展，2011，48(1):133－138.