毕业设计（论文）-基于空间聚类的台风轨迹提取.doc

《毕业设计（论文）-基于空间聚类的台风轨迹提取.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-基于空间聚类的台风轨迹提取.doc（32页珍藏版）》请在三一文库上搜索。

1、中南大学本科生毕业论文（设计）题 目 基于空间聚类的台风轨迹提取 学生姓名 指导教师 学 院 信息物理工程学院 专业班级 测绘06级03班 摘 要空间聚类是空间数据挖掘与空间分析的重要手段之一，常用于揭示空间数据分布规律以及发现空间数据异常。现有的空间聚类方法多是针对空间点目标设计的，而实际应用中积累了大量的轨迹数据如台风轨迹、GPS导航数据、动物迁徙轨迹，对轨迹数据进行空间聚类分析有助于发现一些潜在的空间模式，具有重要的应用价值。本文针对台风轨迹数据，探究了一种基于分割-聚群思想的轨迹数据空间聚类方法。首先系统回顾了空间聚类以及轨迹聚类的相关研究工作；进而重点介绍了基于分割-聚群思想的空间轨

2、迹聚类方法-TRACLUS；最后，采用台风轨迹数据验证了TRACLUS算法在实际中的应用效果，并对其应用条件进行了分析，展望了空间轨迹聚类进一步研究的若干问题。关键词：空间数据挖掘，空间聚类，台风轨迹，TRACLUS算法AbstractSpatial clustering has played an important role in spatial data mining and spatial analysis. It can be used to discover the spatial association rules and spatial outliers in spatial

3、datasets. Existing spatial clustering methods are mainly designed for spatial point objects. Recent improvements in satellites and tracking facilities have made it possible to collect a large amount of trajectory data of moving objects. Examples include vehicle position data, hurricane track data, a

4、nd animal movement data. There is increasing interest to perform data analysis over these trajectory data. Discovering objects that have moved in a similar way is a meaningful data analysis task. Thus, an efficient spatial clustering algorithm for trajectory data should be developed. In this paper,

5、we test a new partition-and-group based method for clustering trajectories in the application of hurricane track data. The performances of the TRACLUS algorithm are fully performed. Some issues can be further improved are also summarized.Keywords: Spatial data mining, spatial clustering, hurricane t

6、rack data, TRACLUS algorithm目录摘 要IAbstractII目录III第一章 前言11.1研究背景与研究意义11.2本文研究内容21.3本文组织结构3第二章 相关研究回顾42.1 空间点数据聚类方法42.2 空间轨迹聚类方法5第三章 台风轨迹空间聚类算法73.1 算法概述73.1.1 问题描述73.1.2 TRACLUS算法83.2 台风轨迹分割93.2.1 特征点提取93.2.2 构造特征线段123.3 特征线段聚类133.3.1 基于密度的特征线段空间聚类133.3.2 簇的代表轨迹18第四章 实验分析224.1 实验设计224.2 台风轨迹提取结果224.3

7、结果分析24第五章 总结25参考文献26致谢28III中南大学本科生毕业论文 第1章 前言-第一章 前言1.1研究背景与研究意义随着科技的发展和社会的进步，人们在工作生活当中需要掌握和运用的各类数据越来越多。为了在不增加数据量的情况下获得更多有用信息，就要想办法从各类数据中充分挖掘隐含的、潜在的信息。基于这种想法，数据挖掘技术应运而生。数据挖掘(Data Mining)，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程1。空间信息技术尤其是对地观测技术的进步使得人们能更多的获得并使用空间数据。将数据挖掘应用于空间数据库，以便从中发现空间知识的理论和技术，产生了一个新

8、的研究领域：空间数据挖掘与知识发现。空间数据挖掘是指从空间数据库中抽取没有清楚表现出来的隐含的知识和空间关系，并发现其中有用的特征和模式的理论、方法和技术2-8。空间聚类是空间数据挖掘技术的一个重要组成部分，其目的是将空间数据库中的空间目标按照相似性分成一系列具有一定意义的簇，使得每个簇内目标相似，而簇间目标不同，主要用于对大量空间数据进行深入分析，显示空间数据分布规律，发现空间数据中的噪声数据。目前空间聚类技术已广泛用于多种应用，包括市场研究，模式识别，数据分析和图像处理等18-22。空间聚类技术虽然来源于传统的聚类分析技术，然而由于空间聚类的研究对象空间数据的独特性，传统的聚类分析方法虽可

9、以用于空间聚类分析，但存在明显的局限性。杂志中已经报道了大量的空间聚类算法，代表算法包括k-均值，BIRCH，DBSCAN，OPTICS和STING。但以前的研究主要是针对点数据的聚类。最近卫星定位技术和跟踪监测设施的发展，使我们能够收集大量的移动物体的轨迹数据。包括车辆的位置数据，飓风跟踪数据，和动物的迁徙数据。对这些轨迹数据进行数据分析的需求持续增长。一种具有代表性的数据分析工作是寻找具有相似移动方式的对象。这样，对于轨迹的一种有效聚类算法对这样的数据分析工作是必须的。现今存在的用于进行轨迹聚类的方法可分为整体轨迹聚类和局部轨迹聚类。整体轨迹聚类又分为基于概率和基于密度的聚类。局部轨迹聚类

10、的代表算法是分割-分组体系。然而整体轨迹聚类不能发现整体轨迹不同而部分相似的轨迹的相似部分（如例1）。例子1 图1-1中的五个轨迹有共同子轨迹，由矩形框内的粗箭头标示。然而，如果对这些轨迹进行整体聚类，由于它们完全朝不同方向移动我们就不能发现共同行为；这样就丢失了有用的信息。 图1-1：公共子轨迹的例子解决方案是将轨迹分割成一系列线段，然后将相似线段分组。这一体系称为分割-分组体系。该体系的主要优点是能从轨迹数据库中发现共同子轨迹。这就是为什么将轨迹分割成一系列线段的原因4-5。提取公共子轨迹非常有用，尤其在分析特殊区域，想要在那些区域中显示公共行为时。在真实应用中有很多例子，如：飓风的登陆预

11、测。飓风不仅影响当地的天气有时还会造成严重的生命财产损失，所以研究飓风在气候变化背景下的行为和变化有着重要的意义。气象学家在努力提高预测飓风登陆的时间和地点的能力。精确的登陆位置的预测更具重要性，因为它对减少飓风损失是至关重要的。气象学家会对飓风靠近海岸线的共同行为感兴趣，因为发现共同子轨迹有助于提高飓风登陆预测精度。1.2本文研究内容本文主要研究建立在分割-分组体系基础上的用于在台风轨迹集中提取台风公共子轨迹的新的轨迹聚类算法：TRACLUS，然后通过编程实现该过程，再对实验结果进行比较以验证其可行性并分析其优缺点。该聚类算法包含分割和分组两个阶段。第一阶段，用最小描述长度（MDL）准则实现

12、轨迹分割。第二阶段则是一基于密度的线段聚类算法。在分割阶段，每个轨迹被优化划分为一组线段。这些线段提供给下一个阶段。在分组阶段，相似的线段组成到一个簇里。线段簇往往是任意形状的，轨迹数据库也包含大量噪音。基于密度的聚类方法非常适合于轨迹聚类，因为它们能发现任意形状的簇并且能剔除噪音。1.3本文组织结构第1章 前言。阐述了本文的研究背景与研究意义，介绍了本文研究内容，并对本文的组织结构进行概述。第2章 空间聚类研究回顾。主要介绍了空间点数据聚类方法和空间轨迹数据聚类方法。第3章 轨迹聚类算法。提出第一阶段的轨迹分割算法，第二阶段的线段聚类算法。第4章 实验分析。分析实验结果并进行评价。第5章 总

13、结。总结了本文的主要工作，并指出了进一步的研究方向。28中南大学本科生毕业论文 第2章 空间聚类研究回顾-第二章 相关研究回顾聚类是把大量的物理或抽象对象按照相似性分成不同类别的过程。由聚类所生成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此相似，与其它簇中的对象则不同23。空间聚类是聚类分析研究的重要组成部分，但又不同于传统的聚类分析。基于“越近越相似”的地理学指导思想，空间聚类将数据属性划分为空间属性和非空间属性两部分，只有空间上邻近的实体聚在一起才有意义，而空间上邻近实体间的相似性又是通过非空间属性来度量的。此外空间聚类的研究目标也从点目标扩展到了线目标和面目标。同时传统聚类对数

14、据的各属性等同看待，也不考虑实体的形状，因此传统的聚类方法虽然可以用于空间聚类分析，却有一定的局限性9-16。2.1 空间点数据聚类方法大量空间聚类方法在文献内被报道。很难提供清晰的对簇的分类方法，因为这些类别可能重叠，一个方法可能有几个类别的特征。在一般情况下，主要空间聚类算法分为四类：划分的方法，层次的方法，基于密度方法，基于格网方法9： 划分的方法：给定包含n个对象的数据库或数据元组，用一分区方法构造K(，让。并返回第2步，否则停止。算法TRACLUS是基于密度的局部轨迹聚类方法，在该方法中，簇是被低密度区域分离的高密度区域，详细方法会在第三章提到。中南大学本科生毕业论文 第3章 轨迹聚

15、类算法-第三章 台风轨迹空间聚类算法 3.1 算法概述3.1.1 问题描述 想要在分割-分组体系的基础上创建高效聚类算法TRACLUS。先给定一系列轨迹，算法TRACLUS生成一系列簇每个簇对应一代表轨迹，其中轨迹，簇，代表轨迹定义如下。轨迹是一连串多维点。它表示为。在此，是一d维点。一个轨迹的长度不同于其他轨迹。轨迹称为的子轨迹。簇是一系列轨迹分割。轨迹分割是线段，其中和是从相同轨迹中所选点。属于相同簇的线段参照距离量测彼此临近。注意，轨迹可以属于多个簇，因为轨迹被分割成多个线段，然后对这些线段进行聚类操作。代表轨迹是和一般轨迹一样的一列点。它是代表簇中轨迹分割主要行为的假想轨迹。注意代表轨

16、迹指示共同子轨迹。下图显示分割分组体系中轨迹聚类的概略过程。 图3-1 分割分组体系轨迹聚类3.1.2 TRACLUS算法 下图显示轨迹聚类算法TRACLUS的提要。共有两个阶段，做子工作（第二、四、六行）时执行三个算法。下文中会分别解释这些算法。 算法1：TRACLUS算法（轨迹聚类）- TRACLUS算法（轨迹聚类）-输入：轨迹集输出：（1）簇集 （2）代表轨迹集算法： /*分割阶段*/01.对每个轨迹做图五；02.执行近似轨迹分割，应用结果得到线段集；03.积聚线段集到D集； /*分割阶段*/04.对D进行线段聚类，得到簇集；05.对每个簇做图十五；06.执行生成代表轨迹操作，得到代表轨

17、迹；-用在线段聚类中的距离函数由三部分组成：垂直距离，平行距离，角度距离。这些部分适合于模式识别领域的相似度量。在图3-2中直接说明。将三部分定义为定义13。 图3-2、线段间距离函数的三部分定义1.和之间的垂直距离定义如下 （1）定义2.和之间的平行距离定义如下 （2）是到和距离中较小值，是到和距离中较小值。定义3.和之间的角度距离定义如下 （3）另外， （4）其中，（5）定义两线段间距离如下：，其中权值、在本文中取1。3.2 台风轨迹分割3.2.1 特征点提取轨迹行为剧烈变化位置上的点就是特征点。轨迹在每个特征点处分割，每个分割由两相邻特征点间线段表示。这样，轨迹就被分割为一系列线段，称线

18、段为轨迹分割。下图显示轨迹和它的轨迹分割。 图3-3 轨迹及其轨迹分割理想的轨迹分割应包含两个可取的性质：准确性和简明性。准确性指轨迹和它的轨迹分割集间的差别应尽可能的小。简明性指轨迹分割的数目应尽可能的小。这两个性质相互矛盾，因此需要在两者间找到一个理想平衡点。可以采用广泛应用于信息理论的最小描述长度（MDL）准则来发现准确性和简明性间的理想平衡点。MDL包含两部分：L(H)和L(D|H)。其中，H指假设，D指数据。L(H)是假设的描述长度；L(D|H)是数据在假设的帮助下编码的描述长度。对解释D的最佳假设H是使L(H)和L(D|H)之和最小时的值。在轨迹分割难题中，假设与特定轨迹分割集相对

19、应。想找到理想的轨迹分割，就是找最佳分割，也就是用MDL准则找最佳假设。下图显示了L(H)和L(D|H)的构想。 图3-4 L(H)和L(D|H)假定轨迹和特征点集。然后，用公式6规划L(H)，表示线段的长度。所以，L(H)表示所有轨迹分割长度之和。 (6) (7)另一方面，用公式7规划L(D|H)。L(D|H)表示轨迹和它的轨迹分割间差异之和。对每个轨迹分割，将轨迹分割和属于分割的线段 间差异加起来。用垂直距离和角度距离之和衡量差异。可以不考虑平行距离，因为轨迹包围了它的轨迹分割。长度和距离是真值。在实践中，将真值x编码，假定精度为，使得编码数满足|x-|；08. 将前一点添加到特征点集；0

20、9. 开始索引=当前索引-1，长度=1； 10. 否则11. 长度=长度+112. 将结束点添加到特征点集-近似算法的时间复杂度为，n为轨迹长度。3.2.2 构造特征线段经过上一步骤的操作，每个轨迹对应一个特征点集。特征点集中从始点到终点，每两个相邻特征点可以构成一小线段，即特征线段。有时候特征点的提取也会不理想，如下图举例。假设使MDL花费最小的理想分割是。该算法不能发现准确方案，因为他在p4处停止扫描，在此大于。当然，该算法的精确性已经很高了。 图3-5 特征点提取3.3 特征线段聚类3.3.1 基于密度的特征线段空间聚类3.3.1.1 距离函数概述距离函数是三种距离的加权和。首先，垂直距

21、离主要衡量从不同轨迹提取的线段间的位置差异。其次，平行距离主要衡量从相同轨迹提取的线段间的位置差异，一个轨迹中两临近线段间的平行距离总是0。最后，角度距离衡量线段间方向差异。距离函数的对称性对于避免聚类结果的模棱两可很重要。如果距离函数是不对称的，不同聚类结果可以通过过程顺序获得。 3.3.1.2 基于密度聚类的概念 以下定义是基于密度聚类所需的概念。D表示所有线段集。改变本来为DBSCAN算法提出的点的定义为线段的。定义4. 属于D的线段的邻域定义为。定义5. 如果，那么属于D的线段称为核心线段。定义6. 如果并且 ，从线段到线段是直接密度可达的。定义7. 如果有一属于D的线段链使得从是直接

22、密度可达的，那么从线段到线段是密度可达的。定义8. 如果有一线段使得线段和线段对是密度可达的，那么对是密度连接的。定义9. 非空子集是密度连接集，如果c满足以下两个条件：（1） 对于任意属于c的、，对是密度连接的；（2） 对于任意属于D的、，如果属于c，对是密度可达的，那么属于c。 在下图描绘这些定义。密度可达性是直接密度可达性的转化终止，其关系是不对称的。只有核心线段是互相密度可达的。然而，密度连接性却是对称关系。让MinLns为3。粗线段表示核心线段。邻域由不规则椭圆表示。、和是核心线段；或对是直接密度可达的；对是密度可达的；、和都是密度连接的。 图3-6 密度可达与密度连接图3.3.1.

23、3 注意事项 因为线段有方向和长度，它们表现一些与基于密度聚类相关的有用特征。这里提及两个注意事项。1.线段的邻域的形状不是圆或球，它取决于数据，一般为椭圆或椭球。主要受核心线段和邻近线段的方向和长度影响。2.短线段能很大地降低聚类质量。线段的长度表示它的方向强度；也就是，如果线段短，它的方向强度就低。意思是如果其中一个线段很短，那么不管真实角度如何，角度距离都很小。在下图比较两组线段，只有的长度不同。（a）中通过对是密度可达的，（b）中则不是密度可达的。因为与相隔很远，（a）的结果是直接对立的。这样短线段可能导致聚类超出。 图3-7 短线段在聚类中的影响 这一问题的简单解决方案是通过调整分割

24、标准使聚类分割更长。这样，为了精确度而抑制分割。再具体点，为阻止分割，在图5第6行中对加一个小的常量。实验表明将轨迹分割长度提高2030%通常可以提高聚类质量。3.3.1.4 特征线段空间聚类算法现在描述对线段的基于密度的聚类算法。给定一线段集D,用算法产生簇集O。它需要两个算子和MinLns，并将簇定义为密度连接集。算法TRACLUS有很多特征与算法DBSCAN相同。与算法DBSCAN不同的是，不是所有密度连接集都能成为簇。需要考虑从中提取线段的轨迹的数目。这一数目典型的小于线段的数目。这里，检查定义于定义10的轨迹基数。定义10.簇的参与轨迹集由定义。表示提取的轨迹。这样称为簇的轨迹基数。

25、下图描述了线段聚类的算法。开始假定所有的线段都是未分类的。随着算法的进展，它们被分类为簇或噪音。算法由三步组成。第一步（1-12行），算法计算每个未分类线段L的邻域。如果L被判定为核心线段（7-10行），算法执行第二步去扩展簇（9行）。簇目前只包含。第二步（17-28行），算法计算核心线段的密度连接集。扩展簇步骤计算直接密度可达线段（19-21），并将它们添加到临时簇（22-24行）。如果新添加线段是未分类的，它就会为了进一步扩展而被添加到列，因为它可能是核心线段（25-26行）；否则它不会被添加到，因为已经知道它不是核心线段。第三步（13-16），算法检查每个簇的轨迹基数。如果它的轨迹基数低

26、于阀值，算法就会剔除相应的簇。 算法3： 线段聚类算法- 线段聚类算法-输入：（1）线段集， （2）两个算子和MinLns输出：簇集算法：01. 将簇的ID赋值为0；02. 将D内所有线段标为未分类；03. 对每个属于D的L,做04. 如果L是未分类的05. 计算；06. 如果07. 分配簇的ID给； 08. 将插入列；09. 扩展簇（，簇ID，）；10. 将簇的ID加为1；11. 其它12. 将L标为噪音；13. 将分配给簇；14. 对每个，做15. 如果16. 从簇集O中移除C； 17. 扩展簇（，簇ID，）18. 当时19. 让M为中的第一个线段；20. 计算 ；21. 如果22. 对每

27、个23. 如果X是未分类的或是噪音24. 将簇ID分配给X；25. 如果X是未分类的26. 将X插入列；27. 从列中移除M；28. -如果空间索引被应用，那么该聚类算法的时间复杂度是，其中n是数据库中线段总数。对于更高维（）则是。如果不用任何空间索引，将不得不扫描数据库中所有线段。这样，时间复杂度就是。如果使用像R树一样的合适索引，就能够通过横渡索引有效的找到邻域的线段。这样，时间复杂度就减小到。该算法很容易扩展以便支持带权的轨迹。该扩展在很多应用中都非常有用。距离函数不是米制的，因为它不服从三角不等式。即。这使得传统空间索引的直接应用很困难。一些技术可以用来对付这一难题。例如，可以采用常数

28、转换插入法将不服从三角不等式的距离函数转化为紧邻的另一个。3.3.2 簇的代表轨迹簇的代表轨迹描述属于簇的轨迹分割的大概移动。可以把它看做簇的模型。需要从簇中提取大量的移动信息使得该领域专家能够明白轨迹中的运动。这样，为了从轨迹聚类中得到充足的实际可能，就确实需要代表轨迹。下图说明生成代表轨迹的方法。代表轨迹是一列点。这些点是用扫描线方法确定的。当穿过簇的主轴方向线段扫描垂线时，计算撞击扫描线的线段数目。该数字只有当扫描线通过开始点或结束点时才改变。如果该数字大于或等于MinLns，计算这些关于主轴的线段的平均坐标并将之插入代表轨迹；否则，跳过临时点。同时，如果前面一点太靠近，跳过临时点平滑代

29、表轨迹。 图3-8 提取代表轨迹下面更详细的解释以上方法。为表示簇的主轴，在定义11定义平均方向向量。将向量相加得到方向向量，并将结果标准化。这是个给对平均方向向量贡献更多的较长向量的影响的探索法。在代表簇中每个线段的向量集上计算平均方向向量。定义11. 假定一向量集。的平均方向向量定义如公式（8）。这里，是的基数。 （8） 如上所述，计算关于平均方向向量的平均坐标。为使计算更容易，旋转坐标轴使X轴与平均方向向量平行。这里，要用到公式（9）中的旋转矩阵。角度可以通过平均方向向量和单位向量间的内部乘积来获得。如图3-9在XY坐标系中计算平均坐标后，它就会转回为XY坐标系中一点。 （9） 图3-9

30、. X和Y轴的旋转。下图显示代表轨迹生成算法。首先计算平均方向向量并且暂时旋转坐标轴（1-2行）。然后用旋转轴坐标对始点和终点进行分类（3-4行）。当按照已分类的顺序扫描始点和终点时，计算线段数并计算这些线段的平均坐标（5-12行）。 算法4：产生代表轨迹的算法- 代表轨迹生成算法-输入：（1）线段簇，（2），（3）平滑算子输出：的代表轨迹算法：01. 计算平均方向向量；02. 旋转坐标轴使X轴与平行；03. 让为簇中线段的始点与终点集； /*X 值表示X轴坐标*/04. 通过点的X值对中点分类；05. 对每个做 /*用扫描线（或平面）计算*/06. 让为包含点X值的线段数目；07. 如果08

31、. ：=和紧邻的前一点间X值的差别；09. 如果10. 计算平均坐标；11. 撤销循环得到点；12. 将 附加到的末尾；- 下面讨论参数和的数值选择问题： 先展示选择算子数值的探索法。采用熵原理。在信息原理中，回归与关于与给定概率分布联合的事件的不确定数目相关。如果所有输出可能相等，熵应最大。探索法是基于以下观察。在最差的聚类中，趋于一致。即，对于太小的，对于几乎所有线段都为1；对于太大的，对于几乎所有线段都为，其中是线段总数。这样回归就最大化了。相反，在好的聚类中，趋于偏斜。这样，熵变得较小。用公式（10）的熵定义。然后，找到使最小的值。理想的值可以通过模仿锻炼技术有效获得。 (10)其中， ， 然后展示选择算子数值的探索法。在理想的数值上计算的平均。这一操作导致没有附加花费，因为它能在计算时完成。然后，确定理想的值（）。这是正常的，因为应大于来发现有意义的簇。 用探索法估计的算子数值并不确定真的理想。然而，相信探索法在理想数值可能存在处提供合理的变动。该领域专家能够在估计值周围试用一些数值，并通过视觉检验选择最理想的一个。第四章中会证明该探索法的有效性。中南大学本科生毕业论文