美團(tuán)推薦算法實(shí)踐_數(shù)據(jù)分析師

推薦系統(tǒng)并不是新鮮的事物，在很久之前就存在，但是推薦系統(tǒng)真正進(jìn)入人們的視野，并且作為一個(gè)重要的模塊存在于各個(gè)互聯(lián)網(wǎng)公司，還是近幾年的事情。

隨著互聯(lián)網(wǎng)的深入發(fā)展，越來越多的信息在互聯(lián)網(wǎng)上傳播，產(chǎn)生了嚴(yán)重的信息過載。如果不采用一定的手段，用戶很難從如此多的信息流中找到對自己有價(jià)值的信息。

解決信息過載有幾種手段：一種是搜索，當(dāng)用戶有了明確的信息需求意圖后，將意圖轉(zhuǎn)換為幾個(gè)簡短的詞或者短語的組合（即query），然后將這些詞或短語組合提交到相應(yīng)的搜索引擎，再由搜索引擎在海量的信息庫中檢索出與query相關(guān)的信息返回給用戶；另外一種是推薦，很多時(shí)候用戶的意圖并不是很明確，或者很難用清晰的語義表達(dá)，有時(shí)甚至連用戶自己都不清楚自己的需求，這種情況下搜索就顯得捉襟見肘了。尤其是近些年來，隨著電子商務(wù)的興起，用戶并非一定是帶著明確的購買意圖去瀏覽，很多時(shí)候是去“逛”的，這種情景下解決信息過載，理解用戶意圖，為用戶推送個(gè)性化的結(jié)果，推薦系統(tǒng)便是一種比較好的選擇。

美團(tuán)作為國內(nèi)發(fā)展較快的o2o網(wǎng)站，有著大量的用戶和豐富的用戶行為，這些為推薦系統(tǒng)的應(yīng)用和優(yōu)化提供了不可或缺的條件，接下來介紹我們在推薦系統(tǒng)的構(gòu)建和優(yōu)化過程中的一些做法，與大家共享。

框架

從框架的角度看，推薦系統(tǒng)基本可以分為數(shù)據(jù)層、觸發(fā)層、融合過濾層和排序?qū)?。?shù)據(jù)層包括數(shù)據(jù)生成和數(shù)據(jù)存儲，主要是利用各種數(shù)據(jù)處理工具對原始日志進(jìn)行清洗，處理成格式化的數(shù)據(jù)，落地到不同類型的存儲系統(tǒng)中，供下游的算法和模型使用。候選集觸發(fā)層主要是從用戶的歷史行為、實(shí)時(shí)行為、地理位置等角度利用各種觸發(fā)策略產(chǎn)生推薦的候選集。候選集融合和過濾層有兩個(gè)功能，一是對出發(fā)層產(chǎn)生的不同候選集進(jìn)行融合，提高推薦策略的覆蓋度和精度；另外還要承擔(dān)一定的過濾職責(zé)，從產(chǎn)品、運(yùn)營的角度確定一些人工規(guī)則，過濾掉不符合條件的item。排序?qū)又饕抢?a href='/map/jiqixuexi/' style='color:#000;font-size:inherit;'>機(jī)器學(xué)習(xí)的模型對觸發(fā)層篩選出來的候選集進(jìn)行重排序。

同時(shí)，對與候選集觸發(fā)和重排序兩層而言，為了效果迭代是需要頻繁修改的兩層，因此需要支持ABtest。為了支持高效率的迭代，我們對候選集觸發(fā)和重排序兩層進(jìn)行了解耦，這兩層的結(jié)果是正交的，因此可以分別進(jìn)行對比試驗(yàn)，不會相互影響。同時(shí)在每一層的內(nèi)部，我們會根據(jù)用戶將流量劃分為多份，支持多個(gè)策略同時(shí)在線對比。

數(shù)據(jù)應(yīng)用

數(shù)據(jù)乃算法、模型之本。美團(tuán)作為一個(gè)交易平臺，同時(shí)具有快速增長的用戶量，因此產(chǎn)生了海量豐富的用戶行為數(shù)據(jù)。當(dāng)然，不同類型的數(shù)據(jù)的價(jià)值和反映的用戶意圖的強(qiáng)弱也有所不同。

用戶主動行為數(shù)據(jù)記錄了用戶在美團(tuán)平臺上不同的環(huán)節(jié)的各種行為，這些行為一方面用于候選集觸發(fā)算法（在下一部分介紹）中的離線計(jì)算（主要是瀏覽、下單），另外一方面，這些行為代表的意圖的強(qiáng)弱不同，因此在訓(xùn)練重排序模型時(shí)可以針對不同的行為設(shè)定不同的回歸目標(biāo)值，以更細(xì)地刻畫用戶的行為強(qiáng)弱程度。此外，用戶對deal的這些行為還可以作為重排序模型的交叉特征，用于模型的離線訓(xùn)練和在線預(yù)測。

1. 負(fù)反饋數(shù)據(jù)反映了當(dāng)前的結(jié)果可能在某些方面不能滿足用戶的需求，因此在后續(xù)的候選集觸發(fā)過程中需要考慮對特定的因素進(jìn)行過濾或者降權(quán)，降低負(fù)面因素再次出現(xiàn)的幾率，提高用戶體驗(yàn)；同時(shí)在重排序的模型訓(xùn)練中，負(fù)反饋數(shù)據(jù)可以作為不可多得的負(fù)例參與模型訓(xùn)練，這些負(fù)例要比那些展示后未點(diǎn)擊、未下單的樣本顯著的多。
2. 用戶畫像是刻畫用戶屬性的基礎(chǔ)數(shù)據(jù)，其中有些是直接獲取的原始數(shù)據(jù)，有些是經(jīng)過挖掘的二次加工數(shù)據(jù)，這些屬性一方面可以用于候選集觸發(fā)過程中對deal進(jìn)行加權(quán)或降權(quán)，另外一方面可以作為重排序模型中的用戶維度特征。
3. 通過對UGC數(shù)據(jù)的挖掘可以提取出一些關(guān)鍵詞，然后使用這些關(guān)鍵詞給deal打標(biāo)簽，用于deal的個(gè)性化展示。

策略觸發(fā)

上文中我們提到了數(shù)據(jù)的重要性，但是數(shù)據(jù)的落腳點(diǎn)還是算法和模型。單純的數(shù)據(jù)只是一些字節(jié)的堆積，我們必須通過對數(shù)據(jù)的清洗去除數(shù)據(jù)中的噪聲，然后通過算法和模型學(xué)習(xí)其中的規(guī)律，才能將數(shù)據(jù)的價(jià)值最大化。在本節(jié)中，將介紹推薦候選集觸發(fā)過程中用到的相關(guān)算法。

1. 協(xié)同過濾

提到推薦，就不得不說協(xié)同過濾，它幾乎在每一個(gè)推薦系統(tǒng)中都會用到?；镜乃惴ǚ浅：唵?，但是要獲得更好的效果，往往需要根據(jù)具體的業(yè)務(wù)做一些差異化的處理。

• 清除作弊、刷單、代購等噪聲數(shù)據(jù)。這些數(shù)據(jù)的存在會嚴(yán)重影響算法的效果，因此要在第一步的數(shù)據(jù)清洗中就將這些數(shù)據(jù)剔除。
• 合理選取訓(xùn)練數(shù)據(jù)。選取的訓(xùn)練數(shù)據(jù)的時(shí)間窗口不宜過長，當(dāng)然也不能過短。具體的窗口期數(shù)值需要經(jīng)過多次的實(shí)驗(yàn)來確定。同時(shí)可以考慮引入時(shí)間衰減，因?yàn)榻诘挠脩粜袨楦芊从秤脩艚酉聛淼男袨閯幼鳌?/span>
• user-based與item-based相結(jié)合。| 群體/個(gè)體 | 計(jì)算代價(jià) | 適用場景 | 冷啟動 | 可解釋性 | 實(shí)時(shí)性
  —|—-|—-|—-|—-|—-|—-
  user-based | 更依賴于當(dāng)前用戶相近的用戶群體的社會化行為 | 適用于用戶數(shù)較少的場合 | 時(shí)效性強(qiáng)，用戶個(gè)性化興趣不太顯著的場合 | 新加入的物品能很快進(jìn)入推薦列表 | 弱 | 用戶新的行為不一定導(dǎo)致推薦結(jié)果的變化
  item-based | 更側(cè)重用戶自身的個(gè)體行為 | 適用于物品數(shù)較少的場合 | 長尾物品豐富，用戶個(gè)性化需求強(qiáng)烈的場合 | 新加入的用戶能很快得到推薦 | 強(qiáng) | 用戶新的行為一定導(dǎo)致推薦結(jié)果的變化
• 嘗試不同的相似度計(jì)算方法。在實(shí)踐中，我們采用了一種稱作loglikelihood ratio[1]的相似度計(jì)算方法。在mahout中，loglikelihood ratio也作為一種相似度計(jì)算方法被采用。
  下表表示了Event A和Event B之間的相互關(guān)系，其中：
  k11 ：Event A和Event B共現(xiàn)的次數(shù)
  k12 ：Event B發(fā)生，Event A未發(fā)生的次數(shù)
  k21 ：Event A發(fā)生，Event B未發(fā)生的次數(shù)
  k22 ：Event A和Event B都不發(fā)生的次數(shù)| Event A | Everything but A
  —|—-|—-
  Event B | A and B together (k_11) | B, but not A (k_12)
  Everything but B | A 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為幾個(gè)元素組成的系統(tǒng)的香農(nóng)熵)

2. location-based

對于移動設(shè)備而言，與PC端最大的區(qū)別之一是移動設(shè)備的位置是經(jīng)常發(fā)生變化的。不同的地理位置反映了不同的用戶場景，在具體的業(yè)務(wù)中可以充分利用用戶所處的地理位置。在推薦的候選集觸發(fā)中，我們也會根據(jù)用戶的實(shí)時(shí)地理位置、工作地、居住地等地理位置觸發(fā)相應(yīng)的策略。

• 根據(jù)用戶的歷史消費(fèi)、歷史瀏覽等，挖掘出某一粒度的區(qū)域（比如商圈）內(nèi)的區(qū)域消費(fèi)熱單和區(qū)域購買熱單

區(qū)域消費(fèi)熱單

區(qū)域購買熱單

• 當(dāng)新的線上用戶請求到達(dá)時(shí)，根據(jù)用戶的幾個(gè)地理位置對相應(yīng)地理位置的區(qū)域消費(fèi)熱單和區(qū)域購買熱單進(jìn)行加權(quán)，最終得到一個(gè)推薦列表。
• 此外，還可以根據(jù)用戶出現(xiàn)的地理位置，采用協(xié)同過濾的方式計(jì)算用戶的相似度。

3. query-based

搜索是一種強(qiáng)用戶意圖，比較明確的反應(yīng)了用戶的意愿，但是在很多情況下，因?yàn)楦鞣N各樣的原因，沒有形成最終的轉(zhuǎn)換。盡管如此，我們認(rèn)為，這種情景還是代表了一定的用戶意愿，可以加以利用。具體做法如下：

• 對用戶過去一段時(shí)間的搜索無轉(zhuǎn)換行為進(jìn)行挖掘，計(jì)算每一個(gè)用戶對不同query的權(quán)重。
  
• 計(jì)算每個(gè)query下不同deal的權(quán)重。
  
• 當(dāng)用戶再次請求時(shí)，根據(jù)用戶對不同query的權(quán)重及query下不同deal的權(quán)重進(jìn)行加權(quán)，取出權(quán)重最大的TopN進(jìn)行推薦。

4. graph-based

對于協(xié)同過濾而言，user之間或者deal之間的圖距離是兩跳，對于更遠(yuǎn)距離的關(guān)系則不能考慮在內(nèi)。而圖算法可以打破這一限制，將user與deal的關(guān)系視作一個(gè)二部圖，相互間的關(guān)系可以在圖上傳播。Simrank[2]是一種衡量對等實(shí)體相似度的圖算法。它的基本思想是，如果兩個(gè)實(shí)體與另外的相似實(shí)體有相關(guān)關(guān)系，那它們也是相似的，即相似性是可以傳播的。

• Let s(A,B) denote the similarity between persons A and B, for A != B
  

Let s(c,d) denote the similarity between items c and d, for c != d

O(A),O(B): the set of out-neighbors for node A or node B
I(c),I(d): the set of in-neighbors for node c or node d

• simrank的計(jì)算（采用矩陣迭代的方式）
  
• 計(jì)算得出相似度矩陣后，可以類似協(xié)同過濾用于線上推薦。