精选|Juliana Freire：普及城市数据分析
“二十一世纪的计算”学术研讨会是微软亚洲研究院自成立之初便开始举办的年度学术盛会。作为中国及亚太地区规模最大、最具影响力的计算机科学教育与研究盛会之一，迄今为止该大会已在中国、日本、韩国、新加坡等多个国家和地区成功举办了17届，参会人数累计超过40,000人。
11月3日，以“Human and Machine Working as a Team”（人机协作）为主题的第18届“二十一世纪的计算”学术研讨会于韩国首尔举行，包括2002年图灵奖获得者Adi Shamir、微软全球资深副总裁Peter Lee、微软全球资深副总裁，微软亚太研发集团主席兼微软亚洲研究院院长洪小文博士在内的众多计算机领域顶级大师，分享了他们各自独特且深远的见解。
以下是纽约大学Juliana Freire教授的演讲精选，由微软亚洲研究院首席研究员刘铁岩博士担任现场点评。其他演讲亦将陆续发布，敬请期待。
演讲者简介
Juliana Freire是纽约大学计算机科学与数据科学系教授。她最近的研究集中在大数据分析及数据可视化、大规模信息集成、数据起源管理和计算重现性。Freire教授是活跃在数据库和互联网研究领域的研究者，拥有超过150篇技术论文，开发了数个开源系统并拥有11个美国专利。她是美国计算机协会院士、美国国家科学基金会CAREER奖的获得者。她的研究资助来自美国国家科学基金会、DARPA、能源部、国家卫生研究院、斯隆基金会、戈登和贝蒂摩尔基金会、WM Keck基金会、谷歌、亚马逊、犹他州立大学、纽约大学、微软研究院、雅虎和IBM。
点评人简介
刘铁岩博士，微软亚洲研究院首席研究员，美国卡内基梅隆大学（CMU）客座教授、英国诺丁汉大学荣誉教授、中国科技大学、中山大学、南开大学博士生导师。刘博士的研究兴趣包括：人工智能、机器学习、信息检索、数据挖掘等。他的先锋性工作促进了机器学习与信息检索之间的融合，被国际学术界公认为“排序学习”领域的代表人物，他在该领域的学术论文已被引用万余次，并受Springer出版社之邀撰写了该领域的首部学术专著（并成为Springer计算机领域华人作者的十大畅销书之一）。
近年来，刘博士在博弈机器学习、深度学习、分布式机器学习等方面也颇有建树，他的研究工作多次获得最佳论文奖、最高引用论文奖、研究突破奖，被广泛应用在微软的产品和在线服务中，并通过DMTK、Graph Engine等项目开源。他曾受邀担任了包括SIGIR、WWW、NIPS、KDD、AAAI、WINE等在内的十余个顶级国际会议的组委会主席、程序委员会主席或领域主席；以及若干顶级国际期刊的副主编。他是美国计算机学会（ACM）杰出科学家、国际电子电气工程师学会（IEEE）和中国计算机学会（CCF）的高级会员，中国计算机学会的杰出演讲者和学术工委。
微软亚洲研究院：今天，全球有一半人口居住在城市，到2050年，这一比例将增长到70％。城市是经济活动的基地，是21世纪各种挑战的创新解决方案之源。同时，城市也是交通、资源消耗、住房负担能力以及基础设施不足或老化等可持续性问题的根源。大量的城市数据，加上大大提高的计算能力，打开了更好地了解城市的新机会。对城市数据进行有效与成功的分析，就能达至更好的城市管理、更加符合大众知情需求的城市规划、进一步优化的政策以及更好的居民生活质量。然而，从识别相关数据集、清理和整合这些数据集，再到对复杂的时空数据进行探索性的分析……说到分析城市数据，总是意味着大量的工作。
从长期来看，若能确保相关领域的专家可以通过广泛探索城市产生的大量数据，将有助于破解城市管理的秘密。以下演讲主要介绍了Juliana和她的研究团队对数据管理，数据分析和可视化技术进行的卓有成效的研究及其面临的挑战，包括他们开发的系统及研究方法。这些研究成果对城市数据展开具有互动性、可扩展性和可用性的时空分析起到了极为重要的作用。
刘铁岩：今天Freire教授的报告将针对城市大数据分析展开。
微软亚洲研究院： 补充一下，这一项目部分得到国家科学基金会、谷歌研究奖、纽约大学的摩尔斯隆数据科学环境研究中心、IBM研究奖、纽约大学Tandon工程学院以及城市科学和进步中心的支持。
刘铁岩：城市大数据对于城市规划、管理以及科学研究都非常有价值。但城市大数据的大体量、动态变化、时空高维等属性，决定了对城市大数据进行分析不是一件简单的事情。
Juliana Freire教授
刘铁岩：城市数据科学/城市计算是近今年的一个研究热点，例如从2012年开始，每年的KDD（ACMSIGKDD数据挖掘与知识发现大会）都有专门针对这个话题的研讨会。我们研究院的郑宇博士在这个领域做了很多前沿的研究工作。
Freire教授所在的纽约市，是全美乃至全球在城市计算实践方面的先行者。她刚刚介绍的OneBusAway系统是一个集成了城市公共交通数据的开源平台，以此为基础，人们构建了跟多应用，如交通实时查询、规划、推荐等等。对比研究表明，使用这些基于城市大数据的应用，人们的等待时间缩小、满意度明显增加。
刘铁岩：她刚刚讲到另外一个例子：如何治理城市中的私搭乱建。因为投诉量很大，政府受人手所限很难及时执法。有了城市大数据分析作为支撑，虽然人手没有增加，但处理率马上从13%上升到70%。其关键是一个数据驱动的预测系统，用以找到最该优先处理的案例。
微软亚洲研究院： 我们推出的“小鱼天气”也是成果之一，请戳：立志做最专业最贴心的天气顾问。
同时参见郑宇博士介绍：
郑宇：城市计算如何解决城市规划问题（3个规划案例+4大经典选址案例）：https://mp.weixin.qq.com/s?__biz=MzA3OTU3ODgxNA==&mid=2650576546&idx=1&sn=53d09d5a94f5a9daf93e62ab1424c112&chksm=87b96573b0ceec65b3be1afca60f4651e044800fad832ba8be82bc7d8e2f709a631266e9c6bc&mpshare=1&scene=1&srcid=1027C5CW9XS0a3GiMCRlLEia&pass_ticket=EuA%2BOjF3u4XIwi%2Bv5hTOf%2FeZHYC2WqWo2IXbUXMl%2F70%3D#rd
郑宇：城市计算大有可为（http://msra.cn/zh-cn/news/headlines/20141021.aspx）
微软郑宇：大数据解决城市大问题（http://news.xinhuanet.com/tech/2015-01/13/c_127383443.htm）
刘铁岩：虽然城市大数据分析有了很多成功的例子，但其实它存在着很大的技术难度。我们知道，城市是人类社会的产物和人类文明发展的重要载体，因此它的数据非常依赖于人类的活动，从而必然带有很高的复杂性、多样性以及时空动态性。
例如，近年来随着分布式系统、并行数据库、云计算的迅猛发展，我们已经有能力处理海量数据，可是我们还没有非常成熟的办法来处理以及管理海量的人类行为。
刘铁岩：传统上，处理城市大数据通常采用如下的方法：由领域专家提出假设，数据科学家搜集数据来做建设检验。然而这种做法存在很多挑战，比如数据科学家在搜集数据、过滤相关数据、分析多率时空数据等方面都可能遇到困难。城市数据科学作为一门新学科，希望能够系统地解决这些挑战。
刘铁岩：在今天的报告中，Freire教授会介绍她的研究组从事的两项研究工作：第一项是如何交互式地在时空数据上进行查询；第二项是如何知道用户探索和发现城市数据里的事件和潜在联系。
在开始具体的介绍之前，Freire教授先对她最熟悉的城市大数据——纽约出租车数据进行了介绍。出租车数据其实非常丰富，描述了典型人群在城市中的各种活动。
纽约市为了支持城市数据科学的研究，开放了体量非常大的出租车数据，每天有50万次乘车记录，5年下来积累了8亿多次的乘车记录。这些数据不仅体量大，而且包含丰富的信息，比如上车下车的时间与地点，费用，消费，乘车距离等等。想要方便地去查询这样一些数据却并不容易做到，需要设计一个有效的用户界面，支持交互式、探索式的查询。
微软亚洲研究院：铁岩老师在这篇介绍博弈机器学习的文章中提到了博弈机器学习对解决城市交通问题的应用方向，大家可以研读一下：刘铁岩：博弈机器学习是什么？
刘铁岩：其实除了出租车数据，网约车的数据也非常有价值。
刘铁岩：顺便做个广告：我们组的几个实习生，使用我们组开发的LightGBM技术，对网约车大数据进行预测，获得了今年滴滴出行算法竞赛（Di-Tech）的冠军。
针对出租车数据的一种常用的查询时空数据的方式，是指定时间段、起点、终点，然后返回符合条件的所有出租车轨迹数据。
但即使是这样一种简单的查询，如果用传统数据库技术来做的话，相应速度是非常慢的，会耗时几十秒到上百秒。这样会大大降低用户观察、更新查询、生成假设的效率。
微软亚洲研究院：关于LightGBM等，我们在我们的微信平台上会做后续的报道，大家可以期待一下哦。
刘铁岩：那么怎样才能提高查询这种时空数据的效率呢？Freire教授的研究组提出的方法，是利用基于外存的KD-Tree来建时空索引，并且利用GPU进行加速。KD-tree是对高维数据建索引的常用方法，它的构建复杂度不算高，只有log^2(n)，但查询的复杂度还是比较高的。因此，他们利用了GPU的并行处理能力，对搜索的步骤进行加速。
上面提到的查询算法在GitHub上开源了。开源项目叫MongoDB，在出租车数据上进行了测试，与传统数据库相比有非常明显的加速，加速比达到几百，甚至几千倍。
链接：https://github.com/mongodb/mongo
Freire教授把他们的系统演示给纽约交通部门，大获好评。这从另一个侧面也可以看出，传统行业的技术含量还是比较低的，一个KD-Tree分分钟就可能秒杀了他们用了多少年的系统。
这个demo也开源了，叫TaxiVis，比单纯的算法的那个开源包关注度要稍高一点，两位数的star。同样，有兴趣的去关注一下吧！
链接：https://github.com/ViDA-NYU/TaxiVis
如果从另一个角度看出租车数据，就会发现，数据太零散、数目太多，需要进行某种方式的聚合才能发现一些有规律的信息。当然，按照时间或者空间做平均是一种最最简单的聚合方式。但这种做法存在当时的力度太粗而又整齐划一的特点，很可能丢掉了有趣的时空片段。
为了解决这个问题，Freire教授使用基于拓扑结构的技术来做事件检测，并且提供了简单的界面来对这些事件进行检索。具体而言，她把数据建模成定义在图上的随着时间变化的标量函数。对于出租车数据，图就是路网，函数就是出租车的密度；对于地铁数据，图就是铁道线路，函数就是列车的晚点情况。
然后，在如上定义于图上的函数曲面上进行事件检测。这想法其实也很直观：如果某些点上的属性和它的邻居的属性存在显著不同，那么这个区域应该发生了某些事件。
刘铁岩：以出租车数据为例，这个图上的极小值通常对应了出租车稀缺，那么可能说明有道路拥塞。而函数曲面上的极大值有可能就对应着出租车站，旅游景点或者交通枢纽。
因为城市数据本身很复杂，如上定义的事件的数量会非常多。所以，在现实中需要通过拓扑结构的相似性对事件做聚类。Freire教授展示了，通过这样的操作得到很多的类别，都能与现实世界中发生的事件相互对应。
这些事件挖掘的结果有时候分析起来会很有意思。比如，Freire教授把连续两年的事件放在一起比较的时候，会发现它们的模式大体相同，但会有若干个outlier。
刘铁岩：有趣的是，通过分析发现，这些outlier和天气数据有很强的相关性：比如，当飓风来临的时候，出租车密度就会减小（这可能是因为出车少，或者行人出行减少，或者出租车行驶缓慢吧）。
想要发掘出这种潜在的关系，并不容易。首先是数据集实在太多了，而且异构性很强。为了解决这个问题，Freire教授提出了一个数据匹配的框架，用于发掘不同数据集之间存在的内在联系，从而反映出城市的各个组成部分之间是如何交互的，同时支持用户的关系查询。这个系统不同于传统计算相关性的方法（如pearson相关性，互信息，dynamic time wrapping）等，因此可以避免这些方法的计算瓶颈，可以提供更好的分析分辨率。
刘铁岩：具体而言，Freire教授的团队再次利用定义在图上的时变标量函数。在这个函数的曲面上抽取出一些不同分辨率的特征点。特征点的选择可以利用多种规则，比如极大值点、极小值点以及由特定阈值界定的关键点邻域等等（阈值可以通过数据驱动的方式自动计算）。抽取这些特征点之后，就可以在其基础上定义不同数据集之间的关系了。
刘铁岩：
Freire教授的团队把上述方法用MapReduce的框架进行了实现，用它处理了来自纽约市的上百个时空数据集，结果表明这个方法效率很高，200分钟内就完成了标量函数曲面的计算，而且用分布式实现可以取得线性的加速比。
这个项目叫data-polygamy，也在Github上开源了。
除了定量的评估结果，Freire教授举了几个很有趣的具体的关系挖掘的例子。
比如：车速和交通事故的数量有正相关的关系；雨量和出租车费有正相关的关系；等等。
个人感觉，这些数据挖掘的结果，虽然直观，但并没有太多出人意料的地方。另外，这种方法计算的是相关性，而不是因果性；如果可以做一些因果分析，可能对于真正城市管理的价值更大。
总的说来，Freire教授的报告具有很浓厚的数据挖掘的味道，城市大数据很重要，传统的方法对这种新型数据处理起来有一定的困难，如何才能改进算法、build系统、实现有效的数据分析和查询，都需要继续跟进。
总结一下，城市大数据分析领域方兴未艾，还有很多有待解决的问题。这让我想起了我们微软研究院的几个相关工作。
首先，郑宇博士的团队最近在用深度学习来解决时空数据分析方面有很好的进展，有望利用现在人工智能的一些最新研究成果解决城市计算的问题。
其次，我们组的邵斌博士前不久开源了一个微软图引擎，它在图的节点上可以支持用户定义的lambda表达式，对于像城市大数据这种复杂、时变的结构化数据应该有更好的支持。
第三，城市数据的另外一个特点在这个报告里没有特别显著地指出，就是这些数据是人的活动产生的。当我们从这些数据中挖掘出一些规律，并反过来依次制定一些政策法规的时候，人的策略性反应会改变原大数据的分布，从而影响这些政策法规的有效性，若要解决这个问题，就要把博弈论引进来。我们组前一段时间所从事的“博弈机器学习”，以及最近在研究的“增强学习”都为解决这个问题提供一些思路。
微软亚洲研究院：Juliana Freire教授的演讲结束了。关于城市计算的思考不能停，欢迎有兴趣的读者留言或通过文章结尾附带的电子邮件提出你们的看法。
你也许还想看：