面向物联网移动终端设备的用户轨迹异常检测研究

为了有效地从物联网移动设备的数字信息中挖掘出用户在日常行为中的轨迹异常,针对现有用户异常轨迹检测算法效率低的问题,提出了一种双层聚类的用户轨迹异常检测方法。考虑到移动终端设备中的轨迹信息数据量大、分布不均匀等特点,该方法在特定的空间距离与时间间隔下提取出停留点集合,并对这些点进行层次聚类,根据结果划分出停留区域,进而发现其中的异常停留区域;最后,对停留区域之间发生的运动轨迹段进行二次层次聚类,发现异常轨迹段。实验结果表明,该方法在发现异常轨迹时,相较于传统算法,既全面地检测出异常轨迹,又加快了异常检测的速度。     

基于时空模式的轨迹数据聚类算法

针对轨迹聚类算法在相似性度量中多以空间特征为度量标准,缺少对时间特征的度量,提出了一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础,首先利用曲线边缘检测方法提取轨迹特征点;然后根据轨迹特征点对轨迹进行子轨迹段划分;最后根据子轨迹段间时空相似性,采用基于密度的聚类算法进行聚类。实验结果表明,使用所提算法提取的轨迹特征点在保证特征点具有较好简约性的前提下较为准确地描述了轨迹结构,同时基于时空特征的相似性度量因同时兼顾了轨迹的空间与时间特征,得到了更好的聚类结果。     

基于轨迹聚类的公共安全异常检测

公共安全异常检测的需求越来越迫切,监控中基于轨迹聚类的检测方法越来越流行,但是现有方法在处理高维不等长轨迹数据时效果并不理想。提出一个新的轨迹聚类方法,该方法通过组合动态时间弯曲和密度峰算法实现。动态时间弯曲用于度量轨迹间的距离,密度峰算法根据距离进行聚类。前者可直接度量不等长轨迹聚类,后者是近年提出的非球体分布数据聚类算法,以局部密度和最近邻聚类组合实现。实验在PETS2006监控视频数据集上进行,测试结果表明该方法有效地发现了异常的轨迹行为模式。     

基于速度约束的分段轨迹聚类算法

目前的轨迹数据聚类直接对整条轨迹数据聚类,或先分段再对轨迹段聚类。分段聚类法抛弃轨迹段内部点,丢失轨迹局部特征,没有考虑点的速度影响。针对该问题,提出一种基于速度约束的分段轨迹数据聚类方法。该方法将速度约束和two-pass corner detection应用于轨迹分段,在邻域计算中加入速度约束,采用Discrete Fréchet Distance比较轨迹段距离,保留了轨迹段内部特征。用类似DBSCAN的TraDBSCAN算法对轨迹段进行聚类。实验结果表明,该方法考虑速度因素,可以获得更有效的聚类结果。     

基于轨迹聚类的航空器轨迹模式挖掘研究

轨迹模式是航空器在某段时间或某个区域内相对稳定的飞行模式,对理解和判断目标在一段时间或一定区域内的行为有着重要的意义。针对目标轨迹的特点,在基于点密度的聚类算法的基础上,设计并实现了一种基于线段密度的轨迹聚类方法。该方法使用最小描述长度原则将目标的历史轨迹分割为若干轨迹段,通过计算轨迹段之间的相似度对飞行轨迹进行聚类,最后运用扫描线算法生成目标的轨迹模式。实验证明,该方法可以较为准确地从大量轨迹数据中发掘出航空器目标的轨迹模式。     

基于改进Hausdorff距离的轨迹聚类算法

以整条轨迹为目标的聚类方法存在轨迹较长的问题。为此,提出一种以轨迹子段为聚类目标的聚类算法CTIHD。给出一种新的轨迹子段距离度量方法,用以消除轨迹子段之间的公共偏差。利用特征点概念将轨迹划分成轨迹子段集,计算轨迹子段之间的相似度,由此实现聚类。实验结果表明,该算法相比同类算法具有更好的轨迹聚类效果。     

基于移动对象轨迹段分割的聚类算法研究

将对象的运动轨迹作为一个整体聚类,将丢失相似子轨迹段有用的信息.为了找出相似子轨迹段,提出针对某一个轨迹进行子轨迹的聚类算法,先把长轨迹在特征点分割为一组直子段,再用基于密度的聚类算法对子段进行聚类,得到子段的可达距离排序并生成可达性图,最后根据生成的可达性图识别聚类结构.实验结果表明该方法能有效准确地识别相似子轨迹段.     

基于路口信息的出租车异常轨迹检测

针对出租车的异常轨迹检测问题,根据已有的出租车GPS数据,结合城市道路路口信息,提出了一种基于路口的异常轨迹检测算法（Intersection-Based Anomalous Trajectories Detection,IBATD）。该算法将GPS数据进行地图匹配,并将匹配后的GPS轨迹以路口的形式描述,再以多叉树的方式实现轨迹聚类。通过计算待测轨迹的轨迹概率,并与给定异常阈值进行比较,将轨迹分类为正常或异常。与经典的基于Hausdorff距离的谱聚类算法相比,多叉树轨迹聚类具有更准确的轨迹模型库、更快的运算速度以及实时检测的特点。     

基于小波聚类的终端区进场轨迹模式识别

为改善终端区航空器轨迹聚类方法中存在的自动化程度低、无法精确识别异常轨迹的不足,提出基于小波聚类的进场轨迹模式识别方法。首先,建立基于3D空间网格的轨迹相似性矩阵,推导得到轨迹间相似特征子空间,进一步构建轨迹相似特征2D图模型。通过特征图模型的数字化、小波变换与聚类,实现对盛行交通流模式以及异常交通流轨迹的识别。实例分析在无人工指导情况下,从352条进场轨迹中识别出4个类的331条盛行交通流轨迹,以及21条异常轨迹。实验结果证明,该算法克服了目前航空器轨迹聚类领域需要人工确定类数以及难以识别异常轨迹的不足。     

基于轨迹多特征的运动模式学习及异常检测

为提高轨迹分类和异常检测的准确率,充分利用轨迹特征信息,提出基于轨迹多特征的运动模式分类和异常检测方法。首先通过由粗到细的分层聚类来提取轨迹运动模式,每层分别采用Bhattacharyya距离和基于线段插值的改进Hausdorff距离衡量轨迹间运动方向和空间位置的相似度,并引入Laplacian映射以降低计算复杂度并自动确定每层聚类数目。在此基础上,同时考虑待测轨迹与运动模式在起点分布、位置和方向上的差异,通过学习的起点分布模型和基于位置距离和方向距离的分类器在线判断起点、全局和局部异常。实验验证了提出的轨迹聚类算法和异常检测方法在聚类准确率和异常识别率上更优于传统方法。     

Trajectory outlier detection approach based on common slices sub-sequence

Trajectory outlier detection is one of the most popular trajectory data mining topics. It helps researchers obtain a lot of valuable information that can be used as important guidance in monitoring and forecasting. Existing methods have difficulty in detecting the outlying trajectories with continuous multi-segment exception. To address the problem, in this paper, we propose a novel trajectory outlier detection algorithm based on common slices sub-sequence (TODCSS). For each trajectory, the direction-code sequence is firstly calculated based on the direction of each trajectory segment. Secondly, the corresponding sequence consisting of trajectory slices is obtained by inflection point segmentation. And then, the common slices sub-sequences between two trajectories are found to measure their distance. Finally, the slice outliers and trajectory outliers are detected based on the new CSS distance calculation. Both the intuitive visualization presentation and the experimental results on real Atlantic hurricane dataset, real-life mobility trajectory dataset of taxis in San Francisco and synthetic labeled dataset show that the proposed TODCSS algorithm effectively detects slice and trajectory outliers, and improves accuracy and stability in trajectory outlier detection.     

基于自适应阈值的船舶轨迹异常点检测算法

定位技术的快速发展催生了轨迹大数据,轨迹数据中总是存在着明显偏离轨迹的异常点。检测出轨迹中的异常点对提高数据质量和后续知识发现精度至关重要。目前轨迹异常点检测算法主要为恒定速度阈值法,没有考虑目标在不同时刻运动状态的变化,仅能检测出速度超出指定阈值的一部分异常点,甚至出现检测错误的情况,算法鲁棒性较差。针对现有问题,本文提出一种基于自适应阈值的轨迹异常点检测算法（Trajectory Outlier Detection Algorithm based on adaptive Threshold, TODAT）。TODAT算法充分考虑了目标在一段时间内的运动信息和观测噪声的影响,采用局部阈值窗和均值滤波窗来计算阈值和速度,同时又引入了经济航速阈值和连续异常点放回机制。基于真实船舶数据的实验结果表明,本文算法可根据轨迹数据得到自适应的阈值,有效检测出全部异常点,大幅度提高轨迹数据的质量。     

基于预测模型的轨迹数据压缩方法

针对目前路网环境下海量轨迹数据压缩效率低下的问题,提出了一种基于预测模型的轨迹数据压缩方法（CTPM）。通过将轨迹数据的时间信息和空间信息分别进行压缩,使得压缩后的轨迹数据在空间维度上无损,并且在时间维度上误差有界,以此提高压缩效率。在空间方面,首先利用部分匹配预测（PPM）算法通过轨迹已经行驶的部分路段对其下一时刻可能的位置进行预测;然后通过删除预测成功的路段来减少轨迹数据的存储代价。在时间方面,首先利用轨迹通行状况具有周期性的特点,构建了不同时间区间的通行速度统计模型,来预测移动对象进入下一路段所需要的时间;然后删除预测时间误差小于给定阈值的路段数据来进行压缩处理。实验结果显示,与已有的基于路网的并行轨迹压缩（PRESS）算法相比,CTPM的空间压缩比和时间压缩比平均分别提高了43%和1.5%,同时时间压缩误差减小了9.5%。实验结果表明所提算法在提高压缩比的同时有效地降低了压缩时间和压缩误差。     

基于R-Tree的高效异常轨迹检测算法

提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1) 为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2) 针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义.     

基于核主成分分析的异常轨迹检测方法

针对现有算法不能有效应用于多因素轨迹异常检测的问题,提出基于核主成分分析(KPCA)的异常轨迹检测方法。首先,为了改善轨迹特征提取的效果,采用KPCA对轨迹数据进行空间转换,将非线性空间转换到高维线性空间;其次,为了提高异常检测的准确率,采用一类支持向量机对轨迹特征数据进行无监督学习和预测;最终检测出具有异常行为的轨迹。采用大西洋飓风数据对算法进行测试,实验结果表明,该算法能够有效提取出轨迹特征,并且与同类算法相比,该算法在多因素轨迹异常检测方面具有更好的检测效果。     

基于轨迹分段LDA主题模型的视频异常行为检测方法

基于目标轨迹的异常行为检测算法忽略了轨迹内部信息,容易导致异常检测虚警率偏高。为解决该问题,提出一种基于轨迹分段主题模型的视频异常行为检测方法。首先将目标原始轨迹根据轨迹转角分段,然后采用分段量化的方式提取轨迹片段中包含的行为特征信息,接着通过潜在狄利克雷分配(LDA)主题模型建模发掘目标轨迹之间的时空关系,最后通过学习所构建的模型并结合贝叶斯理论进行行为模式分析和异常行为检测。分别对两个视频场景进行了目标行为模式分析和异常行为检测的仿真实验,检测出了场景内多种异常行为模式。实验结果表明,通过结合轨迹分段与LDA主题模型,该算法能够充分挖掘目标轨迹内部的行为特征信息,识别多种异常行为模式,并且能提高对异常行为检测的准确率。     

基于全息熵的空间离群点挖掘算法研究

基于距离和基于密度的离群点检测算法受到维度和数据量伸缩性的挑战, 而空间数据的自相关性和异质性决定了以属性相互独立和分类属性的基于信息理论的离群点检测算法也难以适应空间离群点检测, 因此提出了基于全息熵的混合属性空间离群点检测算法。算法利用区域标志属性进行区域划分, 在区域内利用空间关系确定空间邻域, 并用R*-树进行检索。在此基础上提出了基于全息熵的空间离群度的度量方法和空间离群点挖掘算法, 有效解决了混合属性的离群度的度量和离群点的挖掘问题。由于实现区域划分有利于并行计算, 从而可适应大数据量的计算。理论和实验证明, 所提算法在计算效率和实验结果的可解释性方面均具有优势。     

基于划分的高效异常轨迹检测

为了在海量轨迹数据库中高效准确地挖掘出异常轨迹,提出了基于划分的异常轨迹检测算法。该算法通过计算局部轨迹点之间的匹配程度来探测异常轨迹,将异常轨迹检测由形状匹配问题转化为传统的异常点检测问题,并设计了一种基于空间划分的网格索引结构,提高算法的运行效率。实验证明,该算法不仅具有较高的挖掘效率,而且能够检测出更具实际意义的异常轨迹。