微软亚洲研究院：铁岩老师在这篇介绍博弈机器学习的文章中提到了博弈机器学习对解决城市交通问题的应用方向，大家可以研读一下：

刘铁岩：其实除了出租车数据，网约车的数据也非常有价值。

刘铁岩：顺便做个广告：我们组的几个实习生，使用我们组开发的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。