一種基于協(xié)同過濾與語義分析的個性化網(wǎng)絡(luò)廣告投放方法研究

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

關(guān)鍵詞： 廣告投放； 協(xié)同過濾； 語義分析； 相似度

中圖分類號： TN911?34 文獻標(biāo)識碼： 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 引 言

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

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

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

1 相關(guān)工作

1.1 協(xié)同過濾方法

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

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

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

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

2.1 數(shù)據(jù)模型

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

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

2.2 算法設(shè)計思想

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

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

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

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

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

2.3 算法流程

本節(jié)在上述數(shù)據(jù)模型和設(shè)計思想的基礎(chǔ)上，對算法的詳細(xì)流程展開描述。

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

（2） 構(gòu)造“用戶?網(wǎng)頁?廣告”的三維模型，當(dāng)用戶瀏覽某目標(biāo)網(wǎng)頁時，計算網(wǎng)頁擴展詞與廣告擴展詞的相似度，并與擴展詞的權(quán)重進行擬合抽取，得到網(wǎng)頁與廣告最終的相似度，將三維模型降維生成二維的“用戶?廣告”模型。

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

3 實 驗

3.1 實驗環(huán)境及數(shù)據(jù)集

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

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

3.2 評測標(biāo)準(zhǔn)

本實驗采用平均準(zhǔn)確率MAP，召回率Recall以及平均匹配時間作為評測標(biāo)準(zhǔn)。MAP通過計算測試集中預(yù)測的用戶點擊情況與實際數(shù)據(jù)的點擊情況進行評測，在實驗中，如果系統(tǒng)匹配的結(jié)果與測試集中的結(jié)果相符，則認(rèn)為投放結(jié)果準(zhǔn)確。因此在測試機中，MAP為被準(zhǔn)確投放廣告的頁面數(shù)量與測試集中的廣告頁面總數(shù)的比值。

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

平均匹配時間反映投放廣告時對系統(tǒng)反應(yīng)時間的影響，因而能夠反映出算法的效率。不考慮預(yù)處理的時間，如網(wǎng)頁和廣告數(shù)據(jù)的抓取，考慮分詞，詞匯擴展以及擴展詞的權(quán)重計算等。

3.3 結(jié)果分析

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

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

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

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

4 結(jié) 語

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

參考文獻

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

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

[3] 霍艷.網(wǎng)絡(luò)廣告投放算法的研究[D].沈陽：東北大學(xué)，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].成都：電子科技大學(xué)，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] 史玉珍，鄭浩.基于協(xié)同過濾技術(shù)的個性化推薦系統(tǒng)研究[J].電子設(shè)計工程，2012，20（11）：41?44.

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

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

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

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