一種無(wú)位置偏見(jiàn)的廣告協(xié)同推薦算法

霍曉駿,賀 樑,楊 燕

(華東師范大學(xué)信息科學(xué)與技術(shù)學(xué)院,上海 200241)

1 概述

進(jìn)入21 世紀(jì),計(jì)算機(jī)的發(fā)展引發(fā)了電子商務(wù)的興起。企業(yè)家通過(guò)展示在搜索引擎頁(yè)面?zhèn)冗厵诘膹V告來(lái)為自己的商品做宣傳,這種方式為廣告發(fā)布者帶來(lái)數(shù)以億計(jì)的收益[1-2]。Google 和Yahoo 都憑借廣告展示系統(tǒng)獲得了巨大的利潤(rùn),這樣的利潤(rùn)僅來(lái)自于用戶對(duì)廣告的點(diǎn)擊。一個(gè)好的廣告推薦系統(tǒng),能為商家?guī)?lái)意想不到的收獲。

廣告推薦系統(tǒng)會(huì)在網(wǎng)頁(yè)的側(cè)邊欄展示多個(gè)廣告,吸引用戶點(diǎn)擊。一個(gè)廣告有時(shí)會(huì)多次展示在同個(gè)網(wǎng)頁(yè)上,有時(shí)會(huì)展示在不同頁(yè)面的不同位置,由此可以計(jì)算出一個(gè)廣告在一個(gè)頁(yè)面上的點(diǎn)擊率(Clickthrough Rate,CTR)。如何預(yù)測(cè)CTR 以及利用CTR來(lái)正確推薦廣告是目前研究的熱點(diǎn)。文獻(xiàn)[3]按照基于用戶協(xié)同過(guò)濾的思想,根據(jù)CTR 的特點(diǎn),通過(guò)找到與待推薦頁(yè)面相似的頁(yè)面,為頁(yè)面進(jìn)行來(lái)自鄰居的推薦。這類方法存在的問(wèn)題是,點(diǎn)擊率的高低并不能完全等同于這個(gè)廣告與展示它的網(wǎng)頁(yè)的相關(guān)性,例如某些廣告由于展示位置靠上,從而點(diǎn)擊率較高,但是相關(guān)性不高。用戶是否點(diǎn)擊廣告,則是由相關(guān)性決定的。因此將點(diǎn)擊率“代替”相關(guān)性直接用于協(xié)同推薦系統(tǒng)是值得斟酌的。

文獻(xiàn)[3]將點(diǎn)擊率等同于相關(guān)性,從而使得廣告排布不合理,導(dǎo)致用戶對(duì)廣告的點(diǎn)擊量下降。為了解決這個(gè)問(wèn)題,文獻(xiàn)[4-5]提出位置模型和級(jí)聯(lián)模型,衡量了點(diǎn)擊率、位置影響、相關(guān)性三者之間的關(guān)系,但是卻各有所短。比如在位置模型中,位置影響通過(guò)實(shí)驗(yàn),如眼球追蹤的實(shí)驗(yàn)和用戶習(xí)慣問(wèn)卷得到,需要耗費(fèi)大量的人力物力,不適用于商業(yè)系統(tǒng),因此難以推廣。

為彌補(bǔ)這些方法的不足,本文將重點(diǎn)對(duì)文獻(xiàn)[3]方法進(jìn)行改進(jìn),考慮位置偏見(jiàn)帶來(lái)的影響,提出NPBCF(No Position Bias Collaborative Filtering)方法,利用頁(yè)面-廣告相關(guān)性來(lái)代替點(diǎn)擊率,通過(guò)構(gòu)造貝葉斯公式,合理地解釋點(diǎn)擊率、相關(guān)性之間的關(guān)系。與傳統(tǒng)方法相比,所有數(shù)據(jù)僅來(lái)自于對(duì)點(diǎn)擊日志的分析,而無(wú)需另行收集。排除歷史數(shù)據(jù)中位置的影響,提取不帶位置偏見(jiàn)的頁(yè)面-廣告相關(guān)性,將這樣的數(shù)據(jù)用于協(xié)同推薦,能夠獲得更準(zhǔn)確的推薦效果。

2 相關(guān)工作

為了推薦廣告,無(wú)論是預(yù)測(cè)點(diǎn)擊率,或者是計(jì)算頁(yè)面與廣告的相關(guān)性,均有2 個(gè)研究方向：(1)基于模型的算法,建立特征模型預(yù)測(cè)點(diǎn)擊率；(2)基于鄰域的協(xié)同過(guò)濾算法,利用頁(yè)面對(duì)廣告的相關(guān)性,找到頁(yè)面或者廣告的相似鄰居,根據(jù)相似鄰居的廣告點(diǎn)擊率將合適的廣告刊登在合適的頁(yè)面上。對(duì)于這種算法,早期的學(xué)者并沒(méi)有考慮位置可能帶來(lái)的偏見(jiàn),下文將介紹對(duì)位置偏見(jiàn)的相關(guān)研究。

2.1 基于模型的機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)可以預(yù)測(cè)點(diǎn)擊率。通過(guò)建立特征模型,從數(shù)據(jù)中提取各種附加特征,如廣告文字內(nèi)容,甚至廣告顏色、大小等[2],然后統(tǒng)計(jì)這些特征下廣告的點(diǎn)擊率,由此,當(dāng)輸入一些條件時(shí),能夠智能地推斷出這些特征條件對(duì)廣告點(diǎn)擊的影響。KDD Cup 2012 中的任務(wù)2[6]是對(duì)廣告點(diǎn)擊次數(shù)的預(yù)測(cè),該比賽提供了豐富的數(shù)據(jù),不僅有最基本的頁(yè)面id、廣告id,同時(shí)還有廣告的相關(guān)屬性,如廣告商、關(guān)鍵詞、點(diǎn)擊用戶等。比賽的優(yōu)勝者[6]將這些內(nèi)容作為機(jī)器學(xué)習(xí)的特征,通過(guò)給定的訓(xùn)練數(shù)據(jù),構(gòu)建點(diǎn)擊率預(yù)測(cè)模型。但是對(duì)于廣告推薦而言,機(jī)器學(xué)習(xí)的可解釋性差,很難向用戶解釋是出于什么原因?yàn)橛脩敉扑]這個(gè)廣告,特別是很多用來(lái)訓(xùn)練的特征有時(shí)往往會(huì)被用戶視為隱私,不愿意被廣告推薦系統(tǒng)提取建模。

2.2 協(xié)同過(guò)濾廣告推薦

傳統(tǒng)的協(xié)同推薦系統(tǒng)[7]只使用了用戶的購(gòu)買記錄,推薦流程盡量少地涉及用戶隱私。文獻(xiàn)[8]對(duì)比了協(xié)同過(guò)濾中的各種模型,瀏覽模型(UBM)、矩陣分解模型(MFCM)、個(gè)性化模型(PCM)并提出獨(dú)創(chuàng)的混合個(gè)性化模型(HPCM),其創(chuàng)新點(diǎn)在于,將原有的用戶-產(chǎn)品二維矩陣,擴(kuò)展為用戶、頁(yè)面、文檔三維空間,通過(guò)張量分解的方式,在這個(gè)立方數(shù)據(jù)上計(jì)算相似度,進(jìn)行鄰居推薦。

文獻(xiàn)[3]將協(xié)同過(guò)濾應(yīng)用到廣告推薦系統(tǒng)中。一般的協(xié)同推薦系統(tǒng)是一個(gè)向用戶推薦產(chǎn)品的系統(tǒng),當(dāng)協(xié)同過(guò)濾被應(yīng)用到廣告推薦系統(tǒng)中時(shí),把頁(yè)面看成“用戶”,把廣告看成“產(chǎn)品”,把某個(gè)頁(yè)面中某個(gè)廣告的點(diǎn)擊率(CTR)看成是“用戶對(duì)產(chǎn)品的評(píng)分”,為待推薦頁(yè)面找到“行為上”與其相似的頁(yè)面,將在這些相似頁(yè)面上刊登過(guò)的并且CTR 較高的廣告刊登在待推薦頁(yè)面中。與基于用戶的協(xié)同推薦相似,用戶可能會(huì)接受來(lái)自于相似用戶的推薦,那么在廣告推薦場(chǎng)景下,在待推薦頁(yè)面上刊登相似頁(yè)面的廣告也可能取得較高的點(diǎn)擊率。

但是這種方法存在一個(gè)問(wèn)題,在基于用戶的協(xié)同過(guò)濾中,用戶對(duì)產(chǎn)品的評(píng)分單純地表示了用戶對(duì)產(chǎn)品的喜好程度,不受其他因素的影響。相似的用戶有著相似的喜好,來(lái)自相似用戶的推薦確實(shí)是能夠被待推薦用戶接受。但在廣告推薦中,CTR 不僅表示頁(yè)面與廣告的相關(guān)程度,同時(shí)也受到廣告刊登位置的影響。某些廣告CTR 高,并不說(shuō)明這個(gè)廣告和刊登它的頁(yè)面很相關(guān),可能僅僅是因?yàn)樗恼故疚恢每可喜盼擞脩舻狞c(diǎn)擊。如果待推薦頁(yè)面刊登了一個(gè)并不相關(guān)的廣告,就無(wú)法吸引用戶的注意,從而成為一次無(wú)用的展示。因此,需要從CTR 中分析出“頁(yè)面-廣告相關(guān)性”,正確地看待位置對(duì)CTR、相關(guān)性產(chǎn)生的影響,這樣才能獲得更準(zhǔn)確的推薦結(jié)果。

2.3 廣告推薦中位置的相關(guān)研究

2.3.1 位置模型

Hotchkiss 等人[9]發(fā)現(xiàn)了位置對(duì)文檔的點(diǎn)擊產(chǎn)生了重大影響。搜索引擎為用戶提交的查詢返回一個(gè)結(jié)果頁(yè)面,其中包含許多查詢結(jié)果鏈接以及廣告鏈接,這些鏈接從上至下地排列。文獻(xiàn)[9]將這些鏈接重新排序后展示,統(tǒng)計(jì)每個(gè)鏈接的點(diǎn)擊率。最終發(fā)現(xiàn),無(wú)論這些鏈接如何排序,位置越靠后的鏈接CTR越小。在廣告推薦系統(tǒng)中,也有類似的現(xiàn)象。例如文獻(xiàn)[4]中,作者統(tǒng)計(jì)了各位置的廣告點(diǎn)擊數(shù)量,發(fā)現(xiàn)最靠上位置的廣告被點(diǎn)擊的最多。于是,文獻(xiàn)[4]通過(guò)貝葉斯公式,將位置看成是一種影響點(diǎn)擊率的條件因素,將點(diǎn)擊率描述為條件概率的形式：

將頁(yè)面-廣告點(diǎn)擊率看成是頁(yè)面-廣告相關(guān)性p(click|ad,seen)和位置因素p(seen|pos)的共同影響,將廣告位置作為一種單獨(dú)作用的因素分離出來(lái),強(qiáng)調(diào)“廣告在某個(gè)位置被看見(jiàn)”這一事件發(fā)生的概率。

2.3.2 級(jí)聯(lián)模型

另一種被稱為級(jí)聯(lián)模型的廣告點(diǎn)擊率預(yù)測(cè)方法受到文獻(xiàn)[9]發(fā)現(xiàn)的另一個(gè)結(jié)果的啟發(fā)。文獻(xiàn)[9]跟蹤用戶在瀏覽網(wǎng)頁(yè)時(shí)的用戶眼球定位,發(fā)現(xiàn)用戶普遍地瀏覽順序是從上到下,于是Kempe 等人[5]將用戶點(diǎn)擊看成伯努利事件,認(rèn)為只有當(dāng)上一個(gè)位置的文檔沒(méi)有被點(diǎn)擊時(shí),下一個(gè)位置的文檔才有可能被點(diǎn)擊。

其中,rai表示廣告ai在頁(yè)面q的位置i下被點(diǎn)擊的概率；qai代表廣告ai被認(rèn)為與頁(yè)面q相關(guān)的概率；Ci代表拒絕概率；qai代表廣告ai不被認(rèn)為與頁(yè)面q相關(guān)的概率；位置因素是通過(guò)拒絕概率Ci的連乘實(shí)現(xiàn)的。

位置模型和級(jí)聯(lián)模型表示了位置因素、點(diǎn)擊率、相關(guān)性三者之間的關(guān)系,它們都表現(xiàn)出了位置對(duì)點(diǎn)擊率的影響。本文工作受到位置模型的啟發(fā),在此基礎(chǔ)上,利用貝葉斯定理推導(dǎo)頁(yè)面和廣告的相關(guān)性,然后使用協(xié)同過(guò)濾的方法,估計(jì)頁(yè)面和廣告的相關(guān)性,形成推薦列表。

除了基于用戶的協(xié)同過(guò)濾可以用于廣告推薦,基于模型的協(xié)同過(guò)濾[10]也可以用于廣告推薦[6]。另外,文獻(xiàn)[11]也是利用位置模型預(yù)測(cè)點(diǎn)擊率的一種變體,文獻(xiàn)[12]詳細(xì)解析了廣告競(jìng)拍的原理,文獻(xiàn)[13]則是針對(duì)廣告拍賣設(shè)計(jì)的競(jìng)拍模型。

3 NPBCF 廣告推薦算法

3.1 級(jí)聯(lián)模型和位置模型的弊端

級(jí)聯(lián)模型和位置模型作為廣告位置研究的一項(xiàng)重大發(fā)現(xiàn),具有重大影響。為了方便地構(gòu)建問(wèn)題模型,研究者們盡量地把問(wèn)題簡(jiǎn)單化,但往往留下了一些弊端。例如在早期的級(jí)聯(lián)模型中,只考慮了一次點(diǎn)擊的情況,而用戶先后點(diǎn)擊多個(gè)廣告的情況則不予考慮,這是不合邏輯的。后來(lái)學(xué)者也做了許多改進(jìn),使級(jí)聯(lián)模型更加符合實(shí)際情況,但是卻導(dǎo)致模型極度復(fù)雜化,使得實(shí)際應(yīng)用難以實(shí)現(xiàn)。

關(guān)于位置模型的問(wèn)題,同樣在于實(shí)際應(yīng)用難實(shí)現(xiàn)。按照模型的意義,對(duì)于p(seen|pos)這項(xiàng),表示“某個(gè)位置的廣告會(huì)被看見(jiàn)的概率”,這個(gè)概率一般是很難準(zhǔn)確測(cè)量得到的。雖然文獻(xiàn)[9]研究了人類的閱讀習(xí)慣,可以統(tǒng)計(jì)各位置被用戶查看的概率,但該文專門(mén)構(gòu)造了一個(gè)實(shí)驗(yàn)環(huán)境,利用精細(xì)的攝像機(jī)來(lái)捕捉人類眼球運(yùn)動(dòng),由此才能得到這些概率。在真實(shí)的應(yīng)用場(chǎng)景下,一般民用攝像頭難以勝任采集數(shù)據(jù)的要求,同時(shí)還將要面對(duì)侵犯隱私的問(wèn)題。

3.2 排除位置偏見(jiàn)的頁(yè)面-廣告相關(guān)性計(jì)算方法

當(dāng)需要計(jì)算某個(gè)廣告ai在某個(gè)頁(yè)面qj的相關(guān)性時(shí),可以用這個(gè)廣告ai和這個(gè)頁(yè)面qj之間的點(diǎn)擊率p(ai,qi)來(lái)衡量相關(guān)性,點(diǎn)擊率越大,說(shuō)明頁(yè)面qj和廣告ai越相關(guān)。此時(shí)：

其中,p(ai|qj)可以認(rèn)為是廣告ai和頁(yè)面qj的相關(guān)性；p(qj)可以認(rèn)為是頁(yè)面的吸引作用。通過(guò)文獻(xiàn)[4-5]可知,位置因素使得一些廣告雖然和刊登它的頁(yè)面有著很高的相關(guān)性,點(diǎn)擊率卻出奇的低。點(diǎn)擊率是相關(guān)性和位置因素共同作用的產(chǎn)物。如果用p(ai|qj)表示頁(yè)面qj和廣告ai的相關(guān)性,那么點(diǎn)擊率應(yīng)該表示為p(ai|qj,pk),其中,pk表示位置。這時(shí)不能使用上式來(lái)計(jì)算相關(guān)性,因?yàn)閜(ai,qj)是無(wú)法被統(tǒng)計(jì)的,它受到了位置的影響,只能統(tǒng)計(jì)例如p(ai,qj,pk)這樣的概率,于是問(wèn)題轉(zhuǎn)化成如何用p(ai,qj,pk)來(lái)表示p(ai|qj)。

在考慮廣告ai、頁(yè)面qj、位置pk三者獨(dú)立的情況下,有：

其中,p(ai|pk)和p(ai)并沒(méi)有特別的意義,只是為了平衡等式而已。如果位置總共有N種,那么根據(jù)貝葉斯定理,有：

其中,p(ai,qj,pk)代表出現(xiàn)在頁(yè)面qj的位置pk的廣告ai的點(diǎn)擊率；p(qj,pk)代表頁(yè)面qj的位置pk的所有廣告點(diǎn)擊率；p(ai,pk)代表出現(xiàn)在位置pk的廣告ai的點(diǎn)擊率；p(pk)表示出現(xiàn)在位置pk的所有廣告的點(diǎn)擊率；p(ai)代表廣告ai的點(diǎn)擊率,這些點(diǎn)擊率數(shù)據(jù)都可以通過(guò)統(tǒng)計(jì)日志信息得到。

為了更加突出位置對(duì)點(diǎn)擊率造成的影響,本文人為地修改頁(yè)面-廣告相關(guān)性。當(dāng)一個(gè)廣告在一個(gè)頁(yè)面的位置2 處被點(diǎn)擊,令這個(gè)頁(yè)面-廣告相關(guān)性為上式計(jì)算結(jié)果的1.2 倍,當(dāng)廣告在頁(yè)面的位置3 處被點(diǎn)擊,令這個(gè)頁(yè)面-廣告相關(guān)性為上式計(jì)算結(jié)果的1.5 倍。一個(gè)廣告如果能吸引用戶在不起眼的地方去點(diǎn)擊它,可想而知這個(gè)廣告與刊登它的頁(yè)面非常相似,以至于克服了不利位置帶來(lái)的不利影響。

3.3 NPBCF 廣告推薦流程

根據(jù)式(5)能夠得到有點(diǎn)擊記錄的廣告和頁(yè)面之間的相關(guān)性,當(dāng)需要對(duì)沒(méi)有記錄的頁(yè)面-廣告估計(jì)相關(guān)性時(shí),可以將問(wèn)題看作協(xié)同過(guò)濾。利用協(xié)同過(guò)濾中基于鄰居的方法來(lái)預(yù)測(cè)相關(guān)性,同第2 節(jié)介紹的利用協(xié)同過(guò)濾預(yù)測(cè)點(diǎn)擊率的方法一樣,在本文方法中,將頁(yè)面看成待推薦的用戶,將廣告看成用來(lái)推薦的產(chǎn)品,將頁(yè)面-廣告相關(guān)性看成是用戶對(duì)產(chǎn)品的評(píng)分。

與傳統(tǒng)的基于用戶的協(xié)同過(guò)濾類似,NPBCF 算法的推薦結(jié)果來(lái)自于用戶的鄰居,即相似的頁(yè)面。待推薦頁(yè)面的某個(gè)鄰居頁(yè)面刊登了一些沒(méi)有在待推薦頁(yè)面上刊登過(guò),并且在鄰居頁(yè)面上被點(diǎn)擊過(guò)的廣告,如果將這些廣告刊登在待推薦頁(yè)面上,很可能就會(huì)被點(diǎn)擊。原因在于這個(gè)頁(yè)面和它的鄰居在點(diǎn)擊行為上是存在相似性的,這種相似性使得它們對(duì)同個(gè)廣告的相關(guān)性也是相近的,如果鄰居頁(yè)面與這個(gè)廣告的相關(guān)程度足以導(dǎo)致被點(diǎn)擊,那么相似頁(yè)面與這個(gè)廣告的相關(guān)程度也可能導(dǎo)致這個(gè)廣告在待推薦頁(yè)面上被點(diǎn)擊。

首先需要衡量用戶之間的關(guān)系,就是要度量不同頁(yè)面之間的相似度。如果2 個(gè)頁(yè)面具有相似的歷史點(diǎn)擊行為,可以認(rèn)為這2 個(gè)頁(yè)面是相似的鄰居。相似的歷史點(diǎn)擊行為,不僅指在這2 個(gè)頁(yè)面上有許多相同的廣告被點(diǎn)擊過(guò),而且2 個(gè)頁(yè)面對(duì)同個(gè)廣告的相關(guān)性數(shù)值上也要接近。具體而言,根據(jù)相關(guān)性構(gòu)建頁(yè)面向量,使用調(diào)整余弦相似度相似計(jì)算每個(gè)頁(yè)面之間的相似度[3]：

其中,px為p(ai|qx)；py為p(ai|qy) -；s(qx,qy)表示刊登在頁(yè)面qx和頁(yè)面qy上的廣告ai集合。

根據(jù)找到相似的頁(yè)面進(jìn)行鄰居推薦,可以利用待推薦頁(yè)面與其鄰居的關(guān)系以及鄰居對(duì)某個(gè)廣告的相關(guān)性推導(dǎo)待推薦頁(yè)面對(duì)這個(gè)廣告的相關(guān)性。如果待推薦頁(yè)面與某個(gè)鄰居特別相似,那么這個(gè)鄰居對(duì)某個(gè)廣告的相關(guān)性將在很大程度上影響待推薦頁(yè)面對(duì)這個(gè)廣告的相關(guān)性,具體來(lái)說(shuō)[3]：

其中,QK(qx)表示頁(yè)面qx的K個(gè)鄰居頁(yè)面集合；qy是其中的元素,表示每個(gè)相似鄰居頁(yè)面,簡(jiǎn)單來(lái)說(shuō)是一個(gè)加權(quán)求和的過(guò)程,待推薦頁(yè)面綜合考慮了它的鄰居們對(duì)某個(gè)廣告的看法后,根據(jù)自己與鄰居的差距預(yù)估了自己對(duì)這個(gè)廣告的看法。

根據(jù)式(7)能夠預(yù)計(jì)出頁(yè)面qx與廣告ai的相關(guān)性,相關(guān)性越大,代表這個(gè)廣告要是刊登在這個(gè)頁(yè)面上,被點(diǎn)擊的可能性就越大,可以選擇最大的M個(gè)廣告用于推薦。

NPBCF 算法流程如圖1 所示。

圖1 NPBCF 算法具體流程

4 實(shí)驗(yàn)結(jié)果與分析

本節(jié)將對(duì)比傳統(tǒng)協(xié)同過(guò)濾(Collaborative Filtering,CF)[3]以及本文所提出的排除位置偏見(jiàn)的協(xié)同過(guò)濾NPBCF 的性能。

4.1 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析

4.1.1 數(shù)據(jù)集

本文使用KDD CUP 2012 任務(wù)2 的訓(xùn)練數(shù)據(jù)集。在這個(gè)任務(wù)中,主辦方收集了騰訊搜搜的廣告點(diǎn)擊數(shù)據(jù)。包含22 023 547 名用戶的641 707 條廣告的共計(jì)149 639 105 會(huì)話記錄,每條會(huì)話記錄包含的特征如表1 所示。

表1 KDD 數(shù)據(jù)集

每個(gè)頁(yè)面上均展示3 個(gè)廣告,從上至下分別表示為位置1、位置2、位置3。使用這個(gè)數(shù)據(jù)集完成對(duì)特定的10 000 個(gè)頁(yè)面的廣告推薦,由于采用最基本的協(xié)同過(guò)濾來(lái)處理推薦任務(wù),有用的數(shù)據(jù)只有Click,Impression,AdID,Position 和QueryID,于是先將相同AdID,Position 和QueryID 的數(shù)據(jù)進(jìn)行整合,得到3 142 966 條記錄,由于數(shù)據(jù)量巨大,需要進(jìn)一步處理。

4.1.2 數(shù)據(jù)預(yù)處理及劃分

由于采用協(xié)同過(guò)濾的方式對(duì)頁(yè)面進(jìn)行推薦,而協(xié)同過(guò)濾對(duì)數(shù)據(jù)稀疏度有較高的要求。通過(guò)整理數(shù)據(jù)發(fā)現(xiàn)共有頁(yè)面1 848 114 個(gè),廣告255 170 條,稀疏度為99.999 4% 。為了進(jìn)一步減小稀疏度,需要減小數(shù)據(jù)集。于是選取了點(diǎn)擊記錄最多的10 000 個(gè)頁(yè)面,只考慮這些頁(yè)面的記錄。此時(shí)數(shù)據(jù)量被壓縮到2 766 393,包含廣告255 170 條,稀疏度99.89%,勉強(qiáng)能夠進(jìn)行協(xié)同過(guò)濾推薦。在每個(gè)頁(yè)面刊登的廣告中,隨機(jī)選擇20% 的廣告以及這些廣告和頁(yè)面的相關(guān)性作為測(cè)試集,其余數(shù)據(jù)作為訓(xùn)練集。

4.1.3 測(cè)評(píng)指標(biāo)

本文采用TopN 的推薦方式,對(duì)推薦結(jié)果計(jì)算不同鄰居數(shù)情況下的準(zhǔn)確率(P)、召回率(R)、以及F 度量值(F)。TopN 推薦是給用戶一個(gè)個(gè)性化的推薦列表,對(duì)應(yīng)本文的應(yīng)用場(chǎng)景,是給頁(yè)面q一個(gè)性化推薦列表。TopN 推薦的預(yù)測(cè)準(zhǔn)確率一般通過(guò)召回率/準(zhǔn)確率度量,召回率又稱查全率,是正確推薦的比率,準(zhǔn)確率是正確推薦結(jié)果占全部推薦的比重,即推薦中存在正確推薦的比例,F 度量值是一種兼顧準(zhǔn)確率和召回率的算法性能總體表現(xiàn)的一種指標(biāo)。令R(q)是根據(jù)頁(yè)面q在訓(xùn)練集上的行為給頁(yè)面q做出的推薦列表,而T(q)是頁(yè)面在測(cè)試集上的行為列表,那么推薦結(jié)果的準(zhǔn)確率、召回率和F 度量值定義為：

4.1.4 數(shù)據(jù)分析

統(tǒng)計(jì)每個(gè)位置的點(diǎn)擊數(shù)量。有時(shí)同樣的廣告會(huì)展示在相同頁(yè)面的不同位置,例如,廣告“電腦維修”有時(shí)展示在頁(yè)面“電腦”的位置1 處,有時(shí)在位置2 處。假設(shè)“電腦維修”在“電腦”的位置1 處展示了10 次,被點(diǎn)擊3 次；位置2 處展示了20 次,未被點(diǎn)擊,那么可以稱“電腦維修-電腦”為一種配對(duì),這種配對(duì)在位置1 處的點(diǎn)擊率是30%,在位置2 處的點(diǎn)擊率是0。

對(duì)于每一個(gè)配對(duì),無(wú)論廣告展示在何處,廣告與頁(yè)面的相關(guān)性是固定不變的,但發(fā)現(xiàn)有51 629 個(gè)廣告在相同頁(yè)面的位置1 處和位置2 處被點(diǎn)擊過(guò),其中,位置1 的點(diǎn)擊率比位置2 的點(diǎn)擊率更高的廣告有30 143 個(gè),有13 564 個(gè)廣告在相同頁(yè)面的位置1 處和位置3 處被點(diǎn)擊過(guò),其中,位置1 的點(diǎn)擊率比位置3 的點(diǎn)擊率更高的廣告有8 433 個(gè),這樣的數(shù)據(jù)對(duì)比說(shuō)明位置偏見(jiàn)確實(shí)存在。

4.2 結(jié)果分析

對(duì)比不同鄰居數(shù)目(分別是5,10,15,20,25,30)情況下,采用傳統(tǒng)協(xié)同過(guò)濾[3]和本文提出的NPBCF 算法,對(duì)10 000 個(gè)頁(yè)面進(jìn)行TOP10 推薦,即每個(gè)頁(yè)面推薦10 個(gè)廣告,觀察2 種算法的準(zhǔn)確率、召回率以及F 度量值,對(duì)比結(jié)果如圖2～圖4 所示。

圖2 準(zhǔn)確率對(duì)比

圖3 召回率對(duì)比

圖4 F 度量值對(duì)比

通過(guò)對(duì)比發(fā)現(xiàn),NPBCF 算法的效果比傳統(tǒng)協(xié)同過(guò)濾算法至少提高了40%,而且隨著鄰居數(shù)目增多,雖然推薦質(zhì)量下滑,但是NPBCF 算法對(duì)于參數(shù)選取錯(cuò)誤有著更強(qiáng)的抵抗性。

對(duì)于一般的協(xié)同過(guò)濾系統(tǒng),鄰居數(shù)目越多,推薦結(jié)果越好,但是在本文實(shí)驗(yàn)中發(fā)現(xiàn),當(dāng)考慮更多的相似頁(yè)面,反而使推薦質(zhì)量嚴(yán)重下滑,為此,對(duì)比了鄰居數(shù)為5 和鄰居數(shù)為10 情況下NPBCF 算法的頁(yè)面相似度和廣告-頁(yè)面相關(guān)性,如表2 所示。

表2 相似度和相關(guān)性的對(duì)比

由此可以看出,在廣告系統(tǒng)中,真正相似的頁(yè)面數(shù)量十分有限。當(dāng)系統(tǒng)考慮了更多不相似的鄰居時(shí),這些鄰居頁(yè)面刊登了點(diǎn)擊率(相關(guān)性)十分高的廣告,以至于這些廣告能夠無(wú)視頁(yè)面不相似,成為協(xié)同推薦的結(jié)果,破壞推薦質(zhì)量。當(dāng)不考慮相似度過(guò)小的鄰居時(shí),即將10 個(gè)鄰居中相似度低于平均相似度的頁(yè)面剔除,發(fā)現(xiàn)NPBCF 的F 度量值上升了25% 。只有當(dāng)系統(tǒng)將真正相似頁(yè)面考慮為鄰居,協(xié)同過(guò)濾才能發(fā)揮其原本的效果,不相似的頁(yè)面對(duì)協(xié)同推薦效果有著嚴(yán)重的影響。

5 結(jié)束語(yǔ)

傳統(tǒng)的觀點(diǎn)誤將頁(yè)面-廣告相關(guān)性看成頁(yè)面-廣告點(diǎn)擊率。點(diǎn)擊率不僅和頁(yè)面-廣告相關(guān)性有關(guān),同時(shí)還受到廣告刊登位置的影響。由于某些廣告展示在靠上的位置,使得這些廣告憑借位置上的優(yōu)勢(shì)獲得了更高的點(diǎn)擊率,如果籠統(tǒng)地將點(diǎn)擊率看成相關(guān)性,將產(chǎn)生錯(cuò)誤的推薦。本文提出一個(gè)相關(guān)性計(jì)算方法,能夠排除點(diǎn)擊數(shù)據(jù)中所帶有的位置偏見(jiàn),正確地計(jì)算頁(yè)面-廣告相關(guān)性,再通過(guò)協(xié)同過(guò)濾技術(shù),為頁(yè)面找到與其相似的其他鄰居頁(yè)面,利用鄰居頁(yè)面找到合適的廣告。最終通過(guò)實(shí)驗(yàn)證明,本文提出的NPBCF 算法能夠比傳統(tǒng)協(xié)同過(guò)濾算法得到更準(zhǔn)確的推薦結(jié)果。

[1]周傲英,周敏奇,宮學(xué)慶.計(jì)算廣告：以數(shù)據(jù)為核心的Web 綜合應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào),2011,34 (10)：1805-1819.

[2]Craswell N,Zoeter O,Taylor M,et al.An Experimental Comparison of Click Position-bias Models[C]//Proceedings of International Conference on Web Search and Web Data Mining.[S.l.]：ACM Press,2008：87-94.

[3]Anastasakos T,Hillard D,Kshetramade S,et al.A Collaborative Filtering Approach to Ad Recommendation Using the Query-ad Click Graph[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management.Hong Kong,China：ACM Press,2009：1927-1930.

[4]Richardson M,Dominowska E,Ragno R.Predicting Clicks：Estimating the Click-through Rate for New Ads[C]// Proceedings of the 16th International Conference on World Wide Web.Alberta,Canada：ACM Press,2007：521-530.

[5]Kempe D,Mahdian M.A Cascade Model for Externalities in Sponsored Search[C]//Proceedings of the 4th International Workshop on Internet and Network Economics.Berlin,Germany：Springer,2008：585-596.

[6]Wu Kuanwei,Ferng Chun-Sung,Ho Chia-Hua,et al.A Two-stage Ensemble of Diverse Models for Ranking Click-through Rates Slides[Z].2012.

[7]Sarwar B,Karypis G,Konstan J,et al.Item-based Collaborative Filtering Recommendation Algorithms[C]//Proceedings of the 10th International Conference on World Wide Web.Hong Kong,China：ACM Press,2001：285-295.

[8]Shen Si,Hu Botao,Chen Weizhu,et al.Personalized Click Model Through Collaborative Filtering [C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining.Seattle,USA：ACM Press,2012：323-332.

[9]Hotchkiss G,Alston S,Edwards G.Eye Tracking Study[EB/OL].(2005-08-11).http：//www.enquiro.com/eye-tracking-pr.asp.

[10]Koren Y,Bell R,Volinsky C.Matrix Factorization Techniques for Recommender Systems[J].Computer,2009,42(8)：30-37.

[11]Chen Ye,Yan T W.Position-normalized Click Prediction in Search Advertising[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA：ACM Press,2012：795-803.

[12]Edelman B,Ostrovsky M,Schwarz M.Internet Advertising and the Generalized Second Price Auction：Selling Billions of Dollars Worth of Keywords[J].American Economic Review,2007,97(1)：242-259.

[13]Pin F,Key P.Stochastic Variability in Sponsored Search Auctions：Observations and Models[C]//Proceedings of the 12th ACM Conference on Electronic Commerce.[S.l.]：ACM Press,2011：61-70.