即時配送的ETA問題之億級樣本特徵構造實踐

01-31

引言

ETA（Estimated time of Arrival，預計送達時間）是外賣配送場景中最重要的變數之一（如圖1）。我們對ETA預估的準確度和合理度會對上億外賣用戶的訂單體驗造成深遠影響，這關係到用戶的後續行為和留存，是用戶後續下單意願的壓艙石。ETA在配送業務架構中也具有重要地位，是配送運單實時調度系統的關鍵參數。對ETA的準確預估可以提升調度系統的效率，在有限的運力中做到對運單的合理分配。在保障用戶體驗的同時，對ETA的準確預估也可以幫助線下運營構建有效可行的配送考核指標，保障騎手的體驗和收益。

圖1. ETA的業務價值

最近幾年，ETA在互聯網行業中的運用取得了令人矚目的進展，其中以外賣行業和打車行業最令人關注。但與打車行業相比，ETA在外賣行業中的業務場景更為複雜。如圖2所示，從業務要素來看，打車涉及到兩方——乘客和司機，而外賣行業則涉及了三方——騎手、商家、用戶，這使得問題的處理難度提升了一個量級。從業務的環節來看，打車分為派單、接人、送達三個環節，是一個司機接單到達指定地點接送乘客到達目的地的過程；而外賣則主要分為接單、到店、取餐、送達四個環節，是一個用戶、騎手、商家來回交錯的場景。業務環節的增加帶來了更多的複雜性和不確定性，如騎手操作在各個環節中存在較多的不可控因素，商家可能出餐較慢，此外還有運力規劃和天氣因素的不確定性等，這就直接導致了外賣ETA採取了端到端（下單到接單）的預估方式，相比於拆分成四個環節單獨預估具有更強的容錯性。無論從業務所涉及的要素還是從業務環節來看，外賣業務的複雜程度遠遠高於打車業務，對ETA預估的難度更大。

圖2. ETA架構圖

ETA中比較常用的模型是以GBDT（Gradient Boost Decision Tree，梯度提升決策樹）、RF（RandomForest，隨機森林）和線性回歸為主的回歸預測模型。GBDT是利用DT Boosting的思路，通過梯度求解的方式追蹤殘差，最終達到利用弱分類器（回歸器）構造強分類器（回歸器）的目的。RF在DT Bagging的基礎之上通過加入樣本隨機和特徵隨機的方式引入更多的隨機性，解決了決策樹泛化能力弱的問題。而線性回歸作為線性模型，很容易並行化，處理上億條訓練樣本不是問題。但線性模型學習能力有限，需要大量特徵工程預先分析出有效的特徵、特徵組合，從而去間接增強線性回歸的線性學習能力。

在回歸模型中，特徵組合非常重要，但只依靠業務理解和人工經驗不一定能帶來效果提升，這導致在實際應用中存在特徵匱乏的問題。所以如何發現、構造、組合有效特徵，並彌補人工經驗的不足，成了ETA中重要的一環。

GBDT構造特徵現狀

Facebook 2014年的文章介紹了通過GBDT解決LR的特徵組合問題。[1]GBDT思想對於發現多種有區分性的特徵和組合特徵具有天然優勢，可以用來構造新的組合特徵。在Facebook的文章中，會基於樣本在GBDT中的輸出節點索引位置構造0-1特徵，實現特徵的豐富化。新構造的0-1特徵中，每一個特徵對應樣本在每棵樹中可能的輸出位置，它們代表著某些特徵的某種邏輯組合。例如一棵樹有n個葉子節點，當樣本在第k個葉子節點輸出時，則第k個特徵輸出1，其餘n-1個特徵輸出0，如圖3所示。

圖3. GBDT(Gradient Boost Decision Tree)特徵構造方法

至於構造新特徵的規模，需要由具體業務規模而決定。當GBDT中樹的數量較多或樹深較深時，構造的特徵規模也會大幅增加；當業務中所用的數據規模較小時，大規模的構造新特徵會導致後續訓練模型存在過擬合的可能。所以構造特徵的規模需要足夠合理。

GBDT構造特徵在ETA場景的中的應用方案

在ETA場景中，由於業務場景複雜，所以特徵的豐富性決定了ETA最終效果的上限。在目前所擁有的特徵中，在特徵工程的基礎階段，我們依靠業務理解、人工分析和經驗總結來構造特徵。但從特徵層面來看仍然存在欠缺，需要讓特徵更加豐富化，深度挖掘特徵之間的潛在價值。

基礎特徵構建

圖4. 基礎特徵構成

特徵作為ETA中的重要部分，決定了ETA的上限。我們基於人工經驗和業務理解構建了不同的離線特徵和在線特徵。

(1) 離線特徵

a. 商戶畫像：商戶平均送達時長、到店時長、取餐時長、出餐狀況、單量、種類偏好、客單價、平均配送距離。

b. 配送區域畫像：區域運力平均水平、騎手規模、單量規模、平均配送距離。

(2) 在線特徵

a. 商家實時特徵：商家訂單擠壓狀況、過去N分鐘出單量、過去N分鐘進單量。

b. 區域實時特徵：在崗騎手實時規模、區域擠壓（未取餐）單量、運力負載狀況。

c. 訂單特徵：配送距離、價格、種類、時段。

d. 天氣數據：溫度、氣壓、降水量。

其中區域實時特徵和商家實時特徵與配送運力息息相關，運力是決定配送時長和用戶體驗的重要因素。

GBDT模型訓練和特徵構造

利用基礎特徵，訓練用於構造新特徵的GBDT模型。在GBDT中，我們每次訓練一個CART（Classification And Regression Trees）回歸樹，基於當前輪次CART樹的損失函數的逆向梯度，擬合下一個CART樹，直到滿足要求為止。

(1) 超參數選擇

a. 首先為了節點分裂時質量和隨機性，分裂時所使用的最大特徵數目為√n。

b. GBDT迭代次數（樹的數量）。

樹的數量決定了後續構造特徵的規模，與學習速率相互對應。通常學習速率設置較小，但如果過小，會導致迭代次數大幅增加，使得新構造的特徵規模過大。
通過GridSearch+CrossValidation可以尋找到最合適的迭代次數+學習速率的超參組合。
c. GBDT樹深度需要足夠合理，通常在4~6較為合適。
雖然增加樹的數量和深度都可以增加新構造的特徵規模。但樹深度過大，會造成模型過擬合以及導致新構造特徵過於稀疏。

(2) 訓練方案

將訓練數據隨機抽樣50%，一分為二。前50%用於訓練GBDT模型，後50%的數據在通過GBDT輸出樣本在每棵樹中輸出的葉子節點索引位置，並記錄存儲，用於後續的新特徵的構造和編碼，以及後續模型的訓練。如樣本x通過GBDT輸出後得到的形式如下：x → [25,20,22,....,30,28] ，列表中表示樣本在GBDT每個樹中輸出的葉子節點索引位置。

OneHotEncoder（新特徵熱編碼）

圖5. OneHotEncoder(新特徵熱編碼)使用方法

由於樣本經過GBDT輸出後得到的x → [25,20,22,....,30,28] 是一組新特徵，但由於這組新特徵是葉子節點的ID，其值不能直接表達任何信息，故不能直接用於ETA場景的預估。為了解決上述的問題，避免訓練過程中無用信息對模型產生的負面影響，需要通過獨熱碼（OneHotEncoder）的編碼方式對新特徵進行處理，將新特徵轉化為可用的0-1的特徵。

以圖5中的第一棵樹和第二棵樹為例，第一棵樹共有三個葉子節點，樣本會在三個葉子節點的其中之一輸出。所以樣本在該棵樹有會有可能輸出三個不同分類的值，需要由3個bit值來表達樣本在該樹中輸出的含義。圖中樣本在第一棵樹的第一個葉子節點輸出，獨熱碼錶示為{100}；而第二棵樹有四個葉子節點，且樣本在第三個葉子節點輸出，則表示為{0010}。將樣本在每棵樹的獨熱碼拼接起來，表示為{1000010}，即通過兩棵CART樹構造了7個特徵，構造特徵的規模與GBDT中CART樹的葉子節點規模直接相關。

基於獨熱碼編碼新特徵完成後，加上原來的基礎特徵，特徵規模達到1000+以上，實現特徵豐富化。

評估指標與實踐效果

評估指標

與傳統的回歸問題不同，ETA與實際業務深度耦合，所以需要基於業務因素考慮更多的評估指標，以滿足各端（C端、R端）用戶利益。

① N分鐘準確率：訂單實際送達時長與預估時長的絕對誤差在N分鐘內的概率。

業務含義:

在N分鐘準確率中，N的判定方法來源於絕對誤差與用戶滿意度的關係曲線。通常絕對誤差在一定範圍內，用戶滿意度不會有明顯波動。如果發現當誤差大於K分鐘時，用戶滿意度出現明顯下滑，則可以將K做為N分鐘準確率中N的取值依據。
預估時長等同於平台提供給C端用戶對送餐快慢的心理預期，如果N分鐘準確率越高，證明預估時長愈發接近用戶的心理預期，表示C端用戶體驗越好。

計算方法:

Xi：樣本i的絕對誤差=abs(實際送達時長-預估時長)。
計算每個樣本的誤差的是否在N分鐘內，並統計概率P(Xi <= N)，如圖6、圖7所示。

圖6.判定訂單預估是否準確的計算方法

圖7.N分鐘準確率計算方法

② N分鐘業務準時率：實際送達時長與預估時長的差值在N分鐘內的概率。

業務含義：

N分鐘業務準時率中N的判定方法與N分鐘準確率類似。
N分鐘業務準時率是一種合理考核騎手以及保障騎手績效收益的指標。ETA場景與其它回歸場景相比，在預估準確的同時，預估合理性同樣很重要。N分鐘準確率雖然有效地量化C端用戶體驗指標，但無法衡量R端騎手體驗。所以N分鐘業務準時率是一個很好的補充指標。

計算方法：

Xi，樣本i的有偏差值=(實際送達時長-預估時長)。
若Xi < 0 ，表示騎手提前送達，等同於業務準時。
若0 < Xi <= N ，表示騎手在超時N分鐘內送達，等同於業務準時；但如果Xi > N ，表示騎手超時N分鐘以上送達，從指標層面看，該訂單騎手配送業務超時。
統計訂單配送不超時的概率P(Xi <= N)，計算方法與N分鐘準確率(圖7)類似。

實踐效果對比

我們在此之前已經做了很多特徵工程和優化方面的工作，本次我們在不增加任何額外特徵的情況下，僅通過模型架構的變化進行優化。在對全量訂單進行評估對比的同時，我們對一些高價值和午高峰期間的訂單進行重點評估。

① 高價值訂單：高價值訂單僅佔全量訂單的5%。這部分訂單用戶滿意度較低、配送體驗較差，屬於長尾訂單範疇，優化難度高於其它類型訂單。

② 午高峰訂單：午高峰運單業務佔比高達40%。午高峰期間，商家存在堂食和外賣資源爭搶問題，造成出餐時間不穩定，導致業務中存在更多不確定性，預估難度明顯大於非高峰期。

將GBDT構造特徵+Ridge與老版本base model（GBDT）進行對比。從結果上來看，構造新特徵後，可以對ETA預估帶來更好的效果，其中在高價值訂單中，騎手的N分鐘業務準時率提升顯著。具體結論如下：

① 全量訂單

平均偏差(MAE)減少了3.4%，誤差率減少1.7個百分點，N分鐘準確率提升2.2個百分點，N分鐘業務準時率持平。

② 高價值訂單

平均偏差(MAE)減少了2.56%，誤差率減少1個百分點，N分鐘準確率提升1.6個百分點，N分鐘業務準時率提升3.46個百分點。

③ 午高峰訂單

平均偏差(MAE)減少了3.1%，誤差率減少1.4個百分點，N分鐘準確率提升1.7個百分點，N分鐘業務準時率持平。

從上述效果來看，GBDT構造特徵可以給ETA場景帶來更多的提升，在線上使用時，也需要在性能和構造特徵的規模上做出取捨。考慮到騎手的主觀能動性等因素，通常上線後，線上效果比線下試驗效果要更加樂觀。

總結

ETA 作為是外賣配送場景中最重要變數之一，是一個複雜程度較高的機器學習問題，其特徵的豐富性決定了ETA的上限。在業務特徵相對匱乏的情況下，GBDT+OneHotEncoder可以實現特徵的豐富化，深度挖掘出特徵的潛在價值。實驗結果顯示，在特徵豐富化的情況下，ETA的準確度明顯提高。

與此同時，我們也在嘗試進行更多的探索。我們認為時序關係也是ETA場景的重要特徵，並嘗試將該關係特徵化加入到目前的模型和策略中，改善特徵質量，提高ETA的預估能力上限。同時引入深度學習和增強學習，在提高上限的同時，用更好的模型去接近這個新的預估上限，為ETA的場景提升打下堅實的基礎。

參考文獻

[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.

招聘

美團外賣配送策略組長期招聘機器學習領域有識之士。come on，快到我碗里來！簡歷發送至郵箱：gaojiuchong#http://meituan.com