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

《毕业设计（论文）轨迹数据的空间概化.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）轨迹数据的空间概化.doc（83页珍藏版）》请在三一办公上搜索。

1、中 国 矿 业 大 学本科生毕业论文姓 名： 杨 光 学 号： 08073757 学 院： 计算机科学与技术学院 专 业： 信息安全 论文题目： 轨迹数据的空间概化 专 题： 指导教师： 职 称： 讲师 2011年 6 月 徐州中国矿业大学毕业论文任务书学院 计算机科学与技术学院 专业年级 信安07-3班 学生姓名 杨光 任务下达日期： 2011年1月10日毕业论文日期：2011年2月21日至2011年6月15日毕业论文题目：轨迹数据的空间概化毕业论文专题题目：毕业论文主要内容和要求：设计轨迹数据空间概化的相关方法，减少轨迹数据的隐私信息。采用C+或C#实现轨迹数据空间概化和聚类原型系统，以飓

2、风数据为测试数据集，对所实现的方法进行测试。要求：（1）抽取轨迹数据关键点，根据空间相近性对抽取的关键点进行分组；（2）抽取每组内的中心点作为概化点；（3）将原始轨迹根据概化点生成概化轨迹，并对轨迹进行聚类；（4）实现轨迹数据空间概化和聚类的原型系统；（5）以飓风数据为测试数据集，对所实现的方法进行测试。院长签字： 指导教师签字：中国矿业大学毕业论文指导教师评阅书指导教师评语（基础理论及基本技能的掌握；独立解决实际问题的能力；研究内容的理论依据和技术方法；取得的主要成果及创新点；工作态度及工作量；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 指导教师签字： 年 月 日中国矿业大学毕

3、业论文评阅教师评阅书评阅教师评语（选题的意义；基础理论及基本技能的掌握；综合运用所学知识解决实际问题的能力；工作量的大小；取得的主要成果及创新点；写作的规范程度；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 评阅教师签字：年 月 日中国矿业大学毕业论文答辩及综合成绩答 辩 情 况提 出 问 题回 答 问 题正 确基本正确有一般性错误有原则性错误没有回答答辩委员会评语及建议成绩：答辩委员会主任签字： 年 月 日学院领导小组综合评定成绩：学院领导小组负责人： 年 月 日摘 要轨迹数据空间概化作为轨迹数据挖掘的一个重要研究内容，其目的是对轨迹数据进行空间抽象，达到降维和隐私保护的目的。本

4、文主要对轨迹数据空间概化方法和基于空间概化的轨迹聚类技术进行研究。首先，阐述了轨迹数据空间概化的背景和意义，总结了轨迹数据挖掘的内容，分析了轨迹数据聚类研究方法并对其进行了分类，并介绍了轨迹数据的空间概化方法。其次，编程实现了传统轨迹数据空间概化方法，并提出基于多约束的轨迹数据空间概化方法。该方法首先根据轨迹点时间、位置、速度等多个特征约束提取出特征点。然后对特征点进行分组，计算原始轨迹所经过的分组信息，连接分组区域中心点生成概化轨迹。在上一步基础上，提出基于空间概化的轨迹聚类方法。该方法对整条概化轨迹进行聚类，并针对不同聚类方法所得聚类结果进行相似性比较。飓风数据实验表明，选择合适概化参数后

5、，在概化轨迹满足聚类等数据处理要求的基础上，数据维度大大降低，所要处理的轨迹点数大大减少，消耗的聚类时间大大减少。同时，实验比较聚类结果的相似性表明，选择合适概化参数后，概化后的轨迹仍然保持了良好的轨迹位置等特征。最后，在理论研究的基础上，本文设计并实现了空间概化轨迹聚类分析系统Trajectory-Generalization，可以轨迹数据集进行概化和聚类分析，能获得更具可视化效果的轨迹数据空间概化和聚类结果。关键词：轨迹空间概化；轨迹特征点；多约束；轨迹聚类；相似性ABSTRACTAs a hot topic of the trajectory data mining, spatial g

6、eneralization 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

7、. 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 trajector

8、y 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 ori

9、gin 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

10、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

11、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

12、 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; multip

13、le constraints; trajectory clustering; similarity目 录1 绪论11.1研究背景与意义11.2国内外研究现状21.3论文主要的研究内容21.4论文结构31.5本章小结42 轨迹数据挖掘及空间概化方法52.1轨迹数据挖掘概述52.2轨迹数据挖掘研究内容52.3轨迹数据聚类方法62.3.1基于层次方法72.3.2基于划分的方法72.3.3基于密度的方法72.3.4基于模型的方法72.3.5基于网格的方法82.3.6其他方法82.4轨迹数据概化方法82.5本章小结93 基于多约束的轨迹数据空间概化方法103.1 引言103.2传统的轨迹数据空间概化方法

14、103.2.1具有时间意识的轨迹特征点提取103.2.2将空间中的特征点分组123.2.3定位区域中心153.2.4概化轨迹的生成163.3轨迹数据的特性和基本定义173.3.1轨迹的几个特性173.3.2轨迹的基本定义183.4基于多约束的轨迹数据空间概化方法193.4.1具有多约束下的轨迹特征点提取193.4.2轨迹概化的其他步骤223.5实验及分析223.5.1实验数据及运行环境223.5.2提取轨迹特征点233.5.3特征点分组253.5.4概化点和概化轨迹生成273.6本章小结294 基于空间概化的轨迹聚类方法304.1引言304.2聚类算法的讨论314.2.1传统的聚类算法及其局限

15、性314.2.2 DBSCAN算法描述及其实现314.3基于空间概化的轨迹聚类324.4空间概化聚类同原始轨迹聚类相似性对比334.5实验及分析344.5.1实验数据及运行环境344.5.2实验分析354.6本章小结415 轨迹数据的空间概化和聚类原型系统的设计与实现435.1系统架构概述435.1.1数据获取435.1.2数据预处理435.2系统的实现445.2.1系统结构445.2.2关键类结构465.3系统的运行465.3.1运行环境465.3.2输入数据465.3.3功能展示475.4本章小结526 结论53参考文献54翻译部分57英文原文57中文译文67致 谢751 绪论1.1研究背

16、景与意义移动设备例如手机、掌上电脑，嵌入式点子产品等已经广泛应用于人们的生活之中，而且将越来越普及。现代的移动设备越来越多都具有GPS功能，设备服务端可以通过移动端为用户提供主动式、基于位置的服务，极大地方便了人们对于位置定位、路线识别等服务的需求。服务提供商为用户提供这些服务的同时也收集到大量的位置数据，这些数据作为宝贵的信息资源，记录了移动对象在某时刻的位置信息，这些数据传达了移动对象在一定时间段内的运动轨迹，通过对这些数据的分析，可以得出一些共性的有价值的模式，利用这些模式可以分析移动对象的日常生活习惯、活动轨迹，提供更好的主动式信息供给、用户位置查询等服务。ITU-国际电信联盟1指出截

17、至2010年底，全球移动电话注册数量达52.8亿，普及率达86.47%，2009年底，该数据为46.6亿，普及率达为67%，而在峰会第一阶段会议召开之际（2003年）普及率仅为20%，移动蜂窝的快速腾飞出人意料。发展中国家的普及率于2008年超过50%，一些区域（欧洲和独联体国家）已达到100%大关；并将在2015年基本实现100%的覆盖。这有可能带来全世界所有人对电话服务的获取。另一方面，手机服务运营商通过各种定位技术如GSM和UMTS，能更好更精确的提供计算一个用户位置的能力，而各种移动标准技术的综合使用：配备GPS的移动设备可以发送他们的轨迹给服务提供者（欧洲伽利略卫星定位系统、中国的北

18、斗卫星导航系统等都可以提供高精度和高普及程度），Wi-Fi和蓝牙设备可以作为一种用于室内定位的数据源，Wi-Max能成为户外定位的一种替代品，还有很多其他的移动轨迹数据源获取技术2。可见随着卫星，传感器，RFID和无线网络等技术的迅速发展，记录了海量的物体移动轨迹数据。例如，一个零售商拥有3000个零售店，每天每个店销售10000件商品，每件商品在被卖掉之前平均移动10次，这样每天就产生30001000010=3亿的数据，那一个月，一年的数据是非常巨大的；一个城市每天的交通轨迹数据也是海量的。对于这些轨迹数据挖掘是现实世界的实际需要驱动的：（1）城市交通方面：现在的很多出租、邮政和货运车辆都配

19、备了GPS设备，这些设备以一定的频率向某些特定的管控中心定时发送自己的坐标。交通警察、公路运输管理、快递公司等单位或部门通过将这些点按时间顺序连接起来就可得到车辆的运行轨迹，这样可以保证车辆的安全和有效调度，以及对交通流量的分析等等。（2）天气预报方面：气象局对于每次的台风都有记录，台风的风速、中心位置、中心附近的风力、台风的等级都有详细的记录；根据历史的台风轨迹数据，预测未来的台风轨迹，能减少很多的人民财富损失。（3）煤矿安全方面：对于煤矿井下人员定位系统，在煤矿的普及率越来越高，而煤矿人员定位系统长期运行后，也产生海量的轨迹数据，对这些海量的历史轨迹数据进行分析，利用分析获得的规律指导今后

20、的煤矿安全工作，具有重要的实际意义。（4）其他：如通过动物运动轨迹，分析研究动物群居的习性；通过研究大超市里人们的购物移动路线，分析研究购物者们的购物爱好，以便后来更好的布置购物场所；另外对于定位服务、视频监控还有其他很多的现实应用都有轨迹数据挖掘的需求。1.2国内外研究现状轨迹数据挖掘是数据挖掘领域下一个新兴的研究方向，近几年才开始有较大的发展，目前国内外研究的机构和学者还不是很多。国内研究轨迹数据挖掘的专家和研究机构主要有：四川大学唐常杰教授领导的数据库与知识工程研究所，做了轨迹数据异常检测3、4、轨迹预测5、6、序列模式挖掘7等方向的研究；中国人民大学孟小峰教授领导的网络与移动数据管理实

21、验室，做了移动数据库系统8和移动对象索引9等技术的研究；华中科技大学李国徽教授；中国科学院软件研究所丁治明教授；台湾地区中央研究院李强教授、曾新穆教授、彭文志教授和黄三义教授也做了些对轨迹数据挖掘的研究。国外研究机构和专家相对比较多：在Han J.W. 教授领导下，美国伊利诺大学香槟校区的数据挖掘实验室开展了Analysis of Spatiotemporal、Trajectory and Traffic Data的相关研究，并且取得了颇多成果，在轨迹模式挖掘、异常发现、轨迹聚类分析等多方面都有较好的表现；意大利比萨大学的知识发现和传递实验室进行了从事移动数据分析（Mobility Data

22、Analysis）相关方向的研究；还有Australias ICT Research Centre of Excellence，IBM China Research Lab，Microsoft Research Asia，U.S. Army Research Laboratory等等研究机构也做了一些对轨迹数据挖掘的研究工作。聚类分析已经有很长的历史，它在数据挖掘、机器学习等研究领域有着非常重要的地位，然而轨迹数据聚类分析是近几年才热门起来。1999年，Scott Gaffney10等人较早提出了进行轨迹数据聚类研究，他们用回归模型组件组成的混合模型，采用基于EM算法的无监督学习方法进行聚类；

23、2004年，Yifan Li、Jiawei Han11等人提出移动对象聚类研究；2006年，Yutaka Yanagisawa12等人提出一种基于移动对象的形状和速度的多维度模型进行轨迹聚类的方法；2007年，Jae-Gil Lee13等人提出一种基于TRACLUS轨迹聚类算法的框架，Xiaolei Li14提出用基于密度算法的FlowScan算法来发现城市交通的热点道路。2009年，Cheng Chang15等人采用分段思想，通过多粒度的可视化来展示聚类结果，Elio Masciari16提出另外一种轨迹聚类框架，用字符串代替轨迹，采用字符串的编辑距离来比较轨迹间的距离，Elio Masci

24、ari还提出利用PCA主成份分析17，将轨迹分割成多个区域的序列，然后用傅里叶变换来比较轨迹的相似性。可以看出，很多学者在轨迹聚类分析上做了大量的研究，但是目前这些方法大多还存在如下几方面的缺点：（1）仅仅只对采样点的位置进行聚类分析，不能从全局的角度把握轨迹的特征、运动趋势等信息。（2）只考虑轨迹点的位置，没有考虑轨迹点的速度、方向、加速度因素。（3）大部分方法对一整条轨迹作为一个整体来处理，忽略轨迹局部的相似特征，而往往两条轨迹在整体上是不相似的。（4）没有考虑移动对象运动时所在环境对其的影响。（5）聚类结果不可靠性：对于同一个轨迹聚类算法，采用不同的参数设置结果有较大的差异性；对于同一轨

25、迹数据集，采用不同的轨迹聚类算法可能得到完全不同的结果。1.3论文主要的研究内容本文的主要研究内容包括以下几个方面：（1）研究轨迹数据的空间概化的方法海量轨迹数据处理过程耗时太久，占用空间大。本文的轨迹数据空间概化方法能够在保持数据原有位置特征的基础上对轨迹进行降维处理。轨迹的空间概化方法基于对轨迹进行特征点提取。概化后的轨迹保留了物体基本的运动特征。轨迹概化的程度可以通过参数设置来控制。（2）研究基于空间概化的轨迹聚类方法现有研究对轨迹聚类研究，主要是在完整的轨迹模型上进行聚类分析，而对于海量数据的处理，完整的轨迹聚类消耗的时间非常大。本文先将原始轨迹进行概化处理，得到概化轨迹。通过基于空间

26、概化的轨迹聚类方法，使用概化处理后的轨迹进行聚类处理。将结果同原始轨迹聚类处理得到的结果进行比较，验证了方法可行性。（3）设计并实现空间概化轨迹聚类分析系统在理论研究的基础上，本文设计并实现空间概化轨迹聚类分析系统，可以对轨迹数据进行概化和聚类分析，能更方便的获得更具可视化效果的轨迹数据概化和聚类结果。1.4论文结构下面给出论文的具体组织结构，本论文一共有六章，具体安排如下：第一章：绪论。论述课题的选题背景与研究意义，介绍了国内外关于轨迹数据挖掘的研究现状，重点讨论了轨迹数据聚类的研究情况，分析了该领域存在的技术难点以及未来的发展趋势。第二章：轨迹数据挖掘及空间概化方法。主要讨论轨迹数据挖掘的

27、研究内容，重点介绍了轨迹数据聚类的基本理论、过程和方法，以及一些轨迹数据聚类的基本概念和轨迹概化的相关方法。第三章：基于多约束的轨迹数据空间概化方法。首先编程实现了传统的轨迹数据空间概化方法，在此基础上提出基于多约束的轨迹数据空间概化方法。该方法首先对轨迹提取特征点，考虑轨迹点的位置、开放角、方向角、速率和速度等多个因素。在提取特征点的基础上，对特征点进行分组。使用每个分组的中心点作为轨迹的概化点，生成Voronoi Cell。最后，对原始轨迹路经分组信息计算，查找原始轨迹经过的一系列分组，并用分组区域中心的连接来代替原始轨迹，达到轨迹数据的空间概化目的。通过飓风数据实验对轨迹数据的空间概化方

28、法进行了分析比较。第四章：基于空间概化的轨迹聚类方法。为了验证前面章节中提出的轨迹数据空间概化方法，提出了基于空间概化的轨迹聚类方法，方法使用概化处理后的轨迹作为实验数据集，聚类算法针对轨迹特征，聚类元素为整条轨迹线段。聚类结束后，针对原始轨迹聚类簇集合以及概化轨迹聚类簇集合进行结果的相似性比较。通过飓风数据实验对基于空间概化的轨迹聚类方法进行了分析比较。第五章：轨迹数据空间概化和聚类原型系统。在理论研究的基础上，本文设计并实现了空间概化轨迹聚类分析系统Trajectory-Generalization，可以对模拟交通数据、真实的飓风运动和动物移动等数据进行概化和聚类分析，能更方便的获得更具可

29、视化效果的轨迹数据概化和聚类结果。第六章：结论。对本研究课题作了总结和概括， 1.5本章小结本章主要介绍了本文的选题背景、国内外本体研究现状、本文的研究思路、研究内容及组织结构。2 轨迹数据挖掘及空间概化方法2.1轨迹数据挖掘概述数据挖掘18就是从大量数据中发现隐含的知识和规律。它既是一种知识获取技术，又是一个数据处理过程。它是数据库研究、开发和应用最活跃的分支之一，是一个多学科的交叉领域，它出现于20世纪80年代后期，90年代有了突飞猛进的发展，近年来已经取得了重大进展，开发出了许多新的数据挖掘方法、系统和应用。很多人把数据挖掘作为另一个普遍使用的术语，从数据库中发现知识即KDD（Knowl

30、edge Discovery in Databases）19，这是从数据中提取有趣的并且以前未知的知识，用来提供战略决策支持。随着卫星、网络、跟踪设备和视频监控等的发展，人们已经能够捕获大量移动物体的轨迹数据，如车辆移动、动物移动、台风走向、人员移动等等轨迹数据。但是对于如此海量的数据，人们却没有加以利用，而是仅仅记录了。这些轨迹数据是基于时间和空间的序列数据，可以也应该通过轨迹数据仓库，发现新的有趣的知识20。轨迹数据与传统数据相比，具有以下两方面的特点：一方面轨迹数据都与某一对象相关，轨迹数据中除包含以字符、文字为特征的属性信息外，还包含以距离关系、 方向关系、拓扑关系为特征的轨迹信息；另

31、一方面是轨迹数据具有空间自相关性，即每一个事物都与其它事物相关，但邻近事物间的相关性比距离较远的事物间的相关性要大得多21。这就使得轨迹数据挖掘比传统数据挖掘更为困难，因此研发高效的轨迹数据挖掘技术是当前轨迹数据挖掘面临的主要挑战。2.2轨迹数据挖掘研究内容轨迹数据挖掘主要研究内容有如下几点：1）轨迹的异常检测：异常检测在数据挖掘领域中比较流行，然而对于轨迹数据的异常检测研究却严重缺乏，现在几乎还没有比较好的算法用于轨迹数据异常检测22。轨迹数据挖掘异常（离群）检测，检测那些极不同的或与现有轨迹数据集不一致的轨迹数据。目前主要异常检测算法有：通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配

32、，进而检测异常轨迹3；文献4提出的轨迹向量度量方法可以有效检测出轨迹点和轨迹分段在空间位置和轨迹方向上的离群性，通过挖掘离群轨迹点探测离群轨迹，并且通过Grid空间划分法，提高算法的运行率；Xiaolei Li22等人提出的ROAM移动对象异常检测方法，将离散模式的轨迹片段进行特征分析，组成一个多层次的特征空间，提出一个通用的，基于分类器的结构化、多层次的有效学习的检测办法；Jae-Gil Lee23等人提出基于TRAOD算法的的异常轨迹检测框架，先将轨迹分成线段集，然后通过检测异常线段来检测异常轨迹。文献24对移动对象轨迹数据流的异常检测做了一定的研究，它用局部连续性特征对数据流进行局部聚类

33、得到局部聚类簇，然后通过有效的剪枝策略进行异常监测。2）轨迹模式发现：Fosca Giannotti25等人最早提出轨迹模式挖掘研究，以移动对象的轨迹模式挖掘为示例，朝着序列模式挖掘这个方向研究，并且简化了轨迹模式挖掘在空间和时间域下的描述。唐常杰7等人提出了PartSpan并行轨迹模式挖掘算法，该算法受时间约束，通过前缀投影办法分解搜索空间来减少候选轨迹序列，引入并行策略将并行计算分解为数据制定和任务制定计算，再通过特定的候选策略来有效的挖掘轨迹模式。文献26通过弗里歇距离来找最长公共子轨迹，然后再对子轨迹进行聚类分析得到轨迹模式。Jiong Yang27等人提出一种基于min-max属性认

34、证的轨迹模式挖掘算法-TrajPattern。文献28对轨迹周期性模式挖掘做了定义，提出了PTV算法用于发现轨迹的周期性模式，并将此用于周期预测。文献29提出了单一移动体在不同时间粒度的时空序列下的周期性模式，它首先通过密度聚类找出关键地点，然后对关键地点进行相似性匹配、运行模式等研究。 3）轨迹知识发现：从地理数据里发现知识是近年来一直开放研究的邻域30，但对于时空模式知识发现这是一个坚实的起点，然而在数据挖掘研究领域的专家们对很多时空地理概念不是非常的了解，所以研究进展不是非常的快，即便如此，在轨迹知识发现研究领域，近年来还是有不少成果。文献31提出了一种通用的上下文感知的轨迹数据挖掘框架

35、，该框架能通过额外的地理信息来增强轨迹信息，当然这些信息是应用领域需要的信息。文献32也提出在轨迹数据中加入语义信息，使得在不同的应用领域内轨迹数据分析更加方便，该方法是一种通用的方法并不限定某个具体的应用领域。文献33提出用户驱动的语义轨迹数据挖掘。城市热点道路（交通流量大的道路）发现一直城市规划部门、交通部门以及房地产商们非常需要的，但是一直没有很好的办法去发现它，由Xiaolei Li14提出的基于密度算法的FlowScan算法，在效率和效果上都能较好的发现热点道路，该方法不是以车辆等移动对象为聚类目标，而是通过移动对象的共同道路段来聚类发现。文献34提出一种基于密度聚类的，从轨迹里发现

36、感兴趣的地点。文献35对移动通信方面的轨迹数据进行行为发现挖掘。文献36通过利用正式的本体论和推理机来加强原始轨迹的语义信息，然后再进行移动行为发现。 4）轨迹分类：根据轨迹数据的标签和其他特性，将轨迹数据分成不同的几类。Jae-Gil Lee37等人提出TraClass轨迹特征生成框架，这种框架通过轨迹分段产生层次特征，然后分别用基于区域和基于轨迹的办法来进行分类。文献38提出一种在移动对象数据库(MOD)里进行轨迹投票的轨迹分类方法，该投票是基于局部轨迹相似性来完成，并且在包括时间在内的三维轨迹数据实验下有较好的表现。文献39提出一种基于神经网络学习的算法，用于轨迹分类。5）轨迹的预测：A

37、nna Monreale40等人提出了WhereNext预测方法，该方法没有考虑用户，只考虑所有移动对象在一个区域内历史移动动作，运用轨迹模式挖掘来预测移动对象的下一个位置。文献28提出用PTV算法进行周期性预测。6）轨迹的聚类分析：本文将在下一小节重点介绍轨迹的聚类分析。2.3轨迹数据聚类方法聚类分析研究已经有很长的历史，几十年来，它的重要性以及与其他研究方向的交叉特点早已得到人们的肯定。聚类是模式识别、数据挖掘等研究方向的重要研究内容之一，在识别数据内在的结构方面具有极其重要的作用。聚类主要应用于模式识别中的字符识别、语音识别等，机器学习中的聚类算法应用于机器视觉和图像分割，图像处理中聚类

38、用于信息检索和数据压缩。聚类的另一个主要应用是时空数据库应用(GIS等) 、多关系数据挖掘、序列和异类数据分析等。此外，聚类还应用于统计科学，对考古学、生物学、地质学、心理学、地理学以及市场营销等研究也都有重要作用41。轨迹数据的聚类分析是时空数据库应用领域下的重要研究方向。轨迹聚类的目标是在轨迹数据库中寻找那些具有相似运动模式的轨迹，通过对轨迹内部特征信息和运动模式的分析，确定轨迹间的相似程度，然后将相似程度较高的轨迹归为一类。近年来，有很多学者对轨迹聚类进行了研究，比较有代表性的算法有：K-MEANS，BIRCH，DBSCAN，OPTICS，STING等13。根据这些算法的不同特点又可以分

39、为：层次聚类方法、划分聚类方法、基于密度的聚类方法、基于网格的聚类方法和其他方法。2.3.1基于层次方法这类方法对给定数据对象集合进行层次分解，它又分为分裂层次聚类与凝聚层次聚类。分裂层次聚类是自顶向下的策略，首先把所有对象看作一个聚类，然后递归的细分成越来越小的聚类，直至达到某个终结条件为止；凝聚层次聚类正好相反，是自底向上的策略，首先将每一个对象视为一个聚类，然后逐渐合并它们，直到满足某个条件才停止。著名的层次方法有CURE算法和BIRCH算法等。Li11提出一种基于微簇的实时自适应聚类方法用于移动对象，该方法基于层次聚类思想，先将相近的对象聚合为一个微聚类簇，然后对各个微簇当做独立个体进

40、行再次聚类。2.3.2基于划分的方法给定一个有 n个对象数据集，同时给定要构建的划分的数目 k ( k n)，划分方法先创建一个初始划分，然后迭代的采用划分方法重定位技术，通过对象在划分区间移动来改进划分。一个划分方法构建数据的k个划分，每个划分表示一个聚类。典型的划分算法如CLARANS算法、k-medoids算法和k-means算法等。2.3.3基于密度的方法 这类方法主要思想是：只要邻近区域的密度(对象的数目)超过某个阈值，就继续递归使用此方法聚类。代表性算法有DBSCAN 算法、GDBSCAN 算法、OPTICS 算法和DENCLUE算法等。Xiaolei Li14提出的基于密度算法的

41、FlowScan算法，在效率和效果上都能较好的发现热点道路，该方法不是以车辆等移动对象为聚类目标，而是通过移动对象的共同道路段来聚类发现。Jae-Gil Lee13等人提出一种基于TRACLUS轨迹聚类算法的框架，该框架先将轨迹通过MDL（最小编辑距离）进行分成线段，然后在这些线段里用改进的DBSCAN密度聚类算法进行聚类，该框架的一个主要优势在于能在一个轨迹数据库中发现公共子轨迹。2.3.4基于模型的方法 这类方法为每个聚类假设一个数学模型，试图为数据查找合适的数学模型。如Scott Gaffney10在1999年就提出了用回归模型组件组成的混合模型进行轨迹聚类，采用基于EM算法的无监督学习

42、办法进行聚类。2.3.5基于网格的方法正如前面提到的DBSCAN这样基于密度的算法，在高纬度情况下，在聚类效率方面它将面临崩溃的危险。为了改进效率，一种基于网格数据结构的聚类方法产生了。该方法采用一个多分辨率的网格数据结构将数据空间分成有限数目的单元，聚类效率不再依赖数据量而是单元数量，处理速度快。著名的有 STING算法(W. Wang, Yang, & Muntz, 1997)、 WaveCluster 算法(Sheikholeslami, Chatterjee, & Zhang, 1998)和 CLIQUE 算法(Agrawal, Gehrke, Gunopulos, & Raghava

43、n, 2005)等。2.3.6其他方法如Elio Masciari16提出另外一种轨迹聚类框架，他的思想是将轨迹表示成字符串，这个表示过程是用合适的区域划分策略来实现，然后比较两条轨迹的相似性就可以通过比较两个字符串的编辑距离的大小来判定。文献17利用PCA（主成份分析）将轨迹表示成多个区域的带注解的序列，然后轨迹的相似性比较就可以利用傅里叶变换后的轨迹序列比较来实现。2.4轨迹数据概化方法轨迹数据的空间概化方法是为了解决轨迹数据可视化的问题，也就是，记录某些运动物体（比如人，车或动物）在不同时刻的空间位置。位置记录的主要项目包括。一个物体在时间上连续的位置就叫做轨迹。轨迹数据的产生来源于现代

44、跟踪技术。二维空间和三维时空1819中的线条轨迹的直观展示，不能很好的应用于轨迹数据：由于标志之间的杂乱和重叠，这种显示方法是不可行的。因此，有必要应用数据抽象方法，该方法在文献42中被详细定义为隐藏数据的过程。在制图和地理可视化中有类似的一个概念，叫做制图综合4345。对于现有的制图综合方法的研究发现，这种方法能够对轨迹进行适当的聚集概化，即将多个对象放在一起，作为一个单位的代表。制图综合过程由一组基本操作组成，它们可以简单地分为以下3类：（1）选择(selection)操作：从源数据集中确定代表性对象的子集。（2）简化(simplification)操作：确定一个对象的哪些部分应该被显示。

45、在这个过程中，一个重要的因素是保持简化后对象和源对象的相似性以及拓扑关系的维持。（3）标记化(tokenization)和合并(amalgamation)操作：对于那些较为重要的对象，如果在制图综合后太小以至于不易辨认时，需要用一个可见的标记来代替。此外，可能也需要将几个对象合并为一个新对象，或者为了保证拓扑关系替代一些对象。在整个制图综合过程中，第一步就是对象选择。在其后的简化标记化和合并操作过程中所针对的对象都是由选择操作从数据库中选择出来的结果。因此，本文将重点放到对空间数据库的选择操作，然后再考察同样的技术对简化标记化和合并操作的支持能力。在本文中，该对象是指轨迹或轨迹段。对于轨迹数据，概化可以减少数据的数量，达到降维的目的，这对于海量轨迹数据的进一步处理是非常有帮助。同时，它不只是省略了一些轨迹对象，同时将原始轨迹转化具有原始轨迹属性的代表概化轨迹。针对轨迹数据概化问题，文献50提出了如下的轨迹数据概化方法。轨迹数据的空间概化首先是从原始轨迹数据上提取特征点。特征点主要包括轨迹点特征