第5章 空间统计建模 3 线(轨迹)模式分析ppt课件.pptx

第5章空间分析统计建模,时间：星期四:1-2节(8:00-8:45,8:50-9:35)地点：3区2-117QQ群：空间分析应用建模(422017069),秦昆地理信息教研室武汉大学遥感信息工程学院,武汉大学遥感信息工程学院硕士生教案2014,2,5.3时空轨迹数据分析PPA:PointPatternAnalysis,3,时空轨迹数据分析,传统的GIS研究中，人们常常只关注于某一时刻对地理空间中的属性与空间信息的分析，这实际上只是描述了研究对象的一个快照，没有对连续的时态数据作专门处理。时间、空间和属性作为地理实体及地理现象本身固有的3个基本特征，是反映地理实体的状态和演变过程重要组成部分。,4,随着卫星定位技术、无线通信、跟踪检测设备及视频实时采集技术的快速发展，人们能够方便地以低廉的价格获得时空轨迹数据。例如，通过传感器遥测野生动物或者鱼类的活动，通过旅行日志记录交通工具的运动状况，通过条形码的检入检出了解物流的状况，通过信用卡刷卡记录或者电话通话记录来跟踪用户的位置，甚至通过互联网搜索某对象的相关事件来确定该对象的运动轨迹等。,时空轨迹数据分析,5,时空轨迹数据：,时空轨迹数据分析,6,时空轨迹数据分析,空间对象的位置、属性都可能随着时间的推移而发生变化，人们不仅需要知道某一对象的属性和空间信息，更要了解该对象的来龙去脉，以便对其形成原因作出评估，对未来情况进行预测。时空轨迹数据恰能有效地表达时空对象的这些特性，通过分析各种不同对象的时空轨迹数据，有助于对人类行为模式、交通物流、应急疏散管理、动物习性、市场营销、计算几何以及模拟仿真等各个领域进行研究。,7,轨迹数据挖掘,轨迹数据挖掘一般采用时空数据挖掘的基本理论、方法，同时又针对轨迹数据的特点，引入了一些特有的挖掘过程和方法，通常轨迹数据的知识发现过程包括三个阶段：轨迹重构(Reconstruction)知识抽取(Extraction)知识传递(Delivery),时空轨迹数据分析,8,时空轨迹数据分析,(1)原始数据采集阶段：数据的采集包括轨迹数据本身的采集和轨迹所处的地理环境数据的采集。(2)数据预处理阶段：对应于时空数据的预处理阶段，通过对采集的数据进行冗余分析、特征提取，将其整理成便于数据挖掘操作的数据格式。(3)数据语义扩充阶段：根据具体应用，对轨迹数据、地理数据进行集成，并根据GIS等应用的要求，突出轨迹的时空语义等特征。(4)数据挖掘与知识发现阶段：采用数据挖掘的各种算法对处理后的数据进行挖掘和分析，并给出挖掘结果的时空语义分析和知识表达的合理解释。,轨迹数据挖掘和知识发现的一般过程,9,时空轨迹数据分析,在数据驱动的空间数据挖掘方法中，聚类分析和关联规则挖掘是两种重要的手段，其区别在于关联规则挖掘是一个异中求同的过程，而聚类分析则是同中求异的过程。通过聚类能够识别对象空间中稠密和稀疏的区域，将数据中的相似性与异常特征提取出来，从而发现全局分布模式和数据属性之间有趣的相关。这正符合人们对时空轨迹数据分析的要求，即在没有先验知识的情况下，先将数据聚合成不同的类，再对各类所代表的模式进行解读从而获得知识。,时空轨迹数据,时空轨迹(Trajectory)数据具有与其他数据不同的重要特征，主要体现在定义、模型和表达3个方面。它既是一种重要的时空对象数据类型，又是一种重要的信息源，因此其应用范围也非常广泛。定义：时空轨迹是移动对象的位置和时间的记录序列。,时空轨迹数据分析,时空轨的模型,从定义中我们可以看出，时空轨迹是连续的，但通常用一组时空记录点序列，以离散的方式表示。例如，对时空对象的实际轨迹曲线进行采样，用得到的集合来代表时空轨迹。因此，时空轨迹的模型如下所示。,时空轨迹数据分析,时空轨迹数据的表达,为了对时空轨迹进行比较，常常需要通过其模型重构时空轨迹，这就是时空轨迹数据的表达。轨迹表达的方法有很多种，结合Nanni对轨迹重构方法的分类方式，按照对轨迹记录点间对象运动过程的不同认识，时空轨迹数据的表达分为三个方面：基于全局回归模型的时空轨迹数据表达基于局部插值模型的时空轨迹数据表达基于领域知识模型的时空轨迹数据表达,时空轨迹数据分析,1基于全局回归模型的时空轨迹数据表达,如果时空对象的运动方式整体上服从某一规则，那么可对该对象的所有记录点进行全局回归，用关于时间t的回归方程代表时空对象的轨迹。,时空轨迹数据分析,如右图所示，黑点和白点分别代表两条不同轨迹的记录点，两条直线是采用线性回归所得到的轨迹。由于这种模型过于简化，重构的时空轨迹也不与所有采样点重合，往往不能满足实际的需要。,2基于局部插值模型的时空轨迹数据表达,有时时空对象的运动方式并非全局一致，但可以假设在相邻记录点间的局部运动是服从特定规则的，不同的规则可以用不同的局部插值方法来表达。最常见的规则是相邻记录点间对象作匀速直线运动，该规则可以用线性插值方法表达。这种模型在时空轨迹模拟和分析中均被广泛使用，并且可以采用时空路径(Space-timePath)的方式来可视化表达。,时空轨迹数据分析,2基于局部插值模型的时空轨迹数据表达,时空轨迹数据分析,3基于领域知识模型的时空轨迹数据表达,如果没有内插函数作为重构轨迹的依据，那么在任意相邻的记录时刻间，时空对象理论上可能在空间中的任何位置出现，但多数情况下各种领域知识会限制该对象出现的位置。例如，由于存在移动速度的限制，在某个记录时刻后，该时空对象只能存在于以该记录点为顶点的一个圆锥体内；或者由于道路的限制，对象只能沿交通网络运动；或者用户在运动过程中需要使用信息通讯技术，故受到网络覆盖区域的限制等等。时空棱镜(Space-timePrism)是一种很好的可视化表达方式。,时空轨迹数据分析,时空轨迹数据分析,3基于领域知识模型的时空轨迹数据表达,为了从时空轨迹数据中提取其相似性与异常，并发现其中有意义的模式，时空轨迹聚类分析方法被广泛采用。该方法的主要目的是试图将具有相似行为的时空对象划分到一起，而将具有相异行为的时空对象划分开来。其关键是根据时空轨迹数据的特点，设计与定义不同轨迹间的相似性度量。要将数据集划分成不同的类别，必须定义一种相似性的测度来度量同一类样本间的类似性和非同类样本间的差异性，而各种时空轨迹聚类方法间的主要区别也正是在于其相似性度量的不同。,时空轨迹数据分析,时空轨迹聚类方法,两个对象之间的相似度(Similarity)是这两个对象相似程度的数值度量，相异度(Dissimilarity)是这两个对象差异程度的数值度量，距离(Distance)常被看作是相异度的同义词。因而，两个对象越类似，它们的相似度就越高，相异度就越低，距离越小。通常，相似度的取值范围是0,1(0代表完全不相似，1代表完全相似)，而相异度(距离)的取值范围是0,)(0代表完全相似，代表完全不相似)。相似度与相异度通常是可以互相转化的，所以使用“相似性度量”作为相似度和相异度(距离)的统称。,时空轨迹数据分析,相似度、相异度,依照相似性度量所涉及的不同时间区间，可将现有的时空轨迹聚类方法划分为六类，如右图所示：,时空轨迹数据分析,时空轨迹聚类方法分类,从右图中可以看出，这六类方法对于相似时间区间的要求是逐渐放松的，从要求时间全区间相似，到局部时间区间相似，最后到无时间区间对应相似。这种分类方式既能体现人们对时空轨迹相似性认知的多样性，又能反映时空轨迹相似性度量的发展过程。,21,1时间全区间相似的聚类方法,时空轨迹数据分析,时间全区间相似的聚类方法将时空轨迹看作一个整体，并要求同一聚类中的轨迹在各个时刻都对应相似。这类方法所使用的相似性度量主要有：轨迹间欧氏距离不同于点与点之间的欧式距离，根据轨迹的特点重新定义轨迹间的欧氏距离。最小外包矩形距离可以看作一种简化时空轨迹的方法。是将每条子轨迹用其最小外包矩形(MinimumBoundaryRectangle，MBR)表示。,22,1.1轨迹间欧氏距离,时空轨迹数据分析,轨迹间欧氏距离和点与点的欧氏距离有所不同。它首先将轨迹用相同维度的坐标向量表示，然后计算每一个时刻上对应两点的欧式距离，再对这些距离进行综合(如求和，求平均值、最大值或者最小值)，就可以得到轨迹间欧式距离。在二维空间中，轨迹间欧式距离公式为：,23,1.1轨迹间欧氏距离,时空轨迹数据分析,轨迹间欧氏距离计算费时，为了提高效率，有学者提出通过离散傅里叶变换和离散小波变换来降维的近似办法，还有提出提出了一种名为APCA(自适应逐段常量近似)的近似方法，但是这些方法都不能应用于采样率不同或者尺度不同的轨迹数据。采样率不同：先将轨迹分段线性表示，然后内插重采样，再计算轨迹间欧氏距离。尺度不同：先对轨迹进行全局缩放再计算轨迹间欧式距离。缺点：严格计算轨迹在每个时刻的对应距离，因此这类方法对噪声较敏感。,24,1.2最小外包矩形距离,时空轨迹数据分析,首先将整条轨迹划分成一些相对平滑的轨迹区间，再将每条子轨迹用其最小外包矩形(MinimumBoundaryRectangle，MBR)表示，这样每条轨迹就变成了一个最小外包矩形的序列，如下图所示。图中虚线矩形框和实线矩形框分别代表虚线轨迹和实线轨迹的最小外包矩形序列，通过比较最小外包矩形序列即可度量时空轨迹间的相似性。,25,1.2最小外包矩形距离,时空轨迹数据分析,根据计算的最小外包矩形距离如何判断相似性：（1）将各对外包矩形间的距离加权平均作为整体轨迹间的距离；（2）将最小外包矩形重叠部分的大小作为整条轨迹相似性度量；优点：使用最小外包矩形代替了轨迹区间，平滑了轨迹的细节，并在一定程度上缓解了噪声的影响。缺点：如何有效地将轨迹划分成平滑轨迹区间。这类时间全区间相似聚类方法的优点在于非常直观，易于理解，但那些不在一一对应时刻上完全相似的轨迹，则可能被遗漏。,26,2全区间变换对应相似的聚类方法,时空轨迹数据分析,该类方法在全区间相似聚类方法的基础上，放松了对时间维的限制，即时空轨迹的时间维可以局部拉伸和缩放，只需要保证轨迹记录点的时间顺序，而不需要在一一对应的时刻上进行比较。这种方法忽略了轨迹度量间时间维尺度不同的问题。其中基于DTW(DynamicTimeWarping)距离的方法就是典型代表。DTW距离又称动态时间弯曲模型，能够克服欧式距离在时间轴的弱点，查找结果要优于欧氏距离，而且可采用下界函数提高计算速度和相似性测量精度。,27,2DTW（动态时间弯曲）距离,时空轨迹数据分析,基于DTW距离的方法在保证时空轨迹对象记录点顺序不变的前提下，通过重复之前的记录点来完成时间维的局部缩放，以此求出轨迹间的最小距离作为相似性度量。具体计算公式：,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)计算为例。首先如果从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距离时，轨迹间的记录点映射需要具有连续性，因此对于噪声很敏感。此外，如果两条轨迹在小部分区间内完全不相似，该方法将无法识别。,31,3多子区间对应相似的聚类方法,时空轨迹数据分析,为解决上一类方法无法识别小部分不相似区间的问题，多子区间对应相似的聚类方法在定义相似性度量时，不要求整条轨迹相似，而是寻找不重叠的多个相似子区间，并将所有子区间的相似性汇总成轨迹间的相似性度量。多子区间对应相似的聚类比较常见的方法有：最长公共子序列距离编辑距离,32,3.1最长公共子序列距离,时空轨迹数据分析,最长公共子序列(Longestcommonsub-sequence,LCSS)是指两个或者多个序列中存在的最长的共同子序列。对于时空轨迹来说，计算其最长公共子序列并转化为LCSS距离可以衡量轨迹间的相似程度。LCSS的计算一般通过递归方式求得,如式:,式中：LCSS(R,S)表示时空轨迹R与S间的LCSS长度，和分别表示x轴和y轴上的相似阈值，当横坐标差小于且纵坐标差小于时，认为这对记录点相似，LCSS值加1，Rest(R)和Rest(S)分别表示轨迹R与S去掉第一个记录点所得的轨迹区间。,33,3.1最长公共子序列距离,时空轨迹数据分析,当轨迹记录点数都为0时，LCSS(R,S)为0；若记录点个数不为0，则用递归的方式判断共有子序列长度的最大值。,如上图所示，实线和虚线分别为一维空间中的两条时空轨迹，横轴为时间，纵轴为一维空间坐标，区间1、2、3内是LCSS公式所定义的共有子序列，两条轨迹在这3个子区间内是对应相似的。,34,3.1最长公共子序列距离计算,时空轨迹数据分析,用动态规划思想进行最长公共子序列距离计算，分为两步：第一步：先计算最长公共子序列的长度。第二步：根据长度，然后通过回溯求出最长公共子序列。,现有两个序列GCCCTAGCG，GCGCAATG。V1=左侧单元格的值；V2=上面单元格的值；V3=左上侧单元格的值。在空单元格中填充下面3个数字中的最大值：V1V2如果C1等于C2则为V3+1，如果C1不等于C2，则为V3，其中C1是当前单元格上面的字符，C2是当前单元格左侧的字符。,从右下侧的单元格开始，看到单元格指针指向左上侧的单元格，而且当前单元格的值（5）比其左上侧单元格的值（4）大1。所以将字符G添加到最初的零长度的字符串之前。下一个箭头，从包含4的单元格开始，也指向左上侧，但是值没有变。接着这个箭头也是如此。下一个单元格的箭头还是指向左上侧，但是这次值从3变为4。这意味着需要将这一行和这一列中的公共字符A添加到LCS中。继续使用这种方式，直到最后到达0。得到的LCS为GCCAG。,35,3.1最长公共子序列距离,时空轨迹数据分析,在应用中，通常使用轨迹间的距离作为相似性度量，因此研究者们将LCSS转换为距离的形式来进行聚类，其转换方式是：,式中:DLCSS(R,S)表示时空轨迹R与S间的LCSS距离；min(m,n)表示R与S的记录点个数的较小值。这个过程使得轨迹间的LCSS转换为0,1间的距离。LCSS方法不需要所有的记录点全部匹配，因此不相似的区间会被剔除。此外，因为点与点的距离被概化为0和1，所以即使噪声点参与到LCSS的计算中，其影响也会被减弱。,36,3.2编辑距离,时空轨迹数据分析,编辑距离(EditDistance)是指两个序列(文本或者模式等)进行比较时，若只进行增、删、改操作，一个序列完全变成另一个序列所需最小操作次数，也可以很容易地将其扩展为时空轨迹间的编辑距离。如式：,式中：ED(R,S)表示轨迹R和S的记录点序列(r1,rm)和(s1,sn)间的编辑距离，m和n分别代表时空轨迹R与S的记录点个数，Rest(R)和Rest(S)分别表示轨迹R与S去掉第一个记录点所得的轨迹区间。,37,3.2编辑距离,时空轨迹数据分析,如式，如果其中一条轨迹的记录点个数为0时，编辑距离为另一条轨迹的记录点个数；如果两条轨迹均存在记录点，且首个记录点坐标相同，则编辑距离不变；否则编辑距离增加，并采用递归的方式求取最小值作为编辑距离。,例如，两条一维时空轨迹的空间坐标序列为1,3,4,5和1,2,3,4,6，那么它们的编辑距离就为2，因为序列1,3,4,5经过第二位增加2和最后一位改成6两次操作就可以变成序列1,2,3,4,6。,38,3.2编辑距离计算,时空轨迹数据分析,用动态规划思想进行编辑距离的计算。,两个序列failing，sailn。定义函数edit(i,j)，表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。显然可以有如下动态规划公式：ifi=0且j=0，edit(i,j)=0ifi=0且j0，edit(i,j)=jifi0且j=0，edit(i,j)=iifi1且j1，edit(i,j)=minedit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+f(i,j)，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i,j)=1；否则，f(i,j)=0。,计算edit(1,1)，edit(0,1)+1=2，edit(1,0)+1=2，edit(0,0)+f(1,1)=0+1=1，min(edit(0,1)，edit(1,0)，edit(0,0)+f(1,1)=1，因此edit(1,1)=1。以此类推,39,3.2编辑距离,时空轨迹数据分析,在编辑距离的计算过程中，要求首个记录点坐标相同的判断条件往往过于严格，影响了计算效率和精度，对其进行了改进：不要求序列在增、删、改操作后完全相同，而只要在一定阈值内相似即可；提出EDR距离，是基于编辑距离的扩展，通过正态化处理解决了空间维缩放的问题。最长公共子序列距离和编辑距离都考虑的是多个子区间对应相似的情况，这一大类方法能发现非整体相似的时空轨迹，但是所发现的相似时间区间是离散且不确定的，这种区间在数学上比较清晰，但是并不直观，不易被人们观察和理解。,40,4单子区间对应相似的聚类方法,时空轨迹数据分析,为解决多子区间对应相似聚类方法中相似区间不直观的问题，单子区间对应相似的聚类方法在其基础上，对时间区间的要求进一步放松：只需获得一个最大的相似子区间，就能衡量轨迹间的相似性。单子区间对应相似的聚类方法主要有：子轨迹聚类时间聚焦聚类移动微聚类移动聚类等,41,4.1子轨迹聚类,时空轨迹数据分析,子轨迹聚类方法由Lee等在2007年提出的，它采用的是先划分再聚合的思路(Partition-and-groupFramework)，其流程如下图所示：,首先将时空轨迹看作一组点序列，然后按照最小描述长度(MinimumDescriptionLength，MDL)原则将轨迹划分为一些子轨迹，再用基于密度的聚类方法对这些子轨迹聚类，最终可以得到子轨迹的运动模式和整条轨迹的相似子区间。,42,4.1子轨迹聚类,时空轨迹数据分析,43,4.2时间聚焦聚类,时空轨迹数据分析,时间聚焦聚类(Time-focusedClustering)方法可以较好地解决子轨迹聚类存在的问题。该方法的思想是：先定义了一个聚类过程，该过程是将某一时间区间内轨迹间的欧氏距离作为相似性度量，并采用基于密度的聚类方法OPTICS对轨迹进行聚类；对每一个不同的时间区间均进行一次上述聚类过程；最终目标是发现使轨迹聚类结果最优(即类内相似度大、类间相似度小)的时间区间，并记录这个区间和相应的聚类结果。,44,4.2时间聚焦聚类,时空轨迹数据分析,轨迹集合由三类轨迹添加一些噪声轨迹组成，每条虚线代表一条时空轨迹，实线代表最优轨迹聚类结果，即在实线所示的时间区间内，聚类结果中的各个类别类内相似度大，类间相似度小，能够被清晰地区分。,45,4.3移动微聚类,时空轨迹数据分析,移动微聚类(MovingMicroClustering，MMC)方法将数据挖掘中经典的BIRCH方法应用于移动对象轨迹数据，在原有的微聚类基础上增加了时间维信息，也就是说在同一聚类中的对象不仅在当前时刻位置靠近，还需要保持相近(共同运动)一段时间。该方法把每个微聚类的中心看作一个对象继续聚类，即不予区分微聚类和对象，最终形成层次结构完成聚类。在这个过程中，移动微聚类需要根据一个预先定义的外包矩形来判断聚类是否应该分裂或合并，但这个矩形的参数需要人为定义，这就是这个方法的不足之处。,46,4.4移动聚类,时空轨迹数据分析,前面提到的方法中，聚类都可以被认为是“内涵固定”的，即相似时间区间内，类内的个体集合不变。移动聚类(MovingCluster)改变了这种对聚类的看法，将聚类视为一个动物群落，群落中时有个体迁入，时有个体迁出，但是处于群落中的个体始终保持聚集。这种方法的思想：首先认为移动对象是由多个时间片(TimeSlices)上的空间位置组成分别对每个时间片上的点进行聚类，然后计算连续时间片中聚类所包含点的重合程度，如果大于一定阈值，那么这个移动聚类成。,47,4.4移动聚类,时空轨迹数据分析,如下图所示(图中每条折线代表一条轨迹，而每一个时间片上的聚类用深色圆形表示)，这个聚类中成员的生命周期(Lifetime)不需要一致，只需在某一时间段内保持聚集即可成为聚类。这种方法更关注聚类所涉及的区域而非其中的轨迹对象，所以可以认为它是一种介于聚类与频繁模式挖掘之间的方法。,48,5单点对应相似的聚类方法,时空轨迹数据分析,这类方法是将轨迹间的相似性概括为某一对记录点间的相似性，即以一个时间点来代表整个时间区间。单点对应相似的聚类方法包括：历史最近距离Frchet距离,49,5.1历史最近距离,时空轨迹数据分析,历史最近距离是任意两条轨迹在给定时间范围内同一时刻的最近距离。计算公式如下：,式中：MinDist(R,S,T)表示时空轨迹R与S在时间区间T内的历史最近距离，R(t)和S(t)分别表示轨迹R与S在t时刻的空间位置，dist(R(t),S(t)表示R(t)和S(t)间的欧氏距离。,50,5.2Frchet距离,时空轨迹数据分析,Frchet距离是一种新的判断曲线之间相似性的距离测度，它最先起源于人-狗距离模式。人-狗距离模式：假设有一个人和一只狗，他们分别位于两条给定曲线A、B上。人牵着狗脖子上的绳索L拉着狗前进。在起始时刻，人与狗分别位于两条曲线的起始点处，向终点走去。这里的人与狗虽然可以以任意的自由速度移动但是限制只能在各自的曲线上行走。于是这两条曲线间的距离以函数的形式定义，并且表示人与狗之间的绳索L的长度。那么Frchet距离就是指连接人与狗之间的最小绳长。,51,5单点对应相似的聚类方法,时空轨迹数据分析,历史最近距离和Frchet距离比较：相同点：将轨迹间的距离抽象为某一个时刻上点与点的距离，以此来代表整条轨迹间的距离。不同点：历史最近距离是一种乐观的相似性度量，只要两条轨迹在某一时刻曾经靠近过就认为它们相似，而Frchet距离是一种悲观的相似性度量，它认为必须在每一时刻都靠近才能说两条轨迹相似。,52,6无时间区间对应相似的聚类方法,时空轨迹数据分析,无时间区间对应相似的聚类方法在度量轨迹间相似性时，将时间维的限制进一步放宽，通常只考虑空间位置的相似性，或者将时空轨迹转换到属性空间进行比较。无时间区间对应相似的聚类方法有：比如单向距离方法特征提取方法等,53,6.1单向距离,时空轨迹数据分析,单向距离(One-wayDistance，OWD)是一种将时间相似性弱化的相似性度量方法。该方法源自巴士线路设计问题，在这类问题中，速度和方向信息不重要，时间顺序的意义也不大，只有空间形状的相似性比较重要。为了定义OWD，首先需要定义点p到轨迹T的距离：,54,6.1单向距离,时空轨迹数据分析,例如，两条一维轨迹的空间坐标序列为T1:1,2,3,4和T2:8,6,4,2，那么T1上每个点到T2的距离分别为1、0、1、0，T1上每个点到T2的距离分别为4、2、0、0，那么轨迹T1到T2的OWD为0.5，轨迹T2到T1的OWD距离为1.5，T1与T2间的距离则为1。单向距离在定义轨迹间相似性时，尽管同样是抽象成点与点的距离，但是不考虑时间上的顺序关系，这点与历史最近距离和Frchet距离不同。,55,6.2特征提取方法,时空轨迹数据分析,该方法不对轨迹本身直接进行比较，而是先从轨迹中提取特征，再通过特征来定义相似性度量。常见的方法有：分别从轨迹中提取地标和签名特征，然后对这些特征定义运算规则来计算轨迹间的距离；将轨迹分别抽象为速度特征和方向特征，并定义了对应的相似性度量进行聚类。,56,7其他聚类方法,时空轨迹数据分析,其他聚类方法包括：人机交互方法人机交互方法是根据用户提出的一些限制来调整参数获得距离度量函数。基于模型的方法基于模型的方法尝试针对轨迹数据特点建模，然后将从同一模型构造出来的对象聚成一类。递增层次方法递增层次方法认为轨迹是由不同元件组成的序列，不同轨迹按泛化程度形成层次结构从而完成聚类。基于图形的方法基于图形的方法则是将轨迹曲线看作一些线状图形的组合，依此为轨迹编码，通过这种编码可以有效地查询指定形状的数据，从而将形状相似的轨迹聚成一类。,57,时空轨迹的应用,时空轨迹数据分析,时空轨迹的应用包含多个方面：通过罪犯的行动轨迹了解其作案模式，以便进行预警和抓捕；通过台风的轨迹认识其形成和运动模式，以便对人群进行疏散；通过人口迁移轨迹数据发现其中不同人群的迁移习惯，以便制定相关政策，帮助人们搬迁定居等。,58,快速寻找乘客,时空轨迹数据分析,对出租车司机来说，最重要的问题当然是盈利，而最关键的则是如何最快找到乘客。一个熟练的出租车司机可以几乎不间断地搭载客人，而缺乏经验的出租车司机却往往找不到最快搭载乘客的路线。幸运的是，移动轨迹分析可以帮助出租车司机们解决这个问题。我们根据历史数据，分析并预测一个区域未来的乘客数量，可为出租车司机提供最快找到乘客的路线。,59,快速寻找乘客,时空轨迹数据分析,首先通过聚类算法找到那些乘客密集的区域，并且将这些区域作为推荐给出租车司机的候选区域。,60,快速寻找乘客,时空轨迹数据分析,注意到所有区域的乘客数量都会以一天为变化周期，我们对不同日但相同时间段的数据使用改进的差分自回归移动平均模型（ARIMA）进行预测。,将乘客数据分成等长的时间段，然后对每个时间段的乘客数量进行预测。,61,快速寻找乘客,时空轨迹数据分析,注意到所有区域的乘客数量都会以一天为变化周期，我们对不同日但相同时间段的数据使用改进的差分自回归移动平均模型（ARIMA）进行预测。,将乘客数据分成等长的时间段，然后对每个时间段的乘客数量进行预测。,62,快速寻找乘客,时空轨迹数据分析,在掌握了区域未来的乘客数量之后，又该如何推荐最快的载客路线呢？我们考虑了载客过程中两段最主要的时间开销，即从当前地点到载客点的行驶时间与在载客点等待乘客上车的时间。我们将历史数据中对应路段的平均行驶时间作为到载客点行驶时间的估计，并假设乘客到来是随机而均匀分布的，建立简单的排队模型计算在载客点等待乘客上车的时间。我们将这两个时间之和最小的路线作为最快的载客路线。从实验结果可发现，我们推荐的载客路线可以帮助出租车司机平均节省37%的时间。,63,异常轨迹检测,时空轨迹数据分析,在乘坐出租车时，不熟悉路途的乘客经常会产生这样的疑问：这么长时间了怎么还没到目的地？出租车司机是不是绕路了？我们将那些不频繁的轨迹定义为异常轨迹。这些异常轨迹反映了出租车司机不合常态的驾驶行为，这些行为很有可能也是不合理或不恰当的。我们可以将两地之间的所有轨迹简单地堆积。,S和D之间存在三条比较频繁且不长的行驶路线，而t0、t1、t2、t3是四条不频繁的轨迹，被定义为异常轨迹。,64,异常轨迹检测,时空轨迹数据分析,应如何从众多轨迹中检出异常轨迹？我们将轨迹映射成字符串然后使用字符串匹配的算法来寻找异常轨迹。从数据结构来说，由于GPS采样的不连续性，每条轨迹实际上由一组点构成。为了去除同一条道路上不同位置的GPS差异，我们将每个GPS点映射为一个250m250m的方块，并用唯一的ID表示。一条轨迹就可以表示为由这些ID构成的字符串。对这些字符串匹配可以比较轨迹的相似程度，使用Isolation Forest算法就可以将所有字符串表达为树的一个结点，而结点的深度对应于它与其它结点的匹配程度，从而快速找到那些异常轨迹。,65,参考文献：,时空轨迹数据分析,1龚玺，裴韬，孙嘉,等.时空轨迹聚类方法研究进展.地理科学进展, 2011, 30(5): 522-534.2潘纲,李石坚,齐观德,等.移动轨迹数据分析与智慧城市.中国计算机学会通讯，2012,8(5):31-37.3唐建波，邓敏，刘启亮.时空事件聚类分析方法研究.地理信息世界, 2013,20(1):38-45.DTW距离计算：http:/,66,66,谢谢！,