空间轨迹分析与应用（前言）Computing with Spatial Trajectories

空间轨迹分析与应用（前言）Computing with Spatial Trajectories

翻译：Esri中国  卢萌

空间轨迹分析与应用（Computing with Spatial Trajectories）一书是微软亚洲研究院主管研究院郑宇博士与昆士兰大学的周晓方教授联名写作的一本关于空间轨迹的经典之作，对于研究LBS有着无可估量的作用，可惜目前没有中文版，从本周开始，我将尝试以翻译和读书笔记的方法在博客上分享这本书。

一般好书的前言都会把整本书的思想做一个简述，从前言就能看出整本书的基本框架，所以这里把整个前言做了完整翻译。还是那句话，本人英文很烂，所以里面肯定各种错误，希望发现了错误的同学直接拍砖就好。或者给我发邮件:allenlu2008@163.com

前言

空间轨迹是一个移动的物体在地理空间中产生的痕迹，这些痕迹通常是一系列按照时间顺便排列的点，例如P1 -> P2 -> P3 …->Pn，其中每一个点都由地理信息空间的坐标集和时间戳所构成如：asp = （X,Y,T）。

因为位置定位和无线通信技术的进步，使得移动计算系统和基于位置的服务（LBS）快速的流行，从而导致表示各种移动对象的信息的产生，如种类繁多的人、车辆、动物和各种自然现象的在室内或者野外环境中的移动性空间轨迹信息，下面就是一些例子。

1、 人员流动：在很长的一段时间汇总，人们一直在空间表达的方式记录他们在真是世界中的运动轨迹，不管是被动的还是主动的。

 主动记录：如旅客们主动记录他们带有GPS轨迹的旅游路线，并且发表在个人空间中，与朋友分享经验。乘骑自行车或者慢跑的人可以记录他们的运动足迹以进行分析。在flickr中，每张带有位置标签来表示拍摄地点，以及带有拍摄时间来表示时间戳的相片，能够制作一系列带有地理标记相片的空间轨迹。同样，在相应区域“Check-ins（签到）”的记录，也可以被视作一个按时间顺序进行排序的轨迹。

 被动记录：用户在携带移动电话时，通过与相应的手机信号塔进行信息交互，从而无意中留下了关于手机信号塔ID表示的位置信息以及在服务区之间切换的时间记录，也留下了丰富的空间轨迹。同时，信用卡的交易记录也能表明持卡人的空间运动轨迹，因为每一笔交易都包含了一个时间戳和用来表示交易位置的商家ID。

2、 车辆的运动：近年来，大量配置有GPS的车辆已经出现在我们的生活中，例如，各大城市中都有大量配置了GPS传感器的出租车，使他们能够用一定的频率向数据中心报告含有时间标记的位置信息。这样的报告生成了大量的空间轨迹，可以用来进行交通资源优化、安全管理和流量分析。

3、 动物和自然现象的运动：生物学家们需要了解动物如候鸟迁徙运动轨迹的研究项目。同样气候学家们也都在忙着收集一些自然现象的轨迹，如飓风、龙卷风和洋流。这些轨迹为科学家们提供了许多关于它们的研究的丰富的信息。

总而言之，空间轨迹已经为我们提供了前所未有的丰富信息用以来研究和了解移动对象，这就要求我们的计算机系统要研究和提供新的计算技术，用于处理、检索和发展空间轨迹以及数据的挖掘和探索更为广泛的应用。因此空间轨迹的计算已经成为一个越来越重要的研究主题，吸引了广泛的关注。在这个研究主题中，有许多的领域，包括了计算机科学、生物学、社会学、地理学和气候学等等。

虽然有很多书都对空间数据库、移动计算、数据挖掘做了论述，但是本身是第一本致力于空间轨迹数据计算的专著，具有覆盖面广和权威的论述。主要针对高年级本科生，研究生，研究人员和专业人士，本身涵盖了空间轨迹计算的基本情况和架构领域的各类主题。每一章都是一个教程，为读者提供了一个计算机入门，空间轨迹的相关研究说明，内容中包含了许多相关研究论文的有价值的参考。本书提供了对空间轨迹索引，搜索和数据挖掘的全面概述，也提供了对此进行研究和程序开发的一般概念，以及新的方法和应用，以便用以帮助研究人员探索这个令人兴奋的领域。它还大致介绍了到最近的一些发展以吸引研究人员和其他有兴趣的读者加入到这个充满希望的研究领域。

本书的章节按照：“轨迹预处理的组织范式 -> 轨迹索引与检索 -> 高级主题”三部分进行组织，如图1。

本书的前两章介绍了空间轨迹数据处理的基础：轨迹预处理（第一章）和轨迹索引及检索（第二章）。第二部分由六个高级的主题组成：空间轨迹的不确定性（第三章），空间轨迹的隐私权（第四章），轨迹模式的挖掘（第五章），基于空间的运动轨迹识别（第六章），驾驶轨迹分析（第七章）以及基于位置的社交网络应用（第八和第九章）。

具体来说，本书会逐步引入各种概念和技术来解决新入门的学习者研究这个领域时面临的一些问题，从最开始的数据预处理到空间运动轨迹，然后进行不确定性挖掘，隐私保护和轨迹模式识别，最后利用空间运动轨迹进行包括行为识别、驾驶和基于位置的社交网络等的一系列高级应用。下面是对每一章的内容进行简要的介绍：

第一章：空间轨迹携带了可在各种应用中使用的丰富信息，我们在使用之前需要处理一些问题。通常，物体的连续运动被记录为一个离散采样的近似形式的定位点。通过这些位置点采样率生成精确的轨迹，但是高精确的轨迹会导致数据存储、通讯和处理的巨大开销。因此，要设计一个能够对轨迹数据进行压缩的技术，另外保存轨迹数据的有效性也是至关重要的。同时，轨迹数据通常会因为异常值或者定位系统的信号不好而产生噪点。例如，在车辆行驶在“城市峡谷”中的时候，卫星信号到GPS设备通常接受效果非常差，由此会产生一系列显著偏离了真实位置的坐标点。有时候，偏移量甚至超过了一英里。所以设计一种减少轨迹噪声的技术对此类轨迹应用的系统是非常有用的。这样一来，就需要用空间轨迹技术的过滤方法对噪音数据进行预处理。

为了解决这个问题，在第一章中提出了一个可以在批处理模式下运行的数据收集或者是在线模式下座位数据被收集后的数据处理技术。本章的第二部分介绍了用于从轨迹位置中过滤和测量噪声的方法，包括均值和中值滤波，卡尔曼滤波和粒子滤波。总之，本章提供了一个新的预处理框架，这是空间运动轨迹分析的基础。

第二章：各种基于位置服务的流行导致了无数的轨迹数据，对这些轨迹数据进行计算对应用系统来说是一个巨大的负担。如果轨迹数据集没有一个很好的组织方式让我们可以快速查找，那么各种计算将非常的耗时。例如，检索一个经过十字路口的轨迹，本来是是一个很简单的任务，如果这些系统必须直接扫描大量的轨迹数据集的方式来检索，那么这种方式在线系统就完全不可行了。在很多场合我们还可能需要寻找满足某些条件的特定轨迹，这就需要通过时间和空间的限制进行检索。例如一个游客要检索在特定的时间范围内通过一个特定的区域的空间轨迹，用来帮助他制定旅行计划。从这些实际的应用要求，就需要我们开发切实有效的运行轨迹索引和检索技术。所以，我们在第二章介绍了在常用的数据库中对轨迹数据的通过索引和检索技术支持的相应查询处理办法。

第三章：对空间轨迹数据继续预处理和组织数据结构之后，我们就可以使用他们来进行各种应用和分析了。然而，定位器本质上是不准确的，从而导致我们获取的关于移动物体的位置有一定的不确定性。例如，GPS传感器的读数通常由10米甚至是更大的定位误差。有了这样的读数，使我们可能不容易识别移动的对象光顾的感兴趣的地点（如餐厅或者商城），尤其是在人员密集的城市地区。同时对象是在连续移动中的，同时他们的位置可以仅在离散的时间内进行更新，这样在两个更新的具体位置之间，运动对象的移动信息就存在不确定性。有两个原因会导致比较长的更新间隔，一是节约能源消耗，二是节约通讯带宽。当两个更新之间时间间隔超过了几分钟甚至是级小时，那么空间轨迹的不确定性就严重的降低其效用性，并且在搜索移动物体的时候，提出了新的挑战。

为了除以以上的不确定性，在第三章介绍了有关不确定性空间轨迹的相关概念以及各种问题和解决方法。对有关建模和代码移动对象数据库（MOD）的不确定性问题进行了介绍。并且讨论了一些高效的处理算法来处理不同的时空查询问题。请注意，第二章的查询处理并没有考虑到空间运动轨迹的不确定性，而这点是本章的重点。

第四章：虽然LBS服务为移动用户提供了很多有价值的应用，但是对于个人私人地点可能暴露给不受信任的LBS服务提供商给人们带来了对隐私的担忧。在LBS服务提供商所提供的服务与用户位置隐私保护之间如何进行平衡？用户位置的定位发现得越精确，可提供的服务质量就越好，但是用户的隐私被保护得就越少。

一般而言，有两种类型的LBS，即快照和连续的LBS服务。对于快照类型的LBS服务，需要获取信息的时候，移动用户才将自己当前的位置报告给服务提供者。事实上，用户认为使用这种服务的时候没有必要通过LBS系统提交精确的位置。例如，寻找附近的酒店，用户只需要报告一个包含当前位置信息的粗略的地理区域即可。有很多文章都已经通过了关于保护用户快照位置的内容，所以第四章将不对此类应用进行讨论。

另一方面，用户需要周期性或者按需的方式，将自己的位置信息提交给服务提供商，以得到连续的LBS服务（例如，获得实时的交通信息或者在驾驶中选择最近的加油站）。保护用户在连续LBS服务上的位置隐私服务，就比快照LBS更有挑战性，因为心怀不轨者可以使用用户运动轨迹样本的时间和空间上的相关性，能够较为精确的却行推断出用户的位置信息。总之，如果原始的空间运动轨迹向公众或者是第三方开放，可能会造成严重的隐私问题。所以目前，对连续的LBS以及相应的轨迹数据发布的隐私保护已经收到业界的重点关注。在这种情况下，我们在第四章介绍了一些国家队连续LBS和轨迹信息开发最先进的一些隐私保护技术。

第五章：空间轨迹的庞大体量能够用户分析任何移动物体，他可以由含有某种模式或者包含有多组相似的模式的单独的轨迹来表示各种移动形态。也可以是有相似的性质但是轨迹不同的区段（如，定义了固定的时间和空间范围的数据集），或是一组满足相同的条件的完整的轨迹。这些运动模型有着广泛的应用领域和服务价值，包括交通、生物研究、体育、社会服务等。例如，集群汇聚的轨迹，里面的各种轨迹具有相似的空间模式，可以帮助检测用户行驶路线或者是研究鸟类的迁徙路线。此外，对一起运动的、提供建议的或者允许出租车共享的一群人的识别，可以促进对社会关系的探索。第五章中介绍并评价了一些现有的文献中关于轨迹模型信息根据不同模式进行分类的索引结构和模式挖掘的研究。

第六章：在对空间轨迹进行预处理、管理和模式挖掘后，人们可能会问，基于这些轨迹数据我们可以做些什么的应用。行为识别就是可以利用直接轨迹信息的一种核心的应用。直观的说，人们产生的空间轨迹意味着用户的行为和活动，这样就通过一些低级别的传感器的读数可以对高层次的目标用户的体现出一种新的洞察力。首先，一个人的活动可以被用作背景环境来感知如何满足一个人对潜在服务的需求。例如，如果已知用户正在驾驶车辆，她的移动电话可以自动显示用户周围道路的交通状况，并且暂时禁用手机的娱乐功能（为了她的安全），因为娱乐功能会分散驾驶员的注意力。如果我们知道用户是在开会或者在看电影时，那么用户的手机就可以切换为静音模式。第二，多个用户的活动使我们能够通过收集社会知识，有助于我们对社交网络和交通信息的分析。如果有多个用户的互动信息，那么我们从两两者之间的相似性，以对二者间估算就会更加精确，所以可以提供更好的社会发现服务以及朋友和位置的相关建议。

同时，快照位置数据之外所能提供的数据信息更加丰富，空间运动轨迹也需要更先进的基于行为识别的技术。为了帮助新入门的学习者，第六章描述了现有的以轨迹活动为主的研究内容，并且更加参与训练和推理的用户样本，把他们分成两类。

第七章：车辆的轨迹体现了与交通运输的情况，驾驶行为是我们生活中最核心的环节之一。可以从这些轨迹中得到丰富的信息，如从驾驶员的行为信息中得出道路网络、交通网络等信息，从而从不同方面给出有利于驾驶体验的建议。例如，根据GPS轨迹创建的路线图是一个比传统方式更便宜的得到最新的路线图的方法。另一方面，基于一个或者多个有经验的司机的轨迹会产生更为有效的建议。

第七章介绍了驾驶行为如何受益于空间运动轨迹的分析，以下是一个应用的基本范式：“从GPS轨迹创建地图道路 -> 将驾驶员的单一运动轨迹映射到道路网络上 -> 挖掘有效的行车路线 -> 从驾驶员的个性化驾驶路线轨迹中学习到基于偏好的特定驾驶习惯”。

第八章和第九章：位置定位和移动通信技术的进步，使个体用户也产生了各种空间轨迹，这意味着丰富了有关用户的行为、兴趣和喜好等的各种信息。最近，人们已经为各种不同目的，而开始通过在线社交网络服务来分享他们的轨迹数据，这样就培养了一批以轨迹为中心的LBSNS应用（基于位置的社交网络）。例如，用户可以记录他的行驶路线，并且在一个在线社区通过GPS轨迹分享他的旅游经验，或者通过慢跑日志和自行车运动来分析或者进行分析。此外，签到类的应用在以Foursquare或者Flickr应用中，将用户的旅行相片“看作空间运行轨迹”。以这些轨迹为中心的LBSNS使我们能够了解用户行为和位置，并且探讨他们之间的关系。

一方面，我们可以了解一个人，并且通过他与其他不同用户之间的轨迹来发现他们的相似性，从而提供个性化的服务，并且还可以进行朋友推荐以及社区发现。另一方面，我们能够识别位置，并且根据用户的信息，以及两个不同位置之间的关系，为用户提供比如旅游一类的更好的建议。

在第八章中，定义了基于位置的社交网络的意义，并从其后的用户和位置的角度讨论了有关LBSNS的研究理论。在以轨迹为重的LBSN中，本章探讨和关心的是以下理解用户位置的两个基本问题。一个是对个体位置的个别历史轨迹数据的建模。另一种是根据其历史位置估计两个不同的用户之间的相似性。相似代表了基于位置的社交网络的两个用户之间的连接强度，通过它可以提供友情建议或者社区发现。有一些为这些应用程序的进行评测的可用的方法以及一些可公开的数据集，已被列入了第八章。

虽然第八章的研究，提出了从用户背后的角度来看一个基于位置的社交网络的研究理念，在第九章将进一步进行从位置的角度探索和研究LBSNS。一系列的研究课题都提出使用大量用户的GPS轨迹挖掘集体的社会知识，以方便用户的出现。首先是一般的旅行建议，都是通过旅游的专家想用户提供最有趣的旅游点、路线和区域，以及一个通过用户开始的时间和位置进行调节的有效的行程。第二，个性化的旅游建议能够发现一些匹配用户个人兴趣的内容，这些个性化的建议可以从收集懂啊的个人历史位置数据中挖掘出来。

最后，我们希望本书能够为您提供一个实用的概述信息，并且为有志于在计算和空间轨迹领域发展的年轻人提供帮助。

微软亚洲研究院Yu Zheng 澳大利亚昆士兰大学 Xiaofang Zhou 2011年7月。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。