前言：本站為你精心整理了平衡采樣的廣告點擊率預(yù)估方式范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

類別不平衡問題，指的是訓(xùn)練樣本的分布不均勻問題。具體的說就是某些類的樣本遠多于其他類的樣本。通常定向廣告聯(lián)盟的廣告點擊日志中正樣本（被點擊的記錄）和負樣本（未被點擊的記錄）比例為1:1000，很顯然這是一個類別不平衡問題。眾多處理類別不平衡算法中，對訓(xùn)練數(shù)據(jù)進行下采樣是一種被廣泛接受和采納的策略[7,8,9]，下采樣能削減訓(xùn)練數(shù)據(jù)的大小，縮短訓(xùn)練時間，然而單純的下采樣無法全面利用大類樣本提供的信息。平衡采樣通過集成一組在下采樣之后訓(xùn)練集上訓(xùn)練所得分類器，補回了下采樣所造成的信息丟失。本文借鑒平衡采樣思想，構(gòu)建一組邏輯回歸模型對進行點擊率預(yù)估，我們稱這一方法為平衡采樣邏輯回歸。本文的組織結(jié)構(gòu)如下，第二節(jié)介紹簡單介紹類別不平衡算法的問題以及常用的采樣策略，第三節(jié)介紹平衡邏輯回歸模型，第四節(jié)給出性能和效果實驗，最后對未來的工作進行總結(jié)和展望。

1類別不平衡問題和下采樣算法

類別不平衡問題指的是訓(xùn)練樣本的分布不均勻的問題。例如在人臉檢測[10]中，照片中人臉的數(shù)據(jù)顯然是大大少于背景的數(shù)目的。類別不平衡問題在生活中非常常見，它會給機器學(xué)習(xí)的算法帶來諸多困難。首先由于類別的不平衡性，稀有類的樣本過少，很難真實的刻畫稀有類的分布信息。同時由于正樣本過于稀疏，很容易在特征空間中形成一些比較小的數(shù)據(jù)區(qū)塊。Weiss[11]表明分類錯誤很多時候都會集中在一些很小的區(qū)塊中間。其次，傳統(tǒng)的機器學(xué)習(xí)算法在處理類別不平衡問題時都會有不同程度的下降。最后，以準確率為標準的評判標準通常會忽視稀有類的重要性和影響。以廣告點擊率為例，在一個千分之一的廣告點擊率下，即使我們認為所有的廣告都不會被點擊，它仍然有99.9%的準確率。這顯然是不符合實際情況的。通常解決類別不平衡問題的方法主要分為兩大類，一種是從訓(xùn)練集角度出發(fā)，通過改變訓(xùn)練樣本的分布，降低訓(xùn)練樣本之間的不平衡性，提高分類效果。另一種從算法的角度出發(fā)，針對算法在處理類別不平衡問題中所碰到的缺陷，有目的性的解決這些問題。基于訓(xùn)練集的算法最重要的策略就是上采樣和下采樣，上采樣通過對稀有類增加數(shù)據(jù)來調(diào)整訓(xùn)練數(shù)據(jù)的類別不平衡性，下采樣方法通過刪除大類的數(shù)據(jù)從而改變訓(xùn)練數(shù)據(jù)的分布使得訓(xùn)練數(shù)據(jù)更加平衡。在點擊率預(yù)估問題中，考慮到線上日志的數(shù)據(jù)量已經(jīng)達到TB級別，上采樣給計算資源和存儲資源的帶來更加沉重的消耗，因此，本文不予考慮。最原始的下采樣方法就是隨機下采樣[3]，事實證明，這樣的采樣方法在一定程度上降低了類別不平衡性。在此基礎(chǔ)上，很多啟發(fā)式的下采樣方法被提了出來，Hart[4]中提出了CNN原則，提出了穩(wěn)定子集的概念。并以此為采樣原則對數(shù)據(jù)進行采樣。Wilson在[9]中提出了ENN原則，如果一個大類樣本最近的三個樣本有兩個是被標記為稀有樣本的，則進行刪除這一樣本。在ENN的基礎(chǔ)上，Laurikkala[8]提出了NCL方法，使用ENN在稀有類和大類同時進行樣本的刪除。Tomek[13]考慮到類別不平衡問題在決策邊界中的不穩(wěn)定性，使用樣本之間距離來刪除訓(xùn)練樣本中決策邊界的樣本點來進行數(shù)據(jù)的下采樣。

2平衡采樣邏輯回歸

2.1基于邏輯回歸的點擊率預(yù)估

邏輯回歸是機器學(xué)習(xí)中被廣泛使用的分類模型，它的輸出值表示了某個樣本被標記為正樣本的概率，在定義上它和點擊率（廣告被點擊的概率）是相吻合的。因此，在文獻[14]中被提出之后，它就被廣泛采用到了各大聯(lián)盟的點擊率預(yù)估系統(tǒng)之中。由于聯(lián)盟廣告點擊率系統(tǒng)中特征總數(shù)非常龐大，然而真正有用的特征較少，L1范式的正則化項能有效的讓模型變得稀疏，起到一個特征選擇的作用。隨后，微軟提出的owlqn[15]算法有效的解決了LBFGS[16]優(yōu)化算法中L1范式不可微的問題，因此，L1范式+邏輯回歸的模型以及owlqn算法的優(yōu)化成了各大聯(lián)盟系統(tǒng)的首選。

2.2平衡隨機森林和easyensemble

隨機森林通過集成多個決策樹在機器學(xué)習(xí)中得到了廣泛的應(yīng)用。它通過的對原始數(shù)據(jù)的自采樣，決策樹訓(xùn)練過程中對特征空間的隨機劃分，使得模型訓(xùn)練過程中在樣本和特征選擇上都進行隨機，讓不同的決策樹都有較高的準確率以及決策樹之間較大的差異性，實驗表明，它比普通單個決策樹在泛化誤差要好.然而，和傳統(tǒng)的機器學(xué)習(xí)算法一樣，它在處理類別不平衡數(shù)據(jù)的時候很難的。文獻[17,18]發(fā)現(xiàn)對于決策樹這樣的分類器，如果能人工的使用采樣或者插值的方法將數(shù)據(jù)集調(diào)整到類別平衡時將會取得更好的分類效果，它也證明了下采樣通常能取得比上采樣更好的分類效果。根據(jù)上述理論，Chen[19]提出了平衡隨機森林方法，該方法對正類和反類分別進行不同力度重采樣，使得采樣后的數(shù)據(jù)類別平衡（這個過程稱之為平衡采樣）。最后在重采樣多次后采用多數(shù)投票的方法進行集成學(xué)習(xí)，整個算法的流程如下所示。

2.3平衡邏輯回歸的點擊率預(yù)估

上文介紹了平衡采樣策略在處理類別不平衡問題時的廣泛應(yīng)用。它刪除了大量的負樣本數(shù)據(jù)，縮短訓(xùn)練時間。而訓(xùn)練多個分類器進行集成能有效的將下采樣所帶來的信息丟失補回。當(dāng)將它應(yīng)用到廣告點擊率預(yù)估問題中的時候，考慮到線上模型都是使用邏輯回歸模型。因此，本文提出了平衡邏輯回歸算法進行點擊率預(yù)估。平衡采樣邏輯回歸算法的流程如算法2所示，和平衡隨機森林相比，兩者之間有以下兩點的區(qū)別。1.平衡邏輯回歸在每一步采樣之后，所采用的方法是邏輯回歸，這一策略主要的考慮在于現(xiàn)有聯(lián)盟所采用的基本都是邏輯回歸算法，獨立開發(fā)一套新的大規(guī)模并行的機器學(xué)習(xí)算法需要消耗大量的時間。2.平衡邏輯回歸在采樣過程中，沒有真正的做到類別平衡。每一輪都是以一定的采樣力度α對負樣本進行采樣。使用這樣的策略主要是出于運算和存儲資源考慮。現(xiàn)有的定向廣告的點擊率通常只有千分之一，這意味著正樣本和負樣本比值達到1:1000，如果在每一輪都做到真正類別平衡，意味著刪除99.9%的負樣本，這會刪除大量的負樣本，相應(yīng)的，也需要訓(xùn)練大量的分類器進行集成以補回采樣造成的信息丟失。這樣的策略在現(xiàn)實點擊率預(yù)估系統(tǒng)是不現(xiàn)實的，首先訓(xùn)練大量的分類器是一個非常消耗計算資源的過程，其次，線上加載大量模型會造成機器的CPU空閑時間大大減少，甚至造成系統(tǒng)的癱瘓。因此在平衡采樣的邏輯回歸算法中，通常只能加載若干（3-5個）模型，因此也在每一輪采樣過程中無法做到真正的平衡采樣。

3實驗結(jié)果

3.1實驗設(shè)置

實驗采用國內(nèi)最大的定向廣告聯(lián)盟，百度聯(lián)盟的點擊日志作為訓(xùn)練集，訓(xùn)練邏輯回歸模型。并使用這一模型在百度線上進行了多天線上實驗。該數(shù)據(jù)集包含150多種特征，既有廣告ID，網(wǎng)站ID等ID類特征，也有廣告物料等泛化類特征，由于所有類的特征都被離散化處理，因此每條記錄的特征數(shù)目是非常龐大的。所有實驗數(shù)據(jù)的準備和owlqn算法的訓(xùn)練過程都在hadoop集群上運行[21]。集群共有4000個節(jié)點，每個節(jié)點由8核*2.4GHZ的CPU以及16G內(nèi)存以及12TB硬盤組成。每天產(chǎn)生原始的日志數(shù)據(jù)量達到20T，在經(jīng)過特征歸一化，hash索引后，壓縮至200G的訓(xùn)練數(shù)據(jù)。

3.2實驗設(shè)計

實驗主要從以下幾個方面展開，首先作為一個廣告點擊率相關(guān)的策略，雖然它主要的目的在于縮短訓(xùn)練時間，減小線上模型。但是它不能在點擊率預(yù)估的效果上有太大下降，要爭取做到持平。其次，在點擊率預(yù)估效果沒有太大下降的前提之下，考察這一算法在性能上的表現(xiàn)，包括計算資源和存儲資源的節(jié)約。最后，性能的提升可以帶來的模型的可擴展性，為了展示這一擴展性。一些過去無法被加入點擊率預(yù)估的特征被采納進來，并取得了良好的點擊率預(yù)估效果。在評判指標的選擇中，采用了類別不平衡問題中最常見的評判標準AUC。同時也在真實線上環(huán)境中做實驗，觀察策略對線上廣告點擊率造成的影響。

3.3點擊率預(yù)估效果實驗

3.3.1不同采樣力度α對點擊率預(yù)估效果影響聯(lián)盟廣告的點擊日志是一份非常冗余的日志。很多網(wǎng)頁或廣告很可能在廣告點擊日志中只有個位數(shù)的展現(xiàn)，無法反映廣告點擊率這樣的數(shù)據(jù)占據(jù)了廣告點擊日志的很大部分，因此我們大膽的刪除大量負樣本數(shù)據(jù)，在實驗中，考察四個刪除力度α（0%、90%、95%、99%）為了排除多個模型帶來的影響，暫時只使用一個線上模型。

3.3.2模型個數(shù)對點擊率預(yù)估效果的影響在平衡采樣的邏輯回歸過程中，模型個數(shù)是非常重要的參數(shù)。模型個數(shù)過少則線上點擊率預(yù)估效果會下降，模型個數(shù)過多則會消耗過多的計算、存儲資源。圖3是刪除力度為90%的情況下，采用不同模型個數(shù)，線下AUC的變化。可以看到，整體上AUC是隨著的模型個數(shù)的增加而逐漸增加的，但是，這樣的趨勢逐漸放緩。模型個數(shù)為7和8的AUC基本持平。造成這樣的現(xiàn)象主要在于邏輯回歸本身是一種比較穩(wěn)定的模型，雖然對樣本的采樣能造成一定的不穩(wěn)定性，然而隨著模型個數(shù)的增多。這樣不穩(wěn)定性逐漸被消除，最終趨于統(tǒng)一。表3反映了加載一、三、五個模型和不進行采樣只使用一個模型的線上的點擊率變化，可以看到，線上實驗和線下的AUC評估效果基本一致。而且，在加載5個模型之后，數(shù)據(jù)刪除所帶來的信息丟失被多個模型的集成補了回來，線上廣告點擊率效果上已經(jīng)基本和未刪除樣本和集成的策略基本持平，這也與本文算法中“加載若干（3-5）模型”的假設(shè)是相一致的。

3.3.3關(guān)于采樣的討論在平衡采樣的邏輯回歸算法中，節(jié)約資源的主要原因在于采樣，然而我們沒有采用類別不平衡算法中啟發(fā)式的ENN，CNN采樣方法，而是用了最簡單的隨機采樣，這主要從性能因素考慮。無論是的ENN，CNN或者NCL這樣的采樣方法，都需要計算樣本和樣本之間的距離或者樣本和決策邊界的距離，由于百度聯(lián)盟點擊率日志規(guī)模龐大，訓(xùn)練樣本數(shù)目較多（TB級別）、特征維度也非常龐大（幾十萬），計算樣本之間距離過程是非常消耗計算資源的。以ENN為例，在每一輪樣本采樣的過程中，都需要計算每個樣本的3NN樣本，這個過程意味我們要重新對整個訓(xùn)練集（TB級樣本）進行一次遍歷，時間復(fù)雜度為O(n)，顯然這是非常消耗資源的。然而，隨機采樣則完全不同，決定每個樣本是否刪除只需要產(chǎn)生一個隨機數(shù)就能完成，時間復(fù)雜度為O(1)。在本算法過程中，本文采用了一種單邊采樣的策略，即只對負樣本進行采樣。為了證明這一思想的正確性，本文進行了一次實驗，對比了對正樣本和負樣本同時采樣和單邊采樣的在不同模型個數(shù)下的線下AUC。（雙邊采樣中對正樣本采樣20%，負樣本采樣90%。單邊采樣只對負樣本采樣90%）。實驗結(jié)果表明，雙邊采樣效果明顯不如單邊采樣。

3.4性能實驗

本算法最主要的目的在于性能上的提升。表5比較了未對數(shù)據(jù)進行采樣和采樣之后整個系統(tǒng)的性能參數(shù)。其中，刪除力度α為90%，使用3個模型進行投票。在進行數(shù)據(jù)刪除之后，在主要的幾個性能指標上都有了顯著的性能提升。每個模型所需的訓(xùn)練數(shù)據(jù)大小縮減了88%，這和刪除90%負樣本的預(yù)期基本一致，節(jié)約了大量的線上數(shù)據(jù)存儲資源。由于owlqn算法每一輪都要遍歷所有的樣本，因此在樣本刪除之后，算法每一輪所遍歷樣本數(shù)目減少，迭代的時間也大幅度縮減，從600秒下降到了100秒。整體訓(xùn)練時間從過去的八個小時下降到了一個半小時，大大加快了模型的產(chǎn)出速度。與此同時，模型的大小也隨之縮減了50%。由于在線上進行點擊率預(yù)估的時候需要同時加載三個模型，因此線上機器的CPU空閑時間下降了，然而這樣的降低和整體的性能提升相比完全是可以接受的。綜合效果實驗和性能實驗的結(jié)果，可以看到平衡采樣邏輯回歸方法節(jié)約了大量的線下存儲和計算資源，有效的提升了點擊率預(yù)估系統(tǒng)的性能。更重要的是，這樣的性能提升并沒有造成點擊率預(yù)估效果上的下降。主要原因在于兩點，首先廣告點擊率預(yù)估的負樣本中的冗余性非常高，即使刪除大量的負樣本也不會造成顯著的預(yù)估效果下降，其次多次采樣的集成多個模型的學(xué)習(xí)方法能有效的補回由于刪除負樣本所造成的信息丟失。

3.5模型可擴展性實驗

平衡采樣邏輯回歸幫助廣告點擊率預(yù)估節(jié)省了大量的計算和存儲資源，這些節(jié)省下來的資源幫助后續(xù)的策略團隊上線更多過去不可能被使用的特征，為了說明這一擴展性，本文簡單的做了一個實驗。網(wǎng)站url和用戶cookie是兩個非常細粒度的特征，每天的點擊日志中會有數(shù)以億計的url和cookie。在離散化的邏輯回歸算法下，如果把這兩個特征加入到模型之中會造成線上模型大小以及訓(xùn)練時間的大幅度增加，因此在過去幾年的特征團隊一直沒有將其放入點擊率預(yù)估模型。然而在進行平衡采樣之后，計算和存儲資源被節(jié)省了下來，這兩個特征以及可以被嘗試加入到廣告點擊率預(yù)估模型之中，首先看一下在加入特征之后系統(tǒng)整體的性能參數(shù)。

4結(jié)束語

本文借鑒了在類別不平衡算法中平衡采樣方法，并針對廣告點擊率問題中訓(xùn)練數(shù)據(jù)的特點，提出了平衡采樣邏輯回歸算法。事實證明，該算法能在不犧牲模型點擊率預(yù)估效果的前提下，有效提升整個系統(tǒng)的性能指標。然而，現(xiàn)有的平衡采樣方法由于加載多個模型造成線上機器CPU空閑時間的下降。因此，是否存在其他方法不讓系統(tǒng)同時加載多個模型，是否有更好的辦法彌補數(shù)據(jù)刪除所帶來的信息丟失是下一步需要考慮的問題和工作。

作者：施夢圜顧津吉單位：南京大學(xué)軟件新技術(shù)國家重點實驗室百度中國有限公司聯(lián)盟研發(fā)部