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

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

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

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ò)廣告是增長(zhǎng)最快的媒體，其為互聯(lián)網(wǎng)市場(chǎng)和用戶創(chuàng)造了大量的直接和間接價(jià)值[1]。當(dāng)前，個(gè)性化廣告投放平臺(tái)需要解決兩個(gè)關(guān)鍵問(wèn)題：一是如何嵌入與網(wǎng)頁(yè)內(nèi)容盡可能相關(guān)的廣告，即投放的準(zhǔn)確性問(wèn)題；二是如何盡可能高效率地嵌入廣告，即投放的高效性問(wèn)題。廣告投放的實(shí)時(shí)性決定了廣告投放過(guò)程必須快速有效。然而，廣告投放的準(zhǔn)確性與高效性之間經(jīng)常是相互矛盾的。已有的廣告投放方法均難以在這兩者之間取得較好的平衡[1]。

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

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

1 相關(guān)工作

1.1 協(xié)同過(guò)濾方法

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

1.2 基于文本語(yǔ)義的分析方法

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

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

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

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

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

2.2 算法設(shè)計(jì)思想

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

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

得到關(guān)鍵詞以后對(duì)其進(jìn)行同義詞的擴(kuò)展，擴(kuò)展的方法是計(jì)算關(guān)鍵詞與擴(kuò)展詞之間的相似度，如果相似度達(dá)到一定的閾值，說(shuō)明兩詞是同義詞。關(guān)鍵詞語(yǔ)擴(kuò)展詞相似度的計(jì)算采用基于詞語(yǔ)距離的同義詞識(shí)別算法。基于詞林的詞語(yǔ)相似度計(jì)算的核心在于對(duì)詞語(yǔ)中的義項(xiàng)進(jìn)行統(tǒng)一編號(hào)，然后根據(jù)兩個(gè)義項(xiàng)語(yǔ)義的距離來(lái)計(jì)算義項(xiàng)的相似度，進(jìn)而得到詞匯的相似度。

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

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

2.3 算法流程

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

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

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

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

3 實(shí) 驗(yàn)

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

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

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

3.2 評(píng)測(cè)標(biāo)準(zhǔn)

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

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

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

3.3 結(jié)果分析

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 霍艷.網(wǎng)絡(luò)廣告投放算法的研究[D].沈陽(yáng)：東北大學(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é)同過(guò)濾技術(shù)的個(gè)性化推薦系統(tǒng)研究[J].電子設(shè)計(jì)工程，2012，20（11）：41?44.

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

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

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

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