移動互聯(lián)網(wǎng)廣告推薦算法研究*

張銘芮，劉建毅

（1.北京郵電大學(xué)世紀(jì)學(xué)院 北京 102613；2.北京郵電大學(xué)計算機學(xué)院 北京 100876）

1 引言

近年來移動終端的用戶數(shù)量增長迅猛，手機逐漸成為繼電視、廣播、報刊、互聯(lián)網(wǎng)之后全新的媒體形式，是極具發(fā)展?jié)摿Φ膹V告新媒體。傳統(tǒng)的短信和WAP廣告由于投放行為與受眾的興趣不相符，雖然數(shù)量眾多但有效性難以提高。傳統(tǒng)廣告的強勢使得移動用戶在瀏覽網(wǎng)絡(luò)信息時，往往被動地接受一些并不感興趣的廣告內(nèi)容，這些非相關(guān)廣告會干擾用戶正常的訪問和瀏覽，甚至?xí)孤队脩舻膫€人隱私，因此用戶對這種“地毯式轟炸”的廣告普遍持反感態(tài)度。面向用戶需求的智能廣告，根據(jù)用戶的個人興趣和行為，挖掘用戶的潛在購買需求，按需投放廣告，其目標(biāo)客戶群價值更高、消費者接觸面更廣、價格更低、品牌影響力更高，代表著移動廣告業(yè)智能化的發(fā)展方向，具有廣闊的應(yīng)用前景。

目前，學(xué)術(shù)界和工業(yè)界尚未見到專有的移動互聯(lián)網(wǎng)廣告推薦理論和技術(shù)，其主要借鑒互聯(lián)網(wǎng)廣告推薦理論技術(shù)，主要有搜索引擎廣告（sponsored search）和上下文相關(guān)廣告（contextual advertising）兩種[1]。

搜索引擎廣告是指顯示在搜索結(jié)果頁面上的網(wǎng)站鏈接廣告。搜索引擎接收到搜索請求后，除了返回匹配網(wǎng)頁外，還返回與查詢關(guān)鍵詞相關(guān)的廣告。目前比較有名的搜索引擎廣告系統(tǒng)包括Google的AdSense Program、百度的競價排名服務(wù)等。搜索引擎廣告的研究主要集中在廣告關(guān)鍵詞優(yōu)化、廣告點擊率預(yù)測、競價排名、查詢詞重寫等方面[2～6]。

上下文相關(guān)廣告是指顯示在新聞網(wǎng)頁上的與當(dāng)前網(wǎng)頁主題接近的廣告。上下文相關(guān)廣告系統(tǒng)的核心假設(shè)是:如果用戶對一個網(wǎng)頁感興趣，那么他很有可能對與網(wǎng)頁內(nèi)容相關(guān)的某個廣告感興趣。網(wǎng)頁與廣告的關(guān)聯(lián)是這種廣告形式的核心技術(shù)，即在網(wǎng)頁上顯示與網(wǎng)頁內(nèi)容相關(guān)的廣告[7]。比較有名的上下文相關(guān)廣告系統(tǒng)有Yahoo的Contextual Match Product、MSN 的 Online Advertising Platform 以 及 天下互聯(lián)的“窄告”。

網(wǎng)頁與廣告的關(guān)聯(lián)技術(shù)可進一步細分為關(guān)鍵詞相關(guān)和內(nèi)容相關(guān)。關(guān)鍵詞相關(guān)廣告通過分析網(wǎng)頁內(nèi)容，利用語法或語義方法抽取網(wǎng)頁的關(guān)鍵詞，通過與廣告商的廣告關(guān)鍵詞進行匹配選取廣告[8～11]；內(nèi)容相關(guān)廣告利用對網(wǎng)頁和廣告內(nèi)容進行相似度計算選取廣告[12～14]。然而，僅僅依靠網(wǎng)頁與廣告在文本內(nèi)容上的關(guān)聯(lián)是不夠的，對于一個“抱怨本田車安全”的網(wǎng)頁，如果按照內(nèi)容相關(guān)性推送關(guān)于“本田車”的廣告就會引起用戶的反感，為此有學(xué)者開始將情緒分析引入內(nèi)容定向廣告[15～17]。

國內(nèi)對網(wǎng)絡(luò)廣告的個性化研究基本停留在定性、表面的分析階段，定量研究并不深入，也并未見到在移動互聯(lián)網(wǎng)上通過智能分析技術(shù)和用戶分析技術(shù)推薦網(wǎng)絡(luò)廣告的研究。

本文研究與設(shè)計了移動互聯(lián)網(wǎng)的上下文廣告推薦系統(tǒng)，當(dāng)手機用戶瀏覽WAP網(wǎng)頁時，系統(tǒng)首先利用WAP網(wǎng)頁分類算法判斷該網(wǎng)頁的類別，然后使用關(guān)鍵詞抽取算法提取網(wǎng)頁中的廣告關(guān)鍵詞，最后根據(jù)網(wǎng)頁類別和關(guān)鍵詞在廣告庫中選擇相匹配的廣告嵌入WAP網(wǎng)頁中，推送給用戶。

2 移動互聯(lián)網(wǎng)廣告推薦系統(tǒng)

移動互聯(lián)網(wǎng)廣告推薦系統(tǒng)的體系架構(gòu)如圖1所示，包括WAP網(wǎng)頁內(nèi)容預(yù)處理子系統(tǒng)、WAP網(wǎng)頁分類子系統(tǒng)、關(guān)鍵詞抽取子系統(tǒng)、廣告投放子系統(tǒng)。

WAP網(wǎng)頁內(nèi)容預(yù)處理子系統(tǒng)，包含網(wǎng)頁解析模塊和分詞模塊。網(wǎng)頁解析模塊實現(xiàn)了正文抽取功能，用于識別網(wǎng)頁中有意義的正文，并把無關(guān)信息剔除，如網(wǎng)頁的導(dǎo)航鏈接、圖片、聲音等多媒體信息，主要采用HTML去標(biāo)簽化技術(shù)，通過匹配網(wǎng)頁腳本標(biāo)簽進行正文抽取，輸出結(jié)果是網(wǎng)頁內(nèi)容正文（帶有標(biāo)題和一些關(guān)鍵標(biāo)簽），將網(wǎng)頁正文交給其他分詞模塊進行處理；分詞模塊采用正向最大匹配算法將正文中的長句分為單個詞語，并通過詞典中的信息給出詞語的詞性。

WAP網(wǎng)頁分類子系統(tǒng)，用于準(zhǔn)確識別網(wǎng)頁的主題，以提高基于內(nèi)容的網(wǎng)絡(luò)廣告推薦系統(tǒng)的性能。按照設(shè)計的分類體系將內(nèi)容分類，包括IT科技、房產(chǎn)、健康時尚、教育、財經(jīng)、汽車交通、氣候、體育、休閑娛樂以及工作，并依據(jù)已建成的內(nèi)容分類體系進行細化摸索，將關(guān)鍵詞提取模塊作為重要輸入，從而選擇合適類別的廣告進行投放。

關(guān)鍵詞抽取子系統(tǒng)，對廣告的推薦有決定性作用，將網(wǎng)頁內(nèi)容預(yù)處理子系統(tǒng)的分詞結(jié)果作為輸入，用于從網(wǎng)頁正文內(nèi)容中抽取多個關(guān)鍵詞，并以此為依據(jù)與廣告庫中的具體內(nèi)容進行匹配。利用網(wǎng)頁中的標(biāo)簽特征以及詞匯之間的語義關(guān)系，將網(wǎng)頁表示為一個詞匯語義網(wǎng)絡(luò)，盡可能保留網(wǎng)頁的結(jié)構(gòu)信息，計算語義網(wǎng)絡(luò)上每個詞語的重要度，根據(jù)重要度選擇詞語作為網(wǎng)頁的關(guān)鍵詞。

廣告投放子系統(tǒng)，利用廣告類別和網(wǎng)頁關(guān)鍵詞，綜合制定廣告投放策略。根據(jù)網(wǎng)頁類別計算網(wǎng)頁關(guān)鍵詞和廣告關(guān)鍵詞的相似度，搜索屬于該類別的廣告庫，然后在廣告庫中搜索與網(wǎng)頁關(guān)鍵詞相似的廣告進行投放。投放過程中結(jié)合了多種投放策略，應(yīng)用靈活，功能完善。

各子系統(tǒng)模塊間的數(shù)據(jù)傳遞關(guān)系如圖2所示，具體介紹如下。

圖1 移動互聯(lián)網(wǎng)廣告推薦系統(tǒng)架構(gòu)

圖2 各子系統(tǒng)模塊間的數(shù)據(jù)傳遞關(guān)系

首先，WAP網(wǎng)頁內(nèi)容預(yù)處理子系統(tǒng)從URL中下載網(wǎng)頁頁面內(nèi)容，網(wǎng)頁解析模塊對內(nèi)容的格式和類型進行解析，輸出帶有標(biāo)記（標(biāo)記顯示出正文標(biāo)題以及各個段落的劃分）的網(wǎng)頁正文并傳遞給分詞模塊，分詞模塊通過詞典中的詞語數(shù)據(jù)完成分詞工作并標(biāo)注詞語的詞性。WAP網(wǎng)頁分類子系統(tǒng)接收分詞后的正文，利用貝葉斯分類算法進行分類，標(biāo)注正文所屬類別；同時，分詞后的正文被當(dāng)作關(guān)鍵詞提取子系統(tǒng)的輸入，正文抽象模塊收到后對正文進行解析操作，記錄正文標(biāo)記中標(biāo)題和段落的劃分情況，同時把正文中的詞語抽象成詞語網(wǎng)絡(luò)，根據(jù)此網(wǎng)絡(luò)用PageRank算法計算每個詞匯的權(quán)重，并進行排名。關(guān)鍵詞輸出模塊根據(jù)詞語在網(wǎng)頁中的標(biāo)簽、頻率和出現(xiàn)的位置對排名進行微調(diào)，使得關(guān)鍵詞排名更合理。最后，根據(jù)網(wǎng)頁所屬類別和關(guān)鍵詞信息在廣告庫中進行匹配，對相應(yīng)的廣告進行投送。網(wǎng)頁分類子系統(tǒng)根據(jù)類別找到廣告庫中相應(yīng)的類別，然后根據(jù)已提取出的關(guān)鍵詞在這個類別中進行語義相近的運算，符合度最高的就是要投送的廣告條目。類判別式為:

3 關(guān)鍵技術(shù)介紹

3.1 WAP網(wǎng)頁分類算法

3.1.1 算法原理

廣告因內(nèi)容不同有不同類別，可以根據(jù)廣告類別推送廣告。通過參考著名的分類目錄并結(jié)合廣告自身特性，在分類體系中建立了10個類別，分別是IT科技、房產(chǎn)、健康時尚、教育、財經(jīng)、汽車交通、氣候、體育、休閑娛樂以及工作。利用WAP網(wǎng)頁分類算法對網(wǎng)頁內(nèi)容類別進行判斷，得到WAP網(wǎng)頁在內(nèi)容上所屬的類別?？紤]到分類性能和效率的折衷，本系統(tǒng)采用了一種改進的樸素貝葉斯算法。

在樸素貝葉斯算法的實現(xiàn)過程中，文本分類預(yù)測主要依據(jù):待測文本中每個詞語出現(xiàn)一次，記錄該詞語在已建立的分類器中對各個類別的貢獻值，當(dāng)所有的詞語都遍歷完成，則計算該文本中所有詞語所屬類別的貢獻值總和，從中選出最大的一個作為預(yù)測類別。這樣看來，詞語在文本中的詞頻和詞語在類別中的貢獻值決定了文本類別信息，但對于類別重疊較多的情況，有可能造成誤分類，這里采用χ2統(tǒng)計值作為詞語的重要特征，把它與類別貢獻值相聯(lián)系，增強對于相近類別的區(qū)分性能。文本分

其中，F(xiàn)為文本特征向量，CHI(w,Cj)為詞w與類別Cj的 χ2統(tǒng)計值，Pr(w|d′)用文本 d′中 w出現(xiàn)的次數(shù)與總詞數(shù)的比值表示，Pr(Cj)可以由類別Cj的文本數(shù)和訓(xùn)練集所有文本數(shù)的比值表示，Pr(w|Cj)可以由類別Cj中w出現(xiàn)的次數(shù)與文本總數(shù)的比值表示。

3.1.2 測試結(jié)果

為了確保分類的正確性，必須建立質(zhì)量優(yōu)良的訓(xùn)練語料庫，并且針對上述10個類別進行足夠的資料采集，才能確保分類引擎的性能。通過服務(wù)器運行爬蟲程序采集了50000篇原始文章，進一步篩選后，每個類別保留了1300篇文章作為有效數(shù)據(jù)，每個類別中500篇文章作為測試數(shù)據(jù)集，800篇文章作為語料庫訓(xùn)練集。測試結(jié)果見表1。

3.2 關(guān)鍵詞抽取算法

3.2.1 算法原理

關(guān)鍵詞抽取是本系統(tǒng)的核心環(huán)節(jié)，廣告的推送主要由關(guān)鍵詞的性質(zhì)和類別決定。由于網(wǎng)頁內(nèi)容多樣化，涉及領(lǐng)域廣泛，需要設(shè)計實現(xiàn)一個適用性強、準(zhǔn)確率高、穩(wěn)定性強的關(guān)鍵詞抽取算法完成這一核心工作。本文采用基于PageRank的關(guān)鍵詞抽取算法，首先將網(wǎng)頁構(gòu)建成一個共現(xiàn)網(wǎng)絡(luò)，將文本D映射為一個詞匯網(wǎng)絡(luò)G={V,E,W}，其中V為頂點集合，E為邊集合，W為邊的權(quán)重。

頂點集:文本主要由名詞和動詞反映語義內(nèi)容，因此經(jīng)過分詞和詞性標(biāo)注等預(yù)處理后只選擇名詞和動詞作為網(wǎng)絡(luò)的頂點。相同詞語只構(gòu)造一個節(jié)點。

邊集:如果兩個詞匯出現(xiàn)在一個窗口單元中，就認為這兩個頂點有關(guān)系，為它們建立一條邊，并統(tǒng)計它們在同一窗口單元中的出現(xiàn)次數(shù)，作為邊的權(quán)重。在共現(xiàn)網(wǎng)絡(luò)上利用PageRank算法計算節(jié)點（即詞匯）的重要程度，選取前N個詞匯作為網(wǎng)頁的關(guān)鍵詞。PageRank算法的具體步驟介紹如下。

表1 分類測試結(jié)果

（1）讀入分詞后的文本正文。

（2）讀入每個獨立詞語作為網(wǎng)絡(luò)節(jié)點（相同的詞語屬于同一個節(jié)點），記錄每個詞語出現(xiàn)的位置，為建立網(wǎng)絡(luò)做準(zhǔn)備。

（3）遍歷整個詞語節(jié)點，如果有兩個詞語出現(xiàn)在共現(xiàn)窗口內(nèi)（窗口值由程序運行時設(shè)定，一般為5～10），就認為這兩個詞語有關(guān)系，在網(wǎng)絡(luò)中的相應(yīng)節(jié)點間建立一條邊，否則沒有連接邊。

（4）統(tǒng)計有邊詞語在窗口內(nèi)的出現(xiàn)次數(shù)，并作為節(jié)點間邊的權(quán)重。

（5）在網(wǎng)絡(luò)中保留名詞、動詞等語義豐富的節(jié)點，使網(wǎng)絡(luò)節(jié)點都是可以承載文本含義的詞語，無向有權(quán)文本網(wǎng)絡(luò)建立完畢。

（6）迭代計算網(wǎng)絡(luò)中各節(jié)點的PageRank值，直至收斂。

（7）各節(jié)點的重要度根據(jù)PageRank值的大小排序，選取前N個作為文本關(guān)鍵詞。

3.2.2 測試結(jié)果

為了驗證程序的穩(wěn)定性和正確性，必須建立一個合適的測試集。關(guān)鍵詞測試集需要以文本的形式存在，且每篇文章都需要正確的人工標(biāo)注的關(guān)鍵詞，用來驗證自動抽取的關(guān)鍵詞的正確性。從上述觀點出發(fā)，最符合條件的測試集是各類學(xué)術(shù)論文，因為學(xué)術(shù)論文都由作者自己標(biāo)注關(guān)鍵詞，但由于專業(yè)性強、涉及領(lǐng)域較深入、含有較多專業(yè)詞語、篇幅過長，和通常所瀏覽的網(wǎng)頁有非常大的偏差，所以不能選取學(xué)術(shù)論文作為測試集驗證關(guān)鍵詞抽取程序。本文選取與網(wǎng)頁形式較為相似的博客作為測試集，因為大多數(shù)博客網(wǎng)站都會要求用戶在寫博客時為文章添加標(biāo)簽——關(guān)鍵詞。為了收集博客文章作為測試集，使用網(wǎng)絡(luò)爬蟲對一些博客網(wǎng)站進行信息采集，確保這些博客文章標(biāo)注的關(guān)鍵詞都是在博主寫文章時人工標(biāo)注的，保證其正確性。

通過服務(wù)器運行爬蟲程序采集到原始文章15000篇，進行進一步篩選。爬蟲抓取保存的是博客原始網(wǎng)頁，所以需要對這些網(wǎng)頁進行解析處理，相當(dāng)于利用網(wǎng)頁解析模塊進行處理，只留下題目和正文內(nèi)容。首先，選取帶有3個以上人工標(biāo)簽的博客為測試集，把人工標(biāo)簽視為已標(biāo)注關(guān)鍵詞；然后，選取的博客以文字描述為主要內(nèi)容，過濾其圖片、視頻、音頻等非文本內(nèi)容；最后，對博客的長度加以限制，因為有些博客較為短小，不能表達主題含義，選取字數(shù)200字以上的博客作為測試集。經(jīng)過處理后的測試集一共有1200篇文章，將每篇已標(biāo)識出的關(guān)鍵詞統(tǒng)一建立一個索引保存到統(tǒng)一的文件中，以便進行對比實驗。

本文中采用精確度P和召回率R作為衡量關(guān)鍵詞抽取子系統(tǒng)的標(biāo)準(zhǔn)。其中，精確度定義為輸出的正確關(guān)鍵詞數(shù)量與輸出的關(guān)鍵詞總數(shù)量之比；召回率定義為輸出的正確關(guān)鍵詞數(shù)量與人工標(biāo)注的關(guān)鍵詞數(shù)量之比。根據(jù)定義，精確度和召回率的最大值都被輸出關(guān)鍵詞和已標(biāo)識人工關(guān)鍵詞數(shù)限制。當(dāng)A＞T時，精確度的范圍是0～1，召回率范圍是0～T/A；否則精確度范圍是0～A/T，召回率范圍是0～1。

共現(xiàn)網(wǎng)絡(luò)的構(gòu)建是整個系統(tǒng)算法的核心，窗口大小是影響共現(xiàn)網(wǎng)絡(luò)構(gòu)建的重要因素，控制著在網(wǎng)絡(luò)節(jié)點間建立邊的規(guī)則。根據(jù)不同的窗口大小，得到關(guān)鍵詞抽取測試結(jié)果，見表2。

表2 關(guān)鍵詞抽取測試結(jié)果

從表2中可以看出，窗口距離由2到10的變化過程中，實驗數(shù)據(jù)有很明顯的上升；但窗口距離從10到20的變化過程中，實驗數(shù)據(jù)變化微小，甚至呈現(xiàn)出微小的下降趨勢。這主要是因為當(dāng)窗口過小時，詞語網(wǎng)絡(luò)對于原文保存的語義不夠，造成了重要節(jié)點在圖中孤立；如果窗口距離過大，將使得許多冗余的無意義邊出現(xiàn)在語義網(wǎng)絡(luò)中，網(wǎng)絡(luò)整體結(jié)構(gòu)將分散在無用連接中。所以需要通過實驗在抽取質(zhì)量和效率之間找一個平衡點，一般情況下選取窗口大小為10。

4 結(jié)束語

本文提出了移動互聯(lián)網(wǎng)廣告推薦系統(tǒng)的體系結(jié)構(gòu)，包括WAP網(wǎng)頁內(nèi)容預(yù)處理子系統(tǒng)、WAP網(wǎng)頁分類子系統(tǒng)、關(guān)鍵詞抽取子系統(tǒng)和廣告投放子系統(tǒng)。其中，WAP網(wǎng)頁分類子系統(tǒng)采用貝葉斯分類器結(jié)合統(tǒng)計特性利用自建語料庫實現(xiàn)對網(wǎng)頁內(nèi)容的高精度分類；關(guān)鍵詞抽取子系統(tǒng)采用基于PageRank算法的數(shù)據(jù)文本網(wǎng)絡(luò)關(guān)鍵節(jié)點挖掘技術(shù)，有效提高文本網(wǎng)絡(luò)隱藏信息挖掘的精確度和效率。

本文實現(xiàn)了移動互聯(lián)網(wǎng)廣告推薦系統(tǒng)所需的基本功能，但仍不是一個完善的系統(tǒng)，需進一步測試并對網(wǎng)絡(luò)廣告的其他技術(shù)進行進一步研究，如行為定向廣告研究，通過挖掘用戶的長期和短期行為，更能掌握和跟蹤用戶的興趣，從而給予更符合用戶需求的廣告內(nèi)容。

1 Broder A,Fontoura M,Josifovski V,et al.A semantic approach to contextual advertising.Proceedings of the 30th International Conference on SIGIR,Amsterdam,2007:559～566

2 Anastasakos T,Hillard D,Kshetramade S,et al.A collaborative filtering approach to ad recommendation using the query-ad click graph.Proceedings of the International Conference on CIKM,2009:1927～1930

3 Attenberg J,Pandey S,Suel T.Modeling and predicting user behavior in sponsored search.Proceedings of the International Conference on KDD,2009:1067～1076

4 Hillard D,Schroedl S,Manavoglu E,et al.Improving ad relevance in sponsored search.Proceedings of the International Conference on WSDM,2010:361～370

5 Zhang W,He X,Rey B,et al.Query rewriting using active learning for sponsored search.Proceedings of the International Conference on SIGIR,2007:853～854

6 Zhang W,Jones R.Comparing click logs and editorial labels for training query rewriting.Proceedings of Workshop on Query Log Analysis:Social and Technological Challenges,2007

7 施水才，程濤，王霞等.基于網(wǎng)頁內(nèi)容的廣告推介研究.中文信息學(xué)報,2007,21(4):42～47

8 Wen-Tau Yih,Joshua Goodman,Vitor R Carvalho.Finding advertising keywords on Web pages.Proceedings of the 15th International Conference on World Wide Web,2006:213～222

9 Jianyi Liu,Cong Wang,Wenbin Yao.Keyword extraction for contextual advertising.China Communications,2010(10)

10 Mehta A,Saberi A,Vazirani U,et al.Adwords and generalized online matching.Journals on ACM,2007,54(5):22

11 Shen D,Sun J T,Yang Q,et al.Building bridges for Web query classification.Proceedings of the International Conference on SIGIR'06,2006:131～138

12 Murdock V,Ciaramita M,PlachourasV.A noisy-channel approach to contextual advertising. Proceedings of the International Conference on ADKDD'07,2007:21～27

13 Berthier Ribeiro-Neto,Macro Cristo.Impedance coupling in content-targeted advertising. Proceedings of the 28th International Conference on SIGIR,2005:496～503

14 Anisio Lacerda, Marco Cristo. Learning to advertise.Proceedings of the 29th Annual International ACMSIGIR Conference on Research and Development in Information Retrieval,2006:549～556

15 Xin Jin,YingLi,TeresaMah,etal.Sensitive Webpage classification for content advertising.Proceedings of the 1st International Workshop on Data Mining and Audience Intelligence for Advertising,San Jose,California,2007:28～33

16 Teng-Kai Fan,Chia-Hui Chang.Sentiment-oriented contextual advertising.Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval,Toulouse,France,2009:202～215

17 KangmiaoLiu,QuangQiu,Can Wang,etal.Incorporate sentiment analysis in contextual advertising.Proceedings of the First Workshop on Targeting and Ranking for Online Advertising,Beijing,China,2008