美團(tuán)技術(shù)解析

作者簡(jiǎn)介：超逸，美團(tuán)點(diǎn)評(píng)技術(shù)專家，主要負(fù)責(zé)外賣(mài)配送策略組機(jī)器學(xué)習(xí)策略迭代工作

1. 引言

ETA（Estimated time of Arrival，預(yù)計(jì)送達(dá)時(shí)間）是外賣(mài)配送場(chǎng)景中最重要的變量之一（如圖1）。我們對(duì)ETA預(yù)估的準(zhǔn)確度和合理度會(huì)對(duì)上億外賣(mài)用戶的訂單體驗(yàn)造成深遠(yuǎn)影響，這關(guān)系到用戶的后續(xù)行為和留存，是用戶后續(xù)下單意愿的壓艙石。

ETA在配送業(yè)務(wù)架構(gòu)中也具有重要地位，是配送運(yùn)單實(shí)時(shí)調(diào)度系統(tǒng)的關(guān)鍵參數(shù)。對(duì)ETA的準(zhǔn)確預(yù)估可以提升調(diào)度系統(tǒng)的效率，在有限的運(yùn)力中做到對(duì)運(yùn)單的合理分配。在保障用戶體驗(yàn)的同時(shí)，對(duì)ETA的準(zhǔn)確預(yù)估也可以幫助線下運(yùn)營(yíng)構(gòu)建有效可行的配送考核指標(biāo)，保障騎手的體驗(yàn)和收益。

圖1 ETA的業(yè)務(wù)價(jià)值

最近幾年，ETA在互聯(lián)網(wǎng)行業(yè)中的運(yùn)用取得了令人矚目的進(jìn)展，其中以外賣(mài)行業(yè)和打車(chē)行業(yè)最令人關(guān)注。但與打車(chē)行業(yè)相比，ETA在外賣(mài)行業(yè)中的業(yè)務(wù)場(chǎng)景更為復(fù)雜。如圖2所示，從業(yè)務(wù)要素來(lái)看，打車(chē)涉及到兩方——乘客和司機(jī)，而外賣(mài)行業(yè)則涉及了三方——騎手、商家、用戶，這使得問(wèn)題的處理難度提升了一個(gè)量級(jí)。

從業(yè)務(wù)的環(huán)節(jié)來(lái)看，打車(chē)分為派單、接人、送達(dá)三個(gè)環(huán)節(jié)，是一個(gè)司機(jī)接單到達(dá)指定地點(diǎn)接送乘客到達(dá)目的地的過(guò)程；而外賣(mài)則主要分為接單、到店、取餐、送達(dá)四個(gè)環(huán)節(jié)，是一個(gè)用戶、騎手、商家來(lái)回交錯(cuò)的場(chǎng)景。

業(yè)務(wù)環(huán)節(jié)的增加帶來(lái)了更多的復(fù)雜性和不確定性，如騎手操作在各個(gè)環(huán)節(jié)中存在較多的不可控因素，商家可能出餐較慢，此外還有運(yùn)力規(guī)劃和天氣因素的不確定性等，這就直接導(dǎo)致了外賣(mài)ETA采取了端到端（下單到接單）的預(yù)估方式，相比于拆分成四個(gè)環(huán)節(jié)單獨(dú)預(yù)估具有更強(qiáng)的容錯(cuò)性。無(wú)論從業(yè)務(wù)所涉及的要素還是從業(yè)務(wù)環(huán)節(jié)來(lái)看，外賣(mài)業(yè)務(wù)的復(fù)雜程度遠(yuǎn)遠(yuǎn)高于打車(chē)業(yè)務(wù)，對(duì)ETA預(yù)估的難度更大。

圖2 ETA架構(gòu)圖

ETA中比較常用的模型是以GBDT（Gradient Boost Decision Tree，梯度提升決策樹(shù)）、RF（RandomForest，隨機(jī)森林）和線性回歸為主的回歸預(yù)測(cè)模型。

GBDT是利用DT Boosting的思路，通過(guò)梯度求解的方式追蹤殘差，最終達(dá)到利用弱分類器（回歸器）構(gòu)造強(qiáng)分類器（回歸器）的目的。RF在DT Bagging的基礎(chǔ)之上通過(guò)加入樣本隨機(jī)和特征隨機(jī)的方式引入更多的隨機(jī)性，解決了決策樹(shù)泛化能力弱的問(wèn)題。而線性回歸作為線性模型，很容易并行化，處理上億條訓(xùn)練樣本不是問(wèn)題。但線性模型學(xué)習(xí)能力有限，需要大量特征工程預(yù)先分析出有效的特征、特征組合，從而去間接增強(qiáng)線性回歸的線性學(xué)習(xí)能力。

在回歸模型中，特征組合非常重要，但只依靠業(yè)務(wù)理解和人工經(jīng)驗(yàn)不一定能帶來(lái)效果提升，這導(dǎo)致在實(shí)際應(yīng)用中存在特征匱乏的問(wèn)題。所以如何發(fā)現(xiàn)、構(gòu)造、組合有效特征，并彌補(bǔ)人工經(jīng)驗(yàn)的不足，成了ETA中重要的一環(huán)。

2. GBDT構(gòu)造特征現(xiàn)狀

Facebook 2014年的文章介紹了通過(guò)GBDT解決LR的特征組合問(wèn)題。[1]GBDT思想對(duì)于發(fā)現(xiàn)多種有區(qū)分性的特征和組合特征具有天然優(yōu)勢(shì)，可以用來(lái)構(gòu)造新的組合特征。在Facebook的文章中，會(huì)基于樣本在GBDT中的輸出節(jié)點(diǎn)索引位置構(gòu)造0-1特征，實(shí)現(xiàn)特征的豐富化。新構(gòu)造的0-1特征中，每一個(gè)特征對(duì)應(yīng)樣本在每棵樹(shù)中可能的輸出位置，它們代表著某些特征的某種邏輯組合。例如一棵樹(shù)有n個(gè)葉子節(jié)點(diǎn)，當(dāng)樣本在第k個(gè)葉子節(jié)點(diǎn)輸出時(shí)，則第k個(gè)特征輸出1，其余n-1個(gè)特征輸出0，如圖3所示。

圖3 GBDT(Gradient Boost Decision Tree)特征構(gòu)造方法

至于構(gòu)造新特征的規(guī)模，需要由具體業(yè)務(wù)規(guī)模而決定。當(dāng)GBDT中樹(shù)的數(shù)量較多或樹(shù)深較深時(shí)，構(gòu)造的特征規(guī)模也會(huì)大幅增加；當(dāng)業(yè)務(wù)中所用的數(shù)據(jù)規(guī)模較小時(shí)，大規(guī)模的構(gòu)造新特征會(huì)導(dǎo)致后續(xù)訓(xùn)練模型存在過(guò)擬合的可能。所以構(gòu)造特征的規(guī)模需要足夠合理。

3. GBDT構(gòu)造特征在ETA場(chǎng)景中的應(yīng)用方案

在ETA場(chǎng)景中，由于業(yè)務(wù)場(chǎng)景復(fù)雜，所以特征的豐富性決定了ETA最終效果的上限。在目前所擁有的特征中，在特征工程的基礎(chǔ)階段，我們依靠業(yè)務(wù)理解、人工分析和經(jīng)驗(yàn)總結(jié)來(lái)構(gòu)造特征。但從特征層面來(lái)看仍然存在欠缺，需要讓特征更加豐富化，深度挖掘特征之間的潛在價(jià)值。

3.1 基礎(chǔ)特征構(gòu)建

圖4 基礎(chǔ)特征構(gòu)成

特征作為ETA中的重要部分，決定了ETA的上限。我們基于人工經(jīng)驗(yàn)和業(yè)務(wù)理解構(gòu)建了不同的離線特征和在線特征。

離線特征

• 商戶畫(huà)像：商戶平均送達(dá)時(shí)長(zhǎng)、到店時(shí)長(zhǎng)、取餐時(shí)長(zhǎng)、出餐狀況、單量、種類偏好、客單價(jià)、平均配送距離。

• 配送區(qū)域畫(huà)像：區(qū)域運(yùn)力平均水平、騎手規(guī)模、單量規(guī)模、平均配送距離。

在線特征

• 商家實(shí)時(shí)特征：商家訂單擠壓狀況、過(guò)去N分鐘出單量、過(guò)去N分鐘進(jìn)單量。區(qū)域?qū)崟r(shí)特征：在崗騎手實(shí)時(shí)規(guī)模、區(qū)域擠壓（未取餐）單量、運(yùn)力負(fù)載狀況。訂單特征：配送距離、價(jià)格、種類、時(shí)段。天氣數(shù)據(jù)：溫度、氣壓、降水量。

其中區(qū)域?qū)崟r(shí)特征和商家實(shí)時(shí)特征與配送運(yùn)力息息相關(guān)，運(yùn)力是決定配送時(shí)長(zhǎng)和用戶體驗(yàn)的重要因素。

3.2 GBDT模型訓(xùn)練和特征構(gòu)造

利用基礎(chǔ)特征，訓(xùn)練用于構(gòu)造新特征的GBDT模型。在GBDT中，我們每次訓(xùn)練一個(gè)CART（Classification And Regression Trees）回歸樹(shù)，基于當(dāng)前輪次CART樹(shù)的損失函數(shù)的逆向梯度，擬合下一個(gè)CART樹(shù)，直到滿足要求為止。

超參數(shù)選擇

• 首先為了節(jié)點(diǎn)分裂時(shí)質(zhì)量和隨機(jī)性，分裂時(shí)所使用的最大特征數(shù)目為√n。

• GBDT迭代次數(shù)（樹(shù)的數(shù)量）。

• 樹(shù)的數(shù)量決定了后續(xù)構(gòu)造特征的規(guī)模，與學(xué)習(xí)速率相互對(duì)應(yīng)。通常學(xué)習(xí)速率設(shè)置較小，但如果過(guò)小，會(huì)導(dǎo)致迭代次數(shù)大幅增加，使得新構(gòu)造的特征規(guī)模過(guò)大。

• 通過(guò)GridSearch+CrossValidation可以尋找到最合適的迭代次數(shù)+學(xué)習(xí)速率的超參組合。c. GBDT樹(shù)深度需要足夠合理，通常在4~6較為合適。

• 雖然增加樹(shù)的數(shù)量和深度都可以增加新構(gòu)造的特征規(guī)模。但樹(shù)深度過(guò)大，會(huì)造成模型過(guò)擬合以及導(dǎo)致新構(gòu)造特征過(guò)于稀疏。

訓(xùn)練方案

將訓(xùn)練數(shù)據(jù)隨機(jī)抽樣50%，一分為二。前50%用于訓(xùn)練GBDT模型，后50%的數(shù)據(jù)在通過(guò)GBDT輸出樣本在每棵樹(shù)中輸出的葉子節(jié)點(diǎn)索引位置，并記錄存儲(chǔ)，用于后續(xù)的新特征的構(gòu)造和編碼，以及后續(xù)模型的訓(xùn)練。如樣本x通過(guò)GBDT輸出后得到的形式如下：x → [25,20,22,....,30,28] ，列表中表示樣本在GBDT每個(gè)樹(shù)中輸出的葉子節(jié)點(diǎn)索引位置。

3.3 OneHotEncoder（新特征熱編碼）

圖5 OneHotEncoder（新特征熱編碼）使用方法

由于樣本經(jīng)過(guò)GBDT輸出后得到的x → [25,20,22,....,30,28] 是一組新特征，但由于這組新特征是葉子節(jié)點(diǎn)的ID，其值不能直接表達(dá)任何信息，故不能直接用于ETA場(chǎng)景的預(yù)估。為了解決上述的問(wèn)題，避免訓(xùn)練過(guò)程中無(wú)用信息對(duì)模型產(chǎn)生的負(fù)面影響，需要通過(guò)獨(dú)熱碼（OneHotEncoder）的編碼方式對(duì)新特征進(jìn)行處理，將新特征轉(zhuǎn)化為可用的0-1的特征。

以圖5中的第一棵樹(shù)和第二棵樹(shù)為例，第一棵樹(shù)共有三個(gè)葉子節(jié)點(diǎn)，樣本會(huì)在三個(gè)葉子節(jié)點(diǎn)的其中之一輸出。所以樣本在該棵樹(shù)有會(huì)有可能輸出三個(gè)不同分類的值，需要由3個(gè)bit值來(lái)表達(dá)樣本在該樹(shù)中輸出的含義。圖中樣本在第一棵樹(shù)的第一個(gè)葉子節(jié)點(diǎn)輸出，獨(dú)熱碼表示為{100}；而第二棵樹(shù)有四個(gè)葉子節(jié)點(diǎn)，且樣本在第三個(gè)葉子節(jié)點(diǎn)輸出，則表示為{0010}。將樣本在每棵樹(shù)的獨(dú)熱碼拼接起來(lái)，表示為{1000010}，即通過(guò)兩棵CART樹(shù)構(gòu)造了7個(gè)特征，構(gòu)造特征的規(guī)模與GBDT中CART樹(shù)的葉子節(jié)點(diǎn)規(guī)模直接相關(guān)。

基于獨(dú)熱碼編碼新特征完成后，加上原來(lái)的基礎(chǔ)特征，特征規(guī)模達(dá)到1000+以上，實(shí)現(xiàn)特征豐富化。

4. 評(píng)估指標(biāo)與實(shí)踐效果

4.1 評(píng)估指標(biāo)

與傳統(tǒng)的回歸問(wèn)題不同，ETA與實(shí)際業(yè)務(wù)深度耦合，所以需要基于業(yè)務(wù)因素考慮更多的評(píng)估指標(biāo)，以滿足各端（C端、R端）用戶利益。

N分鐘準(zhǔn)確率

訂單實(shí)際送達(dá)時(shí)長(zhǎng)與預(yù)估時(shí)長(zhǎng)的絕對(duì)誤差在N分鐘內(nèi)的概率。

• 業(yè)務(wù)含義:

在N分鐘準(zhǔn)確率中，N的判定方法來(lái)源于絕對(duì)誤差與用戶滿意度的關(guān)系曲線。通常絕對(duì)誤差在一定范圍內(nèi)，用戶滿意度不會(huì)有明顯波動(dòng)。如果發(fā)現(xiàn)當(dāng)誤差大于K分鐘時(shí)，用戶滿意度出現(xiàn)明顯下滑，則可以將K做為N分鐘準(zhǔn)確率中N的取值依據(jù)。

預(yù)估時(shí)長(zhǎng)等同于平臺(tái)提供給C端用戶對(duì)送餐快慢的心理預(yù)期，如果N分鐘準(zhǔn)確率越高，證明預(yù)估時(shí)長(zhǎng)愈發(fā)接近用戶的心理預(yù)期，表示C端用戶體驗(yàn)越好。

• 計(jì)算方法:

Xi：樣本i的絕對(duì)誤差=abs(實(shí)際送達(dá)時(shí)長(zhǎng)-預(yù)估時(shí)長(zhǎng))。

計(jì)算每個(gè)樣本的誤差的是否在N分鐘內(nèi)，并統(tǒng)計(jì)概率P(Xi <= N)，如圖6、圖7所示。

圖6 判定訂單預(yù)估是否準(zhǔn)確的計(jì)算方法

圖7 N分鐘準(zhǔn)確率計(jì)算方法

N分鐘業(yè)務(wù)準(zhǔn)時(shí)率

實(shí)際送達(dá)時(shí)長(zhǎng)與預(yù)估時(shí)長(zhǎng)的差值在N分鐘內(nèi)的概率。

• 業(yè)務(wù)含義

N分鐘業(yè)務(wù)準(zhǔn)時(shí)率中N的判定方法與N分鐘準(zhǔn)確率類似。

N分鐘業(yè)務(wù)準(zhǔn)時(shí)率是一種合理考核騎手以及保障騎手績(jī)效收益的指標(biāo)。ETA場(chǎng)景與其它回歸場(chǎng)景相比，在預(yù)估準(zhǔn)確的同時(shí)，預(yù)估合理性同樣很重要。N分鐘準(zhǔn)確率雖然有效地量化C端用戶體驗(yàn)指標(biāo)，但無(wú)法衡量R端騎手體驗(yàn)。所以N分鐘業(yè)務(wù)準(zhǔn)時(shí)率是一個(gè)很好的補(bǔ)充指標(biāo)。

• 計(jì)算方法

Xi，樣本i的有偏差值=(實(shí)際送達(dá)時(shí)長(zhǎng)-預(yù)估時(shí)長(zhǎng))。

若Xi < 0 ，表示騎手提前送達(dá)，等同于業(yè)務(wù)準(zhǔn)時(shí)。

若0 < Xi <= N ， 表示騎手在超時(shí)N分鐘內(nèi)送達(dá)，等同于業(yè)務(wù)準(zhǔn)時(shí)；但如果Xi > N ，表示騎手超時(shí)N分鐘以上送達(dá)，從指標(biāo)層面看，該訂單騎手配送業(yè)務(wù)超時(shí)。

統(tǒng)計(jì)訂單配送不超時(shí)的概率P(Xi <= N)，計(jì)算方法與N分鐘準(zhǔn)確率(圖7)類似。

4.2 實(shí)踐效果對(duì)比

我們?cè)诖酥耙呀?jīng)做了很多特征工程和優(yōu)化方面的工作，本次我們?cè)诓辉黾尤魏晤~外特征的情況下，僅通過(guò)模型架構(gòu)的變化進(jìn)行優(yōu)化。在對(duì)全量訂單進(jìn)行評(píng)估對(duì)比的同時(shí)，我們對(duì)一些高價(jià)值和午高峰期間的訂單進(jìn)行重點(diǎn)評(píng)估。

① 高價(jià)值訂單：高價(jià)值訂單僅占全量訂單的5%。這部分訂單用戶滿意度較低、配送體驗(yàn)較差，屬于長(zhǎng)尾訂單范疇，優(yōu)化難度高于其它類型訂單。

② 午高峰訂單：午高峰運(yùn)單業(yè)務(wù)占比高達(dá)40%。午高峰期間，商家存在堂食和外賣(mài)資源爭(zhēng)搶問(wèn)題，造成出餐時(shí)間不穩(wěn)定，導(dǎo)致業(yè)務(wù)中存在更多不確定性，預(yù)估難度明顯大于非高峰期。

將GBDT構(gòu)造特征+Ridge與老版本base model（GBDT）進(jìn)行對(duì)比。從結(jié)果上來(lái)看，構(gòu)造新特征后，可以對(duì)ETA預(yù)估帶來(lái)更好的效果，其中在高價(jià)值訂單中，騎手的N分鐘業(yè)務(wù)準(zhǔn)時(shí)率提升顯著。具體結(jié)論如下：

① 全量訂單：平均偏差(MAE)減少了3.4%，誤差率減少1.7個(gè)百分點(diǎn)，N分鐘準(zhǔn)確率提升2.2個(gè)百分點(diǎn)，N分鐘業(yè)務(wù)準(zhǔn)時(shí)率持平。

② 高價(jià)值訂單：平均偏差(MAE)減少了2.56%，誤差率減少1個(gè)百分點(diǎn)，N分鐘準(zhǔn)確率提升1.6個(gè)百分點(diǎn)，N分鐘業(yè)務(wù)準(zhǔn)時(shí)率提升3.46個(gè)百分點(diǎn)。

③ 午高峰訂單：平均偏差(MAE)減少了3.1%，誤差率減少1.4個(gè)百分點(diǎn)，N分鐘準(zhǔn)確率提升1.7個(gè)百分點(diǎn)，N分鐘業(yè)務(wù)準(zhǔn)時(shí)率持平。

從上述效果來(lái)看，GBDT構(gòu)造特征可以給ETA場(chǎng)景帶來(lái)更多的提升，在線上使用時(shí)，也需要在性能和構(gòu)造特征的規(guī)模上做出取舍。考慮到騎手的主觀能動(dòng)性等因素，通常上線后，線上效果比線下試驗(yàn)效果要更加樂(lè)觀。

總結(jié)

ETA 作為是外賣(mài)配送場(chǎng)景中最重要變量之一，是一個(gè)復(fù)雜程度較高的機(jī)器學(xué)習(xí)問(wèn)題，其特征的豐富性決定了ETA的上限。在業(yè)務(wù)特征相對(duì)匱乏的情況下，GBDT+OneHotEncoder可以實(shí)現(xiàn)特征的豐富化，深度挖掘出特征的潛在價(jià)值。實(shí)驗(yàn)結(jié)果顯示，在特征豐富化的情況下，ETA的準(zhǔn)確度明顯提高。

與此同時(shí)，我們也在嘗試進(jìn)行更多的探索。我們認(rèn)為時(shí)序關(guān)系也是ETA場(chǎng)景的重要特征，并嘗試將該關(guān)系特征化加入到目前的模型和策略中，改善特征質(zhì)量，提高ETA的預(yù)估能力上限。同時(shí)引入深度學(xué)習(xí)和增強(qiáng)學(xué)習(xí)，在提高上限的同時(shí)，用更好的模型去接近這個(gè)新的預(yù)估上限，為ETA的場(chǎng)景提升打下堅(jiān)實(shí)的基礎(chǔ)。

參考文獻(xiàn)

1.He X, Pan J, Jin O, et al. Practical Lessons from Predicting Clicks on Ads at Facebook[C]. Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 2014: 1-9.

2.https://www.csie.ntu.edu.tw/~r01922136/kaggle-2014-criteo.pdf.

3.GitHub，guestwalk.