數據挖掘：推薦系統綜述以及美團推薦系統介紹

文 | 宿痕
來源 | 知乎
其實推薦系統前面已經講過不少，那時候主要是放在機器學習上講的，既然這次要系統擼一遍數據挖掘，就把推薦系統單獨拿出來說一說。相信如果做過推薦系統的人，都知道是什么回事。一堆features，一堆算法模型，一堆online、offline規則和計算，還有若干的場景。包括著名的netflix、Amazon做的推薦場景都有哪些，有哪些坑需要注意的，之前都有說過。
像阿里還時不時會搞搞天池算法大賽，像最近在弄一個簡歷篩選推薦算法競賽，有興趣的小伙伴都可以去參與了解下。拿些數據來練練，對自己經驗的積累還是挺有好處的。
LZ最近也是在接觸量化投資，通過機器學習的方式來預測股價走勢以及買入賣出等，還是比較有意思啊，如果有做這塊的可以私下交流，當然知道做這塊的相對來說都比較保守，畢竟策略、思想等東西都是比較寶貴。
閑話不多說，今天既然說到推薦系統概述，重點會推薦的場景、推薦的算法、推薦的架構以及美團的推薦算法都是怎么做的講下。
前面介紹的推薦的場景、算法介紹更適合剛入門的同學了解，已經在這塊領域馳騁疆場的老鳥可以直接跳步到后面的架構和美團案例上了。
推薦系統為何物？
先說個事實，為什么需要有推薦系統這個東西？
當我們在龐大的一間圖書館里想找我們要看的一本書時；
當我們在沃爾瑪超市想買個清潔劑時；
當我們想在淘寶上搜個價格合適、質量又不錯的衣服時；
當海量的垃圾郵件和廣告不斷充斥著你的郵箱時；
當我們的信息嚴重過載時，我們已經沒辦法通過人的肉眼來篩選了。

沒錯，就是像樓上這哥兒們這樣，我們已經茫然了?。犎∧承┩瑢W的意見，要求多放些圖片O(∩_∩)O）
所以應運而生，出現了如Amazon的商品推薦

而據說Amazon的推薦系統給他們帶來35%的銷售！
還有像YouTube

netflix

天貓

google

這些案例不計其數，本質上他們都解決了幾個問題：
用戶的信息過載；
更精準的個性化推薦和營銷；
減少資源的浪費和最大化收益。因而推薦系統其實更多的是解決的資源分配的問題，當然從用戶的角度來說是解決的信息篩選的成本問題。
不可避免推薦系統就把人、產品、數據這些都捆綁在一起。
而人、產品都是復雜的，怎么能夠通過推薦系統來實現量化呢？自然而然的就考慮到“人以類聚、物以群分”的feature。
這些feature的選擇是個開放的話題，主要是圍繞人的基本屬性、社會關系、金融資產、地理位置、信用歷史、行為偏好等維度去考慮。

一句話就是能把這個人的吃喝拉撒、從什么時候出生到活到多少歲、他們平時都接觸什么人、都在哪里活動、都做些什么事情都知道了。是不是想象就比較可怕，這樣作為個人還有隱私可言嗎？沒錯，數據安全、個人隱私問題是數據方面的一個重大話題。

而推薦作為機器學習中很重要的一個部分，它所解決的就是把這個人的過去歷史行為、用戶間的relation、item相似度、用戶的個人信息、item特征等信息綜合起來去打分，來評估預測這個用戶對于這個item的喜好程度。LR相比較DT的好處就是能圍繞最終result會有個probability。
推薦算法
常見的推薦算法有這些：

具體的算法公式我就不列了，講了可能會有人會看睡著。
CF遇到的問題就是1.冷啟動，沒數據的時候比較尷尬，本身需要大量的可信用戶數據來訓練；2.數據稀疏的情況，；3.數據分布的問題，長尾部分相似度計算不準確。這里常用的model有聚類、分類、回歸、SVD等等。
CB主要是基于內容的推薦，比如文本內容、圖片、音頻等方面的推薦，優點就是沒有上面說到的冷啟動問題，可以給小眾的用戶推薦內容，但是難點就是在實際業務中沒有太大的效果。這種比較適合在數據特征比較豐富的情況下做。比如像觀看的視頻，圍繞導演、時長、粉絲等各種方面來training。
推薦架構
涉及到推薦架構方面，能說的就特別多了。本身因為到了架構這層就和實際情況結合了，包括計算性能、成本、實時性、評估效果、用戶體驗等很多方面的問題。
之前整理了個推薦系統的基本平臺架構，大體的內容有這些：

像在系統推薦平臺邏輯大體上有這些：

包括你看到的netflix、Amazon大體的架構也是這樣分布，特別要強調的是當你的ML模型最終目標是在生產環節有重要影響，你有必要得思考正確的系統架構。
在延時和復雜性之間權衡很重要，一些計算需要實時，盡快響應給用戶反饋，另外復雜的ML模型需要大量數據，需要長時間才能計算好，還有一些近乎在線NearLine，操作不保證實時發生，但是最好盡可能快地執行。
這方面阿里云是比較強悍，技術杠桿的，在雙十一這種場景里是大展拳腳。
美團的推薦系統
美團在線上線下O2O做的產品體驗的確是不錯，他們的技術分享也比較勤快。所以有很多地方還是值得我們去學習的吧。特別是美團在線上線下這塊應該有不少用戶數據和行為數據可以來做分析。也真的希望他們能夠有時間來線下多搞些活動分享分享。
美團推薦框架

從框架的角度看，推薦系統基本可以分為數據層、觸發層、融合過濾層和排序層。數據層包括數據生成和數據存儲，主要是利用各種數據處理工具對原始日志進行清洗，處理成格式化的數據，落地到不同類型的存儲系統中，供下游的算法和模型使用。候選集觸發層主要是從用戶的歷史行為、實時行為、地理位置等角度利用各種觸發策略產生推薦的候選集。候選集融合和過濾層有兩個功能，一是對出發層產生的不同候選集進行融合，提高推薦策略的覆蓋度和精度；另外還要承擔一定的過濾職責，從產品、運營的角度確定一些人工規則，過濾掉不符合條件的item。排序層主要是利用機器學習的模型對觸發層篩選出來的候選集進行重排序。
同時，對與候選集觸發和重排序兩層而言，為了效果迭代是需要頻繁修改的兩層，因此需要支持ABtest。為了支持高效率的迭代，對候選集觸發和重排序兩層進行了解耦，這兩層的結果是正交的，因此可以分別進行對比試驗，不會相互影響。同時在每一層的內部，會根據用戶將流量劃分為多份，支持多個策略同時在線對比。
數據feature
像數據feature大概有這些：

數據描述：
用戶主動行為數據記錄了用戶在美團平臺上不同的環各種行為，這些行為一方面用于候選集觸發算法（在下一部分介紹）中的離線計算（主要是瀏覽、下單），另外一方面，這些行為代表的意圖的強弱不同，因此在訓練重排序模型時可以針對不同的行為設定不同的回歸目標值，以更細地刻畫用戶的行為強弱程度。此外，用戶對deal的這些行為還可以作為重排序模型的交叉特征，用于模型的離線訓練和在線預測。
負反饋數據反映了當前的結果可能在某些方面不能滿足用戶的需求，因此在后續的候選集觸發過程中需要考慮對特定的因素進行過濾或者降權，降低負面因素再次出現的幾率，提高用戶體驗；同時在重排序的模型訓練中，負反饋數據可以作為不可多得的負例參與模型訓練，這些負例要比那些展示后未點擊、未下單的樣本顯著的多。
用戶畫像是刻畫用戶屬性的基礎數據，其中有些是直接獲取的原始數據，有些是經過挖掘的二次加工數據，這些屬性一方面可以用于候選集觸發過程中對deal進行加權或降權，另外一方面可以作為重排序模型中的用戶維度特征。
通過對UGC數據的挖掘可以提取出一些關鍵詞，然后使用這些關鍵詞給deal打標簽，用于deal的個性化展示。
策略
策略方面主要是架構中得CF、LB、QB、GB、替補策略這些。
1.CF
CF是推薦這塊應用的比較廣的算法了，很簡單但是要用好要看具體的場景問題。
清除作弊、刷單、代購等噪聲數據。這些數據的存在會嚴重影響算法的效果，因此要在第一步的數據清洗中就將這些數據剔除。
合理選取訓練數據。選取的訓練數據的時間窗口不宜過長，當然也不能過短。具體的窗口期數值需要經過多次的實驗來確定。同時可以考慮引入時間衰減，因為近期的用戶行為更能反映用戶接下來的行為動作。
user-based與item-based相結合。

嘗試不同的相似度計算方法。在實踐中，我們采用了一種稱作loglikelihood ratio[1]的相似度計算方法。在mahout中，loglikelihood ratio也作為一種相似度計算方法被采用。
下表表示了Event A和Event B之間的相互關系，其中：
k11 ：Event A和Event B共現的次數
k12 ：Event B發生，Event A未發生的次數
k21 ：Event A發生，Event B未發生的次數
k22 ：Event A和Event B都不發生的次數
Event AEverything but AEvent BA and B together (k_11)B， but not A (k_12)Everything but BA without B (k_21)Neither A nor B (k_22)
則logLikelihoodRatio=2 * (matrixEntropy - rowEntropy - columnEntropy)
其中
rowEntropy = entropy(k11， k12) + entropy(k21， k22)
columnEntropy = entropy(k11， k21) + entropy(k12， k22)
matrixEntropy = entropy(k11， k12， k21， k22)(entropy為幾個元素組成的系統的香農熵)
2.LB
對于移動設備而言，與PC端最大的區別之一是移動設備的位置是經常發生變化的。不同的地理位置反映了不同的用戶場景，在具體的業務中可以充分利用用戶所處的地理位置。在推薦的候選集觸發中，我們也會根據用戶的實時地理位置、工作地、居住地等地理位置觸發相應的策略。
根據用戶的歷史消費、歷史瀏覽等，挖掘出某一粒度的區域（比如商圈）內的區域消費熱單和區域購買熱單
區域消費熱單
區域購買熱單

當新的線上用戶請求到達時，根據用戶的幾個地理位置對相應地理位置的區域消費熱單和區域購買熱單進行加權，最終得到一個推薦列表。
此外，還可以根據用戶出現的地理位置，采用協同過濾的方式計算用戶的相似度。
3. QB
搜索是一種強用戶意圖，比較明確的反應了用戶的意愿，但是在很多情況下，因為各種各樣的原因，沒有形成最終的轉換。盡管如此，這種情景還是代表了一定的用戶意愿，可以加以利用。具體做法如下：
對用戶過去一段時間的搜索無轉換行為進行挖掘，計算每一個用戶對不同query的權重。

計算每個query下不同deal的權重。

當用戶再次請求時，根據用戶對不同query的權重及query下不同deal的權重進行加權，取出權重最大的TopN進行推薦。
4. GB
對于協同過濾而言，user之間或者deal之間的圖距離是兩跳，對于更遠距離的關系則不能考慮在內。而圖算法可以打破這一限制，將user與deal的關系視作一個二部圖，相互間的關系可以在圖上傳播。simrank： a measure of structural-context similarity是一種衡量對等實體相似度的圖算法。它的基本思想是，如果兩個實體與另外的相似實體有相關關系，那它們也是相似的，即相似性是可以傳播的。

5. 實時用戶行為
目前美團的業務會產生包括搜索、篩選、收藏、瀏覽、下單等豐富的用戶行為，這些是進行效果優化的重要基礎。推薦當然希望每一個用戶行為流都能到達轉化的環節，但是事實上遠非這樣。
當用戶產生了下單行為上游的某些行為時，會有相當一部分因為各種原因使行為流沒有形成轉化。但是，用戶的這些上游行為是非常重要的先驗知識。很多情況下，用戶當時沒有轉化并不代表用戶對當前的item不感興趣。當用戶再次到達推薦展位時，根據用戶之前產生的先驗行為理解并識別用戶的真正意圖，將符合用戶意圖的相關deal再次展現給用戶，引導用戶沿著行為流向下游行進，最終達到下單這個終極目標。
目前引入的實時用戶行為包括：實時瀏覽、實時收藏。
6. 替補策略
雖然現在有一系列基于用戶歷史行為的候選集觸發算法，但對于部分新用戶或者歷史行為不太豐富的用戶，上述算法觸發的候選集太小，因此需要使用一些替補策略進行填充。
熱銷單：在一定時間內銷量最多的item，可以考慮時間衰減的影響等。
好評單：用戶產生的評價中，評分較高的item。
城市單：滿足基本的限定條件，在用戶的請求城市內的。
7.子策略融合
為了結合不同觸發算法的優點，同時提高候選集的多樣性和覆蓋率，需要將不同的觸發算法融合在一起。常見的融合的方法有以下幾種：
加權型：最簡單的融合方法就是根據經驗值對不同算法賦給不同的權重，對各個算法產生的候選集按照給定的權重進行加權，然后再按照權重排序。
分級型：優先采用效果好的算法，當產生的候選集大小不足以滿足目標值時，再使用效果次好的算法，依此類推。
調制型：不同的算法按照不同的比例產生一定量的候選集，然后疊加產生最終總的候選集。
過濾型：當前的算法對前一級算法產生的候選集進行過濾，依此類推，候選集被逐級過濾，最終產生一個小而精的候選集合。
目前美團使用的方法集成了調制和分級兩種融合方法，不同的算法根據歷史效果表現給定不同的候選集構成比例，同時優先采用效果好的算法觸發，如果候選集不夠大，再采用效果次之的算法觸發，依此類推。
候選集重排序
如上所述，對于不同算法觸發出來的候選集，只是根據算法的歷史效果決定算法產生的item的位置顯得有些簡單粗暴，同時，在每個算法的內部，不同item的順序也只是簡單的由一個或者幾個因素決定，這些排序的方法只能用于第一步的初選過程，最終的排序結果需要借助機器學習的方法，使用相關的排序模型，綜合多方面的因素來確定。
模型
非線性模型能較好的捕捉特征中的非線性關系，但訓練和預測的代價相對線性模型要高一些，這也導致了非線性模型的更新周期相對要長。反之，線性模型對特征的處理要求比較高，需要憑借領域知識和經驗人工對特征做一些先期處理，但因為線性模型簡單，在訓練和預測時效率較高。因此在更新周期上也可以做的更短，還可以結合業務做一些在線學習的嘗試。在實踐中，非線性模型和線性模型都有應用。
非線性模型
目前主要采用了非線性的樹模型Additive Groves（簡稱AG），相對于線性模型，非線性模型可以更好的處理特征中的非線性關系，不必像線性模型那樣在特征處理和特征組合上花費比較大的精力。AG是一個加性模型，由很多個Grove組成，不同的Grove之間進行bagging得出最后的預測結果，由此可以減小過擬合的影響。
每一個Grove有多棵樹組成，在訓練時每棵樹的擬合目標為真實值與其他樹預測結果之和之間的殘差。當達到給定數目的樹時，重新訓練的樹會逐棵替代以前的樹。經過多次迭代后，達到收斂。

線性模型
目前應用比較多的線性模型非Logistic Regression莫屬了。為了能實時捕捉數據分布的變化，引入了online learning，接入實時數據流，使用google提出的FTRL方法對模型進行在線更新。

主要的步驟如下：
在線寫特征向量到HBase
Storm解析實時點擊和下單日志流，改寫HBase中對應特征向量的label
通過FTRL更新模型權重
將新的模型參數應用于線上
Training
采樣：對于點擊率預估而言，正負樣本嚴重不均衡，所以需要對負例做一些采樣。
負例：正例一般是用戶產生點擊、下單等轉換行為的樣本，但是用戶沒有轉換行為的樣本是否就一定是負例呢？其實不然，很多展現其實用戶根本沒有看到，所以把這樣樣本視為負例是不合理的，也會影響模型的效果。比較常用的方法是skip-above，即用戶點擊的item位置以上的展現才可能視作負例。當然，上面的負例都是隱式的負反饋數據，除此之外，還有用戶主動刪除的顯示負反饋數據，這些數據是高質量的負例。
去噪：對于數據中混雜的刷單等類作弊行為的數據，要將其排除出訓練數據，否則會直接影響模型的效果。
Feature
在目前的重排序模型中，大概分為以下幾類特征：
deal(即團購單，下同)維度的特征：主要是deal本身的一些屬性，包括價格、折扣、銷量、評分、類別、點擊率等
user維度的特征：包括用戶等級、用戶的人口屬性、用戶的客戶端類型等user、deal的交叉特征：包括用戶對deal的點擊、收藏、購買等
距離特征：包括用戶的實時地理位置、常去地理位置、工作地、居住地等與poi的距離對于非線性模型，上述特征可以直接使用；而對于線性模型，則需要對特征值做一些分桶、歸一化等處理，使特征值成為0~1之間的連續值或01二值。
conclusion
以數據為基礎，用算法去雕琢，只有將二者有機結合，才會帶來效果的提升。以下兩個節點是優化過程中的里程碑：
將候選集進行融合：提高了推薦的覆蓋度、多樣性和精度
引入重排序模型：解決了候選集增加以后deal之間排列順序的問題這些對于O2O場景的推薦有非常代表性的借鑒意義。

如果有什么不完善的地方，還請多補充。