基于域內特征間相似性的點擊率預估優化

雷李想，武志昊，4，劉鈺，4，周子站

（1.北京交通大學 計算機與信息技術學院，北京 100044；2.北京交通大學 網絡科學與智能系統研究所，北京 100044；3.中國民航信息網絡股份有限公司，北京 101318；4.民航旅客服務智能化應用技術重點實驗室，北京 101318）

0 概述

自2020 年以來，在線廣告［1］業務已達到1 000 億美元，收入以每年超過15%的速度增長，在線廣告業務是互聯網企業收入的重要來源之一。點擊率（Click-Through Rate，CTR）預估［2］在在線廣告行業中至關重要，其主要目標是在正確的環境中為正確的用戶提供正確的廣告，點擊率預估效果的提升能夠給企業帶來巨大的收益。因此，如何準確有效地預測點擊率已引起學術界和產業界的關注。

早期使用線性模型建模點擊概率，為每個特征分配一個可學習的權重，但該方法無法建模特征間的交互關系。因子分解機（Factorization Machine，FM）［3］為每個特征分配了一個低維的稠密向量即嵌入［4］，通過兩個向量的內積建模特征間的交互關系，此后多數點擊率預模型采用了為每個特征分配一個嵌入的做法，區別在于如何利用特征的嵌入建立特征交互。

盡管大量基于嵌入的點擊率預估方法［5］被提出，但多數方法只關注如何設計建立特征間交互關系的模型，較少有關注特征的嵌入是否得到了較好的更新。而在實際數據集中，由于特征分布的長尾效應［6］，域內的大量特征出現次數極少，而少量的特征的出現次數極多，導致大量的特征嵌入沒有得到較好的更新。文獻［7］和文獻［8］為新出現的商品在ID 域生成即使在少量樣本數據下仍可更新較好的初始嵌入，但該工作只針對ID域，無法解決一般域上的稀疏性問題。

造成特征嵌入學習不充分的本質原因是：直接根據特征取出特征對應的嵌入，這也是現有點擊率預估模型的一般做法。該做法的隱含假設是特征間相互獨立。但實際上特征間存在相似性，以城市域為例，某些小城市出現次數較少，例如臨平，其嵌入訓練不充分，但臨平與杭州相鄰，不論是氣候或居民習慣都與杭州相似，若它能夠有效地利用杭州的嵌入，則能夠提升模型的預測效果。

為解決上述問題，本文提出兩種特征相似度的定義，并利用基于特征相似度的域內特征相似性圖建模域內特征的相似性。在域內特征相似性圖的基礎上，設計基于域內特征相似性的嵌入生成器，該生成器為出現次數較少的特征利用與其相似的特征嵌入生成了新的嵌入，作為預處理過程對特征嵌入向量進行數據增強，新的嵌入與原嵌入維度一致，即可直接作為一般點擊率預估模型的輸入。

1 相關工作

1.1 點擊率預估

點擊率預估的輸入由在不同域上取到的特征值組成，以商品點擊行為預測任務為例，商品產地、商品類別屬于域，而商品產地中具體的中國、日本、美國等稱作特征。每個域下有多個特征，域分為離散域和連續域，離散域內有有限個特征，連續域的特征為連續的數值。

用向量x表示模型的輸入，向量x由在不同域上的特征向量xi拼接而成，用Fi(i=1，2，…，T)表示第i個域，其中T是域的個數。若域Fi是離散域，在該域取到特征fi，a，則xi是一個one-hot 向量，在特征fi，a對應的位置為1，其余位置為0，xi的長度等于域Fi中的特征總數。若第i個域是連續域，則xi是該連續特征值。

點擊率預估的結果用y表示，y=1 表示點擊，否則y=0。點擊率預估任務的目標是獲得輸出點擊概率的映射函數fw(x)，其中，∈[0，1]，w表示函數的參數。

1.2 稀疏特征問題

稀疏特征指域中出現次數極少的特征，該問題導致對應的特征嵌入無法得到較好的更新，而該現象在大型數據集中十分普遍。以Criteo 數據集為例，圖1 所示為Criteo 數據集中C3 和C4 域中特征出現次數的分布情況。從圖1 可以看出：大量的特征出現的次數都非常少，即這些域中的特征存在稀疏性的問題。

圖1 Criteo 數據集中C3 和C4 域中特征出現次數分布Fig.1 Feature occurrence frequency distribution in C3 and C4 domains in Criteo data set

1.3 點擊率預估模型

因為離散域的特征向量xi是高維的one-hot 向量，目前普遍的做法是將其映射到低維的稠密空間，其中，Vi=[ei，1，ei，2，…，ei，Ni]T為域Fi的嵌入矩陣，ei，a∈Rd表示特征fi，a對應的嵌入向量，Ni為域內的特征總數，xi是該域的特征向量，則該特征fi，a的嵌入可表示為：

現有的方法通常直接將ei作為后續分類模型的輸入，即只考慮fi，a對應的嵌入ei，a。不同的模型區別在于：如何使用嵌入ei，a構建特征交互，FM 以特征嵌入的內積表示2 個特征的交互關系。然而，由于缺乏建模更深層特征交互的能力，它的預測能力有限。為了解決這一問題，目前的方法通常采用一個淺層組件學習豐富的低階特征交互，以及一個深度神經網絡［9］來建模高階的特征交互。Wide &Deep［10］提出結合線性模型和深度神經網絡的聯合網絡，但該方法依然需要特征工程［11］。深度因子分解機（Deep Factorization Machine，DeepFM）［12］，將Wide &Deep中的線性模型替換為因子分解機，引入了嵌入來解決這一問題。此后，較新的方法通常都使用基于嵌入的神經網絡來提升模型效果：神經因子分解機（Neural Factorization Machine，NFM）［13］用雙線性交互池將嵌入向量和深度神經網絡連接起來；xDeepFM（eXtreme Deep Factorization Machine）［14］提出了壓縮交互網絡（Compressed Interaction Network，CIN），并將其和深度神經網絡結合，以顯式和隱式方式自動學習高階特征交互；AutoInt［15］提出了利用自注意力機制［16］以及殘差連接［17］建模高階的特征交互；Fi-GNN［18］用圖神經網絡［19］來建模特征間的高階交互關系。

1.4 圖神經網絡

圖卷積網絡（Graph Convolutional Network，GCN）［20］借鑒卷積神經網絡［21］，將卷積算子泛化到圖數據，提出了圖卷積層，每層聚合節點的鄰居節點的表示和其自身表示生成新的表示，公式如下：

其中：H(l)表示第l層的節點嵌入矩陣；表示A+I，A為圖的鄰接矩陣，I表示單位矩陣；表示的度矩陣；W(l)是可學習的參數矩陣。圖卷積網絡在聚合鄰居節點信息時，只是簡單地平均了近鄰的信息，圖注意力網絡（Graph Attention Network，GAT）［22］引入注意力機制［16］，更重要的近鄰節點在聚合時被賦予更高的權重。圖神經網絡近些年發展迅速，在節點分類［23］和鏈路預測［24］領域取得了成功。

2 基于域內特征相似度的嵌入生成模型

2.1 模型框架

如1.3 節描述，現有的方法通常直接將ei作為后續分類模型的輸入，根據損失函數進行反向傳播更新時，只會更新ei，a。考慮丟掉這一假設，通過建模域內特征的相似性，在獲得特征的嵌入時不只考慮該特征，同時考慮域內與其相似的其他特征。

通過建立域內特征相似性圖建模特征的相似性，并根據圖神經網絡，在域內特征相似性圖上聚合相似特征的嵌入信息。由于希望特征能夠有選擇地聚合其近鄰的信息，因此選擇使用圖注意力網絡，更新過程如圖2 所示。具體來說，利用注意力機制決定節點近鄰的重要性。以特征fi，a為例，設域Fi內特征間的相似性圖為GFi，以N(fi，a)表示特征fi，a在GFi中的近鄰，近鄰指與fi，a在圖中存在邊的節點，ei，a表示特征fi，a的嵌入，首先計算特征fi，a與特征fi，k的注意力系數，如式（3）、式（4）所示：

圖2 特征嵌入的更新過程Fig.2 Update process of feature embedding

其中：att 表示注意力函數，首先利用變換矩陣W將嵌入從原始嵌入空間Rd映射到新的空間Rd′，然后將變換后的嵌入進行拼接并乘以長向量aT，最后對值采用激活函 數LeakyReLU［25］。接下來利用系數αa，k更新特征的嵌入，如式（5）所示：

2.2 模型輸出和訓練

經過嵌入生成器后，特征嵌入聚合了與其相似的特征的嵌入信息作為新的嵌入，此時數據的維度與原始嵌入一致，可以作為任意基于嵌入的點擊率預估模型的輸入，輸出點擊概率。

模型訓練使用常用的交叉熵作為損失函數，定義如下：

其中：yj與分別表示真實標簽和模型輸出概率；M表示訓練樣本總量。利用梯度反向傳播［26］最小化損失函數，對嵌入、嵌入生成器、分類器的參數進行更新，模型的整體流程與更新過程如圖3 所示。

圖3 模型整體流程Fig.3 Overall procedure of the model

3 特征相似性圖構建方法

上文描述了利用域內特征相似性解決稀疏特征問題的整體框架，在該模型中利用了域內特征相似性圖建模特征間的相似性，因此如何定義特征的相似以及建立域內特征相似性圖非常關鍵。基于樣本數據，本文提出了2 種特征相似度的定義及高效建立域內特征相似性圖的算法。

3.1 特征相似度的定義

在直觀上，如果2 個特征在其他域上經常取到相同的特征值，就認為這2 個特征較為相似。從該角度出發，提出基于共現概率的相似度定義，將特征相似度定義為2 個特征在其他域共享特征的概率。具體來說，設Fi表示第i個域，域的總數為T，fi，a表示Fi下的具體特征值a，將特征fi，a和特征fi，b在Fj取到相同特征的概率定義為特征fi，a和特征fi，b相對于Fj的相似度sim(fi，a，fi，b，Fj)。fi，a和fi，b在域Fj取到相同特征的概率可以理解為：隨機抽取一條在Fi域取到fi，a的數據和一條在Fj域取到fi，b的數據，這一對數據在Fj域取到的特征是同一個特征的概率。利用頻率估計概率，可得到sim(fi，a，fi，b，Fj)的表達式：

其中：R(Fi=fi，a)表示在Fi取到特征fi，a的數據集合；|R(Fi=fi，a)|表示集合內的元素個數，即在Fi取到特征fi，a的數據條數。最后用特征fi，a和特征fi，b在所有域上的相似度的平均來表示特征fi，a和特征fi，b的相似度：

在共現概率相似度定義中，需要利用特征fi，b的出現次數|R(Fi=fi，b)|對相似度做歸一化，而在實際數據集中，某些特征的出現次數極高，會導致特征fi，a和這些特征的相似度值較小，因此該相似度傾向于其他出現次數較少的特征。為了讓出現次數較多的特征也能夠擁有較高的相似度，提出基于游走概率的特征相似度。相較于共現概率相似度，游走概率相似度的定義使用了不同的歸一化形式，特征fi，a和特征fi，b相對于域Fj的相似度可用式（9）表示：

游走概率相似度與共現概率相似度的區別在于相似度定義中的分母，此時分母不再是fi，b的出現次數，而是求和項中fj，k的出現次數。游走概率相似度本質是在記錄-特征二分圖上，從特征fi，a對應節點游走到特征fi，b對應節點上的概率。

3.2 域內特征相似性圖的構建

以上定義了不同的特征相似度，除了定義外，如何建立特征的相似性圖也是一個關鍵問題。將域內特征相似性圖定義為基于特征相似度的K 最近鄰（K-NearestNeighbor）圖，圖中的每個節點對應一個特征，每個特征和其特征相似度最高的K個特征存在連邊。

直接利用式（7）和式（8）計算特征fi，a和fi，b的相似度的時間復雜度為O(N)，表示所有域的特征總數，Ni表示域Fi內的特征總數，則計算特征fi，a的前K個最相似特征的時間復雜度為O(NNi)。以Criteo 數據集為例，N約為106，對于特征較多的域，Ni約為105，因此想通過兩兩計算相似度，然后取前K個特征的方法是不可行的。針對該問題，提出了高效建立域內特征相似性圖的算法，將特征的相似度計算問題描述為在記錄-特征二分圖上進行廣度優先遍歷的過程。記錄-特征二分圖如圖4（a）所示，左側的節點表示記錄編號，每個點表示一條記錄，右邊的每個點是一個離散特征，連邊表示該記錄取到這一特征。

廣度優先遍歷的具體過程如算法1 所示。現以計 算sim(fi，a，fi，b，Fj) ?fi，b∈Fi為例，說明該算法的 正確性。遍歷從fi，a在記錄-特征二分圖中對應的節點開始，進行第1 層遍歷，找到特征fi，a相鄰的記錄節點，如圖4（a）所示，節點的集合可以表示為R(Fi=fi，a)。然后進行第2 層遍歷，遍歷這些記錄節點在Fj內的近鄰，此時遍歷到域Fj內的特征節點，如圖4（b）所示。將特征節點為起點，通過遍歷，結束于另一個特征節點的跳轉過程為路徑，在遍歷后，每個特征節點應該存在大于等于零條路徑。對Fj內任意一個特征節點fj，x，其以fi，a為起點的路徑數為|R(Fi=fi，a&。進行第3 層遍歷，根據域Fj的特征節點找到其近鄰的節點，如圖4（c）所示，此時假設域Fj的特征節點是fj，x，其近鄰是記錄節點，可以表示為R(Fj=fj，x)。在進行第4 層遍歷時，根據第3 層得到的記錄節點找到其在域Fi內的近鄰，如圖4（d）所示。在進行第3 層和 第4 層遍歷時，以域Fj的特征fj，x為起點，結束于域Fi特征fi，b的路徑總數是R(Fj=fj，x&Fi=fi，b)，因此4 層遍歷從特征節點fi，a開始，經過特征節點fj，x傳播至特征節點fi，b的路徑總數是兩者的乘積，在整個遍歷過程中從特征節點fi，a經過域Fj傳播至特征節點fi，b的路徑總數是，此時即得到了式（7）中的分子，而分母可以簡單地統計得到，因此只需計算并存儲即可。而最終的傳播在多個域上進行，所以最終可以得到sim(fi，a，fi，b)。在進行廣度優先遍歷后，通過fi，a到fi，b的路徑數簡單地計算出了sim(fi，a，fi，b)，此時域Fi內所有特征都有相同的遍歷過程，因此在一次廣度優先遍歷后可以計算出fi，a與域內其他所有特征的相似度。

圖4 建網算法的遍歷過程Fig.4 Traversal process of network building algorithm

算法1域內特征相似性圖構建算法

將計算特征與域內其他特征的相似度描述成廣度優先遍歷具有以下優點：1）廣度優先遍歷無法遍歷到相似度為零的特征，避免了和相似度為零的特征的不必要的計算；2）若想獲得近似的前K個特征，只需要進行近似的廣度優先遍歷即可，即對每層的廣度優先遍歷進行剪枝，并不考慮所有近鄰節點，而是抽樣一定數量的近鄰節點，從而滿足時間和空間復雜度的要求。

在計算得到fi，a和域內其他特征的相似度后，取其中相似度最高的K個特征，在域內特征相似性圖中分別對fi，a和這些特征建立一條邊，完成域內特征相似性圖的構建。

以上是基于共現概率特征相似度建立域內特征相似度圖的過程，對于游走概率相似度，只需改變歸一化系數，將Num(fi，k)×Num(fi，*)改 為Num(fi，k)×Num(fj，*)即可。

4 實驗

本文實驗主要關注以下3 個問題：1）由于本文提出的模型可以用在任意的基于嵌入的模型上，因此在多個點擊率預估模型上進行了實驗，并且關注了不同相似度下點擊率預估的效果；2）嵌入生成器對不同的模型的運行時間的影響；3）在建圖算法中，進行廣度優先遍歷的采樣數對時間效率以及結果準確性的影響。

4.1 實驗設置

在2 個點擊率預估領域常用的公開真實數據集Criteo 和Avazu 上進行實驗。Criteo 是一個點擊率預測的基準數據集，有4 500 萬條用戶點擊記錄，它包含26 個離散域和13 個連續域。Avazu 數據集包含用戶的手機行為，包括顯示的手機廣告是否被用戶點擊，它有23 個域，從用戶/設備功能到廣告屬性，都是離散域。

4.1.1 評估指標

使用2 個在點擊率預估任務中最常用的評估指標來評價模型的表現。

1）AUC：AUC 指在ROC 曲線下的面積，AUC 用于衡量點擊率預估模型為一個隨機選擇的正樣本給出的預測值大于一個隨機選擇的負樣本的概率，更高的AUC 意味著更好的預測表現。

2）LogLoss：指式（6）表示的損失函數，因為所有的模型嘗試去最小化LogLoss，用它作為一個直接的評估指標。

4.1.2 基準模型

在多個主流的點擊率預估模型上加入嵌入生成器來證明模型的有效性。

FM：FM 利用了因子分解的技術建模二階的特征交互。

DeepFM：在FM 模型的基礎上加入了深度神經網絡，大幅提升了模型的效果。xDeepFM：利用CIN 和深度神經網絡的雙塔模型。Autoint：利用自注意力機制捕獲特征間的低階和高階交互關系。

Autoint*：在AutoInt 的基礎上加入了深度神經網絡來進一步提升模型效果。

4.1.3 參數設置

在Criteo 和Avazu 數據集上，嵌入生成器的注意力隱層分別為16 和32，其中Criteo 數據集分別在C3、C4、C12、C16、C21 這幾個特征個數較多的域上使用嵌入生成器，并且只對出現次數小于50 的特征的嵌入進行生成。在Avazu 數據集中，由于該數據集中的特征基本都在device_ip 域中，因此只對device_ip 域進行了嵌入生成，并且只對出現次數小于5 的特征的嵌入進行生成。

模型訓練的batch size、嵌入維度根據經驗取1 024和16，都用了adagrad 優化器對模型進行優化。

4.2 點擊率預估結果

表1 所示為在Criteo 數據集和Avazu 數據集上10 次實驗的平均結果，其中，某個模型后的加號表示在該模型的基礎上使用嵌入生成器，v1、v2 分別表示共現概率相似度和游走概率相似度。評估指標上表現更好的模型效果會被加粗。在點擊率預估領域，評估指標10-4級別的提升也是十分關鍵的。可以看出：1）在大部分模型上，使用嵌入生成器都提升了模型的預測效果；2）嵌入生成器對預測效果的提升相較于Avazu 數據集，在Criteo 數據集上更明顯；3）在大多數模型上，游走概率相似度取得了最好的效果。這是由于嵌入生成器針對的是出現次數較少的低頻特征，為這些特征生成新的嵌入表示。基于共現概率相似度的域內特征相似性圖中，低頻特征的相似特征同樣是低頻特征，嵌入同樣沒有得到較好的訓練，因此難以取得較好的效果。基于游走概率相似度的域內特征相似性圖中，低頻特征的相似特征是高頻特征，低頻特征能夠利用高頻特征的嵌入，生成一個具有更好表示能力的嵌入，因此在大多數模型上，游走概率相似度都取得了最好的表現。

表1 點擊率預測結果 Table 1 CTR predict results

4.3 復雜度分析

本節將展示不同模型加上嵌入生成器之后的訓練時間，由于不同模型訓練時的batch size 是相同的，利用每秒鐘訓練的batch 個數來衡量模型的訓練速度。在Avazu 數據集上的運行結果如圖5 所示。從圖5 可以看出：FM 模型的效率下降的最明顯，約為20%，而xDeepFM 模型效率下降的最少，這是因為xDeepFM 模型中的CIN 模塊的時間復雜度較高，影響了運行效率。可以從圖5 看出：加上嵌入生成器后模型的效率仍可以接受。

圖5 各模型運行效率Fig.5 Running efficiency of each models

4.4 建圖算法實驗

本節通過實驗對建圖算法進行分析，主要有以下2 個方面：

1）近似的建圖算法相較于準確的建圖算法的效率提升，以及在廣度優先傳播時選取的采樣數對建網效率的影響。

2）由于在廣度優先傳播中進行采樣，因此此時計算的前K個相似特征是近似結果，所以需分析采樣數對建圖算法準確程度的影響。

4.4.1 高效性

本節主要分析建圖算法的高效性，以在Criteo數據集的C4 域上建立相似性圖為例，取100 個特征，利用高效建圖算法分別在不同的廣度優先采樣數下計算前K個最相似的特征，記錄其花費的時間，如表2 和圖6 所示。

表2 不同計算方式運行時間 Table 2 Running time of different calculation methods 單位：s

圖6 建圖算法運行時間Fig.6 Running time of mapping algorithm

從表2 和圖6 可以看出：1）在采樣數小于100時，所花費的時間基本沒有變化，此時算法的時間主要是消耗在其他部分；2）在采樣數大于100后，所增加的花費時間約和采樣數成正比；3）不采樣的建圖算法的運行時間與采樣相比會大幅上升，通常是無法接受的。

4.4.2 準確性

通過2 個指標來評估建圖方法的準確性：1）該采樣數下獲得的近似前K個相似特征占準確的前K個相似特征的比例；2）該采樣數下獲得的近似前K個特征，每個特征的相似度在所有特征的相似度中所處的平均位置（例如處于前10%）。接下來詳細介紹這2 個指標的計算方式。

對于特征fi，k，其與域Fi內的其他特征fi，*的相似度可以 表示為sim(fi，k，fi，*)，將sim(fi，k，fi，*)fi，*∈Fi進行降序排序，記sim(fi，k，fi，*)在排序中的序號為orderfi，*，即fi，*是與fi，k第orderfi，*相似的特征，用set(fi，k)記錄與fi，k最相似的K個特征的集合。以上的結果是指通過不進行采樣的建圖算法獲得的準確結果，對于在廣度優先遍歷采樣數為n時，同樣可以計算出fi，k與其他特征fi，*的相似度，此時是近似值，同樣可以獲得與fi，k最相似的K個特征的集合，用setn(fi，k)來表示。第1 個指標可表示為；第 2 個指標可表示為，其中，Ni表示域Fi內特征的總數。

同樣以在Criteo 數據集的C4 域上建立相似性圖為例，取100 個特征，分別在不同的采樣數下運行建圖算法，計算以上2 個指標，并在100 個特征上計算指標的均值，結果如圖7 和圖8 所示。從圖中可以看出：在采樣數較小時（小于200），采樣數的上升會讓建圖算法的準確程度較快地提升，而采樣數較大以后（大于500），則提升較慢。綜合效率和準確率在實驗中建圖都采用200 的采樣數。

圖7 前K 個相似特征的平均排序位置Fig.7 Average ranking position of the top K similar features

圖8 前K 個相似特征的平均占比Fig.8 Average proportion of the top K similar features

5 結束語

特征的稀疏性問題普遍出現在大型的點擊率預估數據集中，造成特征嵌入學習不充分的問題。為解決該問題，本文提出了基于數據集的特征相似度定義以及建立域內特征相似度圖的算法，用于建模域內特征相似度，并設計了利用圖神經網絡在域內特征相似度圖上聚合相似特征嵌入信息的嵌入生成器，用于對出現次數較少的特征生成嵌入，緩解由于特征出現次數過少導致的特征嵌入學習不充分問題。實驗結果證實了嵌入生成器的有效性以及建網算法的高效性。本文運用特征的域內信息解決稀疏特征問題，未來可考慮使用域外特征的信息，引入更先進的圖神經網絡，以在域內相似性圖上更好地捕獲相似特征的信息。