美團(tuán)的愿景是連接消費(fèi)者和商家，而搜索在其中起著非常重要的作用。隨著業(yè)務(wù)的發(fā)展，美團(tuán)的商家和團(tuán)購(gòu)數(shù)正在飛速增長(zhǎng)。這一背景下，搜索排序的重要性顯得更加突出：排序的優(yōu)化能幫助用戶更便捷地找到滿足其需求的商家和團(tuán)購(gòu)，改進(jìn)用戶體驗(yàn)，提升轉(zhuǎn)化效果。
和傳統(tǒng)網(wǎng)頁(yè)搜索問(wèn)題相比，美團(tuán)的搜索排序有自身的特點(diǎn)——90%的交易發(fā)生在移動(dòng)端。一方面，這對(duì)排序的個(gè)性化提出了更高的要求，例如在“火鍋”查詢下，北京五道口的火鍋店A，對(duì)在五道口的用戶U1來(lái)說(shuō)是好的結(jié)果，對(duì)在望京的用戶U2來(lái)講不一定是好的結(jié)果；另一方面，我們由此積累了用戶在客戶端上豐富準(zhǔn)確的行為，經(jīng)分析獲得用戶的地理位置、品類和價(jià)格等偏好，進(jìn)而指導(dǎo)個(gè)性化排序。
針對(duì)美團(tuán)的O2O業(yè)務(wù)特點(diǎn)，我們實(shí)現(xiàn)了一套搜索排序技術(shù)方案，相比規(guī)則排序有百分之幾十的提升。基于這一方案，我們又抽象了一套通用的O2O排序解決方案，只需1-2天就可以快速地部署到其他產(chǎn)品和子行業(yè)中，目前在熱詞、Suggestion、酒店、KTV等多個(gè)產(chǎn)品和子行業(yè)中應(yīng)用。
我們將按線上和線下兩部分分別介紹這一通用O2O排序解決方案，本文是線上篇，主要介紹在線服務(wù)框架、特征加載、在線預(yù)估等模塊，下篇將會(huì)著重介紹離線流程。
為了快速有效的進(jìn)行搜索算法的迭代，排序系統(tǒng)設(shè)計(jì)上支持靈活的A/B測(cè)試，滿足準(zhǔn)確效果追蹤的需求。
美團(tuán)搜索排序系統(tǒng)如上圖所示，主要包括離線數(shù)據(jù)處理、線上服務(wù)和在線數(shù)據(jù)處理三個(gè)模塊。
HDFS/Hive上存儲(chǔ)了搜索展示、點(diǎn)擊、下單和支付等日志。離線數(shù)據(jù)流程按天調(diào)度多個(gè)Map Reduce任務(wù)分析日志，相關(guān)任務(wù)包括：
離線特征挖掘
產(chǎn)出Deal（團(tuán)購(gòu)單）/POI（商家）、用戶和Query等維度的特征供排序模型使用。
數(shù)據(jù)清洗標(biāo)注 & 模型訓(xùn)練
數(shù)據(jù)清洗去掉爬蟲(chóng)、作弊等引入的臟數(shù)據(jù)；清洗完的數(shù)據(jù)經(jīng)過(guò)標(biāo)注后用作模型訓(xùn)練。
效果報(bào)表生成
統(tǒng)計(jì)生成算法效果指標(biāo)，指導(dǎo)排序改進(jìn)。
特征監(jiān)控
特征作為排序模型的輸入是排序系統(tǒng)的基礎(chǔ)。特征的錯(cuò)誤異常變動(dòng)會(huì)直接影響排序的效果。特征監(jiān)控主要監(jiān)控特征覆蓋率和取值分布，幫我們及時(shí)發(fā)現(xiàn)相關(guān)問(wèn)題。
和離線流程相對(duì)應(yīng)，在線流程通過(guò)Storm/Spark Streaming等工具對(duì)實(shí)時(shí)日志流進(jìn)行分析處理，產(chǎn)出實(shí)時(shí)特征、實(shí)時(shí)報(bào)表和監(jiān)控?cái)?shù)據(jù)，更新在線排序模型。
Rank Service接到搜索請(qǐng)求后，會(huì)調(diào)用召回服務(wù)獲取候選POI/Deal集合，根據(jù)A/B測(cè)試配置為用戶分配排序策略/模型，應(yīng)用策略/模型對(duì)候選集合進(jìn)行排序。
下圖是Rank Service內(nèi)部的排序流程。
L1 粗粒度排序（快速）
使用較少的特征、簡(jiǎn)單的模型或規(guī)則對(duì)候選集進(jìn)行粗粒度排序。
L2 細(xì)粒度排序（較慢）
對(duì)L1排序結(jié)果的前N個(gè)進(jìn)行細(xì)粒度排序。這一層會(huì)從特征庫(kù)加載特征（通過(guò)FeatureLoader），應(yīng)用模型（A/B測(cè)試配置分配）進(jìn)行排序。
L3 業(yè)務(wù)規(guī)則干預(yù)
在L2排序的基礎(chǔ)上，應(yīng)用業(yè)務(wù)規(guī)則/人工干預(yù)對(duì)排序進(jìn)行適當(dāng)調(diào)整。
Rank Service會(huì)將展示日志記錄到日志收集系統(tǒng)，供在線/離線處理。
A/B測(cè)試的流量切分是在Rank Server端完成的。我們根據(jù)UUID（用戶標(biāo)識(shí)）將流量切分為多個(gè)桶（Bucket），每個(gè)桶對(duì)應(yīng)一種排序策略，桶內(nèi)流量將使用相應(yīng)的策略進(jìn)行排序。使用UUID進(jìn)行流量切分，是為了保證用戶體驗(yàn)的一致性。
{ "search": { "NumberOfBuckets": 100, "DefaultStrategy": "Base", "Segments": [ { "BeginBucket": 0, "EndBucket": 24, "WhiteList": [123], "Strategy": "Algo-1" }, { "BeginBucket": 25, "EndBucket": 49, "WhiteList": [], "Strategy": "Algo-2" } ] }}對(duì)于不合法的UUID，每次請(qǐng)求會(huì)隨機(jī)分配一個(gè)桶，以保證效果對(duì)比不受影響。白名單（White List）機(jī)制能保證配置用戶使用給定的策略，以輔助相關(guān)的測(cè)試。
除了A/B測(cè)試之外，我們還應(yīng)用了Interleaving[7]方法，用于比較兩種排序算法。相較于A/B測(cè)試，Interleaving方法對(duì)排序算法更靈敏[9]，能通過(guò)更少的樣本來(lái)比較兩種排序算法之間的優(yōu)劣。Interleaving方法使用較小流量幫助我們快速淘汰較差算法，提高策略迭代效率。
搜索排序服務(wù)涉及多種類型的特征，特征獲取和計(jì)算是Rank Service響應(yīng)速度的瓶頸。我們?cè)O(shè)計(jì)了FeatureLoader模塊，根據(jù)特征依賴關(guān)系，并行地獲取和計(jì)算特征，有效地減少了特征加載時(shí)間。實(shí)際業(yè)務(wù)中，并行特征加載平均響應(yīng)時(shí)間比串行特征加載快約20毫秒。
FeatureLoader的實(shí)現(xiàn)中我們使用了Akka[8]。如上圖所示，特征獲取和計(jì)算的被抽象和封裝為了若干個(gè)Akka actor，由Akka調(diào)度、并行執(zhí)行。
美團(tuán)從2013年9月開(kāi)始在搜索排序上應(yīng)用機(jī)器學(xué)習(xí)方法（Learning to Rank[1]），并且取得很大的收益。這得益于準(zhǔn)確的數(shù)據(jù)標(biāo)注：用戶的點(diǎn)擊下單支付等行為能有效地反映其偏好。通過(guò)在特征挖掘和模型優(yōu)化兩方面的工作，我們不斷地優(yōu)化搜索排序。下面將介紹我們?cè)谔卣魇褂谩?shù)據(jù)標(biāo)注、排序算法、Position Bias處理和冷啟動(dòng)問(wèn)題緩解等方面的工作。
從美團(tuán)業(yè)務(wù)出發(fā)，特征選取著眼于用戶、Query、Deal/POI和搜索上下文四個(gè)維度。
用戶維度
包括挖掘得到的品類偏好、消費(fèi)水平和地理位置等。
Query維度
包括Query長(zhǎng)度、歷史點(diǎn)擊率、轉(zhuǎn)化率和類型（商家詞/品類詞/地標(biāo)詞）等。
Deal/POI維度
包括Deal/POI銷量、價(jià)格、評(píng)價(jià)、折扣率、品類和歷史轉(zhuǎn)化率等。
上下文維度
包括時(shí)間、搜索入口等。
此外，有的特征來(lái)自于幾個(gè)維度之間的相互關(guān)系：用戶對(duì)Deal/POI的點(diǎn)擊和下單等行為、用戶與POI的距離等是決定排序的重要因素；Query和Deal/POI的文本相關(guān)性和語(yǔ)義相關(guān)性是模型的關(guān)鍵特征。
Learning to Rank應(yīng)用中，我們主要采用了Pointwise方法。采用用戶的點(diǎn)擊、下單和支付等行為來(lái)進(jìn)行正樣本的標(biāo)注。從統(tǒng)計(jì)上看，點(diǎn)擊、下單和支付等行為分別對(duì)應(yīng)了該樣本對(duì)用戶需求的不同的匹配程度，因此對(duì)應(yīng)的樣本會(huì)被當(dāng)做正樣本，且賦予不斷增大的權(quán)重。
線上運(yùn)行著多種不同類型模型，主要包括：
Gradient boosting decision/regression tree（GBDT/GBRT）[2]
GBDT是LTR中應(yīng)用較多的非線性模型。我們開(kāi)發(fā)了基于Spark的GBDT工具，樹(shù)擬合梯度的時(shí)候運(yùn)用了并行方法，縮短訓(xùn)練時(shí)間。GBDT的樹(shù)被設(shè)計(jì)為三叉樹(shù)，作為一種處理特征缺失的方法。
Logistic Regression（LR）
參考Facebook的paper[3]，我們利用GBDT進(jìn)行部分LR特征的構(gòu)建。用FTRL[4]算法來(lái)在線訓(xùn)練LR模型。
對(duì)模型的評(píng)估分為離線和線上兩部分。離線部分我們通過(guò)AUC（Area Under the ROC Curve）和MAP（Mean Average Precision）來(lái)評(píng)價(jià)模型，線上則通過(guò)A/B測(cè)試來(lái)檢驗(yàn)?zāi)Ｐ偷膶?shí)際效果，兩項(xiàng)手段支撐著算法不斷的迭代優(yōu)化。
在我們的搜索排序系統(tǒng)中，冷啟動(dòng)問(wèn)題[6]表現(xiàn)為當(dāng)新的商家、新的團(tuán)購(gòu)單錄入或新的用戶使用美團(tuán)時(shí)，我們沒(méi)有足夠的數(shù)據(jù)用來(lái)推測(cè)用戶對(duì)產(chǎn)品的喜好。商家冷啟動(dòng)是主要問(wèn)題，我們通過(guò)兩方面手段來(lái)進(jìn)行緩解。一方面，在模型中引入了文本相關(guān)性、品類相似度、距離和品類屬性等特征，確保在沒(méi)有足夠展示和反饋的前提下能較為準(zhǔn)確地預(yù)測(cè)；另一方面，我們引入了Explore&Exploit機(jī)制，對(duì)新商家和團(tuán)單給予適度的曝光機(jī)會(huì)，以收集反饋數(shù)據(jù)并改善預(yù)測(cè)。
在手機(jī)端，搜索結(jié)果的展現(xiàn)形式是列表頁(yè)，結(jié)果的展示位置會(huì)對(duì)用戶行為產(chǎn)生很大的影響。在特征挖掘和訓(xùn)練數(shù)據(jù)標(biāo)注當(dāng)中，我們考慮了展示位置因素引入的偏差。例如CTR（click-through-rate）的統(tǒng)計(jì)中，我們基于Examination Model[5]，去除展示位置帶來(lái)的影響。
本文主要介紹了美團(tuán)搜索排序系統(tǒng)線上部分的結(jié)構(gòu)、算法和主要模塊。在后續(xù)文章里，我們會(huì)著重介紹排序系統(tǒng)離線部分的工作。
一個(gè)完善的線上線下系統(tǒng)是排序優(yōu)化得以持續(xù)進(jìn)行的基礎(chǔ)。基于業(yè)務(wù)對(duì)數(shù)據(jù)和模型上的不斷挖掘是排序持續(xù)改善的動(dòng)力。我們?nèi)栽谔剿鳌?/p>
聯(lián)系客服
