面向交通状态时空模式的双向聚类可视分析

胡 浩，朱 敏，杨 啸，李季倬

(四川大学 计算机学院，成都 610065)

1 引 言

城市道路的交通拥堵已经成为世界各国广泛面对的问题.由于人类日常出行存在规律性，道路交通状态的时序变化和地理分布实际上存在一些反复出现的模式[1].随着交通数据自动采集能力的提升，可以从大量历史数据中挖掘出交通状态的时空模式并制定相应的交通管理策略，从而提高路网的通行效率.然而，不同路段可出现不同的时序变化模式(如市中心主干道和绕城高速)，不同时间段可出现不同的空间分布模式(如工作日和周末).交通管理部门需要掌握这些时空模式在时间和空间上的分布情况，以制定差异化的管理策略.因此，研究如何从大量交通数据中发现和分析潜在的交通状态时空模式及其分布具有重要意义.

聚类分析可以在聚簇级别上概述数据集，同时支持对单个簇包含的样本进行探索以洞察详细信息，因而有助于从时空数据集中提取和分析模式[2].为了对交通状态的时空模式进行直观和高效地探索，大量研究结合聚类和可视化技术.首先对时序数据或空间分布数据进行聚类，然后可视化类簇所含样本的时空特征以解译模式，进而分析模式在时间和空间上的分布情况.但是，现有研究未考虑对时序模式的空间分布和空间模式的时间分布进行综合分析.

针对该不足，本文提出一种基于双向聚类的交通状态时空模式可视分析方法.通过双向聚类同时将路段集合和以小时为尺度的时间戳集合(以下简称小时集合)按交通状态相似性划分为簇.同一路段簇中的路段具有相同的时序模式，进而可以分析各时序模式在空间上的分布；同一小时簇中的时刻具有相同的空间模式，进而可以分析空间模式在时间上的分布.以上两方面的分析推断可以交叉印证，并借助多视图联动技术进行综合分析.基于降维投影可视化可分析各日期时序向量的相似度，进而提取出日模式[3]，并分析其空间分布.本文的贡献总结如下：1)提出了一种基于双向聚类的交通状态时空模式分析框架；2)设计了一种多视图联动的时空模式可视分析方法，以支持用户综合分析空间模式的时间分布和时序模式的空间分布.3)设计了基于降维投影可视化的日模式分析视图，辅助用户进一步从日期尺度上分析时序模式及其空间分布.

2 相关工作

2.1 交通数据可视化与可视分析

可视化利用视觉通道表征数据以支持对数据高效直观的理解和探索，因而有助于挖掘交通、社会、地理时空数据中蕴含的模式[4].Zhu 等[5]总结了城市时空数据的各种可视化技术，包括反映时空分布特征的视觉通道设计、基于时空密度聚类、基于高维向量投影等可视化方法.一些学者利用可视分析有效地探索了时空共现模式[6]、迁移模式[7]、时空分布模式[8-10]等.综述[11]总结了对交通数据的各种可视化编码方案，以及在此基础上对时空模式的可视分析技术.

可视分析领域大量研究基于OD数据[12]、轨迹数据[13]分析了交通流量的时空模式，但是，交通流量并不能完全反映道路的交通状态是拥堵还是畅通(例如宽阔的主干道交通流量大不一定拥堵)，而本文工作主要针对道路交通状态.针对交通拥堵，Wang等[14]基于矩阵像素热力图分析交通拥堵在路网上的传播情况.Lee等[15]基于交通拥塞的预测结果，通过对路段交通量和速度的可视化辅助用户探索交通拥堵原因.Kalamaras等[16]面向交通拥堵设计了交互式可视分析平台，并运用降维投影技术以支持用户探索各路段交通状态的相似性.交通拥堵可以视为交通状态的子集，而本文更侧重于对所有交通状态的变化和分布进行分析.

2.2 交通状态时空模式分析

为了对交通状态时空模式进行分析，聚类技术被广泛运用[17].许多研究将交通状态的时序数据聚类后，都尝试在地图上可视化类簇所含路段样本，以进一步分析时序模式的空间分布.例如Su等[18]对一天内的交通状态数据运用模糊聚类，并根据各路段的类簇隶属度在地图上对各路段进行可视化编码.Li等[1]对各道路交通状态日变化数据运用谱聚类，一个路段各日期的样本可能属于不同类簇，对各路段按其样本所属最多的类簇做为该路段的可视化编码.Zhao等[19]基于k-means和层次聚类对时序数据处理，然后基于聚类结果在地图上可视化早晚高峰的地理分布.这些研究能支持用户划分时序模式并在地图上判断各路段所属的时序模式，但用户难以据此直观地推断出各时间段的空间模式.

也有学者从路网整体交通状态入手，研究如何划分空间模式.韦伟等[20]提出一种基于时空自相关预分类的道路交通状态层次聚类方法，以路段作为聚类单元，将道路按交通状态划分为几种模式并探索其时序演变.邬群勇等[21]基于聚类对路网局部位置交通状态进行精细识别并分析其演化情况.Zhang等[22]使用带有Dunn索引的自组织映射算法对相关道路链上的交通状态进行分类并确定最佳分类数量.Li等[23]利用高斯混合聚类法对交通运行状态特征数据进行聚类，划分区域交通拥堵的空间分布模式并基于热力图分析.这些研究能够有效地划分空间模式，并分析各模式在不同时间段的出现规律，但未考虑到将空间模式的时间分布与各路段时序模式联系起来.

综上所述，针对交通状态时空模式，现有研究主要采用的方式是从时间或空间维度上划分模式后分析该模式在另一个维度上的分布情况，缺少对时空模式及其分布情况的综合分析.

2.3 基于双向聚类的时空模式分析

在一个维度(时间或空间)上进行简单聚合或分别分析每个维度可能会导致发现结果不能代表时空数据的整体情况[24]，双向聚类能够通过同时对空间位置和时间戳进行聚类以解决此问题.Wu等[25]利用具有I散度的Bregman块平均双向聚类算法[26](BBAC_I)处理气温数据，综合分析了空间模式的时间分布和时序模式的空间分布，这是第一次有学者尝试将双向聚类运用于分析地理时空数据[2].Wu等[2]对地理时空模式及其分布的综合分析任务进行了详细拆分，并通过实例对比了单向聚类和双向聚类在综合分析能力上的差异.除了自然现象，最近也有学者将双向聚类应用于出租车数据以分析人类活动的时空模式[24].

综上所述，已经有一些学者开始将双向聚类应用于对时空模式及其分布的综合分析，以克服单向聚类的不足.但是，目前尚未发现其在交通状态分析中的应用.而且，这些研究主要使用静态的并列可视化[27]呈现时序模式和空间模式，用户难以对模式的时空分布进行双向地多尺度地交互式探索.本文通过设计一种多视图联动的时空模式可视分析方法，将时空模式的可视化与其分布情况的可视化通过交互链接起来，以支持用户对交通状态进行双向(时序模式的空间分布和空间模式的时间分布)、多尺度(小时尺度和日期尺度)地综合分析.

3 交通状态时空模式分析框架

3.1 分析框架

为了能同时发现交通状态的时序模式和空间模式并综合分析其时空分布，本文提出一种基于双向聚类的交通状态时空模式分析框架.如图1所示，首先将交通状态数据预处理为时空矩阵数据，运用双向聚类算法，同时沿空间维度和时间维度，将道路集合和小时集合划分为簇.对聚类得到的每个双向簇设计相应的视觉通道，使用户借助可视化界面解译空间模式和时间模式，进而同时分析空间模式在时间上的分布和时序模式在空间上的分布.提取出交通状态变化的日模式，以进一步从日期尺度上分析时序模式的空间分布.

3.2 交通状态和双向聚类

本文将平均车速与路段限速做为道路交通状态的判别指标[28].对于整个路网的交通状态，使用时空矩阵O(R，T)表示.矩阵的行表示路段集合{r1，r2，…，rm}，列表示小时集合{t1，t2，…tn}.矩阵的元素为各路段在指定时刻的交通状态数值，使用下式计算：

(1)

其中v(rp，tq)为路段p在q时刻记录的小时平均车速，maxv(rp)为路段rp的限速.为了保证各个路段的公平性，将超速的记录截断为该路段限速，使矩阵元素的最大值不超过1.0.不同日期的小时按时序展开，如所研究数据的全部时间范围为5天，则展开得5×24列，这是为了通过聚类探索不同日期的某些时段之间是否存在相似的交通状态.

图1 交通状态时空模式分析框架Fig.1 Analysis framework of temporal and spatial patterns of traffic state

双向聚类的目标是同时对R和T聚类.假设目标是将R划分为k个簇，T划分为w个簇，令{rc1，rc2…，rck}表示R的k个簇，令{tc1，tc2…，tcw}表示T的w个簇，则目的是找到一个映射MR和Mt，使行向量和列向量划分到不同的簇中.

(2)

本文采用BBAC_I算法[26]进行双向聚类，该算法实质是通过迭代使双向聚类后的矩阵与原始矩阵间的互信息损失最小.最终计算出的互信息损失也可以做为聚类数量选取的参考依据[24].通过双向聚类得到k个行簇和w个列簇，交叉部分的矩阵元素组成了k×w个双向簇：

CoCluster={(rci，tcj)，1≤i≤k，1≤j≤w}

(3)

3.3 空间模式和时序模式提取

通过统计双向簇的均值可提取空间模式和时序模式.列簇与行簇均是包含相近交通状态的时间段的子集，因此各双向簇中的均值刻画了该双向簇的交通状态特征，使用下式计算：

(4)

每个列簇对应的双向簇均值代表了该时间段子集下各路段交通状态的概况，因而可使用长度为k的w个向量，描述各时间段出现的全局交通状态空间分布模式SPj.同理，可使用长度为w的k个向量TPi描述在各路段出现的时序模式.

(5)

(6)

通过该方法提取的时空模式可以交叉印证.对于从双向簇中提取出的w种空间模式和k种时序模式，每一个列簇TC均对应一种空间分布模式SP，每一个行簇RC均对应一种时序模式TP.对于任意一个时刻t，按其所属的列簇，可得该时刻对应的空间模式，同理可提取各路段对应的时序模式.由于时空矩阵被分割为规则的棋盘结构，因而能够将空间模式的时序演变与所提取的各路段时序模式相印证，反之，也能将时序模式的空间分布与所提取的各时刻空间模式相印证，为时空模式的综合分析建立基础.

为了能进一步从日期尺度上分析时序模式及其空间分布，从TP中提取出日模式.将k组TP按小时展开：

(7)

再以24小时为粒度分别对k个HTP进行分段得到k组日分段向量，使用欧氏距离计算组内向量间的相似度，并采用UMAP[29]降维投影技术将其投影到二维平面，用户根据各向量的相似度和聚集情况发现日模式.本文并没有采用传统研究中工作日/周末的预定义划分方式，而是由用户基于降维投影进行探索性分析，这是为了确保系统在分辨日模式方面的鲁棒性.

4 时空模式可视分析

4.1 可视分析任务

为了对模式的时空分布进行可视分析，本文通过与两位交通领域的专家交流，依据其需求制定了以下可视分析任务.

T1.交通状态空间模式解译

用户需要通过可视化直观了解空间分布模式的特征.对一种空间模式，能描述各路段的拥堵/畅通状态，分析各种状态主要出现在哪些区域，并结合其地理位置周边如学校、海滨、生活区等进行分析.

T2.交通状态时序模式解译

用户需要通过可视化直观了解时序变化模式的特征.对一种时序模式，能描述各时刻的拥堵/畅通状态，分析各种状态主要出现在哪些小时段及哪些日期，并结合其时间事件因素如工作日、节假日、交通限制令等进行分析.

T3.空间模式在时间上的分布

用户需要分析某种空间模式主要出现在哪些日期和一天内的哪些时段，对比工作日/周末空间模式日演变的差异，对比一天内各时段空间模式的差异，并分析一天内各种空间模式交替演进的规律.

T4.时序模式在空间上的分布

用户需要分析某种时序模式主要分布在哪些路段和哪些区域(市中心、外环、商贸区)，对比不同地理区域时序模式的差异，对比不同路段(如高速路、环形岛等)时序模式的差异.

4.2 多视图

面向可视分析任务，本文通过设计一种多视图联动的可视分析方法，以支持用户对模式及其时空分布进行双向、多尺度地综合分析.

在不同视图中分别可视化时空模式与模式的分布情况，当通过交互切换某个模式时，其对应的分布情况在另一个视图中也相应地呈现.如图2所示，图2(a)下方每个方块代表一个列簇TC，雷达图的每个维度代表一个行簇RC，当点击任一TC时，雷达图将展示该TC与所有RC相交的双向簇交通状态均值CoAvgij，.图2(b)中的地图展示了各路段，当点击了雷达图中对应RC标签时，属于该行簇的路段将会高亮.图2(a)内环的弧形方块对应不同的日期，周末和周一之间会有较大的空隙，方便用户探索时间分布规律.每个弧形方块上均附有24条呈发散状的直线线段，属于同一列簇的小时拥有相同的长度.

图2 多视图Fig.2 Multi-view

图2(c)通过散点图展示各RC对应的HTP日分段向量的降维投影，并支持刷选交互，进而支持从日期尺度上进行分析.散点间的欧氏距离反映了各向量的相似度，因而其全局和局部结构揭示了向量的聚集情况.当用户框选了部分聚集的散点后，图2(a)中对应日期会高亮，以反映所选散点对应的日期.同时在图2(d)中，将框选散点对应的向量聚合后，用折线图展示其均值和方差，以揭示日模式.图2(c)和图2(d)反映了各RC所对应的日模式，因而可以结合地图进一步分析日模式在空间上的分布情况.

4.3 对时空模式及其分布的可视分析

对时序模式和空间模式的解译需要借助多视图.由3.3节可知，任一TC均对应一个空间模式SP，任一RC均对应一个时序模式TP.以图2为例，用户根据图2(a)中列簇TC1对应的4个数值(0.40，0.05，0.39，0.23)，可解译出SP1模式的含义为“属于RC1和RC3的路段严重拥堵；属于RC4的路段稳定通行；属于RC2的路段畅通”，再通过切换高亮地图中对应不同RC的路段可进一步探索该SP1模式的特征.对时序模式的解译则通过图2(a)外环线段，线段长短变化展示了时序模式的演进，任一种长度的线段对应了一个TC，同时也对应了4个双向簇(k=4)的交通状态均值.

为了对时空模式的时空分布进行双向地可视分析，设计了相应的联动机制.当用户点选图2(a)中某列簇的方块时，属于该列簇的小时线段会高亮，用户可据此分析各空间模式在时间上的分布情况.对时序模式在空间上的分布情况，则主要通过切换观察图2(b)中属于各RC的路段，不同RC所含路段的交通状态变化有着不同的时序模式.

5 实例分析

本文使用公开数据集[30]验证所设计方法的有效性.该数据集包含罗马尼亚部分城市疫情期间所有路段的交通状态，罗马尼亚政府在2020年5月15日这一天将风险等级由紧急下调至警告.本文主要选择了康斯坦察这一港口城市进行分析.

首先对数据集进行预处理.该城市共包含546个路段，时间范围从2020年5月14日-2020年6月7日.该数据集采集频率为15分钟一次，每小时包含4个记录，统计其均值做为小时平均车速.

在双向聚类时需要设定行簇和列簇数量，对该数据集测试了行簇数量2-10、列簇数量6-10的配置.设定不同行簇列簇数量后聚类得到的互信息损失如图3所示，横轴为列簇数量，可以观察到行簇数量>4、列簇数量>10时互信息损失的变化较小.因此，选择行簇数量4和列簇数量10作为双向聚类的设定.

图3 不同行簇列簇数量对应的互信息损失Fig.3 Mutual information loss corresponding to the different number of row clusters and column clusters

图4 时空模式及其分布情况Fig.4 Temporal-spatial distribution of spatial patterns and temporal patterns

5.1 案例1：空间模式及其时间分布

系统得到11个列簇(TC1-11)和4个行簇(RC1-4)，对应空间模式SP1-11和时序模式TP1-4.因篇幅所限，图4(a)仅列举了TC1-6，图4(b)列举了RC1-4.

用户通过多视图可逐步解译出这11种空间模式.以SP1和SP6为例，根据SP1在视图中的特征，可将其描述为“RC1、RC3、RC4路段(市中心和靠海地区)比较拥堵而RC2路段(入城高速公路)比较畅通”，SP6则可以描述为“RC1路段稳定通行，RC2-4的路段畅通”.

用户接下来可进一步分析空间模式SP1-11在时间上的分布情况.以图4(a)中的TC1为例，用户可据此分析出SP1这一空间模式主要在每周工作日的7：00～16：00出现，由此可得出结论，对于每周的工作日，市中心和靠海地区路段在的7：00～16：00比较拥堵，而入城高速公路在7：00～16：00时段则比较畅通.用户还可进一步分析空间模式交替出现的日演化规律，如工作日从0：00～4：00的SP6模式、5：00～6：00的SP5模式到7：00开始进入SP3模式，可据此推断属于RC1的路段交通状态在一天中最先开始活跃.用户通过对比各日期的空间模式日演化，得知空间模式SP1在后3周的工作日集中出现，而周六和周日均没有出现，因此RC1和RC2所属街道主要在工作日都很拥堵，而周六周日相对较畅通.然而，用户观察到第1周却打破了这种规律.第1天即5月14日也是工作日，但没有出现SP1模式而主要是SP2模式，因此用户断定14日和15日这两天一定发生了对交通状态影响较大的事件，通过前述罗马尼亚5月15日下调紧急状态这一事实可验证该判断.

5.2 案例2：时序模式及其空间分布

用户通过多视图可逐步解译出4种时序模式.以5月18日为例，位于顺时针第5段，展示的线段长度排布情形为“1：00～5：00最短；6：00～8：00逐渐变长；9：00～16：00最长；后续时间逐渐变短”.线段的不同长度对应不同列簇，结合雷达中RC1对应的交通状态数值，用户可得知TP1的时序模式在该日内为“1：00～5：00畅通；6：00～8：00开始拥堵；9：00～16：00最拥堵”.当用户关注TP2时序模式时，由于所有TC与RC2对应的双向簇交通状态均值较小，因此用户得出的结论就是TP2时序模式，也就是RC2所有路段的时序模式，“全天都很畅通”.

用户接下来可分析TP1-4这4种时序模式在空间上的分布.每个行簇对对应的路段拥有相同的时序模式，例如RC1所包含的路段主要在市中心和靠海地区，因此市中心和靠海地区的路段主要呈现时序模式TP1，RC4所包含的路段主要为入城高速公路，因此入城高速公路的交通状态主要呈现时序模式TP4.用户可对TP1-TP4时序模式出现的主要区域(市中心或外环)、范围、道路特征(主干道或环城高速)、地理周边(医院或学校)等进行分析.

接下来用户通过降维投影散点图进一步分析TP1-4中所包含的日模式.4种时序模式所对应的降维投影散点图如图5(a)所示，基本上每个视图里的散点均分为两簇聚集.用户通过框选散点，发现其中一簇样本对应的日期均为工作日，周末聚集在另一簇中，而且5月14日这一特殊的工作日位于周末那一簇中.当用户框选散点后，系统提取出该簇的所有日模式并可视化.如图5(b)所示，基本上反应了分属于RC1-4的路段在工作日和周末的日模式，用户结合RC1-4路段的分布进一步分析，并对比了限制令前后各路段交通状态的日变化.

图5 HTP日分段向量降维投影Fig.5 Dimension reduction projection of HTP

6 总 结

本文提出了一种基于双向聚类的交通状态时空可视分析方法.该方法通过对时空矩阵双向簇的划分，并结合多视图联动、降维投影可视化辅助用户综合分析交通状态的时空模式及其分布.通过在一份疫情期间采集的交通数据集上进行实例分析，验证了该方法能够同时分析空间模式在时间上的分布和时序模式在空间上的分布，且有效地发现和分析了限制令前后、工作日/节假日不同地区和时段出现的不同模式.该方法将有助于交通领域专家制定差异化的交通管理策略.

在未来的工作中，可以考虑对双向簇的粒度和数量提供让用户主动介入调整的交互式可视化工具，以更好地融入领域专家经验划分时空模式.还可以考虑结合交通事故、天气等数据分析其他因素与时空模式的关联性.