阿里妹導讀：你是否也曾遇到類似的情況——差5塊錢就能包郵，跨店滿400減50就少20怎么辦？湊單作為購物券導購鏈路的一個重要環節，旨在幫助你找到合適的商品。如何在湊單場景突破找相似、發現驚喜的同時做到成交翻倍，實現體驗和數據上的雙贏？今天我們一起來破解。

一、背景
湊單作為購物券導購鏈路的一個重要環節，旨在幫助用戶找到商品，達成某個滿減門檻（比如滿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。

商品graph

b）Sampling

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

帶權重的商品graph

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

算法實現是在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模型（DNN）

三、實現
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。

總結

以上是生活随笔為你收集整理的阿里凑单算法首次公开！打包购商品挖掘系统解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。