美團網站的數據搜索排序解決方案精華分享

         一、線上篇

　　隨著業務的發展，美團的商家和團購數正在飛速增長。這一背景下，搜索排序的重要性顯得更加突出：排序的優化能幫助用戶更便捷地找到滿足其需求的商家和團購，改進用戶體驗，提升轉化效果。

　　和傳統網頁搜索問題相比，美團的搜索排序有自身的特點——90%的交易發生在移動端。一方面，這對排序的個性化提出了更高的要求，例如在“火鍋”查詢下，北京五道口的火鍋店A，對在五道口的用戶U1來說是好的結果，對在望京的用戶U2來講不一定是好的結果;另一方面，我們由此積累了用戶在客戶端上豐富準確的行為，經分析獲得用戶的地理位置、品類和價格等偏好，進而指導個性化排序。

　　針對美團的O2O業務特點，我們實現了一套搜索排序技術方案，相比規則排序有百分之幾十的提升。基于這一方案，我們又抽象了一套通用的O2O排序解決方案，只需1-2天就可以快速地部署到其他產品和子行業中，目前在熱詞、Suggestion、酒店、KTV等多個產品和子行業中應用。

　　我們將按線上和線下兩部分分別介紹這一通用O2O排序解決方案，本文是線上篇，主要介紹在線服務框架、特征加載、在線預估等模塊，下篇將會著重介紹離線流程。

　　排序系統

　　為了快速有效的進行搜索算法的迭代，排序系統設計上支持靈活的A/B測試，滿足準確效果追蹤的需求。

　　美團搜索排序系統如上圖所示，主要包括離線數據處理、線上服務和在線數據處理三個模塊。

　　離線數據處理

　　HDFS/Hive上存儲了搜索展示、點擊、下單和支付等日志。離線數據流程按天調度多個Map Reduce任務分析日志，相關任務包括：

　　離線特征挖掘

　　產出Deal(團購單)/POI(商家)、用戶和Query等維度的特征供排序模型使用。

　　數據清洗標注 & 模型訓練

　　數據清洗去掉爬蟲、作弊等引入的臟數據;清洗完的數據經過標注后用作模型訓練。

　　效果報表生成

　　統計生成算法效果指標，指導排序改進。

　　特征監控

　　特征作為排序模型的輸入是排序系統的基礎。特征的錯誤異常變動會直接影響排序的效果。特征監控主要監控特征覆蓋率和取值分布，幫我們及時發現相關問題。

　　在線數據處理

　　和離線流程相對應，在線流程通過Storm/Spark Streaming等工具對實時日志流進行分析處理，產出實時特征、實時報表和監控數據，更新在線排序模型。

　　在線服務(Rank Service)

　　Rank Service接到搜索請求后，會調用召回服務獲取候選POI/Deal集合，根據A/B測試配置為用戶分配排序策略/模型，應用策略/模型對候選集合進行排序。

　　下圖是Rank Service內部的排序流程。

　　L1 粗粒度排序(快速)

　　使用較少的特征、簡單的模型或規則對候選集進行粗粒度排序。

　　L2 細粒度排序(較慢)

　　對L1排序結果的前N個進行細粒度排序。這一層會從特征庫加載特征(通過FeatureLoader)，應用模型(A/B測試配置分配)進行排序。

　　L3 業務規則干預

　　在L2排序的基礎上，應用業務規則/人工干預對排序進行適當調整。

　　Rank Service會將展示日志記錄到日志收集系統，供在線/離線處理。

　　A/B測試

　　A/B測試的流量切分是在Rank Server端完成的。我們根據UUID(用戶標識)將流量切分為多個桶(Bucket)，每個桶對應一種排序策略，桶內流量將使用相應的策略進行排序。使用UUID進行流量切分，是為了保證用戶體驗的一致性。

　　下面是A/B測試配置的一個簡單示例。

　　代碼如下:

　　{

　　"search": {

　　"NumberOfBuckets": 100,

　　"DefaultStrategy": "Base",

　　"Segments": [

　　{

　　"BeginBucket": 0,

　　"EndBucket": 24,

　　"WhiteList": [123],

　　"Strategy": "Algo-1"

　　},

　　{

　　"BeginBucket": 25,

　　"EndBucket": 49,

　　"WhiteList": [],

　　"Strategy": "Algo-2"

　　}

　　]

　　}

　　}

　　對于不合法的UUID，每次請求會隨機分配一個桶，以保證效果對比不受影響。白名單(White List)機制能保證配置用戶使用給定的策略，以輔助相關的測試。

　　除了A/B測試之外，我們還應用了Interleaving[7]方法，用于比較兩種排序算法。相較于A/B測試，Interleaving方法對排序算法更靈敏，能通過更少的樣本來比較兩種排序算法之間的優劣。Interleaving方法使用較小流量幫助我們快速淘汰較差算法，提高策略迭代效率。

　　特征加載

　　搜索排序服務涉及多種類型的特征，特征獲取和計算是Rank Service響應速度的瓶頸。我們設計了FeatureLoader模塊，根據特征依賴關系，并行地獲取和計算特征，有效地減少了特征加載時間。實際業務中，并行特征加載平均響應時間比串行特征加載快約20毫秒。

　　FeatureLoader的實現中我們使用了Akka[8]。如上圖所示，特征獲取和計算的被抽象和封裝為了若干個Akka actor，由Akka調度、并行執行。

　　特征和模型

　　美團從2013年9月開始在搜索排序上應用機器學習方法(Learning to Rank)，并且取得很大的收益。這得益于準確的數據標注：用戶的點擊下單支付等行為能有效地反映其偏好。通過在特征挖掘和模型優化兩方面的工作，我們不斷地優化搜索排序。下面將介紹我們在特征使用、數據標注、排序算法、Position Bias處理和冷啟動問題緩解等方面的工作。

　　特征

　　從美團業務出發，特征選取著眼于用戶、Query、Deal/POI和搜索上下文四個維度。

　　用戶維度

　　包括挖掘得到的品類偏好、消費水平和地理位置等。

　　Query維度

　　包括Query長度、歷史點擊率、轉化率和類型(商家詞/品類詞/地標詞)等。

　　Deal/POI維度

　　包括Deal/POI銷量、價格、評價、折扣率、品類和歷史轉化率等。

　　上下文維度

　　包括時間、搜索入口等。

　　此外，有的特征來自于幾個維度之間的相互關系：用戶對Deal/POI的點擊和下單等行為、用戶與POI的距離等是決定排序的重要因素;Query和Deal/POI的文本相關性和語義相關性是模型的關鍵特征。

　　模型

　　Learning to Rank應用中，我們主要采用了Pointwise方法。采用用戶的點擊、下單和支付等行為來進行正樣本的標注。從統計上看，點擊、下單和支付等行為分別對應了該樣本對用戶需求的不同的匹配程度，因此對應的樣本會被當做正樣本，且賦予不斷增大的權重。

　　線上運行著多種不同類型模型，主要包括：

　　Gradient boosting decision/regression tree(GBDT/GBRT)

　　GBDT是LTR中應用較多的非線性模型。我們開發了基于Spark的GBDT工具，樹擬合梯度的時候運用了并行方法，縮短訓練時間。GBDT的樹被設計為三叉樹，作為一種處理特征缺失的方法。

　　選擇不同的損失函數，boosting tree方法可以處理回歸問題和分類問題。應用中，我們選用了效果更好的logistic likelihood loss，將問題建模為二分類問題。

　　Logistic Regression(LR)

　　參考Facebook的paper[3]，我們利用GBDT進行部分LR特征的構建。用FTRL算法來在線訓練LR模型。

　　對模型的評估分為離線和線上兩部分。離線部分我們通過AUC(Area Under the ROC Curve)和MAP(Mean Average Precision)來評價模型，線上則通過A/B測試來檢驗模型的實際效果，兩項手段支撐著算法不斷的迭代優化。

　　冷啟動

　　在我們的搜索排序系統中，冷啟動問題表現為當新的商家、新的團購單錄入或新的用戶使用美團時，我們沒有足夠的數據用來推測用戶對產品的喜好。商家冷啟動是主要問題，我們通過兩方面手段來進行緩解。一方面，在模型中引入了文本相關性、品類相似度、距離和品類屬性等特征，確保在沒有足夠展示和反饋的前提下能較為準確地預測;另一方面，我們引入了Explore&Exploit機制，對新商家和團單給予適度的曝光機會，以收集反饋數據并改善預測。

　　Position Bias

　　在手機端，搜索結果的展現形式是列表頁，結果的展示位置會對用戶行為產生很大的影響。在特征挖掘和訓練數據標注當中，我們考慮了展示位置因素引入的偏差。例如CTR(click-through-rate)的統計中，我們基于Examination Model，去除展示位置帶來的影響。

　　線上篇總結

　　線上篇主要介紹了美團搜索排序系統線上部分的結構、算法和主要模塊。在后續文章里，我們會著重介紹排序系統離線部分的工作。

　　一個完善的線上線下系統是排序優化得以持續進行的基礎。基于業務對數據和模型上的不斷挖掘是排序持續改善的動力。我們仍在探索。

　　二、線下篇

　　針對美團90%的交易發生在移動端的業務特點，我們實現了一套適用于O2O業務的搜索排序技術方案，已在許多產品和子行業中得到應用。在之前的線上篇中，我們已經介紹了服務的框架、排序算法等。本文為線下篇，主要講述數據清洗、特征矩陣、監控系統、模型訓練和效果評估等模塊。

　　數據清洗

　　數據清洗的主要工作是為離線模型訓練準備標注數據，同時洗掉不合法數據。數據清洗的數據源主要有團購的曝光、點擊和下單。

　　整個數據清洗的流程如下：

　　序列化

　　曝光、點擊和下單數據從Hive表中讀取，采用schema的處理方式，可以直接根據日志字段名來抽取相應的字段，不受日志字段增加或者減少的影響。

　　曝光日志存儲了一次用戶行為的詳細信息，包括城市、地理位置、篩選條件及一些行為特征;點擊日志主要記錄了用戶點擊的POIID、點擊時間;下單日志記錄了用戶下單的POIID、下單時間和下單的金額。數據清洗模塊根據配置文件從數據源中抽取需要的字段，進行序列化(Serialization)之后存儲在HDFS上。

　　序列化的過程中，如果日志字段不合法或者單一用戶曝光、點擊或下單超出設定的閾值，相關日志都會被清洗掉，避免數據對模型訓練造成影響。

　　數據標注

　　數據序列化之后在HDFS上保存三份文本文件，分別是曝光(Impression)、點擊(Click)和下單(Order)。數據標注模塊根據globalid(一次搜索的全局唯一標示，類似于sessionid)和相應的團購id為key，將曝光、點擊和下單關聯起來，最終生成一份標注好是否被點擊、下單、支付的標注數據。同時這份標注數據攜帶了本次展現的詳細特征信息。

　　數據標注通過一次Map/Reduce來完成。

　　Map階段：Map的輸入為曝光、點擊和下單三種HDFS數據。 用三個Mapper分別處理三種日志。數據分發的key為globalid。其中，如果點擊和下單數據中的globalid字段為空("")，則丟棄該條日志(因為globalid為空無法和曝光日志join，會出現誤標注)。

　　Reduce階段：Reduce接收的key為globalid, values為具有相同globalid的曝光、點擊、下單數據List，遍歷該List, 如果

　　日志類型為曝光日志，則標記該globalid對應的曝光日志存在(imp_exist=true)。

　　日志類型為點擊日志，則將曝光日志的clicked字段置為1。

　　日志類型為下單日志，則將曝光日志的ordered字段置為1。

　　日志類型為下單日志，如果pay_account字段>0， 則將曝光日志的paid字段置為1。

　　遍歷List之后，如果imp_exist == true, 則將標注好的數據寫入HDFS， 否則丟棄。

　　數據標注的流程圖如下：

　　特征矩陣

　　特征矩陣的作用是提供豐富的特征集合，以方便在線和離線特征調研使用。

　　特征矩陣的生成

　　特征矩陣的生成框架為：

　　下面我們來詳細說明一下流程。

　　基礎特征按來源可分為三部分：

　　1、Hive表：有一些基礎特征存儲在Hive標注，如POI的名字、品類、團購數等。

　　2、離線計算：一些特征需要積累一段時間才能統計，如POI的點擊率、銷量等，這部分通過積累歷史數據，然后經過Map/Reduce處理得到。

　　3、HDFS：特征矩陣可能融合第三方服務的特征，一般第三方服務將產生的特征按照約定的格式存儲在HDFS上。

　　數據源統一格式為： poiid/dealid/bizareaid 't' name1:value1't' name2:value2...

　　特征合并模塊，將所有來源合并為一個大文件，通過feature conf配置的特征和特征順序，將特征序列化，然后寫入Hive表。

　　特征監控模塊每天監控特征的分布等是否異常。 特征矩陣的特征每日更新。

　　添加新的特征來源，只需要按照約定的格式生成數據源，配置路徑，可自動添加。

　　添加新特征，在feature conf文件末尾添加相應的特征名，特征名字和數據源中的特征name保持一致，最后修改相應的特征Hive表結構。

　　特征矩陣的使用

　　特征矩陣的使用框架為：

　　我們來詳細說明一下流程。

　　其中特征矩陣既提供在線的特征倉庫，又可提供離線的特征調研。線上服務需要大量的特征來對POI/DEAL質量打分，特征分散會造成服務取用特征很耗時，特征矩陣將特征整合，很好的解決了特征耗時的問題。一般調研一個新特征需要積累一段時間的數據，將特征放入特征矩陣，

　　然后和已有的數據進行融合，可方便的構造包含新特征的訓練數據。下面我們分別來看一下在線、離線和特征融合的流程。

　　在線使用

　　在線方面的使用主要是方便特征的獲取，將線上需要的特征納入特征矩陣統一管理，通過配置文件讀取特征矩陣的特征，封裝成Proto Buffers寫入Medis(美團自主構建的Redis集群，支持分布式和容錯)，通過Medis key批量讀取該key對應的特征，減少讀取Medis的次數，從而縮減特征獲取的時間，提高系統的性能。

　　特征矩陣在線使用框架如下：

　　流程說明：

　　序列化模塊通過特征配置文件從特征矩陣抽取需要的特征，調用protoBuffer Lib將特征封裝成protoBuffer的格式，寫入Medis。

　　線上通過featureLoader服務從Medis讀取數據，然后通過protoBufferLib反序列化數據，取到相應的特征值。

　　離線使用

　　離線方面的使用主要是方便調研新特征。如果從線上獲取新特征，由于需要積累訓練數據，特征調研的周期會變長;而如果將待調研的特征納入特征矩陣中，可以很方便地通過離線的方法調研特征的有效性，極大的縮短了特征調研的周期，提高開發效率和模型迭代的速度。

　　特征矩陣離線使用框架如下：

　　其中，從特征矩陣取出待調研的新特征，格式化為 joinKey 't' FeatureName:FeatureValue， 例如 12345 't' CTR:0.123，joinkey為poiid, 新特征為CTR，特征值為0.123。格式化后的新特征文件和標注好的rerank日志作為輸入，經過Map/Reduce處理生成新的標注日志，用于模型訓練。

　　特征融合

　　特征融合作用于離線特征調研，上篇我們提到數據標準會輸出擁有豐富特征的標注日志，特征融合的目的在于將待調研的新特征通過某一個joinkey 合并到在線特征列表中，從而在模型訓練中使用該特征。

　　特征融合的框架：

　　流程說明： 特征融合模塊可以指定任意一個或者多個join key，將離線特征加入在線特征列表。

　　監控系統

　　監控系統的目的是確保在線和離線任務的正常運行。監控系統按照作用范圍的不同又分為線上監控和離線監控。

　　線上監控

　　線上監控主要是監測收集的在線特征日志是否正常，線上特征監控主要檢測特征的覆蓋度、閾值范圍、分布異常三方面。

　　三方面的監控主要分以下幾個場景：

　　覆蓋度：監控特征的數據源是否存在或者有數據丟失。

　　閾值范圍：監控特征的閾值是否符合預期，防止因為生成特征的算法改變或者在線計算方法的不同等因素造成特征的最大值或者最小值發生比較明顯的變化，導致特征不可用。

　　分布異常：監控特征值的分布是否符合預期，主要防止因為獲取不到特征，使得特征都使用了默認值，而又沒有及時發現，導致線上模型預估出現偏差。分布異常主要用到了卡方距離[3]。

　　特征覆蓋度監控效果圖：

　　下圖是用戶到POI距離的覆蓋度監控。從圖中可以直觀的看出，該特征的覆蓋度約為75%，也即只有75%的用戶能得到距離特征，另外25%可能沒有開手機定位服務或者得不到POI的坐標。75%的覆蓋度是一個比較穩定的指標，如果覆蓋度變的很高或者很低都說明我們的系統出現了問題，而我們的監控系統能及時發現這種問題。

　　離線監控

　　離線監控主要檢測兩方面：1、離線任務是否按時完成及生成的數據是否正確。 2、特征矩陣特征的有效性。

　　當離線定時任務多達數十個的時候，很難每天去逐個檢查每個任務是否如期完成，這時候離線任務監控的重要性就凸顯出來。當前離線監控可以根據配置文件，監控需要關注的任務，以及這些任務生成的數據是否正常。如果不正常則發出報警給任務負責人，達到任務失敗能夠及時處理的目的。

　　特征矩陣監控的目的與在線特征的監控目的一樣，監控指標也相同，所不同的是因為監控數據的獲取不同，監控實現也不盡相同，這里不再贅述。

　　模型調研

　　模型訓練

　　模型訓練框架支持多種模型的訓練，將訓練數據格式化為模型需要的輸入格式。修改模型訓練的配置文件，就可以使用該框架訓練模型了。

　　模型訓練框架：

　　其中，頂層是訓練數據和測試數據的輸入層，該層是原始訓練和測試數據。

　　中間是模型訓練的框架，框架支持多個配置項，包括配置模型算法、相應的參數、數據源的輸入及模型的輸出等。

　　底層是多種模型的實現，算法之前相互獨立，每種算法封裝成獨立的jar，提供給模型訓練框架使用，目前支持的算法包括GBDT[4]、FTRL[5]。

　　為了實現模型的快速迭代，模型訓練支持在Spark上運行。

　　效果評估

　　模型的效果評估主要是對比新模型和老模型的效果，以評估結果來決定是否更新線上模型。

　　我們的系統支持兩種效果指標的評估，一種是AUC[1]，另一種是MAP。

　　MAP(Mean Average Precision)[2]是一種對搜索排序結果好壞評估的指標。

　　Prec@K 的定義： 設定閾值K，計算排序結果topK的相關度。

　　注：綠色表示搜索結果與搜索詞相關，紅色表示不相關。

　　AP(Average Precision)的定義： Average Precision = average of Prec@K

　　AP作為排序好壞的直觀理解

　　灰色表示與搜索相關的結果，在團購中表示被點擊的DEAL，從召回結果看Ranking#1要好于Ranking#2，反映在MAP指標上，Ranking#1的MAP值大于Ranking#2的MAP值。

　　所以可以簡單地使用AP值來衡量模型排序的好壞。

　　MAP的計算

　　對于多個query的搜索結果，MAP為這些搜索結果AP的均值。

　　實驗結果表明MAP作為排序指標，對模型好壞的評估起到很好的指導作用。

　　在AUC的近似計算方法中，主要考慮有多少對正負樣本組合中正樣本的得分大于負樣本的得分，與正樣本在排序中的具體位置沒有絕對的關系。當正負樣本的分布變化，如某一小部分正樣本得分變大，大部分正樣本得分變小，那么最終計算的AUC值可能沒有發生變化，但排序的結果卻發生了很大變化(大部分用戶感興趣的單子排在了后邊)。

　　因此AUC指標沒法直觀評估人對排序好壞的感受。