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

黎新華，李俊輝，黎景壯

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

0 引 言

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

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

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

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

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

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

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

2 改進(jìn)DTW_AGNES聚類算法

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

2.1 動(dòng)態(tài)時(shí)間彎曲(DTW)

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

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

(1)

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

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

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

(2)

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

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

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

(3)

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

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

(4)

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

2.2 凝聚層次聚類(AGNES)

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

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

(5)

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

2.3 改進(jìn)DTW_AGNES聚類

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

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

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

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

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

(6)

(7)

改進(jìn)后的DTW_AGNES聚類算法的計(jì)算步驟如下：①計(jì)算兩時(shí)間序列的歐式距離矩陣D；②在[Ymin,Ymax]區(qū)間進(jìn)行動(dòng)態(tài)時(shí)間彎曲路徑W匹配，得到兩個(gè)時(shí)間序列的動(dòng)態(tài)時(shí)間彎曲距離DTW；③重復(fù)步驟①～②求得兩兩時(shí)間序列的動(dòng)態(tài)時(shí)間彎曲距離，得到動(dòng)態(tài)時(shí)間彎曲距離矩陣DTSDTW；④從距離矩陣DTSDTW中找出非主對角線的最小距離，將其對應(yīng)的兩個(gè)時(shí)間序列簇合并成一個(gè)簇；⑤反復(fù)進(jìn)行步驟③-④，直到合并后簇?cái)?shù)等于1，算法結(jié)束。

3 實(shí)例分析

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

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

3.1 計(jì)算過程

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

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

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

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

3.2 聚類結(jié)果分析

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

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

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

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

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

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

對不同聚類方法的時(shí)間開銷進(jìn)行測算，在相同計(jì)算平臺(tái)下，分別運(yùn)行5次，求得平均值，如表2。

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

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

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

4 結(jié) 語

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

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