金紫嫣, ,,1b,,華薇

(1.南昌大學(xué) a.計(jì)算機(jī)科學(xué)與技術(shù)系; b.軟件學(xué)院,南昌330031; 2.共青科技職業(yè)學(xué)院,江西 共青 332020)

0 概述

目前,我國(guó)互聯(lián)網(wǎng)廣告已經(jīng)有千億級(jí)規(guī)模,搜索廣告已成為在線(xiàn)廣告的重要形式[1]。廣告產(chǎn)業(yè)已從逐漸形成有針對(duì)性投放,廣告投放價(jià)值可精準(zhǔn)度量,發(fā)展成為用戶(hù)友好型、廣告客戶(hù)有益型的廣告市場(chǎng)[2]。搜索引擎收益(Revenue Per Search,RPS)是搜索廣告推薦系統(tǒng)成功與否的重要評(píng)價(jià)指標(biāo)之一,它可以通過(guò)搜索廣告的計(jì)價(jià)方式(如CPC、Cost Per Click)與廣告吸引用戶(hù)點(diǎn)擊的能力點(diǎn)擊率(Click-Through Rate,CTR)來(lái)反映,即RPS=CTR×CPC[3]。因此,如何準(zhǔn)確預(yù)測(cè)CTR并合理利用其進(jìn)行廣告推薦具有重要意義。

文獻(xiàn)[4]將基于用戶(hù)的協(xié)同過(guò)濾算法應(yīng)用到廣告推薦領(lǐng)域,將用戶(hù)與廣告推薦系統(tǒng)中的Query頁(yè)面相對(duì)應(yīng)、商品與廣告推薦系統(tǒng)中的廣告相對(duì)應(yīng)、用戶(hù)對(duì)商品的評(píng)分矩陣用CTR相對(duì)應(yīng),即待推薦Query頁(yè)展示與其相似的Query頁(yè)上的廣告,可獲得較高的CTR。文獻(xiàn)[5]提出一種無(wú)位置偏見(jiàn)的協(xié)同過(guò)濾廣告推薦算法,該方法考慮了廣告位置對(duì)CTR的影響,利用頁(yè)面和廣告的相關(guān)性代替用戶(hù)對(duì)商品的評(píng)分。文獻(xiàn)[6]將對(duì)CTR的預(yù)測(cè)問(wèn)題轉(zhuǎn)換成排序問(wèn)題,把CTR作為已知有用信息加入至推薦模型中,使用每個(gè)廣告的預(yù)測(cè)權(quán)重值對(duì)廣告進(jìn)行排序。影響CTR的因素有點(diǎn)擊量和展現(xiàn)量?jī)蓚€(gè)方面:其中影響點(diǎn)擊量的因素有廣告的創(chuàng)意、展現(xiàn)形式、相關(guān)性、展現(xiàn)位置等,影響展現(xiàn)量的因素有廣告關(guān)鍵詞的數(shù)量、質(zhì)量、出價(jià)、推廣地域及時(shí)段等。而且,在相關(guān)性計(jì)算中,廣告關(guān)鍵詞同樣擔(dān)當(dāng)重要角色,其可以有效反映廣告與Query的匹配程度。因此,充分考慮廣告關(guān)鍵詞對(duì)CTR的影響并改進(jìn)傳統(tǒng)相似性度量方法,是提高廣告推薦質(zhì)量的關(guān)鍵之一。

社會(huì)化標(biāo)簽(Social Tag)是Web2.0時(shí)代集體智慧的表征,是建立用戶(hù)與資源之間的橋梁。標(biāo)簽系統(tǒng)不僅在音樂(lè)、電影、圖書(shū)等領(lǐng)域得到了廣泛的應(yīng)用[7],也在廣告推薦中得以應(yīng)用。目前,標(biāo)簽廣告推薦方法主要通過(guò)分析標(biāo)簽(廣告關(guān)鍵詞)、用戶(hù)和資源(廣告)三者之間的關(guān)系獲得其推薦規(guī)則。比如,文獻(xiàn)[8]提出一種改進(jìn)的FolkRank廣告推薦方法,在用戶(hù)、資源、標(biāo)簽三元組中進(jìn)行迭代計(jì)算,求出推薦標(biāo)簽。其中資源對(duì)應(yīng)于廣告推薦系統(tǒng)中的廣告,標(biāo)簽對(duì)應(yīng)于廣告關(guān)鍵字。文獻(xiàn)[9]分析用戶(hù)在不同時(shí)間間隙中行為軌跡的相似性,將時(shí)隙間相似度作為權(quán)重值,將用戶(hù)在不同時(shí)隙瀏覽的廣告進(jìn)行協(xié)同推薦處理。因此,如何合理找到標(biāo)簽推薦技術(shù)與協(xié)同過(guò)濾技術(shù)結(jié)合點(diǎn),充分挖掘廣告關(guān)鍵詞、Query頁(yè)、廣告之間的關(guān)系,是提高廣告推薦質(zhì)量的關(guān)鍵之一。

本文在標(biāo)簽技術(shù)和系統(tǒng)過(guò)濾方法的基礎(chǔ)上,將廣告關(guān)鍵詞作為標(biāo)簽引入Query頁(yè)相似性計(jì)算中,采用Query頁(yè)加權(quán)綜合相似度度量方法,降低相似矩陣稀疏性,提出一種基于廣告關(guān)鍵詞的廣告搜索興趣模型Q-K-A(Query-Keywords-AD)。

1 相關(guān)定義

本節(jié)主要介紹與ADR-CF_T算法相關(guān)的Q-K-A興趣偏好模型、加權(quán)相似度計(jì)算以及廣告預(yù)測(cè)點(diǎn)擊率等相關(guān)概念。

1.1 Q-K-A興趣偏好模型

基于用戶(hù)的協(xié)同過(guò)濾推薦主要是研究用戶(hù)之間的關(guān)系[10],采用最近鄰域技術(shù),通過(guò)分析目標(biāo)用戶(hù)的興趣偏好信息向其推薦符合其興趣偏好的項(xiàng)目。然而,對(duì)于搜索廣告實(shí)際應(yīng)用背景,建立Query頁(yè)之間的興趣偏好模型仍需要考慮諸多因素。點(diǎn)擊率(CTR)可以反映用戶(hù)所輸入的請(qǐng)求(即輸出的Query頁(yè))對(duì)搜索引擎所選擇展現(xiàn)廣告的偏好程度。由于廣告關(guān)鍵詞因素不僅影響廣告的展現(xiàn)量,又在影響點(diǎn)擊量的相關(guān)性計(jì)算中充當(dāng)重要角色。因此,考慮在Query頁(yè)-廣告的二維興趣偏好模型中加入廣告關(guān)鍵詞因素,建立充分描述Query頁(yè)偏好程度的三維興趣偏好模型?；趶V告關(guān)鍵詞的Q-K-A興趣模型需要考慮三方面因素:與Query頁(yè)相匹配的廣告關(guān)鍵詞信息,被Query頁(yè)展現(xiàn)過(guò)的廣告信息以及Query頁(yè)相匹配的廣告關(guān)鍵詞和其選擇展現(xiàn)的廣告之間的關(guān)系。為此,引入如下定義。

假設(shè)IS=(Q,K,A,C)為信息系統(tǒng),其中,Q={q1,q2,…,qm}為Query頁(yè)集合,m為Query頁(yè)總數(shù),K={k1,k2,…,kn}為廣告關(guān)鍵詞集合,n為廣告關(guān)鍵詞總數(shù),A={a1,a2,…,ar}為廣告集合,r為廣告的總數(shù),C={cq,a|q∈Q,a∈A},cq,a表示在Q中的元素q上展現(xiàn)A中的元素a所產(chǎn)生的點(diǎn)擊率。

定義1(廣告標(biāo)簽) 令T={t1,t2,…,ts}為廣告標(biāo)簽集合,其中s為廣告標(biāo)簽的總數(shù)。對(duì)任意ti∈T,kj∈K(1≤i≤s,1≤j≤r),有ti=kj,當(dāng)且僅當(dāng)i=k。

定義2(廣告) 給定信息系統(tǒng)IS=(Q,K,A,C),非空有限集表示所有廣告點(diǎn)擊數(shù)據(jù)集,對(duì)?x∈D,有x=。對(duì)任意ai∈A,qj∈Q(1≤i≤r,1≤j≤m),x∈D,若x.a=ai,則a.q=qj在qj上展現(xiàn)ai所產(chǎn)生的點(diǎn)擊率cqj,ai定義如下:

(1)

定義3(點(diǎn)擊行為矩陣) 設(shè)矩陣是一個(gè)m×n的矩陣,其中,m行代表集合Q,n列代表集合A,表示m個(gè)Query頁(yè)對(duì)n個(gè)廣告的點(diǎn)擊情況。矩陣Rm×n的第i行第j列的元素rij為qi的興趣因子,用qi展現(xiàn)aj產(chǎn)生的點(diǎn)擊率cqi,aj表示,若qi展現(xiàn)aj,則rij等于cqi,aj;否則rij為0。即:

(2)

定義4(組合) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q,al∈A(1≤i≤m,1≤l≤r)分別為任意Query頁(yè)、廣告,令qi相匹配的廣告標(biāo)簽組合為Kqi,I(qi,kj,al)為qi的興趣因子,且:

(3)

Kqi可定義如下:

Kqi={kj|kj∈K,I(qi,kj,al)=1},Kqi?K

(4)

定義5(相關(guān)關(guān)系組合) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q,kj∈K,al∈A(1≤i≤m,1≤j≤n,1≤l≤r)分別為任意Query頁(yè)、廣告標(biāo)簽(關(guān)鍵詞)、廣告,令KAqi表示Query頁(yè)qi對(duì)應(yīng)的廣告標(biāo)簽(關(guān)鍵詞)和廣告之間的相關(guān)關(guān)系的組合,I(qi,kj,al)為qi的興趣因子,定義同式(3)。于是,可定義如下:

KAqi={|kj∈K,al∈A,I(qi,kj,al)=1}

(5)

根據(jù)定義1～定義5,所提Q-K-A模型可做如下描述:

定義6(Q-K-A興趣模型) 給定信息系統(tǒng)IS=(Q,K,A,C),令I(lǐng)M={IMi|i=1,2,…,m}為興趣模型,設(shè)qi∈Q(1≤i≤m)為任意Query頁(yè),則qi的興趣模型為IMi=(Rqi,Kqi,KAqi)。其中,Rqi表示qi的點(diǎn)擊行為集合,Kqi表示qi相匹配的廣告標(biāo)簽(關(guān)鍵詞)集合,KAqi表示qi的廣告標(biāo)簽(關(guān)鍵詞)和廣告間的相關(guān)關(guān)系。

1.2 相似度計(jì)算

基于用戶(hù)的協(xié)同過(guò)濾算法的關(guān)鍵環(huán)節(jié)是如何尋找與目標(biāo)用戶(hù)偏好程度相似的用戶(hù),本文采用修正的余弦相似度度量,不僅可使相關(guān)度在數(shù)值上保持相近,也使得所有的評(píng)分曲線(xiàn)趨于平穩(wěn)。令I(lǐng)xy是用戶(hù)和共同評(píng)分的項(xiàng)目向量組合,Ix和Iy分別表示用戶(hù)和用戶(hù)的評(píng)分項(xiàng)目向量,則用戶(hù)和用戶(hù)之間的相似度可以表示如下:

(6)

在基于廣告標(biāo)簽的搜索廣告推薦系統(tǒng)中,Query頁(yè)面相似性主要取決于3個(gè)方面因素:Query頁(yè)間的共擊相似性,共配標(biāo)簽相似性以及共含關(guān)系相似性。本文為充分表示用戶(hù)評(píng)分差異性Query,上述三方面因素分別采用修正余弦相似度度量方法[11]、兩Query頁(yè)之間共同匹配的廣告關(guān)鍵詞的比例以及頁(yè)之間共同匹配的廣告關(guān)鍵詞與廣告相關(guān)關(guān)系的比例來(lái)計(jì)算。同時(shí)本文通過(guò)綜合加權(quán)的方法計(jì)算推薦算法中Query頁(yè)間相似度以降低相似矩陣計(jì)算的稀疏性,并使用Top-N策略減少Q(mào)uery頁(yè)的K-最近鄰域候選集的大小。設(shè)待計(jì)算相似性的2個(gè)Query頁(yè)分別為qi和qj,則相關(guān)定義如下:

定義7(Query頁(yè)間共擊相似性) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q和qj∈Q(i,j=1,2,…,m)為2個(gè)Query頁(yè),則qi與qj之間具有共同點(diǎn)擊行為時(shí)的相似性simQA(qi,qj)可定義為:

(7)

定義8(Query頁(yè)間共配標(biāo)簽相似性) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q和qj∈Q(i,j=1,2,…,m)為2個(gè)Query頁(yè),則qi與qj之間具有共同匹配的廣告標(biāo)簽(關(guān)鍵詞)的相似性simQK(qi,qj)可定義如下:

(8)

其中,Kqi、Kqj、Kqc分別是qi、qj、qc相匹配的廣告標(biāo)簽(關(guān)鍵詞)集合。

定義9(Query頁(yè)間共含關(guān)系相似性) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q和qj∈Q(i,j=1,2,…,m)為2個(gè)Query頁(yè),則qi與qj之間具有共同包含的廣告標(biāo)簽(關(guān)鍵詞)與廣告相關(guān)關(guān)系的相似性simQKA(qi,qj),可定義如下:

(9)

其中,KAqi、KAqj、KAqc分別是qi、qj、qc對(duì)應(yīng)的廣告標(biāo)簽(關(guān)鍵詞)和廣告之間的相關(guān)關(guān)系的集合。

為降低相似矩陣計(jì)算的稀疏性,減少計(jì)算誤差,基于定義7～定義9,通過(guò)綜合加權(quán)的方法得到推薦算法中Query頁(yè)間的綜合加權(quán)相似度。

定義10(Query頁(yè)間綜合加權(quán)相似性) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q和qj∈Q(i,j=1,2,…,m)為2個(gè)Query頁(yè),α≥0,β≥0,γ≥0為3個(gè)權(quán)重調(diào)和因子,且α+β+γ=1,則qi與qj之間的綜合加權(quán)相似性Sim(qi,qj)可定義如下:

Sim(qi,qj)=αSimQA(qi,qj)+βSimQK(qi,qj)+

γSimQKA(qi,qj)

(10)

在本文中,式(10)的權(quán)重調(diào)和因子α、β、γ的具體值是根據(jù)實(shí)驗(yàn)參數(shù)調(diào)節(jié)的方法確定。

1.3 廣告預(yù)測(cè)點(diǎn)擊率

為獲得高質(zhì)量的廣告推薦結(jié)果,帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法思路如下:

1)對(duì)目標(biāo)Query頁(yè)qi與其他Query頁(yè)qx(x=1,2,…,m,但x≠i)之間的綜合加權(quán)相似度計(jì)算結(jié)果進(jìn)行逆序排序(從大到小排序),采用Top-N策略取其中前K個(gè)相似度最高的Query頁(yè)得到目標(biāo)Query頁(yè)qi的K-最近鄰域NK(qi),并獲得NK(qi)中Query頁(yè)上所有展現(xiàn)過(guò)的廣告集合作為候選推薦廣告集A′。

2)以廣告預(yù)測(cè)點(diǎn)擊率為廣告推薦衡量指標(biāo),對(duì)A′中每個(gè)候選展示的廣告al(l=1,2,…,s,s≤r),計(jì)算其在目標(biāo)Query頁(yè)qi上展示時(shí)的預(yù)測(cè)點(diǎn)擊率CTRpre(qi,al),結(jié)合CTRpre(qi,al)和Top-N策略從候選推薦廣告集A′中篩選出最佳推薦廣告集A*。

目標(biāo)Query頁(yè)K-最近鄰域、候選推薦廣告集和廣告預(yù)測(cè)點(diǎn)擊率分別定義如下:

定義11(目標(biāo)Query頁(yè)K-最近鄰域) 給定信息系統(tǒng)IS=(Q,K,A,C),設(shè)qi∈Q為目標(biāo)Query頁(yè),qx∈Q(x=1,2,…,m,但x≠i)為其他Query頁(yè),Sim(qi,qx)為qi與qx之間的綜合加權(quán)相似度,δ>0為給定閾值,則qi的δ-鄰域Nδ(qi)為:

(11)

若將所有其他Query頁(yè)與目標(biāo)Query頁(yè)的綜合加權(quán)相似度序列按從大到小的順序排序,記為S1≥S2≥…≥SK≥…≥Sm-1,其中K

定義12(候選推薦廣告集) 目標(biāo)Query頁(yè)的K-最近鄰域NK(qi)中Query頁(yè)上所有展現(xiàn)過(guò)且目標(biāo)Query頁(yè)qi沒(méi)有展現(xiàn)的廣告構(gòu)成集合稱(chēng)為候選推薦廣告集,記為A′。顯然,A′?A。

(12)

2 帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法

依據(jù)第1節(jié)給出的相關(guān)定義和算法設(shè)計(jì)思路,帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法可描述如下:

算法帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法ADR-CF_T

輸入目標(biāo)Query頁(yè)qi(i=1,2,…,m),Query頁(yè)集合Q(|Q|=r),廣告關(guān)鍵詞集合K(|K|=n),廣告集合A,CTR集合C,鄰居數(shù)N

輸出目標(biāo)Query頁(yè)qi的最佳推薦廣告集A*

步驟1對(duì)集合中的每個(gè)Query頁(yè)qj,1≤j≤|Q|,j≠1,循環(huán)執(zhí)行如下操作:

步驟1.1計(jì)算Query頁(yè)間共擊相似性SimQA(qi,qj)。

步驟1.2計(jì)算Query頁(yè)間共配標(biāo)簽相似性SimQK(qi,qj)。

步驟1.3計(jì)算Query頁(yè)間共含關(guān)系相似性SimQKA(qi,qj)。

步驟1.4計(jì)算Query頁(yè)間綜合相似性Sim(qi,qj)。

步驟2根據(jù)Sim(qi,qj),對(duì)集合中除了目標(biāo)Query頁(yè)qi的剩余對(duì)象從大到小排序。

步驟3選取集合中排序靠前的N個(gè)Query頁(yè)為目標(biāo)Query頁(yè)qi的最近鄰域N(qi)。

步驟4廣告集合中的每個(gè)廣告aj,1≤j≤|Q|,循環(huán)執(zhí)行如下操作:

步驟4.1若目標(biāo)Query頁(yè)qi展現(xiàn)了廣告aj,重新返回步驟4.1;否則,跳到步驟4.2。

步驟4.2將廣告aj加入目標(biāo)Query頁(yè)qi的待展示廣告集合A′中。

步驟5對(duì)于待展示廣告集合A′中的每個(gè)廣告aj,1≤j≤|A′|,循環(huán)執(zhí)行如下操作:計(jì)算目標(biāo)Query頁(yè)qi對(duì)未展示的廣告aj的預(yù)測(cè)點(diǎn)擊率CTRpre(qi,aj)。

步驟6根據(jù)CTRpre(qk,aj),對(duì)待展示廣告集合A′中的廣告從大到小排序。

步驟7選取集合A′中預(yù)測(cè)點(diǎn)擊率最高的前N個(gè)廣告作為T(mén)OP-N最佳推薦廣告集A*。

ADR-CF_T算法時(shí)間開(kāi)銷(xiāo)關(guān)鍵在于Query頁(yè)之間的相似度計(jì)算,計(jì)算Query頁(yè)間共擊相似性SimQA上的時(shí)間開(kāi)銷(xiāo)與傳統(tǒng)CF算法一致,都為O(m·r),計(jì)算Query頁(yè)間共配標(biāo)簽相似性SimQK上的時(shí)間開(kāi)銷(xiāo)是O(m·n),計(jì)算Query頁(yè)間共含關(guān)系相似性SimQKA上的時(shí)間開(kāi)銷(xiāo)為O(m·n·r),因此,ADR-CF_T算法的時(shí)間復(fù)雜度為O(m·n·r)。

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

本文選擇KDDCUP2012[12]中track2的訓(xùn)練數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。該數(shù)據(jù)提供了騰訊搜搜的搜索廣告點(diǎn)擊數(shù)據(jù),共10.6 GB大小,149 639 105條數(shù)據(jù)。本文選取數(shù)據(jù)屬性中的點(diǎn)擊次數(shù)、出現(xiàn)次數(shù)、廣告標(biāo)示符、Query頁(yè)面標(biāo)示符、廣告關(guān)鍵詞標(biāo)示符這5個(gè)屬性作為搜索廣告推薦系統(tǒng)的實(shí)驗(yàn),即Click、Impression、AdID、QueryID、KeywordID。

3.1 數(shù)據(jù)預(yù)處理

本文首先對(duì)原數(shù)據(jù)進(jìn)行隨機(jī)抽樣,選取其中的1 000 000條數(shù)據(jù);根據(jù)本文實(shí)驗(yàn)的數(shù)據(jù)需求,刪除其他7個(gè)屬性列,并刪除重復(fù)項(xiàng)后得到641 566條數(shù)據(jù)。其中Query頁(yè)面290 479個(gè),廣告101 422個(gè),廣告關(guān)鍵詞113 470個(gè);其次,為了進(jìn)一步避免嚴(yán)重的數(shù)據(jù)稀疏性問(wèn)題,選擇點(diǎn)擊記錄不少于30的Query頁(yè)和廣告,剩下19 436條數(shù)據(jù),包含Query頁(yè)10 936個(gè),廣告8 789個(gè),廣告關(guān)鍵詞10 439個(gè),在每個(gè)Query頁(yè)面展現(xiàn)的廣告中,隨機(jī)選取80%的數(shù)據(jù)作為訓(xùn)練集,剩余數(shù)據(jù)作為測(cè)試集。

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

由于采取Top-N的推薦方式,本文實(shí)驗(yàn)采用對(duì)不同鄰居數(shù)計(jì)算的準(zhǔn)確率(Precision)、召回率(Recall)以及F度量(F-measure)來(lái)評(píng)價(jià)搜索廣告推薦系統(tǒng)的質(zhì)量。分別對(duì)它們進(jìn)行如下定義[11,13-14]:

1)準(zhǔn)確率是指為測(cè)試集中目標(biāo)Query頁(yè)推薦的廣告集合Top(q)中,有多少?gòu)V告是q展示過(guò)并且點(diǎn)擊率較高的廣告。令Result(q)是Query頁(yè)在訓(xùn)練集中實(shí)際展現(xiàn)的廣告集合,每個(gè)Query頁(yè)推薦結(jié)果的準(zhǔn)確率計(jì)算公式為:

(13)

2)召回率又稱(chēng)作查全率,是指測(cè)試集中的推薦結(jié)果中,正確推薦所占的比例,則每個(gè)Query頁(yè)推薦結(jié)果的召回率計(jì)算公式為:

(14)

3)F度量是兼顧準(zhǔn)確率和召回率的總體表現(xiàn)的綜合指標(biāo)。F度量的計(jì)算公式為:

(15)

采用平均絕對(duì)誤差(Mean Absolute Error,MAE)對(duì)各權(quán)重調(diào)和因子預(yù)測(cè)的準(zhǔn)確度。對(duì)測(cè)試集中的一個(gè)Query頁(yè)和廣告,令CTRreal(q,a)為Query頁(yè)對(duì)廣告的實(shí)際點(diǎn)擊率,CTRpre(q,a)為Query頁(yè)對(duì)廣告的預(yù)測(cè)點(diǎn)擊率。則平均絕對(duì)誤差(MAE)[14]的計(jì)算表達(dá)式為:

(16)

3.3 結(jié)果分析

3.3.1 參數(shù)調(diào)節(jié)

在帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法中,其關(guān)鍵的相似度計(jì)算方法是對(duì)Query頁(yè)間的共擊相似性、共配標(biāo)簽相似性、共含關(guān)系相似性進(jìn)行加權(quán),使得相似性的計(jì)算更加準(zhǔn)確。本文分別選取10%、20%、30%的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),通過(guò)對(duì)α、β遍歷取值,觀(guān)察MAE(α,β)的變化,權(quán)衡各相似性度量方法的權(quán)重。考慮到α+β+γ=1,因此,只取α、β作為因變量,實(shí)驗(yàn)結(jié)果如圖1～圖3所示。

圖1 10%數(shù)據(jù)集權(quán)重調(diào)節(jié)因子對(duì)MAE的影響

圖2 20%數(shù)據(jù)集權(quán)重調(diào)節(jié)因子對(duì)MAE的影響

圖3 30%數(shù)據(jù)集權(quán)重調(diào)節(jié)因子對(duì)MAE的影響

從圖1～圖3可知,α、β的變化可以影響廣告推薦算法的預(yù)測(cè)準(zhǔn)確度,當(dāng)0.2<α<0.4,0.4<β<0.6時(shí),所提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法的性能最優(yōu)。本文選取α、β、γ最優(yōu)值分別為0.2、0.4、0.4。

3.3.2 可擴(kuò)展性驗(yàn)證

為測(cè)試ADR-CF_T算法的可擴(kuò)展性能,本文通過(guò)隨機(jī)選取數(shù)據(jù)集規(guī)模的20%、40%、60%、80%的數(shù)據(jù)與整體數(shù)據(jù)集的執(zhí)行時(shí)間進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 數(shù)據(jù)集規(guī)模與執(zhí)行時(shí)間之間的關(guān)系

由圖4可知,隨著數(shù)據(jù)規(guī)模的增加,算法的執(zhí)行時(shí)間從緩慢遞增變化為急劇增加,又逐漸平穩(wěn)遞增。

可見(jiàn),帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法在數(shù)據(jù)規(guī)模增加的情況下,其執(zhí)行時(shí)間的增長(zhǎng)在可接受的范圍內(nèi),故該算法具有較好的可擴(kuò)展性。

3.3.3 推薦質(zhì)量對(duì)比實(shí)驗(yàn)

在本文實(shí)驗(yàn)過(guò)程中將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集兩部分,其中,訓(xùn)練集占80%,測(cè)試集占20%。通過(guò)Top-N輸出推薦列表,并采用準(zhǔn)確率、召回率、F度量值對(duì)實(shí)驗(yàn)的推薦質(zhì)量進(jìn)行評(píng)測(cè)。為了更明顯地展現(xiàn)本文提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法的有效性,將權(quán)重調(diào)和因子α、β、γ分別調(diào)為1,即得到基于用戶(hù)的協(xié)同廣告推薦算法[3]、基于標(biāo)簽的廣告推薦算法[15]、基于標(biāo)簽和項(xiàng)目關(guān)系的廣告推薦算法[16]。為了比較以上3種算法和所提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法的推薦質(zhì)量,本文設(shè)計(jì)了3組實(shí)驗(yàn):即TOP5推薦各算法的推薦質(zhì)量對(duì)比、不同N值下各算法的推薦質(zhì)量對(duì)比、推薦質(zhì)量?jī)?yōu)化程度對(duì)比。

1)TOP5推薦各算法的推薦質(zhì)量對(duì)比

本文實(shí)驗(yàn)從準(zhǔn)確率、召回率、F度量值3個(gè)方面,對(duì)所提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法與基于用戶(hù)的協(xié)同廣告推薦算法、基于標(biāo)簽的廣告推薦算法以及基于標(biāo)簽和項(xiàng)目關(guān)系的廣告推薦算法進(jìn)行比較分析,根據(jù)廣告推薦的實(shí)際應(yīng)用情況,本文實(shí)驗(yàn)對(duì)每個(gè)頁(yè)面推薦5個(gè)廣告,即進(jìn)行Top5推薦,實(shí)驗(yàn)結(jié)果如表1、圖5所示。

表1 4種算法TOP5推薦實(shí)驗(yàn)評(píng)價(jià)指標(biāo)結(jié)果

圖5 不同推薦算法Top5推薦質(zhì)量比較

通過(guò)對(duì)比發(fā)現(xiàn),本文提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法在準(zhǔn)確率上比傳統(tǒng)協(xié)同過(guò)濾算法提高52%,在召回率上提高25%,在F度量值上提高46%,整體效果提高近41%。由于本文在計(jì)算Query頁(yè)面之間相似性時(shí),考慮了CTR、廣告關(guān)鍵詞以及廣告關(guān)鍵詞和廣告之間的關(guān)系三方面因素的影響,綜合的相似度計(jì)算方法可以有效地反映Query頁(yè)對(duì)廣告的偏好信息,廣告關(guān)鍵詞對(duì)于Query頁(yè)和廣告之間的相關(guān)性以及廣告本身的特征進(jìn)行較完整的描述。同時(shí),本文提出的相似性度量的權(quán)重調(diào)和因子α、β、γ,通過(guò)分析發(fā)現(xiàn)其取值對(duì)推薦算法的預(yù)測(cè)準(zhǔn)確度有較大的影響。

2)不同N值下各算法的推薦質(zhì)量對(duì)比

最近鄰居數(shù)的選擇對(duì)推薦算法的推薦質(zhì)量同樣產(chǎn)生影響,因此,本文對(duì)比了最近鄰居數(shù)選擇為5、10、15、20、25、30的情況下,分別對(duì)基于用戶(hù)的協(xié)同廣告推薦算法、基于標(biāo)簽的廣告推薦算法、基于標(biāo)簽和項(xiàng)目關(guān)系的廣告推薦算法以及本文提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法的準(zhǔn)確率、召回率及F度量值進(jìn)行比較,其對(duì)比結(jié)果如圖6～圖8所示。

圖6 不同N值下的準(zhǔn)確率對(duì)比

圖7 不同N值下的召回率對(duì)比

圖8 不同N值下的F度量值

通過(guò)對(duì)比發(fā)現(xiàn),當(dāng)為每個(gè)頁(yè)面推薦25個(gè)廣告時(shí),本文提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法與其他3種算法相比,在準(zhǔn)確率上提高至少17%,在召回率上提高至少0.9%,在F度量值上提高至少21%。隨著最近鄰居數(shù)的增加,出現(xiàn)推薦效果不增反減的現(xiàn)象。這是因?yàn)樵趶V告推薦系統(tǒng)中,真正相似的Query頁(yè)面的數(shù)量有限。當(dāng)選擇更多的不相似鄰居后,這些Query頁(yè)面展現(xiàn)了來(lái)自不相似Query頁(yè)面中的點(diǎn)擊率較高的廣告,導(dǎo)致推薦質(zhì)量下降。因此,只有在廣告推薦系統(tǒng)中正確地選擇相似的Query頁(yè)作為最近鄰居,才能得到理想的協(xié)同推薦效果。

3)推薦質(zhì)量?jī)?yōu)化程度對(duì)比

表2 不同算法的系數(shù)選擇以及擬合優(yōu)度指數(shù)

圖9 推薦結(jié)果的準(zhǔn)確率和召回率高斯擬合曲線(xiàn)

通過(guò)高斯擬合后的曲線(xiàn)看出,基于用戶(hù)的協(xié)同廣告推薦算法和基于標(biāo)簽和項(xiàng)目關(guān)系的廣告推薦算法相比,隨著召回率升高,兩條曲線(xiàn)產(chǎn)生交點(diǎn),根據(jù)表2中提供的系數(shù)可以求得交點(diǎn)坐標(biāo)約為(0.047 2,0.016 8),則在召回率區(qū)間(0,0.047 2),基于用戶(hù)的協(xié)同廣告推薦算法的準(zhǔn)確率低于基于標(biāo)簽和項(xiàng)目關(guān)系的廣告推薦算法,其相差程度逐漸減小;在區(qū)間[0.047 2,0.08],基于用戶(hù)的協(xié)同廣告推薦算法的準(zhǔn)確率高于基于標(biāo)簽和項(xiàng)目關(guān)系的廣告推薦算法,并且相差程度逐漸增大。隨著召回率增加,本文提出的帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法的準(zhǔn)確率明顯高于其他3種算法,相比之下基于標(biāo)簽的廣告推薦算法的準(zhǔn)確率最低,與上一實(shí)驗(yàn)結(jié)果一致。

綜上所述,通過(guò)分析廣告關(guān)鍵詞、廣告及其之間的關(guān)系來(lái)構(gòu)建Query頁(yè)的興趣度模型,計(jì)算綜合的整體相似性,相對(duì)于利用CTR作為偏好信息以及廣告關(guān)鍵詞作為隱式偏好信息的方法,本文提出的廣告推薦算法構(gòu)建的Q-K-A興趣度模型更加準(zhǔn)確,具有較好的可擴(kuò)展性,推薦的質(zhì)量也得到了提高。

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

本文基于用戶(hù)的協(xié)同推薦以及基于標(biāo)簽的推薦技術(shù),探索標(biāo)簽與項(xiàng)目之間的關(guān)聯(lián)關(guān)系,提出一種綜合整體相似性的度量算法。該算法可正確地表達(dá)搜索廣告推薦系統(tǒng)中Query頁(yè)面的興趣模型,使計(jì)算鄰域的準(zhǔn)確性得到保證,進(jìn)而提高了推薦的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明,相比傳統(tǒng)協(xié)同過(guò)濾算法、基于標(biāo)簽的推薦算法以及基于標(biāo)簽和項(xiàng)目關(guān)系的推薦算法,帶標(biāo)簽的協(xié)同過(guò)濾廣告推薦算法具有更好的可擴(kuò)展性和更優(yōu)的推薦質(zhì)量。但該算法未考慮影響廣告點(diǎn)擊率的其他因素,如位置、出價(jià)等因素,因此,下一步將考慮與機(jī)器學(xué)習(xí)算法相結(jié)合,挖掘廣告本身屬性,提取特征信息,在實(shí)際應(yīng)用中分析影響廣告點(diǎn)擊率的因素,提高推薦精確度。

[1] 王勇睿.互聯(lián)網(wǎng)廣告算法和系統(tǒng)實(shí)踐[EB/OL].[2014-10-20].https://yuedu.com.

[2] WANG Jinqiao,WANG Bo,DUAN Lingyu,et al.Interactive ads recommendation with contextual search on product topic space[J].Multimedia Tools and Applications,2014,70(2):799-820.

[3] ANASTASAKOS T,HILLARD D,KSHETRAMADE S,et al.A collaborative filtering approach to ad recom-mendation using the query-ad click graph[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management.New York,USA:ACM Press,2009:1927-1930.

[4] 霍曉駿,賀 樑,楊 燕.一種無(wú)位置偏見(jiàn)的廣告協(xié)同推薦算法[J].計(jì)算機(jī)工程,2014,40(12):39-44.

[5] MA H,LYU M R,ZHOU D,et al.Recommender systems with social regularization[C]//Proceedings of the 4th ACM International Conference on Web Search and Data Mining.New York,USA:ACM Press,2011:287-296.

[6] 范雙燕.基于廣告點(diǎn)擊率以及標(biāo)簽推薦圖模型的廣告推薦方法研究[D].北京:北京交通大學(xué),2015.

[7] 張國(guó)燕.基于標(biāo)簽的個(gè)性化廣告精準(zhǔn)營(yíng)銷(xiāo)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].武漢:華中師范大學(xué),2013.

[8] 范雙燕,王志海,劉海洋.基于改進(jìn)的FolkRank廣告推薦及預(yù)測(cè)算法[J].軟件,2014,35(9):43-48.

[9] 田雪松.基于協(xié)同過(guò)濾的移動(dòng)互聯(lián)網(wǎng)廣告推薦方法的研究[D].成都:西華大學(xué),2016.

[10] BREESE J S,HECKERMAN D,KADIE C.Empirical analysis of predictive algorithms for collaborative filtering[J].Uncertainty in Artificial Intelligence,1998,98(7):43-52.

[11] JASCHKE R,MARINHO L,HOTHO A,et al.Tag recommendations in social bookmarking systems[J].AI Communications,2008,21(4):231-247.

[12] KDDCup[EB/OL].[2012-12-21].http://acm.sjtu.edu.cn/courses/kddcup/2012.

[13] NANOPOULOS A.Item recommendation in collaborative tagging systems[J].EEE Transactions on Systems Man & Cybernetics,Part A:Systems & Humans I,2011,41(4):760-771.

[14] AMANDI A,GODOY D.Hybrid content and tag-based profiles for recommendation in collaborative tagging systems[C]//Proceedings of Latin American Web Con-ference.Washington D,C.,USA:IEEE Press,2008:58-65.

[15] SCHLEE C.Targeted advertising technologies in the ICT space[M].Berlin,Germany:Springer,2013.

[16] CANTADOR I,BELLOGIN A,IGNACIO F T,et al.Semantic contextualisation of social tag-based profiles and item recommendations[J].E-Commerce and Web Tech-nologies,2011,85:101-113.