一種基于協同過濾與語義分析的個性化網絡廣告投放方法研究

摘 要： 針對個性化網絡廣告中網頁與廣告匹配的問題，通過將基于關鍵詞擴展的語義分析技術引入到協同過濾系統中，提出一種基于協同過濾與語義分析結合的個性化網絡廣告投放方法（CFKE）。該方法首先提取網頁與廣告文本的關鍵詞，并對關鍵詞擴展同義詞；然后，計算網頁擴展詞與廣告擴展詞的相似度，并與擴展詞的權重進行擬合抽取，得到網頁與廣告最終的相似度，將三維模型降維成二維模型；最后，再利用協同過濾方法進行匹配。仿真表明，與其他算法相比，該算法不僅具有較高的準確度，同時具有較好的系統響應能力。

關鍵詞： 廣告投放； 協同過濾； 語義分析； 相似度

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2016）19?0107?04

Abstract： Aiming at the matching problems of webpage and advertisement in personalized network advertising， a personalized network network advertising method based on the combination of collaborative filtering and semantic analysis is proposed by introducing the semantic analysis technology based on keyword expansion into the collaborative filtering system. With the method， the keywords of webpage and advertising text are extracted for synonyms extension. And the similarity of webpage extension words and advertising extension words is calculated， and fitted and extracted with the weights of expansion words to obtain the final similarity of webpage and advertisement， and reduce the 3D model to 2D model. Then the collaborative filtering method is used to match with the similarity. The simulation results show that， in comparison with the other algorithms， this algorithm has higher accuracy， and better system response ability.

Keywords： advertising putting； collaborative filtering； semantic analysis； similarity

0 引 言

隨著互聯網的快速普及，網絡廣告的重要性日益顯著。目前，網絡廣告是增長最快的媒體，其為互聯網市場和用戶創造了大量的直接和間接價值[1]。當前，個性化廣告投放平臺需要解決兩個關鍵問題：一是如何嵌入與網頁內容盡可能相關的廣告，即投放的準確性問題；二是如何盡可能高效率地嵌入廣告，即投放的高效性問題。廣告投放的實時性決定了廣告投放過程必須快速有效。然而，廣告投放的準確性與高效性之間經常是相互矛盾的。已有的廣告投放方法均難以在這兩者之間取得較好的平衡[1]。

協同過濾技術主要依靠用戶歷史點擊和用戶偏好等行為數據上，算法較為簡單，但是需要足夠的用戶個性化數據并能夠合理識別用戶，一旦數據不足，會極大影響算法的準確率[2]。基于上下文語義的方法，其主要依靠有效的內部語義知識庫組織模型和準確高效的網頁特征化方法，適用于用戶信息匱乏或者有隱私保護的場景下，但是目前，準確率較高的算法往往較復雜，以至于效率較低；例如，關鍵字檢索的匹配方法[3?4]能很好地保證廣告投放的高效性，但難以保證其準確性；基于知庫識的語義匹配方法[5?6]則相反，其準確性通常以犧牲效率為代價。

因此，在投放的準確性和高效性之間取得較好的平衡，設計一種既準且快的廣告投放方法具有重要的科學意義及應用前景。本文結合基于協同過濾和基于語義分析的方法，在基于協同過濾方法的基礎上，引入關鍵詞擴展及其相關度的計算對系統進行補足，減弱冷啟動問題并向用戶提供更加精準的投放結果。

1 相關工作

1.1 協同過濾方法

個性化信息推送技術是基于推薦技術發展而出現的一種新型服務技術。協同過濾是推薦系統中相當成功的一項技術，在協同過濾中，用戶獲得的推薦結果是系統從用戶購買或點擊行為等隱式方式中獲取的，不需要用戶尋找適合自己興趣的信息。其核心在于根據相似度獲得來自鄰居的推薦[7]，對于基于用戶的過濾來說，關鍵點在于相似鄰居用戶的選取以及相似度的計算。鄰居用戶之間相似度計算常見為余弦相似度，用戶[u]和用戶[v] 之間的相似性[sim（u，v）]由相似度公式可表示為：

1.2 基于文本語義的分析方法

語義分析是利用文本內部詞匯的內在語義聯系進行計算，主要思想是建立網頁與廣告匹配的相關性模型。在文獻[5，8]中，網頁與廣告之間語義相似度的計算通常需要把文本表示成關鍵詞向量的形式，然后利用語義知識庫，如HowNet和WordNet等分析語義的關聯圖及相關性，以建立網頁與廣告文本的語義向量空間模型。

其中關鍵詞抽取主要使用TF?IDF方法， TF?IDF的主要思想是：如果某個詞或短語在文本中出現的頻率TF高，并且在其他文本中很少出現，則認為此詞或者短語具有很好的類別區分能力，其中TF是詞頻，表示詞條在文本中出現的頻率；IDF是反文檔頻率，表示一個詞匯在文本集合中分布的度量。關鍵詞[ti（lin）]在文檔[Dj]中出現的次數為[TF（j，i），]IDF的計算公式為：

2.1 數據模型

定義1 以[Dj]表示進行廣告投放的網頁文檔集合中的某文檔；[Ki]表示關鍵詞；[n]為關鍵詞的個數；[Wj，i]表示對應關鍵詞在該網頁中的權重；[EKi]表示[Ki]的擴展詞。使用向量模型表示廣告頁面特征向量[Dj=（Wj，1，K1），][（Wj，2，K2），…，（Wj，i，Ki），…，（Wj，n，Kn），]由[n]個文本關鍵詞組成數據集[Keyword=K1，K2，…，Ki，…，Kn；]一個關鍵詞的擴展實例表示為[EK=EK1，EK2，…，EKi，…，EKn，]其中[EKi（lin）]為一個關鍵詞的具體擴展詞。

定義2 將“用戶?網頁?廣告”三維模型記作User?web?Ad模型，它是一個三維的向量空間{user，web，ad}，每個維度分別用各自屬性值組成的向量來表示。其中三者組成的一條記錄稱為偏好記錄。偏好記錄的集合叫做偏好數據集。在三維數據中，User為被推送廣告的用戶集合；web為User所瀏覽過的所有頁面集合；Ad為待推薦給用戶的所有廣告集合。

2.2 算法設計思想

本文考慮在廣告投放中，通常對語義特征化利用知識庫生成語義特征向量，充實廣告的內容特征表示，然而候選廣告的文本篇幅通常較短，即包含的關鍵字較少，單純的特征提取不能很好地反映候選廣告的語義特征。并且，準確度較高的語義特征化方法，如文獻[5，8]等采用語義關聯圖的分析方法較為復雜，以至于效率較低。利用詞匯擴展技術對原有的關鍵詞集進行補充，能夠提高廣告投放的準確性。

詞匯擴展是指通過同義詞典查找關鍵詞的同義詞或近義詞，對原有的關鍵詞集進行補充。詞匯擴展首先要提取網頁和廣告文本中的關鍵詞，關鍵詞提取采用TF?IDF方法，表示文檔[Dj]中第[i]個關鍵詞的權重，[m]表示每個文檔中關鍵詞的個數。

得到關鍵詞以后對其進行同義詞的擴展，擴展的方法是計算關鍵詞與擴展詞之間的相似度，如果相似度達到一定的閾值，說明兩詞是同義詞。關鍵詞語擴展詞相似度的計算采用基于詞語距離的同義詞識別算法。基于詞林的詞語相似度計算的核心在于對詞語中的義項進行統一編號，然后根據兩個義項語義的距離來計算義項的相似度，進而得到詞匯的相似度。

在同義詞詞典中詞語距離是度量兩詞關系的重要指標，相似度的計算先要判斷在同義詞林中作為葉子節點的兩個義項在哪一層的分支，即兩個義項的編號是在哪一層有不同。在分支層乘以相應的系數以后，然后乘以調節參數[cosnπ180，]該調節參數的作用是把相似度限定在取值范圍內。詞語所在樹的密度以及分支的多少會直接影響到義項的相似度，密度較大的義項其相似度的值會比密度小的相似度的值精確[9]。因此，再乘以一個控制參數[n-k+1n，]其中[n]表示兩詞所在同義詞詞典中分支層的分支數，[k]表示兩個分支之間的距離。這樣把原本計算出的只對應在幾點的值細化，精確計算結果。

利用網頁與廣告的語義相似度數值就可以預測瀏覽當前頁面的用戶對該頁面的偏好數據。利用偏好數據就可以構建當前頁面下的“用戶?廣告”二維矩陣模型。這樣，“用戶?網頁?廣告”三維的向量空間模型簡化為二維矩陣。最后，利用協同過濾算法進行分析，協同過濾算法可針對用戶偏好數據進行個性化的信息推送，得到個性化的網頁廣告匹配結果。

2.3 算法流程

本節在上述數據模型和設計思想的基礎上，對算法的詳細流程展開描述。

（1） 利用TF?IDF公式分別統計當前網頁與待投放廣告集合中的關鍵詞，并利用詞典對關鍵詞進行擴展。然后，計算該擴展詞在本文檔中的權值，擴展詞的權值由擴展詞與關鍵詞的相似度以及關鍵詞原始權值決定。

（2） 構造“用戶?網頁?廣告”的三維模型，當用戶瀏覽某目標網頁時，計算網頁擴展詞與廣告擴展詞的相似度，并與擴展詞的權重進行擬合抽取，得到網頁與廣告最終的相似度，將三維模型降維生成二維的“用戶?廣告”模型。

（3） 由協同過濾算法確定目標用戶[u]的鄰居用戶，預測用戶[u]對待投放廣告集合的偏好，將偏好最大的TOP?N個廣告推薦給目標用戶[u，]實現個性化的廣告匹配。

3 實 驗

3.1 實驗環境及數據集

實驗收集某門戶網站某段時間廣告的點擊數據，為了減小稀疏度，從所有用戶數據中選取點擊廣告較多的1 000名用戶，其共在7 486個網頁頁面上具有點擊廣告行為，對應的廣告有3 539條。用戶點擊廣告即代表有興趣，記錄網頁頁面的ID和與之對應被點擊廣告的ID，就可將這1 000個用戶的偏好數據作為數據集。在實驗中，將1 000名用戶分為10組，每組100名，起始先對100名用戶數據進行分析，然后逐次遞增至1 000。由于協同過濾方法依靠的是用戶的歷史數據，所以逐步增加用戶數量便于觀察用戶數量對算法性能的影響情況。

每組實驗將80%的用戶的偏好數據作為訓練集，20%作為測試集。例如，第一組的100名用戶中涉及738個頁面，對應356條廣告。取80名用戶的偏好數據作為訓練集，涉及565個頁面，對應262條廣告；其他20名用戶的偏好數據作為測試集，涉及173個頁面，對應94條廣告。

3.2 評測標準

本實驗采用平均準確率MAP，召回率Recall以及平均匹配時間作為評測標準。MAP通過計算測試集中預測的用戶點擊情況與實際數據的點擊情況進行評測，在實驗中，如果系統匹配的結果與測試集中的結果相符，則認為投放結果準確。因此在測試機中，MAP為被準確投放廣告的頁面數量與測試集中的廣告頁面總數的比值。

召回率也叫查全率，可以表示為正確匹配的對象與樣本集中所有相關對象的比值。在該實驗中，召回率為測試機中被選中的廣告數量與測試集中的廣告頁面總數的比值。

平均匹配時間反映投放廣告時對系統反應時間的影響，因而能夠反映出算法的效率。不考慮預處理的時間，如網頁和廣告數據的抓取，考慮分詞，詞匯擴展以及擴展詞的權重計算等。

3.3 結果分析

實驗對比傳統協同過濾（CF），無位置偏見矩陣分解協同過濾算法（NPBCF）[2]，基于向量空間模型的中文文本相似度方法（CN?SIM）[5]，NPBCF是CF的改進方法，將頁面和廣告的特征融入矩陣分解中，更好地解決了數據稀疏性問題。CN?SIM采用提取文本特征分析語義關聯的方法，對文本進行深度分析。

實驗統計四種方法的MAP與召回率如圖1，圖2所示。通過MAP及召回率可得出算法的準確度情況。由圖1，圖2可得出，采用文本特征分析語義關聯的CN?SIM方法準確度較高。由于協同過濾存在冷啟動的問題，初始用戶較少匹配結果較差，但隨著用戶數量的增加，準確率不斷提高。本文設計的CFKE算法初始準確率與CN?SIM有較大差距，當用戶增加至1 000名時，準確度與CN?SIM算法較接近。實驗結果表明，本文設計的CFKE方法準確度比CF和NPBCF方法高。

實驗統計的平均匹配時間如圖3所示。從圖3中可以看出，由于頁面與廣告規模不斷增大，系統所需的查找時間相應增加，CN?SIM方法消耗的時間成倍增加，即效率急劇下降。但是相比之下，本文設計的CFKE算法匹配時間的增長率不大。

總體來看，采用提取文本特征分析語義關聯的CN?SIM方法雖然準確度比本文設計的CFKE算法要高，但是隨著用戶數量的增加，效率會急劇下降，因而應用于大規模的系統中響應能力較差。傳統的CF算法及其改進的NPBCF算法雖然效率比CFKE算法略高，但是準確率較低。綜合來看，本文設計的CFKE算法在較高準確率的同時，具有較好的響應能力。

4 結 語

本文在協同過濾和語義分析方法相關研究的基礎上，針對傳統推薦方法難以應對數據稀疏的冷啟動問題，以及上下文語義分析運行效率較低的特點，提出一種基于協同過濾與語義分析的結合個性化網絡廣告投放方法。該方法在基于協同過濾方法的基礎上，引入關鍵詞擴展及其相關度的計算，使該算法不僅具有較高的準確度，同時具有較好的系統響應能力，從而提高了投放的質量和用戶的體驗。

參考文獻

[1] 宋樂怡，宮學慶，張蓉，等.在線廣告投放系統及技術的演變[J].華東師范大學學報（自然科學版），2013（3）：106?117.

[2] 霍曉駿.基于協同過濾的廣告推薦研究[D].上海：華東師范大學，2014：70?77.

[3] 霍艷.網絡廣告投放算法的研究[D].沈陽：東北大學，2013：45?60.

[4] FAN T K， CHANG C H. Sentiment?oriented contextual advertising [J]. Knowledge and information systems， 2010， 23 （3）： 321?344.

[5] 陳飛宏.基于向量空間模型的中文文本相似度算法研究[D].成都：電子科技大學，2011：65?78.

[6] HU J， FANG L J， CAO Y， et al. Enhancing text clustering by leveraging Wikipedia semantics [C]// Proceedings of 35th Annual ACM SIGIR Conference. New York： ACM Press， 2008： 179?186.

[7] 史玉珍，鄭浩.基于協同過濾技術的個性化推薦系統研究[J].電子設計工程，2012，20（11）：41?44.

[8] 唐果.基于語義領域向量空間模型的文本相似度計算[D].昆明：云南大學，2013：55?62.

[9] 田久樂，趙蔚.基于同義詞詞林的詞語相似度計算方法[J].吉林大學學報（信息科學版），2010，28（6）：602?608.

[10] 王立才，孟祥武，張玉潔，等.上下文感知推薦系統[J].軟件學報，2012，23（1）：1?20.

[11] 段利國，陳俊杰.限定語義距離的關鍵詞同義擴展及精簡[J].計算機工程與應用，2011，47（23）：13?16.