摘 要

通过时空图（STG）可以对许多类型的人类流动性数据建模，例如出租车的流动，地铁的刷卡数据，自行车出行数据和呼叫详细记录。STG是一个有向图，其中顶点和边与时空属性相关联。本文能从STG中发现一种现象，称为黑洞和火山。具体来说，黑洞是（STG的）子图，其总流入量和总流出量的差大于一个阈值，而火山是也是一个子图，其总流出量和总流入量的差小于一个阈值。

根据设计后的STG索引，本文提出了通过两个步骤来检测黑洞的算法：第一步，先确定一组候选的单元格；第二步，将候选单元格中的初始边扩展到黑洞，并在检测到黑洞后修剪其他候选单元格。然后，本文将这样的检测算法改为连续的黑洞检测方案。为了发现城市异常情况和人类出行方式，本文使用美国纽约的自行车移动数据来评估本文的方法。

关键词：城市计算；时空图；黑洞检测

Abstract

STG can be used to model many types of human mobility data, such as taxi flow, subway swipe card data, bicycle travel data and call detailed record. STG is a directed graph in which vertices and edges are associated with spatiotemporal attributes. We can find a phenomenon in STG called black hole and volcano. Specifically, a black hole is a subgraph of (STG), the difference between its total inflow and total outflow is greater than a threshold, while a volcano is also a subgraph, the difference between its total outflow and total inflow is less than a threshold.

According to the designed STG index, we propose an algorithm to detect black holes through two steps: the first step is to determine a group of candidate grid cells; the second step is to extend the initial edge of candidate cells to black holes, and trim other candidate cells after detecting black holes. Then, we change this detection algorithm to a continuous black hole detection scheme. In order to detect urban anomalies and human travel patterns, we use bicycle mobility data from New York, USA, to assess our approach

Key Words：Urban computing; STG; black hole detection

目 录

第1章 绪论 1

1.1 课题研究背景、目的及意义 1

1.2 国内外研究现状及课题研究内容 1

第二章 概念及架构介绍 3

2.1 定义及定理 3

2.1.1 定义 3

2.1.2 定理 4

2.2 架构 5

第三章 黑洞/火山的检测 6

3.1 STG索引 6

3.2 候选单元格选择 7

3.3 空间扩展 8

3.4 流上限更新 11

3.5 连续检测 11

第四章 实验评估 14

4.1 数据说明 14

4.2 实验结果分析 14

4.2.1 代表异常的黑洞/火山 15

4.2.2 黑洞和火山模式 15

4.2.3 黑洞和火山之间的关系 16

4.2.4 两种空间扩展算法的比较 16

第五章 结论 18

参考文献 19

附录A 21

致 谢 27

第1章 绪论

1.1 课题研究背景、目的及意义

城市的迅猛发展给我们带来便捷生活方式的同时，也带来了交通拥堵、能源消耗、环境污染等问题。如何利用科学的方法解决城市化所导致的诸多问题一直人们所关注的问题。城市交通状况的好坏对人们的出行、学习、工作有着至关重要的影响。实时了解城市的交通状况有助于人们进行出行规划，避开交通拥堵；同时也对管理人员调控城市交通有很大的帮助^[12]。然而，造成交通拥堵的影响要素众多，包括上下班高峰对学校、公司、办公场所等地方的影响、节假日对旅游景点的影响，天气状况、突发事故对道路情况的影响等。因此想要充分了解并分析城市交通状况并不容易^[1]。

通过对人类出行数据的分析，去在线检测黑洞或火山，能够及时反映异常事件的产生，例如车祸、上下班高峰、突发应急事件等。因此有助于维护公共安全。黑洞/火山的模式及其之间的关系揭示了城市中的人类活动模式，从而有助于制定更好的城市规划或者是提高系统的运行效率。

1.2 国内外研究现状及课题研究内容

近年来，关于城市数据的研究有很多，主要使用在智能交通、资源与环境保护、城市规划等方面。城市轨迹数据主要有人类活动出行数据、交通出行数据等^[3，13]。人类活动出行数据，包括APP签到数据、手机定位数据等，依照时间顺序跟踪这些位置记录就形成人们在一段时间内的位置信息。然而这类轨迹数据精度不高，有时无法持续进行跟踪，而且大多涉及到个人隐私，无法被轻易获取，所以得不到广泛的应用；交通出行数据包括两种：一种是通过固定地点设施所采集得到的数据，如视频监控数据、地铁扫码的数据等；另一种是通过车载定位设备采样得到的交通工具移动轨迹，如公交车轨迹数据、出租车轨迹数据、共享单车轨迹数据等。在这两类交通出行数据中，固定地点设备数据只能粗粒度地描绘人群或车辆在不同固定地点之间的移动；公交车轨迹数据也只能记录运营时间内公交车的固定路线轨迹^{[4，10，6，11]}。但是出租车和自行车不受线路和时间的约束，是最灵活、覆盖范围最广的轨迹数据，且精度较高、较少涉及隐私问题，常被作为轨迹数据研究和应用的主要数据集^[15]。

在一份国内的研究中，使用时空图完成了对于城市黑洞和火山的检测。但其中对于空间扩展算法存在了一定漏洞^[5]。本课题通过查找和阅读相关文献，了解出行数据挖掘的相关知识，然后通过对城市火山和黑洞的研究，发现了原论文中的算法漏洞，结合文献中的相关资料进行重新实现，设计和改进城市火山和黑洞挖掘的算法。再根据实现的算法和实际的自行车出行的数据进行实验评估。分析实验过程和实验结果，完成毕业设计的论文。

第二章 概念及架构介绍

2.1 定义及定理

2.1.1 定义

定义1.（STG）时空图（STG）是有向图，其中V和E分别表示G中的顶点和边的完整集合（）。每个顶点具有地理空间位置，每个边具有空间长度。每个顶点/边与随时间变化的属性相关联，例如流入和流出。