基于Graph Embedding的湊單算法是什么

這篇文章主要講解了“基于Graph Embedding的湊單算法是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“基于Graph Embedding的湊單算法是什么”吧！

一、背景

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

??舉個例子來說，假設游走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），規避無監督模型無法離線評估模型效果的問題。模型結構如下圖。

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

graph的核心優勢，具有傳播能力，朋友的朋友，也是朋友，傳統i2i（統計版i2i）,只統計直接關系，而我們構建的共同購買的graph，可以通過游走挖掘多度關系，彌補購買行為稀疏的問題，有效的提升了覆蓋率，我們離線實驗發現，對比統計版本auc提升非常明顯。我們實現了實時大規模graph更新，每分鐘最高可更新10萬條邊，雙11這么大的qps能夠平穩運行。

感謝各位的閱讀，以上就是“基于Graph Embedding的湊單算法是什么”的內容了，經過本文的學習后，相信大家對基于Graph Embedding的湊單算法是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！