基于改进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大簇：工作日簇、休息日簇、异常的工作日簇和异常休息日簇。对于管理者而言，同一簇的网约车需求量变化趋势具有较高的相似性，可采取相同的运营方案，有利于资源有效配置，也可作为需求量预测的参考依据，提前做好运营调度计划。而异常的工作日和休息日需求量簇，运营者需要调查引起需求量突变的偶然因素，确定是否由不良天气、大型活动等造成，还是由调度不当、优惠补贴增加造成，对完善运营调度方案，提高运输服务水平具有重要价值。

虽然笔者提出的改进动态时间弯曲距离凝聚层次聚类算法能减少时间开销，但相比欧式距离凝聚层次聚类，时间开销仍增加不少。因此如何进一步提高运算效率，对于大数据量的网约车需求量时间序列数据分析将具有重大参考价值，这也是笔者后续研究方向。