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

（1.北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044；2.北京交通大學(xué) 網(wǎng)絡(luò)科學(xué)與智能系統(tǒng)研究所，北京 100044；3.中國民航信息網(wǎng)絡(luò)股份有限公司，北京 101318；4.民航旅客服務(wù)智能化應(yīng)用技術(shù)重點實驗室，北京 101318）

0 概述

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

早期使用線性模型建模點擊概率，為每個特征分配一個可學(xué)習(xí)的權(quán)重，但該方法無法建模特征間的交互關(guān)系。因子分解機（Factorization Machine，F(xiàn)M）［3］為每個特征分配了一個低維的稠密向量即嵌入［4］，通過兩個向量的內(nèi)積建模特征間的交互關(guān)系，此后多數(shù)點擊率預(yù)模型采用了為每個特征分配一個嵌入的做法，區(qū)別在于如何利用特征的嵌入建立特征交互。

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

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

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

1 相關(guān)工作

1.1 點擊率預(yù)估

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

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

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

1.2 稀疏特征問題

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

圖1 Criteo 數(shù)據(jù)集中C3 和C4 域中特征出現(xiàn)次數(shù)分布Fig.1 Feature occurrence frequency distribution in C3 and C4 domains in Criteo data set

1.3 點擊率預(yù)估模型

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

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

1.4 圖神經(jīng)網(wǎng)絡(luò)

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

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

2 基于域內(nèi)特征相似度的嵌入生成模型

2.1 模型框架

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

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

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

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

2.2 模型輸出和訓(xùn)練

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

模型訓(xùn)練使用常用的交叉熵作為損失函數(shù)，定義如下：

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

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

3 特征相似性圖構(gòu)建方法

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

3.1 特征相似度的定義

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

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

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

游走概率相似度與共現(xiàn)概率相似度的區(qū)別在于相似度定義中的分母，此時分母不再是fi，b的出現(xiàn)次數(shù)，而是求和項中fj，k的出現(xiàn)次數(shù)。游走概率相似度本質(zhì)是在記錄-特征二分圖上，從特征fi，a對應(yīng)節(jié)點游走到特征fi，b對應(yīng)節(jié)點上的概率。

3.2 域內(nèi)特征相似性圖的構(gòu)建

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

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

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

圖4 建網(wǎng)算法的遍歷過程Fig.4 Traversal process of network building algorithm

算法1域內(nèi)特征相似性圖構(gòu)建算法

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

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

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

4 實驗

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

4.1 實驗設(shè)置

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

4.1.1 評估指標

使用2 個在點擊率預(yù)估任務(wù)中最常用的評估指標來評價模型的表現(xiàn)。

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

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

4.1.2 基準模型

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

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

DeepFM：在FM 模型的基礎(chǔ)上加入了深度神經(jīng)網(wǎng)絡(luò)，大幅提升了模型的效果。xDeepFM：利用CIN 和深度神經(jīng)網(wǎng)絡(luò)的雙塔模型。Autoint：利用自注意力機制捕獲特征間的低階和高階交互關(guān)系。

Autoint*：在AutoInt 的基礎(chǔ)上加入了深度神經(jīng)網(wǎng)絡(luò)來進一步提升模型效果。

4.1.3 參數(shù)設(shè)置

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

模型訓(xùn)練的batch size、嵌入維度根據(jù)經(jīng)驗取1 024和16，都用了adagrad 優(yōu)化器對模型進行優(yōu)化。

4.2 點擊率預(yù)估結(jié)果

表1 所示為在Criteo 數(shù)據(jù)集和Avazu 數(shù)據(jù)集上10 次實驗的平均結(jié)果，其中，某個模型后的加號表示在該模型的基礎(chǔ)上使用嵌入生成器，v1、v2 分別表示共現(xiàn)概率相似度和游走概率相似度。評估指標上表現(xiàn)更好的模型效果會被加粗。在點擊率預(yù)估領(lǐng)域，評估指標10-4級別的提升也是十分關(guān)鍵的?？梢钥闯觯?）在大部分模型上，使用嵌入生成器都提升了模型的預(yù)測效果；2）嵌入生成器對預(yù)測效果的提升相較于Avazu 數(shù)據(jù)集，在Criteo 數(shù)據(jù)集上更明顯；3）在大多數(shù)模型上，游走概率相似度取得了最好的效果。這是由于嵌入生成器針對的是出現(xiàn)次數(shù)較少的低頻特征，為這些特征生成新的嵌入表示?；诠铂F(xiàn)概率相似度的域內(nèi)特征相似性圖中，低頻特征的相似特征同樣是低頻特征，嵌入同樣沒有得到較好的訓(xùn)練，因此難以取得較好的效果?；谟巫吒怕氏嗨贫鹊挠騼?nèi)特征相似性圖中，低頻特征的相似特征是高頻特征，低頻特征能夠利用高頻特征的嵌入，生成一個具有更好表示能力的嵌入，因此在大多數(shù)模型上，游走概率相似度都取得了最好的表現(xiàn)。

表1 點擊率預(yù)測結(jié)果 Table 1 CTR predict results

4.3 復(fù)雜度分析

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

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

4.4 建圖算法實驗

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

1）近似的建圖算法相較于準確的建圖算法的效率提升，以及在廣度優(yōu)先傳播時選取的采樣數(shù)對建網(wǎng)效率的影響。

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

4.4.1 高效性

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

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

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

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

4.4.2 準確性

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

對于特征fi，k，其與域Fi內(nèi)的其他特征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個特征的集合。以上的結(jié)果是指通過不進行采樣的建圖算法獲得的準確結(jié)果，對于在廣度優(yōu)先遍歷采樣數(shù)為n時，同樣可以計算出fi，k與其他特征fi，*的相似度，此時是近似值，同樣可以獲得與fi，k最相似的K個特征的集合，用setn(fi，k)來表示。第1 個指標可表示為；第 2 個指標可表示為，其中，Ni表示域Fi內(nèi)特征的總數(shù)。

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

圖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 結(jié)束語

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