FM集成模型在廣告點(diǎn)擊率預(yù)估中的應(yīng)用

潘 博 張青川 于重重 謝小蘭

(北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院 北京 100048)

0 引 言

隨著廣告計(jì)費(fèi)方式的改變，廣告點(diǎn)擊率CTR(Click-through Rate)估計(jì)在廣告投放過程中占有越來越重要的地位。在預(yù)測效果的評價(jià)標(biāo)準(zhǔn)中，AUC (Area Under Curve)為ROC(Receiver Operating Characteristics)曲線下的面積，可以反映分類器的平均性能，并對不同的ROC曲線進(jìn)行比較，比起ROC曲線更能反映分類器效果。因此AUC值適合作為CTR 預(yù)估模型的評價(jià)標(biāo)準(zhǔn)，一個(gè)完美分類器的AUC為1.0，而隨機(jī)猜測的AUC為0.5。

隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，這一技術(shù)被逐漸采用到廣告點(diǎn)擊率預(yù)估中。基于機(jī)器學(xué)習(xí)的CTR預(yù)估方法一般可以分為三種：線性機(jī)器學(xué)習(xí)模型、非線性機(jī)器學(xué)習(xí)模型，以及融合模型。線性機(jī)器學(xué)習(xí)模型具有簡單易實(shí)現(xiàn)、易擴(kuò)展、易在線更新的特點(diǎn)，可以處理超大規(guī)模的數(shù)據(jù)，因此在產(chǎn)業(yè)界應(yīng)用較為廣泛。文獻(xiàn)[1]首次將CTR預(yù)估問題由概率估計(jì)問題轉(zhuǎn)成回歸問題。該文提出用邏輯回歸LR(Logistic Regression)來解決CTR預(yù)估問題，將具體廣告、環(huán)境抽象成特征，用特征來達(dá)到泛化的目的，從而對廣告點(diǎn)擊率進(jìn)行預(yù)測。文獻(xiàn)[2]提出了基于L-BFGS的OWLQN(Orthant Wise Limitedmemory Quasi Newton)優(yōu)化算法，解決了邏輯回歸損失函數(shù)在L1正則化非連續(xù)可導(dǎo)的問題。這個(gè)方法的優(yōu)點(diǎn)在于：這是一種Batch Learning的方法，可以收斂到全局最優(yōu)解，且收斂速度快；損失函數(shù)中使用了L1正則化，避免過擬合的同時(shí)輸出稀疏模型。

線性機(jī)器學(xué)習(xí)模型雖然簡單易擴(kuò)展，但是表達(dá)能力有限，不能學(xué)習(xí)特征間的非線性關(guān)系，即使構(gòu)造出復(fù)雜特征+輕量模型的形式也不一定對線性模型有效，而且費(fèi)時(shí)費(fèi)力。因此非線性模型也被研究用來預(yù)估廣告CTR，形成簡單特征+復(fù)雜模型的形式。文獻(xiàn)[3]首次提出使用點(diǎn)擊日志計(jì)算搜索結(jié)果的點(diǎn)擊率，結(jié)合搜索引擎查詢?nèi)罩竞陀脩酎c(diǎn)擊日志，自動優(yōu)化搜索引擎的檢索質(zhì)量。通過分析用戶在當(dāng)前返回的排序結(jié)果中點(diǎn)擊鏈接的日志，使用支持向量機(jī)算法最大化Kendall相關(guān)系數(shù)，從而達(dá)到排序結(jié)果接近最佳排序的目的。文獻(xiàn)[4]提出了一種在線貝葉斯概率回歸模型OBPR(Online Bayesian Probability Regression)用于在搜索廣告情景下對廣告CTR進(jìn)行預(yù)測。

為了進(jìn)一步提高點(diǎn)擊率預(yù)估的效果，近些年來融合模型也得到了一些嘗試。文獻(xiàn)[5]針對Facebook的社交廣告點(diǎn)擊率預(yù)估研究，提出了迭代決策樹算法GBDT(Gradient Boost Decision Tree)+LR的融合模型。該方法結(jié)合了GBDT非線性模型能擬合非線性特征的特點(diǎn)，以及LR線性模型具有很好的擴(kuò)展性以及模型訓(xùn)練速度快的特點(diǎn)，融合之后的AUC比GBDT和LR單模型均高出3%。文獻(xiàn)[6]提出了人工神經(jīng)網(wǎng)絡(luò)+決策樹(ANN+MatrixNet)融合模型。ANN用來擬合ID類離散特征，輸出點(diǎn)擊概率。MatrixNet為Yandex公司版本的GBDT，用來擬合連續(xù)特征和ANN模型輸出的特征。該融合模型有效地融合了CTR預(yù)估中的分類特征和連續(xù)特征，實(shí)驗(yàn)效果比LR、MatrixNet和ANN單模型要好。

廣告數(shù)據(jù)呈現(xiàn)的高維稀疏性和特征之間存在著高度非線性關(guān)聯(lián)的特點(diǎn)，雖然上述融合模型能同時(shí)具有非線性模型與線性模型的優(yōu)點(diǎn)，但是MatrixNet、GBDT和LR等模型仍然無法有效學(xué)習(xí)特征間的非線性關(guān)系，所以對于高維稀疏、類別不平衡的廣告數(shù)據(jù)無法建立準(zhǔn)確的CTR預(yù)估模型。本文將針對已有的數(shù)據(jù)量大、高維稀疏、類別不平衡的廣告數(shù)據(jù)集，重點(diǎn)研究FM集成模型以使廣告點(diǎn)擊率預(yù)估具有更高的效率和更好的模型精度。

1 FM集成模型原理

1.1 問題描述

本文研究的廣告點(diǎn)擊率預(yù)估問題可以描述為：輸入一個(gè)用戶查詢和其他信息(如性別、年齡、地域、興趣愛好等)，經(jīng)過點(diǎn)擊率預(yù)估系統(tǒng)計(jì)算輸出每一則廣告的點(diǎn)擊概率，即廣告的預(yù)估點(diǎn)擊率。圖1中的黃色模塊描述了一個(gè)廣告點(diǎn)擊率預(yù)估系統(tǒng)的構(gòu)建流程。

圖1 點(diǎn)擊率預(yù)估系統(tǒng)工作流程

針對高維稀疏、類別不平衡的廣告數(shù)據(jù)建立廣告點(diǎn)擊率預(yù)估模型是本文研究重點(diǎn)。本文利用因子分解機(jī)FM(Factorization Machine)模型自動擬合特征間的交互，處理高維稀疏問題；同時(shí)提出了FM集成模型，解決了分類不均衡問題。本文結(jié)合文獻(xiàn)[7]中GBDT的高層特征提取方法形成GBDT+FM融合模型，利用大數(shù)據(jù)處理平臺Hadoop的分布式系統(tǒng)對該模型進(jìn)行并行式訓(xùn)練，減少模型對海量廣告數(shù)據(jù)的訓(xùn)練時(shí)間。

1.2 集成學(xué)習(xí)概述

集成學(xué)習(xí)用多重或多個(gè)弱分類器結(jié)合為一個(gè)強(qiáng)分類器，從而達(dá)到提升分類效果的目的。文獻(xiàn)[8]對解決不均衡問題的集成模型進(jìn)行了分類，集成學(xué)習(xí)主要是基于Bagging[9]和Boosting[10]兩種基本思想。Bagging通過自舉匯聚原始訓(xùn)練集來訓(xùn)練不同的分類器。也就是從原始數(shù)據(jù)集隨機(jī)采樣N次得到N個(gè)數(shù)據(jù)集，通常這N個(gè)數(shù)據(jù)集和原始數(shù)據(jù)集保持同樣的大小，從而通過重采樣過程獲得數(shù)據(jù)多樣性。N個(gè)數(shù)據(jù)集建好后，將某種學(xué)習(xí)算法分別作用于每個(gè)數(shù)據(jù)集，得到N個(gè)分類器。當(dāng)對新數(shù)據(jù)進(jìn)行分類時(shí)，應(yīng)用這N個(gè)分類器進(jìn)行分類，選擇分類器投票結(jié)果中最多的類別為最后的分類結(jié)果。

Boosting與 Bagging 很類似，使用的多個(gè)分類器的類型都是一樣的。但是在Boosting中，不同的分類器是通過串行訓(xùn)練獲得，每個(gè)新分類器都根據(jù)已訓(xùn)練出的分類器的性能進(jìn)行訓(xùn)練，通過集中關(guān)注被已有分類器錯(cuò)分的那些數(shù)據(jù)來獲得新的分類器。Boosting分類的最終結(jié)果是根據(jù)所有基分類器的權(quán)重加權(quán)求和得到的，該權(quán)重代表的是分類器在上一輪迭代中的成功度。AdaBoost算法[14]已成為目前最流行的Boosting算法，該算法的效率與Freund改進(jìn)算法很接近，卻可以非常容易地應(yīng)用到實(shí)際問題中。

本文數(shù)據(jù)集中的未被點(diǎn)擊的廣告數(shù)(反例數(shù)目)比被點(diǎn)擊的廣告數(shù)(正例數(shù)目)多出25倍，顯然屬于非均衡分類問題。為了解決非均衡分類問題，本文采用多重?cái)?shù)據(jù)抽樣方法，構(gòu)造基于數(shù)據(jù)集多重抽樣的集成分類器，同時(shí)采用了AUC作為模型評價(jià)指標(biāo)。

1.3 FM集成模型

FM是由Steffen Rendle[11-12]提出的一種基于矩陣分解的機(jī)器學(xué)習(xí)算法。其最大的特點(diǎn)是對于稀疏的數(shù)據(jù)具有很好的學(xué)習(xí)能力。本文涉及廣告CTR預(yù)估，其數(shù)據(jù)同樣具有高維稀疏的特點(diǎn),因此采用FM模型作為基分類器，結(jié)合了Bagging和Boosting的集成思想進(jìn)行集成學(xué)習(xí)。由于本文中廣告原始數(shù)據(jù)集正負(fù)比例相差較大，類別分布不均衡。為了使輸入到單個(gè)分類器的樣本均衡，本文將正負(fù)樣本分開存儲，分別進(jìn)行采樣。其中正例可全采樣或過采樣，負(fù)例樣本欠采樣，得到的N個(gè)數(shù)據(jù)集進(jìn)行轉(zhuǎn)換后分別輸入FM模型進(jìn)行單獨(dú)訓(xùn)練，每個(gè)FM單模型會有自己的輸出和模型AUC指標(biāo)。各個(gè)模型的輸出通過自身AUC加權(quán)求和形成最終的FM集成分類器，其算法流程圖見圖2。

一般Bagging所用的基分類器為不穩(wěn)定算法，如決策樹，集成才會有較大的效果。此處稍微不同于Bagging思想的地方在于，一方面為了達(dá)到樣本類別均衡，另一方面盡量不丟失原始數(shù)據(jù)模式。FM模型為穩(wěn)定算法，此處集成是為了擬合不同分桶中的負(fù)例樣本。通常廣告數(shù)據(jù)量很大，對N個(gè)數(shù)據(jù)集進(jìn)行串行式訓(xùn)練會消耗大量時(shí)間。針對這個(gè)問題，本文基于大數(shù)據(jù)平臺Hadoop中的MapReduce離線計(jì)算框架進(jìn)行并行化訓(xùn)練，從而提高效率，其模型見圖3。

圖3 FM集成算法的并行化訓(xùn)練模型圖

負(fù)樣本是基于Hive分桶采樣的，如將負(fù)樣本分為N桶，將第1桶負(fù)列樣本和正例樣本混合作為訓(xùn)練集1，將第2桶負(fù)列樣本和正例樣本混合作為訓(xùn)練集2，以此類推，將第N桶負(fù)列樣本和正例樣本混合作為訓(xùn)練集N。分桶的大小需要經(jīng)過實(shí)驗(yàn)來確定。通過Map對每個(gè)數(shù)據(jù)集同時(shí)進(jìn)行單獨(dú)訓(xùn)練出對應(yīng)FM模型，然后通過Reduce對各個(gè)模型的輸出通過自身AUC加權(quán)求和，形成最終的FM集成分類器。該模型既實(shí)現(xiàn)了Bagging和Boosting的集成思想的結(jié)合，又降低了訓(xùn)練時(shí)間成本，從而實(shí)現(xiàn)了精度與效率的雙贏。

2 廣告點(diǎn)擊率預(yù)估模型實(shí)驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境介紹

本文采用3個(gè)實(shí)驗(yàn)數(shù)據(jù)集：① 騰訊多媒體展示廣告數(shù)據(jù)集。② SIGKDD Cup2012 track2[15]提供的廣告點(diǎn)擊日志數(shù)據(jù)。③ 國內(nèi)最大的定向廣告聯(lián)盟——百度聯(lián)盟的點(diǎn)擊日志。三個(gè)數(shù)據(jù)集包含會話日志、用戶信息、廣告信息三方面內(nèi)容。

本文采用文獻(xiàn)[7]中基于GBDT 特征提取方法，不僅能提升模型的效果，而且可以減少特征工程的成本和時(shí)間，因此可利用該算法分別提取出其中的ID類特征與GBDT類特征(高層特征)。針對類標(biāo)簽信息，從三個(gè)數(shù)據(jù)集中抽出相同數(shù)量訓(xùn)練集、測試集，信息如表1所示。

表1 訓(xùn)練集、測試集類標(biāo)簽信息

實(shí)驗(yàn)平臺為基于Hadoop的大數(shù)據(jù)處理平臺，用到的組件包括HDFS分布式文件系統(tǒng)、MapReduce離線計(jì)算框架、YARN分布式資源管理系統(tǒng)、Hive分布式數(shù)據(jù)倉庫和Spark的MLlib機(jī)器學(xué)習(xí)算法庫。實(shí)驗(yàn)中集群規(guī)模為1個(gè)Master節(jié)點(diǎn)，3個(gè)Slave節(jié)點(diǎn)，集群網(wǎng)絡(luò)拓?fù)湫畔⑷鐖D4所示。

圖4 集群網(wǎng)絡(luò)拓?fù)?/p>

2.2 實(shí)驗(yàn)總體框架

實(shí)驗(yàn)總體框架如圖5所示。

圖5 FM集成模型實(shí)驗(yàn)總體框架

原始數(shù)據(jù)按正例(點(diǎn)擊記錄)和負(fù)例(展示記錄)分別存放到不同的表。對于正例進(jìn)行隨機(jī)全采樣，即采樣樣本的數(shù)據(jù)量等于原始正例的數(shù)量；對負(fù)例進(jìn)行分桶采樣，第1桶與正例樣本組成數(shù)據(jù)集1，第2桶與正例樣本組成數(shù)據(jù)集2，以此類推，第N桶與正例樣本組成數(shù)據(jù)集N。采樣得到的各個(gè)數(shù)據(jù)集由連續(xù)特征和分類特征組成，對于連續(xù)特征訓(xùn)練GBDT模型提取高層二值特征向量；對于分類特征進(jìn)行ONE HOT獨(dú)熱編碼，形成高維稀疏特征。將兩種特征組合在一起形成最終的N個(gè)訓(xùn)練集。這些訓(xùn)練集用來學(xué)習(xí)最終的FM集成模型。

2.3 實(shí)驗(yàn)過程

2.3.1 單模型實(shí)驗(yàn)

本文采用的三個(gè)廣告數(shù)據(jù)集均為稀疏數(shù)據(jù)。本文利用GBDT 模型的多維特征提取方法提取出的高層特征，并聯(lián)合獨(dú)熱編碼后的 ID 類特征一起輸入到 CTR 預(yù)估模型。為了驗(yàn)證FM模型比LR模型能更好處理高維稀疏數(shù)據(jù)，對兩者進(jìn)行了對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表2所示。

表2 FM與LR在三個(gè)數(shù)據(jù)集上的AUC

由表可以看出，F(xiàn)M模型在三個(gè)稀疏數(shù)據(jù)集都表現(xiàn)出比LR模型更好的預(yù)估性能。FM 因子分解機(jī)基于因子分解，能擬合特征之間的相關(guān)性，可以有效地濾除高維稀疏數(shù)據(jù)中的“噪聲”，提取出權(quán)重較高的特征。

2.3.2 采樣實(shí)驗(yàn)

當(dāng)訓(xùn)練數(shù)據(jù)類別分布極度不平衡時(shí)，嚴(yán)重影響模型的預(yù)測精度。因此在本文中，當(dāng)負(fù)樣本多余正樣本兩個(gè)數(shù)據(jù)量級時(shí)，需采取合理的采樣策略使訓(xùn)練樣本盡量平衡且不丟失有效信息。本文實(shí)驗(yàn)了在三個(gè)數(shù)據(jù)集上的多種正負(fù)樣本比例時(shí)FM模型的效果，AUC取平均值，結(jié)果如圖6所示。

圖6 不同正負(fù)樣本比例下FM模型的AUC指標(biāo)

由圖6可見，AUC隨負(fù)樣本的比重增多呈現(xiàn)出下降的趨勢。當(dāng)正負(fù)比例1∶1時(shí)AUC最大，為0.752 4。除了以上的正負(fù)比之外，本實(shí)驗(yàn)也測試了全量數(shù)據(jù)下(正負(fù)比為1∶25)FM模型效果，其AUC值為0.605 4。當(dāng)對正樣本重采樣，負(fù)樣本欠采樣(正負(fù)比分別為2∶2,2∶3,2∶4)時(shí)，AUC停留在0.5左右，即模型沒有預(yù)測效果。故本文將采用正負(fù)樣本采樣比為1∶1的數(shù)據(jù)集進(jìn)行單模型訓(xùn)練。

2.3.3 模型集成實(shí)驗(yàn)

對于不均衡分類問題，必須經(jīng)過采樣使訓(xùn)練樣本盡量平衡。但采樣之后的數(shù)據(jù)有可能丟失大量的有效信息，即便確定了合理的采樣比例，還是會有信息的丟失，所以提出了FM集成模型，將分桶采樣后的數(shù)據(jù)分別輸入FM單模型訓(xùn)練，然后將單模型輸出按AUC加權(quán)求和，得到最終的FM集成模型輸出。實(shí)驗(yàn)的輸入數(shù)據(jù)為ID類特征，同2.3.2節(jié)一樣在三個(gè)數(shù)據(jù)集上取AUC均值為實(shí)驗(yàn)結(jié)果，如圖7所示。其中橫坐標(biāo)1代表只有一個(gè)單模型，2代表第一個(gè)單模型與第二個(gè)單模型集成，3代表第三個(gè)單模型與前兩個(gè)模型集成，依次類推，25代表第25個(gè)單模型與前面24個(gè)單模型集成。

圖7 FM集成模型指標(biāo)與集成模型個(gè)數(shù)關(guān)系圖

由圖7可知，前5個(gè)模型累計(jì)集成的時(shí)候變化較大，后面隨著單模型的加入AUC仍然在上升，但上升相對緩慢。FM集成模型的AUC比FM單模型AUC提高0.01以上，效果較明顯。

2.3.4 模型對比驗(yàn)證

實(shí)驗(yàn)將ID類特征和GBDT類特征輸入分別輸入到LR模型、FM模型和FM集成模型進(jìn)行AUC比較，進(jìn)一步驗(yàn)證FM模型對于其他輸入特征的有效性。采用的訓(xùn)練數(shù)據(jù)條數(shù)為1 511 992條，正負(fù)樣本比為1∶1。與文獻(xiàn)[7] 相同，ID類特征通過獨(dú)熱編碼后的維數(shù)為3 963 094維，連續(xù)類特征通過訓(xùn)練好的GBDT模型后得到的高層特征維數(shù)為3 840(27×30)維。實(shí)驗(yàn)結(jié)果如表3所示。

表3 FM模型與FM集成模型對比實(shí)驗(yàn)結(jié)果

續(xù)表3

由表3可知，在三個(gè)數(shù)據(jù)集上，無論輸入的是ID類特征還是ID類特征+GBDT類特征，F(xiàn)M集成模型AUC指標(biāo)均為最高，比FM模型高0.01以上，比LR模型高出0.07以上；LR模型的AUC最低，其表達(dá)能力有限，不能學(xué)習(xí)特征間的非線性關(guān)系。顯然，相比其他模型，F(xiàn)M集成模型具有更好學(xué)習(xí)能力。

3 結(jié) 語

本文首先對集成學(xué)習(xí)進(jìn)行了概述，涉及到解決不均衡問題的集成模型的分類，介紹了Bagging和Boosting兩種基本思想；然后提出了本文的FM集成模型架構(gòu)；最后通過采樣實(shí)驗(yàn)、模型集成實(shí)驗(yàn)、模型對比驗(yàn)證，實(shí)驗(yàn)驗(yàn)證了FM集成模型的有效性。

類別不平衡問題在互聯(lián)網(wǎng)廣告點(diǎn)擊率預(yù)估當(dāng)中是常見問題，本文提出了FM集成模型，結(jié)合GBDT高層特征提取方法，形成GBDT+FM的融合模型，并用Hadoop實(shí)現(xiàn)了并行化。該模型在減少建模人工成本和時(shí)間成本的同時(shí)，也能有效提高精度。

[1] McMahan H B, Holt G, Sculley D, et al. Ad click prediction: a view from the trenches[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 1222-1230.

[2] Shan L, Lin L, Sun C, et al. Predicting ad click-through rates via feature-based fully coupled interaction tensor factorization [J]. Electronic Commerce Research and Applications, 2016, 16:30-42.

[3] Agarwal D, Agrawal R, Khanna R, et al. Estimating rates of rare events with multiple hierarchies through scalable log-linear models[C]//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010: 213-222.

[4] Dembczynski K, Kotlowski W, Weiss D. Predicting ads click-through rate with decision rules[C]//Workshop on targeting and ranking in online advertising, WWW’08. 2008.

[5] Shen S, Hu B, Chen W, et al. Personalized click model through collaborative filtering[C]//Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012:323-332.

[6] Agarwal D, Chen B C, Elango P. Spatio-temporal models for estimating click-through rate[C]//Proceedings of the 18th international conference on World wide web. ACM, 2009:21-30.

[7] 田嫦麗, 張珣, 潘博,等. 互聯(lián)網(wǎng)廣告點(diǎn)擊率預(yù)估模型中特征提取方法的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(2):334-338.

[8] Galar M, Fernandez A, Barrenechea E, et al. A review on ensembles for the class imbalance problem: bagging-, boosting-, and hybrid-based approaches[J]. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 2012, 42(4):463-484.

[10] Rok Blagus, Lara Lusa. Gradient boosting for high-dimensional prediction of rare events[J]. Computational Statistics and Data Analysis,2016.

[11] Rendle S. Factorization machines[C]//Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010: 995-1000.

[12] Rendle S. Social network and click-through prediction with factorization machines[C]//KDD-Cup Workshop,2012.

[13] 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. ACM, 2007:521-530.

[14] Pouria Ramzi, Farhad Samadzadegan, Peter Reinartz. An AdaBoost Ensemble Classifier System for Classifying Hyperspectral Data[J]. Photogrammetrie, Fernerkundung, Geoinformation, 2014(1):27-39.

[15] SIGKDD12 Cup[OL]. http://www.kddcup2012.org/c/kddcup2012-track2.