标签:
it城市计算大数据微软研究院 |
分类: 技术 |
作者:微软亚洲研究院研究员 郑宇
城市计算的基本框架及核心问题
基本框架
城市计算的基本框架包括城市感知及数据捕获、数据管理、城市数据分析和服务提供(如图1)。与自然语言分析和图像处理等“单数据单任务”系统相比,城市计算是一个“多数据多任务”系统。城市计算中的任务包括改进城市规划、缓解交通拥堵、保护自然环境、减少能源消耗等。而一个任务又需要同时用到多种数据。例如,在城市规划的设计过程中,需要同时参考道路结构、兴趣点分布、交通流等多种数据源。
核心问题
城市计算是一门新兴的交叉领域,涵盖面较广。从计算机科学的角度来看,其核心的研究问题主要包括以下4 个方面:
城市感知 如何利用城市现有的资源(如手机、传感器、车辆和人等),在不干扰人们生活的前提下自动感知城市的韵律,是一个重要的研究课题。如何从大量的传感器和设备中高效而可靠地收集、传送数据将给现有的传感器网络技术带来挑战。此外,人作为传感器参与到城市感知过程是一个新概念。例如,当一场灾难发生后,有些用户会在社交网络上发布消息或上传照片。这些用户其实就是在感知发生在他们身边的事情。用户在出入地铁站时的刷卡行为也间接帮助我们感知了地铁系统的拥挤和人们的出行。人赋予了传统传感器强大的感知能力和前所未有的灵活性,但产生的数据更加随机、无序(如微博上的文字),数据的产生时间也变得难以预测、不可控,这给数据的收集和解析带来了挑战。
海量异构数据的管理 城市产生的数据五花八门,属性差别很大。例如:气象是时序数据,兴趣点是空间点数据,道路是空间图数据,人的移动是轨迹数据(时间+ 空间),交通流量是流数据,社交网上用户发布的信息是文本或图像数据。如何管理和整合大规模的异构数据是一个新的挑战。尤其是在一个应用中使用多种数据时,只有提前建立起不同数据之间的关联,才能使后面的分析和挖掘过程变得高效、可行。
异构数据的协同计算 这部分包括三个方面:(1) 如何从不同的数据源中获取相互增强的知识是一个新的课题。传统的机器学习往往基于单一数据,如自然语言处理主要分析文本数据,图像视觉主要基于图像数据。在城市计算的很多应用中,对不同性质的数据一视同仁,其效果并不理想。(2) 在保证知识提取深度的同时,如何提高对大数据的分析效率,从而满足城市计算中众多实时性要求较高的应用(如空气质量预测、异常事件监测等),也是一个难题。(3) 数据维度的增加也容易导致数据稀疏性问题。当数据规模达到一定程度,简单的矩阵分解算法都变得难以执行。
虚实结合的混合式系统 城市计算常常催生混合系统,如云加端模式,即信息产生在物理世界,通过终端设备被收集到云端(虚拟世界)分析和处理,最后云再将提取的知识作为服务提供给物理世界的终端用户。数据在物理和虚拟世界中来回穿行,从分散到集中,再到分散。这对系统的设计和搭建提出了更高的要求。基于浮动车数据的快速行车路线设计以及城市异常事件的监测都是典型的混合式系统。
城市计算的典型应用
城市规划
城市拥堵在一定程度上突显了现有道路网的设计已经不能满足不断发展的城市交通流的需求。如图2(a) 所示,利用高速和环路等主干道将城市分割成区域,然后分析大规模车流轨迹数据在不同区域之间行驶的一些特征,便可找到连通性较差的区域对,从而发掘现有城市道路网的不足之处。图2(b) 给出了基于北京市3 万多辆出租车3 个月轨迹数据的分析结果。这些结果可以作为制定下一版交通规划的参考。同时,通过对比连续两年的检测结果,可以验证一些已经实施的规划(如新建道路和地铁)是否合理。
城市的不断发展催生了不同的功能区域,如文教、商业和住宅区等。准确掌握这些区域的分布对制定合理的城市规划有着极其重要的意义。但是一个区域的功能并不是单一的,例如在科学文教区里仍然有饭店和商业设施的存在。因此,一个区域需要由一个功能的分布来表达(如70%的功能为商业,20% 的功能为住宅,剩余的为教育)。由于一个区域杂糅了很多不同类别的兴趣点,而且每个兴趣点的作用大小和被访问频度都很难预知,这给城市规划提出了很大的挑战。例如,同样都是餐馆,一个小区里的小店和全聚德之类的大店所反映的区域功能是完全不一样的。
结合兴趣点数据和人们的移动模式,Discovering regions of different functions in a city using human mobility and POIs分析了城市中不同的功能区域。如图3(a) 所示,相同颜色的区域具有相同的功能分布(如红色区域主要为科学文教区)。图中所采用的人的移动性数据是从出租车的轨迹数据中提取出来的,该轨迹数据包含乘客上车和下车地点的信息。人的移动性数据可以很好地区分相同类别的兴趣点的热度,也可以揭示一个区域的功能。例如有一个区域,大部分人都是上午8 点左右离开,晚上7 点返回,则这个区域很可能是住宅区。一个区域的主要功能是文教,但也不代表该区域的任何一个地点都服务于文教。因此,给定一种功能,我们希望知道它的核心区域所在。图3(b) 显示了成熟商业区的核心区域,颜色越深表示该区域是成熟商业区的概率越大。
智能交通
T-Drive 系统利用装有GPS 传感器的出租车来感知交通流量,并为普通用户设计出真正意义上的最快驾车线路。如图4 所示,T-Drive 提出了一个基于地标图的路由算法,其中一个红点表示出租车司机走过最频繁的路段之一(称为一个地标),红点之间的连线表示连接两个地标点的一条虚拟边,代表连续经过这两个地标点的出租车轨迹的聚合。根据出租车轨迹数据,可以学习出任何一条虚拟边的通行时间。T-Drive 的改进版进一步考虑了天气及个人驾车习惯、技能和道路熟悉程度等因素,提出了针对个人的个性化最快线路设计。这个系统不仅可以为每30 分钟的驾车路程节约5分钟时间,还可以通过让不同用户选择不同的道路来缓解可能出现的拥堵。
打车难是很多大城市面临的一个问题。通过分析出租车乘客的上下车记录,T-Finder提供了一个面向司机和乘客的双向推荐服务。一方面,这个系统向出租车司机建议一些“趴活”地点。只要向这些地点行驶,司机将在最短的时间内(在路上或者推荐地点)拉到乘客,并且使收入最大化。另一方面,如图5(a) 所示,该系统向乘客推荐一些周边的路段,在这些路段上寻找到空车的概率更高(不同颜色表示不同概率,蓝色最高,红色最低)。同时,T-Finder 还可以预测周边的一些出租车停靠站在未来半小时内将驶入的空车数目。T-Finder通过推荐能够缓解非高峰时段的打车难问题,但该系统并不能真正解决高峰时段的问题。T-Share则通过出租车实时动态拼车的方案来解决这一难题。在T-Share系统里,用户通过手机提交打车请求,表明上下车地点、乘客人数和期望到达目的地的时间。后台系统实时维护所有出租车的状态,在接收到一个用户请求后,搜索出满足新用户条件和车上已有乘客条件的最优的车。这里的最优是指出租车去接一个新的用户所增加的里程最小。如图5(b)所示,该出租车被规划为先后接 u1 和 u2,放下 u1 接 u3,再放 u2 ,然后放 u3(+ 表示上车,- 表示下车)。根据仿真结果显示,TShare系统一年可以为北京市节约8 亿升汽油(可供100 万辆车开10 个月,价值10 亿元人民币,并减排二氧化碳 16 亿千克),乘客能打到车的概率提高3 倍,但费用降低7%,出租车司机的收入增加10%。
还有一些研究工作,利用乘客在地铁系统中的刷卡数据来估计单个地铁站点内的拥挤程度和不同站点间的通行时间,从而优化人们的出行线路、时间和购票方式的选择。还有人通过分析出租车的轨迹数据来建议开通公交线路。如果有大量的人通过打出租车从一个地点到另一个地点,则说明这两个地点需要公交线路来连通。
环境
空气质量信息对控制污染和保护人们身体健康有着重要的意义。很多城市都开始通过建设地面空气监测站来实时感知地面的空气质量。但是由于监测站的建设成本高昂,一个城市的站点有限,并不能完全覆盖整个城市。如图6(a) 所示,北京城区仅有22 个空气监测站点(平均约100平方公里设一个站点)。然而空气质量受多方面因素影响(如地表植被、交通流量、楼房密度等),而且随地域不均匀变化。如果一个区域没有监测站,我们并不知道该地区空气质量的好坏,更不能用一个笼统的数据来概括整个城市的空气状况。
利用群体感知是解决这个问题的一种方式。例如,“哥本哈根车轮”项目在自行车车轮里安装一些传感器,通过用户手机将收集的数据发送至后台服务器。依靠群体的力量,我们就可以感知整个城市不同角落的温度、湿度和二氧化碳浓度。由于受传感器大小和感知时间的限制,这种方式只适用于部分气体,如一氧化碳和二氧化碳。由于传感器体积较大,不便于携带,对于细颗粒物(PM2.5) 这样的悬浮物则需要2~4 小时的测量时间才能产生较为精确的数据。
U-Air 利用地面监测站有限的空气质量数据,结合交通流、道路结构、兴趣点分布、气象条件和人们流动规律等大数据,基于机器学习算法建立数据和空气质量的映射关系,从而推断出整个城市细粒度的空气质量。图6(b) 显示了北京某时刻的细粒度空气质量(其中不同颜色表示不同污染指数,绿色为优)。
社交和娱乐
社交网络的盛行,尤其是基于位置的社交网络的风靡,带来了丰富的媒体数据,如用户关系图、位置信息(签到和轨迹)、照片和视频等。这些数据不仅表现了个人的喜好和习惯,也反映了整个城市人们的生活方式和移动规律。基于这些数据,产生了很多推荐系统,包括朋友推荐、社区推荐、地点推荐、旅行线路推荐和行为活动推荐。文献A survey on recommendations in location-based social networks 综述了基于位置的社交网络中的各种推荐系统。
城市计算中的社交应用更加强调从大量用户的社交媒体数据中提炼出群体智慧。人作为一个重要的感知和计算单元参与到计算的过程中是城市的重要特点之一。例如,一个用户的签到或者带有地标的照片数据都可被看成是不确定的轨迹,原因在于用户不会不停地签到或拍照。在得到这样一条轨迹数据时,我们无法判断出该用户选择的具体线路,如图7(a)。但是,当我们把很多个用户的不确定线路叠加到一起,就能猜测出最有可能的线路,如图7(b),即“不确定+ 不确定→确定”。这样的应用可以帮助人们规划旅行线路。例如,一个用户想在一条线路中去后海、天坛和颐和园3 个地方,把这3 个点输入到系统里,可以根据大众的签到数据计算出一条最热门的游玩路线。
社交媒体数据同时也向城市计算的其他方面贡献着力量。例如,通过网民在社交网络中发布的信息来预测总统选举结果、疾病蔓延和房价走势,发现异常事件和灾难,分析交通流量,设计广告推送和商业选址。通过社交媒体还能分析一个城市的风格以及不同城市之间的相似性。
能源消耗
文献Sensing the pulse of urban refueling behavior利用装有GPS 的出租车在加油站的等待时间来估计加油站的排队长度,估算出此时加油站内的车辆数目及加油量。通过将全城的加油站数据汇总,便可计算出任意时刻消耗掉(加入到汽车油箱里)的燃油数。这些数据能实现三方面的应用:第一,给需要加油的用户提供推荐信息,寻找排队时间最短的加油站;第二,可让加油站运营商知道各个地区的加油需求,从而考虑增加新的站点或动态调整某些加油站的工作时间;第三,政府可以实时掌握整个城市的油耗,制定更为合理的能源战略,如图8 所示。
文献Coordinated clustering algorithms to support charging infrastructure design for electric vehicles通过分析人口数据、车辆的轨迹数据、各地区能源消耗情况和兴趣点的分布来研究未来新能源汽车的充电站建在何处最优。也有不少工作通过分析汽车内部的传感器数据(如踩油门、刹车的时间和次数等)来建议经济省油的开车方式。
经济
城市经济是一个相对成熟的研究领域。例如,分析决定土地价格的因素、土地使用限制对经济的影响,公司选址和人们选择住宅的位置对周边未来经济的影响等。
文献Geo-spotting: mining online location-based services for optimal retail store placement通过分析大量用户的签到数据为商业选址提供位置建议。比如,要开设一个新的麦当劳餐厅,什么地方是最理想的位置。结合道路结构、兴趣点分布、人口流动等诸多因素来对屋的价值排序。即在市场向好时,哪些小区的房价将会涨得更多;市场下行时,哪些小区的房价比较抗跌。与使用传统经济学模型不同,以上这两个例子采用了机器学习算法和数据驱动的方法。
城市安全和应急响应
城市中总是会有一些突发事件,如自然灾害(地震和洪水等)、大型赛事和商业促销、交通事故和临时管制、群体性事件等。如果能及时感知、甚至预警这些事情,将能极大地改善城市管理,提高政府对突发事件的应对能力,保障城市安全,减少损失和悲剧的发生。
Discovering spatio-temporal causal interactions in traffic data streams、On mining anomalous patterns in road traffic streams、On detection of emerging anomalous traffic patterns using GPS data通过分析北京3 万多辆出租车的轨迹来发现城市中的异常事件。其主要思想是当异常事件发生时,附近的交通流将出现一定程度的紊乱。文献Inferring the root cause in road traffic anomalies 试图用具体的交通线路来进一步解释异常出现的原因。如图9所示,L1 连通的两个区域之间出现了交通流异常,但问题本身可能并不在这两个区域。其原因在于天安门附近因马拉松比赛而导致了交通管制,之前通过紫色虚线出行的车流就不得不绕道到绿色分段线的线路。所以绿色的线路才是产生这次异常的原因。根据司机选择路线的改变来捕捉交通异常,并进一步从相关的微博中提取关键词来解释异常的原因,如婚博会、道路坍塌等。
Modelingand probabilistic reasoning of population evacuation during large-scale disaster通过分析160 万日本人一年的GPS 移动轨迹数据库来对日本大地震和福岛核事故发生后的灾民移动、避难行为进行建模、预测和模拟。这样日后再有类似事件发生时,便可从之前的灾难中吸取经验,提前做好准备。例如,为人们推荐合理的撤退线路。
城市计算的主要技术
传感器技术
传感器网络 实现现有专业传感器(如温度传感器、位置传感器、交通流线圈、空气质量监测仪等)之间的互联互通,完成数据的快速收集。
主动参与式感知 用户通过主动分享自己获取的数据来共同完成一个复杂的任务。例如,每个用户都利用手机上的传感器来分享自己周边的气温和湿度,从而构建出全城细粒度的气象信息。
被动群体感知 城市里各种信息基础设施(如蜂窝移动通信系统和公交卡系统)为城市计算提供了良好的感知平台。这些基础设施可能并不是专门为城市计算设立的,但当用户在使用这些基础设施时会产生大量的数据,将这些数据融合到一起能很好地反映城市的韵律。例如,通过分析大量用户的地铁刷卡数据就能掌握城市的人口流动规律。通过分析大规模的出租车轨迹数据就能感知城市路面的交通流。与主动参与式感知技术不同,被动式群体感知中的用户并不知道自己的数据将作何使用,甚至不知道自己在产生数据。
数据管理技术
流数据管理 由于大量的传感器数据都以流的形式输入,高效的流数据库技术是城市计算数据管理层的基石。
轨迹管理 交通流、人的移动以及带位置标签的社交媒体都可以表示为轨迹数据(即带有时间戳并按时间排序的点序列)。在城市计算中经常会用到轨迹处理技术,如地图匹配算法、轨迹压缩、轨迹搜索、轨迹频繁模式挖掘等。
图数据管理 社交网络中人的关系、不同地区之间的人口流动、道路上的交通流等等都可表达为图模型。因此,图数据的管理和模式发现技术尤为重要。城市计算的应用中更多会用到带有时空属性的图模型,即每个节点都有空间坐标信息,图中边和点的属性(甚至图结构)会随时间而变化。前文提到的最快行车路线设计、查找路网中不合理规划、发现城市不同的功能区域以及交通流异常检测都是以带有时空属性的图为研究模型。
时空索引 有效的索引可以大大提高数据提取的效率。由于空间和时间是城市计算中最常用的两个数据维度,各种空间索引和时空索引都是常用技术。更重要的是利用时空索引技术将不同种类的数据(如文本、车流等)关联和组织起来,为之后的高效数据挖掘和分析做好准备。
数据挖掘技术
用于城市计算的数据挖掘和机器学习算法比较多。各种模式发现、统计学习和人工智能方法都可以应用到该领域。但在挑选这些技术时需要考虑以下两个因素:
能从异构数据中学习到相互增强的知识 通常有3 种方法来实现这个目标:(1) 分别从不同数据中提取特征,然后简单地将这些特征直接拼接并归一化到一个特征向量里,输入到机器学习的模型中。由于不区分不同数据的特性,因此这种方法并不是最有效的。(2) 在计算模型的不同阶段先后使用不同数据。例如,文献Urban computing with taxicabs先用道路数据将城市分割成很多区域,然后再将轨迹数据映射到这些区域上构建图,最后通过分析图模型来找出不合理的道路规划。(3) 将不同的数据分别输入到同一个计算模型的不同部分。如文献Discovering regions of different functions in a city using human mobility and POIs将人的移动性数据和兴趣点数据分别输入到一个主题模型的两个不同部分来分析城市的不同功能区域。文献U-Air: when urban air quality inference meets big data将交通流、人的移动性和气象数据等时变信息输入到一个随机条件场conditional random fields, CRF) 来模拟一个地点空气的时序相关性,将道路结构、兴趣点分布等空间(非时变)信息输入到神经网络中来模拟不同区域间空气质量的相关性。然后,这两个模型在半监督学习的框架里相互迭代、增强,共同推断出一个地点的空气质量。如果只是简单将所有数据输入到一个分类器中,由于那些空间数据不随时间变化,会被忽略,因此预测效果并不好。
应对数据的稀疏性 大数据与数据的稀疏性并不矛盾。以预测城市的细粒度空气为例,我们能观测到的交通流、人流、道路和兴趣点数据都是大数据,由于只有有限的监测站能产生空气质量的读数,因此,训练数据很稀疏。另外一个例子是利用出租车来估计城市的燃油消耗。出租车的GPS 轨迹数据巨大,但某些时刻有相当一部分加油站并没有出租车出入。如何估计这些站点的油耗,也是一个应对数据稀疏性的问题。解决这一问题通常可采用以下3 种方法:(1) 使用半监督学习算法或转移学习算法。如文献使用半监督学习算法来弥补因空气监测站少而带来的训练样本稀疏性问题。(2)采用矩阵分解算法和协同过滤。城市油耗估计就是利用这种方法来解决数据稀疏性问题的。(3) 基于相似性的聚类算法。假设我们需要根据埋在地面的线圈传感器来估计行驶在道路上的车辆数,但由于不是所有路面都埋有线圈,所以很多道路上的流量无法估计。根据道路的拓扑结果、周边的兴趣点分布等信息,我们可以计算不同道路之间的相似性,从而对道路进行聚类。这样被分在同一个类里的道路很可能具有相同的车流模式。于是,在一个类中,我们可以将有传感器道路的读数赋给那些没有传感器的道路。
优化技术
城市计算中也经常用到各种优化技术。比如文献T-Share: a large scale dynamic taxi ridesharing service就是通过将时空搜索技术和路径优化相结合来寻找能够接送乘客的最佳出租车。文献Inferring the root cause in road traffic anomalies通过线性规划来分析最有可能造成交通异常的车流。文献Where to Find My Next Passenger? 向出租车司机推荐最优的乘客寻找路线。
混合数据的可视化技术
可视化以直观的方式帮助我们理解获取的知识和模式。图10
是每个工作日 12~14
点之间乘坐出租车到达各个区域的人数的热度图(颜色越深,人越多)。将不同时间段的此类热度图连续播放,便可以动态反映整个城市的人口流动规律。相对而言,北京东部的中央商业区具有更高的人气。与单一数据可视化不同,城市计算中的可视化技术需要同时考虑多个维度,其中空间和时间是两个至关重要的维度。
结语
城市计算是一个新兴的交叉领域,是计算机学科与传统城市规划、交通、能源、经济、环境和社会学等多个领域在城市空间的交汇。它关系到人类未来的生活质量和可持续性发展。大数据时代的到来为城市计算提供了更多的机遇和更广阔的前景。
申明:《城市计算与大数据》一文在微软研究院博客上转载经由《中国计算机学会通讯》同意,版权归《中国计算机学会通讯》所有。原文刊登于《中国计算机学会通讯》2013年8月第90期
郑 宇
CCF高级会员、杰出演讲者。微软亚洲研究院主管研究员。
主要研究方向为基于位置的服务等。
参考文献
[1] Yu Zheng,Furui Liu, Hsun-Ping Hsie.
U-Air: when urban air qualityinference meets big data.
KDD 2013
[2] Yu Zheng,Yanchi Liu, Jing Yuan, Xing Xie,
Urban computing with taxicabs,
UbiComp 2011
[3] Jing Yuan,Yu Zheng, Xing Xie.
Discoveringregions of different functions in a city using human mobility and POIs.
KDD 2012
[4] Jing Yuan,Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, Yan Huang.
T-Drive: driving directions based on taxi trajectories.
ACM SIGSPATIAL GIS 2010
[5] Jing Yuan,Yu Zheng, Xing Xie, Guangzhong Sun.
Driving with knowledge from thephysical world.
KDD 2011
[6]Jing Yuan, YuZheng, Xing Xie, Guangzhong Sun,
T-Drive: enhancing driving directions with taxi driversintelligence.
IEEETransactions on Knowledge and Data Engineering, 2013
[7] Jing Yuan,Yu Zheng, Liuhang Zhang, Xing Xie, Guangzhong Sun,
Where to find my next passenger?
UbiComp 2011
[8]Jing Yuan,Yu Zheng, Liuhang Zhang, Xing Xie.
T-Finder: a recommender system for finding passengers and vacant taxis.
IEEE Transactions on Knowledge and Data Engineering
[9]Shuo Ma, YuZheng, Ouri Wolfson.
T-Share: a largescale dynamic taxi ridesharing service.
ICDE 2013
[10]N. Lathia andL. Capra.
Mining mobility data to minimise travellers’ spending on public transport.
KDD 2011
____________________________________________________________________________________
相关阅读
欢迎关注
微软亚洲研究院人人网主页:http://page.renren.com/600674137
微软亚洲研究院微博:http://t.sina.com.cn/msra