基于改進DTW_AGNES的網約車需求量時間序列聚類研究

黎新華，李俊輝，黎景壯

(1. 廣東交通職業技術學院 軌道交通學院，廣東 廣州 510650；2. 華南理工大學 土木與交通學院，廣東 廣州 510640)

0 引 言

網絡預約出租汽車(簡稱“網約車”)基于移動互聯網和大數據技術得以快速發展[1]，積累了海量的乘客預約車輛數據。對這些數據進行統計分析，可以得到特定區域的網約車需求量時間序列數據，深入剖析其隱含著的變化規律，將有利于車輛調度，為乘客提供更高水平的運輸服務。

唐立等[2]基于混合Logit模型研究了網約車選擇行為特征，指出乘客的預計到達時間、出行距離會影響網約車出行需求。郭瑞雪[3]分析了網約車需求量的時間變化特征，發現在工作日的早晚高峰會出現比較明顯的需求量增加現象，但非工作日無明顯需求高峰。安磊等[4]對網約車需求量和供給量的時間序列進行分析，發現工作日的早高峰有較大的供需缺口，而在周末14:00—18:00之間，網約車供需缺口保持穩定增長。以往研究多從時間序列中截取局部數據，提取特定指標，來說明時間序列的變化規律。為了把握時間序列的全局特征，程靜等[5]使用時間序列聚類分析方法，對城市內不同地塊的出租車出行量時間序列數據進行聚類，分析不同地塊的乘客出行時空分布相似性和差異性。但傳統的時間序列相似性度量采用歐氏距離計算，不能識別時間序列偏移、伸縮等問題，因此梁坤等[6]提出使用動態時間彎曲(DTW)距離計算時間序列的相似度，再使用K 均值聚類來識別不同時間序列的異常情況。DTW算法能夠通過偏移、彎曲來計算每個樣本點間的距離，以求得兩時間序列的相似度，最大程度的保留了時間序列的全局特征，但也增加了算法的復雜度，耗費更多的時間和數據存儲空間[7]。另外，以往研究多為對網約車單日需求量變化特征進行分析，并未對不同日期網約車的需求量變化規律的相似性和差異性進行詳細分析。

因此，筆者提出一種通過優化DTW的動態規劃搜索范圍來提高運行效率的方法，使用改進后的DTW作為凝聚層次聚類(AGNES)相似性度量的改進DTW_AGNES聚類方法，對網約車需求量時間序列數據進行聚類分析，以揭示不同日期網約車需求量變化規律，為車輛調度運營提供建議。

1 網約車需求量時間序列

網約車逐漸成為大城市的一種常規化交通工具，其需求量受居民出行特征影響，存在工作日早晚需求高峰的特點，且區域總需求量受用地類型影響。由于小汽車的便捷性、靈活性和舒適性，網約車需求量在不良天氣狀況、大型活動后會出現需求高峰。

獲取國內某大型網約車平臺公開的M市2016年1月1日—1月9日的訂單數據，選取市中心居住用地和商業用地混合區域的訂單數據進行分析，結果如圖1。1月4日和1月8日分別為星期一、星期五，皆為工作日，需求量時間序列形狀具有較高相似性，在8:00—9:30出現需求早高峰，在17:30—19:00出現需求晚高峰，但星期五晚間和夜間需求量明顯大于星期一；1月9日為休息日(星期六)，需求量時間序列變化與工作日有較大區別，無明顯的需求高峰；1月1日為節假日，需求量變化有別于工作日和休息日，但與休息日又有較高的相似性。因此，如何識別各日期的網約車需求量時間序列變化的相似性和差異性，對網約車變化規律的把握具有巨大價值。

圖1 網約車需求量變化情況Fig. 1 Change of online car-hailing demand quantity

2 改進DTW_AGNES聚類算法

采用DTW算法作為AGNES聚類的距離度量方法，對時間序列的相似性進行聚類分析，并在保持精度的前提下，通過優化DTW算法中動態規劃的搜索范圍，提高DTW的計算效率，構建改進的DTW_AGNES聚類算法，對不同日期的需求量時間序列進行聚類分析。

2.1 動態時間彎曲(DTW)

相似性度量通過計算兩個數據或者兩個實例間的距離來衡量他們之間的關系。距離越大，相似性越小；距離越小，相似性越大。常用的時間序列相似性度量方法有歐式(Euclidean， Euc)距離和動態時間彎曲(dynamic time warping， DTW)距離。

對于兩個等長的時間序列x=(x1,x2,…,xn)和y=(y1,y2,…,yn)，他們之間的歐式距離[8]為：

(1)

式中：i=1,2,…,n,其中n為時間序列數據個數。

歐式距離能快速計算時間序列的相似性，但其對噪聲點敏感(單個數據點的異常引起總距離的大幅度偏差)，且不能識別時間序列的拉伸和平移，忽略了時間序列整體形態變化趨勢。因此，研究者提出了動態時間彎曲距離[9]，根據最小代價的時間彎曲路徑進行匹配獲得兩時間序列的相似性，對時間序列發生彎曲后的相似性度量具有很好的魯棒性。

首先，對于兩個時間序列x=(x1,x2,…,xn)和y=(y1,y2,…,ym)(若m=n，則為等長時間序列)，計算各點間的歐式距離，得到歐式距離矩陣D：

(2)

式中：i=1,2,…,n,其中n為時間序列x的數據個數；j=1,2,…,m,其中m為時間序列y的數據個數；dij為x中第i個點到y中第j個點的歐式距離。

接著，從矩陣網絡尋找通過若干節點的動態彎曲路徑W=(w1,w2,…,wk,…wl)，其中k=1,2,…,l，使其滿足以下4個約束條件：① 有界性：max(m,n)≤l

在眾多滿足上述4個約束條件的路徑中，選取匹配度最高、整體代價最小的路徑，即為動態時間彎曲距離：

(3)

動態時間彎曲距離的計算可以使用動態規劃方法，求得最短動態彎曲路徑上的累加距離r(m,n)。該累加距離越小，規整代價就越小。累加距離的計算公式可表示為：

r(i,j)=d(xi,yj)+…+min{r(i-1,j-1),r(i,j-1),r(i-1,j)}

(4)

動態時間彎曲距離相比較于歐式距離，在一定程度上可以識別出時間序列的拉伸和平移，且可以適用于非等長時間序列，但其計算復雜度要遠遠高于歐氏距離，算法的時間復雜度為O(nm)。

2.2 凝聚層次聚類(AGNES)

層次聚類具有計算量小、計算結果可靠性高等特點，廣泛使用于聚類分析[10]。層次聚類可分為自底向上的凝聚層次聚類(agglomerative nesting， AGNES)和自頂向下的分裂層次聚類兩種方法。由于分裂層次聚類存在如果某步沒有選擇好分裂點會導致低質量聚類結果的問題，因此筆者選用凝聚層次聚類。

凝聚層次聚類首先將樣本中每個對象分為一個簇，然后根據兩簇的相似度合并為更大的簇，直到所有的對象都在同一個簇內，或者終結條件被滿足則結束運算[11]。兩簇的鄰近性度量基于距離計算。常用到的距離度量有單連接距離、全連接距離、質心距離、平均距離和均值距離等。為了更好地從總體上把握各點集簇的差異，以及提高運算效率，選用平均距離度量方式，其表達式如式(5)：

(5)

式中：Ci,Cj為兩個簇；p為Ci簇的點樣本數據；q為Cj簇的點樣本數據。

2.3 改進DTW_AGNES聚類

傳統DTW算法在對時間序列x和y尋找匹配路徑W時，采用逐點法對整個平面域進行搜索，導致算法時間復雜度增加，如圖2。

圖2 動態時間彎曲路徑Fig. 2 Dynamic time warping path

對網約車需求量的時間序列進行觀察，發現在早高峰之前和晚高峰過后，每日的需求量變化不大。僅在早高峰至晚高峰時段內，需求量波動較大，導致時間序列形狀的較大差異，但DTW算法在時間序列匹配最佳路徑W時搜索范圍仍處于特定區域。將此區域定義為平行四邊形OAEB，如圖3。

圖3 匹配路徑約束范圍Fig. 3 Constraint range of matching path

受涂輝等[12]、尚福華等[13]的研究成果啟發，時間序列x和y不需要每個數據點逐個匹配，只需在Y軸上[Ymin,Ymax]區間內數據點進行比較，在平行四邊形OAEB的邊界內進行路徑W搜索，有效減少搜索范圍，且OB、OA的斜率常用值分別為0.5、2。于是，將動態彎曲搜索路徑分為3段，分別為(1,Xa)、(Xa+1,Xb)、(Xb+1,n)，有Xa=(2m-n)/3，Xb=2(2n-m)/3，Xa和Xb向上取整。Ymin和Ymax的計算式如式(6)、式(7)：

(6)

(7)

改進后的DTW_AGNES聚類算法的計算步驟如下：①計算兩時間序列的歐式距離矩陣D；②在[Ymin,Ymax]區間進行動態時間彎曲路徑W匹配，得到兩個時間序列的動態時間彎曲距離DTW；③重復步驟①～②求得兩兩時間序列的動態時間彎曲距離，得到動態時間彎曲距離矩陣DTSDTW；④從距離矩陣DTSDTW中找出非主對角線的最小距離，將其對應的兩個時間序列簇合并成一個簇；⑤反復進行步驟③-④，直到合并后簇數等于1，算法結束。

3 實例分析

實例分析數據來自國內某大型網約車出行平臺。選取華東某城市中心城區2016年1月1日至1月21日共3周時間的網約車需求量作為研究對象。數據以10 min為短時間窗進行時間段統計，得到每日時間序列。日期與工作日、休息日、節假日對應關系如表1。

表1 日期與自然日對應關系Table 1 Relationship between date and calendar day

3.1 計算過程

對1月1日至1月21日的網約車需求量時間序列采用改進的動態時間彎曲距離進行相似性度量。圖4為1月4日與1月5日的動態時間彎曲路徑。

計算得到動態時間彎曲距離DTW=395.6。分別兩兩計算不同日期的時間序列動態時間彎曲距離，得到矩陣DTSDTW：

接著，使用凝聚層次距離對動態時間彎曲距離矩陣DTSDTW進行聚類分析，得到不同日期的網約車需求量時間序列聚類樹，并采用歐式距離的凝聚層次聚類、普通動態時間彎曲距離的凝聚層次聚類結果作為對比。

圖4 網約車時間序列改進后動態時間彎曲路徑Fig. 4 Dynamic time warping path after improvement of time seriesof online car-hailing

3.2 聚類結果分析

分別使用EUC_AGNES聚類、DTW_AGNES聚類和改進DTW_AGNES聚類得到聚類樹形圖，如圖5。由圖5可以看出，動態時間彎曲距離范圍(200,700)小于歐式距離范圍(400,1 400)，說明動態時間彎曲距離更能度量時間序列的相似性，且改進后的動態時間彎曲距離范圍(200,750)并未發生大幅度改變。DTW_AGNES聚類和改進DTW_AGNES聚類結果有一致性，且有別于EUC_AGNES聚類結果。

圖5 聚類結果Fig. 5 Clustering results

圖6 聚類簇Fig. 6 Clusters of the clustering

當簇數K=4時，DTW_AGNES聚類和改進DTW_AGNES聚類將日期{1,2,3,9,10,17}歸為一類，如圖6(a)中部分日期數據。對照表1，該簇為休息日(包含元旦假日)集合。元旦假日的網約車需求量時間序列相對休息日向左平移，DTW算法能夠識別其相似性，歸為一簇，說明元旦假日與普通休息日的網約車需求量時間序列具有較高相似性，且需求量提前約1.5 h，網約車運營商需要在節假日提前發布通知給網約車司機，預先調度好充足車輛。而EUC_AGNES聚類不能精確識別{2,3,9,10,17}與{1}的時間序列特征，將其歸為兩簇，可能造成網約車運營商缺少節假日需求量變化規律參考對象，導致調度編排方案出錯。

DTW_AGNES聚類和改進DTW_AGNES聚類將日期{4,5,6,8,11,12,13,14,15,21,19}歸為一類，如圖6(b)中部分日期數據。對照表1，該簇為工作日集合，說明工作日網約車需求量時間序列具有較高相似性，網約車運營商可以根據前一天以及當天的需求量變化規律做好第二天的車輛調度安排。

DTW_AGNES聚類和改進DTW_AGNES聚類將{16}、{20}單獨歸為兩類，如圖6(c)和圖6(d)，分別為異常休息日(16日/星期六)需求量時間序列和異常工作日(1月20日/星期三)需求量時間序列。這是因為16日的白天需求量大于往常休息日，且夜間(21:00—23:00)出現網約車高峰需求量，有別于其他休息日需求量時間序列；20日的白天需求量從上午10:00之后大于往常工作日需求量，且在晚間高峰(17:00—21:00)出現超高峰需求量，有別于其他工作日需求量時間序列變化規律。網約車運營商需要考慮車輛編排計劃、活動信息、天氣狀況等因素，檢查是否做好調度方案，進而提高下次對異常需求量的處理水平。

對不同聚類方法的時間開銷進行測算，在相同計算平臺下，分別運行5次，求得平均值，如表2。

表2 不同聚類方法的時間開銷Table 2 Time consumption of different clustering algorithms

由表2可以看出，普通DTW_AGNES聚類和改進DTW_AGNES聚類的時間開銷均大于EUC_AGNES聚類，但改進后的DTW_AGNES聚類的時間開銷減少明顯，比普通DTW_AGNES聚類運行效率提高 62%。

因此動態時間彎曲距離作為相似性度量方法的凝聚層次聚類比歐氏距離凝聚層次聚類更能識別網約車需求量時間序列的特性，聚類結果更具有合理性，但也導致時間開銷增加，而通過優化DTW的動態規劃搜索范圍，限制病態動態彎曲路徑，改進動態時間彎曲距離的凝聚層次聚類能有效提高運行效率，減少計算時間和儲存資源，節省人力物力資源，集中資源做出合理的網約車編排調度計劃。

4 結 語

相比歐式距離凝聚層次聚類(EUC_AGNES)結果，采用動態時間彎曲(DTW)距離作為凝聚層次聚類的相似性度量方法，構建DTW_AGNES算法對網約車需求量時間序列數據進行聚類分析，更具有合理性，能更好地識別出需求量時間序列的變化特征，但也導致算法運行時間增加。通過優化動態規劃搜索范圍的改進DTW_AGNES聚類算法可以明顯減少時間開銷，在保證相同精度的情況下，大幅度提高運行效率。改進DTW_AGNES聚類將不同日期的需求量分為4大簇：工作日簇、休息日簇、異常的工作日簇和異常休息日簇。對于管理者而言，同一簇的網約車需求量變化趨勢具有較高的相似性，可采取相同的運營方案，有利于資源有效配置，也可作為需求量預測的參考依據，提前做好運營調度計劃。而異常的工作日和休息日需求量簇，運營者需要調查引起需求量突變的偶然因素，確定是否由不良天氣、大型活動等造成，還是由調度不當、優惠補貼增加造成，對完善運營調度方案，提高運輸服務水平具有重要價值。

雖然筆者提出的改進動態時間彎曲距離凝聚層次聚類算法能減少時間開銷，但相比歐式距離凝聚層次聚類，時間開銷仍增加不少。因此如何進一步提高運算效率，對于大數據量的網約車需求量時間序列數據分析將具有重大參考價值，這也是筆者后續研究方向。