《第5章空间统计建模3线(轨迹)模式分析资料讲解》由会员分享，可在线阅读，更多相关《第5章空间统计建模3线(轨迹)模式分析资料讲解（66页珍藏版）》请在金锄头文库上搜索。
1、第5章空间分析统计建模,时间：星期四:1-2节(8:00-8:45,8:50-9:35) 地点：3区2-117 QQ群：空间分析应用建模(422017069),秦昆 地理信息教研室 武汉大学遥感信息工程学院,武汉大学遥感信息工程学院硕士生教案2014,2,5.3时空轨迹数据分析 PPA:PointPatternAnalysis,3,时空轨迹数据分析,传统的GIS研究中，人们常常只关注于某一时刻对地理空间中的属性与空间信息的分析，这实际上只是描述了研究对象的一个快照，没有对连续的时态数据作专门处理。 时间、空间和属性作为地理实体及地理现象本身固有的3个基本特征，是反映地理实体的状态和演变过程重要
2、组成部分。,5,时空轨迹数据：,时空轨迹数据分析,6,时空轨迹数据分析,空间对象的位置、属性都可能随着时间的推移而发生变化，人们不仅需要知道某一对象的属性和空间信息，更要了解该对象的来龙去脉，以便对其形成原因作出评估，对未来情况进行预测。 时空轨迹数据恰能有效地表达时空对象的这些特性，通过分析各种不同对象的时空轨迹数据，有助于对人类行为模式、交通物流、应急疏散管理、动物习性、市场营销、计算几何以及模拟仿真等各个领域进行研究。,7,轨迹数据挖掘,轨迹数据挖掘一般采用时空数据挖掘的基本理论、方法，同时又针对轨迹数据的特点，引入了一些特有的挖掘过程和方法，通常轨迹数据的知识发现过程包括三个阶段： 轨
3、迹重构(Reconstruction) 知识抽取(Extraction) 知识传递(Delivery),时空轨迹数据分析,8,时空轨迹数据分析,(1)原始数据采集阶段：数据的采集包括轨迹数据本身的采集和轨迹所处的地理环境数据的采集。 (2)数据预处理阶段：对应于时空数据的预处理阶段，通过对采集的数据进行冗余分析、特征提取，将其整理成便于数据挖掘操作的数据格式。 (3)数据语义扩充阶段：根据具体应用，对轨迹数据、地理数据进行集成，并根据GIS等应用的要求，突出轨迹的时空语义等特征。 (4)数据挖掘与知识发现阶段：采用数据挖掘的各种算法对处理后的数据进行挖掘和分析，并给出挖掘结果的时空语义分析和知
4、识表达的合理解释。,轨迹数据挖掘和知识发现的一般过程,9,时空轨迹数据分析,在数据驱动的空间数据挖掘方法中，聚类分析和关联规则挖掘是两种重要的手段，其区别在于关联规则挖掘是一个异中求同的过程，而聚类分析则是同中求异的过程。 通过聚类能够识别对象空间中稠密和稀疏的区域，将数据中的相似性与异常特征提取出来，从而发现全局分布模式和数据属性之间有趣的相关。这正符合人们对时空轨迹数据分析的要求，即在没有先验知识的情况下，先将数据聚合成不同的类，再对各类所代表的模式进行解读从而获得知识。,时空轨迹数据,时空轨迹(Trajectory)数据具有与其他数据不同的重要特征，主要体现在定义、模型和表达3个方面。它
5、既是一种重要的时空对象数据类型，又是一种重要的信息源，因此其应用范围也非常广泛。 定义：时空轨迹是移动对象的位置和时间的记录序列。,时空轨迹数据分析,时空轨的模型,从定义中我们可以看出，时空轨迹是连续的，但通常用一组时空记录点序列，以离散的方式表示。例如，对时空对象的实际轨迹曲线进行采样，用得到的集合来代表时空轨迹。因此，时空轨迹的模型如下所示。,时空轨迹数据分析,时空轨迹数据的表达,为了对时空轨迹进行比较，常常需要通过其模型重构时空轨迹，这就是时空轨迹数据的表达。 轨迹表达的方法有很多种，结合Nanni对轨迹重构方法的分类方式，按照对轨迹记录点间对象运动过程的不同认识，时空轨迹数据的表达分为
6、三个方面： 基于全局回归模型的时空轨迹数据表达 基于局部插值模型的时空轨迹数据表达 基于领域知识模型的时空轨迹数据表达,时空轨迹数据分析,1基于全局回归模型的时空轨迹数据表达,如果时空对象的运动方式整体上服从某一规则，那么可对该对象的所有记录点进行全局回归，用关于时间t的回归方程代表时空对象的轨迹。,时空轨迹数据分析,如右图所示，黑点和白点分别代表两条不同轨迹的记录点，两条直线是采用线性回归所得到的轨迹。由于这种模型过于简化，重构的时空轨迹也不与所有采样点重合，往往不能满足实际的需要。,2基于局部插值模型的时空轨迹数据表达,有时时空对象的运动方式并非全局一致，但可以假设在相邻记录点间的局部运动
7、是服从特定规则的，不同的规则可以用不同的局部插值方法来表达。 最常见的规则是相邻记录点间对象作匀速直线运动，该规则可以用线性插值方法表达。 这种模型在时空轨迹模拟和分析中均被广泛使用，并且可以采用时空路径(Space-timePath)的方式来可视化表达。,时空轨迹数据分析,2基于局部插值模型的时空轨迹数据表达,时空轨迹数据分析,3基于领域知识模型的时空轨迹数据表达,如果没有内插函数作为重构轨迹的依据，那么在任意相邻的记录时刻间，时空对象理论上可能在空间中的任何位置出现，但多数情况下各种领域知识会限制该对象出现的位置。 例如，由于存在移动速度的限制，在某个记录时刻后，该时空对象只能存在于以该记
8、录点为顶点的一个圆锥体内；或者由于道路的限制，对象只能沿交通网络运动；或者用户在运动过程中需要使用信息通讯技术，故受到网络覆盖区域的限制等等。 时空棱镜(Space-timePrism)是一种很好的可视化表达方式。,时空轨迹数据分析,时空轨迹数据分析,3基于领域知识模型的时空轨迹数据表达,为了从时空轨迹数据中提取其相似性与异常，并发现其中有意义的模式，时空轨迹聚类分析方法被广泛采用。 该方法的主要目的是试图将具有相似行为的时空对象划分到一起，而将具有相异行为的时空对象划分开来。其关键是根据时空轨迹数据的特点，设计与定义不同轨迹间的相似性度量。 要将数据集划分成不同的类别，必须定义一种相似性的测
9、度来度量同一类样本间的类似性和非同类样本间的差异性，而各种时空轨迹聚类方法间的主要区别也正是在于其相似性度量的不同。,时空轨迹数据分析,时空轨迹聚类方法,两个对象之间的相似度(Similarity)是这两个对象相似程度的数值度量，相异度(Dissimilarity)是这两个对象差异程度的数值度量，距离(Distance)常被看作是相异度的同义词。 因而，两个对象越类似，它们的相似度就越高，相异度就越低，距离越小。 通常，相似度的取值范围是0,1(0代表完全不相似，1代表完全相似)，而相异度(距离)的取值范围是0,)(0代表完全相似，代表完全不相似)。 相似度与相异度通常是可以互相转化的，所以使
10、用“相似性度量”作为相似度和相异度(距离)的统称。,时空轨迹数据分析,相似度、相异度,依照相似性度量所涉及的不同时间区间，可将现有的时空轨迹聚类方法划分为六类，如右图所示：,时空轨迹数据分析,时空轨迹聚类方法分类,从右图中可以看出，这六类方法对于相似时间区间的要求是逐渐放松的，从要求时间全区间相似，到局部时间区间相似，最后到无时间区间对应相似。这种分类方式既能体现人们对时空轨迹相似性认知的多样性，又能反映时空轨迹相似性度量的发展过程。,21,1时间全区间相似的聚类方法,时空轨迹数据分析,时间全区间相似的聚类方法将时空轨迹看作一个整体，并要求同一聚类中的轨迹在各个时刻都对应相似。这类方法所使用的
11、相似性度量主要有： 轨迹间欧氏距离 不同于点与点之间的欧式距离，根据轨迹的特点重新定义轨迹间的欧氏距离。 最小外包矩形距离 可以看作一种简化时空轨迹的方法。是将每条子轨迹用其最小外包矩形(MinimumBoundaryRectangle，MBR)表示。,22,1.1轨迹间欧氏距离,时空轨迹数据分析,轨迹间欧氏距离和点与点的欧氏距离有所不同。它首先将轨迹用相同维度的坐标向量表示，然后计算每一个时刻上对应两点的欧式距离，再对这些距离进行综合(如求和，求平均值、最大值或者最小值)，就可以得到轨迹间欧式距离。在二维空间中，轨迹间欧式距离公式为：,23,1.1轨迹间欧氏距离,时空轨迹数据分析,轨迹间欧氏
12、距离计算费时，为了提高效率，有学者提出通过离散傅里叶变换和离散小波变换来降维的近似办法，还有提出提出了一种名为APCA(自适应逐段常量近似)的近似方法，但是这些方法都不能应用于采样率不同或者尺度不同的轨迹数据。 采样率不同：先将轨迹分段线性表示，然后内插重采样，再计算轨迹间欧氏距离。 尺度不同：先对轨迹进行全局缩放再计算轨迹间欧式距离。 缺点：严格计算轨迹在每个时刻的对应距离，因此这类方法对噪声较敏感。,24,1.2最小外包矩形距离,时空轨迹数据分析,首先将整条轨迹划分成一些相对平滑的轨迹区间，再将每条子轨迹用其最小外包矩形(MinimumBoundaryRectangle，MBR)表示，这样
13、每条轨迹就变成了一个最小外包矩形的序列，如下图所示。 图中虚线矩形框和实线矩形框分别代表虚线轨迹和实线轨迹的最小外包矩形序列，通过比较最小外包矩形序列即可度量时空轨迹间的相似性。,25,1.2最小外包矩形距离,时空轨迹数据分析,根据计算的最小外包矩形距离如何判断相似性： （1）将各对外包矩形间的距离加权平均作为整体轨迹间的距离； （2）将最小外包矩形重叠部分的大小作为整条轨迹相似性度量； 优点：使用最小外包矩形代替了轨迹区间，平滑了轨迹的细节，并在一定程度上缓解了噪声的影响。 缺点：如何有效地将轨迹划分成平滑轨迹区间。 这类时间全区间相似聚类方法的优点在于非常直观，易于理解，但那些不在一一对应
14、时刻上完全相似的轨迹，则可能被遗漏。,26,2全区间变换对应相似的聚类方法,时空轨迹数据分析,该类方法在全区间相似聚类方法的基础上，放松了对时间维的限制，即时空轨迹的时间维可以局部拉伸和缩放，只需要保证轨迹记录点的时间顺序，而不需要在一一对应的时刻上进行比较。这种方法忽略了轨迹度量间时间维尺度不同的问题。 其中基于DTW(DynamicTimeWarping)距离的方法就是典型代表。 DTW距离又称动态时间弯曲模型，能够克服欧式距离在时间轴的弱点，查找结果要优于欧氏距离，而且可采用下界函数提高计算速度和相似性测量精度。,27,2DTW（动态时间弯曲）距离,时空轨迹数据分析,基于DTW距离的方法
15、在保证时空轨迹对象记录点顺序不变的前提下，通过重复之前的记录点来完成时间维的局部缩放，以此求出轨迹间的最小距离作为相似性度量。具体计算公式：,28,2DTW（动态时间弯曲）距离,时空轨迹数据分析,29,2DTW（动态时间弯曲）距离计算,时空轨迹数据分析,假设标准模板R为字母ABCDEF(6个)，测试模板T为1234(4个)。R和T中各元素之间的距离已经给出。,现假设题目满足如下的约束：当从一个方格(i-1,j-1)或者(i-1,j)或者(i,j-1)中到下一个方格(i,j)，如果是横着或者竖着的话其距离为d(i,j)，如果是斜着对角线过来的则是2d(i,j)。,g(2,2)计算为例。首先如果从
16、g(1,2)来算的话是g(2,2)=g(1,2)+d(2,2)=5+4=9，因为是竖着上去的。如果从g(2,1)来算的话是g(2,2)=g(2,1)+d(2,2)=7+4=11，因为是横着往右走的。如果从g(1,1)来算的话，g(2,2)=g(1,1)+2*d(2,2)=4+2*4=12.因为是斜着过去的。综上所述，取最小值为9.所有g(2,2)=9.,每一个红色的箭头表示最小值来源的那个方向,到此为止，我们已经得到了答案，即2个模板直接的距离为26.我们还可以通过回溯找到最短距离的路径，通过箭头方向反推回去,30,2DTW（动态时间弯曲）距离,时空轨迹数据分析,利用DTW距离进行相似性度量的改进： （1）使用DTW来度量不等长序列的相似性存在计算量过大的问题，而通过建立索引则能提高计算效率； （2）先用路径和速度曲线来表示轨迹，再用DTW度量距离； （3）将轨迹引入极坐标空间，通过角度与长度来表示轨迹，再计算轨迹间的DTW距离。 优点：DTW方法可较好地发现时间维局部缩放后才相似的时空轨迹，解决了采样率不同和时间尺度不一的问题。 缺点：计算DTW距离时，轨迹间的记录
