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

黎新華，李俊輝，黎景壯

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

0 引 言

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

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

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

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

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

獲取國(guó)內(nèi)某大型網(wǎng)約車(chē)平臺(tái)公開(kā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ū)別，無(wú)明顯的需求高峰；1月1日為節(jié)假日，需求量變化有別于工作日和休息日，但與休息日又有較高的相似性。因此，如何識(shí)別各日期的網(wǎng)約車(chē)需求量時(shí)間序列變化的相似性和差異性，對(duì)網(wǎng)約車(chē)變化規(guī)律的把握具有巨大價(jià)值。

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

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

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

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

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

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

(1)

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

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

首先，對(duì)于兩個(gè)時(shí)間序列x=(x1,x2,…,xn)和y=(y1,y2,…,ym)(若m=n，則為等長(zhǎng)時(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ò)尋找通過(guò)若干節(jié)點(diǎn)的動(dòng)態(tài)彎曲路徑W=(w1,w2,…,wk,…wl)，其中k=1,2,…,l，使其滿(mǎn)足以下4個(gè)約束條件：① 有界性：max(m,n)≤l

在眾多滿(mǎn)足上述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í)間序列的拉伸和平移，且可以適用于非等長(zhǎng)時(shí)間序列，但其計(jì)算復(fù)雜度要遠(yuǎn)遠(yuǎn)高于歐氏距離，算法的時(shí)間復(fù)雜度為O(nm)。

2.2 凝聚層次聚類(lèi)(AGNES)

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

凝聚層次聚類(lèi)首先將樣本中每個(gè)對(duì)象分為一個(gè)簇，然后根據(jù)兩簇的相似度合并為更大的簇，直到所有的對(duì)象都在同一個(gè)簇內(nèi)，或者終結(jié)條件被滿(mǎn)足則結(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聚類(lèi)

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

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

對(duì)網(wǎng)約車(chē)需求量的時(shí)間序列進(jìn)行觀察，發(fā)現(xiàn)在早高峰之前和晚高峰過(guò)后，每日的需求量變化不大。僅在早高峰至晚高峰時(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聚類(lèi)算法的計(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中找出非主對(duì)角線(xiàn)的最小距離，將其對(duì)應(yīng)的兩個(gè)時(shí)間序列簇合并成一個(gè)簇；⑤反復(fù)進(jìn)行步驟③-④，直到合并后簇?cái)?shù)等于1，算法結(jié)束。

3 實(shí)例分析

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

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

3.1 計(jì)算過(guò)程

對(duì)1月1日至1月21日的網(wǎng)約車(chē)需求量時(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：

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

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

3.2 聚類(lèi)結(jié)果分析

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

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

圖6 聚類(lèi)簇Fig. 6 Clusters of the clustering

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

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

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

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

表2 不同聚類(lèi)方法的時(shí)間開(kāi)銷(xiāo)Table 2 Time consumption of different clustering algorithms

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

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

4 結(jié) 語(yǔ)

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

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