交通相关的可视化案例综述02：事件为引导的城市数据探索

Using Topological Analysis to Support Event-Guided Exploration in Urban Data

[1] Harish Doraiswamy, Nivan Ferreira, Theodoros Damoulas, Juliana Freire, and Cl´audio T. Silva. Using Topological Analysis to Support Event-Guided Exploration in Urban Data. IEEE Transactions on Visualization and Computer Graphics, 2014 

[2]http://vis.pku.edu.cn/blog/%E4%BD%BF%E7%94%A8%E6%8B%93%E6%89%91%E5%88%86%E6%9E%90%E6%9D%A5%E6%94%AF%E6%8C%81%E4%BB%A5%E4%BA%8B%E4%BB%B6%E4%B8%BA%E5%BC%95%E5%AF%BC%E7%9A%84%E5%9F%8E%E5%B8%82%E6%95%B0%E6%8D%AE%E6%8E%A2%E7%B4%A2/

数据分析领域的具体问题最终都可以归纳为模式识别问题。考虑一个实际场景：一个安防公司在城市里每个ATM机周围部署了很多摄像头和报警点，但是每天都有很多错误报警，如何将误报消除，但又绝不能漏过一个真实报警？可行之路就是要从已有数据中推断出误报的行为模式，然后将之应用到更大的数据集中不断测试，从而完善特征集。最终实现误报的自动过滤。整个过程并不是写个程序算个结果那么简单，而是一条不断开动的根据产品品质不断纠错的生产线。模式识别作为大数据分析的关键性技术，一直是计算机科学研究的重点。数据挖掘方面相关的例子很多，而近年来逐渐火热的可视分析领域中，这方面还在逐渐发展中。来自纽约大学的这一篇论文或许能给我们这方面的启发。（下文中用笔者作为我个人的代称，论文作者则直接称为论文作者）

发现问题

近年来技术的不断革新使得大量城市数据的收集变得越来越方便，这些收集到的数据还可以用来分析城市，如果这些数据得到了适当的分析利用，可以用来帮助我们解决现有问题并有利于政策制定。然而，对于城市数据的有效分析，还有着许多挑战，无论是从数据量，还是从一个城市固有的时空复杂性。通常分析这种数据的方式是使用不同的聚类并且产生视觉总结，但是这些会产生许多矛盾，如使用粗糙聚类可以减少数据片的量，但是可能引起信息丢失。所以问题的症结在于，如何找出一种更加有效的、自动化的模式识别手段。

处理流程

这篇文章提出了一种有效并且可扩展的可视分析技术，这种技术可以自动发现事件并且引导用户到很可能感兴趣的时间片。

上图所示是这篇文章提出的技术的流程图，第一步，输入数据被转化成随时间变化的标量函数，第二步，从标量函数中计算得到拓扑特征来识别事件集，第三步，从识别到的事件中创建一个事件集指数来支持对大量事件的查询，第四步，一个可视界面可以引导用户到感兴趣的事件，第五步，在数据中，允许用户选择一个事件，第六步，交互搜索相似事件。

关键技术

可以看到整个技术的关键在于事件检测方法，即标量函数的定义。直观来说，最小值（最大值）捕捉到了对应于数据的低谷（高峰）的特征，拓扑的使用也使得事件可以有任意的空间结构。为了支持可能存在的大量事件，他们还设计了事件组，通过将时间分片来把跨越多个时间片的相似模式组合到一起。从而不仅能够支持识别周期时间，还可以识别有不同频率的事件。

（注：遗憾的是笔者缺乏拓扑学数学基础，对其中拓扑的理解不深，所以上面只能泛泛而谈，下文中对拓扑的描述也可能有误）

有了标量函数就可以识别事件集。识别了事件集就要进行相似事件的查询，为此需要有一个标准来衡量事件的相似度。为了计算事件的相似度， 每个事件E被表示成一个键值对（R，τ），其中R是事件E的空间面积，表示E的几何相似性；τ是一个实数，表示E的拓扑重要性。论文作者使用如下公式表示R1与R2之间的几何相似度，几何相似性度量的是两个区域之间的重叠量，确保类似的区域有一个明显的重叠：

而拓扑相似度直接取τ1与τ2的绝对值，确保两事件在拓扑重要性上是拓扑接近的：

事件相似度有了衡量的标准，但并不意味着事件组就能依此解决。因为事件组包含一组在给定时间间隔中发生的相似事件，使用蛮力法计算两个事件组的相似性，要对其中所有的事件进行两两比较，当事件组规模变得很大就会发生组合爆炸的问题。为了避免这种问题，论文作者提出了群体事件的固定时间间隔——一个月：这个时间间隔下，一方面有足够数量的事件以便不错过周期性事件，但同时事件的数量也不至于造成计算瓶颈。给定一个事件组Σ= { E1，E2，……，EK }，我们定义事件组的key为Σ  =（RΣ，τΣ），其中两个键值的定义如下：

定义事件组的key有助于对项目组之间的相似性使用一致的定义。如果事件组Σ 中的事件是相似的，那么我们可以得出结论：其中的事件有着相当大的重叠。同时事件组Σ 拓扑重要性也是所有内部事件的均值。

最后，论文作者提供了一个可视化的交互界面，引导用户探索相似事件，并支持多属性过滤器：事件组大小过滤器、事件大小过滤器、事件时间过滤器、空间区域过滤器。下图所示的是过滤后的某天的事件组分布视图，图中游行对应的事件在视图中非常突出，用户可以识别到这个模式。

案例分析

论文作者们以纽约市的出租车数据和地铁数据为例进行了案例开发。出租车数据集来自Taxi & Limousine Commission (TLC)收集的纽约市出租车运营的历史数据。地铁数据来自Metropolitan Transportation Authority提供的纽约地铁实时数据。（http://web.mta.info/developers/），没错这些数据集都是公开的。

对于出租车运营者来说，他们对所谓极小事件特别感兴趣。因为在这些极小事件发生的地方，通常会有高密度的出租车运行，这通常意味着交通阻塞。政策制定者对于识别这些交通阻塞有浓厚的兴趣。通过分析其空间位置和发生概率，他们可以落实政策来帮助他们处理类似问题。论文作者以下图为例，展示了纽约1区极小事件的发生情况。

fig.8 图a，在十月份内区域一的事件分布图中选择孤立的高密度事件组，从而标识出2011年万圣节游行的对应事件；图b，将时间单位改为每日，选择范围= 2，标识对应的西班牙国庆阅兵和哥伦布日游行连续几天所发生的事件的高密度事件组；图C，以八月每周为单位，选择范围=3，标识对应于纽约夏天街道连续三星期六所发生的事件的高密度事件组。

在fig.8的c小图中，已经选择了相当于三周结果的多个事件组。将这些事件组导入到时间线图中以便进一步观察是否有周期性规律，其中将不同事件用不同颜色标注，这有助于发现周期性事件。fig.9中的b小图显示了结果。图中黑色箭头指明的事件显然有某种周期性规律。

 

总结

此论文介绍了一种基于拓扑的事件引导城市数据探测技术，其目的是通过引导用户对感兴趣的数据部分延伸当前可视化分析系统的能力。论文作者提供技术采用高效的算法来捕捉时空数据的拓扑特性和使用分组索引事件灵活的探索。通过在大型数据集中的应用研究，表明其所提出的方法是有效的。事实上此方法也可以应用到其他大型数据集和事件类型上去，例如证卷交易，科学模拟，和实验研究。

笔者认为此论文提供的方法是一个典型的探索式可视分析案例。这种基于事件拟态从而引导用户发现模式的方法，无疑是切合可视分析学要害的探索分析方法。当然，其算法复杂度较高，而且使用者需要一定的数据分析素养才能使用。这也许就是数据分析专家和普通用户之间的区别吧。