90％的預測準確率覆蓋30％的訂單，滴滴出行「猜您要去」目的地預測系統是怎麼做的？

作者｜張凌宇

編輯｜小智

「猜你想去」是滴滴出行大數據智能預測體系的主要功能之一。通過此功能，滴滴可為一些大型商超、火車站等人流密集場所提供出行解決方案建議。目前「猜你想去」功能已覆蓋了滴滴平台上 30% 的訂單，預測準確率達 90%。與「猜你想去」功能相關的專利也已提交受理。

1

寫在前面

滴滴的「猜您去哪」目的地預測系統是我們的一個非常酷炫的系統，背後有著強勁的演算法和技術支撐。

當用戶打開滴滴出行 app 的時候，如果我們的系統能夠猜用戶即將去往的目的地，就會填寫到「猜您要去」的框中。大多數用戶評論這個功能的時候，都會說我們猜的是準的，很酷炫。

這個功能有什麼用呢？我們在設計這個功能的時候，有這麼幾個出發點：一是要能方便用戶，降低用戶發單時候的輸入成本；二是要驚艷用戶，彰顯滴滴的人工智慧科技，以 90% 以上的準確率，預測 30% 以上的出行；三是預測人群的出行流向，從而更好的規劃交通運力。

下面會從我們問題定義、模型抽象、用數據統計求解模型以及數據分享等幾個方面進行介紹。

2

定義問題：從業務場景到模型抽象

研發工程師每天都會面對的一個場景，就是產品經理提需求。當時我們是把需求定義成這樣一個問題：通過用戶的出行歷史，預測用戶當前時間、當前地點下的出行目的地。

有了問題定義之後接下來就是要把這個問題抽象成預測模型。T 是當前時間，S 是當前位置，X 是預測目的地，我在當前時間、當前地點出發，在這個條件下用戶即將去往的那個目的地條件概率應該是遠遠大於他去其他地方的概率。比如說今天晚上九點我在酒店打開滴滴出行 APP，如果查出我去虹橋機場的遠遠大於外灘的概率，那麼這個系統就猜去我去虹橋機場。這是一個條件概率的問題。

3

從 0 到 1 快速搭建模型：基於互信息選擇主要特徵

有了模型之後，我們由簡單到複雜地從 0 到 1 快速搭建系統。目的地是待預測的變數，時間變數是一個複合變數，包含日期和時刻，比如日期為 2016 年 8 月 23 日，時刻是 18 點 10 分。地址變數也是複合變數，包括地址名稱和經緯度。這些變數又包含不同的類型，比如說地址名稱，是一個離散型的隨機變數，經度和緯度是連續性變數，時間是周期型變數，經度和緯度兩個聯合起來又是一個二維的聯合變數。把所有這些變數都用起來，讓每個變數都充分發揮它的功能，是我們要研究的長期課題。而現階段，我們的目標是快速搭建一個系統，快速上線。

這個時候，面對這麼多特徵，我們需要做的首先是選擇一個主要特徵。特徵選擇的原則，是選擇和被預測變數最相關的特徵。通常，度量變數之間的相關性的指標是皮爾遜係數和互信息。皮爾遜係數通常用來衡量兩個連續型隨機變數的相關性，計算出來的結果是線性相關性。剛才我們說到我們的備選特徵既有連續型，也有離散型，還有周期型和複合型的，所以在這我們選擇了互信息來衡量變數之間的相關性。因為我們的目標是目的地，待選特徵先圈定了出發地、出發時刻、出發時期這三個變數。

如圖所示，最左邊是目的地和出發地，中間是目的地和出發時期，最右邊是目的地和出發時刻，數值最高的是目的地和出發時刻兩個變數間的互信息值。這也符合我們的認知：一般情況下，我早上打開滴滴出行的時候，往往出行的目的地是公司，如果是晚上打開，目的地可能就是我的家。所以我們得到的結論就是出發時刻這個特徵是預測目的地最好的單一特徵。

接下來這個問題就進一步簡化為，計算在出發時刻這個特徵下每個目的地的條件概率，這樣一個概率模型。這也就是貝葉斯估計的概率問題，根據貝葉斯公式和全概率公式轉換一下，關鍵要求解的變數，就是在目的地這個條件下出發時刻的概率分布。

4

關鍵問題求解：從數據中發現規律

下面介紹下關鍵問題的求解。我們先看一個用戶的數據，下表最左邊一列都是用戶的出發時間，右邊是對應的目的地。

這樣的數據可能不太容易看出規律來。剛才說統計時刻特徵，所以把日期去掉，左邊是目的地，右邊是發單時刻。這樣可能還是不太容易看出規律。

下面是我繪製目的地 A 的出行頻率的直方圖。這麼一看就非常明顯了。這個分布非常像經典的數據統計里的正態分布，也叫高斯分布。我們分析了很多個 case 之後發現都跟這個類似，也就是同一用戶、同一目的地是符合正態分布的。

接下來的問題就是，我們如何去估計這個正態分布。我們知道，正態分布有兩個關鍵參數，一個是期望一個是方差，接下來就是我們如何去估計均值和方差。

我們先看兩個例子。第一個例子，時刻分別是 8 點、9 點、10 點，所以均值是 9 點，這個直接得到結果了。下一個時刻分別是 23 點、0 點、1 點，均值是 0 點。留一個計算題給各位，3 點、22 點、23 點，均值是多少？3 點、15 點、21 點均值是多少？

在這裡我介紹兩種方法，第一種方法是向量法。

下圖是一個圓的錶盤，有兩個坐標軸，x 軸和 y 軸。每一個時刻用向量表示，然後求和向量。剛才問題里的 3 點、22 點、23 點三個點的和向量是 0，所以均值是 0。

整個演算法的流程是這樣，首先計算每一個時刻對應的向量表示，也就是把每個時刻轉換成向量角度。分別計算它的正弦餘弦值，來表示它的 x 軸、y 軸坐標。第二步計算 n 個時刻對應的和向量。第三步計算和向量與 x 軸的夾角，用反餘弦公式。第四步把夾角轉換為對應的時刻，也就是我們要計算的均值。最後計算對應的方差。

但是這個向量法是有兩個小問題的：

看這麼兩個例子，第一個例子，如果三個時刻是 0 點、0 點、3 點，用向量法計算的均值是 0 點 58 分 33 秒，但實際上它的均值應該是 1 點。另外一個例子是，如果兩個時刻 0 點和 12 點，轉換成向量互為反向量，加和是零向量，零向量是沒有方向的，也就是無解的。那麼問題來了，向量法只能得到近似解，並且在邊界情況下無解，我們該怎麼辦？

我介紹的第二個方法是拉格朗日法，能解決這個問題。我們先回顧下算術平均值的概念和性質，算術平均值滿足這麼一個重要性質：它與所有觀測樣本的距離平方和最小。怎麼求解？就是拉格朗日法。

先對方程求導，讓導數等於 0，得到一個新的標紅的公式，這個公式就是我們熟知的算數平均值的計算公式。

類比一下，平均時刻也可以表示成這個樣子，平均時刻可以認為是與所有時刻距離平方和最小的那個時刻。這裡引入了一個新的概念，就是兩個時刻的距離。那怎麼去計算兩個時刻的距離？我先看兩個時刻的距離應該滿足的兩個性質：首先兩個時刻的距離不能是負值，必須大於等於 0；另外是兩個時刻的距離不能超過 12，也就是 23 點和 0 點，它們的距離是 1 而不是 23。有了這兩個之後，可以用下面這個分段函數。

這個分段函數不太容易代入到上面的問題進行求解，沒有關係，可以用絕對值的性質再轉化一下就推出了統一的表達式，這時候這兩個分段函數就統一了。

最後代入到上面的優化問題裡面，然後解這個優化問題我就能得到時刻和方差，這個是任何時候都有解的，並且解是精確解。關於這個模型求解由於時間關係我就不展開了。

總結一下，向量法簡潔，容易理解，但是它求的是近似解，而且邊界條件下無解。拉格朗日法得到的是精確解，但直觀上不好理解，求解演算法略複雜，時間複雜度是 O(nlogn)。

最後還有一個問題，上面我有假設同一用戶、同一目的地下出發時刻符合正態分布。這裡是有點小問題的，正態分布自變數的分布是整個數軸，從負無窮到正無窮。但出發時刻的分布是 0 到 24，並且有周期循環性。在高級的數理統計裡面，這種分布叫循環正態分布，也叫馮·米賽斯分布。

下面是我們整個演算法的流程，首先根據用戶的歷史訂單，依次計算每個目的地對應的發單時刻的期望和方差；然後根據當前時間計算每個目的地概率的中間數據；第三步用貝葉斯框架計算每個目的地的概率；最後確定閾值，滿足閾值的就是我們要的計算結果。

接下來我舉一個形象點的例子。這個表是一個用戶去每個目的地的出發時間分布，最右邊是他的分布指標。

最後用貝葉斯公式轉換一下，得到當天時間 9 點這個用戶去 A 的概率是 0.98，如果閾值設置的是 0.9，那麼目的地 A 就是我們「猜您要去」的結果。

5

精益求精：模型的進一步調優與優化

簡單的模型之後，下一步我們要追求更好的效果，也就是要一步步把這個模型做的越來越複雜。首先我們看另一個單一的特徵，這次不選出發時刻了，選出發地經緯度。下面是一個用戶出發目的地出發經緯度的聚合，這個特徵也具有正態分布的性質，有一個中心點，離這個中心越來越遠，對應的頻次會越來越低。

畫一個三維圖像就是這樣子，所以說我再提一個假設，同一用戶同一目的地下的出發地經緯度符合二維正態分布，具體密度函數是下面的公式。

每個參數我就不解釋了，重點的推導過程我也不推了，其實跟我上面講的出發時刻一樣，算出概率來，最後套貝葉斯公式。

直接看結果，這是我選的用戶，用出發地經緯度建模之後，如果這個用戶從最右邊的經緯度出發，他去幾個目的地的概率。他去目的地 A 的概率最高，0.81。如果閾值選的是 0.9 的話，因為沒有一個目的地的概率是高於 0.9 的，這種情況下，這個用戶雖然打開 app 了，但並不會出現「猜您要去」，表示我們並沒有充分預測出來他要去哪。

經過上面的研究討論，我們能得出下面兩個結論：一是同一用戶同一目的地下的他的出發時刻是符合一維的正態分布的，二是同一用戶同一目的地對應的出發經緯度是符合二維正態分布的。所以能推導出同一用戶同一目的地出發時刻和出發經緯度符合三維正態分布。

我計算這三個變數的期望向量，以及協方差矩陣以及逆矩陣得到一個參數，然後套用貝葉斯公式。我們發現目的地 A 的概率最高，剛才是 0.81，現在是 0.97。也就是增加一個變數之後，系統預測出來的即將去往的目的地結果不確定性降低了。

前面我基本是用貝葉斯框架 + 正態分布這些傳統的數理統計的知識，對業務進行建模。用三元正態分布的時候處理起來就已經比較複雜了，一般對傳統的數理統計方法來說如果你有幾十個特徵的話那就是災難了。

接下來我嘗試從正態出發，套用貝葉斯框架，推導出一個機器學習的經典模型 LR 模型，代入我們系統，進入到機器學習時代。

我做了這麼一個變數設定，用 D 表示特定目的地，Y 是目的地取值。

上面這兩個方程的含義，可以具象為一個用戶去 D 類目的地和不去 D 類目的地的正態分布。要估計的是用戶在 X 這個特徵下去 D 這個目的地的概率，套用貝葉斯公式變換一下，得到下面的式子。

其實這一塊無非是線性代數的一些計算。把括弧裡面的東西展開合併，再做一些變換，最後得到的公式就比較簡單了，就是邏輯回歸的方程。

這裡有幾個需要注意的點，對比標準的邏輯回歸，我用正態分布 + 貝葉斯框架推導出來的邏輯回歸有二次項和交叉項。再一個，最初假設符合兩個正態分布，而實際上不一定符合正態分布，甚至你很難找到一種分布去擬合。

如果我不對特徵進行處理，而直接套用邏輯回歸機器學習方法的話，得到的效果可能還沒有傳統的數理方法效果更好，所以要對特徵進行一些工程化處理，就是特徵工程。

接下來簡單介紹一下我們機器學習特徵工程的處理方法。特徵工程是很大的課程，沒有辦法深入交流，我只簡單介紹一下我們是怎麼做的。

首先要進行一些特徵篩選，在這裡，因為我們被預測的變數是目的地，我們要選擇跟目的地相關性很高的特徵，比如出發時間、出發地以及用戶信息，這是相關性比較高的特徵。選出初始的特徵之後下一步就要對這個特徵進行拆分，通常的方法是利用業務常識，把選出來的特徵拆分成更多粒度更細的子特徵，比如把時間拆分成時刻來。對另外的一些特徵可能我們需要進行深入的挖掘，比如說用戶特徵實際上是隱藏在用戶行為背後的很多隱藏特徵，這個時候我們有專門的數據挖掘團隊，對用戶特徵進行用戶畫像或者用戶行為分析。

拆分出來這麼多特徵之後，這些特徵之間可能相互之間不獨立，需要對特徵做進一步提取和變換。選出特徵之後，如果要用邏輯回歸，那麼可能還需要數據進行離散化，離散化成 0、1 變數。離散化主要是解決特徵的增長，每個特徵的增長可能對最後的結果貢獻不是線性的，同時離散化成 0、1 變數之後線下訓練的權重被線上系統載入之後能夠直接使用，相當於把乘法直接轉為加法，能夠使系統的性能得到很大的提升。

6

數據之美：分享幾個有意思的 case 的數據分布

以上主要是介紹了技術，接下來咱們一塊看幾個比較有意思的 case，感受一下我們滴滴數據的魅力。

第一個用戶，他的數據只用出發時間這一個特徵就能夠很好的區分他去往哪個目的地。他去目的地 A 的平均出發時刻是 10.5，他去目的地 B 的平均出發時刻是 19 點 20，我畫的圖裡面，藍色就是去目的地 A 的出發時刻分布，紅色是去目的地 B 的出發時刻分布，兩個分布幾乎沒有交集。

目的地和出發時刻的互信息是很高的，1.36。目的地和出發時刻、出發地這兩個變數的聯合變數的互信息是 1.47。我們能看到，對這個用戶來說，即使增加目的地特徵，信息增益也沒有漲多少。

第二個用戶，用出發時刻不太能區分他去哪個目的地。他去目的地 A 的平均出發時刻是 12.4，他去目的地 B 的平均時刻是 11.6，這兩個時間比較接近。這個用戶在 12 點左右的時刻，我們發現他去目的地 A 和目的地 B 的概率都比較高，不太好區分，概率分布曲線有很大的交集。

下邊是他去目的地 A 和目的地 B 對應的出發地經緯度分布，橫軸是緯度，縱軸是經度。藍點是這個用戶去目的地 A 的經緯度，集中在一個區域；紅點是這個用戶去目的地 B 的經緯度，集中在另外一個區域。我們發現我們用他的出發地經緯度可以很好的區分他是去 A 目的地還是 B 目的地。

對這個用戶，我們一次計算了他的目的地跟他對應的出發地、出發時刻以及出發地出發時刻聯合變數的互信息，目的地和出發時刻的互信息是最高的。

上面是這個用戶的出行歷史，如果這個用戶從 B 這個地方出發的話，多數情況是去 A，如果這個用戶是在 A 這個地方出發的話多數情況是去 B，我們猜測這個人可能是中午下班的時候用我們的 APP 打車從 A 地打車到 B 地吃飯，然後吃完飯之後他再用我們的 APP 打車從 B 地到 A 地，而且他吃飯時間很快。這是個挺有意思的 case。

最後一個 case，出發時間和出發地的單一特徵都不容易區分，我們可以看一下它的互信息。他的目的地和出發地的互信息不高，目的地和出發時刻的互信息也不高，但他的目的地和出發地、出發時刻兩個聯合變數的互信息就比較高了。對這個用戶來說，用出發地和出發時刻兩個變數聯合出來，就可以知道他去哪裡。我們直接看一下這個列表，如果這個用戶是 18 點左右，並且他從 A 地出發的話，他很大概率是去 B 地。

本文分享的主線基本是按照滴滴「猜您要去」目的地預測系統，從無到有從有到優的順序介紹的。另一條隱含的線是從數理統計到機器學習，前半部分我用傳統的數理統計方法講解了怎麼建模，後半部分我們用現在的人工智慧的潮流，用機器學習在這裡建模，希望今天的分享給大家在工作和學習中帶來一定的啟發。謝謝大家。

作者介紹

張凌宇，2012 年加入百度，任搜索策略演算法研發工程師；2013 年加入滴滴，高級演算法工程師、計程車策略演算法方向技術負責人、策略模型部資深技術專家，利用機器學習和大數據技術設計並主導實現了多個公司級智能系統引擎，如基於組合優化的訂單分配系統、基於密度聚類與全局優化的運力調度引擎、流量引導與個性化推薦、「猜您去哪」個性化目的地推薦系統等。參與公司十多項技術創新專利研發、申請。擅長利用數學建模、業務模型抽象、機器學習等解決實際業務問題。

今日薦文

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！