阿里湊單演算法首次公開！基於Graph Embedding的打包購商品挖掘系統解析

摘要： 本文描述如何在湊單場景突破找相似、發現驚喜的同時做到成交翻倍，實現體驗和數據上的雙贏。

原文：http://click.aliyun.com/m/41564/

一、背景

湊單作為購物券導購鏈路的一個重要環節，旨在幫助用戶找到商品，達成某個滿減門檻（比如滿400減50），完成跨店湊單，完善購物券整個鏈路的體驗。滿減購物券作為大促中使用最廣泛的一種營銷手段，優勢遠大於紅包、商品打折等優惠活動，它不僅能給用戶帶來切實的優惠，而且能讓用戶買的更多，提升客單價。湊單作為用券的重要鏈路，旨在幫助消費者找到能使用同門檻優惠券的商品。

今年湊單相比往年，有兩個重大突破，首先是產品形態上的改變，往年，湊單只是一個商品推薦頁，今年，湊單能夠支持搜索、價格篩選、類目篩選、銷量排序、價格排序等搜索功能。其次，演算法上做了重大突破，基於Graph Embedding的bundle mining，bundle是打包購的意思，我們認為湊單的重要場景是當用戶已經加購了商品A，還想找一個能一起打包買的商品B，而不是想找跟A相似的商品C，傳統的u2i、相似i2i並不能滿足湊單場景的需求，為了突破找相似等經常被人詬病的體驗，我們甚至不能有u2i、相似i2i等邏輯，所以bundle mining變成湊單演算法優化的重點，不僅能提升豐富性的體驗，還能提升轉化效率。

二、核心演算法

1、基本思路

圖是一種抽象程度高、表達能力強的數據結構，它通過對節點和邊的定義來描述實體和實體之間的關聯關係。常用的圖有社交關係網路、商品網路、知識圖譜等等。

用戶行為是一個天然的網路圖，邊和節點往往有著各種豐富的信息，graph embedding是學習節點隱表示向量，在一個連續向量空間中對節點的關聯關係進行編碼，便於計算節點之間的關聯關係，同時，graph具有傳播能力，通過random walk可以挖掘多度關係，能有效的提升覆蓋度，擴大召回。

Graph Embedding是學術界一個重要研究方向，比如deep walk，是語言模型和無監督學習從單詞序列擴展到圖結構上的一個典型方法，該方法將截斷遊走的序列當成句子進行學習，之後採用word2vec中Skip-Gram模型進行訓練，得到每個節點的embedding向量。Line只針對邊進行採樣，Node2vec可以調節參數來進行BFS或者DFS的抽樣。

所以Graph Embedding的基本思路是，對graph進行採樣（Sampling），采出來的序構建模型（Embedding）。

2、主要技術

結合我們的場景，要挖掘共同購買的關係，直接通過item-item的關係挖掘也可以做到，傳統的協同過濾，也可以做到，為什麼我們還需要構建graph？因為graph具有傳播能力，它不僅能有效的提取出來直接關聯，而且可以通過遊走策略，挖掘出來二度、三度的關係。我們認為，朋友的朋友，也是朋友，也存在一定的弱關聯，有效的利用這種傳播能力，能解決購買數據的稀疏性，大大的提升覆蓋。

我們主要有三方面的工作，一是，基於用戶購買行為構建graph，節點：商品，邊：商品間同時購買的行為，權重：同時購買的比重，可以是購買次數、購買時間、金額等feature；二是，基於權重Sampling（weighted walk）作為正樣本的候選，負樣本從用戶非購買行為中隨機抽樣；三是，embedding部分將無監督模型升級成有監督模型，將基於weighted walk采出來的序，構造成item-item的pair對，送給有監督模型（DNN）訓練。下圖是演算法框架圖。

a) 構建Graph

上文提到，我們要挖掘商品間共同購買的關係（bundle mining），類似買了又買的問題，所以，我們構建的graph是帶權重的商品網路，節點：商品，邊：商品間共同購買的關係，權重：共同購買次數、購買時間。

為什麼需要帶權重的Graph？因為random walk等傳統方法不適用商品網路，商品節點動輒上千萬，其中大部分節點的關聯性是很弱的，也就是冷門商品居多，只有少部分商品構建的graph是熱點，如果採用random walk去採樣，會采出很多冷門節點的序列，所以我們基於邊的權重去採樣（weighted walk），使採樣盡量往熱門節點方向遊走，這樣採樣出來的樣本置信度才更高。

因此，我們的輸入是一個帶weight的graph ，Graph定義：G = （V，E，W），V = vertex （頂點或者節點，在bundle的問題中，特指商品），E = edge（邊，在bundle的問題中，特指共同購買） ，W = weight（邊的權重，共同購買的次數、時間），如下圖，接下來就要進行sampling。

b）Sampling

傳統的方法，比如deep walk，它的Sampling本質上是有兩部分，首先，通過random walk的方式進行遊走截斷，其次，在仍給word2vec中Skip-Gram模型進行embedding之前，用negative sampling的方式去構造樣本；這種隨機採樣的方法會大概率的將熱門節點採集為負樣本，這種方式適用於語言模型，因為在自然語言中，熱門的單詞均為無用單詞（比如he、she、it、is、the）。對於我們的商品網路，剛好相反，熱門商品往往是最重要的樣本，如果採用negative sampling的方式去構造樣本，模型肯定是學不出來。因此，我們基於邊的權重去採樣（weighted walk），使採樣盡量往熱門節點方向遊走，以下圖為例：

舉個例子來說，假設遊走2步，從節點A出發，隨機取下一個鄰居節點時，如果是random walk演算法，它會等概率的遊走到B或C節點，但是我們的演算法會以7/8的概率取節點C，再會以8/12的概率遊走到節點D，最終很大概率上會采出來一條序walk=（A，C，D）walk=（A，C，D），對於原始graph，A和D是沒有關聯的，但是通過weighted walk，能夠有效的挖掘出A和D的關係，演算法詳見：

Algorithm 1 Weigted Walk(G,n,WalksG,n,Walks)

Input: Graph G(V,E,W)G(V,E,W)

Step nn

Output: walkwalk

Initialization: walkwalk to empty

For each vivi ∈∈ VV do

Append vivi to walkwalk

For j=1...nj=1...n do

vj=GetNeighbor(G,vi)vj=GetNeighbor(G,vi)

Append vjvj to walkwalk

Return walkwalk

Algorithm 2 GetNeighbor(G,vi)GetNeighbor(G,vi)

Input: Graph G(V,E,W)G(V,E,W)

Node vivi

Output: next node vjvj vj=WeightedSample(vi,w)vj=WeightedSample(vi,w)

演算法實現是在odps graph平台實現的，一個分散式的圖計算平台，離線graph有2億條邊，3千萬節點，10分鐘跑完所有的數據，實時部分，我們實現了每分鐘最高可更新10w的Graph邊的結構，如何在分散式odps graph平台實現這套演算法詳見另一篇ata，盡請期待

c）Embedding

上一部分介紹了如何構建了帶權重的概率圖，基於帶權重的採樣（weighted walk）作為正樣本的候選，負樣本從用戶非購買行為中隨機抽樣；這一部分主要介紹embedding的部分，將基於weighted walk采出來的序，構造成item-item的pair對，送給embedding模型，我們構造了一個有監督embedding模型（DNN），規避無監督模型無法離線評估模型效果的問題。模型結構如下圖。

有監督的embedding環節做了許多迭代優化，詳見另一篇ata：基於DNN的多目標、多通道的bundle演算法。

三、實現

1、離線

a）訓練：離線模型在PAI平台上用tensorflow框架實現，抽取了歷史50天的全網成交數據，大概抽取3000萬節點，構建的graph，在odps graph平台做完weighted walk，產出2億條樣本，也就是item-item的pair對，訓練至收斂需要2小時的時間

b）預測：從全網所有行為中，隨機抽取幾十億條pair對，去做預測，給每對item pair預測一個score

c）上線：對每個種子商品取topN的bundle商品，打到搜索引擎的倒排和正排欄位，從qp中取出每個用戶的種子商品，基於倒排欄位召回bundle商品，基於正排欄位做bundle排序

2、實時

用戶購買行為，日常和大促差異很大，為了能夠實時的捕獲用戶實時行為，我們在porsche上建了一套實時計算bundle mining的流程：

a）數據預處理：在porsche上對用戶實時日誌進行收集，按離線的數據格式處理成實時的數據流

b）Sampling：發送給odps graph實時計算平台，構建graph，做weighted walk，生成序，再通過swift消息發出

c）Embedding：在porsche上做DNN模型訓練和實時預測

d）數據後處理：計算item的topN的bundle item list，實時寫到dump和引擎

四、實驗和結果

雙十一預熱期間，我們將bundle演算法上線對比基準桶，提升很明顯

1、點擊：離線版bundle演算法對比基準桶，ipv提升13%，實時版bundle演算法在此基礎上又提升4%，如下圖：

2、豐富性：bundle演算法對比基準桶，人均曝光葉子類目提升88%，人均曝光一級類目提升43%，如下圖。

五、總結

graph的核心優勢，具有傳播能力，朋友的朋友，也是朋友，傳統i2i（統計版i2i）,只統計直接關係，而我們構建的共同購買的graph，可以通過遊走挖掘多度關係，彌補購買行為稀疏的問題，有效的提升了覆蓋率，我們離線實驗發現，對比統計版本auc提升非常明顯。

我們實現了實時大規模graph更新，每分鐘最高可更新10萬條邊，雙11這麼大的qps能夠平穩運行。

六、未來和展望

湊單在未來還要繼續努力，我們還有不完善的地方，在產品形態上，第一，價格preview沒有做出來，用戶不知道自己已經加購了多少，還差多少，能用多少優惠券，我們希望下次能在湊單頁幫用戶實時的算出湊單進度，第二，我們這次沒有實時捕捉到入口種子商品，下次我們期望能做到，不同入口點進去，湊單的商品能和入口種子商品強相關；在演算法優化上，把新穎性做強，嘗試用graph bandit的方法，給用戶投放一些沒看過的但又相關的品類，根據投放的收益，設計一個合理的機制去explore。

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎

推薦閱讀：