移動互聯網廣告推薦算法研究*

張銘芮，劉建毅

（1.北京郵電大學世紀學院 北京 102613；2.北京郵電大學計算機學院 北京 100876）

1 引言

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

目前，學術界和工業界尚未見到專有的移動互聯網廣告推薦理論和技術，其主要借鑒互聯網廣告推薦理論技術，主要有搜索引擎廣告（sponsored search）和上下文相關廣告（contextual advertising）兩種[1]。

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

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

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

國內對網絡廣告的個性化研究基本停留在定性、表面的分析階段，定量研究并不深入，也并未見到在移動互聯網上通過智能分析技術和用戶分析技術推薦網絡廣告的研究。

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

2 移動互聯網廣告推薦系統

移動互聯網廣告推薦系統的體系架構如圖1所示，包括WAP網頁內容預處理子系統、WAP網頁分類子系統、關鍵詞抽取子系統、廣告投放子系統。

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

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

關鍵詞抽取子系統，對廣告的推薦有決定性作用，將網頁內容預處理子系統的分詞結果作為輸入，用于從網頁正文內容中抽取多個關鍵詞，并以此為依據與廣告庫中的具體內容進行匹配。利用網頁中的標簽特征以及詞匯之間的語義關系，將網頁表示為一個詞匯語義網絡，盡可能保留網頁的結構信息，計算語義網絡上每個詞語的重要度，根據重要度選擇詞語作為網頁的關鍵詞。

廣告投放子系統，利用廣告類別和網頁關鍵詞，綜合制定廣告投放策略。根據網頁類別計算網頁關鍵詞和廣告關鍵詞的相似度，搜索屬于該類別的廣告庫，然后在廣告庫中搜索與網頁關鍵詞相似的廣告進行投放。投放過程中結合了多種投放策略，應用靈活，功能完善。

各子系統模塊間的數據傳遞關系如圖2所示，具體介紹如下。

圖1 移動互聯網廣告推薦系統架構

圖2 各子系統模塊間的數據傳遞關系

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

3 關鍵技術介紹

3.1 WAP網頁分類算法

3.1.1 算法原理

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

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

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

3.1.2 測試結果

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

3.2 關鍵詞抽取算法

3.2.1 算法原理

關鍵詞抽取是本系統的核心環節，廣告的推送主要由關鍵詞的性質和類別決定。由于網頁內容多樣化，涉及領域廣泛，需要設計實現一個適用性強、準確率高、穩定性強的關鍵詞抽取算法完成這一核心工作。本文采用基于PageRank的關鍵詞抽取算法，首先將網頁構建成一個共現網絡，將文本D映射為一個詞匯網絡G={V,E,W}，其中V為頂點集合，E為邊集合，W為邊的權重。

頂點集:文本主要由名詞和動詞反映語義內容，因此經過分詞和詞性標注等預處理后只選擇名詞和動詞作為網絡的頂點。相同詞語只構造一個節點。

邊集:如果兩個詞匯出現在一個窗口單元中，就認為這兩個頂點有關系，為它們建立一條邊，并統計它們在同一窗口單元中的出現次數，作為邊的權重。在共現網絡上利用PageRank算法計算節點（即詞匯）的重要程度，選取前N個詞匯作為網頁的關鍵詞。PageRank算法的具體步驟介紹如下。

表1 分類測試結果

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

（2）讀入每個獨立詞語作為網絡節點（相同的詞語屬于同一個節點），記錄每個詞語出現的位置，為建立網絡做準備。

（3）遍歷整個詞語節點，如果有兩個詞語出現在共現窗口內（窗口值由程序運行時設定，一般為5～10），就認為這兩個詞語有關系，在網絡中的相應節點間建立一條邊，否則沒有連接邊。

（4）統計有邊詞語在窗口內的出現次數，并作為節點間邊的權重。

（5）在網絡中保留名詞、動詞等語義豐富的節點，使網絡節點都是可以承載文本含義的詞語，無向有權文本網絡建立完畢。

（6）迭代計算網絡中各節點的PageRank值，直至收斂。

（7）各節點的重要度根據PageRank值的大小排序，選取前N個作為文本關鍵詞。

3.2.2 測試結果

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

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

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

共現網絡的構建是整個系統算法的核心，窗口大小是影響共現網絡構建的重要因素，控制著在網絡節點間建立邊的規則。根據不同的窗口大小，得到關鍵詞抽取測試結果，見表2。

表2 關鍵詞抽取測試結果

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

4 結束語

本文提出了移動互聯網廣告推薦系統的體系結構，包括WAP網頁內容預處理子系統、WAP網頁分類子系統、關鍵詞抽取子系統和廣告投放子系統。其中，WAP網頁分類子系統采用貝葉斯分類器結合統計特性利用自建語料庫實現對網頁內容的高精度分類；關鍵詞抽取子系統采用基于PageRank算法的數據文本網絡關鍵節點挖掘技術，有效提高文本網絡隱藏信息挖掘的精確度和效率。

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

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 施水才，程濤，王霞等.基于網頁內容的廣告推介研究.中文信息學報,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