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

黎新華，李俊輝，黎景壯

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

0 引 言

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

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

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

1 網(wǎng)約車需求量時間序列

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

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

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

2 改進DTW_AGNES聚類算法

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

2.1 動態(tài)時間彎曲(DTW)

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

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

(1)

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

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

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

(2)

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

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

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

(3)

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

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

(4)

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

2.2 凝聚層次聚類(AGNES)

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

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

(5)

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

2.3 改進DTW_AGNES聚類

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

圖2 動態(tài)時間彎曲路徑Fig. 2 Dynamic time warping path

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

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

受涂輝等[12]、尚福華等[13]的研究成果啟發(fā)，時間序列x和y不需要每個數(shù)據(jù)點逐個匹配，只需在Y軸上[Ymin,Ymax]區(qū)間內(nèi)數(shù)據(jù)點進行比較，在平行四邊形OAEB的邊界內(nèi)進行路徑W搜索，有效減少搜索范圍，且OB、OA的斜率常用值分別為0.5、2。于是，將動態(tài)彎曲搜索路徑分為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]區(qū)間進行動態(tài)時間彎曲路徑W匹配，得到兩個時間序列的動態(tài)時間彎曲距離DTW；③重復(fù)步驟①～②求得兩兩時間序列的動態(tài)時間彎曲距離，得到動態(tài)時間彎曲距離矩陣DTSDTW；④從距離矩陣DTSDTW中找出非主對角線的最小距離，將其對應(yīng)的兩個時間序列簇合并成一個簇；⑤反復(fù)進行步驟③-④，直到合并后簇數(shù)等于1，算法結(jié)束。

3 實例分析

實例分析數(shù)據(jù)來自國內(nèi)某大型網(wǎng)約車出行平臺。選取華東某城市中心城區(qū)2016年1月1日至1月21日共3周時間的網(wǎng)約車需求量作為研究對象。數(shù)據(jù)以10 min為短時間窗進行時間段統(tǒng)計，得到每日時間序列。日期與工作日、休息日、節(jié)假日對應(yīng)關(guān)系如表1。

表1 日期與自然日對應(yīng)關(guān)系Table 1 Relationship between date and calendar day

3.1 計算過程

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

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

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

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

3.2 聚類結(jié)果分析

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

圖5 聚類結(jié)果Fig. 5 Clustering results

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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