毕业设计（论文）-轨迹数据的空间概化.doc

中 国 矿 业 大 学 本科生毕业论 文 姓 名： 杨杨 光光 学 号： ： 08073757 学 院： 计计算机科学与技算机科学与技术术学院学院 专 业： 信息安全信息安全 论文题目： 轨轨迹数据的空迹数据的空间间概化概化 专 题： 指导教师： 职 称： 讲师讲师 2011 年 6 月 徐州 中国矿业大学毕业论文任务书 学院 计算机科学与技术学院 专业年级 信安 07-3 班 学生姓名 杨光 任任务务下下达达日日期期： 2011 年年 1 月月 10 日日 毕业论文日期：毕业论文日期：2011 年年 2 月月 21 日至日至 2011 年年 6 月月 15 日日 毕业论文题目：轨迹数据的空间概化毕业论文题目：轨迹数据的空间概化 毕业论文专题题目：毕业论文专题题目： 毕业论文主要内容和要求：毕业论文主要内容和要求： 设计轨迹数据空间概化的相关方法，减少轨迹数据的隐私信息。采用 c+或 c#实现 轨迹数据空间概化和聚类原型系统，以飓风数据为测试数据集，对所实现的方法进行测 试。 要求： （1）抽取轨迹数据关键点，根据空间相近性对抽取的关键点进行分组； （2）抽取每组内的中心点作为概化点； （3）将原始轨迹根据概化点生成概化轨迹，并对轨迹进行聚类； （4）实现轨迹数据空间概化和聚类的原型系统； （5）以飓风数据为测试数据集，对所实现的方法进行测试。 院长签字： 指导教师签字： 中国矿业大学毕业论文指导教师评阅书 指导教师评语（基础理论及基本技能的掌握；独立解决实际问题的能力；研究 内容的理论依据和技术方法；取得的主要成果及创新点；工作态度及工作量；总 体评价及建议成绩；存在问题；是否同意答辩等）： 成 绩： 指导教师签字： 年 月 日 中国矿业大学毕业论文评阅教师评阅书 评阅教师评语（选题的意义；基础理论及基本技能的掌握；综合运用所学知识 解决实际问题的能力；工作量的大小；取得的主要成果及创新点；写作的规范程 度；总体评价及建议成绩；存在问题；是否同意答辩等）： 成 绩： 评阅教师签字： 年 月 日 中国矿业大学毕业论文答辩及综合成绩 答 辩 情 况 回 答 问 题 提 出 问 题 正 确 基本 正确 有一 般性 错误 有原 则性 错误 没有 回答 答辩委员会评语及建议成绩： 答辩委员会主任签字： 年 月 日 学院领导小组综合评定成绩： 学院领导小组负责人： 年 月 日 摘 要 轨迹数据空间概化作为轨迹数据挖掘的一个重要研究内容，其目的是对轨迹数据进 行空间抽象，达到降维和隐私保护的目的。本文主要对轨迹数据空间概化方法和基于空 间概化的轨迹聚类技术进行研究。 首先，阐述了轨迹数据空间概化的背景和意义，总结了轨迹数据挖掘的内容，分析 了轨迹数据聚类研究方法并对其进行了分类，并介绍了轨迹数据的空间概化方法。 其次，编程实现了传统轨迹数据空间概化方法，并提出基于多约束的轨迹数据空间 概化方法。该方法首先根据轨迹点时间、位置、速度等多个特征约束提取出特征点。然 后对特征点进行分组，计算原始轨迹所经过的分组信息，连接分组区域中心点生成概化 轨迹。在上一步基础上，提出基于空间概化的轨迹聚类方法。该方法对整条概化轨迹进 行聚类，并针对不同聚类方法所得聚类结果进行相似性比较。 飓风数据实验表明，选择合适概化参数后，在概化轨迹满足聚类等数据处理要求的 基础上，数据维度大大降低，所要处理的轨迹点数大大减少，消耗的聚类时间大大减少。 同时，实验比较聚类结果的相似性表明，选择合适概化参数后，概化后的轨迹仍然保持 了良好的轨迹位置等特征。 最后，在理论研究的基础上，本文设计并实现了空间概化轨迹聚类分析系统 trajectory-generalization，可以轨迹数据集进行概化和聚类分析，能获得更具可视化效果 的轨迹数据空间概化和聚类结果。 关键词：轨迹空间概化；轨迹特征点；多约束；轨迹聚类；相似性 abstract as a hot topic of the trajectory data mining, spatial generalization of trajectory data is aimed at special abstraction of trajectory data, which is useful for dimensionality reduction and privacy protection. firstly, this paper represents the background and meaning of trajectory data clustering, and then summarizes the contents of trajectory data mining. after that, we analyze the trajectory clustering research methods and make a classification to these methods. at last, we discuss the method of spatial generalization of trajectory data. secondly, we design a program to test and verify the traditional method for spatial generalization of trajectory data, and then propose a new method with multiple constraints for that. the method firstly extracts feature trajectory points with multiple feature constraints, for example, time, position, speed, etc. then the method groups the feature points, and calculates the group information of which the origin trajectories pass. at last, we connect grouping regional center point in order to generating generalized trajectories. after the above steps, we propose the spatial generalization trajectory clustering method. the method clusters on the entire generalized trajectories, and make a comparison for various clustering results generated by different clustering methods. experiments on hurricane data show that the original data dimension is greatly reduced with the appropriate parameters chosen in the condition that generalized trajectories are satisfied with the requirements of clustering and the clustering time consumption is also greatly reduced. at the same time, the experiments on comparison of clustering results similarity show that after selecting the appropriate parameters, almost of trajectories remains good features of the trajectories such as the position information. finally, based on the research theory, this paper designs and achieves the primitive system of trajectory-generalization, which can do clustering analysis on trajectory data, and visualization results for trajectory data generalization and clustering. keywords: spatial generalization; characteristic points; multiple constraints; trajectory clustering; similarity 目目 录录 1 1 绪论绪论 1 1 1.1 研究背景与意义 .1 1.2 国内外研究现状 .2 1.3 论文主要的研究内容 .2 1.4 论文结构 .3 1.5 本章小结 .4 2 2 轨迹数据挖掘及空间概化方法轨迹数据挖掘及空间概化方法 5 5 2.1 轨迹数据挖掘概述 .5 2.2 轨迹数据挖掘研究内容 .5 2.3 轨迹数据聚类方法 .6 2.3.1 基于层次方法 .7 2.3.2 基于划分的方法 .7 2.3.3 基于密度的方法 .7 2.3.4 基于模型的方法 .7 2.3.5 基于网格的方法 .8 2.3.6 其他方法 .8 2.4 轨迹数据概化方法 .8 2.5 本章小结 .9 3 3 基于多约束的轨迹数据空间概化方法基于多约束的轨迹数据空间概化方法 1010 3.1 引言10 3.2 传统的轨迹数据空间概化方法 10 3.2.1 具有时间意识的轨迹特征点提取 10 3.2.2 将空间中的特征点分组 12 3.2.3 定位区域中心 15 3.2.4 概化轨迹的生成 16 3.3 轨迹数据的特性和基本定义 17 3.3.1 轨迹的几个特性 17 3.3.2 轨迹的基本定义 18 3.4 基于多约束的轨迹数据空间概化方法 19 3.4.1 具有多约束下的轨迹特征点提取 19 3.4.2 轨迹概化的其他步骤 22 3.5 实验及分析 22 3.5.1 实验数据及运行环境 22 3.5.2 提取轨迹特征点 23 3.5.3 特征点分组 25 3.5.4 概化点和概化轨迹生成 27 3.6 本章小结 29 4 4 基于空间概化的轨迹聚类方法基于空间概化的轨迹聚类方法 3030 4.1 引言 30 4.2 聚类算法的讨论 31 4.2.1 传统的聚类算法及其局限性 31 4.2.2 dbscan 算法描述及其实现 .31 4.3 基于空间概化的轨迹聚类 32 4.4 空间概化聚类同原始轨迹聚类相似性对比 33 4.5 实验及分析 34 4.5.1 实验数据及运行环境 34 4.5.2 实验分析 35 4.6 本章小结 41 5 5 轨迹数据的空间概化和聚类原型系统的设计与实现轨迹数据的空间概化和聚类原型系统的设计与实现 4343 5.1 系统架构概述 43 5.1.1 数据获取 43 5.1.2 数据预处理 43 5.2 系统的实现 44 5.2.1 系统结构 44 5.2.2 关键类结构 46 5.3 系统的运行 46 5.3.1 运行环境 46 5.3.2 输入数据 46 5.3.3 功能展示 47 5.4 本章小结 52 6 6 结论结论 5353 参考文献参考文献 5454 翻译部分翻译部分 5757 英文原文57 中文译文67 致致 谢谢 7575 中国矿业大学 2011 本科生毕业设计（论文） 第 1 页 1 绪论绪论 1.1 研究背景与意义研究背景与意义 移动设备例如手机、掌上电脑，嵌入式点子产品等已经广泛应用于人们的生活之中， 而且将越来越普及。现代的移动设备越来越多都具有 gps 功能，设备服务端可以通过移 动端为用户提供主动式、基于位置的服务，极大地方便了人们对于位置定位、路线识别 等服务的需求。服务提供商为用户提供这些服务的同时也收集到大量的位置数据，这些 数据作为宝贵的信息资源，记录了移动对象在某时刻的位置信息，这些数据传达了移动 对象在一定时间段内的运动轨迹，通过对这些数据的分析，可以得出一些共性的有价值 的模式，利用这些模式可以分析移动对象的日常生活习惯、活动轨迹，提供更好的主动 式信息供给、用户位置查询等服务。 itu-国际电信联盟1指出截至 2010 年底，全球移动电话注册数量达 52.8 亿，普及率 达 86.47%，2009 年底，该数据为 46.6 亿，普及率达为 67%，而在峰会第一阶段会议召开 之际（2003 年）普及率仅为 20%，移动蜂窝的快速腾飞出人意料。发展中国家的普及率 于 2008 年超过 50%，一些区域（欧洲和独联体国家）已达到 100%大关；并将在 2015 年 基本实现 100%的覆盖。这有可能带来全世界所有人对电话服务的获取。另一方面，手机 服务运营商通过各种定位技术如 gsm 和 umts，能更好更精确的提供计算一个用户位置 的能力，而各种移动标准技术的综合使用：配备 gps 的移动设备可以发送他们的轨迹给 服务提供者（欧洲伽利略卫星定位系统、中国的北斗卫星导航系统等都可以提供高精度 和高普及程度） ，wi-fi 和蓝牙设备可以作为一种用于室内定位的数据源，wi-max 能成为 户外定位的一种替代品，还有很多其他的移动轨迹数据源获取技术2。可见随着卫星，传 感器，rfid 和无线网络等技术的迅速发展，记录了海量的物体移动轨迹数据。例如，一 个零售商拥有 3000 个零售店，每天每个店销售 10000 件商品，每件商品在被卖掉之前平 均移动 10 次，这样每天就产生 30001000010=3 亿的数据，那一个月，一年的数据是 非常巨大的；一个城市每天的交通轨迹数据也是海量的。对于这些轨迹数据挖掘是现实 世界的实际需要驱动的： （1）城市交通方面：现在的很多出租、邮政和货运车辆都配备了 gps 设备，这些设 备以一定的频率向某些特定的管控中心定时发送自己的坐标。交通警察、公路运输管理、 快递公司等单位或部门通过将这些点按时间顺序连接起来就可得到车辆的运行轨迹，这 样可以保证车辆的安全和有效调度，以及对交通流量的分析等等。 （2）天气预报方面：气象局对于每次的台风都有记录，台风的风速、中心位置、中 心附近的风力、台风的等级都有详细的记录；根据历史的台风轨迹数据，预测未来的台 风轨迹，能减少很多的人民财富损失。 （3）煤矿安全方面：对于煤矿井下人员定位系统，在煤矿的普及率越来越高，而煤 矿人员定位系统长期运行后，也产生海量的轨迹数据，对这些海量的历史轨迹数据进行 分析，利用分析获得的规律指导今后的煤矿安全工作，具有重要的实际意义。 （4）其他：如通过动物运动轨迹，分析研究动物群居的习性；通过研究大超市里人 们的购物移动路线，分析研究购物者们的购物爱好，以便后来更好的布置购物场所；另 外对于定位服务、视频监控还有其他很多的现实应用都有轨迹数据挖掘的需求。 中国矿业大学 2011 本科生毕业设计（论文） 第 2 页 1.2 国内外研究现状国内外研究现状 轨迹数据挖掘是数据挖掘领域下一个新兴的研究方向，近几年才开始有较大的发展， 目前国内外研究的机构和学者还不是很多。国内研究轨迹数据挖掘的专家和研究机构主 要有：四川大学唐常杰教授领导的数据库与知识工程研究所，做了轨迹数据异常检测3、 4、轨迹预测5、6、序列模式挖掘7等方向的研究；中国人民大学孟小峰教授领导的网络 与移动数据管理实验室，做了移动数据库系统8和移动对象索引9等技术的研究；华中科 技大学李国徽教授；中国科学院软件研究所丁治明教授；台湾地区中央研究院李强教授、 曾新穆教授、彭文志教授和黄三义教授也做了些对轨迹数据挖掘的研究。 国外研究机构和专家相对比较多：在 han j.w. 教授领导下，美国伊利诺大学香槟校 区的数据挖掘实验室开展了 analysis of spatiotemporal、trajectory and traffic data 的相关 研究， ，并且取得了颇多成果，在轨迹模式挖掘、异常发现、轨迹聚类分析等多方面都有 较好的表现；意大利比萨大学的知识发现和传递实验室进行了从事移动数据分析 （mobility data analysis）相关方向的研究；还有 australias ict research centre of excellence，ibm china research lab，microsoft research asia，u.s. army research laboratory 等等研究机构也做了一些对轨迹数据挖掘的研究工作。 聚类分析已经有很长的历史，它在数据挖掘、机器学习等研究领域有着非常重要的 地位，然而轨迹数据聚类分析是近几年才热门起来。1999 年，scott gaffney10等人较早提 出了进行轨迹数据聚类研究，他们用回归模型组件组成的混合模型，采用基于 em 算法 的无监督学习方法进行聚类；2004 年，yifan li、jiawei han11等人提出移动对象聚类研 究；2006 年，yutaka yanagisawa12等人提出一种基于移动对象的形状和速度的多维度模 型进行轨迹聚类的方法；2007 年，jae-gil lee13等人提出一种基于 traclus 轨迹聚类 算法的框架，xiaolei li14提出用基于密度算法的 flowscan 算法来发现城市交通的热点道 路。2009 年，cheng chang15等人采用分段思想，通过多粒度的可视化来展示聚类结果， elio masciari16提出另外一种轨迹聚类框架，用字符串代替轨迹，采用字符串的编辑距离 来比较轨迹间的距离，elio masciari 还提出利用 pca 主成份分析17，将轨迹分割成多个 区域的序列，然后用傅里叶变换来比较轨迹的相似性。 可以看出，很多学者在轨迹聚类分析上做了大量的研究，但是目前这些方法大多还 存在如下几方面的缺点： （1）仅仅只对采样点的位置进行聚类分析，不能从全局的角度把握轨迹的特征、运 动趋势等信息。 （2）只考虑轨迹点的位置，没有考虑轨迹点的速度、方向、加速度因素。 （3）大部分方法对一整条轨迹作为一个整体来处理，忽略轨迹局部的相似特征，而 往往两条轨迹在整体上是不相似的。 （4）没有考虑移动对象运动时所在环境对其的影响。 （5）聚类结果不可靠性：对于同一个轨迹聚类算法，采用不同的参数设置结果有较 大的差异性；对于同一轨迹数据集，采用不同的轨迹聚类算法可能得到完全不同的结果。 中国矿业大学 2011 本科生毕业设计（论文） 第 3 页 1.3 论文主要的研究内容论文主要的研究内容 本文的主要研究内容包括以下几个方面： （1）研究轨迹数据的空间概化的方法 海量轨迹数据处理过程耗时太久，占用空间大。本文的轨迹数据空间概化方法能够 在保持数据原有位置特征的基础上对轨迹进行降维处理。轨迹的空间概化方法基于对轨 迹进行特征点提取。概化后的轨迹保留了物体基本的运动特征。轨迹概化的程度可以通 过参数设置来控制。 （2）研究基于空间概化的轨迹聚类方法 现有研究对轨迹聚类研究，主要是在完整的轨迹模型上进行聚类分析，而对于海量 数据的处理，完整的轨迹聚类消耗的时间非常大。本文先将原始轨迹进行概化处理，得 到概化轨迹。通过基于空间概化的轨迹聚类方法，使用概化处理后的轨迹进行聚类处理。 将结果同原始轨迹聚类处理得到的结果进行比较，验证了方法可行性。 （3）设计并实现空间概化轨迹聚类分析系统 在理论研究的基础上，本文设计并实现空间概化轨迹聚类分析系统，可以对轨迹数 据进行概化和聚类分析，能更方便的获得更具可视化效果的轨迹数据概化和聚类结果。 1.4 论文结构论文结构 下面给出论文的具体组织结构，本论文一共有六章，具体安排如下： 第一章：绪论。论述课题的选题背景与研究意义，介绍了国内外关于轨迹数据挖掘 的研究现状，重点讨论了轨迹数据聚类的研究情况，分析了该领域存在的技术难点以及 未来的发展趋势。 第二章：轨迹数据挖掘及空间概化方法。主要讨论轨迹数据挖掘的研究内容，重点 介绍了轨迹数据聚类的基本理论、过程和方法，以及一些轨迹数据聚类的基本概念和轨 迹概化的相关方法。 第三章：基于多约束的轨迹数据空间概化方法。首先编程实现了传统的轨迹数据空 间概化方法，在此基础上提出基于多约束的轨迹数据空间概化方法。该方法首先对轨迹 提取特征点，考虑轨迹点的位置、开放角、方向角、速率和速度等多个因素。在提取特 征点的基础上，对特征点进行分组。使用每个分组的中心点作为轨迹的概化点，生成 voronoi cell。最后，对原始轨迹路经分组信息计算，查找原始轨迹经过的一系列分组， 并用分组区域中心的连接来代替原始轨迹，达到轨迹数据的空间概化目的。通过飓风数 据实验对轨迹数据的空间概化方法进行了分析比较。 第四章：基于空间概化的轨迹聚类方法。为了验证前面章节中提出的轨迹数据空间 概化方法，提出了基于空间概化的轨迹聚类方法，方法使用概化处理后的轨迹作为实验 数据集，聚类算法针对轨迹特征，聚类元素为整条轨迹线段。聚类结束后，针对原始轨 迹聚类簇集合以及概化轨迹聚类簇集合进行结果的相似性比较。通过飓风数据实验对基 于空间概化的轨迹聚类方法进行了分析比较。 第五章：轨迹数据空间概化和聚类原型系统。在理论研究的基础上，本文设计并实 现了空间概化轨迹聚类分析系统 trajectory-generalization，可以对模拟交通数据、真实的 飓风运动和动物移动等数据进行概化和聚类分析，能更方便的获得更具可视化效果的轨 中国矿业大学 2011 本科生毕业设计（论文） 第 4 页 迹数据概化和聚类结果。 第六章：结论。对本研究课题作了总结和概括， 1.5 本章小结本章小结 本章主要介绍了本文的选题背景、国内外本体研究现状、本文的研究思路、研究内 容及组织结构。 中国矿业大学 2011 本科生毕业设计（论文） 第 5 页 2 轨迹数据挖掘及空间概化方法轨迹数据挖掘及空间概化方法 2.1 轨迹数据挖掘概述轨迹数据挖掘概述 数据挖掘18就是从大量数据中发现隐含的知识和规律。它既是一种知识获取技术， 又是一个数据处理过程。它是数据库研究、开发和应用最活跃的分支之一，是一个多学 科的交叉领域，它出现于 20 世纪 80 年代后期，90 年代有了突飞猛进的发展，近年来已 经取得了重大进展，开发出了许多新的数据挖掘方法、系统和应用。很多人把数据挖掘 作为另一个普遍使用的术语，从数据库中发现知识即 kdd（knowledge discovery in databases）19，这是从数据中提取有趣的并且以前未知的知识，用来提供战略决策支持。 随着卫星、网络、跟踪设备和视频监控等的发展，人们已经能够捕获大量移动物体的轨 迹数据，如车辆移动、动物移动、台风走向、人员移动等等轨迹数据。但是对于如此海 量的数据，人们却没有加以利用，而是仅仅记录了。这些轨迹数据是基于时间和空间的 序列数据，可以也应该通过轨迹数据仓库，发现新的有趣的知识20。轨迹数据与传统数 据相比，具有以下两方面的特点：一方面轨迹数据都与某一对象相关，轨迹数据中除包 含以字符、文字为特征的属性信息外，还包含以距离关系、 方向关系、拓扑关系为特征 的轨迹信息；另一方面是轨迹数据具有空间自相关性，即每一个事物都与其它事物相关， 但邻近事物间的相关性比距离较远的事物间的相关性要大得多21。这就使得轨迹数据挖 掘比传统数据挖掘更为困难，因此研发高效的轨迹数据挖掘技术是当前轨迹数据挖掘面 临的主要挑战。 2.2 轨迹数据挖掘研究内容轨迹数据挖掘研究内容 轨迹数据挖掘主要研究内容有如下几点： 1）轨迹的异常检测：异常检测在数据挖掘领域中比较流行，然而对于轨迹数据的异 常检测研究却严重缺乏，现在几乎还没有比较好的算法用于轨迹数据异常检测22。轨迹 数据挖掘异常（离群）检测，检测那些极不同的或与现有轨迹数据集不一致的轨迹数据。 目前主要异常检测算法有：通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配， 进而检测异常轨迹3；文献4提出的轨迹向量度量方法可以有效检测出轨迹点和轨迹分段 在空间位置和轨迹方向上的离群性，通过挖掘离群轨迹点探测离群轨迹，并且通过 grid 空间划分法，提高算法的运行率；xiaolei li22等人提出的 roam 移动对象异常检测方法， 将离散模式的轨迹片段进行特征分析，组成一个多层次的特征空间，提出一个通用的， 基于分类器的结构化、多层次的有效学习的检测办法；jae-gil lee23等人提出基于 traod 算法的的异常轨迹检测框架，先将轨迹分成线段集，然后通过检测异常线段来检 测异常轨迹。文献24对移动对象轨迹数据流的异常检测做了一定的研究，它用局部连续 性特征对数据流进行局部聚类得到局部聚类簇，然后通过有效的剪枝策略进行异常监测。 2）轨迹模式发现：fosca giannotti25等人最早提出轨迹模式挖掘研究，以移动对象的 轨迹模式挖掘为示例，朝着序列模式挖掘这个方向研究，并且简化了轨迹模式挖掘在空 中国矿业大学 2011 本科生毕业设计（论文） 第 6 页 间和时间域下的描述。唐常杰7等人提出了 partspan 并行轨迹模式挖掘算法，该算法受时 间约束，通过前缀投影办法分解搜索空间来减少候选轨迹序列，引入并行策略将并行计 算分解为数据制定和任务制定计算，再通过特定的候选策略来有效的挖掘轨迹模式。文 献26通过弗里歇距离来找最长公共子轨迹，然后再对子轨迹进行聚类分析得到轨迹模式。 jiong yang27等人提出一种基于 min-max 属性认证的轨迹模式挖掘算法-trajpattern。文献 28对轨迹周期性模式挖掘做了定义，提出了 ptv 算法用于发现轨迹的周期性模式，并将 此用于周期预测。文献29提出了单一移动体在不同时间粒度的时空序列下的周期性模式， 它首先通过密度聚类找出关键地点，然后对关键地点进行相似性匹配、运行模式等研究。 3）轨迹知识发现：从地理数据里发现知识是近年来一直开放研究的邻域30，但对于 时空模式知识发现这是一个坚实的起点，然而在数据挖掘研究领域的专家们对很多时空 地理概念不是非常的了解，所以研究进展不是非常的快，即便如此，在轨迹知识发现研 究领域，近年来还是有不少成果。文献31提出了一种通用的上下文感知的轨迹数据挖掘 框架，该框架能通过额外的地理信息来增强轨迹信息，当然这些信息是应用领域需要的 信息。文献32也提出在轨迹数据中加入语义信息，使得在不同的应用领域内轨迹数据分 析更加方便，该方法是一种通用的方法并不限定某个具体的应用领域。文献33提出用户 驱动的语义轨迹数据挖掘。城市热点道路（交通流量大的道路）发现一直城市规划部门、 交通部门以及房地产商们非常需要的，但是一直没有很好的办法去发现它，由 xiaolei li14提出的基于密度算法的 flowscan 算法，在效率和效果上都能较好的发现热点道路， 该方法不是以车辆等移动对象为聚类目标，而是通过移动对象的共同道路段来聚类发现。 文献34提出一种基于密度聚类的，从轨迹里发现感兴趣的地点。文献35对移动通信方面 的轨迹数据进行行为发现挖掘。文献36通过利用正式的本体论和推理机来加强原始轨迹 的语义信息，然后再进行移动行为发现。 4）轨迹分类：根据轨迹数据的标签和其他特性，将轨迹数据分成不同的几类。jae- gil lee37等人提出 traclass 轨迹特征生成框架，这种框架通过轨迹分段产生层次特征， 然后分别用基于区域和基于轨迹的办法来进行分类。文献38提出一种在移动对象数据库 (mod)里进行轨迹投票的轨迹分类方法，该投票是基于局部轨迹相似性来完成，并且在 包括时间在内的三维轨迹数据实验下有较好的表现。文献39提出一种基于神经网络学习 的算法，用于轨迹分类。 5）轨迹的预测：anna monreale40等人提出了 wherenext 预测方法，该方法没有考虑 用户，只考虑所有移动对象在一个区域内历史移动动作，运用轨迹模式挖掘来预测移动 对象的下一个位置。文献28提出用 ptv 算法进行周期性预测。 6）轨迹的聚类分析：本文将在下一小节重点介绍轨迹的聚类分析。 2.3 轨迹数据聚类方法轨迹数据聚类方法 聚类分析研究已经有很长的历史，几十年来，它的重要性以及与其他研究方向的交 叉特点早已得到人们的肯定。聚类是模式识别、数据挖掘等研究方向的重要研究内容之 一，在识别数据内在的结构方面具有极其重要的作用。聚类主要应用于模式识别中的字 符识别、语音识别等，机器学习中的聚类算法应用于机器视觉和图像分割，图像处理中 中国矿业大学 2011 本科生毕业设计（论文） 第 7 页 聚类用于信息检索和数据压缩。聚类的另一个主要应用是时空数据库应用(gis 等) 、多 关系数据挖掘、序列和异类数据分析等。此外，聚类还应用于统计科学，对考古学、生 物学、地质学、心理学、地理学以及市场营销等研究也都有重要作用41。 轨迹数据的聚类分析是时空数据库应用领域下的重要研究方向。轨迹聚类的目标是 在轨迹数据库中寻找那些具有相似运动模式的轨迹，通过对轨迹内部特征信息和运动模 式的分析，确定轨迹间的相似程度，然后将相似程度较高的轨迹归为一类。近年来，有 很多学者对轨迹聚类进行了研究，比较有代表性的算法有：k- means，birch，dbscan，optics，sting 等13。根据这些算法的不同特点又可以 分为：层次聚类方法、划分聚类方法、基于密度的聚类方法、基于网格的聚类方法和其 他方法。 2.3.1 基于层次方法基于层次方法 这类方法对给定数据对象集合进行层次分解，它又分为分裂层次聚类与凝聚层次聚 类。分裂层次聚类是自顶向下的策略，首先把所有对象看作一个聚类，然后递归的细分 成越来越小的聚类，直至达到某个终结条件为止；凝聚层次聚类正好相反，是自底向上 的策略，首先将每一个对象视为一个聚类，然后逐渐合并它们，直到满足某个条件才停 止。著名的层次方法有 cure 算法和 birch 算法等。li11提出一种基于微簇的实时自适 应聚类方法用于移动对象，该方法基于层次聚类思想，先将相近的对象聚合为一个微聚 类簇，然后对各个微簇当做独立个体进行再次聚类。 2.3.2 基于划分的方法基于划分的方法 给定一个有 n 个对象数据集，同时给定要构建的划分的数目 k ( k 。一个物体在时间上连续的位置就叫做轨迹。 轨迹数据的产生来源于现代跟踪技术。二维空间和三维时空1819中的线条轨迹的直 观展示，不能很好的应用于轨迹数据：由于标志之间的杂乱和重叠，这种显示方法是不 可行的。因此，有必要应用数据抽象方法，该方法在文献42中被详细定义为隐藏数据的 过程。在制图和地理可视化中有类似的一个概念，叫做制图综合4345。对于现有的制图 综合方法的研究发现，这种方法能够对轨迹进行适当的聚集概化，即将多个对象放在一 起，作为一个单位的代表。 制图综合过程由一组基本操作组成，它们可以简单地分为以下 3 类： （1）选择(selection)操作：从源数据集中确定代表性对象的子集。 （2）简化(simplification)操作：确定一个对象的哪些部分应该被显示。在这个过程中， 一个重要的因素是保持简化后对象和源对象的相似性以及拓扑关系的维持。 （3）标记化(tokenization)和合并(amalgamation)操作：对于那些较为重要的对象，如 果在制图综合后太小以至于不易辨认时，需要用一个可见的标记来代替。 此外，可能也需要将几个对象合并为一个新对象，或者为了保证拓扑关系替代一些 对象。在整个制图综合过程中，第一步就是对象选择。在其后的简化标记化和合并操作 过程中所针对的对象都是由选择操作从数据库中选择出来的结果。因此，本文将重点放 到对空间数据库的选择操作，然后再考察同样的技术对简化标记化和合并操作的支持能 中国矿业大学 2011 本科生毕业设计（论文） 第 9 页 力。 在本文中，该对象是指轨迹或轨迹段。对于轨迹数据，概化可以减少数据的数量， 达到降维的目的，这对于海量轨迹数据的进一步处理是非常有帮助。同时，它不只是省 略了一些轨迹对象，同时将原始轨迹转化具有原始轨迹属性的代表概化轨迹。 针对轨迹数据概化问题，文献50提出了如下的轨迹数据概化方法。 轨迹数据的空间概化首先是从原始轨迹数据上提取特征点。特征点主要包括轨迹点 特征如拐点、速度等因素比较大的点，将这些点标记为特征点，以供下一步的利用。第 二步是将轨迹空间上的特征点进行分组，根据特征点空间位置以及其特征信息，将特征 点归到不同组中，以进行区域划分之用；第三步针对第二步的特征点分组信息，根据分 组中的所有轨迹特征点位置、速度等信息，分别对每个组找到其区域中心，得到概化点； 最后一步对原始轨迹路经分组信息计算，查找原始轨迹经过的一系列分组，并用分组区 域中心的连接来代替原始轨迹，达到轨迹数据的空间概化目的。轨迹概化的程度可以通 过参数设置来控制。 2.5 本章小结本章小结 本章非常详细地阐述了轨迹数据空间概化的背景和意义，总结了轨迹数据挖掘的有 关概念和研究内容，并对轨迹聚类方法进行了详细的分类，介绍了轨迹数据的空间概化 方法。 中国矿业大学 2011 本科生毕业设计（论文） 第 10 页 3 3 基于多约束的基于多约束的轨迹数据空间概化方法轨迹数据空间概化方法 3.1 引言引言 轨迹数据空间概化的目的就是对海量轨迹数据的降维，并且可以起到隐私保护的作 用。轨迹的空间概化方法基于对轨迹进行特征点提取。概化后的轨迹保留了移动对象基 本的运动特征。轨迹概化的程度可以通过参数设置来控制。 轨迹数据的空间概化首先是从原始轨迹数据上提取特征点。特征点主要包括轨迹点 特征如拐点、速度等因素比较大的点，将这些点标记为特征点，以供下一步的利用。第 二步是将轨迹空间上的特征点进行分组，根据特征点空间位置以及其特征信息，将特征 点归到不同组中，以进行区域划分之用；第三步针对第二步的特征点分组信息，根据分 组中的所有轨迹特征点位置、速度等信息，分别对每个组找到其区域中心，得到概化点； 最后一步对原始轨迹路经分组信息计算，查找原始轨迹经过的一系列分组，并用分组区 域中心的连接来代替原始轨迹，达到轨迹数据的空间概化目的。 海量轨迹数据处理过程耗时太久，占用空间大。对轨迹数据进行概化处理，保持其 基本空间特征，同时降低轨迹点的维度。此外，概化后的轨迹无法还原出原始轨迹，起 到了隐私保护的作用。 本文首先编程实现了传统的轨迹数据空间概化方法50，然后在该方法的基础上，提 出了基于多约束的轨迹数据空间概化方法。 3.2 传统的轨迹数据空间概化方法传统的轨迹数据空间概化方法 3.2.1 具有时间意识的轨迹特征点提取具有时间意识的轨迹特征点提取 概化过程的第一步是提取轨迹上的特征点，本文通过对轨迹上点的特征进行计算， 通过比较轨迹点的速度、拐角、运动趋势等特征，具有明显变化的点作为特征点，将轨 迹用一系列特征点表示，进而降低了计算的复杂度。 轨迹的特征点包括轨迹的起点和终点，明显的转折点，和明显的停滞点（在运动中 的暂停点）。如果一条轨迹上有连续的长直线，也有必要从这些区段上提取一些代表点。 否则，直线的区段就无法纳入生成 voronoi 单元格的生成点的考虑范围中，而且因此不能 生成具有代表性的概化结果（即，表示这些区段的概化轨迹可能偏离太多段的方向）。 如果一条轨迹上有一系列连续的点，它们的运动特征非常相似，空间距离也非常近，也 需要从这一系列点中选取特征点来作为这些点的代表。 提取轨迹的特征点，本节使用下面的算法： algorithm 1(a)：具有时间意识的轨迹特征点（：具有时间意识的轨迹特征点（key point finding with time- reference） input： -轨迹 t = (xi, yi, ti), 1i n, n2 , ti j + 1 /* there are points between the jth and kth points whose spatial positions are close to the jth point */ then compute dtime = tk-1 - tj if dtime minstopduration then /* the j-th point is a significant stop point */ let c = c(xj,yj,tj); let i = j; let j = k; go_to 3; else /* compute the average spatial position */ compute (xave, yave): xave = get_mean(xp), yave = get_mean(yp),jpk-1; /* find the closest point to the average position */ find m, jmk - 1 : spatial_distance(xm, ym),(xave, yave) spatial_distance(xp,yp),( xave, yave), j p k-1; /* this will be a representative point among the points from jth to (k 1)th */ let j = m; end_if; 中国矿业大学 2011 本科生毕业设计（论文） 第 12 页 end_if; 8: compute aturn = angle_between_vectors(,); if aturn minangle then /* the j-th point is a significant turning point */ let c = c(xj, yj, tj); let i = j; let j = k; else let j = j + 1; /* skip the jth point */ end_if; go_to 3; 9: let c = c (xn, yn, tn); /* add the end point to c */ 10: return c; algorithm 1(a)的计算复杂性是轨迹上的点数的线性关系。n 个点轨迹的计算时间的 上限是的 m*n，其中 m 是半径为 mindistance 的圆中所包含的点的个数的最大值。 3.2.2 将空间中的特征点分组将空间中的特征点分组 将空间中的特征点分组是轨迹空间概化的关键。本章中 algorithm 2 对提取出的特征 点进行处理，按照其相互间的空间位置关系进行分组。该算法得到一系列特征点的分组， 属于同一组的特征点在空间上是紧凑的，也就是说，分组中可以有一个点来代表该组内 所有特征点。这样就把对轨迹的处理转化为对分组的处理，达到了降维的目的。 对空间中的点分组的传统方法是聚类。但是，现有的聚类方法不能满足本文的需求。 通用的聚类算法，如“k-均值”、“k-中心”要求所需的集群的数量被指定为一个参数。 但是，在本文中，群集的数量在事先无法得知的。同时，基于密度的聚类算法可以产生 任意形状和空间范围的群集，而本文需要这类群体的点，可以被封闭在某些用户设定大 小的凸多边形内，凸多边形的大小取决于用户所需的概化的程度。目前并没有发现任何 聚类算法能够根据用户需求，生产所需的空间范围的间集群。因此，本章执行下面的算 法： algorithm 2：将空间中的特征点分组：将空间中的特征点分组 input： -set of points p = xi,yi.1in； -maxradius-概化半径，一个分组所占区域的边长的期望值，也就是包含该组内所有 点的圆的半径。 output： 特征点分组的集合 r。 算法描述：算法描述： 1.find xmin, xmax, ymin, ymax: p p: xmin p. x xmax /* g is a grid with square cells covering the bounding rectangle of p. the size of a grid 中国矿业大学 2011 本科生毕业设计（论文） 第 13 页 cell is maxradius maxradius. the grid is used as a spatial index for a better efficiency of the algorithm. as point groups are built, their centroids (average points) are put in the grid cells according to their coordinates. */ 3. let r = ; /* this will be the resulting set of groups */ 4. for each p p put in proper group(p, r, g); end_for_each; 5. redistribute_points(p,r,g); 6. return r; procedure put_in_proper_group (point p, set r, grid g): 1. let c = get_closest_centroid(p, g); 2. if c = null then build g = group(p, p); /* the new group g consists of a sin