搜索
第5章空间分析统计建模时间：星期四:1-2节(8:00-8:45,8:50-9:35)地点：3区2-117QQ群：空间分析应用建模(422017069)秦昆地理信息教研室武汉大学遥感信息工程学院空间分析应用建模武汉大学遥感信息工程学院硕士生教案201425.3时空轨迹数据分析PPA:PointPatternAnalysis3时空轨迹数据分析传统的GIS研究中，人们常常只关注于某一时刻对地理空间中的属性与空间信息的分析，这实际上只是描述了研究对象的一个快照，没有对连续的时态数据作专门处理。时间、空间和属性作为地理实体及地理现象本身固有的3个基本特征，是反映地理实体的状态和演变过程重要组成部分。4随着卫星定位技术、无线通信、跟踪检测设备及视频实时采集技术的快速发展，人们能够方便地以低廉的价格获得时空轨迹数据。例如，通过传感器遥测野生动物或者鱼类的活动，通过旅行日志记录交通工具的运动状况，通过条形码的检入检出了解物流的状况，通过信用卡刷卡记录或者电话通话记录来跟踪用户的位置，甚至通过互联网搜索某对象的相关事件来确定该对象的运动轨迹等。时空轨迹数据分析5时空轨迹数据：时空轨迹数据分析6时空轨迹数据分析空间对象的位置、属性都可能随着时间的推移而发生变化，人们不仅需要知道某一对象的属性和空间信息，更要了解该对象的来龙去脉，以便对其形成原因作出评估，对未来情况进行预测。时空轨迹数据恰能有效地表达时空对象的这些特性，通过分析各种不同对象的时空轨迹数据，有助于对人类行为模式、交通物流、应急疏散管理、动物习性、市场营销、计算几何以及模拟仿真等各个领域进行研究。7轨迹数据挖掘轨迹数据挖掘一般采用时空数据挖掘的基本理论、方法，同时又针对轨迹数据的特点，引入了一些特有的挖掘过程和方法，通常轨迹数据的知识发现过程包括三个阶段：轨迹重构(Reconstruction)知识抽取(Extraction)知识传递(Delivery)时空轨迹数据分析8时空轨迹数据分析(1)原始数据采集阶段：数据的采集包括轨迹数据本身的采集和轨迹所处的地理环境数据的采集。(2)数据预处理阶段：对应于时空数据的预处理阶段，通过对采集的数据进行冗余分析、特征提取，将其整理成便于数据挖掘操作的数据格式。(3)数据语义扩充阶段：根据具体应用，对轨迹数据、地理数据进行集成，并根据GIS等应用的要求，突出轨迹的时空语义等特征。(4)数据挖掘与知识发现阶段：采用数据挖掘的各种算法对处理后的数据进行挖掘和分析，并给出挖掘结果的时空语义分析和知识表达的合理解释。轨迹数据挖掘和知识发现的一般过程9时空轨迹数据分析在数据驱动的空间数据挖掘方法中，聚类分析和关联规则挖掘是两种重要的手段，其区别在于关联规则挖掘是一个异中求同的过程，而聚类分析则是同中求异的过程。通过聚类能够识别对象空间中稠密和稀疏的区域，将数据中的相似性与异常特征提取出来，从而发现全局分布模式和数据属性之间有趣的相关。这正符合人们对时空轨迹数据分析的要求，即在没有先验知识的情况下，先将数据聚合成不同的类，再对各类所代表的模式进行解读从而获得知识。时空轨迹数据时空轨迹(Trajectory)数据具有与其他数据不同的重要特征，主要体现在定义、模型和表达3个方面。它既是一种重要的时空对象数据类型，又是一种重要的信息源，因此其应用范围也非常广泛。定义：时空轨迹是移动对象的位置和时间的记录序列。时空轨迹数据分析抽象地来看，如上式所示，时空轨迹是时间到空间的映射，由一个以时间为自变量的连续函数o表示的，当给定某一个时刻t(t∈𝑅+)时，通过该函数可以得到t时刻该对象所处的d维空间𝑅𝑑(一般是二维或者三维空间)中的位置。时空轨的模型从定义中我们可以看出，时空轨迹是连续的，但通常用一组时空记录点序列，以离散的方式表示。例如，对时空对象的实际轨迹曲线进行采样，用得到的集合来代表时空轨迹。因此，时空轨迹的模型如下所示。时空轨迹数据分析式中：T代表一条轨迹，序列中每一个(d+1)元组(𝑋𝑛1,⋯,𝑋𝑛𝑑,𝑡𝑛)代表轨迹对象𝑡𝑛时刻在d维空间中的一个记录点，其空间位置是(𝑋𝑛1,⋯,𝑋𝑛𝑑)。例如，二维空间位置通常以(𝑥𝑛,𝑦𝑛)表示。时空轨迹数据的表达为了对时空轨迹进行比较，常常需要通过其模型重构时空轨迹，这就是时空轨迹数据的表达。轨迹表达的方法有很多种，结合Nanni对轨迹重构方法的分类方式，按照对轨迹记录点间对象运动过程的不同认识，时空轨迹数据的表达分为三个方面：基于全局回归模型的时空轨迹数据表达基于局部插值模型的时空轨迹数据表达基于领域知识模型的时空轨迹数据表达时空轨迹数据分析1基于全局回归模型的时空轨迹数据表达如果时空对象的运动方式整体上服从某一规则，那么可对该对象的所有记录点进行全局回归，用关于时间t的回归方程代表时空对象的轨迹。时空轨迹数据分析如右图所示，黑点和白点分别代表两条不同轨迹的记录点，两条直线是采用线性回归所得到的轨迹。由于这种模型过于简化，重构的时空轨迹也不与所有采样点重合，往往不能满足实际的需要。2基于局部插值模型的时空轨迹数据表达有时时空对象的运动方式并非全局一致，但可以假设在相邻记录点间的局部运动是服从特定规则的，不同的规则可以用不同的局部插值方法来表达。最常见的规则是相邻记录点间对象作匀速直线运动，该规则可以用线性插值方法表达。这种模型在时空轨迹模拟和分析中均被广泛使用，并且可以采用时空路径(Space-timePath)的方式来可视化表达。时空轨迹数据分析2基于局部插值模型的时空轨迹数据表达图𝑎是局部差值模型。图b是时空路径可视化方法示意图。时空路径表达方式将二维的空间和一维的时间整合到一个三维坐标系中表示，每个记录点的x、y坐标对应记录点的空间坐标，第三维坐标则对应记录点的时间值，图b中实线表示的是时空路径，虚线为时空路径在空间维上的投影。时空轨迹数据分析3基于领域知识模型的时空轨迹数据表达如果没有内插函数作为重构轨迹的依据，那么在任意相邻的记录时刻间，时空对象理论上可能在空间中的任何位置出现，但多数情况下各种领域知识会限制该对象出现的位置。例如，由于存在移动速度的限制，在某个记录时刻后，该时空对象只能存在于以该记录点为顶点的一个圆锥体内；或者由于道路的限制，对象只能沿交通网络运动；或者用户在运动过程中需要使用信息通讯技术，故受到网络覆盖区域的限制等等。时空棱镜(Space-timePrism)是一种很好的可视化表达方式。时空轨迹数据分析图a是基于领域知识的模型表达。图b是采用时空棱镜的可视化方法示意图。两相邻记录点的空间位置分别是𝑙1和𝑙2，记录时间分别为𝑡1和𝑡2，坐标表示方法与时空路径相同，记录点间的棱镜部分表示对象可能出现的时空范围，而该棱镜在空间维平面上的投影则表示对象的潜在活动区域。时空轨迹数据分析3基于领域知识模型的时空轨迹数据表达为了从时空轨迹数据中提取其相似性与异常，并发现其中有意义的模式，时空轨迹聚类分析方法被广泛采用。该方法的主要目的是试图将具有相似行为的时空对象划分到一起，而将具有相异行为的时空对象划分开来。其关键是根据时空轨迹数据的特点，设计与定义不同轨迹间的相似性度量。要将数据集划分成不同的类别，必须定义一种相似性的测度来度量同一类样本间的类似性和非同类样本间的差异性，而各种时空轨迹聚类方法间的主要区别也正是在于其相似性度量的不同。时空轨迹数据分析时空轨迹聚类方法两个对象之间的相似度(Similarity)是这两个对象相似程度的数值度量，相异度(Dissimilarity)是这两个对象差异程度的数值度量，距离(Distance)常被看作是相异度的同义词。因而，两个对象越类似，它们的相似度就越高，相异度就越低，距离越小。通常，相似度的取值范围是[0,1](0代表完全不相似，1代表完全相似)，而相异度(距离)的取值范围是[0,∞)(0代表完全相似，∞代表完全不相似)。相似度与相异度通常是可以互相转化的，所以使用“相似性度量”作为相似度和相异度(距离)的统称。时空轨迹数据分析相似度、相异度依照相似性度量所涉及的不同时间区间，可将现有的时空轨迹聚类方法划分为六类，如右图所示：时空轨迹数据分析时空轨迹聚类方法分类从右图中可以看出，这六类方法对于相似时间区间的要求是逐渐放松的，从要求时间全区间相似，到局部时间区间相似，最后到无时间区间对应相似。这种分类方式既能体现人们对时空轨迹相似性认知的多样性，又能反映时空轨迹相似性度量的发展过程。211时间全区间相似的聚类方法时空轨迹数据分析时间全区间相似的聚类方法将时空轨迹看作一个整体，并要求同一聚类中的轨迹在各个时刻都对应相似。这类方法所使用的相似性度量主要有：轨迹间欧氏距离不同于点与点之间的欧式距离，根据轨迹的特点重新定义轨迹间的欧氏距离。最小外包矩形距离可以看作一种简化时空轨迹的方法。是将每条子轨迹用其最小外包矩形(MinimumBoundaryRectangle，MBR)表示。221.1轨迹间欧氏距离时空轨迹数据分析轨迹间欧氏距离和点与点的欧氏距离有所不同。它首先将轨迹用相同维度的坐标向量表示，然后计算每一个时刻上对应两点的欧式距离，再对这些距离进行综合(如求和，求平均值、最大值或者最小值)，就可以得到轨迹间欧式距离。在二维空间中，轨迹间欧式距离公式为：式中：R、S分别表示两条轨迹，记录点数均为n；Eu(R,S)为轨迹R、S间的欧式距离；𝑟𝑖、𝑠𝑖分别表示轨迹R、S上第i个记录点；𝑟𝑖,𝑥、𝑟𝑖,𝑦、𝑠𝑖,𝑥、𝑠𝑖,𝑥分别表示记录点𝑟𝑖、𝑠𝑖的x坐标和y坐标；(dist(𝑟𝑖、𝑠𝑖)表示记录点𝑟𝑖和𝑠𝑖间的欧式距离。231.1轨迹间欧氏距离时空轨迹数据分析轨迹间欧氏距离计算费时，为了提高效率，有学者提出通过离散傅里叶变换和离散小波变换来降维的近似办法，还有提出提出了一种名为APCA(自适应逐段常量近似)的近似方法，但是这些方法都不能应用于采样率不同或者尺度不同的轨迹数据。采样率不同：先将轨迹分段线性表示，然后内插重采样，再计算轨迹间欧氏距离。尺度不同：先对轨迹进行全局缩放再计算轨迹间欧式距离。缺点：严格计算轨迹在每个时刻的对应距离，因此这类方法对噪声较敏感。241.2最小外包矩形距离时空轨迹数据分析首先将整条轨迹划分成一些相对平滑的轨迹区间，再将每条子轨迹用其最小外包矩形(MinimumBoundaryRectangle，MBR)表示，这样每条轨迹就变成了一个最小外包矩形的序列，如下图所示。图中虚线矩形框和实线矩形框分别代表虚线轨迹和实线轨迹的最小外包矩形序列，通过比较最小外包矩形序列即可度量时空轨迹间的相似性。251.2最小外包矩形距离时空轨迹数据分析根据计算的最小外包矩形距离如何判断相似性：（1）将各对外包矩形间的距离加权平均作为整体轨迹间的距离；（2）将最小外包矩形重叠部分的大小作为整条轨迹相似性度量；优点：使用最小外包矩形代替了轨迹区间，平滑了轨迹的细节，并在一定程度上缓解了噪声的影响。缺点：如何有效地将轨迹划分成平滑轨迹区间。这类时间全区间相似聚类方法的优点在于非常直观，易于理解，但那些不在一一对应时刻上完全相似的轨迹，则可能被遗漏。262全区间变换对应相似的聚类方法时空轨迹数据分析该类方法在全区间相似聚类方法的基础上，放松了对时间维的限制，即时空轨迹的时间维可以局部拉伸和缩放，只需要保证轨迹记录点的时间顺序，而不需要在一一对应的时刻上进行比较。这种方法忽略了轨迹度量间时间维尺度不同的问题。其中基于DTW(DynamicTimeWarping)距离的方法就是典型代表。DTW距离又称动态时间弯曲模型，能够克服欧式距离在时间轴的弱点，查找结果要优于欧氏距离，而且可采用下界函数提高计算速度和相似性测量精度。272DTW（动态时间弯曲）距离时空轨迹数据分析基于DTW距离的方法在保证时空轨迹对象记录点顺序不变的前提下，通过重复之前的记录点来完成时间维的局部缩放，以此求出轨迹间的最小距离作为相似性度量。具体计算公式：式中：