面向位置服务的空间同位模式挖掘研究

Location-based service is an efficient way of helping service providers and users to acquire the needed information from massive location data. Location-based service is based on the analysis of users’ trajectories in location data. Existing methods to analyze trajectories focus on the information alone in trajectories. Nevertheless, richer and more meaningful knowledge about trajectories can be discovered by exploring spatial co-location patterns of spatial features in and around trajectories due to incomplete trajectories and the spatial autocorrelation. But traditional co-location mining methods do not properly consider spatio-temporal characteristics of data, such as co-locations’ occurrence time, granularity and time-variant. However, spatio-temporal characteristics of location data must be considered. The project aims to mine co-locations for location-based service by exploiting spatio-temporal characteristics of location data, including spatio-temporal co-locations, multi-granularity co-locations and evolving co-locations; propose novel models, methods and algorithms to mine co-locations; discuss the applications of co-locations in location-based service; and develop a prototype of co-location mining for location-based service. The success of this project will advance the development of the theories and technologies for co-location mining on location data, and underpin location-based service.

基于位置的服务是协助服务商和用户从海量的位置数据中选取所需信息的有效手段。位置数据中的用户轨迹分析是位置服务的基础，目前的轨迹分析方法主要考虑轨迹自身的信息。由于轨迹的不完整性和空间自相关性，为了更好地揭示轨迹所蕴含的知识，需要考虑轨迹中空间特征与周边空间特征的空间同位模式。但是传统的同位模式挖掘方法没有较好地考虑数据的时空特性，如同位模式的出现时间、粒度特性、时变特性，而位置数据固有的时空特性却不容忽视。因此，本项目面向位置服务，着重考虑位置数据的时空特性，系统地研究时空同位模式、多粒度同位模式、演化同位模式，提出支持这些同位模式挖掘的数据模型、挖掘方法及算法，讨论这些同位模式在位置服务中的应用，开发面向位置服务的同位模式挖掘原型系统。本项目的研究将促进位置数据的同位模式挖掘理论及技术的发展，为位置服务提供支持。

随着移动终端、移动互联网等信息技术的发展，用户签到、城市兴趣点等位置数据急剧膨胀。通过分析海量位置数据，提供诸如兴趣点推荐等位置服务，以协助人们选取所需信息，成为了大数据时代应对信息过载的有效手段。为了更好地揭示位置数据蕴含的知识以支持位置服务，需要考虑位置数据的时空特性，研究位置数据中的同位模式。.项目分析了位置数据的时空特性，研究了时空同位模式、多粒度同位模式、演化同位模式的数据模型、挖掘方法及算法，以及在位置服务中的应用。.项目研究时空同位模式，提出表达空间特征间丰富时空关系的星型实例模型，进而提出亚频繁同位模式、时空亚频繁同位模式及挖掘算法；提出融合用户签到的时空聚集和衰减影响的时空同现模式及用户时空相似性度量方法；提出融合空间实例间空间距离和社会距离的共同访问模式及挖掘算法；提出兼顾用户轨迹的时空聚集及时间连续性和方向性的停留点识别方法；设计同位模式的高效挖掘算法、并行挖掘算法及检索方法。.项目研究多粒度同位模式，提出基于本体的空间特征概念层次模型、非点状空间实例的邻近关系计算方法、自适应空间实例分布的邻近关系抽取方法，进而提出同位模式交互挖掘方法，关键同位模式、显著同位模式及挖掘算法；利用IL-Quadtree索引结构的优势，设计空间模式的有效匹配算法。.项目研究演化同位模式，分析空间特征间的主导关系，提出含主导特征的同位模式、亚频繁同位模式及挖掘算法；分析闭同位模式中空间实例间及空间特征间的相互关系，提出同位模式无损压缩表达即超参与度闭同位模式及挖掘算法；分析交通拥堵的时空传递性，提出时空拥堵同位模式、拥堵传播模式及挖掘算法；设计同位模式的增量挖掘算法。.基于上述研究成果，项目研究同位模式在搜索与推荐朋友、兴趣点、路径、选址等位置服务中的应用。.项目研究成果在理论上促进了同位模式挖掘模型、方法及算法的发展，在应用上为位置服务提供了技术支持。