【作者】 邵非；

【导师】 顾君忠；

【作者基本信息】 华东师范大学 ， 系统分析与集成， 2012， 博士

【摘要】 在目前信息与通信技术(Information&Commuication Technology, ICT)飞速发展的时代背景下,基于固定网络的通信模式已逐渐为基于无线网络的移动通信所取代；与此同时,空间信息技术,尤其是Web GIS、GPS、RS、VR以及与Context Awareness、CSCW的集成,有力的推动了移动信息服务的社会化和普及化。在技术进步和市场需求的双重驱动下,基于位置的服务(Location Based Service, LBS)得以飞速发展,在多种应用中开始扮演越来越重要的角色。基于位置的信息服务是面向移动的,所以它是一种移动信息服务,是一种能通过移动网络,使用移动设备,并借助于移动设备的定位功能得到访问信息的服务。实际上这种应用是因特网、GIS/空间数据库和新一代信息与通信技术(NICT)的汇集,它把对象的时空位置作为相关信息的索引,在一定程度上屏蔽了物理世界与虚拟世界之间的鸿沟,其计算的透明性、移动的无缝性、信息访问的普遍性、基于情景感知的智能性,使用户在日常环境下能够使用任意设备、通过任意网络、在任意时间获取与位置有关的信息,真正实现了以“人”为中心的信息服务、而不是桌面计算模式以“机器”为中心的操作处理。在目前各种基于用户或移动对象时空位置的应用中,应用系统会通过多种传感器不断获取用户或移动对象的时空位置情景信息,并将这些信息集合通过移动网络以时空轨迹(Spatio-Temporal Trajectory)的形式存储于移动对象数据库(Moving Object Database,MOD)中。在上述这些应用中,时空轨迹是移动对象在三维时空中移动行为的数字化抽象,其中隐含着大量的用户或移动对象的移动模式、行为偏好等有价值的特征信息,对其进行有效的分析和挖掘是前述应用的基础。基于位置感知的移动信息服务就是依据移动对象的时空位置提供相应的信息。典型应用如：信息推送。其应用的基础同样是移动对象的时空位置,故其关键问题一言以蔽之,就是对移动对象过去、现在、将来位置的获取、管理、挖掘,而移动对象的时空位置是连续变化的(相对静止是移动的特例),基于位置感知的移动信息服务的关键问题也就转换为对移动对象轨迹的获取、管理、挖掘。目前位置感知领域的研究主要集中于对时空轨迹中蕴含的历史位置、当前位置的感知、存储和查询,而对于轨迹中蕴含的移动行为偏好及特征模式进行研究、进而对用户或移动对象的未来位置查询与移动意图判断却相对滞后。受其影响,移动信息服务的依据是用户当前所在位置,默认用户的当前位置即代表用户的移动意图,其不合理性是显而易见的。1、不同的用户在相同的时空位置其意图并不一定相同,同一用户不同时刻在同一空间位置需求也不一样,仅依照用户当前所在位置推送信息,其准确性难以确定；2、即便当前时空位置在一定程度上能代表用户的移动意图,由于系统计算的时间开销,依照用户当前所在位置推送信息必然产生一定的滞后性,对于移动速度较快的用户尤为明显。从生活实践中我们可以知道,对信息的需求不仅局限于过去和当前的信息,更重要的是要应对或远或近的将要发生的事件,而当前的基于位置感知的移动信息服务未能从用户移动的历史数据中有效挖掘共性规律,未来位置感知的准确性、及时性较低,对用户移动意图判断的智能化、个性化不足,严重影响了移动信息服务的应用。目前在无法预先获取移动对象移动计划的情况下,判断移动对象未来位置的有效也是唯一的依据便是其历史时空轨迹信息,由此,如何从移动对象的历史轨迹信息中获取共性特征,发现偏好模式,并据此推断出移动对象的未来较远时空位置,将是基于位置感知的移动信息服务中的关键技术,也即是本文讨论的重点。本文基于移动对象移动行为的重复性,提取移动对象历史时空轨迹集中隐含的共性的移动偏好模式,然后将移动对象当前轨迹与不同的移动偏好模式比对,以其中似然度最大者作为其未来的移动计划,并据此采用回归算法获取移动对象的未来较远时空位置,将其作为移动信息服务提供的基础性依据。按照这一技术路线,本文从四个方面研究了上述位置感知中的关键问题：1)位置感知计算系统框架：提出了位置感知计算和通用情景感知计算的区别与特点,在综合通用情景感知计算模型的基础上建立了一个专用的位置感知计算概念模型,解决了情景感知计算的单向性问题。基于此,本文将现代心理学中“外观-内省”学习过程引入位置情景感知计算中,提出了一种基于外观感知和内省感知的“外观-内省”情景感知计算流程EICACP。外观感知通过感知外部环境中与对象时空位置相关的可用信息,并自动自主地进行推理、决策和计算,从而大大降低需要人参与的程度,进而实现透明交互和精确服务；内省感知通过对整个位置感知计算过程进行监视,检查情景感知系统自身的情景信息处理和推理方式,从失败或低效中发现问题,进而自动修正感知计算过程、改进系统自身效能；外观与内省在位置感知计算中相互促进、相辅相成。同时本文基于上述“外观-内省”情景感知计算流程提出了一个相应的位置感知系统模型。整个模型由低层情景搜集、情景组织、高层情景应用、应用程序接口、情景存储与管理、安全与隐私6个部分组成,其中情景组织是核心部分,情景信息的建模、过滤、推断、融合、内省构成了情景信息演化的主要内容,其功能一是通过对低层情景信息进行建模、过滤、推断、融合等得到各应用所需的高层情景信息,其中通过移动历史信息提取移动偏好模式、进而依据当前移动行为推断未来情景信息是其最基本、最关键的功能；二是监视高层情景信息的应用结果,从中判定失败、解释失败、修正失败,并将修正及时反馈给推断、融合部分,不断提高情景组织的准确性。2)位置情景建模：时空位置情景建模一直是位置感知计算的关键问题之一。本文结合基于本体的模型和时空数据模型,提出并设计了两层结构的位置情景层次化模型。本文将位置情景模型分为两层：高层情景本体模型(Context Ontology Model)(?)口低层时空数据模型(Spatio-Temporal Data Model),两层间通过模型翻译器的查询接口互连,用以解决位置情景的查询与推理分离的问题。高层情景本体模型主要解决推理和共享的问题；本文使用OWL对其进行描述,定义核心位置情景实体为：对象(Object)、位置(Location)、行为(Activity),并使用RDF三元组<Subject, Predicate, Value>进行规范表达,描述移动环境中的物理实体或逻辑实体及其状态,以实现位置情景的共享和明确,在此基础上集中探讨了核心情景实体间关系、情景状态变迁、位置情景的生命周期管理。低层时空数据模型主要解决存储与查询的问题；本文对模型原理和信息更新策略进行了探讨,对基本概念进行了定义并设计了时空数据模型总体视图。针对时空位置信息的动态属性,本文分析了位置情景的可能状态与变迁,提出了位置情景信息的生命周期管理算法。针对目前移动对象数据库存在的不足,本文提出了改进的2维移动对象时空数据模型EBMOST,设计了时空数据模型总体结构。针对目前移动对象数据库位置更新策略仅针对点状对象的不足,提出了一种新的特定时空位置更新策略,当移动对象进入环境对象所在位置点一定范围,MOD即认为移动对象已进入该对象并更新MOD中的位置信息；该位置更新策略能更有效地反映移动对象与环境之间复杂的语义及拓扑关系,并在一定程度弥补了MOD将实体对象抽象为零维点之后无法表示面状对象的不足。3)移动情景组织相关算法——移动偏好模式提取算法：本文以未来位置情景计算为目标,首先根据时空轨迹的连续性特征与位置更新的离散化途径之间的矛盾,提出一种轨迹插值算法,用以屏蔽不同位置更新策略、采样信息粒度等因素对轨迹间距离造成的干扰；然后将Hausdorff距离引入轨迹间距离的计算中,并基于轨迹插值算法,提出了时空轨迹间距离算法IMHD-ST,分别从空间和时间维度度量轨迹间差异,解决了移动情景组织中最基础的轨迹间距离度量的问题。本文其次对移动偏好模式的语义进行了探讨,基于移动偏好模式语义提出了移动偏好模式的提取方法PPCG,将移动偏好模式提取分为分害(?)(Partition)-剪枝(Prune)-聚类(Clustering)-生成(Generation)四个步骤,分割步骤将相似直子轨迹段合并为一条直轨迹段,用于在精度的有限损失的前提下降低算法的时间开销；剪枝步骤剔出直子轨迹段集合中的噪声,留下相似的直子轨迹段聚类簇；分类步骤将直子轨迹段聚类簇中的轨迹段还原为完整的轨迹,并进行聚类；生产步骤则最终生成三维时空内的移动偏好轨迹,实现了从离散的移动对象时空位置更新点到连续的移动偏好模式的提取目标。其中,本文在PPCG的“分割”步骤中提出基于MHD-S的固定阀限轨迹分割算法MHDS-Partition;在“生成”步骤中提出了基于扫描圆和垂直扫描线的移动偏好轨迹生成算法,并给出了由静态的、离线的处理模式向动态的、在线的处理模式的变换算法。4)移动情景组织相关算法——未来位置情景计算相关算法：未来位置情景计算是未来位置情景预测中最重要的算法,本文针对时空位置情景信息的特殊性,在算法思想上提出基于集成的朴素贝叶斯分类器与线性回归相结合的方法实现性能互补,既具备朴素贝叶斯分类器的准确,又具备线性回归的速度,以满足时空位置情景信息特殊性和移动信息服务实时性的需求。在算法设计上本文首先提出基于朴素贝叶斯分类器集成的动态偏好轨迹分类模型(Boosted Dynamic Naive Bayes Classifier for MTP, BDNBCM);朴素贝叶斯分类器以其高效而著称,而集成的方法可以在较大程度上优化分类性能,动态偏好轨迹分类模型将二者结合起来用于处理动态变化且不完整的时空位置情景信息,提高了未来时空位置预测精确度；同时本文给出了动态基分类器数量K的选取思想及其算法,使动态偏好轨迹分类模型结构在满足分类要求的前提下,计算开销最小。本文同时给出了上述分类模型参数的条件密度计算方法；由于时空位置情景信息的特殊性,直接估计移动模式类或移动轨迹类的相关参数比较困难,故在本文中以连续移动偏好轨迹为介质,基于插值算法动态获得待分类轨迹各位置更新点对应的参数估计其次本文研究了基于回归的未来时空位置算法；提出未来位置情景的回归算法；该算法基于分类计算获得的未来移动计划和当前移动状态,将回归计算转化为以时间为索引的查询,改变以前文献中将移动模式拟合到某一以时间为变量的函数中的方法。由于有未来移动计划限制和当前移动状态修正,其预测精确度较无限制、无修正的回归算法有较大提高。本文以在移动环境下实现准确计算用户未来时空位置等高层位置情景信息作为研究目标,对能够有效提高高层位置情景信息准确度方面的关键技术进行了系列深入研究,就获取未来时空位置情景所涉及的若干相关问题提出了高效、实用的解决方案。本文主要创新在于：1、引入心理学“外观-内省”概念、建立了专用的位置感知计算概念模型,并提出了与之相适应的位置感知系统模型；2、提出并设计了两层结构的位置情景层次化模型,兼具本体模型与时空数据模型的优点；3、提出并设计了基于Hausdorff距离的3维时空(2维平面-1维时间)轨迹相似度算法；4、提出并设计了基于密度聚类的移动偏好模式的提取方法；5、提出并设计了基于集成的朴素贝叶斯分类器与线性回归相结合的未来位置情景算法。本文主要贡献在于：提出了系统化的未来时空位置情景预测方法和相关算法；该方法及算法能够在现有技术条件下,依据移动对象历史位置情景信息更快速、更准确的计算其未来时空位置等高层位置情景信息。本文对提出的各种算法都进行了详细的功能、性能分析,使用了模拟数据集或实际数据集在不同参数情况下进行了详细实验,并与相应领域当前主流算法进行了功能、性能方面的对比。本文的多项研究成果也发表于相关领域的国际会议和国内核心期刊上,并被EI或SCI-E检索,其中包含ICCSE2010.APCIP2010等国际会议各一篇,《Journal of Computational information Science》一篇,《China Communications》-一篇等共计4篇学术论文。综上所述：本文所述各算法能有效解决相关问题,与当前相关算法相比具备完备的功能和良好的性能。因此,本文的研究成果对于基于位置感知的移动信息服务若干关键技术的解决具有较大的理论及应用价值。本文所使用实际数据集来自美国unisys网站提供的全球(包括大西洋、东太平洋、西太平洋、南太平洋、南印度洋、北印度洋)飓风历年轨迹数据集。更多还原

【Abstract】 With the rapid development of Information&Communication Technology (ICT) recently, the fixed network-based communication pattern has gradually been replaced by wireless network-based one. Meanwhile, spatial information technology, especially the integration of Web GIS,GPS,RS,VR and Context Awareness、CSCW, has powerfully promoted socialization and popularity of the mobile information service. Being driven by technological progress and market needs, the Location Based Service (LBS) develops rapidly and plays more and more important role in various applications.LBS is moving oriented, so it is a mobile information service, which can get accessed information by virtue of location of mobile equipments through the mobile network. In fact, this application is a collection of internet, GIS/spatial database and a new generation of information and communication technology. It makes spatio-temporal locations of objects as index of related information and shields the gap between physical world and virtual world. Besides, its characters, such as transparency of the computation, seamlessness of the moving, generality of the information access and context-aware intellectuality, has made users get access to any location based information by any device and any network at any time and realized the people-centered information service rather than the machine-centered operation just as desktop pattern does.During these applications based on users and spatio-temporal location of moving objects, applying systems can continuously obtain the information of spatio-temporal location of users and moving objects through kinds of sensors. Meanwhile, the information will be stored in Moving Object Database (MOD) in the form of spatio-temporal trajectories. A large number of valuable characteristic information of users or moving objects, such as moving patterns and favored patterns, is implied in spatio-temporal trajectories, which reflects moving behaviors of moving objects in the MOD under three dimensional time space and is also the basis of applications mentioned above.The location aware-based mobile information service supplies relevant information according to spatio-temporal locations of moving objects and typical application is such as the information recommendation. The basis of it is also the spatio-temporal locations of moving objects. In a word, its key problem is to obtain, manage and mine the historical, present and future locations of moving objects. However, spatio-temporal locations of moving objects change continuously (Relative rest is a particular case of motion), so for location aware moving information service the key is transformed to the acquisition, management and mining for moving object trajectories.At present, the researches in location-aware fields mainly focus on the inquiry for historical and future locations implied in spatio-temporal trajectories, which doesn’t do well in studying for moving behavior preference and characteristic patterns implied in trajectories and then querying future locations and judging moving intensions for users or moving objects. Affected by it, moving information service comes to make the present location of users to represent moving intensions of them, which is obviously unreasonable. First of all, different users may not have the same intensions even in the same spatio-temporal locations, so it cannot guarantee accuracy to recommend information according to users’ present locations. Besides, even if present locations can represent users’moving intensions to some extent, it will still cause hysteresis to do so considering the time cost of system computing, which is especially obvious to users who move fast.In daily life, we know that the need for information is not only confined to historical and present information but impending incidents. However, present location aware-based moving information service cannot effectively mine common characters from historical data of users’ movement, which cause low accuracy and low timeliness for future location awareness and is not enough intelligent to judge users’ moving intensions. All of these cause serious influences on the applications of moving information serviceConsidering the situation that moving plans cannot be obtained previously, the historical spatio-temporal trajectory information is the only basis to judge if the future locations of moving objects are effective. Thus, it will be the key technique in location aware-based moving information service and also important points in the thesis to research how to get common characters from historical trajectory information of moving objects and discover biased patterns, according to which farther future spatio-temporal locations of moving objects will be inferred.Based on repeatability of moving behaviors for moving objects, the paper generates common moving preference patterns implied in historical spatio-temporal trajectories of moving objects. Then present trajectories of moving objects are compared with different moving preference patterns and the nearest one is found, according to which we can discover future father spatio-temporal locations of moving objects. It can be viewed the basis of the mobile information service. The paper does research on key problems from four aspects for location aware above which are respectively the schema of location-aware computing, model of location context, algorithm of location context organization and algorithm of future location context generation.1) The schema of location-aware computing. This paper proposes the characteristics of location-aware computing in comparison to comprehensive general context-aware computing. On that basis, a special location-aware computing conceptual model build on comprehensive general context-aware conceptual model is put forward. In the paper, it introduces the "extrospection-introspection" learning process in modern psychology in location-aware computing and proposes the "extrospection-introspection" context-aware computing process based on extrospection perception and introspection perception. Extrospection perception is to perceive available information related with spatio-temporal position in the external environment and then to proceed with deduce, decision and computation automatically, which can decrease manual participation to a great extent and then achieve transparent interaction and precise service. Introspection perception is to monitor the whole location-aware computing process and check context information process and reasoning method of the context-aware system itself. Then it can find problems from failures and low efficiency and further correct computing process and improve efficiency automatically. So extrospection and introspection supplement each other in location-aware computing.According to the "extrospection-introspection" learning process in modern psychology, it proposes a corresponding location-aware system model in the paper. The whole model is composed of lower context collection, context organization, high-level context application, application program interface, context storage and management and safety and privacy, in which context organization is the key and modeling, filtering, deducing, integration and introspection consist of main content in context information evolution. On the one hand, it can get high-level context information needed by each application by modeling, filtering, deducing and integrating lower context information and then extract moving preference model through moving historical information and further deduce context information in the future through current moving behavior, which is the basic and key function. On the other hand, it can monitor results of high-level context information and then judge, explain and correct failures and further feed back them to deduce and integration parts so that precision of the context organization is improved.2) Location context modeling. Space-time location context modeling is always one of the key problems in location-aware computing. Combined with the ontology-based model and spatio-temporal data model, the paper proposes and designs hierarchical model for location context which is consisted of two-layered structures. The location context model is divided into two layers which are respectively high-level Context Ontology Model and low-level Spatio-Temporal Data Model. Two layers are connected by query interface of model translator to solve the problem of separating the query and the reasoning in location context.The high-level Context Ontology Model is mainly to solve problems of reasoning and sharing and it is described by OWL. The key location context entity is defined as object, location and activity and expressed by the triples of RDF<Subject, Predicate, Value>. It describes physical entities or logical entities and their states in the moving environment to realize the sharing and precision of location context based on which the model focuses on discussing relations among key context entities, context state transition and life circle management of the location context.The low-level Spatio-Temporal Data Model is mainly to solve problems of storage and query. The paper discusses the model principle and information updating strategies and also defines the basic concept and designs the overall view of the spatio-temporal data model. As for the dynamic attribute of spatio-temporal location information, the paper analyses possible states and transitions of the location context and proposes the life circle management algorithm of location context information. As for present shortages of database of moving objects, the paper proposes the improved2-dimentional spatio-temporal data model of moving objects EBMOST and designs the overall structure of the spatio-temporal data model. As for the shortage that location updating strategies of databases of moving objects are just suitable for the point-like objects, the paper proposes a new location updating strategy for specific space-time. When the moving object is in a specific range where the environmental object is, MOD will view that the moving object has been in the location information of updated MOD. The location updating strategy can more effectively reflect the complex semantics and topological relations between moving objects and the environment. Besides, it to some extent compensates the shortage that the MOD cannot express face like objects after entity objects is abstracted zero dimension.3) Related algorithms of location context organization-moving preference pattern extraction algorithm. Aim at the location context computing in the future, the paper first put forward a trajectory interpolation algorithm according to the contradiction between continuity and discrete ways of location updating. The algorithm can shield the interference for the distance between trajectories caused by different locations updating strategies and sampling information granularity. And then, the paper introduces the Hausdorff distance and proposes the distance algorithm between spatio-temporal trajectories named IMHD-ST which measures differences between trajectories from temporal dimension and spatial dimension respectively and solves the problem of the basic distance measurement in the moving context organization. The paper then discusses semantics of the moving preference pattern. Based on these, the paper puts forward the moving preference pattern extraction algorithm named PPCG by adopting the mentioned distance algorithm between trajectories and density-based clustering algorithms. In the algorithm, it divides the moving preference pattern extraction into four steps which are partition, prune, clustering and generation. The partition is to merge similar straight sub trajectories to a straight trajectory so that the time costing can be decreased on the premise of limited loss of precision. The prune is to get rid of the noise in straight sub trajectories and keep similar ones. The classification is to reduce remained straight sub trajectories into complete trajectories and carry out clustering. The generation is finally to generate the moving preference trajectory in three-dimensional space-time. Thus, the algorithm accomplishes the extraction from discrete spatio-temporal location updating points of moving objects to continuous moving preference pattern.What’s more, in the partition step, it proposes MHD-S-based fixed threshold partitioning algorithm named MHDS-Partition. Without the increase of time complexity, the algorithm can effectively find characteristic location points among temporal trajectories and improve precision and simplicity of trajectory partitioning. In the generation step, it proposes moving preference trajectory generation algorithm based on scanning circles and vertical scanning lines. Besides, it gives the changing algorithm from static and offline process pattern to dynamic and online process pattern.4) Related algorithms of moving context organization-future location context computing algorithm. The future location context computing is the most important algorithm in future location context prediction. By comparing and analyzing existing methods and then combing the particularity of spatio-temporal location context information, the paper proposes a performance complementary algorithm based on integrated naive Bayes Classifier and linear regression. So the algorithm not only possesses the precision of the naive Bayes Classifier but also velocity of the linear regression to meet the needs of particularity in spatio-temporal location context information and real time in the moving information service.On the algorithm design, the paper first proposes the Boosted Dynamic Naive Bayes Classifier for MTP (BDNBCM). The Naive Bayes Classifier is famous for its high efficiency and integrated methods can optimize classifying performance to a great extent, so the two are combined to process dynamic changes and incomplete spatio-temporal location context information in dynamic preference trajectory classifying model, which can improve prediction precision of future spatio-temporal location. Besides, in the paper, it also gives chosen thoughts and related algorithms of the quantity k of the dynamic classifier and makes the computing cost least on the premise of meeting the needs of classifying requests. What’s more, the paper shows the condition density calculation method of the above classifying model parameters. Owning to the particularity of spatio-temporal location information, it is difficult to directly estimate related parameters of moving patterns or moving trajectories. So in the paper, it makes continuous moving preference trajectories as media and dynamically obtains corresponding parameters estimation of each location updating point in classified trajectories based on the interpolation algorithm.Besides, the paper does researches on regression-based future spatio-temporal location algorithms and proposes the regression algorithm of future location context. Based on future moving plans and current moving states obtained through classification-based calculation, the algorithm translates regression calculation into the query in the index of the time, which changes the method in previous references that moving patterns are fitted into a certain function which makes the time as the variable. Owning to the restriction of future moving plans and correction of current moving states, the algorithm performs better on prediction precision compared with ones without restriction and correction.The paper aims to realize exact computation of the high-level location context information such as the future spatio-temporal locations for users and does a serious of in-depth studies on it. What’s more, the paper proposes efficient and practical solutions for several related questions which are involved in the computation.The innovations of the paper are as follows:firstly, the psychological concept of "extrospection-introspection" is introduced and specified computation concept model of location awareness is built and then corresponding system model is proposed. Secondly, the paper puts forward and builds two-layers hierarchical model of the location context, which possesses advantages of ontology model and spatio-temporal data model; thirdly, the algorithm of Hausdorff-based three dimensional spatio-temporal (two dimensional plane and one dimensional time) trajectory similarity is proposed, in which two dimension is plane and one; Fourthly, it puts forward the mobile preference pattern extraction method which is based on density clustering; fifth, it proposes an algorithm of future location context which combines integrated Naive Bayes Classifier and linear regression.The main contribution of the paper is that it puts forward a systematic spatio-temporal location prediction method and related algorithms, which can more accurately and rapidly calculate the high-level position information such as future spatio-temporal location according to historical positions under the existing technical conditions.The paper makes detailed performances analysis for proposed algorithms and adopts simulated data sets or actual data sets to do detailed experiments at different parameters. A number of research results have been published on international meetings or national core journals and retrieved by El or SCI-E, which includes ICCSE2010, APCIP2010,《Journal of Computational information Science》 and 《China Communications》. Experiments show that algorithms in the paper can effectively solve related problems and possess complete functions and good performances compared with existing ones. Therefore, researches in the paper can provide great theories and applications for many key technologies on location-aware mobile information service.The real data sets come from data sets of global (including the Atlantic, the eastern Pacific, the western Pacific, the southern Pacific, the southern Indian Ocean and the northern Indian Ocean) historical hurricane trajectories which are provided by an American website, unisys.更多还原