EN中文

地球信息科学学报 >

2023 , Vol. 25 >Issue 7: 1514 - 1530

DOI: https://doi.org/10.12082/dqxxkx.2023.220753

基于出租车上下客数据流与分布式多阶段网格聚类的城市热点区域实时探测方法

  • 王浩成 ,
  • 向隆刚 , * ,
  • 关雪峰 ,
  • 张叶廷
展开
  • 武汉大学 测绘遥感信息工程国家重点实验室，武汉 430079
*向隆刚（1976— ），男，湖南怀化人，博士，教授，主要从事空间数据库、轨迹数据时空挖掘研究。 E-mail:

王浩成（1998— ），男，河北保定人，硕士生，主要从事时空大数据管理研究。E-mail:

收稿日期: 2022-10-05

  修回日期: 2022-12-25

  网络出版日期: 2023-06-30

基金资助

湖北省珞珈实验室专项基金(220100010)

湖北省科技重大专项(2020AAA004)

收起

Urban Hotspot Detection from the Data Stream of Taxi Pick-up and Drop-off based on Distributed Multistage Grid Clustering

  • WANG Haocheng ,
  • XIANG Longgang , * ,
  • GUAN Xuefeng ,
  • ZHANG Yeting
Expand
  • State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China
*XIANG Longgang, E-mail:

Received date: 2022-10-05

  Revised date: 2022-12-25

  Online published: 2023-06-30

Supported by

Fund of Hubei Luojia Laboratory, China(220100010)

Key Science and Technology Program of Hubei Province, China(2020AAA004)

Fold

摘要

城市热点区域的实时探测能够提高管理者对突发事件的响应能力。随着物联网、通信技术的发展，出租车运单的起讫信息实时上传至数据中心，形成了持续的上下客数据流。考虑到出租车具有全天候运营、全区域覆盖、数据时空分辨率高等特点，其上下客数据流可作为城市热点区域实时探测的有效信息源。目前，面向静态上下客数据集的热点区域探测方法不支持流式数据的处理，难以直接应用于实时的热点区域探测，而现有流式聚类算法难以同时满足低聚合成本、任意形状类簇识别、灵活扩展性等要求。面对以上挑战，本文基于分布式流计算技术，设计了适用于出租车上下客数据流的城市热点区域探测算法，基本思想为将上下客数据流映射至网格状监控单元，并以时间窗口为单位统计各监控单元热度，在此基础上进行热点单元的分布式识别，最终将热点单元汇聚为热点区域。为了避免分布式算法中聚合算子的性能瓶颈，本文进一步设计了由冗余分区、链接识别、修正规则构建、区域ID修正、区域生成等步骤组成的多阶段分布式区域合并算法。最后，本文基于分布式流计算框架Flink实现了上述算法，并使用武汉市出租车数据集、纽约市出租车上下客数据集模拟数据流开展实验，结果表明本算法可以高效挖掘城市空间的热点区域分布及其动态变化，在并行度为8时吞吐量可达9万条/s，具有较好的性能与可扩展性。

关键词： 出租车上下客; 数据流; 热点区域探测; 分布式计算; 网格聚类; 实时; 武汉市; 纽约市

本文引用格式

王浩成 , 向隆刚 , 关雪峰 , 张叶廷 . 基于出租车上下客数据流与分布式多阶段网格聚类的城市热点区域实时探测方法[J]. 地球信息科学学报, 2023 , 25(7) : 1514 -1530 . DOI: 10.12082/dqxxkx.2023.220753

Abstract

Real-time identification of urban hotspot areas can improve the response ability of city managers on emergencies. With the development of the Internet of Things and communication technology, the starting and ending information of taxi trips can be uploaded to the data center in real-time, forming a massive and continuous data stream of pick-up and drop-off events. Taxi is a welcoming means of transportation, and have characteristics of all-weather operation, full regional coverage, and high spatial-temporal resolution, so its pick-up and drop-off data stream can be used as a high-quality data source for real-time identification of urban hotspots. However, the hotspots area identification methods aimed at historical data sets have a high delay and can’t meet the real-time requirement. At the same time, the existing clustering algorithm based on distributed streaming processing technology is difficult to meet all the requirements including low aggregation cost, good scalability, and supporting arbitrary shape cluster recognition when facing pick-up and drop-off streams. Based on the distributed stream processing technology, an urban hotspot area identification method suitable for taxi pick-up and drop-off data stream is designed in this study. By mapping the real-time pick-up and drop-off records to grid monitoring units, we can obtain the heat value of each monitoring unit for each time window, filter the monitoring units which have higher heat values than a specified threshold as hot units, and finally gather the hot units of same time window into hotspot areas. To avoid the performance bottleneck of the aggregation operator in distributed region identification, a multi-stage distributed hot area aggregating method is designed. The method is implemented on Apache Flink, and the pick-up and drop-off data stream is simulated with the historical taxi trip records from Wuhan and New York City. The results show that: (1) The spatial distribution and status of hotspots differ from time to time, which is related to citizens' activities at different times; (2) Using smaller monitoring units can get finer spatial positions of each hotspot area; (3) Our method can accurately identify the hotspot areas using different parameter pair of monitoring unit sizes and hotspot thresholds; (4) The method has excellent throughput which increases with the computing parallelism and reaches 90k/s with parallelism at 8. The proposed method can correctly capture the spatial distribution of urban hotspot areas of each period in real-time and has good performance and scalability.

Key words： the pick-up and drop-off; data stream; hotspot area identification; distributed computing; grid-based clustering; real-time; Wuhan; New York

1 引言

城市热点区域是指在一定时段内，存在大量人群聚集活动，引发较大交通流量的局部区域[1-2]。显然，受城市功能分布、人群移动模式、社会经济事件等影响，城市热点区域的时空位置及其空间分布呈现出规律性，但也表现出一定的随机性。城市热点区域的实时探测能够反映热点区域在城市空间的实时分布及其动态变化，将为城市管理者的交通管制、安全保障、运力调配，以及居民的出行规划提供决策依据[3]。
城市居民在出行时有多种出行方式可供选择，如轨道交通、常规公交、出租车、自驾等，其中，出租车因其全天候运营、全路网覆盖、交通成本低等特点，已经成为了居民出行的重要交通工具[4]。随着传感器技术的发展、物联网的建设以及各类LBS应用的普及，具有时空维度的出租车上下客事件正源源不断上传到城市数据中心，形成持续的实时上下客数据流，成为城市热点区域实时探测的重要数据源。图 1为武汉市2015年5月2日早晨、夜间2个时间窗口内三地的上下客情况。其中，早晨的就医挂号需求较多，与同济医院早晨上下客数量远多于夜间相符；而早晨较多商铺尚未营业，且夜间的购物需求较多，故循礼门商圈夜间的上下客数量远多于早晨；武汉站在早晨、夜间均有较多旅客的活动，故早、晚的上下客点都较多。以上示例说明基于时间窗口的城市热点区域实时探测具有可行性。为此，本文尝试从出租车上下客数据流入手，以时间窗口为单位，开展城市热点区域的实时探测研究。据笔者所知，已有一些文献[1]—[3]利用出租车上下客事件来识别城市热点，但其时间粒度至少为日，难以满足热点区域的实时探测需求。
图1 武汉市多地多时段上下客点

Fig. 1 Pick-up and drop-off events at different time and place in Wuhan

基于历史上下客数据集的城市热点区域识别通常作为居民出行、城市空间特征分析的前置步骤，目前已有成熟且多样的解决方案，可以大致分为基于核密度、空间统计、空间聚类3种类型。在基于核密度的方案中，唐炉亮等[5-6]利用对出租车上下客事件轨迹呈现的线状特征，提出线密度探测模型并以密度峰值区域作为热点区域。羊琰琰[7]、谷岩岩等[8]利用核密度算法构建密度场，基于密度值发现热点区域。Hu等[9]利用核密度估计法提取了出租车聚集区域，并基于密度表面的拓扑结构分析城市热点变化。Chen等[3]基于局部最大密度研究了细微空间尺度下的热点区域分布；在基于空间统计的方案中，王宇环等[10]基于Getis-Ord Gi*发现空间上的上下客聚集，并结合城市功能区分析居民出行的时空特征；在基于聚类的方案中， Zhao等[1]在决策图和数据场理论与方法的基础上，研究了一种基于决策图和数据场的轨迹聚类方法，并用于居民日常出行热点区域的提取。Shen等[11]基于DBSCAN及其变种算法识别热点区域。周勍等[12]将上下客点映射至网格中，利用数据场理论计算各网格势值，最终利用阈值分割与网格聚类提取城市热点区域。Xia等[2]将上下客点映射至路网后，在网络空间中使用数据场聚类识别热点区域。
总体而言，以上方法从空间相关性、密度聚类、网格聚类等角度进行热点区域识别，并均取得了良好的识别效果。然而，这些研究均在离线环境下处理历史数据集，且未考虑持续到达数据流的高效计算，难以直接满足城市热点区域实时探测的低延时要求。
虽然基于实时上下客数据流的城市热点区域实时探测目前仍缺少研究，但面向数据流的聚类算法已有一些探索。数据流聚类算法由传统批聚类算法发展而来，旨在以有限的计算资源，挖掘无限的流数据的实时聚类特征。为降低数据维护压力，并保持计算结果的时效性，数据流聚类算法通常以概要数据结构与时间衰减模型作为聚类基础。另外，为避免数据更新时的重复聚类，一些数据流聚类算法还支持增量聚类[13]。
现有的数据流聚类算法可以分为基于划分的、基于层次的和基于密度的算法[14]。前2种流聚类算法基于记录之间的距离进行聚类，其中以Aggarwal等提出的CluStream[15]为代表，该算法采用在线-离线两阶段框架，在线阶段以短暂的时间窗口将数据流汇聚为微簇并存储，离线阶段负责在接收到聚类请求后，利用K-Means对微簇宏聚类，得到最终聚类结果。该两阶段框架满足了增量聚类要求，被许多流聚类算法借鉴，如HPStream[16]、D-Stream[17]、DenStream[18]。然而，CluStream、HPStream采用的基于划分的聚类算法需要预设参数值，不能识别多种形状的类簇，且需要多次遍历数据集，以上缺点使其不能用于城市热点区域探测场景。
基于密度的流聚类算法以D-Stream[17]与DenStream[18]为代表。D-Stream的在线组件将输入数据流映射至网格，离线组件基于时间衰减模型计算网格密度，根据密度定期执行网格聚类；DenStream以微簇组织数据流，并在在线阶段基于时间衰减维护微簇信息，离线阶段负责接收聚类请求，并对现有微簇执行DBSCAN聚类。这些算法避免了CluStream中由K-Means导致的缺陷，但其默认执行环境为单机，扩展性不佳。
分布式计算是提升算法性能的有效手段。随着分布式计算及大数据的发展，一系列针对数据流的分布式计算框架被提出，其中具有代表性的框架包括Flink、Storm和Spark Streaming等，它们都使用DAG（Directed Acyclic Graph，有向无环图）形式的数据流图，抽象流计算作业的逻辑，具有类似的编程模型、数据分区策略，但在状态管理、消息传递保证、容错恢复、社区支持、高级语言支持等方面有各自的特点[19]。
分布式流计算框架选择虽多，但目前基于分布式流计算框架的聚类研究仍然较少。Karunaratne[20]等在Storm的基础之上，分别以共享内存、非共享内存的方式实现了CluStream的并行版本，虽然摆脱了单机性能限制，但其采用的基于划分的聚类算法无法识别任意形状的城市热点区域。除此之外，利用时间窗口缓存数据流形成窗口快照，对各窗口快照作分布式批聚类也是一个可选的方案。MR-DBSCAN[21]基于MapReduce架构，以预处理、局部 DBSCAN、获取需要合并的类簇、全局类簇聚合四阶段聚类的形式，将DBSCAN改进为分布式版本，避免使用单一节点聚合分布式聚类过程中的中间结果，取得了良好的可伸缩性与较高的吞吐量；RP-DBSCAN[22]基于伪随机分区与两层单元字典结构实现了并行的DBSCAN，并基于Spark实现，为分布式聚类的数据分区策略提供了新的思路。但是，以上研究均直接对数据点聚类，大量的待聚类对象使得聚类算法耗时较久，无法保证实时城市热点探测的时效性。PatchWork[23]基于分布式批计算引擎Spark实现网格聚类算法，减少了待聚类对象，得到了线性的计算复杂度，但其密度网格聚合的工作由集中式单节点执行，在处理超大体量数据时，又将面对单机性能限制。
面对以上挑战，本文基于分布式流计算技术设计了分布式多阶段网格聚类算法，并将其与出租车上下客数据流结合，应用于城市热点区域探测。该算法支持流式计算，可识别任意形状热点区域，具有灵活扩展性、高性能等诸多优势。该算法的核心思想为：以网格状监控单元作为热点区域的最小组成单位，将上下客数据流映射至监控单元后，以时间窗口为单位统计各监控单元热度并筛选得到热点单元。接下来将热点单元按分区网格分片，执行分布式热点区域探测，进一步聚合得到热点区域。为避免分布式聚类中的单节点性能瓶，设计了基于链接识别、修正规则构建、区域ID修正、区域生成等多阶段的分布式子区域合并算法。分别使用武汉市、纽约市数据集对算法有效性、性能进行实验，结果表明本文方法能够较准确地识别出城市热点区域，且具有良好的性能与可扩展性，能够以较低延时实时完成城市热点区域实时探测。

2 研究方法

本文主要关注基于上下客数据流的城市热点区域实时探测，首先给出相关的形式化定义。各符号及其含义见表1。
表1 符号定义

Tab. 1 Symbol definition

符号 定义
S 上下客数据流
p i 上下客记录
g 监控单元
W 时间窗口
v 热点阈值
g W ' 时段 W下的热点监控单元 g
R r W 时段 W下ID为 r的热点区域
定义 1 上下客数据流。上下客数据流为由实时生成的出租车上下客行为记录组成的无边界序列，记为 S = p 1 , p 2 , p 3 , …。其中， p i为一条上下客记录，由该上下客行为发生的位置、时间戳组成，即 p i = ( x i , y i , t i )。
城市上下客数据流体量巨大，直接对上下客记录点作实时热点识别需要大量计算资源。因此，本研究将上下客数据流采样至网格状监控单元，并将其作为热点区域的基本组成单位。将持续到达的上下客数据流映射至不同的监控单元，实现上下客数据流到监控单元数据流的转换。监控单元的具体定义如下。
定义 2 监控单元。表现为二维空间内长宽均为 s的连续、不重叠网格，记为 g。监控单元ID由其在空间内的行号与列号确定。对于任意上下客记录 p i = ( x i , y i , t i )，都根据其空间位置映射至唯一监控单元 g p i = x i s , y i s。
定义 3 邻近监控单元。本研究以8-邻域作为监控单元的邻近判定标准。类似于DBSCAN算法中密度可达的概念，对于监控单元 g i , g j i ≠ j，若存在监控单元序列 { c 1 , c 2 , c 3 … , c T }，满足 c 1 = g i、 c T = g j，且任意 c k、 c k + 1 ( 1 ≤ k < T )互为邻近监控单元，则称 g i , g j互为邻近可达单元。
城市热点区域实时探测旨在持续获取最近时段的热点区域，而较早时的上下客记录与当前时刻热点区域结果无关。因此，本文使用滑动窗口模型，将无界、连续的上下客数据流转换为由时间窗口切分的有界、离散集合，并统计各时间窗口中各监控单元的上下客数量，进而得到可作为热点单元的监控单元。
定义 4 时间窗口。时间窗口代表一左开右闭的时间范围，以 W [ t s t a r t , t e n d )表示。本文的时间窗口使用滑动窗口模型。滑动窗口模型由窗口时长、滑动步长共同定义，例如“每5分钟一个的长为10分钟的窗口”，滑动步长可小于窗口时长，故不同滑动窗口间可能存在重叠。
定义 5 热点单元。给定上下客数据流 S、时间窗口 W [ t s t a r t , t e n d )、监控单元 g、热点阈值 v，取 S在 W内落于 g的上下客数据集合为 G W , g = { p 1 , p 2 , … , p n }，其中任意上下客记录 p i = ( x i , y i , t i )，均满足 p i所处监控单元 g p i = g， t s t a r t ≤ t i且 t i < t e n d。若集合大小 G W , g ≥ v，则称监控单元 g在时间窗口 W下为热点单元，记为 g W '。
图2给出了一个利用滑动窗口识别热点单元的示例，若以 v = 4，则在时间为10:20时得热点单元 g W 0 , 0、 g W 0 , 1，10:35时得热点单元 g W 1 , 1、10:50时得热点单元 g W 2 , 0，可以注意到，滑动步长的长度与滑动窗口间的闭合间隔相同，反映了各时刻热点区域结果间的间隔。
图2 基于滑动窗口的热点单元识别

Fig. 2 Hotspot unit identification based on sliding window

定义 6 热点区域。给定时间窗口 W热点区域由 W内邻近可达的热点单元集合组成，即 R r W = g W , 1 ' , g W , 2 ' , … , g W , n '。其中， r为该热点区域ID， g W , i '为组成该热点区域的一热点单元。对于任意 g W , m ' 、 g W , n '， 1 ≤ m < n ≤ k，均有 g m 、 g n互为邻近可达单元。
基于上下客数据流实现城市热点区域实时探测的基本步骤为：给定上下客数据流 S，将其中各上下客记录映射至不同监控单元 g后，按时间窗口 W为单位分组，识别时间窗口 W下的热点单元。将同属 W并彼此邻近的热点单元拼接，得到城市热点区域 R r W。
图3是针对时间窗口 W的热点区域识别样例， v = 2。该示例将时间窗口 W内的上下客记录按空间位置映射至不同的监控单元内，结合热点阈值 v筛选出热点单元 g W , 0、 g W , 1、 g W , 3，并将临近可达的热点单元合并，形成热点区域 R 1 W。
图3 热点区域识别样例

Fig. 3 Example of hotspot area identification

2.1 算法处理流程

分布式流处理技术使用算子（Operator）抽象数据的处理逻辑，数据流沿着由算子连接而成的管道（Pipe），从上游算子流向下游算子，可以以数据流图的形式表达实时数据流的处理逻辑。同时，每个算子可以由多个分布式计算节点并行实现。本文利用分布式流处理技术，设计了基于出租车上下客数据流的分布式热点区域实时探测算法。本文算法的数据处理流图见图4。
图4 分布式数据流

Fig. 4 Distributed data flow diagram

上下客数据流中的上下客记录以带有位置信息的空间点为载体，首先在监控单元映射算子中，将每条上下客记录根据其坐标信息映射至对应的监控单元，按监控单元ID分流后，在热点单元识别算子中按照监控单元ID与时间窗口，将连续数据流分割为离散数据集，并累积各监控单元在时间窗口内的上下客记录数量，最终根据热点阈值 v判断各监控单元在此窗口内是否为热点单元，若是热点单元则发送至下游。
本文算法相比于简单的分布式网格聚类算法，改进之处体现在热点网格到分布式节点的分发、热点区域的合并2个方面。传统方法将待聚类网格按照空间位置分发至不同的算子上作区域识别，后将其集中至单节点上，使用空间索引查询待合并区域间的拓扑邻接关系，实现区域合并，单节点易成为整个集群的瓶颈，扩展性较差。为避免前述方案的问题，本文借鉴MR-DBSCAN的多阶段聚合思想，设计了适用于监控单元的分布式热点区域识别与聚合算法，利用少量的数据冗余与多阶段聚合，减轻全局聚合节点的计算压力。该算法中，热点单元首先被发送至冗余分区算子，在此之后，以分区网格（见定义7）为单位并行执行热点区域识别，得到子区域，再以多阶段聚合的方式，修正区域ID、完成子区域合并，最终得到由各时间窗口内的热点区域输出流。
监控单元映射与热点单元识别部分的处理逻辑相对简单（图3），本文不再赘述。下文将重点介绍冗余分区、区域识别、区域合并等分布式热点单元汇聚算法的核心步骤。

2.2 冗余分区

分布式流处理技术支持对原数据流按键归约，将具有某种关联的元素汇聚至某节点做局部计算。通过为属于同一分区的数据分配相同的键，即可实现数据流的分区性归约，从而实现以分区为粒度的并行计算。并行计算后的结果可以再由后续算子汇聚整合，最终得到与单机计算同样准确的计算结果。
本文基于分布式流处理技术探测城市热点区域，故需对热点监控单元制定恰当的数据分区策略，以实现热点区域识别的并行化。均匀网格分区在实时环境中无需更新，具有稳定的性能，因此本文采用分区网格作为监控单元的分区依据,其定义如下。
定义 7 分区网格。分区网格为将二维研究空间作均匀网格划分后的网格。给定分区网格边长 p S i z e和监控单元 g（监控单元中心坐标为 x、 y），则监控单元 g对应的分区网格 P = x p S i z e , y p S i z e。
分区网格彼此紧密排列且互不交叠，是数据切片并分发至下游分布式算子的基本单位。城市热点区域可能跨越多个分区网格，不可避免地出现跨分区网格的热点区域被分区网格分割，并行识别出多个子区域的状况，故在并行的热点区域识别后，仍需将全部区域聚合。简单的方案将热点区域传输至一个全局计算节点实现聚合，该节点将承担较大的计算负载与网络传输压力，易成为整个系统的性能瓶颈。
本文在简单方案的基础上，设计了适用于监控单元的冗余分区策略，即将监控单元分配至其所处分区网格的同时，冗余分配至到其邻近分区网格。以分区后总数据量小幅增加为代价，配合后续的子区域识别与子区域合并，减轻全局聚合节点的计算任务，更高效地完成区域识别。
在本文的热点区域识别场景中，监控单元的大小 s为米级，而分区网格大小 p S i z e为千米级，故分区网格远大于监控单元，但受篇幅限制，无法直观展示二者的大小关系。在不影响正确性的前提下，本文在图5中抽象了监控单元与分区网格的大小差异，并以此图为例说明冗余分区流程。
图5 冗余分区示意图

Fig. 5 An example of redundant partition

g 1位于分区网格 P 4中，其邻近监控单元 g 3 、 g 4 、 g 5分别位于分区网格 P 1 、 P 2 、 P 3中，因此 g 1与 P 1 、 P 2 、 P 3邻近，故在对 g 1的热点单元 g W , 1 '应用算法1后，可以得到以下二元组： P 4 , g W , 1 ' , P 1 , g W , 1 ' , P 2 , g W , 1 ' , P 3 , g W , 1 '。 g 2位于分区网格 P 1中，但不与其他分区网格邻近，因此，在对 g 2的热点单元 g W , 2 '应用算法1后，仅可得二元组： P 1 , g W , 2 '。
具体而言：对任意到达冗余分区节点的待分区热点单元 g W '，基于流计算技术的数据扁平化操作，执行算法1。对到达冗余分区节点的所有热点单元 g W '执行算法1后，可得由分区网格ID与热点单元信息组成的二元组数据流。以分区网格ID为键将其分组，并以分区为单位发往下游的进行分区级子区域识别。
算法 1 冗余分区
输入：监控单元 g ,分区网格大小 p S i z e
输出：分配至分区网格后的二元组 ( P i , g W ' )
1 获取 g W '所在分区网格 P
2 输出 ( P i , g W ' )并标记 P已访问
3 遍历 g W '的邻近监控单元 g x 1 ≤ x ≤ 8
4 获取 g x所在分区网格 P x，若 P x未被访问过
5 输出 P x , g W '
6 标记 P x已访问

2.3 区域识别

各区域识别节点接收经冗余分区后，以分区网格为依据对热点单元流分组，并以分区网格为单位作并行的热点区域识别。在这种数据分区方法中，位于分区网格边缘的热点区域可能被多个分区网格切分至不同的计算节点，故在此步骤后仍需额外的合并操作。下文将介绍区域识别算子的热点区域识别过程，及为跨分区的区域合并而设计的额外操作。
经冗余分区后，负责某分区网格的节点所接收的热点单元可能来自多个邻近分区网格，为更清晰地说明分布式热点区域识别与合并流程，首先给出更多相关定义：
定义 8 分区过渡带。分区过渡带是由2个相邻分区网格唯一确定的空间范围。给定邻近监控单元 g i与 g j，其对应分区网格分别为 P i与 P j，若 P i ≠ P j，则称 g i与分区 P j邻接。若位于分区网格 P i的监控单元 g i与 P j邻接，则 g i位于 P i , P j的分区过渡带上，该分区过渡带记为 B P i , P j。
定义 9 热点单元子集。给定一个分区网格 P和一个时间窗口 W，热点单元子集指 W中的热点单元经冗余分区后，被分区至 P的集合，记为 S e t P W = { g W , 1 ' , g W , 2 ' , … , g W , k ' }。
定义 10 本地单元与外来单元。给定分区网格 P在时间窗口 W的热点单元子集 S e t P W，对于热点单元 g W , i ' ∈ S e t P W，令该热点单元对应的分区网格为 P i，若 P i = P，则称 g W , i '为 P的本地单元。否则，称 g W , i '为 P的外来单元。
区域识别算法流程见算法 2。该算法从本地单元出发，作深度优先搜索，拼接邻近可达监控单元，获取热点区域 R p , k W，并记 r P , k为该热点区域的ID， P为产生该区域的分区网格ID， k为该分区网格在 W下的递增数值。由于分布式流计算技术中不同窗口算子的输出时间戳不同，因此同一时间窗口下各分区内生成的热点区域ID将互不重复。
根据搜索过程中是否遇到外来单元，判断该热点区域是否被分区网格切割：若未被切割，该热点区域将作为完整区域输出；若被切割，则当前热点区域为一完整区域的子区域，尚需进一步合并。
与汇聚全部子区域至单节点，根据子区域几何邻近关系作实现子区域合并的方案不同，本方法通过修正子区域ID，并基于新的区域ID将子区域分组，间接地完成子区域合并。区域识别作为子区域合并的前置步骤，将会把子区域及分区过渡带上的监控单元信息分别发送至区域ID修正算子与链接识别算子中。
综上，区域识别节点接收分区网格的热点单元后，以时间窗口为单位得到热点单元子集 S e t P W，并向3条数据流 S 1 、 S 2 、 S 3输出结果，它们分别为完整区域流、待修正区域ID的子区域流、用于生成区域ID修正规则的过渡带单元流。
图6给出了某时间窗口内并行区域识别的一个简单案例，此处略去 W符号。其中，灰色网格代表非热点监测单元，其他颜色代表热点监测单元。所有热点单元被冗余分区至4个分区网格并行计算，其中位于分区过渡带的监控单元均以编号标识。图6两侧展示了各分区内并行热点区域识别结果。表2中展示了各分区网格作区域识别后 , S 1、 S 2、 S 3中的输出结果。
图6 并行热点区域识别示意

Fig. 6 An example of hotspot area identification in parallel

表2 区域识别示例中各分区输出

Tab. 2 Output streams of each partition on the example

S 1 S 2 S 3
P 1 R P 1 , 1 — —
P 2 R P 2 , 2 R P 2 , 1 ( B P 2 , P 4 , r P 2 , 1 , g 2 )
P 3 — R P 3 , 1 ( B P 3 , P 4 , r P 3 , 1 , g 6 )
P 4 — R P 4 , 1 , R P 4 , 2 ( B P 3 , P 4 , r P 4 , 1 , g 6 ) ( B P 2 , P 4 , r P 4 , 2 , g 2 )

2.4 子区域合并

子区域合并部分将借鉴MR-DBSCAN的多阶段聚类思想，分解为4个相互协作的阶段：链接识别、修正规则构建、区域ID修正、区域生成（对应图 4中5.1—5.4）。不同于直接将所有子区域数据汇聚至单一节点并拼接的方案，本文通过把应合并的多个子区域的ID修正为统一值，再以新的区域ID为标准对子区域流分组，间接完成子区域的合并工作。该部分中，仅修正规则构建阶段由单节点负责，其余部分均可以并行完成，能充分利用分布式技术的优势。

2.4.1 链接识别

链接识别节点以分区过渡带 B P a , P b、时间窗口 W为单位，处理分组后的边界单元流 S 3，识别各分区过渡带上由不同分区网格产出的应被合并的子区域，并将其ID组合为链接对，该链接对由二元组 ( r P a , i , r P b , j )表示。对于分区过渡带 B P a , P b与时间窗口 W，链接识别流程见算法3。
可以证明，基于算法2与算法3，所有应被合并的子区域均能在本部分得到对应的链接对：若有一跨分区网格 P 1 与 P 2的热点区域 R，其在两分区中的子区域ID分别为 r p 1、 r P 2，且必然存在 g 1 ∈ r p 1、 g 2 ∈ r P 2，满足 g 1与 g 2互为邻近单元。同时，在负责分区网格 P 1的区域识别节点中， g 1为 P 1的本地单元， g 2为 P 1的外来单元。同样地，在分区 P 2的区域识别节点中，必有 g 2为 P 2的本地单元， g 1为 P 2的外来单元。由算法2可知，负责 P 1， P 2的两个区域识别节点将分别输出 B 1,2 , r P 1 , g 1、 B 1,2 , r P 2 , g 1，因此可以通过监控单元 g 1桥接两个子区域ID，获取链接对 ( r P 1 , r P 2 )。
算法 2 区域识别
输入：热点单元子集 S e t P W
输出：全局区域流 S 1 ,子区域流 S 2 ,过渡带单元流 S 3
1 初始化 k = 0
2 遍历 S e t P W中的监控单元 g W , i '
3 若 g W , i '为本地网格且未被访问过
4 k自增
5 初始化新的区域 R r P , k W
6 初始化flag为假
7 初始化栈Stack; g W , i '入栈
8 While
9 取栈顶 g W , m '并将其加入 R r P , k W
10 标记 g m已访问
11 遍历 g m的邻近单元，记为 g n
12 若 g W , n ' ∈ S e t p W且为未访问的本地单元
13 g W , n '入栈
14 若 g W , n ' ∈ S e t p W且为未访问的外来单元
15 获取 g n的原分区 P n
16 置flag为真
17 若 P < P n：输出 ( B P , P n , r P , k , g m )至 S 3
18 否则，输出 ( B P n , P , r P , k , g n )至 S 3
19 若flag为假：输出 R r P , k W至 S 1
20 否则，输出 R r P , k W至 S 2
算法 3 链接识别
输入： S 3内属于分区过渡带 B P a , P b、窗口 W的数据集 S e t
输出：链接对数据流 S l i n k
1 初始化以 g为键、区域ID为值的 M a p P a , M a p P b
2 对 S e t中的每一个 r i , j W , g k
3 若 i = P a 4 M a p P a . p u t g k , r i , j W
5 否则
6 M a p P b . p u t g k , r i , j W
7 对 M a p a中的每一个 < g k , r a , j W >
8 若在 M a p a中可得键为 g k的值 r b , j W
9 输出 ( r a , j W , r b , j W )至 S l i n k

2.4.2 修正规则构建

在得到各分区过渡带上的子区域链接对后，可以实现跨两个分区网格的热点区域子区域ID统一，但尚不支持跨更多分区网格的热点区域的子区域合并。因此，仍需将所有的链接对再汇聚至单节点，才能得到最终的修正规则。
修正规则构建阶段在全局仅有一单节点，该节点接收算法3生成的链接对流 S s i n k，以时间窗口为单位汇聚链接对，在时间窗口闭合时，为该时间窗口内的各子区域ID生成相应的修正规则。每个修正规则表现为一个二元组 r i , j W , r t W，表示ID为 r i , j W的子区域，其ID应被修正为 r t W。应被合并的子区域对应的修正值相同。修正规则构建基于并查集算法实现，伪代码见算法4。
算法 4 修正规则构建
输入： S l i n k时间窗口 W中接收的链接对数据集 S e t
输出：修正规则流 S f i x
1 初始化以区域ID为键和值的Map
2 对 S e t中每个链接对 ( r a , i W , r b , j W )
3 若Map中没有键为 r a , i W或 r b , j W的条目
4 Map.put ( r a , i W , r b , j W )
5 Map.put ( r a , i W , r b , j W )
6 否则，若Map仅有键为 R a , i W的条目
7 令 r x W = M a p . g e t ( r a , i W )
8 M a p . p u t ( r b , j W , r x W )
9 否则，若Map仅有键为 R b , j W的条目
10 令 r x W = M a p . g e t r b , j W
11 M a p . p u t ( r b , j W , r x W )
12 否则：
13 r x W = M a p . g e t r a , i W； r y W = M a p . g e t r b , j W
14 若 r y W ≠ r x W： M a p . p u t ( r y W , r x W )
15 对Map中的每个条目 < r x W , r y W >
16 当 M a p . g e t ( r y W ) ≠ r y W , 循 环 执 行
17 r y W= M a p . g e t M a p . g e t ( r y W )
18 输出 r x W , r y W至 S f i x

2.4.3 区域ID修正与区域生成

本部分基于修正规则流 S f i x，修正 S 2中的各区域记录的区域ID，使应被合并的区域具有相同的编码。汇聚具有相同区域ID的子区域记录，并拼接为最终的热点区域。
流计算中，时间窗口闭合时产生的记录将以 W闭合时间的前1 ms作为其事件时间。由图4可知，各时间窗口的 S 2先于同窗口的 S f i x生成，但由于它们由相同的时间窗口触发，故具有相同的事件时间。因此，可以基于事件时间完成 S 2与 S f i x的关联操作。
本文基于区域ID对 S 2与 S f i x分组，并以之作为关联键，基于事件时间关联同时刻的子区域记录与修正规则记录。在此基础上，将区域记录的区域ID更新为修正值，同时以新的修正后的区域ID为键，输出至区域生成节点。
各区域生成节点接收以区域ID分组后的区域流，并按时间窗口 W聚合，拼接同属 W的子区域几何，最终得到目标热点区域。
最终，本方法利用多阶段聚合的方式完成了各节点生成的热点区域的全局合并工作，其中全局算子仅需接收并处理子区域ID链接对，输出子区域ID的修正规则，而实际的合并工作借助流计算技术中的分布式关联完成，相比于传统的直接将所有子区域数据汇聚至全局算子并拼接的方案，极大降低了分布式集群中全局汇聚算子所在节点的工作负载。

3 实验及结果分析

3.1 实验环境与数据准备

为了验证基于出租车上下客的城市热点区域实时探测算法的有效性与性能，本文基于Flink实现了上述算法（代码地址： https://github.com/haochengw/FlinkHotAreaDetect），并基于物理机上的3个虚拟机，搭建了Flink与Kafka集群。物理机配备Intel(R) Xeon(R) Gold 6240处理器，其基本频率2.60 GHz，最大睿频频率可达3.90 GHz，内部含18个内核，每个内核包含2个逻辑核心，共36个逻辑内核。内存总量为256 GB，速率为2933 MT/s。另外还配有1 TB SSD与4 TB HDD。
各虚拟机安装Ubuntu 20.04 LTS操作系统，各分配了64 GB内存与8个逻辑CPU核心，且物理机与虚拟机操作系统均安装在SSD上，虚拟机所配备集群的软件版本见表3。
表3 集群软件版本

Tab. 3 Deployment details of experimentation clusters

软件名称 版本
Java JDK 1.8.0_261
Apache Flink 1.13.3
Apache Kafka 2.6.0
Apache Zookeeper 3.6.2
实验数据方面，为便于与实际情况类比，本文以作者所在的武汉为研究对象，并使用了武汉市2015年5月2日7 188辆出租车的运营数据，将其用于评估算法的敏感性、有效性。武汉市数据集经清洗后，可得按时间排序的上下客记录502 580条，该数据量相对较少，故另选取了数据量更大、由纽约市出租车和豪华轿车委员会公开的2015年1月黄色出租车运单数据来评估算法的性能，该数据集共有上下客记录25 491 183条。2份数据集被加载至分布式消息队列Kafka Topic的24个分区中，Flink热点区域识别任务订阅并按时间顺序消费Kafka Topic，实现数据流的模拟与实时接入。热点区域识别结果将发送至相应的Kafka Topic中。

3.2 算法参数分析

热点区域识别结果受热点区域判定标准影响。本算法中，热点区域判定标准与3个因素相关：滑动窗口模型、监控单元大小 s、热点阈值 v。 W由滑动窗口模型切分而来，其滑动步长、窗口时长依具体应用场景的时效性要求而定，时效性要求越高，滑动步长、窗口时长均越小，但可供参考的上下客事件变少，而在上下客事件过少时，上下客的空间分布具有较大的随机性，将导致结果的准确性受到影响；在滑动窗口模型根据具体需求明确后， s将城市切分为监控单元，基于统一的阈值 v判断各监控单元在各时间窗口内是否为热点单元。 s代表热点区域的最小颗粒度， s越小，识别结果越精细。 v应结合滑动窗口模型、 s取值与上下客数据的统计信息而定。 v越低，被判定为热点的监控单元越多，得到的热点区域也越大，其区分性可能有所缺失。
本节以武汉市2015年5月2日出租车运营数据模拟实时数据流，使用该数据集模拟数据流时，平均每10 min约有3500个上下客事件，故使用10 min的时间窗口既能保证一定的规模的上下客数量，又使结果具有较高的时效性。因此，本实验中令滑动窗口的滑动步长与窗口时长同为10 min，即每 10 min基于过去10 min的上下客记录作热点区域识别。在此基础上，选取不同 s、 v的组合，讨论 s、 v的敏感性。

3.2.1 热点阈值

为保证可视化结果的可读性，本实验先取 s = 0.2 k m，后确定热点阈值的基准值。本文计算了各监控单元在2015年5月2日各时间窗口、各监控单元的上下客数量，统计得各上下客数量出现频数的分布图（图7（b））。图7（b）可视为单峰直方图，可在其上应用Robin[24]提出的适用于单峰直方图的分割算法：该算法假设直方图横轴低端存在一个高峰，将该峰顶点与直方图横轴最右端相连得到一条直线，以距离该直线最远点作为该直方图的分割阈值。将该算法应用于图7（b）后，得 v=6。本实验将在此基础上，调整 v的取值，分别执行热点区域识别作业，分析热点阈值的敏感性。
图7 各数据集不同 s下的上下客频次的出现次数与热点阈值选取

Fig. 7 Occurrences of pick-up and drop-off frequency with varying s and data sets and hotspot threshold selection

为便于对比，本实验聚焦武汉市城区（三环内）在2015年5月2日18时00分—18时10分的热点区域识别结果（图8），并统计了不同 v取值下，该时段的热点区域的数量、面积特征（表4）。
图8 武汉市不同热点阈值 v下的热点区域识别结果对比

Fig. 8 Hotspot areas in Wuhan obtained with varying v

表4 不同 v的热点区域统计信息

Tab. 4 Hotspot area statistics with varying v

v 热点区域数量/个 总面积/km2 平均热点单元数/个 单热点单元区域占比/%
5 99 5.40 1.36 76.77
6 62 3.28 1.32 80.65
7 41 2.20 1.34 78.05
结合图8与表4可见，当热点阈值 v以基准值为中心变化时，随着 v的上升，热点单元的判别标准变高，热点区域的数量、面积明显下降，但热点区域的平均热点单元数与单热点单元区域的占比变化不大，说明受影响的是热点区域的数量、面积。值得注意的是，若 v偏离合理的基准值而取极端小值，将有大量的监控单元将被识别为热点单元，使得热点单元间彼此连通，导致热点区域数量减少、总面积增大，甚至出现研究区域内大部分均为热点区域的现象，导致结果丧失区分性。因此，选取热点阈值 v时，应结合 s、 W的设置，分析上下客数据集在特定监控单元、时间窗口组合下的统计规律，确定适当的基准值，在此基础上结合对热点区域的数量、热度的具体要求，选取恰当值。

3.2.2 监控单元大小

本节讨论不同监控单元大小对算法结果的影响，除了应设置 s的不同大小，还需为 s确定恰当的热点阈值 v。由于上下客点均沿线状路网分布，而监控单元为方形网格单元，故不能简单地假设 v与监控单元的面积呈线性正比关系。在使用与4.2.1节相同的方法绘制不同 s对应的上下客出现频数图（图7(a)(b)(c)）后，发现均为单峰分布，故仍选用三角阈值法获取不同 s对应的 v基准值，使得不同 s、 v参数组合对应的热点区域语义相近，最终分别得到 s , v = 0.1 k m , 4、 ( 0.2 k m , 6 )、 ( 0.3 k m , 7 )。
为便于对比，本节聚焦武汉市三环内2015年 5月2日18:00—18:10的时间窗口，得可视化结果（图9）与相关统计信息（表5）。
图9 武汉市不同监控单元边长s下的热点区域识别结果对比

Fig. 9 Hotspot areas in Wuhan obtained with varying s

表5 不同 s的热点区域统计信息

Tab. 5 Hotspot area statistics with varying s

s/km 热点区域数量/个 总面积/km2 平均热点单元数/个 单热点单元区域占比/%
0.1 99 1.27 1.28 81.82
0.2 62 3.28 1.32 80.65
0.3 68 9.09 1.48 72.06
不同 s的热点区域识别结果的空间分布大致相同，而区别主要体现在热点区域的面积上： s越小，热点区域的面积也越小，且更难以分辨。对图9的比例尺而言，取 s = 0.1 k m的可视化效果较差。本实验将研究范围进一步缩小至汉口火车站附近，在更大的比例尺下，比较不同 s间热点区域识别结果的影响（图10）。可见， s越小，热点区域面积越小，同时形状越精细，如在 s = 0.1 k m时，可以看到热点区域对应的路口位置（如参照点A、D）。
图10 汉口站周边不同监控单元边长s的热点区域识别结果对比

Fig. 10 Hotspot areas obtained with varying s around Hankou Station

另外，在使用不同 s作热点区域识别时，同一时段、位置的识别结果并不相同，如参照点A在图10(a)、(c)中位于热点区域中，而在图10(b)中不是热点区域。类似的还有参照点B、参照点C。以上情况由不同 s、 v的取值组合与上下客点的空间分布造成，图11展示了 s , v = 0.1 k m , 4 、 0.2 k m , 6的情况下该现象的成因：图11(a)中， s = 0.2 k m的 g满足热点单判断条件，但 s = 0.1 k m的 g 0、 g 1、 g 2、 g 3均不能被判定为热点单元；图11(b)中， g 3满足热点单元条件，而 g不满足。本实验中不同监控单元大小对应的热点阈值由对应空间尺度的统计结果作单峰阈值选取而来，并未考虑不同监控单元大小间的联系，故图11所示现象无法避免。从另一个角度看，不同 s、 v的识别结果都准确识别了对应条件下的热点单元，故在具体应用中， s、 v的取值应与对热点区域空间尺度需求匹配。
图11 不同s、v组合对热点单元识别的影响

Fig. 11 The effect of varying s, v pairs on hotspot units

3.3 算法有效性分析

为便于验证基于出租车上下客数据流的城市热点区域实时探测算法的效果，本节选取武汉市核心城区（三环内）作为研究区域，结合4.2节对相关参数的讨论，以 s = 0.3 k m、 v = 7为参数，取滑动窗口时长与步长均为10分钟，使用Flink接入并处理Kafka内模拟的武汉市2015年5月2日上下客数据流，并选取8:00—8:10、14:00—14:10、20:00—20:10三个时间窗口的结果可视化（图12）。为便于区分各热点区域，本实验以热点单元的上下客数量为热点区域的热度值，并基于热度值的统计分布规律，使用自然断点法将热度值分级，得到多级热点区域，其中一级热点区域的热度值最高。将本实验结果与相似研究[1,12]的结论对比，评估本算法的有效性。
图12 武汉市2015年5月2日多时段热点区域空间分布

Fig. 12 Hotspot areas in Wuhan on May 2nd, 2015 at varying time

从热点区域的时序变化上看，由图12可见，在2015年5月2日8:00，热点区域主要出现在火车站、大型医院、商圈附近，面积大、热度高的热点区域位于武昌站、汉口站、武汉站、同济医院、儿童医院周边，部分商圈、文旅景点、居民区周边也出现了一些热点区域；5月2日14:00热点区域明显增多，医院周边的热点区域有所减少，新增的热点区域主要在商圈（如光谷商圈、武广商圈、循礼门、洪山广场等）及旅游休闲场所（如黄鹤楼、湖北省博物馆等）周边。此时面积较大的热点区域位于光谷广场、武昌站、汉口站、武广商圈，上下客较密集的区域在汉口站、循礼门、武汉站；5月2日20:00，居民区中出现了较多零散的单热点单元区域，同时商圈、火车站附近的热点区域仍然较多，与夜间市民的娱乐、返程活动相符。此时面积较大的热点区域位于武胜路商圈、彭刘杨社区、菱角湖商圈、吉庆街、江汉关、万松园等地。上下客较密集的区域在汉口站、武广商圈、循礼门等附近。
但是，本文方法的识别结果仍有瑕疵。例如，江汉路和楚河汉街均为武汉市著名的商业步行街，分别长1.6 k m、1.5 k m，在五一等节假日时顾客众多。但在图12（b）（c）中，2个步行街的热点区域仅位于其周边入口处，而步行街主体内未能识别出线状热点区域。这是因为步行街内部机动车限行，导致热点在空间上存在偏离。此外，江汉路等地点对于公共交通更为友好，其周边的热点区域也难以通过出租车上下客数据揭示。
总体而言，2015年5月2日不同时刻的热点区域识别结果与市民在节假日的出行、就医、休闲、购物活动规律相符：早上主要是出行、就医挂号需求，而购物、休闲需求较少；下午开始有较多的购物、休闲活动；夜间有较多市民返程休息。另外，武汉市作为全国重要的铁路枢纽，节假日期间承载大量的客运需求，本文方法也准确地识别出了各火车站周边的持续型热点区域。表明本文方法能够准确的识别出大部分热点区域。

3.4 算法性能分析

实时计算中重要的性能评估指标包括延迟与吞吐量。延迟为一条记录从生成至输出结果的时延。吞吐量为实时计算任务每秒处理的记录数。在使用历史数据模拟数据流时，每条记录的生成时间与执行实验的时间具有较大的差值，导致测算的延迟无实际意义，故本节仅使用吞吐量作为算法性能评估指标。
本文算法中涉及算法性能的参数有分区网格大小 p S i z e与分布式集群的计算并行度。 p S i z e过大或并行度为1时，所有热点单元的聚合由单节点处理，算法退化为集中式计算。故本节将讨论不同并行度、 p S i z e对算法吞吐量的影响。实验数据方面，由于武汉市数据集的数据量较小，作业耗时较短、随机性较大，故本节选取数据量更大的纽约市2015年1月黄色出租车运单数据作为实验数据。该数据预加载至Kafka后， Flink实时计算任务将以最大的速度消费该数据流，反映算法的极限性能。实验数据经随机采样后的空间分布如图13所示，可见纽约市绝大部分上下客点集中于曼哈顿约 10 k m × 10 k m的网格区域内。除特殊说明外，本节使用的算法参数默认如下：时间窗口的时长为10 min、滑动步长为1 min、 s = 100 m、 p S i z e = 1 k m、并行度为8。使用纽约市数据集模拟数据流时，平均每10 min约有5 700个上下客事件，上下客数量同样较多，故时间窗口选用10 min。纽约市数据集的上下客频数分布图见图7（d），与武汉市数据集的频数分布图类似，故使用了与之相同的阈值选取方法，得 v = 7。
图13 纽约市2015年1月黄色出租车运单数据采样分布

Fig. 13 Sampling of New York City yellow taxi pick up and drop off in January 2015

以简单的分布式网格聚类算法（见2.1节）为基线，图14展示了不同并行度下基线方法与本文方法的吞吐量差异。在并行度为1时，基线方法与本文方法的吞吐量相近，此时二者的所有计算负载均由单节点承担，随着并行度增大，基线方法的吞吐量提升逐渐变少，其单节点的区域合并算子成为了性能提升瓶颈，而本文方法得益于多阶段、分布式的区域合并，随并行度加大，吞吐量提升更明显，说明本文算法具有良好的可扩展性。
图14 不同并行度的算法吞吐量

Fig. 14 Throughput with varying parallelism

p S i z e需结合研究区的数据在研究范围内的空间分布而定。图15展示了不同分区网格大小对吞吐量的影响。在 p S i z e = 1 k m时，算法吞吐量达到最高，此时曼哈顿的上下客密集区域可被切分为约100个分区网格，并被分发至8个计算节点上，充分利用了计算资源。当 p S i z e过大（ 0.5 k m）时，大量数据落于少数几个分区网格中，造成数据倾斜，部分节点成为集群瓶颈。而当 p S i z e过小（ 0.5 k m）时，大量热点区域被分区网格分割，导致需合并的区域增多，算法性能恶化。综合以上分析， p S i z e的选取应结合上下客点的空间分布，保证上下客数据能被切分至适当数量（如并行度的10倍）的多个分区网格中。
图15 不同分区网格大小下的算法吞吐量

Fig. 15 Throughput with varying partition grid size

除并行度、 p S i z e之外，本算法中时间窗口模型、 s、 v等其他参数的变化也会造成计算过程中监控单元、热点单元、热点区域的数量变化，从而对性能带来一些影响，但是其主要作用为表达具体的热点区域识别规则，调整空间较小，故本节不讨论这些参数带来的性能差异。

4 结论与讨论

城市热点区域实时探测在交通管理、城市治理等领域扮演着重要作用。出租车具有全城区覆盖、全天候运营等特点，其上下客事件反映居民出行活动，蕴含城市空间的人群出行规律。现有利用出租车的上下客数据提取城市热点区域研究均不支持在实时环境中流式处理上下客数据，难以实现城市热点区域实时探测以挖掘其时效价值。本文即以出租车上下客数据流为研究对象，提出了适用于城市热点区域实时探测的分布式算法，其核心思想有以下几点：
（1）以分布式流计算技术为基础，将连续上下客数据流按滑动时间窗口模型切片，将流计算问题转换为批处理问题；
（2）统计各网格状监控单元在当前时间片内的上下客数量，从中提取热点单元，最终聚合为热点区域；
（3）针对热点单元聚合过程中易出现的单节点I/O与计算瓶颈问题，设计了基于冗余分区、链接识别、修正规则构建、区域ID修正、区域生成等步骤的多阶段、分布式区域合并方法。
最后基于分布式流计算框架Flink实现了上述算法，并使用武汉市、纽约市出租车数据模拟数据流，对方法的效果与性能进行验证。首先以武汉市为研究区域，讨论了不同参数对结果的影响，并重点分析了3个时间片的热点区域结果，准确的识别出了医院、商圈、交通枢纽、居民区、文旅景点等POI周边在不同时刻下的热点区域变化情况，表明方法的有效性。之后，使用纽约市出租车数据集测试算法性能，结果表明在相关参数下，本文算法吞吐量可达数万条/秒，且相比基线方法具有更好的可扩展性。总体而言，本文方法基于出租车上下客数据流，实现了高效、准确的城市热点区域实时探测。
需要注意的是，本文方法在应用中存在一定的不确定性：
（1）出租车上下客事件有随机性，在使用不同出租车运营商提供的数据源时，即使对相同时间、地点作热点区域识别，结果仍可能存在差异。另外，小城市内出租车需求与运营数量显著少于大型城市，大多数居民选择步行、公交等交通方式出行，使得时间窗口内累积的出租车上下客事件较少，将导致热点区域的识别结果不准；
（2）在设置 s、 v、滑动时间窗口时长与步长等参数时，需要综合考虑数据流特征、应用时效性要求等诸多因素，不同参数组合也会造成结果的差异。
本文方法在数据代表性方面尚有不足：出租车活动受限于路网，其上下客数据仅能够反映沿道路分布的热点区域，难以揭示不可达场所（如步行街）的热点情况，此外，出租车只是城市交通的一种方式，仅使用出租车数据降低了人群的代表性。在进一步的研究中，有必要将本文方法与手机信令、社交媒体签到等不受路网限制、人群覆盖面更广的多源数据融合，弥补出租车上下客数据的空间分布受限性，提升热点区域识别结果的全面性与准确性。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Zhao P X, Qin K, Ye X Y, et al. A trajectory clustering approach based on decision graph and data field for detecting hotspots[J]. International Journal of Geographical Information Science, 2017, 31(6):1101-1127. DOI:10.1080/13658816.2016.1213845

DOI

[2]
Xia Z L, Li H, Chen Y H, et al. Identify and delimitate urban hotspot areas using a network-based spatiotemporal field clustering method[J]. ISPRS International Journal of Geo-Information, 2019, 8(8):344. DOI:10.3390/ijgi8080344

DOI

[3]
Chen X J, Wang Y, Xie J Y, et al. Urban hotspots detection of taxi stops with local maximum density[J]. Computers, Environment and Urban Systems, 2021, 89:101661. DOI:10.1016/j.compenvurbsys.2021.101661

DOI

[4]
吴华意, 黄蕊, 游兰, 等. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11):1341-1356.

DOI

[Wu H Y, Huang R, You L, et al. Recent progress in taxi trajectory data mining[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11):1341-1356.] DOI:10.11947/j.AGCS.2019.20190210

DOI

[5]
唐炉亮, 郑文斌, 王志强, 等. 城市出租车上下客的GPS轨迹时空分布探测方法[J]. 地球信息科学学报, 2015, 17(10):1179-1186.

DOI

[Tang L L, Zheng W B, Wang Z Q, et al. Space time analysis on the pick-up and drop-off of taxi passengers based on GPS big data[J]. Journal of Geo-Information Science, 2015, 17(10):1179-1186.] DOI:10.3724/SP.J.1047.2015.01179

DOI

[6]
唐炉亮, 阚子涵, 刘汇慧, 等. 网络空间中线要素的核密度估计方法[J]. 测绘学报, 2017, 46(1):107-113.

DOI

[Tang L L, Kan Z H, Liu H H, et al. A kernel density estimation method for linear features in network space[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(1):107-113.] DOI:10.11947/j.AGCS.2017.20150158

DOI

[7]
羊琰琰. 基于出租车GPS数据的热点区域识别及寻客推荐模型研究[D]. 北京交通大学, 2020.

[Yang Y Y. Research on hotspot recognition and seeking recommendation model based on taxi GPS data[D]. Beijing: Beijing Jiaotong University, 2020.] DOI:10.26944/d.cnki.gbfju.2020.001429

DOI

[8]
谷岩岩, 焦利民, 董婷, 等. 基于多源数据的城市功能区识别及相互作用分析[J]. 武汉大学学报·信息科学版, 2018, 43(7):1113-1121.

[Gu Y Y, Jiao L M, Dong T, et al. Spatial distribution and interaction analysis of urban functional areas based on multi-source data[J]. Geomatics and Information Science of Wuhan University, 2018, 43(7):1113-1121.] DOI:10.13203/j.whugis20160192

DOI

[9]
Hu Y J, Miller H J, Li X. Detecting and analyzing mobility hotspots using surface networks[J]. Transactions in GIS, 2014, 18(6):911-935. DOI:10.1111/tgis.12076

DOI

[10]
王宇环, 靳诚, 杜家禛. 基于多源数据的成都市居民出行热点时空特征分析[J]. 南京师范大学学报(工程技术版), 2020, 20(2):80-87.

[Wang Y H, Jin C, Du J Z. Temporal and spatial characteristics of traveling hotspots of Chengdu residents based on multi-source data[J]. Journal of Nanjing Normal University (Engineering and Technology Edition), 2020, 20(2):80-87.] DOI:10.3969/j.issn.1672-1292.2020.02.012

DOI

[11]
Shen Y, Zhao L G, Fan J. Analysis and visualization for hot spot based route recommendation using short-dated taxi GPS traces[J]. Information, 2015, 6(2):134-151. DOI:10.3390/info6020134

DOI

[12]
周勍, 秦昆, 陈一祥, 等. 基于数据场的出租车轨迹热点区域探测方法[J]. 地理与地理信息科学, 2016, 32(6):51-56,127.

[Zhou Q, Qin K, Chen Y X, et al. Hotspots detection from taxi trajectory data based on data field clustering[J]. Geography and Geo-Information Science, 2016, 32(6):51-56,127.] DOI:10.3969/j.issn.1672-0504.2016.06.009

DOI

[13]
Silva J A, Faria E R, Barros R C, et al. Data stream clustering: A survey[J]. ACM Computing Surveys, 2013, 46(1):1-31. DOI:10.1145/2522968.2522981

DOI

[14]
Zubaroğlu A, Atalay V. Data stream clustering: A review[J]. Artificial Intelligence Review, 2021, 54(2):1201-1236. DOI:10.1007/s10462-020-09874-x

DOI

[15]
Aggarwal C C, Yu P S, Han J W, et al. A framework for clustering evolving data streams[M]// Proceedings 2003 VLDB Conference. Amsterdam: Elsevier, 2003:81-92. DOI:10.1016/b978-012722442-8/50016-1

DOI

[16]
Aggarwal C C, Han J W, Wang J Y, et al. A framework for projected clustering of high dimensional data streams[M]// Proceedings 2004 VLDB Conference. Amsterdam: Elsevier, 2004:852-863. DOI:10.1016/b978-012088469-8.50075-9

DOI

[17]
Chen Y X, Tu L. Density-based clustering for real-time stream data[C]// KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 2007:133-142. DOI:10.1145/12811 92.1281210

DOI

[18]
Cao F, Estert M, Qian W N, et al. Density-based clustering over an evolving data stream with noise[C]// Proceedings of the 2006 SIAM International Conference on Data Mining. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2006. DOI:10.1137/1.9781611972764.29

DOI

[19]
Isah H, Abughofa T, Mahfuz S, et al. A survey of distributed data stream processing frameworks[J]. IEEE Access, 7:154300-154316. DOI:10.1109/ACCESS.2019.2946884

DOI

[20]
Karunaratne P, Karunasekera S, Harwood A. Distributed stream clustering using micro-clusters on Apache Storm[J]. Journal of Parallel and Distributed Computing, 2017, 108:74-84. DOI:10.1016/j.jpdc.2016.06.004

DOI

[21]
He Y, Tan H, Luo W, et al. MR-DBSCAN: An Efficient Parallel Density-Based Clustering Algorithm Using MapReduce[C] //2011 IEEE 17th International Conference on Parallel and Distributed Systems. Tainan, Taiwan, China: IEEE, 2011:473-480. DOI:10.1109/ICPADS.2011.83

DOI

[22]
Song H, Lee J G. RP-DBSCAN: A superfast parallel DBSCAN algorithm based on random partitioning[C]// SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data. 2018:1173-1187. DOI:10.1145/3183713.3196887

DOI

[23]
Gouineau F, Landry T, Triplet T. PatchWork, a scalable density-grid clustering algorithm[C]// SAC '16: Proceedings of the 31st Annual ACM Symposium on Applied Computing. 2016:824-831. DOI:10.1145/2851613.2851643

DOI

[24]
Rosin P L. Unimodal thresholding[J]. Pattern Recognition, 2001, 34(11):2083-2096. DOI:10.1016/S0031-3203(00)00136-9

DOI

Options
文章导航

/

〈 〉