CIKM 2019 挑戰杯冠軍方案分享：「初篩-精排」兩階求解框架

• 2019 年 11 月 11 日
• 筆記

作者 | 楊鯉萍

編輯 | 唐里

近日，在中國北京舉辦 CIKM 2019 AnalytiCup 中，由來自浙江大學、中央財經大學、阿里巴巴等機構組成的團隊 WWG 摘得「用戶行為預測」賽道的桂冠。

CIKM 是中國計算機學會（CCF）推薦的數據庫/數據挖掘/內容檢索領域的 B 類會議。CIKM AnalytiCup 挑戰賽是會議同期舉行的國際數據挖掘比賽，今年由 CIKM、阿里媽媽、阿里巴巴算法大學、阿里雲天池共同承辦，挑戰賽分為兩個賽道，用戶興趣高效檢索（Efficient User Interests Retrieval）和用戶行為多樣性預測（Predicting User Behavior Diversities in A Dynamic Interactive Environment）。

我們將 WWG 團隊冠軍方案整理如下，希望能給開發者們一些經驗與啟發。（關於「用戶興趣高效檢索」賽道冠軍方案，我們也正在整理中，敬請期待~）

賽題簡介和分析

基本問題

根據歷史用戶-商品交互行為、用戶屬性和商品屬性，對給定用戶進行未來點擊預測，選出該用戶未來三天最可能點擊的商品 top50；其中，在複賽中需特別注意一點，即用戶歷史點擊商品並不在未來可能出現的點擊商品可選池中。

評估指標 Recall@50

其中為用戶在未來三天內的實際點擊商品集合，為用戶在未來三天內的預測點擊商品集合，此處需要注意，預測點擊商品集合的數量需滿足，即返回商品數量嚴格約束為 50 個。

簡要分析

僅僅看題目描述我們可以發現，這個題目本質上是一個召回預估問題。更具體的，這個問題應該以 u-i 對為輸入，經過一定模型的判斷，最終給出一個 u-i 對對應的分數，再根據每個 user 對應的 u-i 對分數從大到小的排序，取出 top50 的 item 作為最終得到預測點擊商品集合。

同時，考慮到規模問題，對於千萬級別的獨立 user 和 item，直接去做全集的 u-i 對預測顯然既不現實又不經濟，因此我們在結題初期就確定了「初篩-精排」兩階段求解框架，如圖 1 所示：

圖 1 「初篩-精排」兩階段求解框架

然而，這個題目的標題為用戶行為預測，在賽題官方的描述里也多次提到 Graph 的概念。從這一角度思考，這個問題可以描述為 u-i 二部圖的 link prediction 問題，雖然從模型的角度來看可能和剛剛說到的類似，但這一特點似乎在暗示圖結構信息在這一比賽當中的重要性。

因此，我們決定從兩個角度對此問題進行分析和求解：傳統的基於靜態屬性信息的統計特徵工程，以及基於 u-i 二部圖的結構特徵工程。

解題思路

統計特徵的提取在我們的工作中相對簡略，因此在本節中，我們着重介紹我們對圖結構特徵的思考和使用。

算法動機

為了可以預測用戶未來的點擊行為，我們需要對用戶和商品進行更為精準的刻畫和表達，由於本次賽題的主視角是用戶視角（用戶會點哪些商品），所以我們認為，解決 u-i 對預測問題的核心思想是：如何更好的表達用戶的偏好。即什麼樣的商品用戶會點擊，歷史的交互行為所傳達出來的哪些信息對未來點擊的預測是有效的。

通過對用戶的行為進行思考和分析，我們發現用戶的偏好存在如下兩類的關係：

• 如果一名用戶點擊了某個商品，那麼該用戶對該商品所在類目的商品具有一定程度的偏好，如：iPhone，Mate 30->MI MIX Alpha（智能手機類目）；
• 如果一名用戶點擊了某個商品，那麼該用戶對該商品所在主題的商品具有一定程度的偏好，如：沙灘褲，太陽眼鏡->防晒霜（沙灘旅行主題）。

層次關係

更深入的，我們發現這兩類關係存在相對明晰的層次關係，如：

• 基於類目的層次偏好：iPhone，Mate 30->MI MIX Alpha（智能手機）->Canon EOS 相機（電子產品）；
• 基於用戶興趣主題的層次偏好：沙灘褲，太陽眼鏡->防晒霜（沙灘旅行）->運動鞋（戶外旅行）。這裡的沙灘旅行和戶外旅行都是用戶興趣層面的表達。

這兩類偏好關係廣泛存在與用戶的歷史行為中，具體如圖 2 所示；因此，如何合理捕捉這兩類層次特徵，是我們接下來算法的重點。

圖 2 層次偏好特徵表達示意圖

解決方案

在接下來的算法中，我們將基於類目的層次偏好稱為顯式層次偏好，將基於用戶興趣主題的層次偏好稱為隱式層次偏好。我們的解決方案一共包含以下四部分：

圖 3 解決方案大綱

數據預處理

由於數據集本身是存在不同日期，不同交互行為（點擊，購買，加購，收藏）的，我們首先通過引入時間衰減因子和行為衰減因子兩個超參數，對原始數據集進行處理，並構建完成 user-item 二部圖（如圖 4）。

與此同時，也根據 user 特徵數據集和 item 特徵數據集構建一系列統計特徵，以及 user 和 item 的屬性特徵。

圖 4 user-item 二部圖

顯式層次特徵提取

顯式層次特徵主要基於 item-cate-cate1 的層次關係，通過將歷史行為與 item 特徵進行匹配，可以分別構建出 user-item，user-cate，user-cate1 三張二部圖，對三個層次分別實現協同過濾算法，從而得出 user 對不同 item，不同 cate 以及不同 cate1 的相似性得分。我們可以看到顯性的層次特徵是只有 item 維度的。

圖 5 顯性層次特徵提取

隱式層次特徵提取

隱式層次特徵的提取相對困難，因為興趣主題並不像類目一樣，每個商品並沒有被標定一個顯式的興趣主題。為了比較好的解決這一問題，我們提出 Hierarchical Graph Neural Network（HGNN）算法，對圖結構進行表達。

具體的，我們對原始的 u-i 二部圖做 GraphSAGE 算法，以具有邊的 user，item 的向量表達相似（餘弦相似度）為目標（注意，這裡嚴格意義上應該區分兩個向量空間，在比賽中我們為了提高效率將兩個向量空間的維度設定成了相同的 16 維，因此可以實現餘弦相似度的計算），做無監督的 Graph Embedding 訓練。待網絡穩定後，我們可以得到每個 user 和 item 的向量表達。這一向量即為該 user/item 的一級隱式特徵。

為了表達出層次特性，我們根據 user/item 的一級隱式特徵，分別在 user 和 item 的向量空間中做聚類（比賽中採用 K-means 聚類），以聚類簇的平均特徵向量作為簇節點的向量，以簇間原始節點關聯關係的統計作為簇與簇之間的關聯（邊）。這樣，我們便通過聚類操作，將原始 u-i 二部圖粗化，變為了一個以主題用戶簇和主題商品簇為節點，節點數量更少的粗化圖。對粗化圖做和原始 u-i 二部圖相同基於 GraphSAGE 的 Graph Embedding 操作，我們便可以得到粗化隱式特徵，原始節點的二級隱式特徵即為其所屬簇的粗化隱式特徵。

對於每個 user/item，將其一級隱式特徵和二級隱式特徵級聯，即得到該節點的隱式層次特徵。在實際計算 u-i 對相似度時，將層次隱式特徵分級比較即可得到這一部分的相似分。我們可以看到隱性層次特徵是既有 user 維度，也有 item 維度的。

圖 5 隱性層次特徵提取

排序模型

在 Candidate Generation 階段（初篩階段），我們採用計算效率相對較高的顯式層次特徵（即採用協同過濾分）對所有商品進行初篩，對每個 user，保留其最有可能點擊的 2000 個商品進行 Ranking 階段的精排。需要注意的是，在初賽中歷史商品也可能在未來曝光並被點擊，所以歷史商品無需特殊處理。而複賽階段由於歷史商品不會在未來曝光，所以複賽階段在初篩階段的結尾要對歷史出現過的商品做篩除，以避免無效精排。

Ranking 階段基本上每個 user 要處理 2000 個左右的商品，因此我們的預測模型選擇了相對簡單高效的 LR 模型，將前置工作中得到的顯式層次特徵，隱式層次特徵和統計特徵進行不同階的特徵交叉後引入 LR 模型後，將 LR 模型的輸出作為排序分數, 取分數 top50 作為最終的預測結果進行輸出。

這裡交叉特徵的引入本質是一個 kernel 函數的思想, 輔助提高了 LR 模型的非線性能力，我們先後採用了顯性層次特徵和隱性層次特徵之間 2 階的特徵交叉以及 3 階特徵交叉; 分別對最後的模型效果有一定提升。

圖 6 排序模型圖

成果展示

以下是我們算法迭代過程中的一些重要節點：

• version1 基於協同過濾+統計特徵
• version2 基於顯性層次特徵+統計特徵
• version3 基於顯性/隱形層次特徵+統計特徵
• version4 基於二階結構特徵交叉+統計特徵
• version5 基於三階結構特徵交叉+統計特徵

圖 7 重要節點示意圖

可以發現，通過引入層次結構特徵，尤其是隱式層次結構特徵的提取，我們對這一問題進行了較好的求解，從結論上可以看出，結構特徵確實對整個預測準確度帶來了較大的性能提升，後續對結構特徵信息做了特徵交叉之後，性能也有了進一步的提高。

總結及未來計劃

本次比賽我們嘗試了 Hierarchical GNN 模型來獲取用戶和商品的隱性層次特徵，獲得了非常不錯的效果，由於比賽時間非常有限，我們的排序模型使用了 LR, 以便於快速迭代並調整相應參數，使用了 point-wise 的訓練方式。

如果還有足夠的時間，我們還會嘗試更多的排序模型，比如 xgboost, deepFM, wide&deep 等，並對模型做相應的融合，再採樣 pair-wise 的訓練方式，相信還會進一步提升模型效果。

圖 8 冠軍獲獎合影

關於冠軍團隊

本次冠軍團隊 WWG 的兩位學生成員——孟憲令和焦宇航在阿里巴巴算法團隊實習期間，參與了該比賽；比賽過程中，團隊負責人李朝博士，以及兩位師兄潘旭明和鄒朋成在算法的創新和思路上給予了一定的輔導。

更多信息請參考大賽官網：

https://tianchi.aliyun.com/markets/tianchi/cikm19_en_copy?spm=a2c22.265802.1380778.2.4cdb2b2cFZlc5l&wh_ttid=pc