楊 誠

(常州信息職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)與通信工程學(xué)院,江蘇 常州 213164) (*通信作者電子郵箱phlsage@163.com)

基于用戶實(shí)時(shí)反饋的點(diǎn)擊率預(yù)估算法

楊 誠*

(常州信息職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)與通信工程學(xué)院,江蘇 常州 213164) (*通信作者電子郵箱phlsage@163.com)

當(dāng)前主流的在線廣告點(diǎn)擊率(CTR)預(yù)估算法主要通過機(jī)器學(xué)習(xí)方法從大規(guī)模日志數(shù)據(jù)中挖掘用戶與廣告間的相關(guān)性從而提升點(diǎn)擊率預(yù)估精度，其不足之處在于沒有充分考慮用戶實(shí)時(shí)行為對(duì)CTR的影響。對(duì)大規(guī)模真實(shí)在線廣告日志進(jìn)行分析后發(fā)現(xiàn)，在會(huì)話中，用戶CTR的動(dòng)態(tài)變化和用戶先前的反饋行為高度相關(guān)，不同的用戶行為對(duì)用戶實(shí)時(shí)CTR的影響不盡相同?；谏鲜龇治鼋Y(jié)果，提出一種基于用戶實(shí)時(shí)反饋的點(diǎn)擊率預(yù)估算法。首先，從大規(guī)模真實(shí)在線廣告日志數(shù)據(jù)中定量分析用戶反饋和點(diǎn)擊率預(yù)估精度的相關(guān)關(guān)系；然后，根據(jù)分析結(jié)果將用戶的反饋行為特征化；最后，使用機(jī)器學(xué)習(xí)方法對(duì)用戶的行為進(jìn)行建模，并根據(jù)用戶的反饋實(shí)時(shí)動(dòng)態(tài)調(diào)整廣告投放，從而提升在線廣告系統(tǒng)的點(diǎn)擊率預(yù)估精度。實(shí)驗(yàn)結(jié)果表明，用戶實(shí)時(shí)反饋特征和用戶點(diǎn)擊率高度相關(guān)；相比于傳統(tǒng)沒有用戶實(shí)時(shí)反饋信息的預(yù)測(cè)模型，該算法在測(cè)試集上對(duì)AUC(Area Under the Curve)和RIG(Relative Information Gain)指標(biāo)提升分別為0.83%和6.68%。實(shí)驗(yàn)結(jié)果表明，用戶實(shí)時(shí)反饋特征顯著提高點(diǎn)擊率預(yù)估的精度。

機(jī)器學(xué)習(xí);計(jì)算廣告學(xué);點(diǎn)擊率預(yù)估;個(gè)性化;實(shí)時(shí)反饋

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展,在線廣告作為一個(gè)成功的商業(yè)模型,市場(chǎng)規(guī)模已達(dá)到百億美元級(jí)別[1]。在線廣告的點(diǎn)擊率(Click Through Rate, CTR) 預(yù)估一直以來都是計(jì)算廣告領(lǐng)域研究的核心問題。提高CTR預(yù)估精度可以同時(shí)提高廣告平臺(tái)、廣告主和用戶三方的利益:對(duì)廣告平臺(tái)而言,提高廣告點(diǎn)擊率可以提高平臺(tái)收益;對(duì)廣告主而言,高點(diǎn)擊率意味著廣告得到精確推送,有利于產(chǎn)品的推廣和廣告預(yù)算的優(yōu)化使用;對(duì)用戶而言,精準(zhǔn)優(yōu)質(zhì)的廣告可以帶來更好的上網(wǎng)體驗(yàn)。因此,點(diǎn)擊率預(yù)估一直以來都是業(yè)界研究熱點(diǎn)。

CTR預(yù)估任務(wù)是根據(jù)用戶歷史廣告點(diǎn)擊數(shù)據(jù)預(yù)測(cè)未來用戶對(duì)廣告的點(diǎn)擊情況。目前,國內(nèi)外相關(guān)企業(yè)和機(jī)構(gòu)在此問題上開展了廣泛深入的研究。McMahan等[2]利用超大規(guī)模歷史數(shù)據(jù)挖掘用戶與廣告的相關(guān)性,使用大規(guī)模機(jī)器學(xué)習(xí)方法訓(xùn)練預(yù)估模型,從而提高點(diǎn)擊率預(yù)估的精度。Hillard等[3]針對(duì)用戶搜索詞歷史數(shù)據(jù)的稀疏問題,提出了將戶搜索詞(query) 拆分成單詞(unigram) 和詞組 (phrase),然后根據(jù)這些單詞和詞組的平均點(diǎn)擊率來估計(jì)搜索詞和候選廣告的相關(guān)性,以此提高CTR預(yù)估精度的算法。張志強(qiáng)等[4]針對(duì)廣告數(shù)據(jù)特征高維稀疏的特點(diǎn),提出了基于張量分解實(shí)現(xiàn)特征降維,然后使用深度學(xué)習(xí)方法建模調(diào)整廣告投放的算法,以此提升廣告點(diǎn)擊率預(yù)估精度。Shen等[5]在點(diǎn)擊率預(yù)估模型中重點(diǎn)考察用戶的個(gè)性化偏好,提出了一種基于協(xié)同過濾和張量分解的方法,從歷史數(shù)據(jù)中挖掘用戶與展示廣告間的相關(guān)性,以提升廣告點(diǎn)擊率預(yù)估精度。潘書敏等[6]提出了一種基于用戶相似度和特征分化的點(diǎn)擊率預(yù)估算法,通過對(duì)相似用戶建模,挖掘不同用戶類型的特征差異性,從而提升廣告的點(diǎn)擊率預(yù)估精度。

目前這些工作主要集中在通過歷史數(shù)據(jù)挖掘、模型表達(dá)能力增強(qiáng)、特征稀疏性降維、廣告創(chuàng)意與用戶相關(guān)性提升,以及個(gè)性化建模等方面提升廣告點(diǎn)擊率預(yù)估精度，尚未考慮用戶實(shí)時(shí)反饋對(duì)CTR預(yù)估精度的影響。事實(shí)上,用戶的點(diǎn)擊率并非恒定不變,而是伴隨時(shí)間動(dòng)態(tài)變化,當(dāng)前利用用戶歷史點(diǎn)擊率預(yù)測(cè)其未來點(diǎn)擊率的做法還有很大提升空間。從這個(gè)角度出發(fā),本文研究了用戶實(shí)時(shí)反饋對(duì)CTR預(yù)估精度的影響。基于大規(guī)模數(shù)據(jù)比對(duì)分析,本文發(fā)現(xiàn)同一會(huì)話(Session)中用戶的當(dāng)前點(diǎn)擊率與其先前行為呈高度相關(guān)性。舉一個(gè)例子,假設(shè)用戶在最近的網(wǎng)頁瀏覽中忽視了大部分的廣告,那么該用戶點(diǎn)擊下一個(gè)廣告時(shí)的可能性將大大降低;相反,如果該用戶點(diǎn)擊了大部分推送給其的航班廣告,那么該用戶在見到下一個(gè)航班廣告時(shí)的點(diǎn)擊可能性將大大提升。因此,廣告投放系統(tǒng)應(yīng)當(dāng)根據(jù)用戶的反饋實(shí)時(shí)調(diào)整廣告投放。例如：對(duì)喜歡點(diǎn)擊廣告的用戶展示更多的廣告,對(duì)經(jīng)常忽視廣告的用戶應(yīng)當(dāng)減少甚至停止推送廣告。

本文從多個(gè)維度定量地分析了用戶實(shí)時(shí)反饋與用戶CTR的相關(guān)關(guān)系,根據(jù)數(shù)據(jù)分析結(jié)果,提出了一種基于用戶實(shí)時(shí)反饋的點(diǎn)擊率預(yù)估算法。該算法將用戶行為特征化,利用機(jī)器學(xué)習(xí)方法從大規(guī)模歷史數(shù)據(jù)中對(duì)用戶的實(shí)時(shí)行為進(jìn)行建模,根據(jù)用戶反饋實(shí)時(shí)調(diào)整廣告投放,從而提升在線廣告的點(diǎn)擊率預(yù)估精度。

1 用戶實(shí)時(shí)反饋行為分析

為了深入地理解實(shí)際生產(chǎn)環(huán)境中用戶的不同行為在點(diǎn)擊率預(yù)估問題中的作用,本章將從多個(gè)維度定量地分析和討論同一會(huì)話中用戶當(dāng)前點(diǎn)擊概率與用戶先前的不同行為之間的相關(guān)關(guān)系。本文以某廣告公司的真實(shí)廣告歷史點(diǎn)擊日志[7]作為研究數(shù)據(jù)。該數(shù)據(jù)集共包括23天日志約2 400萬條展示和被點(diǎn)擊的廣告樣本。數(shù)據(jù)集的具體情況如表1所示。

表1 行為分析數(shù)據(jù)集基本情況

1.1 用戶點(diǎn)擊或忽視廣告的次數(shù)與用戶實(shí)時(shí)CTR的相關(guān)關(guān)系

用戶點(diǎn)擊或者忽視廣告的行為是用戶對(duì)廣告系統(tǒng)最為直接的反饋。圖1顯示了從會(huì)話開始到當(dāng)前的時(shí)間段內(nèi),用戶點(diǎn)擊的廣告次數(shù)與用戶實(shí)時(shí)CTR兩者之間的關(guān)系,其中橫軸表示用戶先前的點(diǎn)擊次數(shù),縱軸表示符合該模式的這些用戶當(dāng)前時(shí)刻的平均CTR,即實(shí)時(shí)CTR。

從圖1可以看出,用戶的實(shí)時(shí)CTR與用戶先前點(diǎn)擊廣告的次數(shù)呈正相關(guān)關(guān)系。如果用戶先前點(diǎn)擊的廣告次數(shù)為0,那么該用戶的實(shí)時(shí)CTR為0.081%,低于平均值0.084%;如果用戶在此之前點(diǎn)擊過一次廣告,其實(shí)時(shí)CTR上升到12.44%,遠(yuǎn)高于平均CTR;若用戶點(diǎn)擊過兩次廣告,實(shí)時(shí)CTR則繼續(xù)上升到25.27%。隨著點(diǎn)擊廣告次數(shù)的增多,該用戶的實(shí)時(shí)CTR也不斷上升。

與圖1中揭示的點(diǎn)擊模式相反,用戶忽視廣告的個(gè)數(shù)越多,則用戶的實(shí)時(shí)CTR越低。圖2顯示了在會(huì)話中,用戶忽視的廣告?zhèn)€數(shù)與實(shí)時(shí)CTR的關(guān)系。其中,橫軸表示用戶忽視的廣告?zhèn)€數(shù),縱軸表示實(shí)時(shí)CTR。這里,忽視的廣告?zhèn)€數(shù)定義為用戶見到卻關(guān)閉或者沒有點(diǎn)擊的廣告?zhèn)€數(shù)。從圖2可以看出,隨著用戶忽視廣告?zhèn)€數(shù)的增多,用戶實(shí)時(shí)CTR隨之呈下降趨勢(shì)。

圖1 會(huì)話中用戶先前點(diǎn)擊廣告的次數(shù)與實(shí)時(shí)CTR的相關(guān)關(guān)系

圖2 會(huì)話中用戶忽視的廣告?zhèn)€數(shù)與CTR的相關(guān)關(guān)系

1.2 廣告點(diǎn)擊時(shí)間間隔與實(shí)時(shí)CTR的相關(guān)關(guān)系

除了點(diǎn)擊或忽視廣告等直接反饋,用戶點(diǎn)擊廣告的時(shí)間分布也是一種反饋類型。本文針對(duì)會(huì)話中有多次點(diǎn)擊記錄的用戶,分析了其當(dāng)前CTR與其上一次點(diǎn)擊時(shí)間的相關(guān)關(guān)系。圖3顯示點(diǎn)擊數(shù)比例和相鄰兩次點(diǎn)擊廣告的時(shí)間間隔的相關(guān)性,其中橫軸表示相鄰兩次點(diǎn)擊的時(shí)間間隔,單位為分鐘;縱軸表示點(diǎn)擊數(shù)的百分比。由圖3可知,超過80%的點(diǎn)擊,其發(fā)生時(shí)間和上一次點(diǎn)擊時(shí)間的間隔小于1 min。隨著距離上一次點(diǎn)擊時(shí)間的拉長(zhǎng),用戶實(shí)時(shí)CTR不斷下降。可見,用戶點(diǎn)擊廣告的時(shí)間分布也是影響CTR預(yù)估的重要因素。

圖3 會(huì)話中用戶相鄰兩次點(diǎn)擊的時(shí)間間隔比例

1.3 用戶廣告駐留時(shí)長(zhǎng)與實(shí)時(shí)CTR的相關(guān)關(guān)系

一旦用戶點(diǎn)擊了某個(gè)廣告,瀏覽器就會(huì)跳轉(zhuǎn)到對(duì)應(yīng)的廣告頁上。一般而言,用戶在廣告頁上駐留時(shí)長(zhǎng)反映了用戶對(duì)于該廣告的感興趣程度[8]。從圖3可知,大部分的連續(xù)點(diǎn)擊發(fā)生在1 min之內(nèi),本節(jié)以這個(gè)時(shí)間段的數(shù)據(jù)為基礎(chǔ),分析用戶在廣告頁上的駐留時(shí)長(zhǎng)對(duì)用戶實(shí)時(shí)CTR的影響。

圖4顯示了用戶的駐留時(shí)長(zhǎng)與實(shí)時(shí)CTR的相關(guān)關(guān)系。從圖4中可以看出,用戶在上一個(gè)廣告頁的駐留時(shí)長(zhǎng)和實(shí)時(shí)CTR的具有高度相關(guān)性。廣告駐留時(shí)長(zhǎng)小于30 s的實(shí)時(shí)CTR顯著高于駐留時(shí)長(zhǎng)大于30 s的實(shí)時(shí)CTR,駐留時(shí)長(zhǎng)超過30 s以后CTR呈明顯下降趨勢(shì)?？梢?用戶廣告頁駐留時(shí)長(zhǎng)是影響CTR預(yù)估的又一重要因素。

圖4 用戶在上一廣告頁上的駐留時(shí)長(zhǎng)與其實(shí)時(shí)CTR的相關(guān)關(guān)系

1.4 廣告類型與實(shí)時(shí)CTR的相關(guān)關(guān)系

用戶對(duì)于廣告類型的選擇是另一種反饋類型。通過分析數(shù)據(jù)發(fā)現(xiàn),在會(huì)話中很少有用戶重復(fù)點(diǎn)擊同一類型廣告,點(diǎn)擊兩種類型廣告的用戶占大多數(shù)。圖5顯示了在會(huì)話中用戶比例與被點(diǎn)擊廣告類型之間的關(guān)系。其中,橫軸表示被點(diǎn)擊的廣告類型數(shù),縱軸表示用戶百分比。從圖5中可知,在同一會(huì)話中,只有1.14%的用戶會(huì)重復(fù)點(diǎn)擊同一類型廣告。這就意味著,如果用戶已經(jīng)點(diǎn)擊了某個(gè)類型的廣告,那么用戶再次點(diǎn)擊該類型廣告的概率就會(huì)大大降低。

圖5 會(huì)話中被點(diǎn)擊廣告的類型個(gè)數(shù)與用戶比例的相關(guān)關(guān)系

以上數(shù)據(jù)分析結(jié)果表明,用戶的行為反饋與其實(shí)時(shí)CTR高度相關(guān),不同的用戶行為導(dǎo)致用戶實(shí)時(shí)CTR發(fā)生不同變化。用戶點(diǎn)擊或者忽視哪些廣告,點(diǎn)擊廣告的時(shí)間分布,駐留廣告頁時(shí)長(zhǎng)以及所點(diǎn)擊的廣告類型等不同用戶行為反饋對(duì)實(shí)時(shí)CTR的影響不盡相同。因此,只要能從線下歷史數(shù)據(jù)中挖掘用戶反饋與實(shí)時(shí)CTR變化的相關(guān)關(guān)系,對(duì)用戶實(shí)時(shí)行為進(jìn)行建模,基于線上所獲取/跟蹤得到的用戶行為,實(shí)時(shí)反饋到在線廣告系統(tǒng),以此動(dòng)態(tài)調(diào)整廣告投放,就可有效提升線上廣告點(diǎn)擊率。

基于上述分析結(jié)果,本文提出了一種基于用戶實(shí)時(shí)反饋的點(diǎn)擊率預(yù)估算法,多維度量化分析用戶行為特征,利用機(jī)器學(xué)習(xí)方法從大規(guī)模歷史數(shù)據(jù)中學(xué)習(xí)用戶多維度反饋與其實(shí)時(shí)CTR之間的相關(guān)關(guān)系,對(duì)用戶行為進(jìn)行建模,根據(jù)用戶反饋動(dòng)態(tài)調(diào)整廣告投放,從而提升廣告點(diǎn)擊率預(yù)估精度。

2 模型訓(xùn)練

廣告點(diǎn)擊率預(yù)估是機(jī)器學(xué)習(xí)領(lǐng)域中經(jīng)典的有監(jiān)督二分類問題。為了評(píng)估用戶實(shí)時(shí)反饋特征對(duì)于提升點(diǎn)擊率預(yù)估精度的作用,本文分別了選取目前業(yè)界廣泛使用的線性分類器和非線性分類器兩類模型作為預(yù)測(cè)模型,即LR(Logistic Regression)和GBDT(Gradient Boosting Decision Tree)[9]。

2.1 損失函數(shù)

本文選用交叉熵作為預(yù)測(cè)模型的損失函數(shù)(Loss Function), 目標(biāo)是最大化正例的似然估計(jì)。

損失函數(shù)的定義為:

(1)

其中:M為訓(xùn)練樣本的個(gè)數(shù);pi為模型的輸出概率;yi為樣本的標(biāo)簽。

2.2 LR模型

LR模型支持大規(guī)模特征并行訓(xùn)練,模型簡(jiǎn)單穩(wěn)定,結(jié)果可解釋性強(qiáng),目前廣泛應(yīng)用于點(diǎn)擊率預(yù)估等問題[2]。LR點(diǎn)擊率預(yù)估模型表達(dá)式為:

其中：wi為模型需要估計(jì)的參數(shù)；n為特征的維度;xi為樣本的特征。所有特征的加權(quán)和通過sigmoid函數(shù)σ(x)映射到值域(0,1)內(nèi),即該模型輸出概率y。σ(x)的表達(dá)式為:

σ(x)=1/(1+exp(-x))

因?yàn)長(zhǎng)R模型為線性模型,所以可將wi視為特征xi對(duì)應(yīng)的權(quán)重,即|wi|在模型中的相對(duì)大小反映了特征xi的重要性程度。

2.3 GBDT模型

GBDT模型[9]是解決回歸和分類問題的經(jīng)典模型,通常由若干決策樹組合表示,具有擬合非線性特征的能力,廣泛用于解決點(diǎn)擊率預(yù)估等問題[10]。

GBDT模型的訓(xùn)練過程首先從一個(gè)簡(jiǎn)單的模型開始,通過不斷迭代訓(xùn)練產(chǎn)生新的模型來減小已有模型和損失函數(shù)的殘差(residual) 得到最終的模型。具體訓(xùn)練過程如算法1所示。

算法1 GBDT訓(xùn)練算法。

輸入 訓(xùn)練集{(xi,yi)},i=1,2,…,M;損失函數(shù)L(y,F(x));算法迭代次數(shù)T。

輸出 GBDT模型。

1)初始化模型為常數(shù):

2)對(duì)于t=1,2,…,T:

2.1)計(jì)算殘差:

2.2)擬合殘差r。即在數(shù)據(jù)集{(xi,rit)}i=1,2,…,M上訓(xùn)練,得到模型ht(x)。

2.3)求解γt[11]:

2.4)更新模型:

Ft(x)=Ft-1(x)+γtht(x)

3)輸出Ft(x)。

算法1中的h(x)即為每輪迭代產(chǎn)生的新模型,一般用決策樹表示。擬合決策樹經(jīng)典算法包括ID3(Iterative Dichotomiser 3)[12]、CART(Classification And Regression Tree)[13]等,算法的關(guān)鍵點(diǎn)在于如何選取特征值劃分?jǐn)?shù)據(jù)集。以ID3算法為例,該算法采用信息增益(Information Gain, IG) 作為指標(biāo)來選取特征構(gòu)成決策樹的節(jié)點(diǎn)。從數(shù)據(jù)集中訓(xùn)練決策樹的算法如算法2所示。

算法2 決策樹訓(xùn)練算法ID3。

輸入 數(shù)據(jù)集S；特征集合X={x1,x2,…,xn};算法迭代次數(shù)T。

輸出 決策樹模型。

1)從i=1,2,…,n, 在數(shù)據(jù)集S上計(jì)算IG(S,xi), 選取使得IG(S,xi)最大者的特征xi作為決策樹的節(jié)點(diǎn)。其中,IG(S,xi)的計(jì)算公式為:

IG(S,x)=H(S)-H(S′)

(2)

其中:S′表示根據(jù)特征xi劃分的數(shù)據(jù)集的集合;H(S)表示數(shù)據(jù)集S中的熵;C表示數(shù)據(jù)集的類別集合;p(c)表示該類別所占的比例。在本文中,C={0,1},p(c)為數(shù)據(jù)中正例所占百分比,即CTR。

2)遞歸生成決策樹子節(jié)點(diǎn),即在數(shù)據(jù)集S′重復(fù)步驟1),選取特征xj(j≠i)作為特征xi的子節(jié)點(diǎn)。

3)輸出決策樹模型。

綜合應(yīng)用算法1和算法2,通過多次迭代訓(xùn)練即可得到GBDT預(yù)測(cè)模型。

從算法2中可以看出,信息增益IG(S,xi)值的大小反映了特征xi對(duì)數(shù)據(jù)集S的劃分能力,即分類能力。特征越重要,IG(S,xi)值越大,分類能力越強(qiáng)。因此,IG是衡量特征xi相對(duì)于其他特征重要性程度的指標(biāo)。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用某廣告公司的真實(shí)廣告歷史點(diǎn)擊日志[7]作為訓(xùn)練和測(cè)試的數(shù)據(jù)集,樣本包含有用戶、廣告主、域名、廣告創(chuàng)意、廣告展示和點(diǎn)擊時(shí)間等字段信息。按照7∶3的比例,數(shù)據(jù)集被劃分為訓(xùn)練集和測(cè)試集。

訓(xùn)練集和測(cè)試集的具體情況如表2所示。

表2 實(shí)驗(yàn)中訓(xùn)練和測(cè)試數(shù)據(jù)統(tǒng)計(jì)

3.2 特征設(shè)計(jì)

實(shí)驗(yàn)中設(shè)計(jì)的特征分為兩類,即基本特征和用戶實(shí)時(shí)反饋特征。其中,基本特征包含描述基本用戶信息的相關(guān)特征和描述廣告相關(guān)信息的特征,如用戶編號(hào)、用戶所在城市、用戶上網(wǎng)代理(user Agent)信息、廣告編號(hào)、廣告展示位置和廣告類型等。用戶實(shí)時(shí)反饋特征主要根據(jù)第1章的分析結(jié)果設(shè)計(jì)而成,特征的設(shè)計(jì)細(xì)節(jié)及其描述如表3所示。

表3 用戶實(shí)時(shí)反饋特征設(shè)計(jì)

實(shí)驗(yàn)設(shè)置中,對(duì)照模型只包含基本特征,測(cè)試模型包含全部特征。

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

為了更好地理解用戶實(shí)時(shí)反饋特征在點(diǎn)擊率預(yù)估問題中的作用,本文從兩個(gè)方面衡量用戶實(shí)時(shí)反饋特征對(duì)于CTR預(yù)估精度的提升效果:一是從模型的預(yù)測(cè)性能出發(fā),衡量實(shí)時(shí)反饋特征的有效程度;二是從特征與目標(biāo)的相關(guān)性程度出發(fā),衡量實(shí)時(shí)反饋特征的重要程度。

3.3.1 模型性能指標(biāo)

本文采用AUC(Area Under the Curve)和RIG(Relative Information Gain)作為衡量預(yù)測(cè)模型性能的指標(biāo)。

AUC是衡量模型分類能力的一種重要指標(biāo),在實(shí)際應(yīng)用中被廣泛采用[14]。AUC值是ROC(Receiver Operating Characteristic)曲線[15-16]的直觀表示,即ROC曲線下面積。二值分類中,預(yù)測(cè)模型輸出的p值大小表示樣本屬于正例的概率。對(duì)于分類問題,通常需要設(shè)定一個(gè)閾值t將樣本判定為正例或者負(fù)例。AUC指標(biāo)衡量了預(yù)測(cè)模型在任意閾值t下的分類能力。換句話說,AUC指標(biāo)衡量了一個(gè)模型與其輸出值大小無關(guān)的分類能力。AUC的取值為0～1,值越高,表示預(yù)測(cè)模型的分類性能越好。

RIG指標(biāo)[14]是Log Loss函數(shù)的一種線性變換,衡量預(yù)測(cè)模型的輸出p和期望CTR的接近程度。RIG值越高,表示預(yù)測(cè)模型在數(shù)據(jù)集上擬合得越好,輸出的p值和實(shí)際CTR越接近。RIG的計(jì)算公式為：

RIG=1-L(y,p)/H(S)

其中:L(y,p)的計(jì)算見式(1);H(S)的計(jì)算見式(2)。

3.3.2 特征重要性指標(biāo)

獲取特征在預(yù)測(cè)模型中的重要性排名也稱為特征重要性測(cè)試。一般而言,特征和目標(biāo)相關(guān)性程度越高,則該特征越重要,預(yù)測(cè)模型的輸出越依賴于該特征。

由2.2節(jié)可知,LR模型中的特征權(quán)重|wi|的相對(duì)大小反映特征xi在預(yù)測(cè)模型中的重要性。|wi|值越大,特征xi和目標(biāo)y的相關(guān)性程度越高,對(duì)模型輸出結(jié)果的影響越顯著。因此,將LR模型中根據(jù)|wi|值由大到小排列,即可得到不同特征的重要性排名。

由2.3節(jié)可知,特征xi越重要,其劃分?jǐn)?shù)據(jù)集的能力越強(qiáng),即IG(S,xi)的值越大。同理,IG(S,xi)的大小衡量了特征xi和目標(biāo)y的相關(guān)性程度。在GBDT預(yù)測(cè)模型中,對(duì)所用特征關(guān)于IG從大到小排名,即可得到特征的重要性排名。

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

表4列出了不同模型在測(cè)試集上的不同指標(biāo)對(duì)比。從表4中可以看出,利用用戶實(shí)時(shí)反饋信息的預(yù)測(cè)模型的各項(xiàng)指標(biāo)顯著優(yōu)于沒有用戶實(shí)時(shí)反饋特征的對(duì)照模型。加了用戶實(shí)時(shí)反饋信息的預(yù)測(cè)模型LR+User的AUC相對(duì)于對(duì)照模型LR,相對(duì)提升0.65%,RIG相對(duì)提升4.91%;預(yù)測(cè)模型GBDT+User相對(duì)于對(duì)照模型GBDT,AUC相對(duì)提升0.83%,RIG相對(duì)提升6.68%。顯而易見,采用用戶實(shí)時(shí)反饋信息的預(yù)測(cè)模型性能提升顯著。

AUC和RIG兩個(gè)指標(biāo)的顯著提升表明用戶實(shí)時(shí)反饋特征不僅有利于提升預(yù)測(cè)模型的廣告分類能力 (即點(diǎn)擊和非點(diǎn)擊兩類),而且模型對(duì)于歷史數(shù)據(jù)擬合得更好,模型的預(yù)估概率p和實(shí)際的CTR更加接近。

表4 不同模型的AUC和RIG指標(biāo)

表5列出了用戶實(shí)時(shí)反饋特征在LR和GBDT模型中的重要性排名。從表5可知,廣告點(diǎn)擊次數(shù)這一特征在LR和GBDT中的重要性排名分別為第二和第一,由此可見用戶實(shí)時(shí)反饋特征對(duì)點(diǎn)擊率模型的重要性。同時(shí)還可以看到,用戶的實(shí)時(shí)反饋特征排名整體比較靠前,這說明相對(duì)于其他特征,用戶實(shí)時(shí)反饋和用戶的點(diǎn)擊率相關(guān)程度更高,因此用戶實(shí)時(shí)反饋特征對(duì)提升用戶點(diǎn)擊率預(yù)估精度至關(guān)重要。

表5 用戶反饋特征在LR和GBDT模型中的重要性排名

總體而言,用戶實(shí)時(shí)反饋特征和用戶點(diǎn)擊率高度相關(guān),無論從模型的最終預(yù)測(cè)效果還是從特征的重要性測(cè)試結(jié)果來看,實(shí)時(shí)反饋特征對(duì)于預(yù)測(cè)模型的點(diǎn)擊率預(yù)估精度都有著不可忽視的影響。實(shí)驗(yàn)結(jié)果表明,對(duì)用戶行為建模,然后根據(jù)用戶反饋動(dòng)態(tài)調(diào)整廣告投放,可以顯著提升點(diǎn)擊率預(yù)估精度。

4 結(jié)語

在線廣告的點(diǎn)擊率預(yù)估問題一直以來都是機(jī)器學(xué)習(xí)領(lǐng)域中的熱點(diǎn)難點(diǎn)，提高點(diǎn)擊率預(yù)估精度對(duì)于廣告平臺(tái)、廣告商和用戶三方均有重要意義。本文從多個(gè)維度對(duì)用戶實(shí)時(shí)反饋與用戶實(shí)時(shí)CTR兩者的關(guān)系進(jìn)行了量化分析,提出了一種基于用戶實(shí)時(shí)反饋的點(diǎn)擊率預(yù)估算法。該算法對(duì)用戶的實(shí)時(shí)行為特征進(jìn)行建模,根據(jù)線上所跟蹤和獲取的用戶反饋動(dòng)態(tài)調(diào)整廣告投放,從而提升模型點(diǎn)擊率預(yù)估精度。基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)驗(yàn)證了該算法的有效性，相比于對(duì)照模型,采用用戶實(shí)時(shí)反饋特征的預(yù)測(cè)模型AUC指標(biāo)相對(duì)提升0.83%,RIG指標(biāo)相對(duì)提升4.91%。

References)

[1] 智穎. 2015全球廣告預(yù)測(cè)報(bào)告[J]. 中國廣告, 2015(3) : 118-119. (ZHI Y. 2015 global advertising forecast[J]. China Advertising, 2015(3): 118-119.)

[2] McMAHAN H B, HOLT G, SCULLEY D, et al. Ad click prediction: a view from the trenches[C]// KDD 2013: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2013: 1222-1230.

[3] HILLARD D, MANAVOGLU E, RAGHAVAN H, et al. The sum of its parts: reducing sparsity in click estimation with query segments[J]. Information Retrieval, 2011, 14(3): 315-36.

[4] 張志強(qiáng), 周永, 謝曉芹, 等. 基于特征學(xué)習(xí)的廣告點(diǎn)擊率預(yù)估技術(shù)研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2016, 39(4) : 780-794. (ZHANG Z Q, ZHOU Y, XIE X Q, et al. Research on advertising click-through rate estimation based on feature learning[J]. Chinese Journal of Computers, 2016, 39(4): 780-794.)

[5] SHEN S, HU B, CHEN W, et al. Personalized click model through collaborative filtering[C]// WSDM 2012: Proceedings of the Fifth ACM International Conference on Web Search and Data Mining. New York: ACM, 2012: 323-332.

[6] 潘書敏, 顏娜, 謝瑾奎. 基于用戶相似度和特征分化的廣告點(diǎn)擊率預(yù)測(cè)研究[J]. 計(jì)算機(jī)科學(xué), 2017, 44(2) : 283-289. (PAN S M, YAN N, XIE J K. Study on advertising click-through rate prediction based on user similarity and feature differentiation[J]. Computer Science, 2017, 44(2): 283-289.)

[7] ZHANG W, YUAN S, WANG J, et al. Real-time bidding benchmarking with iPinYou dataset[EB/OL]. [2017- 01- 10]. https://arxiv.org/pdf/1407.7073.pdf.

[8] KIM Y, HASSAN A, WHITE R W, et al. Modeling dwell time to predict click-level satisfaction[C]// Proceedings of the 7th ACM International Conference on Web Search and Data Mining. New York: ACM, 2014: 193-202.

[9] FRIEDMAN J H. Stochastic gradient boosting[J]. Computational Statistics amp; Data Analysis, 2002, 38(4): 367-378.

[10] HE X, PAN J, JIN O, et al. Practical lessons from predicting clicks on ads at Facebook[C]// ADKDD 2014: Proceedings of the Eighth International Workshop on Data Mining for Online Advertising. New York: ACM, 2014: 1-9.

[12] QUINLAN J R. Induction of decision trees[J]. Machine Learning, 1986, 1(1): 81-106.

[13] BREIMAN L. Classification and Regression Trees[M]. Boca Raton, Florida, USA: CRC Press, 1984.

[14] YI J, CHEN Y, LI J, et al. Predictive model performance: offline and online evaluations[C]// KDD 2013: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2013: 7-14.

[15] SWETS J A. Measuring the accuracy of diagnostic systems[J]. Science, 1988, 240(4857): 1285.

[16] FAWCETT T. ROC graphs: notes and practical considerations for researchers[J]. Machine Learning, 2004, 31(1): 1-38.

Clickthroughratepredictionalgorithmbasedonuser’sreal-timefeedback

YANG Cheng*

(SchoolofNetworkandCommunicationEngineering,ChangzhouCollegeofInformationTechnology,ChangzhouJiangsu213164,China)

At present, most of the Click Through Rate (CTR) prediction algorithms for online advertising mainly focus on mining the correlation between users and advertisements from large-scale log data by using machine learning methods, but not considering the impact of user’s real-time feedback. After analyzing a lot of real world online advertising log data, it is found that the dynamic changes of CTR is highly correlated with previous feedback of user, which is that the different behaviors of users typically have different effects on real-time CTR. On the basis of the above analysis, an algorithm based on user’s real-time feedback was proposed. Firstly, the correlation between user’s feedback and real-time CTR were quantitatively analyzed on large scale of real world online advertising logs. Secondly, based on the analysis results, the user’s feedback was characterized and fed into machine learning model to model the user’s behavior. Finally, the online advertising impression was dynamically adjusted by user’s feedback, which improves the precision of CTR prediction. The experimental results on real world online advertising datasets show that the proposed algorithm improves the precision of CTR prediction significantly, compared with the contrast models, the metrics of Area Under the ROC Curve (AUC) and Relative Information Gain (RIG) are increased by 0.83% and 6.68%, respectively.

machine learning; computational advertising; Click Through Rate (CTR) prediction; personalization; real-time feedback

2017- 04- 17;

2017- 06- 08。

楊誠(1975—),男,江蘇常州人,副教授,碩士,CCF會(huì)員,主要研究方向:機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘。

1001- 9081(2017)10- 2866- 05

10.11772/j.issn.1001- 9081.2017.10.2866

TP181

A

YANGCheng, born in 1975, M. S., associate professor. His research interests include machine learning, data mining.