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

(清華大學(xué) 智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室100084 北京)

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 基于查詢?cè)~內(nèi)容匹配的點(diǎn)擊預(yù)測(cè)模型

2.1 基本思想

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

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

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

2.2 模型描述

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

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

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

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

給定任意用戶查詢Q，進(jìn)行中文分詞，得到一個(gè)詞項(xiàng)集合s，并定義一個(gè)映射g 即

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

2.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

3.1 模型設(shè)計(jì)

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

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

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

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

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

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

4 廣告點(diǎn)擊曲線擬合模型

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

圖2 2009年11月和12月的查詢?cè)~項(xiàng)廣告點(diǎn)擊數(shù)據(jù)擬合曲線

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

5 結(jié)論

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

2)通過實(shí)驗(yàn)驗(yàn)證，表明兩種模型均能改進(jìn)廣告投放效果，其中第1 種模型效果更佳;

3)通過對(duì)不同月份的查詢?cè)~項(xiàng)的分布進(jìn)行了曲線擬合，驗(yàn)證了所提出預(yù)測(cè)方法的可行性.該方法可適用于用戶查詢廣告點(diǎn)擊意圖的在線預(yù)測(cè).

［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é)報(bào)，2008，22(6)，92－97.

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