随着移动定位技术的蓬勃发展与移动定位设备的广泛应用,衍生了海量移动对象的位置信息。该类位置数据包含地理坐标、速度、方向以及时间戳等信息,被实时采集且持续增加,形成了大规模、高速的集中式/分布式轨迹流。及时、有效的对轨迹流数据进行分析处理,可以感知移动对象时变进化的行为规律,继而揭示移动行为模式背后所隐含的特殊事件。聚类与异常检测是两类典型的轨迹数据挖掘技术。作为一种无监督的移动模式发现方法,聚类旨在将海量的轨迹数据集划分成若干相似的簇以提取不同移动对象的代表路径或共同移动趋势。与之相对应的另一类工作是轨迹的异常检测,异常检测的主要任务是识别与其他大多数轨迹具有明显差异的“少数”轨迹,进而及时发现异常的事件。面向轨迹流数据设计高效的聚类分析与异常检测方法可以服务于广泛的实时位置服务,例如智能交通管理、路径规划、道路设施优化等。目前,面向轨迹流的在线聚类分析与异常检测的研究工作相对较少,其原因在于轨迹流本身是一个持续的、无限的时序位置流。处理持续到达的轨迹数据不仅面临严格的时空复杂性限制要求,还需有效解决伴随轨迹流数据产生的“概念漂移”问题。与此同时,轨迹流数据固有的“时变进化性”和“偏态分布性”等特性,也给研发有效的轨迹聚类分析与异常检测方法带来了巨大的挑战。而更为严峻的是,在处理分布式轨迹流时,不但需要保证分析结果的高精度,还需设计高效的并行分析任务以及最小化的通信开销策略来满足低处理延迟的实时分析需求。为了解决上述问题,本文致力于设计面向集中式、分布式轨迹流的聚类分析与异常检测方法。本文的研究内容和主要贡献概括如下:1.面向轨迹流的聚类分析。本文基于滑动窗口模型首先提出了OCluWin框架实现对集中式轨迹流数据的聚类分析。OCluWin框架包括对最近到达的轨迹线段集进行在线分析的微聚类阶段,以及基于用户特定时间范围内微聚类结果进行再次聚类的宏聚类阶段。随后,在OCluWin框架基础上,本文提出了使用两种不同的概要数据结构(包括E五o与EF)的轨迹流聚类方法:TSCluWin和OCluST方法。EFo与EF结构不仅可以实时获取轨迹流数据的聚类特征,还能追踪轨迹流数据的聚类演变趋势。理论分析与实际轨迹数据上的实验结果表明,本文所提的两种方法(TSCluWin和OCluST)在对轨迹流数据进行聚类分析时均具有优越的性能。2.面向分布式轨迹流的在线聚类分析。面对地理上分散部署的不同节点采集获得的分布式轨迹流数据,本文首先提出了适于分布式聚类的概要数据结构来实时获取轨迹簇的聚类特征,继而维护持续进化的轨迹流。在此基础上,使用基于滑动窗口模型的两层结构的分布式框架设计了一个可在线处理分布式轨迹流的增量聚类算法(OCluDTS)。通过多个远程节点并行聚类局部轨迹流以及协调者节点合并局部聚类结果的方式,保证分布式聚类能获得较高精度的全局聚类结果。此外,仅限于聚类更新的远程节点传输局部聚类结果给协调者节点、以及基于协调者节点相似性计算的剪枝技术等优化策略,进一步降低了OCluDTS算法的总执行开销。理论分析与基于真实轨迹数据集的实验结果表明,OCluDTS方法在高效处理大规模分布式轨迹流数据的同时能够确保聚类结果的高精度。3.基于特征分组机制的轨迹流异常检测。实际应用中轨迹异常往往表现为与其局部时空近邻的明显移动行为差异,但现有异常检测技术并未考虑解决这一问题。为了发现基于局部邻域内显著移动行为差异的异常轨迹,本文首次提出了基于特征分组机制的异常检测技术,将从轨迹数据的属性中提取的特征集划分为相似性特征和差异性特征两类。对于实时到达的轨迹数据先通过轨迹简化处理获得轨迹分段集,再使用相似性特征提取各个轨迹分段的局部空间邻域,随后使用差异性特征识别各个局部空间邻域内的异常轨迹分段。根据一个(或多个)时间间隔内局部邻域内的明显移动行为差异,本文给出了局部异常的轨迹分段(TF-outlier)与进化的异常移动对象(MO-outlier)两个轨迹异常定义。同时,设计了用于检测上述两种轨迹异常的基本方法以及优化的解决方案。最后,基于多个真实轨迹数据集上的实验结果验证了本文所提轨迹流异常检测方法的高效率与有效性。4.面向分布式轨迹流的在线异常检测。为了实时发现分布式轨迹流中基于轨迹局部空间邻域的异常移动行为,本文提出了异常轨迹分段、异常分段簇和进化的异常对象等三种轨迹异常定义。在此基础上,提出了第一个适于分布式轨迹流的高可伸缩分布式异常检测算法(ODDTS)。ODDTS算法以在分布式轨迹流中持续提供基于特征分组的异常检测任务为目标,主要工作包括各个远程节点上异常轨迹分段与异常分段簇的并行检测、以及协调者节点上的进化异常对象识别等两阶段任务。本文所提的分布式轨迹流异常检测方法(ODDTS)得益于并行异常检测机制的高效性以及节点间(远程节点与协调者节点之间)的较少传输开销,能获得相对于集中式轨迹流异常检测方法的显著性能提升。基于真实轨迹数据的广泛实验证明,ODDTS方法能高效完成分布式轨迹流的在线异常检测,同时具有较高的检测精度以及线性的可伸缩性。总之,本文重点研究了轨迹流的聚类分析与异常检测技术,并围绕其中的四个基本问题进行了详细分析。滑动窗口模型是处理轨迹流的基本模型之一,具有消除过时数据对分析结果影响的优势。如何在滑动窗口内对持续到达的轨迹流进行增量的聚类分析是一个基本问题;当轨迹流越来越多的由分散部署的节点采集得到时,如何扩展现有的集中式轨迹流的聚类分析技术,设计适于分布式环境的轨迹流聚类方法,在获得优质聚类结果的同时确保其高效率是一个基本问题;实际应用中轨迹异常通常表现为与其局部时空近邻具有显著的移动行为差异,如何基于轨迹的局部时空邻域评测移动行为的异常程度,从而发现异常的轨迹与移动对象也是一个基本问题;在分布式环境下如何设计适合的轨迹流异常检测算法,保证实时发现各个节点上基于局部时空邻域明显行为差异的异常轨迹或异常轨迹簇,并在此基础上有效检测分布式环境中进化的异常移动对象是一个亟待解决的基本问题。鉴于上述四个基本问题,本文分别提出了基本的解决方案以及相应的优化策略。本文的研究工作是建立在对当前已有的理论、技术与方法的详尽分析基础之上完成的。理论分析以及基于真实轨迹数据的实验测试结果表明,本文提出的解决方案在聚类分析与异常检测结果的准确性、执行效率方面均具有明显的优势。