前言

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

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

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

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

框架

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

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

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

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

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

負(fù)反饋數(shù)據(jù)反映了當(dāng)前的結(jié)果可能在某些方面不能滿足用戶的需求，因此在后續(xù)的候選集觸發(fā)過(guò)程中需要考慮對(duì)特定的因素進(jìn)行過(guò)濾或者降權(quán)，降低負(fù)面因素再次出現(xiàn)的幾率，提高用戶體驗(yàn);同時(shí)在重排序的模型訓(xùn)練中，負(fù)反饋數(shù)據(jù)可以作為不可多得的負(fù)例參與模型訓(xùn)練，這些負(fù)例要比那些展示后未點(diǎn)擊、未下單的樣本顯著的多。

用戶畫(huà)像是刻畫(huà)用戶屬性的基礎(chǔ)數(shù)據(jù)，其中有些是直接獲取的原始數(shù)據(jù)，有些是經(jīng)過(guò)挖掘的二次加工數(shù)據(jù)，這些屬性一方面可以用于候選集觸發(fā)過(guò)程中對(duì)deal進(jìn)行加權(quán)或降權(quán)，另外一方面可以作為重排序模型中的用戶維度特征。

通過(guò)對(duì)UGC數(shù)據(jù)的挖掘可以提取出一些關(guān)鍵詞，然后使用這些關(guān)鍵詞給deal打標(biāo)簽，用于deal的個(gè)性化展示。

策略觸發(fā)

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

1. 協(xié)同過(guò)濾

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

清除作弊、刷單、代購(gòu)等噪聲數(shù)據(jù)。這些數(shù)據(jù)的存在會(huì)嚴(yán)重影響算法的效果，因此要在第一步的數(shù)據(jù)清洗中就將這些數(shù)據(jù)剔除。

合理選取訓(xùn)練數(shù)據(jù)。選取的訓(xùn)練數(shù)據(jù)的時(shí)間窗口不宜過(guò)長(zhǎng)，當(dāng)然也不能過(guò)短。具體的窗口期數(shù)值需要經(jīng)過(guò)多次的實(shí)驗(yàn)來(lái)確定。同時(shí)可以考慮引入時(shí)間衰減，因?yàn)榻诘挠脩粜袨楦芊从秤脩艚酉聛?lái)的行為動(dòng)作。

user-based與item-based相結(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ù)

則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

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

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

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

區(qū)域購(gòu)買熱單

當(dāng)新的線上用戶請(qǐng)求到達(dá)時(shí)，根據(jù)用戶的幾個(gè)地理位置對(duì)相應(yīng)地理位置的區(qū)域消費(fèi)熱單和區(qū)域購(gòu)買熱單進(jìn)行加權(quán)，最終得到一個(gè)推薦列表。

此外，還可以根據(jù)用戶出現(xiàn)的地理位置，采用協(xié)同過(guò)濾的方式計(jì)算用戶的相似度。

3. query-based

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

對(duì)用戶過(guò)去一段時(shí)間的搜索無(wú)轉(zhuǎn)換行為進(jìn)行挖掘，計(jì)算每一個(gè)用戶對(duì)不同query的權(quán)重。

計(jì)算每個(gè)query下不同deal的權(quán)重。

當(dāng)用戶再次請(qǐng)求時(shí)，根據(jù)用戶對(duì)不同query的權(quán)重及query下不同deal的權(quán)重進(jìn)行加權(quán)，取出權(quán)重最大的TopN進(jìn)行推薦。

4. graph-based

對(duì)于協(xié)同過(guò)濾而言，user之間或者deal之間的圖距離是兩跳，對(duì)于更遠(yuǎn)距離的關(guān)系則不能考慮在內(nèi)。而圖算法可以打破這一限制，將user與deal的關(guān)系視作一個(gè)二部圖，相互間的關(guān)系可以在圖上傳播。Simrank[2]是一種衡量對(duì)等實(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é)同過(guò)濾用于線上推薦。

5. 實(shí)時(shí)用戶行為

目前我們的業(yè)務(wù)會(huì)產(chǎn)生包括搜索、篩選、收藏、瀏覽、下單等豐富的用戶行為，這些是我們進(jìn)行效果優(yōu)化的重要基礎(chǔ)。我們當(dāng)然希望每一個(gè)用戶行為流都能到達(dá)轉(zhuǎn)化的環(huán)節(jié)，但是事實(shí)上遠(yuǎn)非這樣。

當(dāng)用戶產(chǎn)生了下單行為上游的某些行為時(shí)，會(huì)有相當(dāng)一部分因?yàn)楦鞣N原因使行為流沒(méi)有形成轉(zhuǎn)化。但是，用戶的這些上游行為對(duì)我們而言是非常重要的先驗(yàn)知識(shí)。很多情況下，用戶當(dāng)時(shí)沒(méi)有轉(zhuǎn)化并不代表用戶對(duì)當(dāng)前的item不感興趣。當(dāng)用戶再次到達(dá)我們的推薦展位時(shí)，我們根據(jù)用戶之前產(chǎn)生的先驗(yàn)行為理解并識(shí)別用戶的真正意圖，將符合用戶意圖的相關(guān)deal再次展現(xiàn)給用戶，引導(dǎo)用戶沿著行為流向下游行進(jìn)，最終達(dá)到下單這個(gè)終極目標(biāo)。

目前引入的實(shí)時(shí)用戶行為包括：實(shí)時(shí)瀏覽、實(shí)時(shí)收藏。

6. 替補(bǔ)策略

雖然我們有一系列基于用戶歷史行為的候選集觸發(fā)算法，但對(duì)于部分新用戶或者歷史行為不太豐富的用戶，上述算法觸發(fā)的候選集太小，因此需要使用一些替補(bǔ)策略進(jìn)行填充。

熱銷單：在一定時(shí)間內(nèi)銷量最多的item，可以考慮時(shí)間衰減的影響等。

好評(píng)單：用戶產(chǎn)生的評(píng)價(jià)中，評(píng)分較高的item。

城市單：滿足基本的限定條件，在用戶的請(qǐng)求城市內(nèi)的。

子策略融合

為了結(jié)合不同觸發(fā)算法的優(yōu)點(diǎn)，同時(shí)提高候選集的多樣性和覆蓋率，需要將不同的觸發(fā)算法融合在一起。常見(jiàn)的融合的方法有以下幾種[3]：

加權(quán)型：最簡(jiǎn)單的融合方法就是根據(jù)經(jīng)驗(yàn)值對(duì)不同算法賦給不同的權(quán)重，對(duì)各個(gè)算法產(chǎn)生的候選集按照給定的權(quán)重進(jìn)行加權(quán)，然后再按照權(quán)重排序。

分級(jí)型：優(yōu)先采用效果好的算法，當(dāng)產(chǎn)生的候選集大小不足以滿足目標(biāo)值時(shí)，再使用效果次好的算法，依此類推。

調(diào)制型：不同的算法按照不同的比例產(chǎn)生一定量的候選集，然后疊加產(chǎn)生最終總的候選集。

過(guò)濾型：當(dāng)前的算法對(duì)前一級(jí)算法產(chǎn)生的候選集進(jìn)行過(guò)濾，依此類推，候選集被逐級(jí)過(guò)濾，最終產(chǎn)生一個(gè)小而精的候選集合。

目前我們使用的方法集成了調(diào)制和分級(jí)兩種融合方法，不同的算法根據(jù)歷史效果表現(xiàn)給定不同的候選集構(gòu)成比例，同時(shí)優(yōu)先采用效果好的算法觸發(fā)，如果候選集不夠大，再采用效果次之的算法觸發(fā)，依此類推。

候選集重排序

如上所述，對(duì)于不同算法觸發(fā)出來(lái)的候選集，只是根據(jù)算法的歷史效果決定算法產(chǎn)生的item的位置顯得有些簡(jiǎn)單粗暴，同時(shí)，在每個(gè)算法的內(nèi)部，不同item的順序也只是簡(jiǎn)單的由一個(gè)或者幾個(gè)因素決定，這些排序的方法只能用于第一步的初選過(guò)程，最終的排序結(jié)果需要借助機(jī)器學(xué)習(xí)的方法，使用相關(guān)的排序模型，綜合多方面的因素來(lái)確定。

1. 模型

非線性模型能較好的捕捉特征中的非線性關(guān)系，但訓(xùn)練和預(yù)測(cè)的代價(jià)相對(duì)線性模型要高一些，這也導(dǎo)致了非線性模型的更新周期相對(duì)要長(zhǎng)。反之，線性模型對(duì)特征的處理要求比較高，需要憑借領(lǐng)域知識(shí)和經(jīng)驗(yàn)人工對(duì)特征做一些先期處理，但因?yàn)榫€性模型簡(jiǎn)單，在訓(xùn)練和預(yù)測(cè)時(shí)效率較高。因此在更新周期上也可以做的更短，還可以結(jié)合業(yè)務(wù)做一些在線學(xué)習(xí)的嘗試。在我們的實(shí)踐中，非線性模型和線性模型都有應(yīng)用。

非線性模型

目前我們主要采用了非線性的樹(shù)模型Additive Groves[4](簡(jiǎn)稱AG)，相對(duì)于線性模型，非線性模型可以更好的處理特征中的非線性關(guān)系，不必像線性模型那樣在特征處理和特征組合上花費(fèi)比較大的精力。AG是一個(gè)加性模型，由很多個(gè)Grove組成，不同的Grove之間進(jìn)行bagging得出最后的預(yù)測(cè)結(jié)果，由此可以減小過(guò)擬合的影響。

每一個(gè)Grove有多棵樹(shù)組成，在訓(xùn)練時(shí)每棵樹(shù)的擬合目標(biāo)為真實(shí)值與其他樹(shù)預(yù)測(cè)結(jié)果之和之間的殘差。當(dāng)達(dá)到給定數(shù)目的樹(shù)時(shí)，重新訓(xùn)練的樹(shù)會(huì)逐棵替代以前的樹(shù)。經(jīng)過(guò)多次迭代后，達(dá)到收斂。

線性模型

目前應(yīng)用比較多的線性模型非Logistic Regression莫屬了。為了能實(shí)時(shí)捕捉數(shù)據(jù)分布的變化，我們引入了online learning，接入實(shí)時(shí)數(shù)據(jù)流，使用google提出的FTRL[5]方法對(duì)模型進(jìn)行在線更新。

主要的步驟如下：

在線寫特征向量到HBase

Storm解析實(shí)時(shí)點(diǎn)擊和下單日志流，改寫HBase中對(duì)應(yīng)特征向量的label

通過(guò)FTRL更新模型權(quán)重

將新的模型參數(shù)應(yīng)用于線上

2. 數(shù)據(jù)

采樣：對(duì)于點(diǎn)擊率預(yù)估而言，正負(fù)樣本嚴(yán)重不均衡，所以需要對(duì)負(fù)例做一些采樣。

負(fù)例：正例一般是用戶產(chǎn)生點(diǎn)擊、下單等轉(zhuǎn)換行為的樣本，但是用戶沒(méi)有轉(zhuǎn)換行為的樣本是否就一定是負(fù)例呢?其實(shí)不然，很多展現(xiàn)其實(shí)用戶根本沒(méi)有看到，所以把這樣樣本視為負(fù)例是不合理的，也會(huì)影響模型的效果。比較常用的方法是skip-above，即用戶點(diǎn)擊的item位置以上的展現(xiàn)才可能視作負(fù)例。當(dāng)然，上面的負(fù)例都是隱式的負(fù)反饋數(shù)據(jù)，除此之外，我們還有用戶主動(dòng)刪除的顯示負(fù)反饋數(shù)據(jù)，這些數(shù)據(jù)是高質(zhì)量的負(fù)例。

去噪：對(duì)于數(shù)據(jù)中混雜的刷單等類作弊行為的數(shù)據(jù)，要將其排除出訓(xùn)練數(shù)據(jù)，否則會(huì)直接影響模型的效果。

3. 特征

在我們目前的重排序模型中，大概分為以下幾類特征：

deal(即團(tuán)購(gòu)單，下同)維度的特征：主要是deal本身的一些屬性，包括價(jià)格、折扣、銷量、評(píng)分、類別、點(diǎn)擊率等

user維度的特征：包括用戶等級(jí)、用戶的人口屬性、用戶的客戶端類型等

user、deal的交叉特征：包括用戶對(duì)deal的點(diǎn)擊、收藏、購(gòu)買等

距離特征：包括用戶的實(shí)時(shí)地理位置、常去地理位置、工作地、居住地等與poi的距離

對(duì)于非線性模型，上述特征可以直接使用;而對(duì)于線性模型，則需要對(duì)特征值做一些分桶、歸一化等處理，使特征值成為0~1之間的連續(xù)值或01二值。

總結(jié)

以數(shù)據(jù)為基礎(chǔ)，用算法去雕琢，只有將二者有機(jī)結(jié)合，才會(huì)帶來(lái)效果的提升。對(duì)我們而言，以下兩個(gè)節(jié)點(diǎn)是我們優(yōu)化過(guò)程中的里程碑：

將候選集進(jìn)行融合：提高了推薦的覆蓋度、多樣性和精度

引入重排序模型：解決了候選集增加以后deal之間排列順序的問(wèn)題

以上是我們?cè)趯?shí)踐中的一點(diǎn)總結(jié)，當(dāng)然我們還有還多事情要做。we are still on the way!

來(lái)源：美團(tuán)技術(shù)博客